G.M.C

Een Grafische Metacirculaire Scheme Evaluator

Project : Interpretatie van computerprogramma's I

Naam : Van Belle Werner

Rolnummer : 47091

1^ste Kandidatuur Computerwetenschappen

Doel van het project :

Om uit te leggen wat het doel van het project is demonstreer ik het eerst even op papier.

(define (create-object x) (lambda (new-x) (set! x new-x)))

(define a (create-object 'testing_1_2_3))

(a (cons a a))

ADT's

GMC bestaat uit 4 grote delen :

1. De grafische interface : een layer rond de BGI

2. De grafische layout : De objecten die zorgen dat alles goed verdeeld wordt over het scherm

3. De objecten die gedisplayed moeten worden : procedures & environments geïmplementeerd met Message-passing.

4. De evaluator : De procedures uit het boek van Abelson & Sussman een beetje aangepast

1. De grafische interface

Hierin heb ik de volgende zaken gedefiniëerd : Type's, Colors, Views, Rectangles, Punten. Allemaal in de vorm van passieve data (t.t.z. geen objecten)

2. De grafische layout

Dit was het moeilijkste deel van het project. Zoals reeds vermeld zorgen deze objecten ervoor dat alles 'goed' op het scherm komt. Eerst ga ik definiëren wat 'goed' inhoud :

De environments/procedures (enkel deze twee komen voor op het scherm) geen andere environments/procedures snijden.

De arrows niet door environments/procedures lopen

De arrows niet over andere arrows lopen.

Om dit te verwezelijken heb ik de volgende opbouw gebruikt :

De environments worden op het scherm gezet in lagen. De bovenste laag is de laag van environments & procedures met geen voorouders (enkel de Global Environment dus). De eerste laag zijn al de environments met slechts 1 voorouder. Enz. Zie onderstaande tekening.
Elke laag wordt voorgesteld door een apart object.

Al de lagen worden bijgehouden in een grote container, envniveaus genaamd.

Een environment-laag

Een environment-laag bestaat uit 3 delen (zie bovenstaande figuur, op niveau 1). Je hebt

1. De X-coördinaten die behoren tot de environments en de pijlen. Deze coordinaten mogen nooit overlappen. Op onderstaande tekening zijn al de X-posities van niveau 1 aangegeven in het vet.

2. De Y-coördinaten die behoren tot de environments. Deze mogen wel overlappen. Op onderstaande tekening zijn al de y-coordinaten van niveau 1 die tot de environment-laag behoren in het vet aangegeven.

3. De Y-coördinaten van de arrows. Deze mogen nooit overlappen, anders heb je twee pijlen die op mekaar vallen. Op onderstaande tekening zijn de arrow-y-coordinaten van niveau 1 in het vet aangegeven.

Deze 3 verschillende soorten coordinaten worden vanzelfsprekend ook bijgehouden in 3 verschillende objecten.

De X-coordinaten worden gewoon bijgehouden in een lijst, XPossen genaamd. Ik heb hier een lijst gekozen omdat dit een soort data is die ik altijd van het begin (de linkerkant op het scherm) moet doorlopen.

De Y-coordinaten die tot de environments behoren heb ik in een Bag gestoken omdat deze verzameling y-posities geen structuur heeft. Het enige dat ik hier nodig heb is een 'insert, een 'delete en een 'foreach

De arrow-y-coordinaten, verzamel ik in een vectorcontainer with freelist. Een vectorcontainer is een vector waarin ik de datas steek op een bepaalde positie (de positie in de vector bepaald de positie op het scherm (vermenigvuldigt met een bepaalde factor)). Als er geen plaats meer is om het element op de gewenste positie toe te voegen dan wordt er een nieuwe vector aangehangen.




Dit is een manier die sneller gaat dan met lijsten te werken, minder geheugen vraagt en toch nog dynamisch is. De freelist die ik eraan heb toegevoegd is een lijst die onthoud welke y-posities vrij zijn. Hierdoor kan in tijd O(1) een ordinaat voor een arrow gevonden worden.

De verzameling niveaus

De niveaus verzamel ik in een VectorContainer (hierboven uitgelegd). Waarom? De vectorcontainer is onmiddelijk toegankelijk in tegenstelling tot lijsten. De positie in de vecorcontainer is het niveau dat je beet hebt. Als je het element op positie 3 opvraagt dan krijg je laag 3 in handen.

Een tweede aspect van de verzameling niveaus zijn de pijltjes, de arrows. Een arrow is een apart object dat gecreëerd wordt in de niveauverzameling-omgeving. Dit omdat een pijltje door meerdere lagen kan gaan en dat hij dan toegang moet hebben tot alle niveaus.

3. De objecten die gedisplayed moeten worden : environments & procedures

In onderstaande paragraaf gebruik ik de naam 'environments' zowel voor procedures als environments.

De objecten die op het scherm moeten komen moeten ook nog samenwerken met de twee layout-objecten. Ze moeten om te beginnen al een positie hebben die toegankelijk is door de layouters. Dit kan verricht worden op twee manieren :

Telkens als een environment zijn positie verandert moeten de layouters op de hoogte gebracht worden en omgekeerd.

Ofwel gebruik ik pointers die data delen. Als ik de ene data aanpas is de andere direct mee verandert.

Ik heb voor de tweede oplossing gekozen omdat deze gemakkelijker te implementeren is en toch evenveel geheugen vraagt als de eerste.

De procedures hebben een aantal messages bijgekregen i.v.m. de garbage-collecting. Deze worden in 4. uitgelegd.

4. De evaluator

Tracen

Hiervoor heb ik de 'evaluate' functie aangepast zodat hij weet of er gesteped -over moet worden of erin getraced. De bijkomende parmaters zijn :

Een parameter voor de indentatie

Een vlaggetje dat zegt of de gebruiker erover stapt of het proces wil blijven volgen.

En nog een parameter : de tekst die zegt wat er geëvalueert wordt.

Staartrecursie

Telkens als een expressie wordt geëvalueert wordt dit aan de verbonden environment mee gedeeld. Deze mededeling moet ook weer opgehoffen worden. Door op de juiste plaats het bericht op te heffen ontstaat staartrecursie. Voor verdere details verwijs ik naar de source.

Garbage collecting

De procedures & environments hebben er 3 messages bijgekregen. Ik leg ze even uit in de volgorde waarin ze opgeroepen dienen te worden.

1. Set-Not-Connected! zegt aan de environment dat hij niet verbonden is aan de global-environment.

2. Check-Connection zegt aan de environment dat hij verbonden is aan de global-environment en vraagt eveneens dat de environment het bericht doorgeeft aan al de procedures en environments die het bevat. (Dit is letterlijk message-passing style)

3. Connection-Test controleert of de environment nog recht heeft tot bestaan, indien niet verwijdert hij zichzelf

Het Tijdschema :

De grafische interface was tegen 22 januari af.

De evaluator was tegen 29 januari ingetypt.

De grafische shell wordt als basis gedefiniëerd tegen 7 februari. Nadien is deze nog een beetje aangepast aan de noden van het moment. Hij ontvangt alle commandos en tekent ze werkelijk op het scherm. Dit is een afwijking van de voorstudie, waarin stond dat hij een bericht op het tekst-scherm zou geven, maar het is nu eenmaal gemakkelijker te zien op het grafische scherm of er is voldaan aan de gestelde eisen, dan op een tekstscherm waar coordinaten worden gegeven.

Nu komt de grafische shell die alles werkelijk op het scherm zet : Dit zijn de layout-objecten die afgemaakt werden : 4 maart

De evaluator aanpassen zodat er getraced kan worden : 25 maart (dit heeft zolang geduurt omdat er een tussentijdse evaluatie was en omdat andere leerstof iets moeilijker werd.)

Testen en debuggen van het geheel : Tijdens Paasvakantie heb ik er alle kleine onaangenaamheden uitgesmeten.

Bijgeleerd ???

Als ik opnieuw zou herbeginnen aan dit project dan denk ik dat ik de grafische layout zou opstellen als een algemener constraint-system dat, los van de toepassing waarin het gebruikt word, toch nog blijft werken.

Wat veranderen ?

Let* toevoegen

De mogelijkheid om expressies te evalueren die niet getekend worden. Zo kan de gebruiker standaardfuncties toevoegen.

De meta-eval (die van PCS) & de evaluate (die van GMC) vrijgeven.

Toevoegen van primitieven

Van de primitives-list een hash-tabel maken. (source : zie primitives, de functie primitive? moet dan herschreven worden)

Het programma bestendig maken tegen circulaire lijsten. (source : zie display-object)