Лямбда-исчисление

Ля́мбда-исчисле́ние (λ-исчисление) — формальная система, разработанная американским математиком Алонзо Чёрчем для формализации и анализа понятия вычислимости.

Чистое λ-исчисление

Чистое λ-исчисление, термы которого, называемые также объектами («обами»), или λ-термами, построены исключительно из переменных применением аппликации и абстракции. Изначально наличие каких-либо констант не предполагается.

Аппликация и абстракция

В основу λ-исчисления положены две фундаментальные операции:

Аппликация (лат. applicatio — прикладывание, присоединение) означает применение или вызов функции по отношению к заданному значению. Её обычно обозначают [math]\displaystyle{ f\ a }[/math], где [math]\displaystyle{ f }[/math] — функция, а [math]\displaystyle{ a }[/math] — аргумент. Это соответствует общепринятой в математике записи [math]\displaystyle{ f(a) }[/math], которая тоже иногда используется, однако для λ-исчисления важно то, что [math]\displaystyle{ f }[/math] трактуется как алгоритм, вычисляющий результат по заданному входному значению. В этом смысле аппликация [math]\displaystyle{ f }[/math] к [math]\displaystyle{ a }[/math] может рассматриваться двояко: как результат применения [math]\displaystyle{ f }[/math] к [math]\displaystyle{ a }[/math], или же как процесс вычисления [math]\displaystyle{ f\ a }[/math]. Последняя интерпретация аппликации связана с понятием β-редукции.

Абстракция или λ-абстракция (лат. abstractio — отвлечение, отделение) в свою очередь строит функции по заданным выражениям. Именно, если [math]\displaystyle{ t\equiv t[x] }[/math] — выражение, свободно^[en] содержащее [math]\displaystyle{ x }[/math], тогда запись [math]\displaystyle{ \ \lambda x.t[x] }[/math] означает: λ функция от аргумента [math]\displaystyle{ x }[/math], которая имеет вид [math]\displaystyle{ t[x] }[/math], обозначает функцию [math]\displaystyle{ x\mapsto t[x] }[/math]. Таким образом, с помощью абстракции можно конструировать новые функции. Требование, чтобы [math]\displaystyle{ x }[/math] свободно входило в [math]\displaystyle{ t }[/math], не очень существенно — достаточно предположить, что [math]\displaystyle{ \lambda x.t\equiv t }[/math], если это не так.

α-эквивалентность

Основная форма эквивалентности, определяемая в лямбда-термах, это альфа-эквивалентность. Например, [math]\displaystyle{ \lambda x.x }[/math] и [math]\displaystyle{ \lambda y.y }[/math]: альфа-эквивалентные лямбда-термы и оба представляют одну и ту же функцию (функцию тождества). Термы [math]\displaystyle{ x }[/math] и [math]\displaystyle{ y }[/math] не альфа-эквивалентны, так как они не находятся в лямбда-абстракции.

β-редукция

Поскольку выражение [math]\displaystyle{ \lambda x. 2\cdot x + 1 }[/math] обозначает функцию, ставящую в соответствие каждому [math]\displaystyle{ x }[/math] значение [math]\displaystyle{ 2\cdot x + 1 }[/math], то для вычисления выражения

[math]\displaystyle{ (\lambda x. 2\cdot x + 1)\ 3, }[/math]

в которое входят и аппликация и абстракция, необходимо выполнить подстановку числа 3 в терм [math]\displaystyle{ 2\cdot x + 1 }[/math] вместо переменной [math]\displaystyle{ x }[/math]. В результате получается [math]\displaystyle{ 2\cdot 3+1=7 }[/math]. Это соображение в общем виде записывается как

[math]\displaystyle{ (\lambda x.t)\ a = t[x:=a] }[/math]

