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

Лямбда-исчисление (также пишется как λ-исчисление) это формальная система в математическая логика для выражения вычисление на основе функции абстракция и заявление используя переменную привязка и замена. Это универсальный модель вычисления который можно использовать для моделирования любого Машина Тьюринга. Его ввел математик Церковь Алонсо в 1930-х годах в рамках его исследования основы математики.

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

производя такие выражения, как: (λИкс.λу. (λz. (λИкс.z x) (λу.z y)) (х у)). Скобки можно опустить, если выражение однозначно. Для некоторых приложений могут быть включены термины для логических и математических констант и операций.

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

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

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

Объяснение и приложения

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

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

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

История

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

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

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

Происхождение символа лямбда

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

Кстати, почему Черч выбрал обозначение «λ»? В [неопубликованном письме 1964 года Харальду Диксону] он ясно заявил, что это произошло из обозначения «${displaystyle {hat {x}}}$”Используется для абстракции классов Уайтхед и Рассел, сначала изменив "${displaystyle {hat {x}}}$”На“ ∧${displaystyle x}$», Чтобы отличить абстракцию функции от абстракции класса, а затем измените« ∧ »на« λ »для облегчения печати.

Об этом происхождении также сообщалось в [Россер, 1984, с.338]. С другой стороны, в последние годы своей жизни Черч сказал двум вопрошающим, что выбор был более случайным: нужен был символ и просто случайно был выбран λ.

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

Уважаемый профессор Черч,

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

По словам Скотта, весь ответ Черча состоял в том, чтобы вернуть открытку со следующей аннотацией: "Ини, Мини, Мини, Мо ".

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

Этот раздел включает Список ссылок, связанное чтение или внешняя ссылка, но его источники остаются неясными, потому что в нем отсутствует встроенные цитаты. Пожалуйста, помогите улучшать этот раздел введение более точные цитаты. (Сентябрь 2013) (Узнайте, как и когда удалить этот шаблон сообщения)

Мотивация

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

${displaystyle operatorname {квадрат _sum} (x, y) = x ^ {2} + y ^ {2}}$

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

${displaystyle (x, y) mapsto x ^ {2} + y ^ {2}}$

(читается как "кортеж Икс и у является нанесенный на карту к ${extstyle x ^ {2} + y ^ {2}}$"). По аналогии,

${displaystyle operatorname {id} (x) = x}$

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

${displaystyle xmapsto x}$

где ввод просто сопоставляется сам с собой.

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

${displaystyle (x, y) mapsto x ^ {2} + y ^ {2}}$

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

${displaystyle xmapsto (ymapsto x ^ {2} + y ^ {2})}$

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

Приложение функции из ${extstyle operatorname {квадрат _sum}}$ функция аргументов (5, 2), сразу дает

${extstyle ((x, y) mapsto x ^ {2} + y ^ {2}) (5,2)}$

${extstyle = 5 ^ {2} + 2 ^ {2}}$

${extstyle = 29}$,

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

${extstyle {Bigl (} {igl (} xmapsto (ymapsto x ^ {2} + y ^ {2}) {igr)} (5) {Bigr)} (2)}$

${extstyle = (ymapsto 5 ^ {2} + y ^ {2}) (2)}$ // определение ${displaystyle x}$ использовался с ${displaystyle 5}$ во внутреннем выражении. Это похоже на β-редукцию.

${extstyle = 5 ^ {2} + 2 ^ {2}}$ // определение ${displaystyle y}$ использовался с ${displaystyle 2}$. Опять же, аналогично β-редукции.

${extstyle = 29}$

чтобы достичь того же результата.

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

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

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

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

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

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

• Переменная, ${displaystyle x}$, сам по себе является допустимым лямбда-термином
• если ${displaystyle t}$ - лямбда-член, а ${displaystyle x}$ переменная, то ${displaystyle (lambda x.t)}$ это лямбда-термин (называемый абстракция);
• если ${displaystyle t}$ и ${displaystyle s}$ являются лямбда-членами, тогда ${displaystyle (ts)}$ это лямбда-термин (называемый заявление).

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

