TCO kiegészítés, REPL, makró alapok

Eddig amiben a Scheme-t követtem:

• Lisp-1, azaz ugyanabban a névtérben vannak a változók és a függvények.
• Két kanonikus logikai konstans – #f és #t –, minden igaz, ami nem #f, az üres lista is.
• Névkonvenciók: kérdőjel végű predikátumfüggvények (eqv?, null?, boolean?, …) és felkiáltójel végű állapotmódosító függvények (set!, set-car!, set-cdr!).

Tail-call optimization

Az előző részben arról írtam, hogy mivel számos C compiler támogatja a tail-call optimizationt, ezért ha jól írjuk meg az interpretert, akkor egyszerűen delegálhatjuk a problémát a C fordítónak.

Az eddigi implementációban van egy eset, ahol ez nem működik, nevezetesen a begin

(lambda x (last x))

implementációval, mivel ez először kiértékeli az összes kifejezést egy listává fűzve őket, majd kikeresi a lista utolsó elemét.

Azt hiszem legjobb lesz, ha a jövőben speciális formával helyettesítem a begin-t. A

(lambda x (last x))

implementáció másik problémája, hogy épít arra, hogy procedúraalkalmazásnál balról jobbra sorrendben értékelem ki az argumentumokat. A R5RS ezt nem írja elő, azt viszont igen, hogy a beginnek így kell működnie, mivel pont ez a feladata (utasításszekvencia megadása).

Egyébként a tail-call optimalizáció megoldható akkor is, ha a C fordító nem támogatja:

void *f(void *arg1, void *arg2)
{
	...
	return f(kif1, kif2);
	...
}

Egyszerűen átírjuk az argumentumokat, és goto-zunk a függvény elejére:

void *f(void *arg1, void *arg2)
{
restart:
	...
	arg1 = kif1;
	arg2 = kif2;
	goto restart;
	...
}

Persze egy normális ciklus ennél szebb, ez a módszer viszont arra az esetre is általánosítható, ha nem önrekurzió, hanem kölcsönös rekurzió esetén akarjuk a tail-callokat optimalizálni. Tehát tegyük fel, hogy van egy

void *g(void *arg1, void *arg2)

függvényünk is, valamint f és g kölcsönösen hívják egymást. Ekkor a két függvényt összevonjuk eggyé:

void *fg(int fn, void *arg1, void *arg2)
{
	restart:
	switch (fn) {
	case F:
		...
		fn = G;
		arg1 = kif1;
		arg2 = kif2;
		goto restart;
		...
	case G:
		...
	}
}

Ez persze ocsmány kódot ad, cserébe viszont a C standard fogja garantálni a szemantikát, nem kell compiler optimalizációkra építeni.

Read-eval-print loop

A korábbi változatban is volt egy primitív REPL, azonban az minden megadott kifejezést a default environmentben értelmezett. Ennek az volt az eredménye, hogy minden szükséges függvényt egyetlen kifejezésbe kellett belefoglalni. Ez az átalakítás persze mechanikusan elvégezhető, azonban a tesztelést rendkívül kényelmetlenné teszi. Ezért bevezettem a define top-level formát, amely megváltoztatja az environmentet, amelyben értelmezik – esetünkben az interpreter default environmentjét.

Ehhez egyszerűen létrehoztam egy eval_toplevel függvényt, ezt hívja alapból a REPL. Az eval_toplevel megvizsgálja, hogy definíciót adtunk-e neki, ha igen, akkor annak megfelelően cselekszik, ha nem, akkor meghívja a kapott kifejezésre a sima eval-t. Az eval rekurzívan az eval-t hívja a részkifejezések kiértékelésére, így a belső define-ok jelenleg nem működnek. Ez azért csináltam így, mert az R5RS szerint a belső define-ok gyakorlatilag egy letrec kifejezéssel ekvivalensek, míg a top-level define leginkább a set!-re hasonlít azzal, hogy akkor is működik, ha az adott név még egyáltalán nem lett bevezetve.

