Reeks 1 : De Meta-Circulaire Evaluator

8.9

Reeks 1 : De Meta-Circulaire Evaluator

Deze oefeningenreeks behandelt de meta-circulaire evaluator uit hoofdstuk 4.1 van Structure and Interpretation of Computer Programs. Dit is een evaluator voor Scheme geschreven in Scheme. De oefeningen (en later ook de oplossingen) kan je vinden op de oefeningenwebsite.

De meta-circulaire evaluator start je door het bestand "icp_1_1_meval.scm" te evalueren in DrRacket. Er zijn dan tegelijkertijd 2 Scheme interpreters in het spel. Allereerst is er de Scheme evaluator van de omgeving waarin je aan het werken bent. Deze evaluator evalueert het programma dat je zonet gedownload hebt. Dit Scheme-programma is toevallig zelf een interpreter voor Scheme.

Wanneer je bij je experimenten met de meta-circulaire evaluator een foutmelding voorgeschoteld krijgt, kan je deze opnieuw starten door de parameterloze functie driver-loop op te roepen. De globale omgeving wordt dan niet geherinitialiseerd, waardoor je eventuele test-variabelen niet opnieuw moet toewijzen. Indien je de globale omgeving toch wil herinitialiseren, moet je de volledige evaluator opnieuw starten (ahv DrRacket’s run).

1 Soorten expressies

1.1 Oefening: Soorten expressies herkennen

De evaluator behandelt de verschillende soorten expressies elk op een specifieke manier. Welke soorten worden onderscheiden? In welke procedure vind je dit terug in de code? Hoe herkent deze procedure de verschillende expressies? Ga dit na voor volgende expressies.

(define x 4)

(* 3 4)

(set! x 99)

(lambda (a b) (* (+ a b) (- a b)))

Opmerking: Expressies kunnen eveneens gecategoriseerd worden aan de hand van de manier waarop de evaluator hen uitvoert:

Functie-applicaties maken het merendeel uit van de expressies in een Scheme-programma.
Primitieve expressies en speciale vormen hebben een specifieke evaluatie-methode.
Afgeleide expressies zijn een subcategorie van speciale vormen die worden doorvertaald naar expressies die de evaluator reeds kan evalueren. Zo worden cond-expressies door de evaluator bijvoorbeeld doorvertaald naar geneste if-expressies.

2 Uitbreiden van de evaluator

Voor het uitbreiden van de evaluator zijn er dus ook drie mogelijkheden overeenkomstig bovenstaande categorieën:

Toevoegen van extra primitieve procedures (zoals cons, +, -, *, ...)
Toevoegen van speciale vormen (zoals define, set!, if, ...)
Toevoegen van extra afgeleide expressies (zoals de cond, let, ...)

Niet elke manier is echter geschikt voor elke uitbreiding. Afgeleide expressies kan je eenvoudig implementeren door deze te vertalen naar eenvoudigere expressies. Dit wil natuurlijk niet zeggen dat je het zo moet doen. Een expressie kan ook altijd rechtstreeks geëvalueerd worden door een specifieke evaluatie-functie. Dit is vaak zelfs efficiënter (maar wel moeilijker te implementeren).

2.1 Oefening: Expressies tracen

Ga na (trace de code en zie welke functies achtereenvolgens worden opgeroepen) hoe de evaluator de waarde (niet) berekent van de volgende expressies:

(+ 3 4)

(lambda () (+ 3 4))

Opmerking: 'xxx en gelijkaardige expressies worden automatisch door de scheme-reader omgezet in "(quote xxx)". Een inverse transformatie gebeurt ook bij het afdrukken. Je zal als gebruiker dus nooit een lijstje van de vorm "(quote ...)" te zien krijgen, alhoewel quotaties intern wel zo voorgesteld worden.

2.2 Oefening: Extra primitieven

Voeg volgende primitieve functies toe aan de meta-circulaire evaluator:

pair?
display
newline
number->string

Test vervolgens of je uitbreiding werkt.

