Een Lisp Interpreter

Ik ben ook nog een tijdje bezig geweest met een Lisp interpreter. Of meer dat wat ik dacht dat Lisp is. Het laatste wat daarmee geprobeerd heb, was het maken van een garbage collector. Hierbij stuitte ik op een aantal problemen.

Problemen met de garbage collector.

De interpreter crashte meestal na een of twee keer garbage collecten. Na een tijdje zoeken, kwam ik er achter, dat de lisp-objecten, die niet gekoppelt waren aan de rootset, niet gemarkt werden. Deze objecten werden dus verwijderd. Op zich wel logisch.

De oplossing is redelijk simpel. Ik heb een globale variable gemaakt, die ervoor zorgt, dat alle nieuwe lisp_atoms immuun worden voor de garbage collector. Op deze manier kan ik regelen of de lisp_atoms gegarbagecollect worden. Daarna wordt de immuniteit voor alle objecten opgeheven en kunnen ze weer verwijderd worden.

Op dit moment zijn de problemen met de Garbage Collector nog steeds niet opgelost. Terwijl ik dacht dat dit wel zo was.

Tail call eliminatie

Nu zijn er natuurlijk nog meer problemen. Als ik een recursieve functie aanroep, die veel (bv. 1000) stappen diep gaat, dan duurt het best lang voordat deze is teruggekeert op het laagste niveau.

Dit gebeurt bij de volgende functie (of functies die erop lijken):

(defun f (x)
    (if (= x 0)
        0
      (f (print (- x 1)))))

Het komt er op neer dat de heenweg (ongeveer) even lang duurt als de terugweg. Dat terwijl je weet dat het antwoordt van de laatste gewoon 0 is.

Om dit op te lossen, zou ik een tail call optimalisatie kunnen gebruiken. En dan dus gewoon de hele stack weg te gooien en 0 als antwoord te geven.

Het probleem is dat tegelijkertijd met de lisp-stack ook de C stack opgebouwd wordt. Die lisp-stack kan redelijk eenvoudig verwijderd worden. Maar hoe dit met de C stack kan? setjmp/longjmp misschien, of de hele evaluator data recursief i.p.v. code recursief maken.

find_local

Terwijl ik bezig met het hacken van de code van de interpreter kwam ik erachter dat de code van find_local helemaal verkeerd was. Het zocht alle lagen van de stack door tot een symbol met de goede naam gevonden was. Op deze manier kon je dus locale variabelen van andere functie aanroepen bekijken en veranderen, dat was natuurlijk niet de bedoeling. Daarom is find_local toch maar even aagepast.

Hierdoor ging de interpreter bij de bovenstaande code gelijk twee keer zo snel (bij (f 1000)) van 17.2s naar 8.4s. Het moet wel genoemd worden dat deze functie f redelijk vaak zijn locale variabele opzoekt.

Later heb ik nog bedacht dat de eerste implementatie van find_local voor het gebruik met dynamic scoping is. Toch was de implementatie niet goed, omdat de argumenten van een hoger liggende functie bezocht zouden worden.

Bytecode

Ik zat zo eens denken, als ik alle lisp-code voor mijn interpreter ga compilen naar bytecode, zou dat dan ook sneller gaan?? Waarschijnlijk wel. Ik zou dat weleens uit kunnen proberen. En wat nou als ik die bytecode JIT ga compilen? Nog meer snelheid waarschijnlijk...

Er zijn eigenlijk maar een aantal instructies, die ik dan nodig heb. Dat zouden zijn: car, cdr, cons, eq, atom, cond nog een paar. En natuurlijk zouden macros ook wel handig zijn.

Dan is het verder nog belangrijk dat de lijststructuur van het programma ook intact blijft. Waarschijnlijk is hier al veel meer onderzoek naar gedaan.

Typed pointers

In de meeste andere lisp interpreters wordt gebruik gemaakt van 'typed pointers'. Dit is een manier om bepaalde onderdelen van de interpreter kleiner te maken. Het komt erop naar dat je eerste vier bits gebruikt om te type informatie op te slaan. Je hebt dan zestien (2⁴⁾ verschillende mogelijkheden.

Snelheid

Bij een vergelijking met CLisp kwam ik erachter dat mijn interpreter best wel traag is. Zo was functie f hierboven bij clisp direct klaar, terwijl die bij mijn interpreter bijna negen seconden duurde.