Иллюстрированный самоучитель по введению в экспертные системы


Приложение функции и лямбда-исчисление



Для того чтобы разобраться в связи между лямбда-исчислением и языком 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)).


Начало  Назад  Вперед



Книжный магазин