SASL 860409 (c) 1986 by ORD-GROUP 45 SASL Inleiding De programeertaal SASL is vrij nieuw en nog niet algemeen bekend. Het is een functionele programmeertaal, d.w.z. alles gaat aan de hand van functies; het begrip 'statement' bestaat niet. (Zie ook de LISP documentatie.) SASL heeft een aantal erg handige eigenschappen. Zo kan men bijvoorbeeld een oneindig lange lijst definieren. De meeste programmeertalen zouden eerst de lijst gaan uitrekenen en hem dan printen, maar aangezien de lijst oneindig lang is zouden ze nooit aan het printen toekomen. SASL rekent alleen het eerste element uit, print dat en gaat dan pas naar het tweede element van de lijst kijken. Dit principe strikt doorgevoerd staat bekend als 'lazy evaluation'. De lazy evaluation samen met het functioneel programmeren maken SASL tot een zeer krachtige taal. Daarom hebben we besloten om SASL te implementeren. Algemeen Voor onze implementatie van SASL hebben wij gekozen om zo min mogelijk willekeurige beperkingen te maken. b.v. Een getal mag een willekeurig geheel getal zijn zolang het maar in het geheugen past. Volgens prognoses zou het grootste getal dat we kunnen representeren ongeveer 50 000 cijfers hebben. In tegenstelling tot floating point berekeningen rekenen wij in de volle nauw- keurigheid (fixed point). Implementatie Onze implementatie bestaat uit 2 delen. Een compiler vertaalt SASL naar een tussencode die wij haakjescode noemen. Een inter- preter leest deze haakjescode in en interpreteert deze. De inter- preter is inmiddels af en werkt naar behoren. De compiler moet nog worden geschreven maar wij hebben een tijdelijke compiler in LISP geschreven. Deze compiler accepteert invoer in een LISP- achtive notatie die veel op SASL lijkt. Het grootste verschil met SASL is dat er veel haakjes nodig zijn. Wij hebben deze compiler gebruikt om de interpreter te testen. De interpreter werkt intern met behulp van combinatorische logica (het is een SK-interpreter). Om de werking van de interpreter te kunnen begrijpen moeten wij eerst wat algemene dingen behandelen. SASL heeft een aantal ingebouwde standaardfuncties. Een aantal van deze standaardfuncties hebben maar een argument nodig. Voor- beelden zijn: head, tail, abs etc. De functies "head" en "tail" dienen ervoor om een lijst uiteen te kunnen rafelen in zijn elementen. 'hd (1,2,3,4,5)' is gelijk aan '1' 'tl (1,2,3,4,5)' is gelijk aan '2,3,4,5' SASL 860409 (c) 1986 by ORD-GROUP 46 Een aantal standaard functie shebben twee argumenten nodig, zoals + - * / mod De formule 5+3 wordt intern opgeslagen als ((+ 5) 3) Merk op dat tussen elk haakjespaar er precies 2 objecten staan. Het linker object is een functie en het rechter object is het argument voor die functie. We noemen zo'n haakjespaar ook wel een cel. + Is strikt genomen een functie waar een argument ingaat en waar een functie uitkomt. Zo komt uit (+ 5) de functie 'er vijf bij optellen'. Als men in deze functie een argument stopt zal de functie er vijf bij optellen en het resultaat teruggeven. De functie ((+ 5) 3) is dus 'er vijf bij optellen' van 3. De uit- komst is natuurlijk 8. Op deze manier worden alle functies in SASL gereduceerd tot een functie van 1 argument. Deze reductie heet currying, naar de uitvinder Curry. Wij gaan nu eens kijken naar wat de compiler doet met de volgende definitie van de faculteitsfunctie Als invoer voor de compiler hebben we: fac 0=1 fac n=n*fac(n-1) Dit is een definitie van de functie 'fac'. Het eerste dat de compiler doet is dit omzetten naar een enkele uitdrukking. fac n= if (n=-) then 1 else n*fac(n-1) Nu worden de '=' de '-' en de '*' naar voren gehaald en alle functies worden gecurried geschreven. We krijgen dan ( ) ( 1) ( ) (if ) (* n) (fac ) ( 0) ( 1) (- n) (- n) Waarbij voor de duidelijkheid het haakjesniveau verticaal is uitgezet. De 'if A then B else C' wordt: (((if A) B) C) De 'n=0' wordt: ((= n) 0) De 'n-1' wordt: ((- n) 1) De 'A*B' wordt: ((* A) B) Dit dient weer op dezelfde manier te worden gelezen als bij de plus. '(= n)' is dus de functie 'is het gelijk aan n?'. (if A) is SASL 860409 (c) 1986 by ORD-GROUP 47 een functie waarin je een argument B kan stoppen. De uitkomst daarvan is een functie waarin je een argument C kan stoppen. De uitkomst daarvan is of B of C al naar gelang de waarde van A. Al met al zijn we nog niet klaar. Er staat nog steeds een n in de formule. Die n gaan we weghalen met een methode die we abstra- heren noemen. ((+ n) 1) Stelt de formule n+1 voor. De n is hier niet bekend en moet nog ingevuld worden. Dit schrijven we als volgt: ((+ B L) C 1) De L staat voor 'lambda' of leeg. De B is een zogenaamde combi- nator en staat tussen de functie en het argument in. Die L staat er om te zeggen: 'als je deze cel tegen komt en je hebt een argument voor mij dan moet je die aan de rechterkant invullen.' De C is ook een combinator en heeft zo ongeveer de betekenis: 'als je deze cel tegen komt en je hebt een argument dan moet je die aan de linkerkant invullen' ((+ B L) C 1) is dus een functie waar 1 argument in moet. Als je er 1 argument in stopt dan vertellen de B en de C je waar je hem moet invullen. Het argument neemt de plaats in van de L. De ontstane expressie kunnen we uitrekenen en er komt een meer dan het argument uit. We zullen deze combinatoren nu ook in onze fac invullen: ( S ) ( C 1) ( S ) (if B ) (* B L) (fac B ) ( C 0) ( C 1) (= B L) (- B L) De S combinator vertelt dat een argument aan beide kanten ingevuld moet worden. Als men een argument neemt en telkens bij een S aan beide kanten, een B rechts en een C links invult komt het argument precies op die plaatsen terecht waar de n eerst stond. Als we alles nu netjes achter elkaar zetten krijgen we dit: fac: (((if B ((= B L) C 0)) C 1) S ((* B L) S (fac B ((- B L) C 1)))) Dit is inderdaad bijna wat er uit de compiler komt. Voor mensen totaal onleesbaar maar voor de interpreter zeer begrijpelijk. Merk op dat we hier het begrip 'faculteit' hebben opgeslagen en niet 'de faculteit van n is n keer n min 1'. In onze repre- sentatie komt geen dummy variabele voor. Merk op dat fac wel naar zichzelf refereert. Dit kan worden opgelost door wat gegoochel met combinatoren maar wij hebben een iets eenvoudigere oplossing. Elk haakjespaar is een cel in onze geheugenrepresentatie en in plaats van 'fac' vullen we gewoon een pointer in naar de eerste cel van de definitie van de faculteit. SASL 860409 (c) 1986 by ORD-GROUP 48 Deze definitie wordt dan wel een cyclische structuur maar daar heeft de interpreter geen last van. De functie 'fac' is nu geheel geschreven als een graaf met daarin referenties naar standaard- functies. Dit hele proces kan worden gegeneraliseerd naar meerdere argu- menten. In het midden van een cel kunnen dan meerdere combi- natoren achter elkaar staan die ieder een argument in de goede richting(en) doorsturen. De interpreter krijgt een expressie van de compiler aangeboden. De interpreter probeert die expressie uit te rekenen door te gaan invullen. De voornaamste regels zijn: ( (p B q) r) = (p (q r)) ( (p C q) r) = ((p r) q) ( (p S q) r) = ((p r) (q r)) d.w.z. Het invullen van de combinatoren die we hierboven hebben gegenereerd. Als de interpreter een standaardfunctie tegenkomt dan wordt de desbetreffende subroutine met de goede argumenten aangeroepen. Het kan worden aangetoond dat er op deze manier het goede antwoord uitkomt. Dit lijkt veel eenvoudiger dan het werk dat de compiler moet doen. In de praktijk is het, voor zover wij kunnen overzien, een stuk moeilijker. Ten eerste moet de interpreter vanwege effi- cientieoverwegingen in assembler worden geschreven terwijl de compiler best in een hogere programmeertaal kan worden geschreven. Ten tweede bestaat een groot deel van het werk van de interpreter uit het werken met 16 bits waarden. Als de snelheid van het programma belangrijk is dan wordt dit op een 8 bits machine op z'n zachtst gezegd onoverzichtelijk. De indexregisters van de Z80 zijn vrij langzaam en kunnen daarom niet al te veel worden gebruikt. Ten derde is het rekenen met zeer grote getallen lang niet eenvoudig. De problemen betreffende de garbagecollector zullen nog besproken worden. Al met al rijst de vraag 'waarom zo moeilijk?'. Zonder combinatoren is het veel moeilijker om lazy evaluation toe te passen. Als we bijvoorbeeld de volgende SASL definities hebben voor een functie f van variabelen: f 0 b=1 f a b="een of andere expressie in a en b" we kunnen dan vragen om b.v. ((f 0) (fac -1) ) Volgens de definitie van fac duurt het uitrekenen van fac(-1) oneindig lang. Maar omdat het eerste argument van f 0 is hebben we het tweede helemaal niet nodig, er komt 1 uit. SASL zal dan ook netjes 1 als resultaat geven. Dit is mogelijk omdat bij het invullen van het eerste argument een functie ontstaat die het tweede argument weggooit. Voor zover wij weten is dit zonder combinatoren nog veel moeilijker om op te lossen. SASL 860409 (c) 1986 by ORD-GROUP 49 Het voornaamste werk van de interpreter bestaat er dus in om telkens maar combinatoren in te vullen in een grote samenhangende meestal cyclische graaf. Verder moet dit natuurlijk zo snel mogelijk gaan. De graaf bestaat in het geheugen uit een aantal cellen met onder- linge pointers. In extra bits is gecodeerd wat voor type pointer of cel het is. Garbage collection Het beschikbare geheugen wordt opgedeeld in 3 gebieden. Van onder naar boven zijn dat de celruimte waar alle cellen staan, de vrije ruimte en de stack. De celruimte groeit naar boven toe en de stack naar beneden. Bij het roeren in de graaf moet de inter- preter soms nieuwe cellen aanmaken terwijl sommige cellen achter- blijven zonder dat een pointer deze aanwijst. Als de bovenste cel in het geheugen in de buurt van de stack komt moet er worden opgeruimd. Alle loze cellen worden weggehaald en alle nuttige cellen naar onder toe aangeschoven. Hierdoor ontstaat weer een grote ruimte tussen de stack en de bovenste cel en beiden kunnen weer groeien. Dit opruimen noemen we garbage collection. Het grote probleem bij garbage collection is dat de garbage collector niet te veel geheugen gebruiken mag want hij wordt pas aangeroepen als er een tekort aan geheugen is. Dat betekent dat de garbagecollector een van tevoren gestelde (lage) bovengrens op het geheugengebruik moet hebben. De garbage collector zoekt alle pointers op die van buiten in de graaf wijzen. De cellen waar die pointers naar toe wijzen zijn in gebruik en worden dus gemerkt. Cellen bevatten pointers en alle cellen die worden aangewezen door een pointer die in een gemerkte cel staat zijn ook in gebruik en moeten dus ook worden gemerkt. Dit gaat door todat alle bereikbare cellen zijn gemerkt. De ongemerkte cellen zijn onbereikbaar en dus nutteloos. Het grote probleem is nu hoe je alle cellen kunt merken zonder te veel geheugen te gebruiken. Het merkproces is inherent recursief en de garbage collector moet ergens bijhouden welke pointers hij nog allemaal moet volgen. De oplossing is als volgt: De garbage collector heeft een op- en een neerpointer. Als de neerpointer niet naar een cel wijst dan gaat de garbagecollector terug omhoog langs de oppointer. Als de neerpointer wel naar een cel wijst dan wordt deze gemerkt. Als deze cel een linkerpointer bevat dan wordt op de plaats waar deze linkerpointer staat de oppointer neergezet, de oppointer wordt de neerpointer met het merkteken 'links', en de neerpointer wordt de linkerpointer van de cel. Het hele proces herhaalt zich dan. Als de garbagecollector terug omhoog wil kan het aan het merkteken van de oppointer zien op welke plaats in de cel de vorige op- pointer staat. Het hele proces wordt herhaald voor de rechter- pointer waarna de garbage collector terug omhoog kan gaan. In feite komt dit erop neer dat je de stack van de garbage collector in de graaf bijhoudti.p.v. op de CPU stack. SASL 860409 (c) 1986 by ORD-GROUP 50 Voor de duidelijkheid volgt hier nu het algoritme: "Volg een pointer en merk alle cellen die bereikbaar zijn" S1 omh:=nil;oml:=pointer om te volgen S2 ALS oml niet naar een cel wijst of cel(oml) is al gemerkt DAN ga naar S5 S3 ALS linkerpointer in cel(oml) bestaat DAN temp:=linkerpointer(cel(oml)) ;linkerpointer(cel(oml)):=omh ;omh:=oml met merkteken links ;oml:=temp ;ga naar S2 S4 temp:=rechterpointer(cel(oml)) ;rechterpointer(cel(oml)):=omh ;omh:=oml met merkteken rechts ;oml:=temp ;ga naar S2 S5 ALS omh=nil DAN stop ;ALS merkteken omh=rechts DAN ga naar S6 ;temp:=oml ;oml:=omh ;omh:=linkerpointer(cel(oml)) ;linkerpointer(cel(oml)):=temp ;ga naar S4 S6 temp:=oml ;oml:=omh ;omh:=rechterpointer(cel(oml)) ;rechterpointer(cel(oml)):=temp ;ga naar S5 In de praktijk is het algorithme nog iets moeilijker omdat er nog wat uitzonderingsgevallen zijn. Nadat alle cellen op deze manier zijn gemerkt worden ze op een hoop geveegd en alle pointers worden omgelegd zodat ze naar de zelfde cel blijven wijzen. De benodigde rekentijd voor het hele algoritme is evenredig met het aantal cellen en het aantal pointers. Dit in tegenstelling tot b.v. de garbage collectors die in veel BASIC interpreters worden gebruikt. Hierbij is de rekentijd vaak evenredig met het kwadraat van het aantal strings. Conclusie Al met al is de SASL interpreter zeker het moeilijkste programma dat wij tot nu toe hebben geschreven. De totale lengte is niet zo groot maar het vele gehutsel met pointers en cellen maakt de machinecode erg moeilijk begrijpbaar, temeer daar er met 16 bits waarden wordt gegeoocheld op een 8 bits machine. De ervaringen die we hebben opgedaan tijdens het testen zijn zeer positief. Programmeren in SASL is veel eenvoudiger dan in andere programmeertalen. Omdat er nauwelijks restricties zijn (de enige SASL 860409 (c) 1986 by ORD-GROUP 51 foutmelding die een programma kan geven is dat er niet genoeg geheugen is) hoeft men veel minder na te denken bij het omzetten van een idee in een programma. Voor zover wij weten is dit de enige implementatie van SASL op een microcomputer.