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

Функция высшего порядка Y, для которой Y f = f (Y f)

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

Формально, если — комбинатор с фиксированной точкой и функция имеет одну или несколько фиксированных точек, то — одна из этих фиксированных точек, т.е. ${\displaystyle {\textrm {fix}}}$ ${\displaystyle f}$ ${\displaystyle {\textrm {fix}}\ f}$

${\displaystyle f\ ({\textrm {fix}}\ f)={\textrm {fix}}\ f\ .}$

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

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

В классическом нетипизированном лямбда-исчислении каждая функция имеет фиксированную точку. Конкретной реализацией является парадоксальный комбинатор Y Хаскеля Карри , заданный как ^{[2] : 131  [примечание 1] [примечание 2]} ${\displaystyle {\textrm {fix}}}$

${\displaystyle Y=\lambda f.\ (\lambda x.f\ (x\ x))\ (\lambda x.f\ (x\ x))}$

(Здесь мы используем стандартные обозначения и соглашения лямбда-исчисления: Y — это функция, которая принимает один аргумент f и возвращает все выражение, следующее за первой точкой; выражение обозначает функцию, которая принимает один аргумент x , рассматриваемую как функция, и возвращает выражение , где обозначает x, примененное к себе. Сопоставление выражений обозначает применение функции, является левоассоциативным и имеет более высокий приоритет, чем точка.) ${\displaystyle \lambda x.f\ (x\ x)}$ ${\displaystyle f\ (x\ x)}$ ${\displaystyle (x\ x)}$

Проверка

Следующий расчет подтверждает, что это действительно неподвижная точка функции : ${\displaystyle Yg}$ ${\displaystyle g}$

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

Использует

Примененный к функции с одной переменной, комбинатор Y обычно не завершается. Более интересные результаты получаются при применении комбинатора Y к функциям двух или более переменных. Дополнительные переменные могут использоваться как счетчик или индекс. Полученная функция ведет себя как цикл while или for в императивном языке.

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

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

Примеры реализации

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

# Y-комбинатор в PythonY  =  лямбда  f :  ( лямбда  x :  f ( x ( x )))( лямбда  x :  f ( x ( x )))Д ( Д )

// Y Combinator в C++, с использованием расширений C++ 14инт мейн () {   авто Y = []( авто f ) {      авто f1 = [ f ]( авто x ) -> decltype ( f ) {        вернуть f ( x ( x ));  }; вернуть f1 ( f1 );  }; Д ( Д );}

Обратите внимание, что обе эти программы, хотя формально и правильны, на практике бесполезны; обе они бесконечно зацикливаются, пока не завершатся из-за переполнения стека . В более общем смысле, поскольку и Python, и C++ используют строгую оценку , комбинатор Y в этих языках, как правило, бесполезен; см. ниже комбинатор Z, который можно использовать в строгих языках программирования .

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

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

• Общая математика
• Нетипизированное лямбда-исчисление
• Типизированное лямбда-исчисление
• Функциональное программирование
• Императивное программирование

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

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

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

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

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

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

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

Многие функции не имеют фиксированных точек, например , с . Используя кодировку Чёрча , натуральные числа могут быть представлены в лямбда-исчислении, и эта функция f может быть определена в лямбда-исчислении. Однако теперь ее область определения будет содержать все лямбда-выражения, а не только те, которые представляют натуральные числа. Комбинатор Y, примененный к f , даст фиксированную точку для f , но эта фиксированная точка не будет представлять натуральное число. Если попытаться вычислить Y f на реальном языке программирования, возникнет бесконечный цикл. ${\displaystyle f:\mathbb {N} \to \mathbb {N} }$ ${\displaystyle f(n)=n+1}$

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

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

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

Определение термина «комбинатор»

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

Рекурсивные определения и комбинаторы с фиксированной точкой

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

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

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

${\displaystyle \operatorname {fact} \ n={\begin{cases}1&{\text{if}}~n=0\\n\times \operatorname {fact} (n-1)&{\text{otherwise.}}\end{cases}}}$

где n — неотрицательное целое число. Если мы хотим реализовать это в лямбда-исчислении, где целые числа представлены с использованием кодировки Чёрча , мы сталкиваемся с проблемой, что лямбда-исчисление не позволяет использовать имя функции («факт») в определении функции. Это можно обойти с помощью комбинатора с фиксированной точкой следующим образом. ${\displaystyle {\textsf {fix}}}$

Определим функцию F двух аргументов f и n :

${\displaystyle F\ f\ n=(\operatorname {IsZero} \ n)\ 1\ (\operatorname {multiply} \ n\ (f\ (\operatorname {pred} \ n)))}$

