Лямбда-исчисление
Ля́мбда-исчисле́ние (
Чистое λ -исчисление
править
Чистое
Аппликация и абстракция
правитьВ основу
- Аппликация (лат. applicatio — прикладывание, присоединение) означает применение функции к заданному значению аргумента (то есть вызов функции). Её обычно обозначают , где — функция, а — аргумент. Это соответствует общепринятой в математике записи , которая тоже иногда используется, однако для
λ -исчисления важно то, что трактуется как алгоритм, вычисляющий результат по заданному входному значению. В этом смысле аппликация может рассматриваться двояко: как результат применения к , или же как процесс вычисления этого результата. Последняя интерпретация аппликации связана с понятиемβ -редукции.
- Абстракция или
λ -абстракция (лат. abstractio — отвлечение, отделение), в свою очередь, строит функции по заданным выражениям. Именно, если — выражение, свободно[англ.] содержащее , тогда запись означает:λ функция от аргумента , которая имеет вид , и обозначает функцию . Здесь скобки не обязательны и использованы для ясности, так как точка является частью нотации и отделяет имя связанной переменной от тела функции. Таким образом, с помощью абстракции можно конструировать новые функции. Требование, чтобы свободно входило в , не обязательно — в этом случае обозначает функцию , то есть такую, которая игнорирует свой аргумент.
α -эквивалентность
править
Основная форма эквивалентности, определяемая в лямбда-термах, это альфа-эквивалентность. Например, и - это альфа-эквивалентные лямбда-термы, которые оба представляют одну и ту же функцию — а именно, функцию тождества . Термы и не являются альфа-эквивалентными, так как являются свободными переменными.
Вообще говоря, -преобразование - это переименование связанных переменных, не меняющее «смысла» терма. Структурно, два
Для абстракций, терм -эквивалентен , если это в котором все свободные появления заменены на , при условии, что 1.) не входит свободно в , и 2.) не входит свободно ни в одну абстракцию внутри (если такие есть).
Требование, чтобы не была свободной переменной в — существенно, так как иначе она окажется «захваченной» абстракцией после -преобразования, и из свободной переменной в превратится в связанную переменную в .
Второе требование необходимо чтобы предотвратить случаи подобные тому, когда, например, является частью . Тогда необходимо произвести -преобразование такой абстракции, например, в данном случае, в .
β -редукция
править
Применение некой функции к некоему аргументу выражается в -исчислении как аппликация -терма, выражающего эту функцию, и -терма аргумента. Например, применение функции к числу 3 выражается аппликацией
в которой на первом месте находится соответствующая абстракция. Поскольку эта функция ставит в соответствие каждому значение , для вычисления результата необходимо заменить каждое свободное появление переменной в терме на терм 3.
В результате получается . Это соображение в общем виде записывается как
и носит название
η -преобразование
править
-преобразование выражает ту идею, что две функции являются идентичными тогда и только тогда, когда, будучи применёнными к любому аргументу, дают одинаковые результаты.
-преобразование переводит друг в друга формулы и , но только если не появляется свободно в . Иначе, свободная переменная в после преобразования стала бы связанной внешней абстракцией , и наоборот; и тогда применение этих двух выражений сводилось бы -редукцией к разным результатам.
Перевод в называют -редукцией, а перевод в — -экспансией.
Каррирование (карринг)
правитьФункция двух переменных и может быть рассмотрена как функция одной переменной , возвращающая функцию одной переменной , то есть как выражение . Такой приём работает точно так же для функций любой арности. Это показывает, что функции многих переменных могут быть выражены в
Соответственно, аппликация 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-х годов преодолел Дана Скотт, построив понятие области (изначально на полных решётках[1], в дальнейшем обобщив до полного частично упорядоченного множества со специальной топологией) и урезав до непрерывных в этой топологии функций[2]. На основе этих построений была создана денотационная семантика[англ.] языков программирования, в частности, благодаря тому, что с помощью них можно придать точный смысл таким двум важным конструкциям языков программирования, как рекурсия и типы данных.
Связь с рекурсивными функциями
правитьРекурсия — это определение функции через саму себя; на первый взгляд, лямбда-исчисление не позволяет этого, но это впечатление обманчиво. Например, рассмотрим рекурсивную функцию , вычисляющую факториал:
- f(n) = 1, if n = 0; else n × f(n - 1).
Эта функция не может быть выражена
Тем не менее,
- 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
Итак, каждое определение рекурсивной функции может быть представлено как неподвижная точка соответствующего закрытого функционала описывающего «один вычислительный шаг» рекурсивной функции. Следовательно, используя , каждое рекурсивное определение может быть выражено как лямбда-выражение (
В языках программирования
правитьВ языках программирования под «
См. также
правитьПримечания
править- ↑ 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.
Литература
править- Барендрегт, Хенк. Ламбда-исчисление. Его синтаксис и семантика. — М.: Мир, 1985. — 606 с. — 4800 экз.
Для улучшения этой статьи желательно:
|