Комбинатор с фиксированной точкой

В математике и Информатика в общем, фиксированная точка функции - это значение, которое функция отображает сама себе. В комбинаторная логика за Информатика, а комбинатор с фиксированной точкой (или же комбинатор фиксированной точки)^[1]^{:стр. 26} это функция высшего порядка ${ displaystyle { extf {fix}}}$ который возвращает некоторую фиксированную точку своей функции аргумента, если таковая существует.

Формально, если функция ж имеет одну или несколько фиксированных точек, то

{ Displaystyle { extf {fix}} f = f ({ extf {fix}} f) ,}

и, следовательно, при повторном применении

{ Displaystyle { extf {fix}} е = е (е ( ldots f ({ extf {fix}} f) ldots)) .}

Y комбинатор

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

{ Displaystyle { extf {Y}} = lambda f. ( lambda x.f (x x)) ( lambda x.f (x x))}

^[2]^:131^{[примечание 1]}^{[заметка 2]}

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

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

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

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

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

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

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

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

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

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

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

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

Ценности и домены

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

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

Например, рассмотрим,

{ displaystyle x ^ {2} = - 1 Rightarrow x = { frac {-1} {x}} Rightarrow f x = { frac {-1} {x}} land { extf {Y }} f = x}

Разделение из Подписанные числа может быть реализован в кодировке Чёрча, поэтому ж может быть представлен лямбда-термином. Это уравнение не имеет решения в действительных числах. Но в области сложные числа я и -я решения. Это демонстрирует, что могут быть решения уравнения в другой области. Однако лямбда-член для решения приведенного выше уравнения более странный, чем это. Лямбда-член ${ displaystyle Y f}$ представляет состояние, в котором x может быть либо я или же -я, как одно значение. Информация, различающая эти два значения, была потеряна при смене домена.

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

Функция против реализации

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

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

Что такое комбинатор?

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

Использование в программировании

Комбинаторы с фиксированной запятой могут использоваться для реализации рекурсивное определение функций. Однако в практическом программировании они используются редко.^[4] Сильно нормализующий системы типов такой как просто типизированное лямбда-исчисление запретить незавершение и, следовательно, комбинаторам с фиксированной точкой часто не может быть назначен тип или требуются системные функции сложных типов. Кроме того, комбинаторы с фиксированной точкой часто неэффективны по сравнению с другими стратегиями реализации рекурсии, поскольку они требуют большего количества сокращений функций и построения и разделения кортежа для каждой группы взаимно рекурсивных определений.^[1]^{:стр. 232}

Факториальная функция

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

{ displaystyle F f n = ( Operatorname {IsZero} n) 1 ( Operatorname {multiply} n (f ( Operatorname {pred} n)))}

Это дает Y F n в качестве,

{ Displaystyle { extf {fix}} F n}

{ Displaystyle = F ({ extf {fix}} F) n}

{ displaystyle = ( operatorname {IsZero} n) 1 ( Operatorname {multiply} n (({ extf {fix}} F) ( operatorname {pred} n)))}

Параметр ${ Displaystyle { extf {fix}} F = operatorname {fact}}$ дает,

{ Displaystyle OperatorName {fact} N = ( Operatorname {IsZero} n) 1 ( Operatorname {multiply} n ( Operatorname {fact} ( Operatorname {pred} n))) }

Это определение ставит F в роли тела цикла, который нужно повторить, и эквивалентен математическому определению факториала:

{ displaystyle operatorname {fact} n = operatorname {if} n = 0 operatorname {then} 1 operatorname {else} n * operatorname {fact} (n-1)}

Комбинаторы с фиксированной точкой в лямбда-исчислении

В Y комбинатор, открытый Хаскелл Б. Карри, определяется как:

{ Displaystyle Y = lambda f. ( lambda x.f (x x)) ( lambda x.f (x x))}

Бета-редукция из этого дает,

${ displaystyle Y g}$	${ Displaystyle = ( lambda f. ( lambda x.f (x x)) ( lambda x.f (x x))) g}$	(по определению Y)
	${ Displaystyle = ( lambda x.g (x x)) ( lambda x.g (x x))}$	(к β-редукция of λf: применено Y к g)
	${ Displaystyle = г (( lambda x.g (x x)) ( lambda x.g (x x)))}$	(путем β-редукции λx: применена левая функция к правой функции)
	${ Displaystyle = г (Y г)}$	(по второму равенству)

