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

Лямбда-исчисление (также пишется как λ -исчисление ) — формальная система в математической логике для выражения вычислений на основе абстракции функций и их применения с использованием связывания и подстановки переменных . Нетипизированное лямбда-исчисление, тема этой статьи, — универсальная модель вычислений , которая может использоваться для моделирования любой машины Тьюринга (и наоборот). Она была введена математиком Алонзо Чёрчем в 1930-х годах в рамках его исследований основ математики . В 1936 году Чёрч нашёл формулировку, которая была логически непротиворечивой, и задокументировал её в 1940 году.

Лямбда-исчисление состоит из построения лямбда-термов и выполнения операций редукции над ними. В простейшей форме лямбда-исчисления термы строятся с использованием только следующих правил: ^[a]

${\textstyle x}$ : Переменная — это символ или строка, представляющая параметр.
${\textstyle (\лямбда xM)}$ : Лямбда-абстракция — это определение функции, принимающее в качестве входных данных связанную переменную (между λ и точкой . ) и возвращающее тело . $x$ ${\textstyle М}$
${\textstyle (М\ Н)}$ : Приложение, применяющее функцию к аргументу . Оба являются лямбда-термами. ${\textstyle М}$ ${\textstyle Н}$ ${\textstyle М}$ ${\textstyle Н}$

Операции по сокращению включают в себя:

${\textstyle (\lambda xM[x])\rightarrow (\lambda yM[y])}$ : α-преобразование, переименование связанных переменных в выражении. Используется для избежания конфликтов имен .
${\textstyle ((\lambda xM)\ N)\rightarrow (M[x:=N])}$ : β-редукция, ^[b] замена связанных переменных выражением аргумента в теле абстракции.

Если используется индексация Де Брейна , то α-преобразование больше не требуется, поскольку не будет никаких коллизий имен. Если повторное применение шагов редукции в конечном итоге заканчивается, то по теореме Чёрча–Россера это даст β-нормальную форму .

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

Объяснение и применение

Лямбда-исчисление является полным по Тьюрингу , то есть представляет собой универсальную модель вычислений , которую можно использовать для моделирования любой машины Тьюринга . ^[3] Его тезка, греческая буква лямбда (λ), используется в лямбда-выражениях и лямбда-термах для обозначения связывания переменной в функции .

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

Лямбда-исчисление имеет приложения во многих различных областях математики , философии , ^[4] лингвистики , ^[5]^[6] и компьютерных наук . ^[7]^[8] Лямбда-исчисление сыграло важную роль в развитии теории языков программирования . Функциональные языки программирования реализуют лямбда-исчисление. Лямбда-исчисление также является актуальной темой исследований в теории категорий . ^[9]

История

Лямбда-исчисление было введено математиком Алонзо Чёрчем в 1930-х годах в рамках исследования основ математики . ^[10]^[c] Первоначальная система оказалась логически противоречивой в 1935 году, когда Стивен Клини и Дж. Б. Россер разработали парадокс Клини–Россера . ^[11]^[12]

Впоследствии, в 1936 году Чёрч выделил и опубликовал только часть, относящуюся к вычислениям, то, что сейчас называется нетипизированным лямбда-исчислением. ^[13] В 1940 году он также представил вычислительно более слабую, но логически последовательную систему, известную как просто типизированное лямбда-исчисление . ^[14]

До 1960-х годов, когда его связь с языками программирования была выяснена, лямбда-исчисление было всего лишь формализмом. Благодаря Ричарду Монтегю и другим лингвистам, применявшим его в семантике естественного языка, лямбда-исчисление начало занимать почетное место как в лингвистике ^[15] , так и в компьютерных науках. ^[16]

Происхождениеλсимвол

Существует некоторая неопределенность относительно причины использования Чёрчем греческой буквы лямбда (λ) в качестве обозначения для абстракции функции в лямбда-исчислении, возможно, отчасти из-за противоречивых объяснений самого Чёрча. Согласно Кардоне и Хиндли (2006):

Кстати, почему Чёрч выбрал обозначение «λ»? В [неопубликованном письме 1964 года Харальду Диксону] он ясно заявил, что оно произошло от обозначения « », которое использовали для абстракции класса Уайтхед и Рассел , сначала изменив « » на « », чтобы отличить абстракцию функции от абстракции класса, а затем изменив « » на «λ» для удобства печати. ${\хэт {x}}$ ${\хэт {x}}$ $\land x$ $\земля$
Это происхождение также было отмечено в [Россер, 1984, стр. 338]. С другой стороны, в последние годы своей жизни Чёрч сказал двум исследователям, что выбор был более случайным: нужен был символ, а λ был выбран просто случайно.

Дэна Скотт также затрагивал этот вопрос в различных публичных лекциях. ^[17] Скотт вспоминает, что однажды он задал вопрос о происхождении символа лямбда бывшему студенту и зятю Чёрча Джону У. Эддисону-младшему, который затем написал своему тестю открытку:

Уважаемый профессор Чёрч,
У Рассела был оператор йота , у Гильберта был оператор эпсилон . Почему вы выбрали лямбду для своего оператора?

По словам Скотта, весь ответ Чёрча состоял в том, чтобы вернуть открытку со следующей аннотацией: « eeny, meeny, miny, moe ».

Неформальное описание

Мотивация

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

\operatorname {квадрат\_суммы} (x,y)=x^{2}+y^{2}

можно переписать в анонимной форме как

(x,y)\mapsto x^{2}+y^{2}

(что читается как « кортеж x и $y$ отображается в » ). ^{[d] Аналогично} $,$ функция ${\textstyle х^{2}+у^{2}}$

\operatorname {id} (x)=x

можно переписать в анонимной форме как

x\mapsto x

где входные данные просто сопоставляются с самими собой. ^[d]

Второе упрощение заключается в том, что лямбда-исчисление использует только функции одного входа. Обычная функция, требующая двух входов, например, функция, может быть переработана в эквивалентную функцию, которая принимает один вход, а в качестве выхода возвращает другую функцию, которая в свою очередь принимает один вход. Например, ${\textstyle \operatorname {квадрат\_сум} }$

(x,y)\mapsto x^{2}+y^{2}

может быть переработан в

x\mapsto (y\mapsto x^{2}+y^{2})

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

Применение функции к аргументам (5, 2) сразу дает ${\textstyle \operatorname {квадрат\_сум} }$

{\textstyle ((x,y)\mapsto x^{2}+y^{2})(5,2)}

{\textstyle =5^{2}+2^{2}}

{\textstyle =29}

тогда как оценка каррированной версии требует еще одного шага

{\textstyle {\Bigl (}{\bigl (}x\mapsto (y\mapsto x^{2}+y^{2}){\bigr )}(5){\Bigr )}(2)}

{\textstyle =(y\mapsto 5^{2}+y^{2})(2)}

// определение было использовано во внутреннем выражении. Это похоже на β-редукцию.

x

5

{\textstyle =5^{2}+2^{2}}

// определение было использовано с . Опять же, аналогично β-редукции.

у

2

{\textstyle =29}

чтобы прийти к тому же результату.

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

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

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

Лямбда-термины

Синтаксис лямбда-исчисления определяет некоторые выражения как допустимые выражения лямбда-исчисления, а некоторые — как недопустимые, так же как некоторые строки символов являются допустимыми программами на языке C , а некоторые — нет. Допустимое выражение лямбда-исчисления называется « лямбда-терм ».

Следующие три правила дают индуктивное определение , которое можно применять для построения всех синтаксически допустимых лямбда-терминов: ^[e]

Переменная $x$ сама по себе является допустимым лямбда-термом.
если $t$ — лямбда-терм, а $x$ — переменная, то ^[f] — лямбда-терм (называемый абстракцией ); $(\лямбда xt)$
если $t$ и $s$ являются лямбда-термами, то — лямбда-терм (называемый приложением ). $(т$ $s)$

Ничто иное не является лямбда-термом. То есть лямбда-терм действителен тогда и только тогда, когда он может быть получен повторным применением этих трех правил. Для удобства некоторые скобки могут быть опущены при написании лямбда-терма. Например, внешние скобки обычно не пишутся. См. § Нотация ниже для явного описания того, какие скобки являются необязательными. Также распространено расширять представленный здесь синтаксис дополнительными операциями, что позволяет осмыслить такие термины, как В центре внимания этой статьи находится чистое лямбда-исчисление без расширений, но лямбда-термины, расширенные арифметическими операциями, используются для пояснительных целей. $\лямбда xx^{2}.$

