La Ipsilonkombinatoro per Ses Paŝoj
Unue, decidu. Kaj faru ĝin. Estas la nura maniero por atingi ion.
—Lacus CLYNE, Gundam SEED Destiny
Enhavotabelo
- Enkonduko
- Kio?
- Paŝo 1-a: Difinu la bazan proceduron
- Paŝo 2-a: Funkcivokarigu la rikuran alvokon
- Paŝo 3-a: Apliku la proceduron al si mem
- Paŝo 4-a: Abstraktu la enan alvokon
- Paŝo 5-a: Izolu la kombinatoron
- Paŝo 6-a: Difinu la kombinatoron
- Finrimarkoj
Enkonduko
Multe da ni estis instruitaj ke, por difini rikuran proceduron, la rikura alvoko devas uzi la nomon de la rikura proceduro. Tamen, la ipsilonkombinatoro (angla artikolo) ebligas onin por presti rikuron, sen referencante la nomatan identigilon.
Kio?
La ipsilonkombinatoro estas la fonto de kaj inspiro kaj frustro de multaj homoj. Ĝi elvokas sensacion kiel surprizego kiam oni pasis la muron, sed ankaŭ igas nin skrapi niajn kapojn kiam ne senchavas trairi la labirinton. Ĉi tiu artikolo celas porti miajn proprajn metodojn kiel derivi la ipsilonan kombinatoron. Eble ne estas la plej eleganta maniero, tamen eblas funkcii por iu.
En la kodaj ekzemploj en ĉi tiu artikolo, la simbolo > montras la invitsimbolon de la skima realigo.
Paŝo 1-a: Difinu la bazan proceduron
Ni komencu per difini proceduron nomata foo kiu komputas la sumadon de pozitiva entjero, malsupren al nulo. En la sekvanta kodaĵo, la rikura alvoko okazas kiam foo aplikiĝas en la else-a parto de la kondiĉo.
> (define foo
(lambda (n)
(if (zero? n)
0
(+ n (foo (- n 1))))))
> (foo 100)
5050
Oni rimarkis, ke mi difinis je foo per eksplicita lambda-esprimo. Oni vidos postnelonge kial.
Paŝo 2-a: Funkcivokarigu la rikuran alvokon
Ni dismembrigu tiun proceduron pli detale per pli rudimentaj eroj, kaj oni aplikos ĝin per funkcivokarigado (angle currying).
> (define foo
(lambda (f)
(lambda (n)
(if (zero? n)
0
(+ n ((f f) (- n 1)))))))
> ((foo foo) 100)
5050
La plia lambda-esprimo estis bezonata ĉar oni bezonis havi manieron por abstrakti la rikuran alvokon. Tiaokaze, oni uzis la identigilon f por kunligi la rikuran proceduron, kiu estas foo mem. La stranga ((f f) …)-esprimo estas bezonata tial, ke oni devas fari la saman proceduran alvokan metodon uzata interne: ((foo foo) 100).
Paŝo 3-a: Apliku la proceduron al si mem
Oni nun eluzas ĉi tiun kvaliton por uzi sennomatan aliron—ne per la identigilo foo.
> (((lambda (f)
(lambda (n)
(if (zero? n)
0
(+ n ((f f) (- n 1))))))
(lambda (f)
(lambda (n)
(if (zero? n)
0
(+ n ((f f) (- n 1)))))))
100)
5050
Konstatiĝu, ke nun, oni ne plu uzos la nomon foo por referenci la difinon, krom poste.
Paŝo 4-a: Abstraktu la enan alvokon
Sekve, oni devas movi la parton (f f) eksteren por izoli la ĝeneralan (ipsilonkombinatoro), el la specifa (foo) kodo.
> (((lambda (f)
((lambda (p)
(lambda (n)
(if (zero? n)
0
(+ n (p (- n 1))))))
(lambda (v) ((f f) v))))
(lambda (f)
((lambda (p)
(lambda (n)
(if (zero? n)
0
(+ n (p (- n 1))))))
(lambda (v) ((f f) v)))))
100)
5050
Dum la aplikaĵo de alvoko, la identigilo p estos kunligata al (lambda (v) ((f f) v)) kaj la identigilo v estos kunligata al (- n 1).
Paŝo 5-a: Izolu la kombinatoron
Sekve, oni izolos la ipsilonan kombinatoron, el la foo proceduro.
> (((lambda (x)
((lambda (f)
(x (lambda (v) ((f f) v))))
(lambda (f)
(x (lambda (v) ((f f) v))))))
(lambda (p)
(lambda (n)
(if (zero? n)
0
(+ n (p (- n 1)))))))
100)
5050
Oni anstataŭigu la difinon specifa al foo, per x. Ĉi tio igas onin denove, por krei la enhavatan lambda-esprimo tial, ke x estas kunligata al la komputata proceduro, oni ne plu devas ripeti ĝin.
Paŝo 6-a: Difinu la kombinatoron
Fine, oni kreos apartan proceduran difinon eksplicite por la ipsilonkombinatoro mem kaj la proceduro foo.
> (define y
(lambda (x)
((lambda (f)
(x (lambda (v) ((f f) v))))
(lambda (f)
(x (lambda (v) ((f f) v)))))))
> (define foo
(lambda (p)
(lambda (n)
(if (zero? n)
0
(+ n (p (- n 1)))))))
> (define f (y foo))
> (f 100)
5050
Finrimarkoj
Kiam la kernaj konceptoj estas komprenataj, estos facile por kapti la ŝajne malfacilegajn konceptojn. Mi esperas, ke ĉi tiu artikolo estas utila por igi onin kompreni la ipsilonan kombinatoron, funkcivokarigadon, kaj proceduran aplikon.