An абстракция ${displaystyle lambda x.t}$ это определение анонимной функции, способной принимать один ввод ${displaystyle x}$ и подставив его в выражение ${displaystyle t}$Таким образом, он определяет анонимную функцию, которая принимает ${displaystyle x}$ и возвращается ${displaystyle t}$. Например, ${displaystyle lambda x.x ^ {2} +2}$ это абстракция для функции ${displaystyle f (x) = x ^ {2} +2}$ используя термин ${displaystyle x ^ {2} +2}$ за ${displaystyle t}$. Определение функции с абстракцией просто «устанавливает» функцию, но не вызывает ее. Абстракция связывает переменная ${displaystyle x}$ в срок ${displaystyle t}$.

An заявление ${displaystyle ts}$ представляет собой приложение функции ${displaystyle t}$ к входу ${displaystyle s}$, то есть представляет собой акт вызова функции ${displaystyle t}$ на входе ${displaystyle s}$ производить ${displaystyle t (s)}$.

В лямбда-исчислении не существует концепции объявления переменных. В таком определении, как ${displaystyle lambda x.x + y}$ (т.е. ${displaystyle f (x) = x + y}$) лямбда-исчисление рассматривает ${displaystyle y}$ как переменная, которая еще не определена. Абстракция ${displaystyle lambda x.x + y}$ синтаксически действителен и представляет функцию, которая добавляет свой ввод к еще неизвестному ${displaystyle y}$.

Могут использоваться скобки, которые могут потребоваться для устранения неоднозначности терминов. Например, ${displaystyle lambda x. ((lambda x.x) x)}$ и ${displaystyle (lambda x. (lambda x.x)) x}$ обозначают разные термины (хотя они по совпадению сводятся к одному и тому же значению). Здесь в первом примере определяется функция, лямбда-член которой является результатом применения x к дочерней функции, а второй пример - это применение самой внешней функции к входу x, который возвращает дочернюю функцию. Таким образом, оба примера оцениваются как функция идентичности ${displaystyle lambda x.x}$.

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

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

Например, ${displaystyle lambda x.x}$ представляет функция идентичности, ${displaystyle xmapsto x}$, и ${displaystyle (lambda x.x) y}$ представляет собой функцию идентичности, применяемую к ${displaystyle y}$. Дальше, ${displaystyle (лямбда x.y)}$ представляет постоянная функция ${displaystyle xmapsto y}$, функция, которая всегда возвращает ${displaystyle y}$, независимо от ввода. В лямбда-исчислении приложение функции рассматривается как левоассоциативный, так что ${displaystyle stx}$ средства ${displaystyle (st) x}$.

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

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

Основная форма эквивалентности, определяемая с помощью лямбда-терминов, - это альфа-эквивалентность. Он улавливает интуицию, что конкретный выбор связанной переменной в абстракции (обычно) не имеет значения. ${displaystyle lambda x.x}$ и ${displaystyle lambda y.y}$ являются альфа-эквивалентными лямбда-членами, и оба они представляют одну и ту же функцию (функцию идентичности). ${displaystyle x}$ и ${displaystyle y}$ не являются альфа-эквивалентными, потому что они не связаны в абстракции. Во многих презентациях обычно используются альфа-эквивалентные лямбда-термины.

Для определения β-редукции необходимы следующие определения:

Бесплатные переменные

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

• Свободные переменные ${displaystyle x}$ просто ${displaystyle x}$
• Набор свободных переменных ${displaystyle lambda x.t}$ - множество свободных переменных ${displaystyle t}$, но с ${displaystyle x}$ удаленный
• Набор свободных переменных ${displaystyle ts}$ является объединением множества свободных переменных ${displaystyle t}$ и набор свободных переменных ${displaystyle s}$.