> (begin (display "azerty")(newline)
(display "qwerty"))
azerty
qwerty
;;; M-eval value:
#<void>
> (pair? (cons 1 2))
;;; M-eval value:
#t
> (number->string 11 2)
;;; M-eval value:
1011

2.3 Oefening: bitwise-and

Voeg de functie bitwise-and toe aan de evaluator als nieuwe primitieve. Deze functie neemt twee getallen en neemt de binaire AND ervan.

> (bitwise-and 2 3)
2

2.4 Oefening: shift

Een veel voorkomende operatie op binaire getallen zijn zogenaamde shifts. Hierbij wordt de binaire representatie van het getal enkele malen naar links of rechts geschoven.

Implementeer deze shift als primitieve procedure.

> (shift 1 2)
4
> (shift 3 1)
6
> (shift 4 -1)
2

2.5 Oefening: and

Voorzie de evaluator van een and. In welke van de categorieën valt een and-expressie?

Je kan deze expressie op twee manieren implementeren. Ofwel rechtsreeks als special form d.m.v. een eval-and functie te definiëren,

(define (eval-and exp env)
...)

ofwel als een afgeleide expressie (derived expression) d.m.v. and->if functie die de and-expressie doorvertaald naar een (aantal) if-expressie(s).

(define (and->if exp)
...)