Абстракция обозначает анонимную функцию § ^[g] , которая принимает один вход $x$ и возвращает $t$ . Например, — это абстракция, представляющая функцию, определенную с использованием термина for $t$ . Имя излишне при использовании абстракции. Синтаксис связывает переменную $x$ в термине $t$ . Определение функции с абстракцией просто «устанавливает» функцию, но не вызывает ее. $\лямбда xt$ $\lambda x.(x^{2}+2)$ $f$ $f(x)=x^{2}+2,$ $х^{2}+2$ $f$ $(\лямбда xt)$

Приложение представляет собой применение функции $t$ к входным данным $s$ , то есть оно представляет собой действие вызова функции t $на$ входных данных $s$ для получения . $т$ $с$ $т(с)$

Лямбда-терм может ссылаться на переменную, которая не была связана, например, терм (который представляет определение функции ). В этом терме переменная $y$ не была определена и считается неизвестной. Абстракция является синтаксически допустимым термином и представляет функцию, которая добавляет свой ввод к еще неизвестному $y$ . $\lambda x.(x+y)$ $f(x)=x+y$ $\lambda x.(x+y)$

Скобки могут использоваться и могут быть необходимы для устранения неоднозначности терминов. Например,

$\lambda x.((\lambda xx)x)$ имеет форму и поэтому является абстракцией, в то время как $\лямбда xB$
$(\lambda x.(\lambda xx))$ $x$ имеет форму и, следовательно, является приложением. $М$ $N$

Примеры 1 и 2 обозначают разные термины, отличающиеся только тем, где находятся скобки. Они имеют разное значение: пример 1 — это определение функции, а пример 2 — это применение функции. Лямбда-переменная $x$ является заполнителем в обоих примерах.

Здесь пример 1 определяет функцию , где есть , анонимная функция , с входными данными ; в то время как пример 2, есть M, примененное к N, где есть лямбда-терм, применяемый к входным данным, которые есть . Оба примера 1 и 2 будут оцениваться как функция тождества . $\лямбда xB$ $Б$ $(\лямбда xx)x$ $(\лямбда xx)$ $x$ $М$ $N$ $М$ $(\lambda x.(\lambda xx))$ $N$ $x$ $\лямбда xx$

Функции, которые работают с функциями

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

Например, лямбда-терм представляет функцию тождества , . Кроме того, представляет константную функцию , функцию, которая всегда возвращает , независимо от входных данных. В качестве примера функции, работающей с функциями, композицию функций можно определить как . $\лямбда xx$ $x\mapsto x$ $\лямбда ху$ $x\mapsto y$ $у$ $\lambda f.\lambda g.\lambda x.(f(gx))$

Существует несколько понятий «эквивалентности» и «редукции», которые позволяют «сводить» лямбда-термы к «эквивалентным» лямбда-термам.

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

Базовая форма эквивалентности, определяемая на лямбда-термах, — это альфа-эквивалентность . Она отражает интуицию, что конкретный выбор связанной переменной в абстракции (обычно) не имеет значения. Например, и являются альфа-эквивалентными лямбда-термами, и они оба представляют одну и ту же функцию (функцию тождества). Термины и не являются альфа-эквивалентными, поскольку они не связаны в абстракции. Во многих презентациях принято идентифицировать альфа-эквивалентные лямбда-термы. $\лямбда xx$ $\лямбда уу$ $x$ $у$

Для того чтобы дать определение β-редукции, необходимы следующие определения:

Свободные переменные

Свободные переменные ^[h] терма — это те переменные, которые не связаны абстракцией. Набор свободных переменных выражения определяется индуктивно:

Свободные переменные — это просто $x$ $x$
Набор свободных переменных — это набор свободных переменных , но с удаленными $\лямбда xt$ $т$ $x$
Множество свободных переменных представляет собой объединение множества свободных переменных и множества свободных переменных . $т$ $с$ $т$ $с$

Например, лямбда-терм, представляющий тождество, не имеет свободных переменных, но функция имеет одну свободную переменную, . $\лямбда xx$ $\лямбда ху$ $x$ $у$

Замены, позволяющие избежать захвата

Предположим , что , и являются лямбда-термами, а и являются переменными. Обозначение указывает на замену for в способом , избегающим захвата . Это определяется так, что: $т$ $с$ $r$ $x$ $у$ $t[x:=r]$ $r$ $x$ $т$

$x[x:=r]=r$ ; с заменой на , становится $r$ $x$ $x$ $r$
$y[x:=r]=y$ если ; с заменой на , (который не является ) остается $x\neq y$ $r$ $x$ $у$ $x$ $у$
$(т$ $s)[x:=r]=(t[x:=r])(s[x:=r])$ ; замена распространяется на обе стороны приложения
$(\lambda xt)[x:=r]=\lambda xt$ ; переменная, связанная с абстракцией, не подлежит замене; замена такой переменной оставляет абстракцию неизменной
$(\lambda yt)[x:=r]=\lambda y.(t[x:=r])$ если и не появляется среди свободных переменных ( ), то говорят, что он « свежий » для ); подстановка переменной, которая не связана абстракцией, выполняется в теле абстракции, при условии, что абстрагированная переменная является «свежей» для термина подстановки . $x\neq y$ $у$ $r$ $у$ $r$ $у$ $r$

Например, , и . $(\lambda xx)[y:=y]=\lambda x.(x[y:=y])=\lambda xx$ $((\lambda xy)x)[x:=y]=((\lambda xy)[x:=y])(x[x:=y])=(\lambda xy)y$

Условие свежести (требующее, чтобы не было свободных переменных ) имеет решающее значение для того, чтобы гарантировать, что подстановка не изменит смысла функций. $у$ $r$

Например, подстановка, игнорирующая условие свежести, может привести к ошибкам: . Эта ошибочная подстановка превратит постоянную функцию в тождество . $(\lambda xy)[y:=x]=\lambda x.(y[y:=x])=\lambda xx$ $\лямбда ху$ $\лямбда xx$

В общем случае, невыполнение условия свежести может быть исправлено путем альфа-переименования сначала с подходящей свежей переменной. Например, возвращаясь к нашему правильному представлению о подстановке, в абстракции можно переименовать с помощью свежей переменной , чтобы получить , и значение функции сохраняется посредством подстановки. $(\lambda xy)[y:=x]$ $z$ $(\lambda z.y)[y:=x]=\lambda z.(y[y:=x])=\lambda z.x$

β-редукция

Правило β-редукции ^[b] гласит, что применение формы сводится к члену . Обозначение используется для указания того, что β-сводится к . Например, для каждого , . Это показывает, что действительно является тождеством. Аналогично, , что показывает, что является постоянной функцией. $(\lambda x.t)s$ $t[x:=s]$ $(\lambda x.t)s\to t[x:=s]$ $(\lambda x.t)s$ $t[x:=s]$ $s$ $(\lambda x.x)s\to x[x:=s]=s$ $\lambda x.x$ $(\lambda x.y)s\to y[x:=s]=y$ $\lambda x.y$

Лямбда-исчисление можно рассматривать как идеализированную версию функционального языка программирования, такого как Haskell или Standard ML . Согласно этой точке зрения,β-редукция соответствует вычислительному шагу. Этот шаг может быть повторен дополнительными β-редукциями до тех пор, пока не останется больше приложений для редукции. В нетипизированном лямбда-исчислении, как представлено здесь, этот процесс редукции может не завершиться. Например, рассмотрим термин . Здесь . То есть, термин редуцируется к самому себе в одной β-редукции, и поэтому процесс редукции никогда не завершится. $\Omega =(\lambda x.xx)(\lambda x.xx)$ $(\lambda x.xx)(\lambda x.xx)\to (xx)[x:=\lambda x.xx]=(x[x:=\lambda x.xx])(x[x:=\lambda x.xx])=(\lambda x.xx)(\lambda x.xx)$

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

Формальное определение

Определение

Лямбда-выражения состоят из:

переменные v ₁ , v ₂ , ...;
символы абстракции λ (лямбда) и . (точка);
скобки ().

Набор лямбда-выражений $Λ$ можно определить индуктивно :

Если x — переменная, то $x \in Λ.$
Если x — переменная и $M \in Λ,$ то $(λ x . M) \in Λ.$
Если $M, N \in Λ,$ то $(MN) \in Λ.$

Примеры правила 2 известны как абстракции , а примеры правила 3 известны как приложения . ^[18] См. § редуцируемое выражение

