Рекурсивные функции и лямбда исчисление а черча

Обновлено: 30.06.2024

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

λ-исчисление может рассматриваться как семейство прототипных языков программирования. Их основная особенность состоит в том, что они являются языками высших порядков. Тем самым обеспечивается систематический подход к исследованию операторов, аргументами которых могут быть другие операторы, а значением также может быть оператор. Языки в этом семействе являются функциональными, поскольку они основаны на представлении о функции или операторе, включая функциональную аппликацию и функциональную абстракцию. λ-исчисление реализовано Джоном Маккарти в языке Лисп. Вначале реализация идеи λ-исчисления была весьма громоздкой. Но по мере развития Лисп-технологии (прошедшей этап аппаратной реализации в виде Лисп-машины) идеи получили ясную и четкую реализацию.

Содержание

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

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

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

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

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

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

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

β-редукция

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

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

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

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

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

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

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

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

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

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

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

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

В лямбда-исчислении, Y g — неподвижная точка g; продемонстрируем это:

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).

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

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

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

См. также

Напишите отзыв о статье "Лямбда-исчисление"

Примечания

↑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 с.

Отрывок, характеризующий Лямбда-исчисление

– Приехали. Жюли Друбецкая говорила мне. Я поехал к ним и не застал. Они уехали в подмосковную.

По сравнению с языками функционального программирования, подобным Ilaskell, в лямбда-исчислении не хватает чисто практических средств, позволяющих удобно записывать функции. Прежде всего, бросается в глаза отсутствие средств описания рекурсивных функций. Действительно, рекурсивные обращения всегда происходят с использованием имени функции, однако лямбда-исчисление — это язык для описания безымянных функций! Конечно, иногда мы можем обойтись и без применения рекурсии, если имеется достаточно богатый набор встроенных функций. Например, имея функцию высшего порядка foldr в качестве одной из встроенных функций, мы можем написать функцию вычисления факториала натурального числа и без использования рекурсии. Аналогично функция свертки дерева tfoldr позволила нам в гл. 4 написать без использования рекурсии функцию линеаризации дерева linearize.

Имея достаточно богатый набор мощных функций высшего порядка, можно всегда обойтись без использования рекурсивных вызовов (такой стиль программирования был, например, использован Джоном Бэкусом при создании системы программирования FP). Однако чистое лямбдаисчисление не предполагает использования встроенных функций вообще! Возникает вопрос: достаточно ли средств лямбда-исчисления для того, чтобы выразить в нем всевозможные вычислимые функции, если в нем невозможно обычным образом задавать рекурсивные функции, а встроенных функций, позволяющих обойти эту проблему, нет вообще?

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

Пусть у нас имеется функция, в определении которой есть прямое рекурсивное обращение к себе, например, такое, как определение функции вычисления факториала в языке Haskell: fact n = if n == 0 then 1 else n * fact(n-l)

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

fact = An.IF (eqO п) 1 (* п (fact (- п 1)))

Здесь мы пока по-прежнему использовали задание имени для функции fact, чтобы выразить рекурсию. Построим теперь новую функцию, в которой вызываемая функция fact будет аргументом: sFact = Af.An.IF (eqO n) 1 (* n (f (- n 1) ) )

Конечно, эта новая функция не будет тем факториалом, который мы пытаемся построить, хотя бы потому, что ее аргументом является не целое число, а некоторая функция, однако она некоторым вполне определенным образом связана с той функцией вычисления факториала, которую мы пытаемся построить. Зададимся задачей найти такую функцию f, что она является неподвижной точкой определенной нами функции sFact, т.е. такую f, что выполнено равенство f = sFact f. Очевидно, что если такую неподвижную точку удастся найти, то найденная функция f как раз и будет тем самым факториалом, который мы ищем, поскольку будет выполнено равенство

f = sFact f = An.IF (eqO n) 1 (* n (f (- n 1)))

