Quasiquote, aritmetika

Először azonban néhány témába vágó forrásra hívnám fel a figyelmet. Matt Might blogja számos témába vágó bejegyzést tartalmaz, és sok olyat is, aminek ugyan nem kötődik szorosan a Lisp implementálásához, de egybevág a szakmai érdeklődésemmel. Ezek közül számos foglalkozik a continuationökkel (1, 2, 3, 4, 5), amelyek jelen vannak a modern Lisp implementációkban, így nekem is szándékomban áll jobban megérteni őket. (A saját interpreteremben egyelőre egyáltalán nem foglalkoztam azzal, hogy a jövőben a continuationök is támogatva legyenek, bár az egyik post épp adott egy ötletet hozzá: úgy érzem egy small-step interpreter kialakításával egyszerűen megoldható lesz a continuation implementálása.)

Sikerült továbbá két jó könyvet beszereznem a könyvtárból: Lisp in Small Pieces – ez nagyon tetszik most; valamint Compiling with Continuations – azt hiszem, ez majd később lesz hasznos.

Számok

Végre vannak számok a Lisp implementációmban. Ennek már csak azért is örülök, mert így már nem csak a logikai értékek az egyedüli elérhető self-evaluating* kifejezések, így kevesebbet kell quote-olni, ha tesztelni akarok valamit.

Egyelőre csak egész számok vannak, valamint az összeadás, kivonás és szorzás műveletek, de mivel nem numerikus számításokra készítem a Lisp változatomat (legfeljebb újabb Lisp interpretert és/vagy compilert írok benne előreláthatólag), ezért azt hiszem ez bőven elég lesz egy jó ideig. Ugyanakkor tetszőlegesen nagy számok használhatóak, köszönhetően annak, hogy GMP library (The GNU Multiple Precision Arithmetic Library) egész típusát használtam fel. Így pl. lazán működik a következő:

> (define fib
    (lambda (a b n)
      (if (eqv? n 0)
          (cons a b)
          (fib b (+ a b) (- n 1)))))
fib
> (fib 0 1 0)
(0 . 1)
> (fib 0 1 5)
(5 . 8)
> (fib 0 1 20)
(6765 . 10946)
> (fib 0 1 50)
(12586269025 . 20365011074)
> (fib 0 1 100)
(354224848179261915075 . 573147844013817084101)
> (fib 0 1 200)
(280571172992510140037611932413038677189525 . 453973694165307953197296969697410619233826)
> (fib 0 1 500)
(139423224561697880139724382870407283950070256587697307264108962948325571622863290691557658876222521294125 . 225591516161936330872512695036072072046011324913758190588638866418474627738686883405015987052796968498626)

Egy dolgot meg kell említeni egy ilyen C-s library integrálásakor, az pedig a memóriakezelés. Míg a fölösleges Lisp objektumokat a garbage collector takarítja, addig a GMP alapértelmezés malloc/free párossal kezeli a memóriát, ezért amikor Lisp objektumba csomagolunk külső C objektumokra hivatkozásokat, akkor a Lisp objektum GC általi felszabadítása nem jár magától automatikusan a kapcsolódó C-s erőforrások felszabadításával. Általános megoldás erre a problémára finalizer, amit a Boehm GC támogat, de én úgy döntöttem, hogy inkább a GMP allokátorait változtatom meg.

Úgy tippelem, hogy gyorsabb lehet, ha a GMP is a GC-n keresztül foglal memóriát, mintha a GC-nek finalizationnel kellene vacakolnia – bár a sebesség egyelőre nem szempont. Viszont van ennek egy hátránya, mégpedig az, hogy mivel a Boehm GC konzervatív, ezért ezentúl a számokban is fog pointereket keresni, ami könnyebben fog szivárgáshoz vezetni (különösen 32 bites rendszeren). Létezik ugyan egy igen hasznos GC_malloc_atomic hívás, ami jelzi, hogy az adott blokkban nem lesznek pointerek, ez azonban nem használható a GMP-vel, mivel a dokumentáció szerint: GMP may use allocated blocks to hold pointers to other allocated blocks. This will limit the assumptions a conservative garbage collection scheme can make.

Apróságok, standard library, rekurzió

Először gyorsan jelezném, hogy megírtam a begin-t speciális formaként, miután az előző írásomban jeleztem, hogy a korábbi implementációnál a begin-t követő utolsó kifejezés nem volt tail-call. Bár a Lisp in Small Pieces-t olvasva nem is tűnik az olyan jó ötletnek, ugyanis mindjárt két módszert is javasol a begin helyes – bár csak kétparaméteres – implementálására:

(if α β β) ≡ (begin α β)

vagy

(begin α β) ≡ ((lambda (void) β) α)

Mindegy, ehhez most egyelőre nem nyúlok.

