Приложение функции и лямбда-исчисление
Для того чтобы разобраться в связи между лямбда-исчислением и языком LISP, нужно постоянно держать в уме сформулированное Черчем отличие между денотацией (означиванием) и абстракцией. Так, выражение (X X) означивает конкретное число, которое зависит от значения X. Но то же число можно получить и при помощи функции square(X), которая является абстракцией, поскольку ее можно приложить к разным значениям X. Для того чтобы отличить означивание от абстракции, первое представляется в лямбда-исчислении в таком виде:
(лх)(X х)
Говорят, что лямбда-оператор, X, связан с переменной X, как квантор связывает отдельные переменные в исчислении предикатов. Тогда (ЛХ)(X X) может служить определением функции возведения в квадрат:
square(X) = (лX)(X X)
Теперь для применения функции возведения в квадрат к конкретному числу, скажем 3, мы должны каким-то образом подставить 3 вместо переменной X и оценить (X,Х), в результате чего получим 9. Когда определение функции применяется к аргументу 3, используется правило влияния, получившее наименование лямбда-преобразования. Доложим, что (лХ)М определяет любую лямбда-абстракцию, и пусть S(a, X, М) – результат подстановки X в М.
Лямбда-преобразование. Заменим любую часть( lХ)М в формуле наs(a, x, М), причем ограниченные переменные вм отличны как отх, так и от свободных переменныха.
Если мы полагаем, что ((ЛХ)М) а обозначает применение определения функции (ЛХ)М к аргументу а, то:
((ЛХ)(Х Х))(3) = (3 3) = 9.
Какое же все это имеет отношение к языку LISP? А вот какое. Определение функции возведения в квадрат в LISP выглядит примерно так:
(defun SQUARE (X) (LAMBDA (X) (X X))).
В различных диалектах языка допустимы вариации, но смысл остается тем же. В частности, в диалекте COMMON LISP используется сокращенная форма:
(defun SQUARE (X) (X X)).
В любом случае имя функции, в данном случае SQUARE, ассоциируется в определении с лямбда-выражением. Выражение (LAMBDA (X) (X X)) – это просто синтаксический вариант ((ЛХ) (X X)). Фактически, если определено SQUARE, в любом диалекте LISP имеем:
(SQUARE 3) = ((LAMBDA (X) (X X)) 3) = ((АХ)(Х Х))(3) = 9.
Обратите внимание на то, что LAMBDA не является функцией. Это специальный оператор в лямбда-исчислении.
Синтаксическая форма вызова функции в языке LISP имеет вид:
(<функция> <аргумент>… <аргумент>).
Это не самая сложная синтаксическая форма, а вместе с QUOTE, LAMBDA и условными выражениями этим фактически исчерпывается все, что необходимо знать о синтаксисе языка LISP. Тем, кто по каким-то иррациональным причинам испытывает тягу к запятым, двоеточиям, точкам с запятой, палиндромам вроде (if… ft, case… esac) и тому подобному, будет поначалу трудно свыкнуться с мыслью, что в LISP единственным ограничителем являются круглые скобки.
Программа на языке LISP – это просто структура данных, и другая LISP-программа ее может читать, записывать и обрабатывать точно так же, как любой другой набор данных.