и носит название β-редукция. Выражение вида [math]\displaystyle{ (\lambda x.t)\ a }[/math], то есть применение абстракции к некому терму, называется редексом (redex). Несмотря на то, что β-редукция по сути является единственной «существенной» аксиомой λ-исчисления, она приводит к весьма содержательной и сложной теории. Вместе с ней λ-исчисление обладает свойством полноты по Тьюрингу и, следовательно, представляет собой простейший язык программирования.

η-преобразование

[math]\displaystyle{ \eta }[/math]-преобразование выражает ту идею, что две функции являются идентичными тогда и только тогда, когда, будучи применёнными к любому аргументу, дают одинаковые результаты. [math]\displaystyle{ \eta }[/math]-преобразование переводит друг в друга формулы [math]\displaystyle{ \lambda x.f\ x }[/math] и [math]\displaystyle{ f }[/math] (только если [math]\displaystyle{ x }[/math] не имеет свободных вхождений в [math]\displaystyle{ f }[/math]: иначе свободная переменная [math]\displaystyle{ x }[/math] после преобразования станет связанной внешней абстракцией или наоборот).

Каррирование (карринг)

Функция двух переменных [math]\displaystyle{ x }[/math] и [math]\displaystyle{ y }[/math] [math]\displaystyle{ f(x,y) = x + y }[/math] может быть рассмотрена как функция одной переменной [math]\displaystyle{ x }[/math], возвращающая функцию одной переменной [math]\displaystyle{ y }[/math], то есть как выражение [math]\displaystyle{ \ \lambda x.\lambda y.x+y }[/math]. Такой приём работает точно так же для функций любой арности. Это показывает, что функции многих переменных могут быть выражены в λ-исчислении и являются «синтаксическим сахаром». Описанный процесс превращения функций многих переменных в функцию одной переменной называется карринг (также: каррирование), в честь американского математика Хаскелла Карри, хотя первым его предложил Моисей Шейнфинкель (1924).

Семантика бестипового λ-исчисления

Тот факт, что термы λ-исчисления действуют как функции, применяемые к термам λ-исчисления (то есть, возможно, к самим себе), приводит к сложностям построения адекватной семантики λ-исчисления. Чтобы придать λ-исчислению какой-либо смысл, необходимо получить множество [math]\displaystyle{ D }[/math], в которое вкладывалось бы его пространство функций [math]\displaystyle{ D \to D }[/math]. В общем случае такого [math]\displaystyle{ D }[/math] не существует по соображениям ограничений на мощности этих двух множеств, [math]\displaystyle{ D }[/math] и функций из [math]\displaystyle{ D }[/math] в [math]\displaystyle{ D }[/math]: второе имеет бо́льшую мощность, чем первое.

Эту трудность в начале 1970-х годов преодолел Дана Скотт, построив понятие области [math]\displaystyle{ D }[/math] (изначально на полных решётках^[1], в дальнейшем обобщив до полного частично упорядоченного множества со специальной топологией) и урезав [math]\displaystyle{ D \to D }[/math] до непрерывных в этой топологии функций^[2]. На основе этих построений была создана денотационная семантика^[en] языков программирования, в частности, благодаря тому, что с помощью них можно придать точный смысл таким двум важным конструкциям языков программирования, как рекурсия и типы данных.

Связь с рекурсивными функциями

Рекурсия — это определение функции через себя; на первый взгляд, лямбда-исчисление не позволяет этого, но это впечатление обманчиво. Например, рассмотрим рекурсивную функцию, вычисляющую факториал:

f(n) = 1, if n = 0; else n × f(n - 1).

В лямбда-исчислении функция не может непосредственно ссылаться на себя. Тем не менее, функции может быть передан параметр, связанный с ней. Как правило, этот аргумент стоит на первом месте. Связав его с функцией, мы получаем новую, уже рекурсивную функцию. Для этого аргумент, ссылающийся на себя (здесь обозначен как [math]\displaystyle{ r }[/math]), обязательно должен быть передан в тело функции.

g := λr. λn.(1, if n = 0; else n × (r r (n-1)))

f := g g

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

