Pravda zostane vždy pravdou.

Ľudia majú radi pekné veci – filmy, knihy, hudbu. Ja mám rád pekné nápady, myšlienky. Dnes vám chcem ukázať jeden z najkrajších myšlienok v informatike: Y-kombinátor. Je ako dokonalý skok v krasokorčuľovaní: zdanlivo nemožný, ale keď ho pochopíte, oceníte jeho veľkú eleganciu.

Predstavte si, že máte napísať návod na výrobu chleba, ale v celom návode nesmiete použiť slovo „chlieb“. Ako opíšete, že výsledkom je práve chlieb? V programovaní existuje podobný problém: ako vytvoriť funkciu, ktorá volá samu seba, keď nemôže použiť svoje vlastné meno?

Tu prichádza na scénu Y-kombinátor – „rekurzívne zrkadlo“. Umožňuje funkcii vidieť svoj vlastný odraz v zrkadle a interagovať s ním, bez toho aby poznala svoju identitu.

Prečo by nás to malo zaujímať?

Je to intelektuálne fascinujúce: ako môže niečo volať samé seba, bez toho aby vedelo, že je to ono?

Ukazuje krásu logiky v informatike

Je základom moderných funkcionálnych programovacích jazykov

Pripomína nám, že niekedy sa musíme na problém pozrieť „z inej strany“

Jednoduchá analógia:
Funkcia, ktorá hľadá cestu z bludiska, potrebuje vedieť, čo robiť v slepej uličke: „vráť sa späť a skús inú cestu“. Ale čo znamená „vráť sa späť“? Znamená to zavolať opäť tú istú funkciu hľadania cesty. Y-kombinátor je kúzlo, ktoré tejto funkcii umožní povedať „urob to, čo robím ja“ bez toho, aby o sebe vedela, že je to „funkcia hľadania cesty z bludiska“.

V praxi Y-kombinátor umožňuje vytvoriť rekurzívne funkcie (ako výpočet faktoriálu) v prostrediach, kde funkcie nemôžu odkazovať samé na seba.

Tento koncept, pochádzajúci z lambda kalkulu z 30. rokov 20. storočia, je dôkazom, že najhlbšie myšlienky sú často tie najjednoduchšie – aspoň v princípe. Je to ako matematická haiku: minimom prostriedkov, maximálny efekt.

Pre zvedavcov: Ako to skutočne funguje?

Ak ste technicky založení alebo len zvedaví, nasleduje podrobné vysvetlenie. Nebojte sa kódu – je to len spôsob, ako zapísať túto krásnu myšlienku.

Ak vás táto myšlienka zaujala a chcete vidieť, ako sa používa v praxi, pripravil som podrobný rozbor, ktorý je dostupný online pre technicky zameraných čitateľov.

Tu je podrobné vysvetlenie, ktoré vyzerá veľmi zložito. Ale v skutočnosti to je jednoduchá a nádherná myšlienka. Jedna z tých najkrajších, ktorá existuje v jazykoch.:

(defparameter Y
(lambda (f)
(funcall
(lambda (x) (funcall f (lambda (v) (funcall (funcall x x) v))))
(lambda (x) (funcall f (lambda (v) (funcall (funcall x x) v))))))

(defun Y (f)
((lambda (x) (funcall f (lambda (v) (funcall (funcall x x) v))))
(lambda (x) (funcall f (lambda (v) (funcall (funcall x x) v))))))

((defun Y (f) (alfa alfa)) => (f (lambda (v) (funcall (funcall x x) v))) ; argument self

(setf fakt (Y #’faktorial-gen)) – vytvoríme faktorial

(Y faktorial-gen) => (funcall faktorial-gen (lambda (v) (funcall (funcall alfa alfa) v)))

kde alfa = (lambda (x) (funcall faktorial-gen (lambda (v) (funcall (x x) v))))

(Y faktorial-gen) =

((lambda (x) (funcall faktorial-gen (lambda (v) (funcall (funcall x x) v))))
(lambda (x) (funcall faktorial-gen (lambda (v) (funcall (funcall x x) v)))))

ROZVINUTIE:

((lambda (x) (funcall faktorial-gen (lambda (v) (funcall (funcall x x) v))))
(lambda (x) (funcall faktorial-gen (lambda (v) (funcall (funcall x x) v)))))
alfa =
(lambda (x) (funcall faktorial-gen (lambda (v) (funcall (funcall x x) v))))

takže (Y faktorial-gen) = (alfa alfa) !!!

VYHODNOTENIE (alfa alfa):

(funcall faktorial-gen (lambda (v) (funcall (Y faktorial-gen) v)))
=> (funcall faktorial-gen (lambda (v) (funcall ( alfa alfa ) v)))

čo faktorial-gen dostane:
Faktorial-gen dostane jeden argument a to je v ; ako self, self je rekurzívna referencia.

nech self=

(lambda (v) (funcall (Y faktorial-gen) v))

a faktorial-gen je:

(defun faktorial-gen (self)
(lambda (n)
(if (= n 0)
1
(* n (funcall self (- n 1))))))

=> (* n funcall (lambda (v) (funcall (Y faktorial-gen) v))(- n 1))

ZJEDNODUŠENIE:
Vo vnútri tela funkcie máme:
(funcall (lambda (v) (funcall (Y faktorial-gen) v))(- n 1))

čo sa redukuje na:
(funcall (Y faktorial-gen)(- n 1)) kde (- n 1) je ako hodnota argumentu v, v je nejaká konkrétna hodnota, napr. 4.

A TU SA UKAZUJE KRÁSA:

Teraz vidíme, že (y faktorial-gen) sa zavolá sám na seba s menším argumentom:

(faktorial 5) = 5 * (faktorial 4)
(faktorial 4) = 4 * (faktorial 3)….až k faktorialu 0 a tu zaúčinkuje if (= n 0)

CELÝ REŤAZEC:
(Y faktorial-gen)
= (faktorial-gen (lambda (v) funcall ((Y faktorial-gen) v))) ; β-krok + η-expanzia, aby nevznikla nekonečná slučka.
= (lambda (n)
(if (= n 0) ;alebo (zerop n)
1
(*n (funcall (lambda (v) (funcall (Y faktorial-gen) v))(- n 1)))))

a po β-redukcii vnútorného funcall:
=  (lambda (n)
(if (= n 0)
1
(* n (funcall (Y faktorial-gen)(- n 1)))))

ČIŽE faktorial-gen dostane ako self:

(lambda (v)(funcall (Y faktorial-gen) v))

A keď faktorial-gen zavolá self vo svojom tele, volá vlastne (Y faktorial-gen) ale s menším agrumentom (o jedna).

Celkové zhrnutie:
pôvodná funkcia f (ktorá je tu uvedená ako faktorial-gen) dostane ako argument funkciu:

(lambda (v)(funcall (Y f) v))

Y-kombinátor je ako umelecké dielo v svete programovania. Na prvý pohľad zložitý, ale po pochopení nádherne jednoduchý a elegantný. A to je to, čo robí pekné myšlienky takými zvláštnymi: ich krása nie je v tom, ako vyzerajú, ale v tom, ako fungujú.