Этот набор правил можно записать в форме Бэкуса–Наура следующим образом:

 < выражение >  :== < абстракция > | < применение > | < переменная >  < абстракция >  :== λ < переменная > . < выражение >  < применение >  :== ( < выражение >  < выражение > ) < переменная >  :== v1 | v2 | ...

Обозначение

Чтобы запись лямбда-выражений не была перегружена, обычно применяются следующие соглашения:

Внешние скобки опускаются: M N вместо ( M N ).
Предполагается, что приложения являются левоассоциативными: вместо (( M N ) P можно записать M N P ). ^[19]
Если все переменные однобуквенные, то пробел в заявках можно опустить: MNP вместо M N P . ^[20]
Тело абстракции простирается как можно дальше вправо : λ x . MN означает λ x .( MN ), а не (λ x . M ) N .
Последовательность абстракций сокращается: λ x .λ y .λ z . N сокращается до λ xyz . N . ^[21]^[19]

Свободные и связанные переменные

Говорят, что оператор абстракции λ связывает свою переменную везде, где он встречается в теле абстракции. Переменные, которые попадают в область действия абстракции, называются связанными . В выражении λ x . M часть λ x часто называют связующим , как намек на то, что переменная x становится связанной путем добавления λ x к M . Все остальные переменные называются свободными . Например, в выражении λ y . xxy y является связанной переменной, а x является свободной переменной. Также переменная связана своей ближайшей абстракцией. В следующем примере единственное вхождение x в выражении связано второй лямбдой: λ x . y (λ x . zx ).

Набор свободных переменных лямбда-выражения M обозначается как FV( M ) и определяется рекурсией по структуре членов следующим образом:

FV( x ) = { x }, где x — переменная.
FV(λ x . M ) = FV( M ) \ { x }. ^[i]
$FV(MN) = FV(M) \cup FV(N).$ ^[Дж]

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

Снижение

Значение лямбда-выражений определяется тем, как выражения могут быть сокращены. ^[22]

Существует три вида редукции:

α-преобразование : изменение связанных переменных;
β-редукция : применение функций к их аргументам;
η-редукция : которая охватывает понятие экстенсиональности.

Мы также говорим о результирующих эквивалентностях: два выражения являются α-эквивалентными , если их можно α-преобразовать в одно и то же выражение. β-эквивалентность и η-эквивалентность определяются аналогично.

Термин редекс , сокращение от редуцируемое выражение , относится к подтермам, которые могут быть редуцированы одним из правил редукции. Например, (λ x . M ) N является β-редексом в выражении замены N на x в M . Выражение, к которому редуцируется редекс, называется его редуктом ; редуктом (λ x . M ) N является M [ x := N ]. ^[b]

Если x не является свободным в M , λ x . M x также является η-редексом с редукцией M.

α-конверсия

α-преобразование ( альфа -преобразование), иногда называемое α-переименованием, ^[23] позволяет изменять имена связанных переменных. Например, α-преобразование λ x . x может дать λ y . y . Термины, отличающиеся только α-преобразованием, называются α-эквивалентными . Часто при использовании лямбда-исчисления α-эквивалентные термины считаются эквивалентными.

Точные правила для α-преобразования не совсем тривиальны. Во-первых, при α-преобразовании абстракции переименовываются только те вхождения переменных, которые привязаны к той же абстракции. Например, α-преобразование λ x .λ x . x может привести к λ y .λ x . x , но не может привести к λ y .λ x . y . Последнее имеет иное значение, чем исходное. Это аналогично программному понятию затенения переменных .

Во-вторых, α-преобразование невозможно, если оно приведет к захвату переменной другой абстракцией. Например, если мы заменим x на y в λ x .λ y . x , то получим λ y .λ y . y , что совсем не одно и то же.

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

В индексной нотации Де Брейна любые два α-эквивалентных термина синтаксически идентичны.

Замена

Подстановка, обозначаемая M [ x := N ], — это процесс замены всех свободных вхождений переменной x в выражении M выражением N. Подстановка в терминах лямбда-исчисления определяется рекурсией в структуре терминов следующим образом (примечание: x и y — это только переменные, тогда как M и N — это любое лямбда-выражение):

х [ х := N ] = N

y [ x := N ] = y , если x ≠ y

( М ₁ М ₂ )[ х := N ] = М ₁ [ х := N ] М ₂ [ х := N ]

(λ x . M )[ x := N ] = λ x . M

(λ y . M )[ x := N ] = λ y .( M [ x := N ]), если x ≠ y и y ∉ FV( N ) См. выше для FV

Чтобы подставить в абстракцию, иногда необходимо α-преобразовать выражение. Например, неправильно, чтобы (λ x . y )[ y := x ] приводило к λ x . x , поскольку подставленный x должен был быть свободным, но в итоге оказался связанным. Правильная подстановка в этом случае — λ z . x , с точностью до α-эквивалентности. Подстановка определяется однозначно с точностью до α-эквивалентности. См. Подстановки, избегающие захвата выше

β-редукция

β-редукция ( бета- редукция) отражает идею применения функции. β-редукция определяется в терминах подстановки: β-редукция (λ x . M ) N равна M [ x := N ]. ^[b]

Например, предположив некоторую кодировку 2, 7, ×, мы имеем следующую β-редукцию: (λ n . n × 2) 7 → 7 × 2.

β-редукцию можно рассматривать как то же самое, что и концепцию локальной сводимости в естественной дедукции , посредством изоморфизма Карри–Ховарда .

η-редукция

η-редукция ( эта -редукция) выражает идею экстенсиональности ^[24] , которая в данном контексте заключается в том, что две функции одинаковы тогда и только тогда, когда они дают одинаковый результат для всех аргументов. η-редукция преобразует λ x . f x и f всякий раз, когда x не появляется свободным в f .

η-редукцию можно рассматривать как то же самое, что и концепцию локальной полноты в естественной дедукции , посредством изоморфизма Карри–Ховарда .

Нормальные формы и слияние

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

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

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

Кодирование типов данных

Базовое лямбда-исчисление может использоваться для моделирования арифметики , булевых значений, структур данных и рекурсии, как показано в следующих подразделах i , ii , iii и § iv .

Арифметика в лямбда-исчислении

Существует несколько возможных способов определения натуральных чисел в лямбда-исчислении, но наиболее распространенными являются числа Чёрча , которые можно определить следующим образом:

0 := λ f .λ x . x

1 := λ f .λ x . f x

2 := λ f .λ x . f ( f x )

3 := λ f .λ x . f ( f ( f x ))

и т. д. Или используя альтернативный синтаксис, представленный выше в Нотации :

0 := λ fx . x

1 := λ fx . f x

2 := λ fx . f ( f x )

3 := λ fx . f ( f ( f x ))

Числовое значение Чёрча — это функция высшего порядка — она принимает функцию f с одним аргументом и возвращает другую функцию с одним аргументом. Числовое значение Чёрча n — это функция, которая принимает функцию f в качестве аргумента и возвращает n -ю композицию f , т. е. функцию f , составленную с самой собой n раз. Это обозначается f ⁽ⁿ⁾ и фактически является n -й степенью f (рассматриваемой как оператор); f ⁽⁰⁾ определяется как функция тождества. Такие повторяющиеся композиции (одной функции f ) подчиняются законам экспонент , поэтому эти числительные можно использовать для арифметики. (В оригинальном лямбда-исчислении Чёрча формальный параметр лямбда-выражения должен был встречаться по крайней мере один раз в теле функции, что делало приведенное выше определение 0 невозможным.)

Один из способов думать о числительном числе Чёрча n , которое часто полезно при анализе программ, — это как инструкция «повторить n раз». Например, используя функции PAIR и NIL, определенные ниже, можно определить функцию, которая создает (связанный) список из n элементов, все из которых равны x , повторяя «добавить другой элемент x » n раз, начиная с пустого списка. Лямбда-терм — это

λ n .λ x . n (ПАРА x ) НОЛЬ

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

Мы можем определить функцию-последователя, которая принимает число Чёрча n и возвращает n + 1 , добавляя ещё одно применение f , где '(mf)x' означает, что функция 'f' применяется 'm' раз к 'x':

SUCC := λ n .λ f .λ x . f ( n f x )

Поскольку m -е построение f, составленное с n -м построением f, дает m + n -е построение f , сложение можно определить следующим образом:

ПЛЮС := λ м .λ п .λ ж .λ x . м ж ( п ж Икс )

PLUS можно рассматривать как функцию, принимающую два натуральных числа в качестве аргументов и возвращающую натуральное число; можно проверить, что