Повторно применяя это равенство, получаем

{ Displaystyle Y g = g (Y g) = g (g (Y g)) = g ( ldots g (Y g) ldots)}

Обратите внимание, что приведенное выше равенство следует рассматривать как последовательность многоступенчатых β-редукций слева направо. Лямбда-член ${ displaystyle g (Y g)}$ не может, как правило, β-сводиться к термину ${ displaystyle Y g}$ . Знаки равенства можно интерпретировать как β-эквивалентности вместо многоступенчатых β-редукций, позволяющих двигаться в обоих направлениях.

Эквивалентное определение комбинатора с фиксированной точкой

Этот комбинатор с фиксированной точкой можно определить как у в,

{ Displaystyle х = е х земля у е = х}

Выражение для y может быть получено с использованием правил из определение let выражения. Во-первых, используя правило,

{ Displaystyle ( существует xE земля F) iff operatorname {let} x: E operatorname {in} F}

дает,

{ displaystyle operatorname {let} x = f x operatorname {in} y f = x}

Также используя,

{ displaystyle x not in operatorname {FV} (E) land x in operatorname {FV} (F) to operatorname {let} x: G operatorname {in} E F = E ( operatorname {let} x: G operatorname {in} F)}

дает

{ displaystyle y f = operatorname {let} x = f x operatorname {in} x}

Затем с помощью эта редукция правило

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

дает,

{ displaystyle y = lambda f. operatorname {let} x = f x operatorname {in} x}

Вывод комбинатора Y

Комбинатор Карри Y легко получить из определения у.^[5]Начиная с,

{ displaystyle lambda f. operatorname {let} x = f x operatorname {in} x}

Лямбда-абстракция не поддерживает ссылку на имя переменной в применяемом выражении, поэтому Икс должен быть передан как параметр в Икс. Мы можем думать об этом как о замене Икс к х х, но формально это неверно. Вместо определения у к ${ displaystyle forall z, y z = x}$ дает,

{ displaystyle lambda f. operatorname {let} y z = f (y z) operatorname {in} y z}

Выражение let можно рассматривать как определение функции у, куда z это параметр. Создание z в качестве у в звонке дает,

{ displaystyle lambda f. operatorname {let} y z = f (y z) operatorname {in} y y}

А поскольку параметр z всегда передает функцию у.

{ displaystyle lambda f. operatorname {let} y z = f (z z) operatorname {in} y y}

С использованием эта редукция правило

{ Displaystyle е х = у эквив е = лямбда х.у}

дает,

{ displaystyle lambda f. operatorname {let} y = lambda z.f (z z) operatorname {in} y y}

А выражение let может быть выражено как лямбда-абстракция с помощью,

{ displaystyle n not in FV (E) to ( operatorname {let} n = E operatorname {in} L Equiv ( lambda n.L) E)}

дает,

{ Displaystyle лямбда е. ( лямбда у.у у) ( лямбда з.ф (г г))}

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

{ displaystyle lambda f. ( lambda z.f (z z)) ( lambda z.f (z z))}

Другие комбинаторы с фиксированной точкой

В нетипизированном лямбда-исчислении комбинаторы с фиксированной точкой не особенно редки. На самом деле их бесконечно много.^[6] В 2005 году Майер Голдберг показал, что набор комбинаторов с фиксированной точкой нетипизированного лямбда-исчисления является рекурсивно перечислимый.^[7]

В Y комбинатор можно выразить в виде SKI-исчисление в качестве

{ Displaystyle Y = S (К (SII)) (S (S (KS) K) (K (SII)))}

Простейший комбинатор с фиксированной точкой в SK-исчислении, найденный с помощью Джон Тромп, является

