Комбинатор неподвижной точки

Запрос «Y-комбинатор» перенаправляется сюда; о венчурном фонде см. Y Combinator.

Комбина́тор неподви́жной то́чки (или оператор неподвижной точки) — это комбинатор, нерекурсивная функция высшего порядка ${\displaystyle Fix}$, создающая неподвижную точку другой функции высшего порядка ${\displaystyle G}$, так что

${\displaystyle Fix(G)=G\,(Fix(G))=G\,(G\,(Fix(G)))=G\,(G\,(G\,(\ldots )))}$

Наиболее известным комбинатором неподвижной точки является Y-комбинатор в λ-исчислении, введённый известным американским учёным Хаскеллом Карри как

${\displaystyle {\begin{aligned}Y&\equiv \lambda f.(\lambda x.xx)\ (\lambda x.f(xx))\\&=\lambda f.(\lambda x.f(xx))\ (\lambda x.f(xx))\\&=\lambda f.f((\lambda x.f(xx))\ (\lambda x.f(xx)))\end{aligned}}}$

Иногда имя этого комбинатора ошибочно используется для обозначения вообще всех комбинаторов неподвижной точки.

Существует бесконечно много комбинаторов неподвижной точки, например^[1]

${\displaystyle {\begin{aligned}\Theta \ \equiv \ &(\lambda xf.xxf)\ (\lambda xf.f(xxf))\\Y{\text{′}}\equiv \ &(\lambda xf.xfx)\ (\lambda fx.f(xfx))\\\Theta _{4}\equiv \ &\lambda f.(\lambda x.xxx)\ (\lambda xy.f(xxx))\\Y_{K}\equiv \ &(\lambda x.xxxxxxxxxxxxxxxxxxxxxxxxxx)\\\ &(\lambda abcdefghijklmnopqstuvwxyzr.r(thisisafixedpointcombinator))\end{aligned}}}$

и т.д. (здесь ${\displaystyle \Theta }$ - это комбинатор Тьюринга).

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

${\displaystyle G\triangleq \lambda \,r\,n.{\text{if }}\mathrm {base\_case} (n)\ \rightarrow \ n{\text{′}}\ {\text{else }}r\,n{\text{′}}{\text{′}}}$

где ${\displaystyle r}$ обозначает "остаток вычислений", ${\displaystyle Y\,G}$ это соответствующая рекурсивная функция

${\displaystyle Y\,G\,n=G\,(Y\,G)\,n}$

где вызов ${\displaystyle r}$ будет происходить в зависимости от значения ${\displaystyle n}$. Но ${\displaystyle r}$ получает как значение ${\displaystyle Y\,G=G\,(Y\,G)}$, и таким образом базисный вычислительный шаг ${\displaystyle G}$ будет повторяться снова и снова, по мере необходимости, без ограничений, как определено значением аргумента:

${\displaystyle r\,n{\text{′}}{\text{′}}=Y\,G\,n{\text{′}}{\text{′}}=G\,(Y\,G)\,n{\text{′}}{\text{′}}}$

Теорема о неподвижной точке

И в λ-исчислении, и в комбинаторной логике для каждого терма ${\displaystyle X}$ существует по крайней мере один терм ${\displaystyle P}$ такой, что ${\displaystyle P=XP}$. И более того, существует комбинатор ${\displaystyle Y}$ такой, что ${\displaystyle YX=X(YX)}$.

См. также

• Комбинаторная логика
• Лямбда-исчисление
• Функциональное программирование