(Вот функция, которая принимает два аргумента и возвращает свой первый аргумент, если n = 0, и свой второй аргумент в противном случае; результатом ее вычисления является n -1.) ${\displaystyle (\operatorname {IsZero} \ n)}$ ${\displaystyle \operatorname {pred} \ n}$

Теперь определим . Тогда — неподвижная точка F , что дает ${\displaystyle \operatorname {fact} ={\textsf {fix}}\ F}$ ${\displaystyle \operatorname {fact} }$

${\displaystyle {\begin{aligned}\operatorname {fact} n&=F\ \operatorname {fact} \ n\\&=(\operatorname {IsZero} \ n)\ 1\ (\operatorname {multiply} \ n\ (\operatorname {fact} \ (\operatorname {pred} \ n)))\ \end{aligned}}}$

по желанию.

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

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

${\displaystyle Y=\lambda f.(\lambda x.f\ (x\ x))\ (\lambda x.f\ (x\ x))}$

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

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

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

${\displaystyle Y=S(K(SII))(S(S(KS)K)(K(SII)))}$

Дополнительные комбинаторы ( система B, C, K, W ) позволяют получить гораздо более короткое определение. С самоприменяемым комбинатором, поскольку и , вышесказанное становится ${\displaystyle U=SII}$ ${\displaystyle S(Kx)yz=x(yz)=Bxyz}$ ${\displaystyle Sx(Ky)z=xzy=Cxyz}$

${\displaystyle Y=S(KU)(SB(KU))=BU(CBU)}$

Простейший комбинатор с фиксированной точкой в ​​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))}$

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

${\displaystyle \Theta =(\lambda xy.y(xxy))\ (\lambda xy.y(xxy))}$

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

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

${\displaystyle \Theta _{v}=(\lambda xy.y(\lambda z.xxyz))\ (\lambda xy.y(\lambda z.xxyz))}$

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

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

В строгом языке программирования комбинатор Y будет расширяться до переполнения стека или никогда не останавливаться в случае оптимизации хвостового вызова . ^[11] Комбинатор Z будет работать в строгих языках (также называемых жадными языками, где применяется аппликативный порядок оценки). У комбинатора Z следующий аргумент определен явно, предотвращая расширение в правой части определения: ^[12] ${\displaystyle Zg}$

${\displaystyle Zgv=g(Zg)v\ .}$

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

${\displaystyle Z=\lambda f.(\lambda x.f(\lambda v.xxv))\ (\lambda x.f(\lambda v.xxv))\ .}$

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

Если F — комбинатор с фиксированной точкой в ​​нетипизированном лямбда-исчислении, то мы имеем

${\displaystyle F=\lambda x.Fx=\lambda x.x(Fx)=\lambda x.x(x(Fx))=\cdots }$

Термины, которые имеют то же дерево Бёма , что и комбинатор с фиксированной точкой, т.е. имеют то же бесконечное расширение , называются нестандартными комбинаторами с фиксированной точкой . Любой комбинатор с фиксированной точкой также является нестандартным, но не все нестандартные комбинаторы с фиксированной точкой являются комбинаторами с фиксированной точкой, потому что некоторые из них не удовлетворяют уравнению с фиксированной точкой, которое определяет «стандартные». Такие комбинаторы называются строго нестандартными комбинаторами с фиксированной точкой ; примером является следующий комбинатор: ${\displaystyle \lambda x.x(x(x\cdots ))}$

${\displaystyle N=BM(B(BM)B)}$

где

${\displaystyle B=\lambda xyz.x(yz)}$

${\displaystyle M=\lambda x.xx\ .}$

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

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

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

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

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

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

