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

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

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

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

 Аппликация ( — прикладывание, присоединение) означает применение функции к заданному значению аргумента (то есть вызов функции). Её обычно обозначают , где  — функция, а  — аргумент. Это соответствует общепринятой в математике записи , которая тоже иногда используется, однако для λ-исчисления важно то, что  трактуется как алгоритм, вычисляющий результат по заданному входному значению. В этом смысле аппликация   может рассматриваться двояко: как результат применения  к , или же как процесс вычисления этого результата. Последняя интерпретация аппликации связана с понятием β-редукции.

 Абстракция или λ-абстракция ( — отвлечение, отделение), в свою очередь, строит функции по заданным выражениям. Именно, если  — выражение,  содержащее , тогда запись  означает: λ функция от аргумента , которая имеет вид , и обозначает функцию . Здесь скобки не обязательны и использованы для ясности, так как точка является частью нотации и отделяет имя связанной переменной от тела функции. Таким образом, с помощью абстракции можно конструировать новые функции. Требование, чтобы  свободно входило в , не обязательно — в этом случае  обозначает функцию , то есть такую, которая игнорирует свой аргумент.

α-эквивалентность 
Основная форма эквивалентности, определяемая в лямбда-термах, это альфа-эквивалентность. Например,  и  это альфа-эквивалентные лямбда-термы которые оба представляют одну и ту же функцию — а именно, функцию тождества . Термы  и  не являются альфа-эквивалентными, так как являются свободными переменными.

Вообще говоря, -преобразование это переименование связанных переменных, не меняющее «смысла» терма. Структурно, два λ-терма -эквивалентны если это один и тот же терм, либо если какие-либо их составляющие термы соответстветственно -эквивалентны.

Для абстракций, терм  -эквивалентен , если  это  в котором все свободные появления  заменены на , при условии, что 1.)  не входит свободно в , и 2.)  не входит свободно ни в одну абстракцию  внутри  (если такие есть).

Требование, чтобы  не была свободной переменной в  — существенно, так как иначе она окажется «захваченной» абстракцией  после -преобразования, и из свободной переменной в  превратится в связанную переменную в .

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

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

В результате получается . Это соображение в общем виде записывается как
 
и носит название β-редукция. Выражение вида , то есть применение абстракции к некоему терму, называется редексом (redex). Несмотря на то, что β-редукция по сути является единственной «существенной» аксиомой λ-исчисления, она приводит к весьма содержательной и сложной теории. Вместе с ней λ-исчисление обладает свойством полноты по Тьюрингу и, следовательно, представляет собой простейший язык программирования.

η-преобразование 
-преобразование выражает ту идею, что две функции являются идентичными тогда и только тогда, когда, будучи применёнными к любому аргументу, дают одинаковые результаты.

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

Перевод  в  называют -редукцией, а перевод  в  — -экспансией.

Каррирование (карринг) 
Функция двух переменных  и   может быть рассмотрена как функция одной переменной , возвращающая функцию одной переменной , то есть как выражение . Такой приём работает точно так же для функций любой арности. Это показывает, что функции многих переменных могут быть выражены в λ-исчислении и являются «синтаксическим сахаром». Описанный процесс превращения функций многих переменных в функцию одной переменной называется карринг (также: каррирование), в честь американского математика Хаскелла Карри, хотя первым его предложил Моисей Шейнфинкель (1924).

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

   (λxy.    ...x...y... )  a  b   =
   (λx.λy.  ...x...y... )  a  b   =
   (λx.(λy. ...x...y... )) a  b   =
 (((λx.(λy. ...x...y... )) a) b)  =
       (λy. ...a...y... )     b   =
            ...a...b...

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

Эту трудность в начале 1970-х годов преодолел Дана Скотт, построив понятие области  (изначально на полных решётках, в дальнейшем обобщив до полного частично упорядоченного множества со специальной топологией) и урезав  до непрерывных в этой топологии функций. На основе этих построений была создана  языков программирования, в частности, благодаря тому, что с помощью них можно придать точный смысл таким двум важным конструкциям языков программирования, как рекурсия и типы данных.

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

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

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

