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

Комбина́тор неподви́жной то́чки (также, ошибочно, иногда встречаются термины оператор неподвижной точки, комбинатор фиксированной точки и Y-комбинатор) — функция высшего порядка, (все комбинаторы являются функциями высшего порядка) вычисляющая неподвижную точку другой функции.

Наиболее известным комбинатором неподвижной точки является Y-комбинатор в λ-исчислении, введённый известным американским ученым Хаскеллом Карри как
$~Y=\lambda f.(\lambda x. f(x x))\;(\lambda x. f(x x))$. Иногда имя этого комбинатора ошибочно используется для обозначения вообще всех комбинаторов неподвижной точки.

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

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

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

Литература

• Вольфенгаген В. Э. Комбинаторная логика в программировании. Вычисления с объектами в примерах и задачах. — М.: МИФИ, 1994. — 204 с.; 2-е изд., М.: АО «Центр ЮрИнфоР», 2003. — 336 с. ISBN 5-89158-101-9.
• Mayer Goldberg, (2005) On the Recursive Enumerability of Fixed-Point Combinators, BRICS Report RS-05-1, University of Aarhus
• Matthias Felleisen. A Lecture on the Why of Y.

См. также

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