fix , fix' :: ( a -> a ) -> a fix f = let x = f x in x -- Лямбда удалена. Совместное использование. -- Исходное определение в Data.Function. -- альтернатива: fix' f = f ( fix' f ) -- Лямбда удалена. Несовместное использование.                        исправить ( \ x -> 9 ) — это вычисляется как 9    fix ( \ x -> 3 : x ) — возвращает ленивый бесконечный список [3,3,3,...]    fact = fix fac — вычисляется как факториальная функция , где fac f 0 = 1 fac f x = x * f ( x - 1 )                  факт 5 -- оценивается как 120  

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

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

${\displaystyle f\ (f...(f\ ({\mathsf {fix}}\ f))...)\ x}$.

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

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

В многопарадигмальном функциональном языке (украшенном императивными функциями), таком как Lisp , Питер Ландин предложил использовать присваивание переменной для создания комбинатора с фиксированной точкой ^[14] , как в следующем примере с использованием Scheme :

( define Y! ( lambda ( f ) (( lambda ( i ) ( set! i ( f ( lambda ( x ) ( i x )))) ;; (set! i expr) присваивает i значение expr i ) ;; заменяя его в текущей лексической области #f )))                 

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

${\displaystyle (Y_{!}\ \lambda x.e)e'=(\lambda x.e)\ (Y_{!}\ \lambda x.e)e'}$

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

( define Y* ( lambda ( f ) (( lambda ( i ) ( let (( i ( f ( lambda ( x ) ( i x ))))) ;; (let ((i expr)) i) локально определяет i как expr i )) ;; нерекурсивно: таким образом, i в expr не является expr #f )))                

Или без внутренней этикетки:

( определить Y ( лямбда ( f ) (( лямбда ( i ) ( i i )) ( лямбда ( i ) ( f ( лямбда ( x ) ( применить ( i i ) x )))))))                

Императивная реализация языка

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

шаблон < имя_типа R , имя_типа D > class fixer { public : R fix ( D x ) { return f ( x ); } private : virtual R f ( D ) = 0 ; };                 факт класса : публичный фиксер < long , long > { virtual long f ( long x ) { if ( x == 0 ) { return 1 ; } return x * fix ( x -1 ); } };                       длинный результат = факт (). исправить ( 5 );   

Печатание

В системе F (полиморфное лямбда-исчисление) полиморфный комбинатор с фиксированной точкой имеет тип ^[17]

∀а.(а → а) → а

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

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

В простом типизированном лямбда-исчислении комбинатору с фиксированной точкой Y не может быть назначен тип ^[18] , поскольку в какой-то момент он будет иметь дело с подтермом самоприменения по правилу применения: ${\displaystyle x~x}$

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

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

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

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

Например, в следующем коде Haskell мы имеем Inи out— имена двух направлений изоморфизма с типами: ^{[19] [20]}

Вход :: ( Рецепт а -> а ) -> Рецепт а выход :: Рецепт а -> ( Рецепт а -> а )                

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

новыйтип Rec a = In { out :: Rec a -> a }            y :: ( a -> a ) -> a y = \ f -> ( \ x -> f ( out x x )) ( In ( \ x -> f ( out x x )))                      

Или эквивалентно в OCaml:

тип  ' a  recc  =  In  of  ( ' a  recc  -  > ' a ) выпустить  ( In x ) =  x   пусть  y  f  =  ( fun  x  a  ->  f  ( out  x  x )  a )  ( In  ( fun  x  a  ->  f  ( out  x  x )  a ))

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

пусть  y  f  =  ( fun  x  ->  f  ( fun  z  ->  out  x  x  z ))  ( In  ( fun  x  ->  f  ( fun  z  ->  out  x  x  z )))

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

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

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

${\displaystyle \forall x(f\ x=x)}$

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

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

${\displaystyle \forall x(f\ (f\ x)=f\ x)}$

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

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

${\displaystyle (Y\ \lambda x.x)=(\lambda x.(xx)\ \lambda x.(xx))}$

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

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

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

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

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

• Анонимная функция
• Итерация с фиксированной точкой
• Лямбда-исчисление#Рекурсия и неподвижные точки
• Лямбда-подъем
• Пусть выражение

Примечания

1. В этой статье для экономии скобок используются правила синтаксиса, приведенные в разделе Лямбда-исчисление#Нотация .
2. Согласно Барендрегту на стр. 132, название произошло от слова «карри».
3. ${\displaystyle \Theta \ f}$ ${\displaystyle \equiv }$ ${\displaystyle (\lambda xy.y(xxy))\ (\lambda xy.y(xxy))\ f}$ ${\displaystyle \to }$ ${\displaystyle (\lambda y.y\ ((\lambda xy.y(xxy))\ (\lambda xy.y(xxy))\ y))\ f}$ ${\displaystyle \to }$ ${\displaystyle f\ ((\lambda xy.y(xxy))\ (\lambda xy.y(xxy))\ f)}$ ${\displaystyle \equiv }$ ${\displaystyle f\ (\Theta \ f)}$
4. Эта терминология, по-видимому, в значительной степени фольклорная , но она встречается в следующих текстах:
   • Trey Nash, Accelerated C# 2008 , Apress, 2007, ISBN  1-59059-873-3 , стр. 462—463. В значительной степени взято из блога Уэса Дайера (см. следующий пункт).
   • В книге Уэса Дайера «Анонимная рекурсия в C#» от 2 февраля 2007 г. содержится по сути аналогичный пример, найденный в приведенной выше книге, но с более подробным обсуждением.

Ссылки

1. Пейтон Джонс, Саймон Л. (1987). Реализация функционального программирования (PDF) . Prentice Hall International.
2. Хенк Барендрегт (1985). Лямбда-исчисление – его синтаксис и семантика . Исследования по логике и основаниям математики. Том 103. Амстердам: Северная Голландия. ISBN 0444867481.
3. Селинджер, Питер. «Конспект лекций по лямбда-исчислению (PDF)». стр. 6.
4. "Для тех из нас, кто не знает, что такое Y-Combinator или чем он полезен, ..." Hacker News . Получено 2 августа 2020 г.
5. Bimbó, Katalin (27 июля 2011 г.). Комбинаторная логика: чистая, прикладная и типизированная. CRC Press. стр. 48. ISBN 9781439800010.
6. Goldberg, 2005
7. Алан Матисон Тьюринг (декабрь 1937 г.). « -функция в - -преобразовании». Журнал символической логики . 2 (4): 164. JSTOR  2268281. ${\displaystyle p}$ ${\displaystyle \lambda }$ ${\displaystyle K}$
8. "Многогранность комбинатора с фиксированной точкой". okmij.org .
9. Поливариантный Y в чистом Haskell98 Архивировано 2016-03-04 на Wayback Machine , lang.haskell.cafe, 28 октября 2003 г.
10. "рекурсия - Комбинатор с фиксированной точкой для взаимно рекурсивных функций?". Stack Overflow .
11. Bene, Adam (17 августа 2017 г.). «Комбинаторы с фиксированной точкой в ​​JavaScript». Bene Studio . Medium . Получено 2 августа 2020 г. .
12. "CS 6110 S17 Лекция 5. Рекурсия и комбинаторы с фиксированной точкой" (PDF) . Корнелльский университет . 4.1 Комбинатор с фиксированной точкой CBV.
13. Исходное определение в Data.Function.
14. Ландин, П.Дж. (январь 1964 г.). «Механическая оценка выражений». Компьютерный журнал . 6 (4): 308–320. дои : 10.1093/comjnl/6.4.308.
15. Феллизен, Матиас (1987). Лямбда-v-CS-исчисление. Университет Индианы.
16. Талкотт, Кэролин (1985). Сущность рома: теория интенсиональных и экстенсиональных аспектов вычислений типа Лисп (диссертация на соискание степени доктора философии). Стэнфордский университет.
17. Жирар, Жан-Ив (1986). «Система F переменных типов, пятнадцать лет спустя». Теоретическая информатика . 45 (2): 159–192. doi :10.1016/0304-3975(86)90044-7. MR  0867281.См. в частности стр. 180.
18. Введение в лямбда-исчисление Архивировано 2014-04-08 на Wayback Machine
19. Тема почтовой рассылки Haskell о том, как определить комбинатор Y в Haskell, 15 сентября 2006 г.
20. Геверс, Герман; Веркелен, Джоп. О фиксированной точке и циклических комбинаторах в теории типов . CiteSeerX 10.1.1.158.1478 . 
21. Дэниел П. Фридман , Маттиас Феллейзен (1986). "Глава 9 - Лямбда The Ultimate". Маленький Шепелявый . Science Research Associates . стр. 179.«В этой главе мы вывели Y-комбинатор, который позволяет нам записывать рекурсивные функции одного аргумента без использования define».
22. Майк Ванье. "Y Combinator (Slight Return) или: Как преуспеть в рекурсии, не прибегая к настоящей рекурсии". Архивировано из оригинала 22.08.2011.«В более общем плане Y дает нам способ реализовать рекурсию в языке программирования, который поддерживает функции первого класса, но не имеет встроенной рекурсии».
23. If Works Deriving the Y combinator, 10 января 2008 г.

• Вернер Клюге, Абстрактные вычислительные машины: перспектива лямбда-исчисления , Springer, 2005, ISBN 3-540-21146-2 , стр. 73–77 
• Майер Голдберг, (2005) О рекурсивной перечислимости комбинаторов с фиксированной точкой , Отчет BRICS RS-05-1, Университет Орхуса
• Маттиас Феллейзен , Лекция о причинах возникновения Y.

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

• Теория рекурсии и радость, Манфред фон Тун, (2002 или ранее)
• Лямбда-исчисление - заметки Дона Блаэты, 12 октября 2000 г.
• Y Combinator Архивировано 23.03.2009 на Wayback Machine
• «Использование Y-комбинатора в Ruby»
• «Функциональное программирование на языке Ada»
• Код Rosetta - Y-комбинатор