Итак, задача нахождения функции, эквивалентной заданной рекурсивной функции, свелась к задаче построения неподвижной точки для некоторой другой функции. Кажется, что эту задачу — задачу нахождения неподвижной точки — в общем виде решить не удастся. A priori вообще не ясно, всегда ли такая неподвижная точка существует. Однако оказывается, что удается построить функционал, который для заданного функционального аргумента вычисляет его неподвижную точку. Если обозначить через Y такой функционал нахождения неподвижной точки, то для любой функции f должно быть справедливо равенство Y f = f (Y f). Другими словами, результатом применения функции Y к функции f должно быть такое значение х, что х = f (х). Одну из таких функций предложил Хаскелл Карри, и теперь эта функция в его честь называется Y-комбинатором Карри. Вот запись этой функции в нотации лямбда-исчисления:

Y = Ah. (Ax.h (х х) ) (Ax.h (х х) )

Проверим, действительно ли для этой функции выполнено равенство

Y f = f (Y f). Для этого запишем выражение Y f и попробуем привести его к СЗНФ. После того как вместо Y будет подставлено соответствующее лямбда-выражение, мы сможем выполнить один шаг р-редукции, и в результате получим выражение (Хх. f (х х) ) (Хх. f (х х) ). Это выражение еще не находится в СЗНФ, так что мы можем выполнить еще один шаг и с помощью Р-редукции привести его к виду f ( (Хх. f (х х)) (Хх. f (х х))). Это выражение также не находится в СЗНФ, более того, теперь видно, что привести это выражение к СЗНФ вообще никогда не удастся, так как каждый следующий шаг редукции приводит только к увеличению длины выражения. Однако из проведенных шагов очевидно, что выражение Y f действительно эквивалентно выражению f (Y f), поскольку второе получается из первого за два шага редукций.

Итак, выражение для рекурсивной функции можно получить, если построить некоторое вспомогательное выражение, а затем применить к нему Y-комбинатор Карри. Получившееся при этом выражение не может быть приведено к СЗНФ, однако оно все же будет работать как соответствующая рекурсивная функция. Убедимся в этом, построив описанным способом функцию для вычисления факториала заданного числа, а затем применим ее к конкретному числу, скажем, 2, и проверим, как получается результат вычисления — число 2, равное (fact 2). Для этого попробуем привести к СЗНФ выражение (Y sFact) 2, где Y обозначает Y-комбинатор Карри, a sFact — функцию, приведенную выше, полученную из рекурсивного определения факториала. Последовательные шаги по преобразованию выражения к СЗНФ показаны ниже:

sFact (Y sFact) 2

(Af.An.IF (eqO n) 1 (* n (f (- n 1)))) (Y sFact) 2
(An.IF (eqO n) 1 (* n ( (Y sFact) (- n 1)))) 2

IF (eqO 2) 1 (* 2 ((Y sFact) (- 2 1)))

