Püsipunktikombinaator

**Püsipunktikombinaator** (inglise keeles *fixed point combinator*) on funktsioon, mis arvutab teiste funktsioonide püsipunkte. See on kõrgemat järku funktsioon, mille parameetriks on funktsioon. 

Funktsiooni püsipunkt on argumendi väärtus, mille see funktsioon samaks jätab ehk mille puhul funktsiooni väärtus võrdub argumendi väärtusega: väärtus x on funktsiooni f püsipunkt siis ja ainult siis, kui f(x) = x. Näiteks 0 ja 1 on ruutfunktsiooni püsipunktid.  

Lambda-arvutuses ja kombinatoorses loogikas on igal funktsioonil mõni püsipunkt. Seal on võimalik genereerida funktsioon (tähis sageli \boldsymbol{Y}), mis arvutab iga etteantud funktsiooni mõne püsipunkti: \boldsymbol{Y} on niisugune funktsioon, et kõikide funktsioonide f korral f(\boldsymbol{Y}(f)) = \boldsymbol{Y}(f).  

Püsipunktikombinaatoreid on võimalik defineerida lambda-arvutuses ja funktsionaalsetes programmeerimiskeeltes. Nende abil on võimalik koostada rekursiivseid definitsioone.  

## ''Y''-kombinaator lambda-arvutuses
Klassikalises tüüpimata lambda-arvutuses on igal funktsioonil püsipunkt. Üks implementatsioon püsipunktikombinaatorist on Haskell Curry paradoksaalne *Y*-kombinaator, mille annab

:Y = \lambda f. \ (\lambda x.f\ (x\ x))\ (\lambda x.f\ (x\ x))
Siin on kasutusel lambda-arvutuse standardne kirjapilt ja konventsioonid: *Y* on funktsioon, mis võtab ühe argumendi *f* ja selle funktsiooni tulemuseks on kogu avaldis, mis on kirjas pärast esimest punkti. Avaldis \lambda x. f\ (x\ x) tähendab funktsiooni, millel on üks argument *x*, mille all mõeldakse funktsiooni, ning tulemuseks on avaldis f\ (x\ x), kusjuures (x\ x) tähendab funktsiooni *x* rakendumist iseendale. Avaldiste kõrvuti paiknemine tähendab funktsiooni aplikatsiooni, on assotsiatiivne vasakule, ning tehete järjekorra järgi rakendub see enne punkti.

### Kinnitamine
Järgnev arvutus kinnitab, et Y g on tõesti funktsiooni *g* püsipunkt:
:
Lambda term g\ (Y\ g) ei pruugi üldiselt β-redutseeruda termiks Y\ g. Siiski β-redutseerub kumbki term samaks termiks, nagu näidatud.

### Kasutamine
Kui seda rakendada funktsioonile, millel on vaid üks argument, siis *Y*-kombinaator üldjuhul ei peatu. Huvitavamad on tulemused siis, kui rakendada *Y*-kombinaatorit funktsioonidele, millel on kaks või rohkem argumenti. Neid lisatud argumente võib kasutada loenduri või indeksina. Tulemuseks on funktsioon, mis käitub nagu *for-* või *while-*tsükkel imperatiivsetes programmeerimiskeeltes.

Sellisel moel võimaldab *Y*-kombinaator lihtsat rekursiooni. Erinevalt paljudest programmeerimiskeeltest, ei luba lambda-arvutus funktsioonil termina ilmuda omaenda definitsioonis, aga funktsiooni võib edasi anda kõrgemat järku funktsioonile, mis võimaldab selle aplikatsiooni rekursiivselt.

*Y*-kombinaator lubab ette näidata ka Curry paradoksi. Sarnaselt Gödeli arvudele annab *Y*-kombinaator funktsioonidele võime "rääkida iseendast". Lisades tüüpimata lambda-arvutusele loogikatehted, on võimalik tõestada mida iganes, mis näitab, et tüüpimata lambda-arvutus on loogikasüsteemina mittetäielik.

### Näide
Järgnev on näide *Y* implementatsioonist R programmeerimiskeeles:
```r
Y <- \(f) {
  g <- \(x) f(x(x))
  g(g)
}
```
Seda saab kasutada selleks, et implementeerida faktoriaal:
```r
fact <- \(f) \(n)
  if (n == 0) 1 else n * f(n - 1)
  
Y(fact)(5) # annab 5! = 120
```
*Y* on vajalik vaid siis, kui funktsioonidel pole nimesid. Kui kõik definitsioonid asendada ja ühele reale panna, nii et funktsioonide nimesid pole vaja:
```r
(\(f) (\(x) f(x(x)))(\(x) f(x(x)))) (\(f) \(n) if (n == 0) 1 else n * f(n - 1)) (5)
```
See funktsioon toimib seetõttu, et R toetab laiska väärtustamist.

Keeled, mis kasutavad ranget väärtustamist, näiteks Python, C++ ja teised sarnased keeled, suudavad *Y*-t väljendada, aga selline implementatsioon oleks kasutu, sest see looks lõputu tsükli kuni pinu ületäitumiseni.

## Vaata ka
* kombinatoorne loogika

## Viited