ПЛЮС 2 3

являются β-эквивалентными лямбда-выражениями. Поскольку добавление m к числу n может быть выполнено путем добавления 1 m раз, альтернативное определение таково:

ПЛЮС := λ м .λ п . м SUCC н ^[25]

Аналогично, умножение можно определить как

MULT := λ m .λ n .λ f . m ( n f ) ^[21]

Альтернативно

MULT := λ м .λ п . м (ПЛЮС n ) 0

поскольку умножение m и n равносильно повторению функции add n m раз и последующему применению ее к нулю. Возведение в степень имеет довольно простую форму в числах Чёрча, а именно

POW := λ б .λ е . е б^[1]

Функция предшественника, определяемая PRED n = n − 1 для положительного целого числа n и PRED 0 = 0, значительно сложнее. Формула

PRED := λ n .λ f .λ x . п (λ г .λ час . час ( г ж )) (λ ты . Икс ) (λ ты . ты )

можно проверить, показав индуктивно, что если T обозначает (λ g .λ h . h ( g f )) , то T ⁽ⁿ⁾ (λ u . x ) = (λ h . h ( f ⁽ⁿ⁻¹⁾ ( x ))) для n > 0 . Ниже приведены два других определения PRED , одно с использованием условных операторов, а другое с использованием пар. С функцией previous вычитание выполняется просто. Определение

SUB := λ м .λ п . п ПРЕДМ ,

SUB m n дает m − n, когда m > n, и 0 в противном случае.

Логика и предикаты

По соглашению, для булевых значений TRUE и FALSE используются следующие два определения (известные как булевы значения Чёрча) :

ИСТИНА := λ x .λ y . x

ЛОЖЬ := λ x .λ y . y

Затем с помощью этих двух лямбда-термов мы можем определить некоторые логические операторы (это всего лишь возможные формулировки; другие выражения могут быть столь же корректными):

И := λ п .λ д . п q п

ИЛИ := λ п .λ q . п п q

НЕ := λ p . p ЛОЖЬ ИСТИНА

ЕСЛИ := λ p .λ a .λ b . п а б

Теперь мы можем вычислять некоторые логические функции, например:

И ПРАВДА ЛОЖЬ

≡ (λ p .λ q . p q p ) ИСТИНА ЛОЖЬ → _β ИСТИНА ЛОЖЬ ИСТИНА

≡ (λ x .λ y . x ) ЛОЖЬ ИСТИНА → _β ЛОЖЬ

и мы видим, что И ИСТИНА ЛОЖЬ эквивалентно ЛОЖИ .

Предикат — это функция, которая возвращает логическое значение. Наиболее фундаментальным предикатом является ISZERO , который возвращает TRUE , если его аргументом является число 0 Чёрча , но FALSE , если его аргументом является любое другое число Чёрча:

ISZERO := λ n . n (λ x .FALSE) ИСТИНА

Следующий предикат проверяет, является ли первый аргумент меньшим или равным второму:

LEQ := λ m .λ n .ISZERO (SUB m n ) ,

и поскольку m = n , если LEQ m n и LEQ n m , то легко построить предикат для числового равенства.

Наличие предикатов и приведенное выше определение TRUE и FALSE делает удобным написание выражений "if-then-else" в лямбда-исчислении. Например, функция previous может быть определена как:

ПРЕД := λ n . n (λ g .λ k .ISZERO ( g 1) k (ПЛЮС ( g k ) 1)) (λ v .0) 0

что можно проверить, показав индуктивно, что n (λ g .λ k .ISZERO ( g 1) k (PLUS ( g k ) 1)) (λ v .0) является функцией сложения n − 1 для n > 0.

Пары

Пара (2-кортеж) может быть определена в терминах TRUE и FALSE , используя кодировку Чёрча для пар . Например, PAIR инкапсулирует пару ( x , y ), FIRST возвращает первый элемент пары, а SECOND возвращает второй.

ПАРА := λ x .λ y .λ f . f x y

ПЕРВЫЙ := λ p . p ИСТИНА

ВТОРОЙ := λ p . p ЛОЖЬ

НОЛЬ := λ x .ИСТИНА

НОЛЬ := λ п . p (λ x .λ y .ЛОЖЬ)

Связанный список может быть определен как NIL для пустого списка или как ПАРА элемента и меньшего списка. Предикат NULL проверяет значение NIL . (В качестве альтернативы, с NIL := FALSE , конструкция l (λ h .λ t .λ z .deal_with_head_ h _and_tail_ t ) (deal_with_nil) устраняет необходимость в явной проверке NULL).

В качестве примера использования пар функция сдвига и приращения, которая отображает ( m , n ) в ( n , n + 1), может быть определена как

Φ := λ x .ПАРА (ВТОРОЙ x ) (ВТОРОЙ x ))

что позволяет нам дать, пожалуй, наиболее прозрачную версию функции-предшественника:

ПРЕД := λ n .ПЕРВЫЙ ( n Φ (ПАРА 0 0)).

Дополнительные методы программирования

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

Именованные константы

В лямбда-исчислении библиотека принимает форму коллекции ранее определенных функций, которые как лямбда-термы являются просто частными константами. Чистое лямбда-исчисление не имеет концепции именованных констант, поскольку все атомарные лямбда-термы являются переменными, но можно эмулировать наличие именованных констант, отложив переменную в качестве имени константы, используя абстракцию для связывания этой переменной в основном теле и применяя эту абстракцию к предполагаемому определению. Таким образом, чтобы использовать f для обозначения N (некоторый явный лямбда-терм) в M (другой лямбда-терм, «основная программа»), можно сказать

(λ ф . М ) Н

Авторы часто вводят синтаксический сахар , такой как let , ^[k], чтобы позволить записывать вышеизложенное в более интуитивно понятном порядке.

пусть f = N в M

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

Примечательным ограничением этого let является то, что имя f не может быть определено в N , чтобы N не выходил за рамки абстракции, связывающей f ; это означает, что определение рекурсивной функции не может быть использовано как N с let . Конструкция letrec ^[l] позволила бы писать определения рекурсивных функций.

Рекурсия и неподвижные точки

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

Рассмотрим факториальную функцию F( n ), рекурсивно определенную как

F( n ) = 1, если n = 0; в противном случае n × F( n − 1) .

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

G := λ r . λ n . (1, если n = 0; иначе n × ( r r ( n −1)))

с r r x = F x = G r x для хранения, поэтому r = G и

F := GG = (λ x . x x ) G

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

Это решает проблему, но требует переписывания каждого рекурсивного вызова как самоприменения. Мы хотели бы иметь общее решение, без необходимости каких-либо переписываний:

G := λ r . λ n . (1, если n = 0; иначе n × ( r ( n −1)))

с r x = F x = G r x для удержания, поэтому r = G r =: FIX G и

F := FIX G , где FIX g := ( r , где r = g r ) = g (FIX g )

так что FIX G = G (FIX G) = (λ n .(1, если n = 0; иначе n × ((FIX G) ( n −1))))

При наличии лямбда-терма с первым аргументом, представляющим рекурсивный вызов (например, G здесь), комбинатор с фиксированной точкой FIX вернет самовоспроизводящееся лямбда-выражение, представляющее рекурсивную функцию (здесь, F ). Функцию не нужно явно передавать самой себе в какой-либо точке, поскольку самовоспроизводство организовано заранее, при ее создании, и будет выполняться каждый раз при ее вызове. Таким образом, исходное лямбда-выражение (FIX G) воссоздается внутри себя, в точке вызова, достигая самоссылки .

На самом деле существует множество возможных определений этого оператора FIX , самое простое из них:

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

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

Y г

(λ ч .(λ х . ч ( х х )) (λ х . ч ( х х ))) г

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

г ((λ x . г ( x x )) (λ x . г ( x x )))

г ( Y г )

Теперь, чтобы выполнить наш рекурсивный вызов функции факториала, мы просто вызовем ( Y G) n , где n — число, факториал которого мы вычисляем. Например, если n = 4, это дает:

( Ю Г) 4

Г ( Ю Г) 4

(λ r .λ n .(1, если n = 0; иначе n × ( r ( n −1)))) ( Y G) 4

(λ n .(1, если n = 0; иначе n × (( Y G) ( n −1)))) 4

1, если 4 = 0; иначе 4 × (( Y G) (4−1))

4 × (Г ( Ю Г) (4−1))

4 × ((λ n .(1, если n = 0; иначе n × (( Y G) ( n −1)))) (4−1))