Эта функция не может быть выражена λ-термом (λn.(1, if n = 0; else n × (f (n-1)))), так как в нём f является свободной переменной. Функция  ссылается на саму себя посредством ссылки на своё имя, но в лямбда-исчислении у λ-термов имен нет.

Тем не менее, λ-термы могут быть переданы как аргумент, в том числе и самим себе. Терм-функция может получить сам себя как аргумент, который окажется связанным с его параметром. Как правило, этот параметр стоит на первом месте. Когда он связан с самой функцией, получается новый λ-терм, выражающий уже саму рекурсивную функцию. Для этого параметр, ссылающийся на себя (здесь обозначен как ), обязательно должен быть передан явным образом как аргумент при рекурсивном вызове (как ):

 U := λh. h h
 F := U (λh. λn. (1, if n = 0; else n × ((h h) (n-1))))

где  — это комбинатор само-аппликации, .

Этот приём позволяет решить каждую конкретную проблему, как вычисление факториала здесь, создавая рекурсивную функцию через изменение λ-терма, для его явной передачи самому себе как добавочного аргумента. Но решение в общем виде также возможно. Несколькими несложными преобразованиями получается (подразумевая каррирование):

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

Это эквивалентное выражение состоит из аппликации двух независимых λ-термов, где второй — это просто лямбда-выражение рекурсивной функции без изменений, но с абстрагированным рекурсивным вызовом . А первый это некий комбинатор, называемый :

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

Этот комбинатор создает рекурсивную функцию из аргумента, являющегося закрытым (то есть в котором нет свободных переменных) λ-термом исходного выражения функции (то есть без удвоения параметра). Таким образом,

 Y g = (λh. g (h h)) (λh. g (h h))
     = g ((λh. g (h h)) (λh. g (h h)))
     = g (Y g)

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

 F = Y (λr. λn. (1, if n = 0; else n × (r (n-1))))
   = Y G
   = G (Y G)
   = (λr. λn. (1, if n = 0; else n × (r (n-1)))) (Y G)
   = (    λn. (1, if n = 0; else n × (Y G (n-1)))) 
   = (    λn. (1, if n = 0; else n × (F   (n-1)))) 
   = G F

Итак,  — это закрытый функционал, то есть λ-терм, вызывающий свой аргумент в качестве функции; его неподвижная точка — это функция (здесь, ), которая передаётся ему в качестве аргумента; а вызов той же самой функции и есть рекурсивный вызов.

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

 Y := λg. (λh. g (h h)) (λh. g (h h))

Используя стандартные комбинаторы  и ,

 Y g = U (λh. g (U h)) = U (λh. B g U h)
     = U (B g U) = U (C B U g) 
     = B U (C B U) g

В самом деле:

 U (B g U) = B g U (B g U)
     = g (U (B g U))
     = g (Y g)

Итак, чтобы определить факториал как рекурсивную функцию, мы можем просто написать , где  — число, для которого вычисляется факториал. Пусть , получаем:

 Y G 4
 Y (λrn.(1, if n = 0; else n×(r (n-1)))) 4
 (λrn.(1, if n = 0; else n×(r (n-1)))) (Y G) 4
 (λn.(1, if n = 0; else n×(Y G (n-1)))) 4
 1, if 4 = 0; else 4×(Y G (4-1))
 4×(Y G 3)
 4×(G (Y G) 3)
 4×((λrn.(1, if n = 0; else n×(r (n-1)))) (Y G) 3)
 4×(1, if 3 = 0; else 3×(Y G (3-1)))
 4×(3×(G (Y G) 2))
 4×(3×(1, if 2 = 0; else 2×(Y G (2-1))))
 4×(3×(2×(G (Y G) 1)))
 4×(3×(2×(1, if 1 = 0; else 1×(Y G (1-1)))))
 4×(3×(2×(1×(G (Y G) 0))))
 4×(3×(2×(1×(1, if 0 = 0; else 0×(Y G (0-1))))))
 4×(3×(2×(1×(1))))
 24

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

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

См. также 
 Типизированное λ-исчисление
 Комбинаторная логика
 Функциональное программирование
 Теорема Чёрча — Россера

Примечания

Литература 
 

Теория алгоритмов
Лямбда-исчисление
Модели вычислений
Формальные методы