Fixed point kombinator

Fixed point combinator (eller fixpunktsoperator ) är en högre ordningsfunktion som beräknar fixpunkten för en annan funktion.

Den mest kända fixpunktskombinatorn är Y-kombinatorn i λ-kalkyl , introducerad av den berömda amerikanske vetenskapsmannen Haskell Curry som

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

Ibland används namnet på denna kombinator felaktigt för att referera till alla fastpunktskombinatorer i allmänhet.

Programmeringsspråk som tillåter fixpunktskombinatorn tillåter att anonyma funktioner återkommer utan att tilldela värdet av en sådan funktion till en variabel.

Fixpunktssats

I både λ-kalkyl och kombinatorisk logik finns det för varje term minst en term så att . Dessutom finns det en sådan kombinator $X$ $P$ $XP=P$ $Y$ $YX=X(YX)$

Se även

Litteratur

Wolfenhagen VE Kombinatorisk logik i programmering. Beräkningar med objekt i exempel och problem. — M.: MEPhI, 1994. — 204 s.; 2:a upplagan, M .: JSC Center YurInfoR, 2003. - 336 sid. ISBN 5-89158-101-9 .
Mayer Goldberg, (2005) On the Rekursive Enumerability of Fixed-Point Combinators , BRICS Report RS-05-1, University of Aarhus
Matthias Felleisen . En föreläsning om varför Y Arkiverad 29 september 2007 på Wayback Machine .