4 × (1, если 3 = 0; иначе 3 × (( Y G) (3−1)))

4 × (3 × (Г ( Ю Г) (3−1)))

4 × (3 × ((λ n .(1, если n = 0; иначе n × (( Y G) ( n −1)))) (3−1)))

4 × (3 × (1, если 2 = 0; иначе 2 × (( Y G) (2−1))))

4 × (3 × (2 × (Г ( Й Г) (2−1))))

4 × (3 × (2 × ((λ n .(1, если n = 0; иначе n × (( Y G) ( n −1)))) (2−1))))

4 × (3 × (2 × (1, если 1 = 0; иначе 1 × (( Y G) (1−1)))))

4 × (3 × (2 × (1 × (Г ( Й Г) (1−1)))))

4 × (3 × (2 × (1 × ((λ n .(1, если n = 0; иначе n × (( Y G) ( n −1)))) (1−1)))))

4 × (3 × (2 × (1 × (1, если 0 = 0; иначе 0 × (( Y G) (0−1))))))

4 × (3 × (2 × (1 × (1))))

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

Стандартные условия

Некоторые термины имеют общепринятые названия: ^[27]^[28]^[29]

Я := λ x . x

S := λ Икс .λ y .λ z . Икс z ( у z )

К := λ x .λ y . x

B := λ Икс .λ y .λ z . х ( у я )

C := λ x .λ y .λ z . x z y

W := λ x .λ y . x y y

ω или Δ или U := λ x . x x

Ω := ω ω

I — это функция тождества. SK и BCKW образуют полные системы комбинаторного исчисления , которые могут выразить любой лямбда-терм — см. следующий раздел. Ω — это UU , наименьший терм, не имеющий нормальной формы. YI — еще один такой терм. Y является стандартным и определен выше, а также может быть определен как Y = BU(CBU) , так что Y g=g( Y g) . TRUE и FALSE , определенные выше, обычно сокращаются до T и F .

Устранение абстракции

Если N — лямбда-терм без абстракции, но, возможно, содержащий именованные константы ( комбинаторы ), то существует лямбда-терм T ( x , N ), который эквивалентен λ x . N , но не имеет абстракции (за исключением части именованных констант, если они считаются неатомарными). Это также можно рассматривать как анонимизацию переменных, поскольку T ( x , N ) удаляет все вхождения x из N , при этом все еще позволяя подставлять значения аргументов в позиции, где N содержит x . Функция преобразования T может быть определена следующим образом:

Т ( х , х ) := I

T ( x , N ) := K N , если x не является свободным в N .

Т ( х , М N ) := С Т ( х , М ) Т ( х , N )

В любом случае терм формы T ( x , N ) P можно сократить, заставив начальный комбинатор I , K или S захватить аргумент P , точно так же, как это сделала бы β-редукция (λ x . N ) P . I возвращает этот аргумент. K отбрасывает аргумент, точно так же, как это сделала бы (λ x . N ) , если x не имеет свободного вхождения в N . S передает аргумент обоим подтермам применения, а затем применяет результат первого к результату второго.

Комбинаторы B и C похожи на S , но передают аргумент только одному подтерму приложения ( B подтерму "аргумент" и C подтерму "функция"), тем самым сохраняя последующий K, если в одном подтерме нет вхождения x . По сравнению с B и C , комбинатор S фактически объединяет две функции: перестановку аргументов и дублирование аргумента, чтобы его можно было использовать в двух местах. Комбинатор W делает только последнее, получая систему B, C, K, W в качестве альтернативы исчислению комбинатора SKI .

Типизированное лямбда-исчисление

Типизированное лямбда-исчисление — это типизированный формализм , который использует лямбда-символ ( ) для обозначения абстракции анонимной функции. В этом контексте типы обычно являются объектами синтаксической природы, которые назначаются лямбда-термам; точная природа типа зависит от рассматриваемого исчисления (см. Виды типизированных лямбда-исчислений ). С определенной точки зрения типизированные лямбда-исчисления можно рассматривать как уточнения нетипизированного лямбда-исчисления, но с другой точки зрения их также можно считать более фундаментальной теорией, а нетипизированное лямбда-исчисление — частным случаем только с одним типом. ^[30] $\lambda$

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

Типизированные лямбда-исчисления тесно связаны с математической логикой и теорией доказательств через изоморфизм Карри–Ховарда , и их можно рассматривать как внутренний язык классов категорий , например, просто типизированное лямбда-исчисление является языком декартовых замкнутых категорий (ЗКК).

Стратегии сокращения

Является ли термин нормализующим или нет, и сколько работы необходимо проделать для его нормализации, если это так, во многом зависит от используемой стратегии редукции. Распространенные стратегии редукции лямбда-исчисления включают: ^[31]^[32]^[33]

Нормальный порядок: Самый левый внешний редекс редуцируется первым. То есть, когда это возможно, аргументы подставляются в тело абстракции до того, как аргументы редуцируются. Если терм имеет бета-нормальную форму, редукция нормального порядка всегда достигнет этой нормальной формы.
Прикладной порядок: Сначала редуцируется самый левый внутренний редекс. Как следствие, аргументы функции всегда редуцируются до того, как они будут подставлены в функцию. В отличие от редукции нормального порядка, аппликативная редукция порядка может не найти бета-нормальную форму выражения, даже если такая нормальная форма существует. Например, термин редуцируется к самому себе аппликативным порядком, в то время как нормальный порядок редуцирует его к бета-нормальной форме . $(\;\lambda x.y\;\;(\lambda z.(zz)\;\lambda z.(zz))\;)$ $y$
Полные β-редукции: Любой редекс может быть сокращен в любое время. Это означает, по сути, отсутствие какой-либо конкретной стратегии сокращения — в отношении сокращаемости «все ставки отменены».

Слабые стратегии редукции не работают при лямбда-абстракциях:

Звонок по значению: Как аппликативный порядок, но внутри абстракций не выполняется никаких сокращений. Это похоже на порядок оценки строгих языков, таких как C: аргументы функции оцениваются до вызова функции, а тела функций даже частично не оцениваются, пока аргументы не будут подставлены.
Назвать по имени: Как и нормальный порядок, но внутри абстракций не выполняется никаких сокращений. Например, λ x .(λ y . y ) x находится в нормальной форме согласно этой стратегии, хотя и содержит редекс (λ y . y ) x .

Стратегии с совместным использованием сокращают количество вычислений, которые «одинаковы» при параллельном выполнении:

Оптимальное сокращение: Как обычно, но вычисления, имеющие одинаковую метку, сокращаются одновременно.
Звонок по необходимости: Как вызов по имени (следовательно, слабый), но функциональные приложения, которые дублируют термины, вместо этого называют аргумент. Аргумент может быть оценен "при необходимости", в этот момент привязка имени обновляется с уменьшенным значением. Это может сэкономить время по сравнению с обычной оценкой порядка.

Вычислимость

Не существует алгоритма, который принимает на вход любые два лямбда-выражения и выводит TRUE или FALSE в зависимости от того, сводится ли одно выражение к другому. ^[13] Точнее, никакая вычислимая функция не может решить этот вопрос. Это была исторически первая проблема, для которой удалось доказать неразрешимость. Как обычно для такого доказательства, вычислимость означает вычислимость любой моделью вычислений , которая является полной по Тьюрингу . Фактически вычислимость сама по себе может быть определена с помощью лямбда-исчисления: функция F : N → N натуральных чисел является вычислимой функцией тогда и только тогда, когда существует лямбда-выражение f такое, что для каждой пары x , y из N , F ( x )= y тогда и только тогда, когда f x = _βy , где x и y — числительные Чёрча , соответствующие x и y , соответственно, и = _β означает эквивалентность с β-редукцией. См. тезис Чёрча–Тьюринга для других подходов к определению вычислимости и их эквивалентности.

Доказательство невычислимости Чёрча сначала сводит проблему к определению того, имеет ли данное лямбда-выражение нормальную форму . Затем он предполагает, что этот предикат вычислим и, следовательно, может быть выражен в лямбда-исчислении. Основываясь на более ранней работе Клини и строя нумерацию Гёделя для лямбда-выражений, он строит лямбда-выражение e , которое близко следует доказательству первой теоремы Гёделя о неполноте . Если e применяется к его собственному числу Гёделя, возникает противоречие.

Сложность