Ez a funkció lehetővé teszi, hogy a korábban

((lambda (begin even-length)
   (begin
     (set! even-length
           (lambda (l)
             (if (null? l)
                 #t
                 (not (even-length (cdr l))))))
     (even-length (quote (1 2 3)))))
 (lambda (one two) two)
 (quote unbound))

formában megadott kódot a következőképpen adhassuk meg:

(define even-length 
  (lambda (l)
    (if (null? l)
        #t
        (not (even-length (cdr l))))))
(even-length (quote (1 2 3)))

Ez nyilván jóval áttekinthetőbb.

Köszönet hrgy84-nek az ötletért, hogy readline-os REPL legyen history-val. Ezt egyelőre még nem csináltam meg, de azt hiszem később meg fogom.

Makrók

A makrók a Lisp egyik karakterisztikus feature-e, melyek segítségével új szintaktikai formákat lehet definiálni, ezzel a metaprogramozást támogatják. A Lisp „code as data” elve – mely azt jelenti, hogy a Lisp forrásszöveg a Lisp beépített adatszerkezeteivel van leírva – lehetővé teszi, hogy egyszerűen manipulálhassunk Lisp forráskódot Lisp programból.

A makrók területén nem az R5RS előírásait követtem, hanem inkább a Common Lispet másoltam. A Common Lisp makrói egyszerűbbek, sokoldalúbbak, ugyanakkor kevésbé „biztonságosak”.

Példának vegyünk egy egyszerű makrót, amely kétszer alkalmaz egy argumentumot valamely procedúrára:

(define-macro twice (lambda (f x) (cons f (cons x (cons x (quote ()))))))

Teszteljük:

> (twice cons #t)
(#t . #t)

Ezt a példát persze egy egyszerű magasabb rendű függvénnyel is meg lehetett volna írni. A makró annyiban különbözik a megfelelő függvénytől, hogy itt a megadott argumentum ténylegesen kétszer kerül kiértékelésre.

> (define x #f)
x
> x
#f
> (set! x #t)
()
> (twice cons (set! x (not x)))
(())
> x
#t

Láthatjuk, hogy set! mindig üres listát ad vissza, ezért lesz a twice hívás eredménye egy üres listát tartalmazó egyelemű lista. Amit észre kell venni, hogy x értéke nem változik, hiszen kétszeri negáláson esett át.

Az implementációról annyit, hogy bevezettem egy define-macro top-level formát, amely egy különálló environmentbe gyűjti a makrókat. Az eval-t átírtam, hogy függvényalkalmazásnak tűnő forma esetén nézze meg a macro environmentben, hogy van-e a lista első elemének megfelelő név. Ha igen, akkor makróhívásként kezeli, ha nem, akkor közönséges procedúraalkalmazásként. Makróhívás esetén az argumentumok kiértékelés nélkül a makrófüggvényhez kerülnek, majd az eredményre újra meghívom az eval-t – kódként értelmezve azt. A tesztelés megkönnyítése érdekében bevezettem a macroexpand függvényt, amely megmutatja, hogy milyen kód fog futni a makrókifejtés után. A fenti példában ezek:

> (macroexpand (quote (twice cons #t)))
(cons #t #t)
> (macroexpand (quote (twice cons (set! x (not x)))))
(cons (set! x (not x)) (set! x (not x)))

Itt már egyre nagyobb igény van a quasiquote-okra, mivel egy bonyolultabb makrónál sokszor kényelmetlen kézzel összerakni a programkódot ábrázoló listát.

Hát azt hiszem most itt abbahagyom, mert már este van és elfáradtam.

TODO

Néhány feljegyzés magamnak, hogy mit akarok a következőkben megcsinálni:

• begin implementálása speciális formaként
• readline integrálás a REPL-be
• aritmetika, quasiquote
• makrókról írni még