Combinator de punct fix

Combinatorul de punct fix (sau operator de punct fix ) este o funcție de ordin superior care calculează punctul fix al altei funcții.

Cel mai faimos combinator în virgulă fixă este combinatorul Y în calculul λ , introdus de celebrul om de știință american Haskell Curry ca

Y=\lambda f.(\lambda xf(xx))(\lambda xf(xx)).

Uneori, numele acestui combinator este folosit în mod eronat pentru a se referi la toți combinatorii în virgulă fixă în general.

Limbajele de programare care permit combinatorul în virgulă fixă permit ca funcțiile anonime să fie recursate fără a atribui valoarea unei astfel de funcții unei variabile.

Teorema punctului fix

Atât în λ-calcul cât și în logica combinatorie, pentru fiecare termen există cel puțin un termen astfel încât . Mai mult, există un combinator astfel încât $X$ $P$ $XP=P$ $Y$ $YX=X(YX)$

Vezi și

Literatură

Wolfenhagen VE Logica combinatorie în programare. Calcule cu obiecte în exemple și probleme. — M.: MEPhI, 1994. — 204 p.; Ed. a II-a, M .: JSC Center YurInfoR, 2003. - 336 p. 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 Arhivat 29 septembrie 2007 la Wayback Machine .