Понятие вычислительной сложности для лямбда-исчисления немного запутано, поскольку стоимость β-редукции может варьироваться в зависимости от того, как она реализована. ^[34] Если быть точным, нужно каким-то образом найти местоположение всех вхождений связанной переменной V в выражение E , что подразумевает временные затраты, или нужно каким-то образом отслеживать местоположения свободных переменных, что подразумевает пространственные затраты. Наивный поиск местоположений V в E составляет O ( n ) по длине n выражения E . Директорные строки были ранним подходом, который обменял эти временные затраты на квадратичное использование пространства. ^[35] В более общем плане это привело к изучению систем, использующих явную подстановку .

В 2014 году было показано, что количество шагов β-редукции, предпринимаемых редукцией нормального порядка для сокращения термина, является разумной моделью затрат времени, то есть, сокращение может быть смоделировано на машине Тьюринга за время, полиномиально пропорциональное количеству шагов. ^[36] Это была давняя открытая проблема из-за взрывного роста размера , существования лямбда-терминов, которые экспоненциально растут в размере для каждого β-редукции. Результат обходит это, работая с компактным общим представлением. Результат ясно показывает, что объем пространства, необходимый для оценки лямбда-термина, не пропорционален размеру термина во время сокращения. В настоящее время неизвестно, какой будет хорошая мера сложности пространства. ^[37]

Неразумная модель не обязательно означает неэффективную. Оптимальное сокращение сокращает все вычисления с той же меткой за один шаг, избегая дублирования работы, но количество параллельных шагов β-сокращения для приведения данного термина к нормальной форме приблизительно линейно зависит от размера термина. Это слишком мало, чтобы быть разумной мерой затрат, поскольку любая машина Тьюринга может быть закодирована в лямбда-исчислении в размере, линейно пропорциональном размеру машины Тьюринга. Истинная стоимость сокращения лямбда-терминов обусловлена не β-сокращением как таковым, а скорее обработкой дублирования редексов во время β-сокращения. ^[38] Неизвестно, являются ли оптимальные реализации сокращения разумными при измерении относительно разумной модели затрат, такой как количество шагов слева-внешнего к нормальной форме, но было показано для фрагментов лямбда-исчисления, что оптимальный алгоритм сокращения эффективен и имеет не более квадратичные накладные расходы по сравнению с самым левым-внешним. ^[37] Кроме того, реализация прототипа BOHM оптимальной редукции превзошла как Caml Light , так и Haskell на чистых лямбда-терминах. ^[38]

Лямбда-исчисление и языки программирования

Как отмечено в статье Питера Ландина 1965 года «Соответствие между АЛГОЛом 60 и лямбда-нотацией Чёрча» ^[39] , последовательные процедурные языки программирования можно понимать в терминах лямбда-исчисления, которое обеспечивает основные механизмы для процедурной абстракции и применения процедур (подпрограмм).

Анонимные функции

Например, в Python функция «square» может быть выражена как лямбда-выражение следующим образом:

( лямбда  x :  x ** 2 )

Приведенный выше пример — это выражение, которое вычисляется как функция первого класса. Символ lambdaсоздает анонимную функцию, заданную списком имен параметров, x— в данном случае это всего лишь один аргумент, и выражение, которое вычисляется как тело функции, x**2. Анонимные функции иногда называют лямбда-выражениями.

Например, Pascal и многие другие императивные языки давно поддерживают передачу подпрограмм в качестве аргументов другим подпрограммам через механизм указателей функций . Однако указатели функций не являются достаточным условием для того, чтобы функции были типами данных первого класса , поскольку функция является типом данных первого класса тогда и только тогда, когда новые экземпляры функции могут быть созданы во время выполнения. И это создание функций во время выполнения поддерживается в Smalltalk , JavaScript и Wolfram Language , а в последнее время и в Scala , Eiffel («агенты»), C# («делегаты») и C++11 , среди прочих.

Параллелизм и конкурентность

Свойство Чёрча –Россера лямбда-исчисления означает, что оценка (β-редукция) может быть выполнена в любом порядке , даже параллельно. Это означает, что различные недетерминированные стратегии оценки являются релевантными. Однако лямбда-исчисление не предлагает никаких явных конструкций для параллелизма . Можно добавлять конструкции, такие как Futures , в лямбда-исчисление. Были разработаны другие исчисления процессов для описания коммуникации и параллелизма.

Семантика

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

В 1970-х годах Дана Скотт показал, что если рассматривать только непрерывные функции , то можно найти множество или область D с требуемым свойством, тем самым предоставив модель для лямбда-исчисления. ^[40]

Эта работа также легла в основу денотативной семантики языков программирования.

Вариации и расширения

Эти расширения находятся в лямбда-кубе :

Типизированное лямбда-исчисление – лямбда-исчисление с типизированными переменными (и функциями)
Система F – Типизированное лямбда-исчисление с переменными типа
Исчисление конструкций – типизированное лямбда-исчисление с типами в качестве значений первого класса

Эти формальные системы являются расширениями лямбда-исчисления, которых нет в лямбда-кубе:

Двоичное лямбда-исчисление — версия лямбда-исчисления с двоичным вводом/выводом, двоичным кодированием термов и выделенной универсальной машиной.
Лямбда-мю исчисление – расширение лямбда-исчисления для обработки классической логики

Эти формальные системы являются вариациями лямбда-исчисления:

Каппа-исчисление – аналог лямбда-исчисления первого порядка.

Эти формальные системы связаны с лямбда-исчислением:

Комбинаторная логика – обозначение математической логики без переменных.
Исчисление комбинаторов SKI – вычислительная система, основанная на комбинаторах S , K и I , эквивалентная лямбда-исчислению, но сводимая без подстановки переменных.

Смотрите также

Аппликативные вычислительные системы – Обработка объектов в стиле лямбда-исчисления
Декартово замкнутая категория – установка для лямбда-исчисления в теории категорий
Категориальная абстрактная машина – модель вычислений, применимая к лямбда-исчислению
Clojure , язык программирования
Изоморфизм Карри–Ховарда – Формальное соответствие между программами и доказательствами
Индекс Де Брейна - обозначение, устраняющее неоднозначность альфа-конверсий
Нотация Де Брейна – нотация с использованием постфиксных функций модификации
Теория доменов – изучение некоторых частично упорядоченных множеств, дающих денотационную семантику для лямбда-исчисления
Стратегия оценки – Правила оценки выражений в языках программирования
Явная замена – Теория замены, используемая в β-редукции
Функциональное программирование
Формула Харропа – разновидность конструктивной логической формулы, в которой доказательства являются лямбда-термами.
Сети взаимодействия
Парадокс Клини–Россера – Демонстрация того, что некоторая форма лямбда-исчисления является противоречивой.
Рыцари лямбда-исчисления – полувымышленная организация хакеров LISP и Scheme
Машина Кривина – абстрактная машина для интерпретации вызова по имени в лямбда-исчислении
Определение лямбда-исчисления – Формальное определение лямбда-исчисления.
Пусть выражение – выражение, тесно связанное с абстракцией.
Минимализм (вычислительная техника)
Переписывание – Преобразование формул в формальных системах
Машина SECD – виртуальная машина, разработанная для лямбда-исчисления.
Теорема Скотта–Карри – Теорема о множествах лямбда-термов
Издеваться над пересмешником – Введение в комбинаторную логику
Универсальная машина Тьюринга – формальная вычислительная машина, эквивалентная лямбда-исчислению.
Unlambda – эзотерический функциональный язык программирования, основанный на комбинаторной логике

Дальнейшее чтение