> (and true true true)
;;; M-eval value:
#t
> (and true false true)
;;; M-eval value:
#f
> (and true true 'some-symbol)
;;; M-eval value:
some-symbol

Implementeer de and op beide manieren: als special form en als afgeleide expressie van een if.

2.6 Oefening: let

Voorzie de evaluator van een let eens als special form en eens als afgeleide expressie van een expressie die de evaluator reeds kan interpreteren. Teken eerst de syntaxboom van deze expressie.

Hint: De expressie (let ((var-1 expr-1) ... (var-n expr-n)) body) is equivalent aan ((lambda (var-1 ... var-n) body) expr-1 ... expr-n)

(define (eval-let exp env)
...)

(define (let->applied-lambda exp)
...)

> (let ((a 1)
(b 2))
(cons a b))
;;; M-eval value:
(1 . 2)

2.7 Oefening: let*

Voorzie de evaluator van een let*. Leg uit hoe een let* expressie kan herschreven worden als een reeks van geneste let expressies. Voorzie vervolgens de evaluator van een let* aan de hand van een transformatiefunctie: (define (let*->lets exp) ...)

Belangrijk: het resultaat van een oproep van deze functie is opnieuw een Scheme-expressie. Vergeet deze niet verder te evalueren.

> (let* ((a 3)
(b (cons 2 a)))
(cons 1 b))
;;; M-eval value:
(1 2 . 3)

2.8 Oefening: while en until

Voeg aan de evaluator de controlestructuren while en until toe door de functies eval-while en eval-until te implementeren.

Je kan de volgende syntax voor de controlestructuren gebruiken: (while condition body ...) (until condition body ...)

> (define i true)
;;; M-eval value:
ok
> (while i
         (display "in while: ")(display i)(newline)
         (set! i false))
in while: #t
;;; M-eval value:
#<void>
> (until i
         (display "in until: ")(display i)(newline)
         (set! i true))
in until: #f
;;; M-eval value:
#<void>

2.9 Oefening: map

Schrijf zelf een hogere-orde my-map-functie en test deze uit in de meta-circulaire evaluator.

Beschouw map nu echter als een primitieve functie. De meta-circulaire evaluator moet applicaties van map dus evalueren door de map uit de onderliggende Scheme-omgeving op te roepen.

Wat gebeurt er als je deze map uittest? Verklaar.

2.10 Oefening: let* als speciale vorm

Voorzie de evaluator van een let*. Maar implementeer let* nu als speciale vorm:

> (let* ((a 3)
(b (cons 2 a)))
(cons 1 b))
;;; M-eval value:
(1 2 . 3)

2.11 Oefening: or

Pas de evaluator aan zodat de evaluator een or-expressie kan evalueren. Doe dit opnieuw als speciale vorm en als een afgeleide expressie.

> (or false true true)
;;; M-eval value:
#t
> (or)
;;; M-eval value:
#f
> (or false false false)
;;; M-eval value:
#f
> (or false 123 false)
;;; M-eval value:
123

2.12 Oefening: omgevingen

Ga na hoe de evaluator omgevingen beheert. Trace daarom doorheen de broncode van de evaluator wat er gebeurt wanneer volgende expressies uitgevoerd worden. Teken de omgevingsdiagrammen, procedure-objecten, etc. die onderweg aangemaakt worden.

Merk op: De expressies evalueren niet noodzakelijk naar een oplossing.

(define x 4)
(set! x 4)
((lambda (x)
   (define (f a b)
     (+ a b b))

   (define (g x)
     (let ((y (+ x 1)))
       (f x y)))

   (g x))
123)
(let ((a 1)
(b (* a 2)))
b)
(let* ((a 1)
(b (* a 2)))
b)
(define (f n)
  (define (g m)
    (f (+ m 1)))
  (g n))

(f 1)
(define (h)
       (define (i n)
         (j n))
       (define (j m)
         (i (+ m 1)))
       (i 2))

     (h)

3 De analyzing evaluator

Deze laatste oefeningen behandelen de analyzing meta-circulaire evaluator uit hoofdstuk 4.1.7 van Structure and Interpretation of Computer Programs. Dit is een alternatief op de meta-circulaire evaluator die de analyse van de syntax ontkoppelt van de uitvoering van het programma. Deze evaluator start je door het bestand "icp_2_aeval.scm" te evalueren in DrRacket.

3.1 Verschil in uitvoertijd ten gevolge van analyse

Ga na welk van de volgende expressies sneller uitvoeren in de analyzing evaluator:

(+ 1 2 3)
(define (fac n) (if (> n 1) (* n (fac (- n 1))) 1))
(define (fac n) (if (> n 1) (* n (fac (- n 1))) 1))
(fac 500)
(lambda (n) (make-list n map))
(let ((x 50))
  (until (> x 40)
         (dhcp-renew)
         ((default-gateway) 'send x)
         (set! x (* x 5))
         (display "Looping...\n")))

3.2 Stapels van evaluatoren

Wanneer we de analyzing evaluator uitvoeren bovenop de DrRacket evaluator, kan tijd bespaard worden wanneer expressies herhaaldelijk uitgevoerd worden. Net als de ’gewone’ meta-circulaire evaluator, is de analyzing evaluator echter meta-circulair. Dit houdt in dat het mogelijk moet zijn om de analyzing evaluator uit te voeren binnen een analyzing evaluator die op zijn beurt binnen bv. de DrRacket evaluator uitvoert (of, natuurlijk, opnieuw binnen een analyzing evaluator. Of binnen een meval).

Beredeneer of het uitvoeren van een meta-circulaire evaluator binnen een analyzing evaluator (a.a) sneller kan zijn dan het uitvoeren van diezelfde meta-circulaire evaluator binnen een niet-analyzing evaluator (a.b).

Beredeneer of het uitvoeren van een analyzing evaluator binnen een meta-circulaire evaluator (dus niet bv. rechtstreeks binnen DrRacket, b.a) sneller kan zijn dan het uitvoeren van een niet-analyzing evaluator binnen diezelfde meta-circulaire evaluator (b.b).

Beredeneer vervolgens of de situatie in c.a sneller kan zijn dan die in c.b, en of deze sneller kan zijn dan deze in c.c.

Een stapel van meta-circulaire evaluatoren

3.3 Fractie van uitvoertijd gespendeerd aan analyse

Gebruik bv. de time procedure ((#%require (only racket/base time))) om na te gaan hoeveel tijd er gespendeerd wordt aan de syntactische analyze, t.o.v. aan de uitvoering van expressies.

1	Soorten expressies
2	Uitbreiden van de evaluator
3	De analyzing evaluator