Инструменты пользователя

Инструменты сайта


examination:flp:question7

7. Определение и вызов функции в языке РС – Лисп. Иерархия вызовов.

Чтобы программировать с помощью функций, нужно иметь возможность определить достаточно богатое множество основных функций и затем использовать композицию, чтобы иметь возможность определить новые функции в терминах исходных. Возникает вопрос, нужно ли еще что-нибудь, кроме набора исходных функций и возможности составлять из них композиции для программирования. Наш ответ гласит, что ничего больше не требуется.

Суть функционального программирования в том, что программы состоят исключительно из функций без побочных эффектов, которые вычисляют свои значения исключительно на основе своих аргументов. Преимущество функционального стиля программирования в том, что он облегчает понимание программы. Устранение побочных эффектов ведёт к устранению практически всех возможностей удалённого воздействия. Т.к. результат функции определяется её аргументами, поведение функции легче понять и протестировать. Например, когда вы видите выражение (+ 3 4), вы знаете, что результат целиком задаётся определением функции + и переданными аргументами 3 и 4. Вам не надо беспокоиться о том, что могло произойти в программе до этого, т.к. нет ничего, что могло бы изменить результат вычисления выражения.

Функции, работающие с числами, естественным образом являются функциональными, т.к. числа неизменяемы. Списки же, как вы видели раннее, могут меняться, при применении функции SETF над ячейками списка. Тем не менее, списки могут рассматриваться как функциональные типы данных, если считать, что их значение определяется элементами, которые они содержат. Так, любой список вида (1 2 3 4) функционально эквивалентен любому другому списку, содержащему эти четыре значения, независимо от того, какие cons-ячейки используются для представления списка. И любая функция, которая принимает списки в качестве аргументов и возвращает значение, основываясь исключительно на содержании списка, могут считаться функциональными. Например, если функции REVERSE передать список (1 2 3 4), она всегда вернёт (4 3 2 1). Различные вызовы REVERSE с функционально-эквивалентными аргументами вернут функционально-эквивалентные результаты. Другой аспект функционального программирования, который я рассматриваю в разделе «Отображение», это использование функций высших порядков: функций, которые используют другие функции, как данные, принимая их в качестве аргументов или возвращая в качестве результата.

Большинство функций Common Lisp для работы со списками написаны в функциональном стиле. Позднее мы обсудим как совмещать функциональный подход к программированию с другими подходами, но сначала вы должны понять некоторые тонкости функционального подхода применительно к спискам.

Т.к. большинство функций для работы со списками написаны в функциональном стиле, они могут возвращать результаты, которые имеют общие cons-ячейки с их аргументами. Возьмём конкретный пример: функция APPEND принимает любое число списков в качестве аргументов и возвращает новый список, содержащий все элементы списков-аргументов, например:

(append (list 1 2) (list 3 4))

=⇒ (1 2 3 4)

С точки зрения функционального подхода, задача функции APPEND - вернуть список (1 2 3 4) не изменяя ни одну из cons-ячеек в списках-аргументах (1 2) и (3 4). Очевидно, что это можно сделать создав новый список, состоящий из четырёх новых cons-ячеек. Однако в этом есть лишняя работа. Вместо этого APPEND на самом деле создаёт только две новые cons-ячейки, чтобы хранить значения 1 и 2, соединяя их вместе и делая ссылку из CDR второй ячейки на первый элемент последнего аргумента - списка (3 4). После этого функция возвращает cons-ячейку содержащую 1. Ни одна из входных cons-ячеек не была изменена, и результатом, как и требовалось, является список (1 2 3 4). Единственная хитрость в том, что результат, возвращаемый функцией APPEND имеет общие cons-ячейки со списком (3 4).

Примеры выражений:

lambda x.x - тождественная функция со значением просто равным ее аргументу;

lambda x.c - постоянная функция со значением, равным c, вне зависимости от аргумента;

lambda x.f(f(x)) - композиция функции f с самой собой, т.е. функция со значением, равным f(f(x)) для аргумента x.

Широкие возможности рассмотренного способа обозначения во многом объясняется возможностью представления с его помощью функций более высоких порядков.

Например, запись lambda f.lambda x.(f(x)) соответствует функции (высшего порядка), значение которой для аргумента x равно функции, получаемой путем композиции функции f с самой собой.

Лямбда-исчисление дает не просто форму записи, но также правила эквивалентных преобразований лямбда-выражений. Наиболее важным является правило betta-редукции, при помощи которого можно упрощать выражения вида:

lambda (x.e1)(e2)

Например, выражение (lambda x.f(x,x))(a) betta-редуцируется в f(a,a).

В сочетании с некоторыми простейшими функциями лямбда-исчисление дает оригинальный способ определения множества всех эффективно вычислимых функций от неотрицательных целых чисел - следовательно, в этом смысле оно эквивалентно машине Тьюринга и аппарату теории рекурсивных функций.

В конструкцию вводимой функции могут, в свою очередь, входить функциональные подвыражения. Тогда аргументы вычисляемой функции заменяются на новые вычисления, ведущие к определению значений этих аргументов. Таким путём вычисления сводятся в конечном счёте к вычислению выражений, значения которых, как, например констант, можно определить непосредственно. Приведём пример:

(1+2)*(3+4)

Вычисляется сначала первая задача (1 + 2) и результат определяет объект (в данном случае число), затем второй элемент списка интерпретируется как функция определенная именно для чисел, затем эта функция вычисляет параллельно все оставшиеся аргументы и применяется непосредственно. Если эти аргументы будут вложенными вызовами функции или другая вычислимая форма, то перед её вычислением определяются значения её аргументов и т.д.

Наконец, опустившись на самый нижний уровень, можно начать в качестве значений аргументов предыдущего уровня подставлять значения, даваемые вложенными вычислениями. Последним возвращается значение всего выражения. Как и в математике, в Лиспе в первую очередь вычисляются выражения, заключённые в скобки:

(1 + 2) * (3 + 4))

  ;(1+2)*(3+4)

21

(1 + 2) * (1 * (2 + 3)))

  ;(1+2)*(1*(2+3))

15

examination/flp/question7.txt · Последние изменения: 2014/01/15 12:17 (внешнее изменение)