Абельсон, Гарольд и Джеральд Джей Сассман. Структура и интерпретация компьютерных программ . Издательство MIT . ISBN 0-262-51087-1 .
Барендрегт, Хендрик Питер Введение в лямбда-исчисление.
Барендрегт, Хендрик Питер, Влияние лямбда-исчисления на логику и информатику. Бюллетень символической логики, том 3, номер 2, июнь 1997 г.
Барендрегт, Хендрик Питер, «Лямбда-исчисление без типов», стр. 1091–1132 Справочника по математической логике , Северная Голландия (1977) ISBN 0-7204-2285-X
Cardone, Felice и Hindley, J. Roger, 2006. История лямбда-исчисления и комбинаторной логики Архивировано 2021-05-06 в Wayback Machine . В Gabbay and Woods (ред.), Handbook of the History of Logic , т. 5. Elsevier.
Чёрч, Алонзо, Неразрешимая проблема элементарной теории чисел , American Journal of Mathematics , 58 (1936), стр. 345–363. В этой статье содержится доказательство того, что эквивалентность лямбда-выражений в общем случае неразрешима.
Чёрч, Алонзо (1941). Исчисления лямбда-преобразования. Принстон: Princeton University Press . Получено 14.04.2020 .( ISBN 978-0-691-08394-0 )
Фринк-младший, Оррин (1944). «Обзор: исчисления лямбда-преобразования Алонзо Чёрча» (PDF) . Bull. Amer. Math. Soc . 50 (3): 169–172. doi : 10.1090/s0002-9904-1944-08090-7 .
Клини, Стивен, Теория положительных целых чисел в формальной логике , American Journal of Mathematics , 57 (1935), стр. 153–173 и 219–244. Содержит определения лямбда-исчисления нескольких известных функций.
Ландин, Питер , Соответствие между ALGOL 60 и лямбда-нотацией Чёрча , Communications of the ACM , т. 8, № 2 (1965), стр. 89–101. Доступно на сайте ACM. Классическая статья, подчеркивающая важность лямбда-исчисления как основы для языков программирования.
Ларсон, Джим, Введение в лямбда-исчисление и схему. Легкое введение для программистов.
Майклсон, Грег (10 апреля 2013 г.). Введение в функциональное программирование с помощью лямбда-исчисления . Courier Corporation. ISBN 978-0-486-28029-5.^[41]
Шалк, А. и Симмонс, Х. (2005) Введение в λ-исчисления и арифметику с хорошим выбором упражнений . Заметки для курса магистратуры по математической логике в Манчестерском университете.
de Queiroz, Ruy JGB (2008). «О правилах редукции, значении как использовании и семантике теории доказательств». Studia Logica . 90 (2): 211–247. doi :10.1007/s11225-008-9150-5. S2CID 11321602.Статья, дающая формальное обоснование идеи «значение-есть-использование», которая, даже если и основана на доказательствах, отличается от семантики теории доказательств, как в традиции Даммета-Правица, поскольку она рассматривает редукцию как правила, придающие значение.
Ханкин, Крис, Введение в лямбда-исчисление для специалистов по информатике, ISBN 0954300653

Монографии/учебники для аспирантов

Sørensen, Morten Heine и Urzyczyn, Paweł (2006), Lectures on the Curry–Howard isomorphism , Elsevier, ISBN 0-444-52077-5 — недавняя монография, охватывающая основные темы лямбда-исчисления от бестипового варианта до большинства типизированных лямбда-исчислений , включая более поздние разработки, такие как чистые системы типов и лямбда-куб . Она не охватывает расширения подтипов .
Пирс, Бенджамин (2002), Типы и языки программирования , MIT Press, ISBN 0-262-16209-1охватывает лямбда-исчисление с точки зрения практической системы типов; некоторые темы, такие как зависимые типы, только упоминаются, но подтипирование является важной темой.

Документы

Краткое введение в лямбда-исчисление - ( PDF ) Ахима Юнга
Хронология лямбда-исчисления - ( PDF ) Даны Скотт
Введение в лямбда-исчисление ( PDF ) от Рауля Рохаса
Конспект лекций по лямбда-исчислению - ( PDF ) Питера Селинджера
Графическое лямбда-исчисление Мариуса Булиги
Лямбда-исчисление как модель рабочего процесса Питера Келли, Пола Коддингтона и Эндрю Вендельборна; упоминает редукцию графа как распространенное средство оценки лямбда-выражений и обсуждает применимость лямбда-исчисления для распределенных вычислений (благодаря свойству Чёрча–Россера , которое допускает параллельную редукцию графа для лямбда-выражений).

Примечания

^ Эти правила создают выражения, такие как: . Скобки можно опустить, если выражение однозначно. Для некоторых приложений могут быть включены термины для логических и математических констант и операций. $(\lambda x.\lambda y.(\lambda z.(\lambda x.z\ x)\ (\lambda y.z\ y))(x\ y))$
^ abcd
Barendregt, Barendsen (2000) называют эту форму
- аксиома β : (λx.M[x]) N = M[N] , переписанная как (λx.M) N = M[x := N], "где M[x := N] обозначает замену N для каждого вхождения x в M". ^[1]^{: 7} Также обозначается M[N/x], "замена N на x в M". ^[2]
↑ Полную историю см. в книге Кардона и Хиндли «История лямбда-исчисления и комбинаторной логики» (2006).
^ ab произносится как « maps to ». $\mapsto$
^ Выражение e может быть: переменными x, лямбда-абстракциями или приложениями —в BNF, .— из Википедии Просто типизированное лямбда-исчисление#Синтаксис для нетипизированного лямбда-исчисления $e::=x\mid \lambda x.e\mid e\,e$
^ иногда записывается в ASCII как $(\lambda x.t)$ $Lx.t$
^ Лямбда-терм представляет функцию , записанную в анонимной форме. $(\lambda x.t)$ $x\mapsto t$
^ свободные переменные в лямбда-нотации и ее исчислении сопоставимы с линейной алгеброй и математическими концепциями с тем же названием
^ Набор свободных переменных M, но с удаленными { x }
^ Объединение множества свободных переменных и множества свободных переменных ^[1] $M$ $N$
^ (λ f . M ) N можно произносить как «пусть f будет N в M».
^ Ариола и Блом ^[26] используют 1) аксиомы для репрезентативного исчисления, использующего правильно сформированные циклические лямбда-графы, расширенные с помощью letrec , для обнаружения возможных бесконечных раскручивающихся деревьев; 2) репрезентативное исчисление с β-редукцией ограниченных лямбда-графов составляет циклическое расширение лямбда-исчисления Ариолы/Блома; 3) Ариола/Блом рассуждают о строгих языках, использующих вызов по значению §, и сравнивают с исчислением Моджи и с исчислением Хасегавы. Выводы на стр. 111. ^[26]

Ссылки

Некоторые части этой статьи основаны на материалах FOLDOC , используемых с разрешения .