Например, лямбда-термин, представляющий личность ${displaystyle lambda x.x}$ не имеет свободных переменных, но функция ${displaystyle lambda x.yx}$ имеет единственную свободную переменную, ${displaystyle y}$.

Замены с избеганием захвата

Предполагать ${displaystyle t}$, ${displaystyle s}$ и ${displaystyle r}$ являются лямбда-терминами и ${displaystyle x}$ и ${displaystyle y}$ являются переменными. ${displaystyle t [x: = r]}$ указывает на замену ${displaystyle r}$ за ${displaystyle x}$ в ${displaystyle t}$ в избегание захвата манера. Это определяется так, что:

• ${displaystyle x [x: = r] = r}$;
• ${displaystyle y [x: = r] = y}$ если ${displaystyle xeq y}$;
• ${displaystyle (ts) [x: = r] = (t [x: = r]) (s [x: = r])}$;
• ${displaystyle (lambda x.t) [x: = r] = lambda x.t}$;
• ${displaystyle (lambda y.t) [x: = r] = lambda y. (t [x: = r])}$ если ${displaystyle xeq y}$ и ${displaystyle y}$ не входит в свободные переменные ${displaystyle r}$. Переменная ${displaystyle y}$ считается "свежим" для ${displaystyle r}$.

Например, ${displaystyle (lambda x.x) [y: = y] = lambda x. (x [y: = y]) = lambda x.x}$, и ${displaystyle ((lambda x.y) x) [x: = y] = ((lambda x.y) [x: = y]) (x [x: = y]) = (lambda x.y) y}$.

Состояние свежести (требующее ${displaystyle y}$ не входит в свободные переменные ${displaystyle r}$) имеет решающее значение для обеспечения того, чтобы подстановка не изменяла смысл функций. Например, выполняется подстановка, которая игнорирует условие свежести: ${displaystyle (lambda x.y) [y: = x] = lambda x. (y [y: = x]) = lambda x.x}$. Эта замена превращает постоянную функцию ${displaystyle lambda x.y}$ в личность ${displaystyle lambda x.x}$ путем подстановки.

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

β-редукция

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

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

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

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

Определение

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

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

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

1. Если Икс переменная, то Икс ∈ Λ.
2. Если Икс переменная и M ∈ Λ, то (λИкс.M) ∈ Λ.
3. Если M, N ∈ Λ, то (M N) ∈ Λ.

Примеры правила 2 известны как абстракции и примеры правила 3 ​​известны как Приложения.^[15][16]

Обозначение

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

• Крайние круглые скобки опускаются: M N вместо (M N).
• Предполагается, что приложения левоассоциативны: вместо ((M N) P) можно написать M N P.^[17]
• Тело абстракции расширяется как можно правее: λИкс.M N означает λИкс.(M N), а не (λИкс.M) N.
• Сжимается последовательность абстракций: λИкс.λу.λz.N сокращенно λxyz.N.^[18][17]

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

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

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

1. FV (Икс) = {Икс}, куда Икс это переменная.
2. FV (λИкс.M) = FV (M) {Икс}.
3. FV (M N) = FV (M) ∪ FV (N).^[19]

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

Снижение

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

Есть три вида сокращения:

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

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

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

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

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

α-преобразование, иногда известное как α-переименование,^[21] позволяет изменять имена связанных переменных. Например, α-преобразование λИкс.Икс может дать λу.у. Термины, которые отличаются только α-преобразованием, называются α-эквивалент. Часто при использовании лямбда-исчисления α-эквивалентные термины считаются эквивалентными.

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

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

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

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

Замена

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

Икс[Икс := N] = N

у[Икс := N] = у, если Икс ≠ у

(M₁ M₂)[Икс := N] = (M₁[Икс := N]) (M₂[Икс := N])

(λИкс.M)[Икс := N] = λИкс.M