{ Displaystyle Y '= SSK (S (K (SS (S (SSK)))) K)}

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

{ Displaystyle Y '= ( lambda xy.xyx) ( lambda yx.y (xyx))}

Следующий комбинатор с фиксированной точкой проще, чем комбинатор Y, и β-сводится к комбинатору Y; его иногда называют самим комбинатором Y:

{ displaystyle X = lambda f. ( lambda x.xx) ( lambda x.f (xx))}

Другой распространенный комбинатор с фиксированной точкой - это комбинатор с фиксированной точкой Тьюринга (названный в честь его первооткрывателя, Алан Тьюринг ):^[8]^[2]^:132

{ Displaystyle Theta = ( lambda xy.y (xxy)) ( lambda xy.y (xxy))}

Его преимущество перед ${ Displaystyle { extf {Y}}}$ в том, что ${ displaystyle Theta f}$ бета-сводится к ${ Displaystyle f ( Theta f)}$ ,^{[заметка 3]}в то время как ${ Displaystyle { extf {Y}} f}$ и ${ Displaystyle е ({ extf {Y}} е)}$ только бета-сводить к общему члену.^{[заметка 2]}

${ displaystyle Theta}$ также есть простая форма вызова по значению:

{ Displaystyle Theta _ {v} = ( lambda xy.y ( lambda z.xxyz)) ( lambda xy.y ( lambda z.xxyz))}

Аналог для взаимная рекурсия это поливариадический комбинатор неподвижных точек,^[9]^[10]^[11] которое можно обозначить Y *.

Строгий комбинатор с фиксированной точкой

В строгий язык программирования язык комбинатор Y будет расширяться до переполнения стека или никогда не останавливаться в случае оптимизации хвостового вызова.^[12] В Z комбинатор будет работать на строгих языках (также называемых энергичными языками, где применяется аппликативный порядок оценки). В Z комбинатор имеет следующий аргумент, определенный явно, предотвращая расширение Z g в правой части определения:^[13]

{ Displaystyle Zgv = г (Zg) v}

а в лямбда-исчислении это эта-разложение Y комбинатор:

{ Displaystyle Z = lambda f. ( lambda x.f ( lambda v.xxv)) ( lambda x.f ( lambda v.xxv))}

Нестандартные комбинаторы с фиксированной точкой

В нетипизированном лямбда-исчислении есть термины, которые имеют одинаковые Дерево Бема как комбинатор с неподвижной точкой, то есть они имеют одно и то же бесконечное расширение λx.x (x (x ...)). Они называются нестандартные комбинаторы с фиксированной точкой. Любой комбинатор с фиксированной точкой также является нестандартным, но не все нестандартные комбинаторы с фиксированной точкой являются комбинаторами с фиксированной точкой, потому что некоторые из них не удовлетворяют уравнению, которое определяет «стандартные». Эти странные комбинаторы называются строго нестандартные комбинаторы с фиксированной точкой; примером является следующий комбинатор;

{ Displaystyle N = BM (B (BM) B)}

куда,

{ Displaystyle B = лямбда xyz.x (yz)}

{ displaystyle M = lambda x.xx}

Множество нестандартных комбинаторов с фиксированной точкой не рекурсивно перечислимо.^[7]

Реализация на других языках

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

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

Ленивая функциональная реализация

На языке, поддерживающем ленивая оценка, как в Haskell, можно определить комбинатор с фиксированной точкой, используя определяющее уравнение комбинатора с фиксированной точкой, которое условно называют исправить. Поскольку Haskell имеет ленивые типы данных, этот комбинатор также можно использовать для определения фиксированных точек конструкторов данных (а не только для реализации рекурсивных функций). Здесь дано определение, за которым следуют некоторые примеры использования. В Hackage исходный образец: ^[14]

исправить, исправить' :: (а -> а) -> аисправить ж = позволять Икс = ж Икс в Икс         - Лямбда упала. Совместное использование.                                 - Исходное определение в Data.Function.- альтернатива:исправить' ж = ж (исправить' ж)              - Лямбда поднялась. Не делиться.исправить (\Икс -> 9)                    - это оценивается в 9исправить (\Икс -> 3:Икс)                  - вычисляет ленивый бесконечный список [3,3,3, ...]факт = исправить фак                   - оценивает факториальную функцию  куда фак ж 0 = 1        фак ж Икс = Икс * ж (Икс-1)факт 5                           - оценивается в 120

Строгая функциональная реализация

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

{ Displaystyle е (е ... (е ( operatorname {fix} f)) ...) x}

.

Это может быть решено путем определения исправления с дополнительным параметром.

позволять rec исправить ж Икс = ж (исправить ж) Икс (* обратите внимание на лишний x; здесь исправьте f =  x-> f (исправьте f) x *)позволять факты факт = функция   (* factabs имеет дополнительный уровень абстракции лямбда *)   0 -> 1 | Икс -> Икс * факт (Икс-1)позволять _ = (исправить факты) 5       (* оценивается как «120» *)

Реализация императивного языка

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

шаблон <typename р, typename D>учебный класс ремонтник{общественный:    р исправить(D Икс)    {        возвращаться ж(Икс);    }частный:    виртуальный р ж(D) = 0;};учебный класс факт : общественный ремонтник<длинный, длинный>{    виртуальный длинный ж(длинный Икс)    {        если (Икс == 0)        {            возвращаться 1;        }        возвращаться Икс * исправить(Икс-1);    }};длинный результат = факт().исправить(5);

В императивно-функциональном языке, таком как Лисп, Схема, или же Ракетка, Ландин (1963)^{[требуется полная цитата ]} предлагает использовать присвоение переменной для создания комбинатора с фиксированной точкой:

(определять Ы!  (лямбда (f-maker)    ((лямбда (ж)       (набор! ж (f-maker (лямбда (Икс) (ж Икс)))) ;; оператор присваивания        ж)     'НИКТО)))

Используя лямбда-исчисление с аксиомами для операторов присваивания, можно показать, что Y! удовлетворяет тому же закону фиксированной точки, что и комбинатор Y вызова по значению:^[15]^[16]

{ displaystyle ({ extf {Y}} _ {!} lambda x.e) e '= ( lambda x.e) ({ extf {Y}} _ {!} lambda x.e) e'}

Печатать

В полиморфное лямбда-исчисление (Система F ) полиморфный комбинатор неподвижной точки имеет тип^{[нужна цитата ]};

∀a. (A → a) → a

куда а это переменная типа. То есть, исправить принимает функцию, которая отображает a → a и использует ее для возврата значения типа a.

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

в просто типизированное лямбда-исчисление комбинатору фиксированной точки Y нельзя присвоить тип^[17] потому что в какой-то момент он будет иметь дело с подпунктом самостоятельного применения ${ Displaystyle х ~ х}$ по правилу применения:

{ displaystyle { Gamma vdash x !: ! t_ {1} to t_ {2} quad Gamma vdash x !: ! t_ {1}} over { Gamma vdash x ~ х !: ! t_ {2}}}

куда ${ displaystyle x}$ имеет бесконечный тип ${ displaystyle t_ {1} = t_ {1} to t_ {2}}$ . Фактически невозможно типизировать комбинатор с фиксированной точкой; в этих системах любая поддержка рекурсии должна быть явно добавлена к языку.

Тип для комбинатора Y

На языках программирования, поддерживающих рекурсивные типы можно ввести комбинатор Y, соответствующим образом учитывая рекурсию на уровне типа. Потребность в самостоятельном применении переменной x может быть устранена с помощью типа (Rec a), который определен как изоморфный (Rec a -> a).

Например, в следующем коде Haskell у нас есть В и из являясь названиями двух направлений изоморфизма, с типами:^[18]^[19]

В :: (Rec а -> а) -> Rec аиз :: Rec а -> (Rec а -> а)

что позволяет нам писать:

Новый тип Rec а = В { из :: Rec а -> а }у :: (а -> а) -> ау = \ж -> (\Икс -> ж (из Икс Икс)) (В (\Икс -> ж (из Икс Икс)))

Или, что то же самое в OCaml:

тип 'а recc = В из ('а recc -> 'а)позволять из (В Икс) = Икспозволять у ж = (весело Икс а -> ж (из Икс Икс) а) (В (весело Икс а -> ж (из Икс Икс) а))

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

позволять у ж = (весело Икс -> ж (весело z -> из Икс Икс z)) (В (весело Икс -> ж (весело z -> из Икс Икс z)))

Общая информация

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

Функция, для которой каждый вход является фиксированной точкой называется функция идентичности. Формально:

{ Displaystyle forall х (е х = х)}

В отличие от универсальной количественной оценки по всем ${ displaystyle x}$ комбинатор с фиксированной точкой строит один значение, которое является фиксированной точкой ${ displaystyle f}$ . Замечательное свойство комбинатора неподвижной точки состоит в том, что он строит неподвижную точку для произвольно данный функция ${ displaystyle f}$ .

Другие функции обладают особым свойством: после однократного применения дальнейшие приложения не имеют никакого эффекта. Более формально:

{ Displaystyle forall х (е (е х) = е х)}

Такие функции называются идемпотент (смотрите также проекция ). Примером такой функции является функция, возвращающая 0 для всех четных чисел и 1 для всех нечетных целых чисел.

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

{ Displaystyle (Y lambda x.x) = ( lambda x. (xx) lambda x. (xx))}

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

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

Комбинатор Y позволяет рекурсия быть определенным как набор переписать правила,^[20] не требуя встроенной поддержки рекурсии в языке.^[21]

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

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

Примечания

^ В этой статье правила синтаксиса, указанные в Лямбда-исчисление # Обозначение используются, чтобы сохранить круглые скобки.
^ ^а ^б Для произвольного лямбда-члена ж, свойство фиксированной точки можно проверить, уменьшив бета-версию левой и правой части: ${ Displaystyle { extf {Y}} f}$ ${ Displaystyle Equiv}$ ${ displaystyle ( lambda f. ( lambda x.f (xx)) ( lambda x.f (xx))) f}$ ${ displaystyle to}$ ${ Displaystyle ( лямбда х.f (хх)) ( лямбда х.f (хх))}$ ${ displaystyle to}$ ${ Displaystyle е (( lambda x.f (xx)) ( lambda x.f (xx)))}$ ,куда ${ Displaystyle Equiv}$ и ${ displaystyle to}$ обозначают синтаксическое равенство по определению и бета-редукцию соответственно. Как и в первых двух шагах, получаем ${ Displaystyle е ({ extf {Y}} f)}$ ${ displaystyle to}$ ${ Displaystyle е (( lambda x.f (xx)) ( lambda x.f (xx)))}$ .Поскольку оба условия ${ Displaystyle { extf {Y}} f}$ и ${ Displaystyle е ({ extf {Y}} f)}$ можно свести к одному и тому же сроку, они равны.
^ ${ displaystyle Theta f}$ ${ Displaystyle Equiv}$ ${ Displaystyle ( лямбда xy.y (xxy)) ( lambda xy.y (xxy)) f}$ ${ displaystyle to}$ ${ Displaystyle ( лямбда y.y (( lambda xy.y (xxy)) ( lambda xy.y (xxy)) y)) f}$ ${ displaystyle to}$ ${ Displaystyle е (( lambda xy.y (xxy)) ( lambda xy.y (xxy)) f)}$ ${ Displaystyle Equiv}$ ${ Displaystyle е ( Тета е)}$
^
Эта терминология в значительной степени фольклор, но он появляется в следующем:
- Трей Нэш, Ускоренный C # 2008, Апресс, 2007, г. ISBN 1-59059-873-3, п. 462–463. В значительной степени получено из Уэс Дайер блог пользователя (см. следующий пункт).
- Уэс Дайер Анонимная рекурсия в C #, 2 февраля 2007 г., содержит по существу аналогичный пример из вышеприведенной книги, но с дополнительным обсуждением.

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

[3] В этой статье правила синтаксиса, указанные в Лямбда-исчисление # Обозначение используются, чтобы сохранить круглые скобки.

[Y_demonstration-4] а ^б Для произвольного лямбда-члена ж, свойство фиксированной точки можно проверить, уменьшив бета-версию левой и правой части: ${ Displaystyle { extf {Y}} f}$ ${ Displaystyle Equiv}$ ${ displaystyle ( lambda f. ( lambda x.f (xx)) ( lambda x.f (xx))) f}$ ${ displaystyle to}$ ${ Displaystyle ( лямбда х.f (хх)) ( лямбда х.f (хх))}$ ${ displaystyle to}$ ${ Displaystyle е (( lambda x.f (xx)) ( lambda x.f (xx)))}$ ,куда ${ Displaystyle Equiv}$ и ${ displaystyle to}$ обозначают синтаксическое равенство по определению и бета-редукцию соответственно. Как и в первых двух шагах, получаем ${ Displaystyle е ({ extf {Y}} f)}$ ${ displaystyle to}$ ${ Displaystyle е (( lambda x.f (xx)) ( lambda x.f (xx)))}$ .Поскольку оба условия ${ Displaystyle { extf {Y}} f}$ и ${ Displaystyle е ({ extf {Y}} f)}$ можно свести к одному и тому же сроку, они равны.

[11] ${ displaystyle Theta f}$ ${ Displaystyle Equiv}$ ${ Displaystyle ( лямбда xy.y (xxy)) ( lambda xy.y (xxy)) f}$ ${ displaystyle to}$ ${ Displaystyle ( лямбда y.y (( lambda xy.y (xxy)) ( lambda xy.y (xxy)) y)) f}$ ${ displaystyle to}$ ${ Displaystyle е (( lambda xy.y (xxy)) ( lambda xy.y (xxy)) f)}$ ${ Displaystyle Equiv}$ ${ Displaystyle е ( Тета е)}$

[25] Эта терминология в значительной степени фольклор, но он появляется в следующем:
Трей Нэш, Ускоренный C # 2008, Апресс, 2007, г. ISBN 1-59059-873-3, п. 462–463. В значительной степени получено из Уэс Дайер блог пользователя (см. следующий пункт).
Уэс Дайер Анонимная рекурсия в C #, 2 февраля 2007 г., содержит по существу аналогичный пример из вышеприведенной книги, но с дополнительным обсуждением.

[5] Трей Нэш, Ускоренный C # 2008, Апресс, 2007, г. ISBN 1-59059-873-3, п. 462–463. В значительной степени получено из Уэс Дайер блог пользователя (см. следующий пункт).

[6] Уэс Дайер Анонимная рекурсия в C #, 2 февраля 2007 г., содержит по существу аналогичный пример из вышеприведенной книги, но с дополнительным обсуждением.

[SPJ1987-1] а ^б Пейтон Джонс, Саймон Л. (1987). Реализация функционального программирования. Prentice Hall International.

[Barendregt.1985-2] а ^б Хенк Барендрегт (1985). Лямбда-исчисление - его синтаксис и семантика. Исследования по логике и основам математики. 103. Амстердам: Северная Голландия. ISBN 0444867481.

[5] Селинджер, Питер. «Конспект лекций по лямбда-исчислению (PDF)». п. 6.

[6] «Для тех из нас, кто не знает, что такое Y-Combinator и почему он полезен, ...» Хакерские новости. Получено 2 августа 2020.

[7] "абстрактная алгебра - Может ли кто-нибудь объяснить Y-комбинатор?". Обмен стеками математики.

[bimbo-8] Бимбо, Каталин. Комбинаторная логика: чистая, прикладная и типизированная. п. 48.

[gold-9] а ^б Гольдберг, 2005 г.

[10] Алан Мэтисон Тьюринг (декабрь 1937 г.). "The ${ displaystyle p}$ -функция в ${ displaystyle lambda}$ - ${ displaystyle K}$ -конверсия ». Журнал символической логики. 2 (4): 164. JSTOR 2268281.

[12] «Многогранность комбинатора с фиксированной точкой». okmij.org.

[13] Поливариадический Y в чистом Haskell98 В архиве 2016-03-04 в Wayback Machine, lang.haskell.cafe, 28 октября 2003 г.

[14] "рекурсия - комбинатор с фиксированной точкой для взаимно рекурсивных функций?". Переполнение стека.

[15] Бене, Адам (17 августа 2017 г.). «Комбинаторы с фиксированной точкой в JavaScript». Бене Студия. Середина. Получено 2 августа 2020.

[16] "CS 6110 S17 Лекция 5. Рекурсия и комбинаторы с фиксированной точкой" (PDF). Корнелл Университет. 4.1 Комбинатор с фиксированной точкой CBV.

[17] Исходное определение в Data.Function.

[18] Фелляйзен, Маттиас (1987). Исчисление Lambda-v-CS. Университет Индианы.

[19] Талкотт, Кэролайн (1985). Сущность рома. Стэндфордский Университет.

[20] Введение в лямбда-исчисление В архиве 2014-04-08 в Wayback Machine

[21] Тема списка рассылки Haskell на Как определить комбинатор Y в Haskell, 15 сен 2006

[22] Геверс, Герман; Веркоелен, Йоп. О комбинаторах с фиксированной точкой и зацикливании в теории типов.

[23] Дэниел П. Фридман, Маттиас Фелляйзен (1986). «Глава 9 - Лямбда The Ultimate». Маленький Лиспер. Научно-исследовательские партнеры. п. 179. «В этой главе мы вывели Y-комбинатор, который позволяет нам писать рекурсивные функции с одним аргументом без использования define».

[24] Майк Ванье. «Комбинатор Y (небольшой возврат) или: как добиться успеха в рекурсии без рекурсии». Архивировано из оригинал на 22.08.2011. «В более общем смысле, Y дает нам способ получить рекурсию на языке программирования, который поддерживает первоклассные функции, но не имеет встроенной рекурсии».

[ifworks-26] Если работает Получение комбинатора Y, 10 января 2008 г.

[1]

[2]

[примечание 1]

[заметка 2]

[3]

[4]

[5]

[6]

[7]

[8]

[заметка 3]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[примечание 4]

[22]

Комбинатор с фиксированной точкой - Fixed-point combinator

Содержание

Y комбинатор