|
|
|
4.3.3.
Приложение функции и лямбда-исчисление
Для того чтобы
разобраться в связи между лямбда-исчислением и языком 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-программа ее может читать, записывать и обрабатывать
точно так же, как любой другой набор данных.
|
|
|