^ abc Барендрегт, Хенк ; Барендсен, Эрик (март 2000 г.), Введение в лямбда-исчисление (PDF)
^ явная замена в n Lab
^ Тьюринг, Алан М. (декабрь 1937 г.). «Вычислимость и λ-определимость». Журнал символической логики . 2 (4): 153–163. doi :10.2307/2268280. JSTOR 2268280. S2CID 2317046.
^ Coquand, Thierry (8 февраля 2006 г.). Zalta, Edward N. (ред.). "Теория типов". The Stanford Encyclopedia of Philosophy (лето 2013 г.) . Получено 17 ноября 2020 г.
^ Муртгат, Майкл (1988). Категориальные исследования: логические и лингвистические аспекты исчисления Ламбека. Foris Publications. ISBN 9789067653879.
^ Бунт, Гарри; Маскенс, Рейнхард, ред. (2008). Вычислительный смысл. Спрингер. ISBN 978-1-4020-5957-5.
^ Митчелл, Джон К. (2003). Концепции языков программирования. Cambridge University Press. стр. 57. ISBN 978-0-521-78098-8..
^ Чакон Сартори, Камило (2023-12-05). Введение в лямбда-исчисление с использованием Racket (технический отчет). Архивировано из оригинала 2023-12-07.
^ Пирс, Бенджамин С. Базовая теория категорий для специалистов по информатике . стр. 53.
^ Чёрч, Алонзо (1932). «Набор постулатов для основания логики». Annals of Mathematics . Серия 2. 33 (2): 346–366. doi :10.2307/1968337. JSTOR 1968337.
^ Клини, Стивен К .; Россер, Дж. Б. (июль 1935 г.). «Непоследовательность некоторых формальных логик». Анналы математики . 36 (3): 630. doi :10.2307/1968646. JSTOR 1968646.
↑ Чёрч, Алонзо (декабрь 1942 г.). «Обзор книги Хаскелла Б. Карри « Непоследовательность некоторых формальных логик ». Журнал символической логики . 7 (4): 170–171. doi :10.2307/2268117. JSTOR 2268117.
^ ab Church, Alonzo (1936). «Неразрешимая проблема элементарной теории чисел». American Journal of Mathematics . 58 (2): 345–363. doi :10.2307/2371045. JSTOR 2371045.
^ Чёрч, Алонзо (1940). «Формулировка простой теории типов». Журнал символической логики . 5 (2): 56–68. doi :10.2307/2266170. JSTOR 2266170. S2CID 15889861.
^ Парти, BBH; тер Мейлен, А.; Уолл, Р. Э. (1990). Математические методы в лингвистике. Springer. ISBN 9789027722454. Получено 29 декабря 2016 г.
^ Alama, Jesse. Zalta, Edward N. (ред.). «Лямбда-исчисление». Стэнфордская энциклопедия философии (лето 2013 г.) . Получено 17 ноября 2020 г.
^ Дана Скотт, «Взгляд назад; Взгляд вперед», Приглашенный доклад на семинаре в честь 85-летия Даны Скотт и 50-летия теории доменов, 7–8 июля, FLoC 2018 (доклад 7 июля 2018). Соответствующий отрывок начинается в 32:50. (См. также этот отрывок из доклада от мая 2016 года в Университете Бирмингема, Великобритания.)
^ Барендрегт, Хендрик Питер (1984). Лямбда-исчисление: его синтаксис и семантика. Исследования по логике и основаниям математики. Т. 103 (пересмотренное издание). Северная Голландия. ISBN 0-444-87508-5.(Исправления).
^ ab "Пример правил ассоциативности". Lambda-bound.com . Получено 2012-06-18 .
^ "Базовая грамматика лямбда-выражений". SoftOption . Некоторые другие системы используют сопоставление для обозначения применения, поэтому 'ab' означает 'a@b'. Это нормально, за исключением того, что требуется, чтобы переменные имели длину один, чтобы мы знали, что 'ab' — это две сопоставленные переменные, а не одна переменная длины 2. Но мы хотим, чтобы метки типа 'firstVariable' обозначали одну переменную, поэтому мы не можем использовать это соглашение о сопоставлении.
^ ab Selinger, Peter (2008), Lecture Notes on the Lambda Calculus (PDF) , т. 0804, Кафедра математики и статистики, Оттавский университет, стр. 9, arXiv : 0804.3434 , Bibcode : 2008arXiv0804.3434S
^ de Queiroz, Ruy JGB (1988). «Теоретико-доказательный отчет о программировании и роль правил редукции». Dialectica . 42 (4): 265–282. doi :10.1111/j.1746-8361.1988.tb00919.x.
^ Турбак, Франклин; Гиффорд, Дэвид (2008), Концепции дизайна в языках программирования , MIT press, стр. 251, ISBN 978-0-262-20175-9
↑ Люк Палмер (29 декабря 2010 г.) Haskell-cafe: Какова мотивация правил η?
^ Феллейзен, Маттиас; Флэтт, Мэтью (2006), Языки программирования и лямбда-исчисления (PDF) , стр. 26, архивировано из оригинала (PDF) 2009-02-05; Примечание (дата обращения 2017 г.) в исходном месте указывает на то, что авторы считают, что изначально упомянутая работа была заменена книгой.
^ ab Zena M. Ariola и Stefan Blom, Proc. TACS '94 Сендай, Япония 1997 (1997) Циклические лямбда-исчисления 114 страниц.
^ Кер, Эндрю Д. «Лямбда-исчисление и типы» (PDF) . стр. 6. Получено 14 января 2022 г.
^ Dezani-Ciancaglini, Mariangiola; Ghilezan, Silvia (2014). "Точность подтипирования типов пересечений и объединений" (PDF) . Переписывание и типизированные лямбда-исчисления . Конспект лекций по информатике. Том 8560. стр. 196. doi :10.1007/978-3-319-08918-8_14. hdl :2318/149874. ISBN 978-3-319-08917-1. Получено 14 января 2022 г. .
^ Форстер, Янник; Смолка, Герт (август 2019 г.). «Вызов по значению лямбда-исчисления как модель вычислений в Coq» (PDF) . Журнал автоматизированного рассуждения . 63 (2): 393–413. doi :10.1007/s10817-018-9484-2. S2CID 53087112 . Получено 14 января 2022 г. .
^ Типы и языки программирования, стр. 273, Бенджамин К. Пирс
^ Пирс, Бенджамин С. (2002). Типы и языки программирования. MIT Press . стр. 56. ISBN 0-262-16209-1.
^ Сестофт, Питер (2002). «Демонстрация сокращения лямбда-исчисления» (PDF) . Сущность вычислений . Конспект лекций по информатике. Том 2566. С. 420–435. doi :10.1007/3-540-36377-7_19. ISBN 978-3-540-00326-7. Получено 22 августа 2022 г. .
^ Берначка, Малгожата; Харатоник, Витольд; Драб, Томаш (2022). Андроник, июнь; де Моура, Леонардо (ред.). «Зоопарк стратегий сокращения лямбда-исчисления и Coq» (PDF) . 13-я Международная конференция по интерактивному доказательству теорем (ITP 2022) . 237 . Замок Дагштуль – Центр информатики Лейбница: 7:1–7:19. дои : 10.4230/LIPIcs.ITP.2022.7 . Проверено 22 августа 2022 г.
^ Frandsen, Gudmund Skovbjerg; Sturtivant, Carl (26 августа 1991 г.). «Что такое эффективная реализация λ-исчисления?». Функциональные языки программирования и архитектура компьютеров: 5-я конференция ACM. Кембридж, Массачусетс, США, 26–30 августа 1991 г. Труды . Заметки лекций по информатике. Том 523. Springer-Verlag. С. 289–312. CiteSeerX 10.1.1.139.6913 . doi :10.1007/3540543961_14. ISBN 9783540543961.
^ Синот, Ф.-Р. (2005). «Повторный взгляд на строки директора: общий подход к эффективному представлению свободных переменных в переписывании высшего порядка» (PDF) . Журнал логики и вычислений . 15 (2): 201–218. doi :10.1093/logcom/exi010.
^ Accattoli, Beniamino; Dal Lago, Ugo (14 июля 2014 г.). «Бета-редукция действительно инвариантна». Труды совместного заседания Двадцать третьей ежегодной конференции EACSL по логике компьютерных наук (CSL) и Двадцать девятого ежегодного симпозиума ACM/IEEE по логике в компьютерных науках (LICS) . стр. 1–10. arXiv : 1601.01233 . doi :10.1145/2603088.2603105. ISBN 9781450328869. S2CID 11485010.
^ ab Accattoli, Beniamino (октябрь 2018 г.). «(Не)эффективность и разумные модели затрат». Электронные заметки по теоретической информатике . 338 : 23–43. doi : 10.1016/j.entcs.2018.10.003 .
^ ab Asperti, Andrea (16 января 2017 г.). «Об эффективном сокращении лямбда-терминов». arXiv : 1701.04240v1 [cs.LO].
^ Ландин, П. Дж. (1965). «Соответствие между АЛГОЛом 60 и лямбда-нотацией Чёрча». Сообщения ACM . 8 (2): 89–101. doi : 10.1145/363744.363749 . S2CID 6505810.
^ Скотт, Дана (1993). «Теоретико-типовая альтернатива ISWIM, CUCH, OWHY» (PDF) . Теоретическая информатика . 121 (1–2): 411–440. doi :10.1016/0304-3975(93)90095-B . Получено 01.12.2022 .Написано в 1969 году, широко распространялось как неопубликованная рукопись.
^ "Грег Майклсон, домашняя страница". Математические и компьютерные науки . Риккартон, Эдинбург: Университет Хериот-Уотт . Получено 6 ноября 2022 г.

Внешние ссылки

На Викискладе есть медиафайлы по теме лямбда-исчисление .

Грэм Хаттон, Лямбда-исчисление, короткое (12 минут) видео для компьютерных фанатов о Лямбда-исчислении
Хельмут Брандл, Пошаговое введение в лямбда-исчисление
«Лямбда-исчисление», Энциклопедия математики , EMS Press , 2001 [1994]
Дэвид С. Кинан, Препарирование пересмешника: графическая запись лямбда-исчисления с анимированной редукцией
Л. Эллисон, Некоторые исполняемые примеры λ-исчисления
Георг П. Лочевский, Лямбда-исчисление и A++
Брет Виктор, «Яйца аллигатора»: игра-головоломка, основанная на лямбда-исчислении
Лямбда-исчисление Архивировано 14 октября 2012 г. на Wayback Machine на сайте Safalra Архивировано 02 мая 2021 г. на Wayback Machine
LCI Lambda Interpreter — простой, но мощный интерпретатор чистого исчисления
Ссылки на лямбда-исчисление на Lambda-the-Ultimate
Майк Тайер, Lambda Animator, графический Java-апплет, демонстрирующий альтернативные стратегии редукции.
Реализация лямбда-исчисления с использованием шаблонов C++
Шейн Стейнерт-Трелкельд, «Лямбда-исчисления», Интернет-энциклопедия философии
Антон Салихметов, Макро-лямбда-исчисление