Остановимся па этом месте. Мы видим, что последовательное выполнение (3- и 6-редукций привело нас от выражения Y sFact 2 к выражению (* 2 (Y sFact 1)). Это уже показывает, что преобразование выражения происходит именно так, как ведет себя рекурсивное вычисление факториала. Продолжим преобразования:

(* 2 (Y sFact 1))
(* 2 (sFact (Y sFact) 1)
(* 2 (Af.An.IF (eqO n) 1 (* n (f (- n 1)))) (Y sFact) 1)
(* 2 (An.IF (eqO n) 1 (* n ((Y sFact) (- n 1)))) 1)
(* 2 (IF (eqO 1) 1 (* 1 ((Y sFact) (- 1 1)))))
(* 2 (* 1 (Y sFact 0)))
(* 2 (* 1 (sFact (Y sFact) 0)))
(* 2 (* 1 ((Xf.Xn.IF (eqO n) 1 (* n (f (- n 1)))) (Y sFact)
0) ) )
(* 2 (* 1 ( (Xn. IF (eqO n) 1 (* n ( (Y sFact) (- n 1)))) 0)))
(* 2 (* 1 (IF (eqO 0) 1 (* 0 ( (Y sFact) (- 0 1))))))
(* 2 (* 1 1))
2

Существенно, что мы использовали при вычислениях нормальный порядок редукций, так как при аппликативном порядке редукций вычисления просто никогда не были бы закончены. Существуют и другие формы Y-комбинаторов, в частности такие, которые применимы и при АИР, однако все другие известные выражения для Y-комбинаторов выглядят сложнее, чем Y-комбинатор Карри.

Если несколько функций определяются таким образом, что в теле каждой из них имеются вызовы других функций из этого набора, то говорят, что мы имеем дело со взаимно-рекурсивными функциями. Этот случай можно свести к прямой рекурсии и, тем самым, выразить в лямбда-исчислении не только прямую, но и взаимную или косвенную рекурсию. Для того чтобы свести взаимную рекурсию к прямой, нам потребуются некоторые встроенные функции, упомянутые в параграфе 9.1. Во-первых, это набор функций кортежирования TUPLE-k, которые составляют кортеж из своих аргументов, и во-вторых, функция INDEX, позволяющая извлечь элемент кортежа по его номеру.

Теперь пусть имеются определения взаимно-рекурсивных функций f 1 = F_x (f_г, f₂, . . . f_n) f₂ = F₂ [f₁, f₂. f_n)

где все F_i — выражения, в которых встречаются рекурсивные обращения к определяемым функциям f_ir f₂, . . . f_n. Прежде всего, образуем новое выражение, представляющее собой кортеж, в котором собраны все определения функций:

Каждая из определяемых функций f_ir f₂, . . . f_n может теперь быть выражена с помощью выделения соответствующего элемента этого кортежа:

поэтому если мы теперь подставим в определение кортежа Т вместо всех вхождений f_i их выражения в виде элемента кортежа, то получим рекурсивное определение для кортежа Т с прямой рекурсией:

F_n( (INDEX 1 T). (INDEX n T) )

Кортеж T теперь может быть представлен, как и раньше, с помощью Y-комбинатора

Y (AT.TUPLE-n F_x ( (INDEX 1 Т), . . . (INDEX n T) ) . . .

F_n((INDEX 1 T). (INDEX n T) ) )

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

Содержание

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

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

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

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

β-редукция

Поскольку выражение обозначает функцию, ставящую в соответствие каждому значение , то для вычисления выражения

$(\lambda x. 2\cdot x + 1)\ 3$

в которое входят и аппликация и абстракция, необходимо выполнить подстановку числа 3 в терм вместо переменной . В результате получается . Это соображение в общем виде записывается как

$(\lambda x.t)\ a = t[x:=a],$

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

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

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

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

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

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

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

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

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

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

В лямбда-исчислении, Y g — неподвижная точка g; продемонстрируем это:

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

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

λ-исчисление реализовано Джоном Маккарти в языке Лисп. В начале реализация идеи λ-исчисления была весьма громоздкой. Но по мере развития Лисп-технологии (прошедшей этап аппаратной реализации в виде Лисп-машины) идеи получили ясную и четкую реализацию.

Содержание

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

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

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

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

β-редукция

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

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

Надо отметить, что если рассматривать лямбда-термы не как функции, а именно как алгоритмы, то данное преобразование не всегда уместно: существуют случаи, когда вычисление \lambda x. f\ x завершается, а вычисление f не завершается.

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

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

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

Эту трудность преодолел Д. С. Скотт, построив понятие области D (полной решётки [1] или, более общо, полного частично упорядоченного множества со специальной топологией) и урезав D → D до непрерывных (в имеющейся топологии) функций [2] . После этого также стало понятно, как можно строить денотационную семантику языков программирования. Это произошло благодаря тому, что с помощью конструкций Скотта можно придать значение также двум важным конструкциям языков программирования — рекурсии и типам данных.

Читайте также: