Дедуктивное лямбда-исчисление - Deductive lambda calculus

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

История

Церковь Алонсо изобрел лямбда-исчисление в 1930-х годах, первоначально чтобы обеспечить новую и более простую основу для математики.^[1]^[2] Однако вскоре после его изобретения основные логические проблемы были выявлены с определением абстракции лямбда: Парадокс Клини – Россера это реализация Парадокс ричарда в лямбда-исчислении.^[3] Хаскелл Карри обнаружили, что ключевой шаг в этом парадоксе может быть использован для реализации более простого Парадокс карри. Существование этих парадоксов означало, что лямбда-исчисление не могло быть одновременно непротиворечивым и полным. дедуктивная система.^[4]

Хаскелл Карри изучал илативный (дедуктивный) комбинаторная логика в 1941 г.^[5] Комбинаторная логика тесно связана с лямбда-исчислением, и в каждом из них существуют одни и те же парадоксы.

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

Вступление

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

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

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

Терминология

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

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

Следующая таблица резюмирует;

Имя	Обозначение
Лямбда-абстракция.	${ displaystyle lambda v.y}$
Применение функции ж к Икс	${ displaystyle f x}$
Умножение а к б	${ displaystyle a cdot b}$
Позволять Икс в у	${ displaystyle operatorname {let} x operatorname {in} y}$
Математическое равенство	${ displaystyle m = n}$
Бета сводимое равенство	${ Displaystyle м { underset { beta} {=}} п}$

Интерпретация лямбда-исчисления как математики

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

{ displaystyle operatorname {eta-reduct} [X] = X}

{ displaystyle operatorname {beta-reduct} [X] = X}

Эта редукция как математика

Эта-редукт определяется как,

{ displaystyle x not in operatorname {FV} (f) to operatorname {eta-reduct} [ lambda x. (f x)] = f}

В математической интерпретации

{ displaystyle operatorname {eta-reduct} [X] = X}

Тогда принимая f за переменную,

{ Displaystyle лямбда х. (е х) = е}

или позволив ${ Displaystyle е х = у}$

{ displaystyle f x = y iff f = lambda x.y}

Это определение определяет ${ displaystyle lambda x.y}$ быть решением для ж в уравнении,

{ Displaystyle е х = у}

Бета-редукция как математика

Бета-редукт - это,

{ displaystyle operatorname {beta-reduct} [( lambda x.b) z] = b [x: = z]}

и, как,

{ displaystyle operatorname {beta-reduct} [X] = X}

тогда,

{ Displaystyle ( лямбда x.b) z = Ь [x: = z]}

Это правило подразумевается реализация из количественно переменные. Если,

{ displaystyle forall x: f x = y}

тогда ${ displaystyle f z}$ - выражение y с количественной переменной x, представленной как z.

{ Displaystyle е Z = у [х: = г]}

так,

{ Displaystyle ( лямбда x.y) z = y [x: = z]}

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

Несоответствие принципу бивалентности

Пусть z будет Булево; тогда мы можем составить уравнение без решений,

{ displaystyle z = neg z}

Чтобы решить это уравнение рекурсией, введем новую функцию $ж$ определяется,

{ Displaystyle е п = нег (п п)}

куда $п$ вспомогательная переменная для хранения значения рекурсии. (Мы считаем, что ${ displaystyle neg}$ по-прежнему возвращает логическое значение, даже если ему задан не-логический аргумент.) С помощью eta-редукции мы получаем,

{ Displaystyle е = лямбда х. neg (х х)}

А потом,

{ Displaystyle { begin {align} е е & = ( лямбда х. neg (х х)) ( лямбда х. neg (х х)) & = neg (( лямбда х . neg (x x)) ( lambda x. neg (x x))) & = neg (f f) end {align}}}

потом $f f$ не является ни истинным, ни ложным, и поскольку $f f$ является логическим значением (на любом $Икс$ , $ж$ возвращает логическое значение ${ Displaystyle neg (х х)}$ ) то мы видим, что $f f$ не является ни истинным, ни ложным; это также демонстрирует, что отрицание имеет меньше смысла в применении к нелогическим значениям.

Интенсиональное и экстенсиональное равенство

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

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

В экстенсиональный определение равенства функций состоит в том, что две функции равны, если они выполняют одно и то же отображение;

{ Displaystyle е = г iff ( forall xf x = g x)}

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

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

Пример

В арифметика, то распределительный закон подразумевает, что ${ displaystyle 2 * (r + s) = 2 * r + 2 * s}$ . С использованием Церковная кодировка цифр левая и правая части могут быть представлены как лямбда-члены.

Итак, закон распределения гласит, что две функции,

{ displaystyle lambda r. lambda s.2 * (r + s) = lambda r. lambda s.2 * r + 2 * s}

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

{ displaystyle { begin {align} lambda r. lambda s. operatorname {mult} 2 ( operatorname {plus} r s) & = lambda r. lambda s. operatorname {plus } ( OperatorName {mult} 2 r) ( Operatorname {mult} 2 s) { scriptstyle lambda r. lambda s. ( lambda m. lambda n. lambda fm (n f)) ( lambda f. lambda xf (f x)) (( lambda m. lambda n. lambda f. lambda xm f (n f x )) r s)} & = { scriptstyle lambda r. lambda s. ( lambda m. lambda n. lambda f. lambda xm f (n f x)) ( ( lambda m. lambda n. lambda fm (n f)) ( lambda f. lambda xf (f x)) r) (( lambda m. lambda n. lambda fm (n f)) ( lambda f. lambda xf (f x)) s)} lambda r. lambda s. lambda f. lambda xr f ( s f (r f (s f x))) & = lambda r. lambda s. lambda f. lambda xr f (r f (s f (s е х))) конец {выровнено}}}

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

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

Если для всех лямбда-выражений $т$ у нас есть ${ Displaystyle е т { подмножество { бета} {=}} г т}$ , тогда ${ displaystyle f { underset { beta} {=}} g}$ .

В нашей ситуации «все лямбда-выражения» означают «все числительные Чёрча», так что это также омега-правило в стандартном смысле. Обратите внимание, что из правила омега следует правило эта, поскольку ${ Displaystyle е T { underset { beta} {=}} ( lambda x.f x) t}$ бета-редукцией с правой стороны.

Теоретико-множественная область

Лямбда-абстракции - это функции функций. Естественным шагом является определение домена для лямбда-абстракции как набора всех функций.

Набор всех функций из домена D к диапазону р дан кем-то K в,

{ displaystyle f in K iff ( forall x: x in D подразумевает f x in R)}

Тогда (мнимое) определение множества всех функций функций дается формулой F в,

{ Displaystyle f in F iff ( forall x: x in F подразумевает, что f x in F)}

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

Теперь лямбда-исчисление определяется бета-редукцией и эта-редукцией. Интерпретация редукции как определения равенства дает неявную область лямбда-исчисления. Правила таковы,

Каждая лямбда-абстракция имеет одно значение.
Бета-сокращение лямбда-члена имеет такое же значение.
Такое же значение имеет сокращение эта лямбда-члена.
Альфа-конвертируемые лямбда-члены равны.
[Если присутствует омега-правило] «омега-эквивалентные» лямбда-члены равны.
Если два лямбда-члена не могут быть показаны как равные по приведенным выше правилам, они не равны.

Если два лямбда-члена можно привести к нормальной форме, то Теорема Черча – Россера может использоваться, чтобы показать, что они равны, если их нормальные формы альфа-конвертируемы.

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

Пример: нет решений → одно решение

Например, уравнение ${ displaystyle x = neg x}$ может быть закодирован Церковная кодировка и используя Y комбинатор Карри в качестве,

{ displaystyle operatorname {not} _ {1} = lambda p. lambda a. lambda b.p b a}

{ displaystyle ( lambda f. ( lambda x.f (x x)) ( lambda x.f (x x))) ( lambda p. lambda a. lambda b.p b a)}

И рекурсия,

{ displaystyle ( lambda x. ( lambda p. lambda a. lambda bp b a) (x x)) ( lambda x. ( lambda p. lambda a. lambda bp б а) (х х))}

{ displaystyle ( lambda p. lambda a. lambda bp b a) (( lambda x. ( lambda p. lambda a. lambda bp b a) (x x) ) ( lambda x. ( lambda p. lambda a. lambda bp b a) (x x)))}

{ displaystyle lambda a. lambda b. (( lambda x. ( lambda p. lambda a. lambda bp b a) (x x)) ( lambda x. ( lambda p. lambda a. lambda bp b a) (x x))) b a}

...

{ displaystyle lambda a. lambda b. ( lambda a. lambda b. (( lambda x. ( lambda p. lambda a. lambda bp b a) (x x)) ( lambda x. ( lambda p. lambda a. lambda bp b a) (x x))) b a) b a}

... (бета, а затем уменьшение эта)

{ displaystyle ( lambda x. ( lambda p. lambda a. lambda bp b a) (x x)) ( lambda x. ( lambda p. lambda a. lambda bp б а) (х х))}

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

Пример: несколько решений → одно решение

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

Используя такую кодировку,

{ displaystyle x ^ {2} = n Rightarrow x = { frac {n} {x}} Rightarrow f x = { frac {n} {x}} land Y f = x}

Используя реализацию разделять тогда,

{ Displaystyle Y ( OperatorName {разделять} п)}

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