Vlákno názorů k článku Jazyk Joy a rekurzivní kombinátory od Tom - Pisete "... některé formy rekurze lze nahradit lineárním...

Pisete "... některé formy rekurze lze nahradit lineárním kódem poměrně snadno, u dalších je to již těžší a ve speciálních případech (matematici by spíše řekli v obecných případech) je to dokonce nemožné.", co ale (pokial sa memymlim) nie je pravda.

Totiz kombinator pevneho bodu (Y) sa da vyjadrit takto:

DEFINE
y == [dup cons [cons] cons [dup] dip dip i] dup cons [cons] cons [dup] dip dip i
.

a pomocou neho sa daju vyjadrit vsetky typy rekurzie. Na zasobniku ocakava citovany program, ktory je napisany tak, ze predpoklada sam seba na vrchu zasobnika. Kombinator Y ho upravi tak aby sam seba pridal na zasobnik a spustil sa. Teda [program] y je to iste ako [[program] y] program

Napriklad funkcia pocitajuca fibonacciho cisla sa pomocou neho da zapisat takto:

DEFINE
fib == [swap [0 =] [pop pop 0] [[1 =] [pop pop 1] [pred swap [dup pred] dip dup [swap] dip i [i] dip +] ifte] ifte] y
.

Tymto zaroven odpovedam tomasovi z, ze linrec nie je kombinator pevneho bodu

Pravda, timto zpusobem se da rekurze opravdu rozepsat, diky za pekny priklad. Neco podobneho jsem videl v nejakem postu, kde autor nahrazoval lambda vyrazy Joyovskymi konstrukcemi (vystacil si, pokud si dobre pamatuji dokonce pouze se swap, dup, pop a dip). Ale ten zpusob konkatenace programu pomoci cons je opravdu pekny.

jeste mozna dodam pro Lispare a Schemare, jak by to mohlo vypadat v jejich oblibenem jazyku:

(lambda (f) 
    (lambda (x) (f (x x))) 
        (lambda (x) (f (x x)))
    )
)

Hezké, díky za ukázky.

Nemyslel jsem ale, že by linrec byl přímo Y, spíše (logicky, ne nutně implementačně) složení funkce generující vhodný parametr pro Y z parametrů linrec a Y samotného. To mi funkčně přijde pořád docela možné.

Otázka mířila tam, kam vaše reakce - že tvrdit, že explicitní rekurze je v jiných jazycích obecně nezbytná, je odvážné.