Mivel a nyelv már egyre erősebb, ezért már egyszerűbb dolgokat meg lehet írni magában a nyelvben, így kezd dagadni lassan a „standard könyvtáram”. Először listakezelő függvényeket írtam, itt leginkább a Haskell háza tájáról merítettem: megírtam az általános foldl, foldr és foldr1 függvényeket rekurzívan, majd ezek segítségével megírhattam a reverse-t (listát fordít), a map-et (lista elemeire alkalmaz egy paraméterként kapott függvényt) és az append-et (tetszőleges számú listát fűz össze) úgy, hogy azokban nem használtam közvetlenül rekurzíót. Ez a listakezelés azért fontos, hiszen a maga a Lisp kód is listákból áll, így az ilyen alapfunkciók szükségesek ahhoz, hogy Lisp programból gyúrjak Lisp kódot. Szóval végül is leginkább a makrók miatt kell egyelőre, amikkel magában a nyelvben bővíthetem a nyelvet.

Quasiquote

A quasiquote a quote-hoz hasonló, azonban lehetőséget nyújt unquote-olásra: tehát az idézésnek megfelelően a kifejezés nagy része nem kódként, hanem adatként értelmezendő (mint a quote-nál), azonban be lehet szúrni unquote-olt kifejezéseket, amelyek kódként fognak futni, és értékük behelyettesítődik az adott helyre. Ezek nagyon kényelmesek makrók írásakor.

Nézzünk egy-két példát:

> (define a 1)
	; definiálunk néhány változót
a
> (define b 2)
b
> (define c 3)
c
> (quote (a b c))
	; sima quote
(a b c)
> (quasiquote (a b c))
	; quasiquote, ugyanazt adja
(a b c)
> (quasiquote (a (unquote b) c))
	; viszont unquote megengedett, b értéke helyettesítődik be
(a 2 c)
> (quote (a (unquote b) c))
	; quote-nál nincs unquote
(a (unquote b) c)

Élve a nyelv adta lehetőséggel, magát a quasiquote-ot is makróként írtam meg: ennek tárgyalásához vegyünk egy decorate-nek nevezett függvényt (azaz makrót), amely olyan kódot generál, amely pontosan ugyanazt az adatot adja futtatva, mint amit a decorate paraméterül kapott, tehát:

> (macroexpand (quote (decorate a)))
(quote a)
> (decorate a)
a
> (macroexpand (quote (decorate (a b c))))
(list (quote a) (quote b) (quote c))
> (decorate (a b c))
(a b c)
> (macroexpand (quote (decorate (a #t p -2 () (c -1)))))
(list (quote a) #t (quote p) -2 (list) (list (quote c) -1))
> (list (quote a) #t (quote p) -2 (list) (list (quote c) -1))
(a #t p -2 () (c -1))

A decorate implementációja:

(define-macro decorate
  (lambda (arg)
    (letrec ((decorator
              (lambda (arg)
                (cond ((symbol? arg)
                       (list (quote quote) arg))
                      ((null? arg)
                       (list (quote list)))
                      ((not (pair? arg))
                       arg)
                      (else
                       (cons (quote list)
                             (map decorator arg)))))))
      (decorator arg))))

Tehát lényegében ha szimbólum, akkor quote-ol, ha lista, akkor (list …) kifejezést generál, self-evaluating érték esetén pedig simán visszaadja az értéket. A quasiquote alapvetően ennek a továbbfejlesztése, csak némiképp bonyolultabb, két okból: a quasiquote-ok egymásba ágyazhatók és az unquote-splicing miatt.

Van még egy súlyos kényelmetlenség: egyelőre ki kell írkálni szavakkal, hogy quote, quasiquote, unquote, unquote-splicing. Más Lisp implementációkban általában vannak rövidítések erre, de ezt azt én readerem még nem támogatja. Azokkal a rövidítésekkel ezen a sorok

> (macroexpand (quote (decorate (a #t p -2 () (c -1)))))
(list (quote a) #t (quote p) -2 (list) (list (quote c) -1))

pl. így néznének ki:

> (macroexpand '(decorate (a #t p -2 () (c -1))))
(list 'a #t 'p -2 (list) (list 'c -1))

Mindjárt könnyebben írható és olvasható.

Szóval a legközelebbi tervem a reader felokosítása. Korábban már írtam kétszer egy majdnem teljes R5RS lexert szimbólumtáblával, várhatóan ezt fogom majd portolni a meglévő Lisp interpreteremhez.

Hej, eredetileg szándékomban állt további terveket írni a makrókkal kapcsolatban, de ezt most egyelőre tovább halasztom. Azért legyen itt magamnak egy kis görgetett tennivalólista:

• reader (lexer + parser) cseréje okosabbra
• readline integrálás a REPL-be
• makrókról írni még
• bootstrapping problémák

----------------

*self-evaluating: olyan adat, ami kódként értelmezve önmagát adja, quote-olás nélkül is. Ilyenek a számok, sztringek, karakterliterálok, logikai literálok, tömb-literálok. Nem ilyen a szimbólum, aminek az alapértelmezett jelentése kódban a változónév, továbbá a lista, amelyik alapértelmezett jelentése a függvényalkalmazás.