(λу.M)[Икс := N] = λу.(M[Икс := N]), если Икс ≠ у и у ∉ FV (N)

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

β-редукция

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

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

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

η-редукция

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

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

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

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

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

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

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

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

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

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

0: = λж.λИкс.Икс

1: = λж.λИкс.ж Икс

2: = λж.λИкс.ж (ж Икс)

3: = λж.λИкс.ж (ж (ж Икс))

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

0: = λFX.Икс

1: = λFX.ж Икс

2: = λFX.ж (ж Икс)

3: = λFX.ж (ж (ж Икс))

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

Один из способов думать о церковной цифре п, который часто бывает полезен при анализе программ, как повторение инструкции п раз ». Например, используя ПАРА и Ноль функций, определенных ниже, можно определить функцию, которая создает (связанный) список п элементы все равны Икс повторяя "добавить еще один" Икс элемент' п раз, начиная с пустого списка. Лямбда-член

λп.λИкс.п (ПАРА Икс) NIL

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

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

SUCC: = λп.λж.λИкс.ж (п ж Икс)

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

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

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

PLUS 2 3

и

5

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

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

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

НЕСКОЛЬКО: = λм.λп.λж.м (п ж)^[18]

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

НЕСКОЛЬКО: = λм.λп.м (ПЛЮС п) 0

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

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

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

PRED: = λп.λж.λИкс.п (λграмм.λчас.час (грамм ж)) (λты.Икс) (λты.ты)

можно проверить, индуктивно показывая, что если Т обозначает (λграмм.λчас.час (грамм ж)), тогда Т^(п)(λты.Икс) = (λчас.час(ж^(п−1)(Икс))) за п > 0. Два других определения PRED приведены ниже, один с использованием условные а другой использует пары. С функцией-предшественником вычитание выполняется просто. Определение

SUB: = λм.λп.п PRED м,

SUB м п дает м − п когда м > п и 0 иначе.

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

По соглашению следующие два определения (известные как логические значения Черча) используются для логических значений ИСТИННЫЙ и ЛОЖНЫЙ:

ИСТИНА: = λИкс.λу.Икс

ЛОЖЬ: = λИкс.λу.у

(Обратите внимание, что ЛОЖНЫЙ эквивалентно ноль Черча, определенному выше)

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

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

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

НЕ: = λп.п FALSE TRUE

IFTHENELSE: = λп.λа.λб.п а б

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

И ИСТИННАЯ ЛОЖЬ

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

≡ (λИкс.λу.Икс) ЛОЖЬ ИСТИНА →_β ЛОЖНЫЙ

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

А предикат - функция, возвращающая логическое значение. Самый фундаментальный предикат - это ISZERO, который возвращает ИСТИННЫЙ если его аргумент - цифра Чёрча 0, и ЛОЖНЫЙ если его аргумент - любое другое число Чёрча:

