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  on funktsiooni  püsipunkt siis ja ainult siis, kui . 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 ), mis arvutab iga etteantud funktsiooni mõne püsipunkti:  on niisugune funktsioon, et kõikide funktsioonide  korral .  

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

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  tähendab funktsiooni, millel on üks argument x, mille all mõeldakse funktsiooni, ning tulemuseks on avaldis , kusjuures  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  on tõesti funktsiooni g püsipunkt:
{| cellpadding="0"
|
|
| definitsiooni järgi
|-
|
|
|β-reduktsioon: asendatakse Y formaalne argument f tegeliku argumendiga g
|-
|
|
|β-reduktsioon: asendatakse esimese funktsiooni formaalne argument x tegeliku argumendiga 
|-
|
|
|teise võrdsuse järgi, üleval
|}
Lambda term  ei pruugi üldiselt β-redutseeruda termiks . 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:Y <- \(f) {
  g <- \(x) f(x(x))
  g(g)
}Seda saab kasutada selleks, et implementeerida faktoriaal:fact <- \(f) \(n)
  if (n == 0) 1 else n * f(n - 1)

Y(fact)(5) # annab 5! = 120Y on vajalik vaid siis, kui funktsioonidel pole nimesid. Kui kõik definitsioonid asendada ja ühele reale panna, nii et funktsioonide nimesid pole vaja:(\(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 

Kategooria:Loogika
Kategooria:Programmeerimine