Существует несколько определений комбинаторов неподвижной точки. Самый простой из них:

Y = λg.(λx.g (x x)) (λx.g (x x))

В лямбда-исчислении, [math]\displaystyle{ \operatorname{Y\ g} }[/math] — неподвижная точка [math]\displaystyle{ \operatorname{g} }[/math]; продемонстрируем это:

Y g

(λh.(λx.h (x x)) (λx.h (x x))) g (λx.g (x x)) (λx.g (x x)) g ((λx.g (x x)) (λx.g (x x)))

g (Y g)

Теперь, чтобы определить факториал, как рекурсивную функцию, мы можем просто написать [math]\displaystyle{ \operatorname{g\ (Y\ g)} n }[/math], где [math]\displaystyle{ n }[/math] — число, для которого вычисляется факториал. Пусть [math]\displaystyle{ n = 4 }[/math], получаем:

g (Y g) 4
   (λfn.(1, if n = 0; and n·(f(n-1)), if n>0)) (Y g) 4
   (λn.(1, if n = 0; and n·((Y g) (n-1)), if n>0)) 4
   1, if 4 = 0; and 4·(g(Y g) (4-1)), if 4>0
   4·(g(Y g) 3)
   4·(λn.(1, if n = 0; and n·((Y g) (n-1)), if n>0) 3)
   4·(1, if 3 = 0; and 3·(g(Y g) (3-1)), if 3>0)
   4·(3·(g(Y g) 2))
   4·(3·(λn.(1, if n = 0; and n·((Y g) (n-1)), if n>0) 2))
   4·(3·(1, if 2 = 0; and 2·(g(Y g) (2-1)), if 2>0))
   4·(3·(2·(g(Y g) 1)))
   4·(3·(2·(λn.(1, if n = 0; and n·((Y g) (n-1)), if n>0) 1)))
   4·(3·(2·(1, if 1 = 0; and 1·((Y g) (1-1)), if 1>0)))
   4·(3·(2·(1·((Y g) 0))))
   4·(3·(2·(1·((λn.(1, if n = 0; and n·((Y g) (n-1)), if n>0) 0))))
   4·(3·(2·(1·(1, if 0 = 0; and 0·((Y g) (0-1)), if 0>0))))
   4·(3·(2·(1·(1))))
   24

Каждое определение рекурсивной функции может быть представлено как неподвижная точка соответствующей функции, следовательно, используя [math]\displaystyle{ \operatorname{Y} }[/math], каждое рекурсивное определение может быть выражено как лямбда-выражение. В частности, мы можем определить вычитание, умножение, сравнение натуральных чисел рекурсивно.

В языках программирования

В языках программирования под «λ-исчислением» зачастую понимается механизм «анонимных функций» — callback-функций, которые можно определить прямо в том месте, где они используются, и которые имеют доступ к локальным переменным текущей функции (замыкание).

См. также

Примечания

↑ Scott D.S. The lattice of flow diagrams.-- Lecture Notes in Mathematics, 188, Symposium on Semantics of Algorithmic Languages.-- Berlin, Heidelberg, New York: Springer-Verlag, 1971, pp. 311—372.
↑ Scott D.S. Lattice-theoretic models for various type-free calculi. — In: Proc. 4th Int. Congress for Logic, Methodology, and the Philosophy of Science, Bucharest, 1972.

Литература

Барендрегт X. Ламбда-исчисление. Его синтаксис и семантика: Пер. с англ. — М.: Мир, 1985. — 606 с.

[1] Scott D.S. The lattice of flow diagrams.-- Lecture Notes in Mathematics, 188, Symposium on Semantics of Algorithmic Languages.-- Berlin, Heidelberg, New York: Springer-Verlag, 1971, pp. 311—372.

[2] Scott D.S. Lattice-theoretic models for various type-free calculi. — In: Proc. 4th Int. Congress for Logic, Methodology, and the Philosophy of Science, Bucharest, 1972.

[1]

[2]