ISZERO: = λп.п (λИкс.FALSE TRUE

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

LEQ: = λм.λп.ISZERO (ПОДП. м п),

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

Доступность предикатов и приведенное выше определение ИСТИННЫЙ и ЛОЖНЫЙ сделать удобным написание выражений «если-то-еще» в лямбда-исчислении. Например, функцию-предшественницу можно определить как:

PRED: = λп.п (λграмм.λk.ISZERO (грамм 1) k (ПЛЮС (грамм k) 1)) (λv.0) 0

что можно проверить, индуктивно показав, что п (λграмм.λk.ISZERO (грамм 1) k (ПЛЮС (грамм k) 1)) (λv.0) это добавление п - 1 функция для п > 0.

Пары

Пару (2-кортеж) можно определить в терминах ИСТИННЫЙ и ЛОЖНЫЙ, используя Церковная кодировка для пар. Например, ПАРА инкапсулирует пару (Икс,у), ПЕРВЫЙ возвращает первый элемент пары, а ВТОРОЙ возвращает второй.

ПАРА: = λИкс.λу.λж.ж Икс у

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

ВТОРОЙ: = λп.п ЛОЖНЫЙ

NIL: = λИкс.ИСТИННЫЙ

NULL: = λп.п (λИкс.λу.ЛОЖНЫЙ)

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

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

Φ: = λИкс.PAIR (ВТОРОЙ Икс) (SUCC (ВТОРОЙ Икс))

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

PRED: = λп.ПЕРВЫЙ (п Φ (ПАРА 0 0)).

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

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

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

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

(λж.N) M

Авторы часто вводят синтаксический сахар, Такие как позволять, чтобы можно было писать вышесказанное в более интуитивном порядке

позволять ж =M в N

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

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

Рекурсия и фиксированные точки

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

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

F (п) = 1, если п = 0; еще п × F (п − 1).

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

G: = λр. λп. (1, если п = 0; еще п × (р р (п−1)))

с р р Икс = F Икс = G р Икс держать, так что {{{1}}} и

F: = G G = (λИкс.Икс Икс) ГРАММ

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

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

G: = λр. λп. (1, если п = 0; еще п × (р (п−1)))

с р Икс = F Икс = G р Икс держать, так что р = G р =: FIX G и

F: = FIX G куда ИСПРАВИТЬ грамм := (р куда р = грамм р) = грамм (ИСПРАВИТЬ грамм)

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

Учитывая лямбда-член с первым аргументом, представляющим рекурсивный вызов (например, грамм здесь), фиксированная точка комбинатор ИСПРАВИТЬ вернет самовоспроизводящееся лямбда-выражение, представляющее рекурсивную функцию (здесь F). Функцию не нужно явно передавать самой себе в любой момент, поскольку саморепликация организована заранее, когда она создается, чтобы выполняться каждый раз при ее вызове. Таким образом, исходное лямбда-выражение (ИСПРАВЛЕНИЕ G) воссоздается внутри себя, в точке вызова, достигая ссылка на себя.

На самом деле есть много возможных определений для этого ИСПРАВИТЬ оператор, простейший из них:

Y : = λграмм. (λИкс.грамм (Икс Икс)) (λИкс.грамм (Икс Икс))

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

Y грамм

(λчас. (λИкс.час (Икс Икс)) (λИкс.час (Икс Икс))) грамм

(λИкс.грамм (Икс Икс)) (λИкс.грамм (Икс Икс))

грамм ((λИкс.грамм (Икс Икс)) (λИкс.грамм (Икс Икс)))

грамм (Y грамм)

Теперь, чтобы выполнить рекурсивный вызов функции факториала, мы просто вызовем (Y ГРАММ) п, куда п это число, факториал которого мы вычисляем. Данный п = 4, например, это дает:

(Y G) 4

ГРАММ (Y G) 4

(λр.λп. (1, если п = 0; еще п × (р (п−1)))) (Y G) 4

(λп. (1, если п = 0; еще п × ((Y ГРАММ) (п−1)))) 4

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

4 × (G (Y G) (4−1))

4 × ((λп. (1, если п = 0; еще п × ((Y ГРАММ) (п−1)))) (4−1))

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

4 × (3 × (G (Y G) (3−1)))

4 × (3 × ((λп. (1, если п = 0; еще п × ((Y ГРАММ) (п−1)))) (3−1)))

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

4 × (3 × (2 × (G (Y G) (2−1))))

4 × (3 × (2 × ((λп. (1, если п = 0; еще п × ((Y ГРАММ) (п−1)))) (2−1))))

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

4 × (3 × (2 × (1 × (G (Y Г) (1−1)))))

4 × (3 × (2 × (1 × ((λп. (1, если п = 0; еще п × ((Y ГРАММ) (п−1)))) (1−1)))))

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

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

24

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

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

У некоторых терминов есть общепринятые названия:^{[нужна цитата ]}

я : = λИкс.Икс

K : = λИкс.λу.Икс

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

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

C : = λИкс.λу.λz.Икс z у

W : = λИкс.λу.Икс у у

U : = λИкс.Икс Икс

ω : = λИкс.Икс Икс

Ω := ω ω

Y : = λграмм. (λИкс.грамм (Икс Икс)) (λИкс.грамм (Икс Икс))

Некоторые из них имеют прямое применение в устранение абстракции что превращает лямбда-термины в комбинаторное исчисление термины.

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

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

Т(Икс, Икс) := я

Т(Икс, N) := K N если Икс не бесплатно в N.

Т(Икс, M N) := S Т(Икс, M) Т(Икс, N)

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

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

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

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

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

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

Вычислимые функции и лямбда-исчисление

Функция F: N → N натуральных чисел является вычислимой функцией тогда и только тогда, когда существует лямбда-выражение ж так что для каждой пары Икс, у в N, F(Икс)=у если и только если ж Икс =_β у, куда Икс и у числа Чёрча, соответствующие Икс и усоответственно и =_β означает эквивалентность с β-редукцией. Это один из многих способов определения вычислимости; увидеть Тезис Черча – Тьюринга для обсуждения других подходов и их эквивалентности.

Неразрешимость эквивалентности

Не существует алгоритма, который принимает на вход любые два лямбда-выражения и выходные данные. ИСТИННЫЙ или же ЛОЖНЫЙ в зависимости от того, эквивалентны ли эти два выражения.^[10] Точнее нет вычислимая функция может решать эквивалентность. Исторически это была первая проблема, неразрешимость которой могла быть доказана. Как обычно для такого доказательства, вычислимый означает вычислимый любым модель вычисления то есть Тьюринг завершен.

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

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

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

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

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

(лямбда (Икс) (* Икс Икс))

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

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

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

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

Полные β-редукции

Любой редекс можно уменьшить в любой момент. По сути, это означает отсутствие какой-либо конкретной стратегии сокращения - в отношении сводимости «все ставки выключены».

Заявочный порядок

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

Большинство языков программирования (включая Lisp, ML и императивные языки, такие как C и Ява ) описываются как «строгие», что означает, что функции, применяемые к ненормализующим аргументам, не являются нормализующими. По сути, это делается с использованием аппликативного порядка, вызывая уменьшение значения (Смотри ниже ), но обычно это называется «нетерпеливой оценкой».

Нормальный порядок

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

Звоните по цене

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

Звоните по имени

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

Звоните по необходимости

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

Аппликативный порядок - это не нормализующая стратегия. Обычный контрпример выглядит следующим образом: определить Ω = ωω куда ω = λИкс.хх. Все это выражение содержит только один редекс, а именно все выражение; его редукция снова Ω. Поскольку это единственное доступное сокращение, Ω не имеет нормальной формы (при любой стратегии оценки). Используя аппликативный порядок, выражение KIΩ = (λИкс.λу.Икс) (λИкс.Икс)Ω уменьшается первым уменьшением Ω к нормальной форме (так как это крайний правый редекс), но поскольку Ω не имеет нормальной формы, аппликативный порядок не может найти нормальную форму для KIΩ.

Напротив, нормальный порядок называется так потому, что он всегда находит нормализующее сокращение, если оно существует. В приведенном выше примере KIΩ уменьшается в обычном порядке до я, нормальная форма. Недостатком является то, что редексы в аргументах могут быть скопированы, что приведет к дублированию вычислений (например, (λИкс.хх) ((λИкс.Икс)у) сводится к ((λИкс.Икс)у) ((λИкс.Икс)у) используя эту стратегию; теперь есть два редекса, поэтому для полной оценки требуется еще два шага, но если бы аргумент был уменьшен первым, теперь не было бы ни одного).

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

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

Замечание о сложности

Хотя идея β-редукции кажется достаточно простой, это не атомарный шаг, поскольку он должен иметь нетривиальную стоимость при оценке вычислительная сложность.^[25] Чтобы быть точным, нужно как-то найти расположение всех вхождений связанной переменной V в выражении E, подразумевая затраты времени, или нужно каким-то образом отслеживать эти места, подразумевая затраты на пространство. Наивный поиск локаций V в E является О(п) в длину п из E. Это привело к изучению систем, использующих явная подстановка. Синота режиссерские струны^[26] предлагают способ отслеживания местоположения свободных переменных в выражениях.

Параллелизм и параллелизм

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

Оптимальное сокращение

В статье Леви 1988 г. "Совместное использование при оценке лямбда-выражений ", он определяет понятие оптимального распределения, так что никакая работа не дублированный. Например, выполнение β-восстановления в нормальном порядке на (λИкс.хх) (II) сводит его к II (II). Аргумент II дублируется приложением на первый лямбда-член. Если сокращение сначала было выполнено в аппликативном порядке, мы сохраняем работу, потому что работа не дублируется: (λИкс.хх) (II) сводится к (λИкс.хх) Я. С другой стороны, использование аппликативного порядка может привести к избыточным сокращениям или даже, возможно, никогда не привести к нормальной форме. Например, выполнение β-восстановления в нормальном порядке на (λж.f I) (λy. (λИкс.хх) (у I)) дает (λy. (λИкс.хх) (y I)) I, (λИкс.хх) (II) мы знаем, что можем обойтись без дублирования работы. То же самое, но в прикладном порядке дает (λж.f I) (λy.y I (y I)), (λy.y I (y I)) I, Я я (я я), и теперь работа дублируется.

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

((λg. (g (g (λx.x)))) (λh. ((λf. (f (f (λz.z)))) (λw. (h (w (λy.y)))) )))

Он состоит из трех одинаковых терминов: х = ((λg. ...) (λh.y)) и y = ((λf. ...) (λw.z)), и наконец z = λw. (h (w (λy.y))). Здесь можно сделать только две возможные β-редукции: по x и по y. Уменьшение внешнего члена x сначала приводит к дублированию внутреннего члена y, и каждая копия должна быть уменьшена, но уменьшение сначала внутреннего члена y будет дублировать его аргумент z, что приведет к дублированию работы, когда значения h и w становятся известными. Между прочим, этот член сводится к тождественной функции (λy.y), и создается путем создания оболочек, которые делают функцию идентификации доступной для связывателей g = λh ..., f = λw ..., h = λx.x (сначала), и w = λz.z (сначала), все из которых применяются к самому внутреннему члену λy.y.

Точное понятие дублированной работы основано на замечании того, что после первого сокращения Я я сделано, ценность другого Я я могут быть определены, поскольку они имеют одинаковую структуру (и фактически имеют одинаковые значения) и являются результатом общего предка. Каждой из таких похожих структур можно присвоить метку, которую можно отслеживать при сокращении. Если имя присвоено редексу, который производит все результирующие II термины, а затем все повторяющиеся вхождения II можно отследить и уменьшить за один раз. Однако не очевидно, что редекс приведет к II срок. Выявление структур, которые похожи в разных частях лямбда-члена, может включать сложный алгоритм и, возможно, иметь сложность, равную истории самого сокращения.

Хотя Леви определяет понятие оптимального совместного использования, он не предлагает алгоритма для этого. В статье Винсента ван Острома, Кис-Яна ван де Лойя и Марин Цвицерлоуд Лямбдаскоп: еще одна оптимальная реализация лямбда-исчисления, они предоставляют такой алгоритм, преобразовывая лямбда-члены в сети взаимодействия, которые затем уменьшаются. Грубо говоря, результирующая редукция является оптимальной, потому что каждый член, который будет иметь те же метки, что и в статье Леви, также будет тем же графом в сети взаимодействий. В документе они упоминают, что их прототипная реализация Lambdascope работает так же, как оптимизированный версия эталонной оптимальной машины высшего порядка BOHM.^[b]

Семантика

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

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

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

Варианты и расширения

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

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

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

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

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

• Исчисление каппа - Аналог первого порядка лямбда-исчисления

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

• Комбинаторная логика - Обозначение математической логики без переменных
• Расчет комбинатора SKI - Вычислительная система на основе S, K и я комбинаторы, эквивалентные лямбда-исчислению, но приводимые без подстановки переменных

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

Примечания

Рекомендации

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

• Абельсон, Гарольд и Джеральд Джей Сассман. Структура и интерпретация компьютерных программ. MIT Press. ISBN  0-262-51087-1.
• Хендрик Питер Барендрегт Введение в лямбда-исчисление.
• Хенк Барендрегт, Влияние лямбда-исчисления в логике и информатике. Бюллетень символической логики, том 3, номер 2, июнь 1997 г.
• Барендрегт, Хендрик Питер, Лямбда-исчисление без типов pp1091–1132 из Справочник по математической логике, Северная Голландия (1977) ISBN  0-7204-2285-X
• Кардоне и Хиндли, 2006. История лямбда-исчисления и комбинаторной логики. В Габбее и Вудсе (ред.), Справочник по истории логики, т. 5. Эльзевир.
• Церковь, Алонсо, Неразрешимая проблема элементарной теории чисел, Американский журнал математики, 58 (1936), стр. 345–363. Эта статья содержит доказательство того, что эквивалентность лямбда-выражений, вообще говоря, неразрешима.
• Церковь Алонсо, Исчисления лямбда-преобразования (ISBN  978-0-691-08394-0) ^[1]
• Фринк-младший, Оррин, Обзор: исчисления лямбда-преобразования ^[2]
• Клини, Стивен, Теория натуральных чисел в формальной логике, Американский журнал математики, 57 (1935), стр. 153–173 и 219–244. Содержит определения лямбда-исчисления для нескольких знакомых функций.
• Ландин, Питер, Соответствие между АЛГОЛОМ 60 и лямбда-нотацией Чёрча, Коммуникации ACM, т. 8, вып. 2 (1965), страницы 89–101. Доступно на Сайт ACM. Классическая статья, подчеркивающая важность лямбда-исчисления как основы для языков программирования.
• Ларсон, Джим, Введение в лямбда-исчисление и схему. Мягкое введение для программистов.
• Шалк, А. и Симмонс, Х. (2005) Введение в λ-исчисления и арифметику с приличным набором упражнений. Примечания к курсу магистра математической логики в Манчестерском университете.
• де Кейруш, Руй Ж. (2008). «О правилах редукции, использовании смысла и теоретической семантике». Studia Logica. 90 (2): 211–247. Дои:10.1007 / s11225-008-9150-5. S2CID  11321602. Документ, в котором формально обосновывается идея «значение-есть-использование», которая, даже если основана на доказательствах, отличается от теоретико-доказательной семантики, как в традиции Даммета – Правица, поскольку она принимает редукцию как правила, придающие смысл.
• Ханкин, Крис, Введение в лямбда-исчисления для компьютерных ученых, ISBN  0954300653

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

• Мортен Гейне Соренсен, Павел Уржичин, Лекции об изоморфизме Карри – Ховарда, Эльзевир, 2006, ISBN  0-444-52077-5 - это недавняя монография, которая охватывает основные темы лямбда-исчисления от разнообразия типов до большинства типизированные лямбда-исчисления, включая более свежие разработки, такие как системы чистого типа и лямбда-куб. Не покрывает подтип расширения.
• Пирс, Бенджамин (2002), Типы и языки программирования, MIT Press, ISBN  0-262-16209-1 охватывает лямбда-исчисления с точки зрения системы практических типов; некоторые темы, такие как зависимые типы, только упоминаются, но выделение подтипов является важной темой.

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

внешняя ссылка

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