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.

De verschillende soorten expressies worden door de functie eval onderscheiden. De grote cond-expressie zorgt er voor dat de juiste evaluatie strategie wordt toegepast.

De meeste expressies worden intern voorgesteld als een door een tag gekwalificeerde lijst. false wordt voorgesteld door de onderliggende Scheme-#false, terwijl eender welke van false verschillende expressie als true beschouwd wordt. Getallen en tekenreeksen zijn zelf-evaluerend. Een quotatie is intern geïmplementeerd als een lijst gekwalificeerd door de tag quote. Symbolen stellen intern variabelen voor.

Voor de interne representatie van elke expressie bestaan er abstracte datastructuren waarvan de encapsulatie niet doorbroken mag worden in je uitbreidingen van de meta-circulaire evaluator.

1.2 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:

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 Uitbreiden van de evaluator

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: Extra primitieven

> (define primitive-procedures   (list (list 'car car)         (list 'cdr cdr)         (list 'cons cons)         (list 'null? null?)         (list '* *)         (list '/ /)         (list '= =)         (list 'list list)         (list '+ +)         (list '- -)         (list '< <)         (list '> >)              (list 'pair?          pair?)           (list 'display        display)           (list 'newline        newline)           (list 'number->string 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.2 Oefening: and als special form

Implementeer dit.

In de and-tak van de eval-procedure moet nu de specifieke eval-and-procedure opgeroepen worden:

...

((and? exp) (eval-and exp env))

...

Waarbij eval-and als volgt gedefinieerd is:

(define (eval-and exp env)

(define (aux conjuncts)

(if (null? (cdr conjuncts))

(eval (car conjuncts) env)

(if (true? (eval (car conjuncts) env))

(aux (cdr conjuncts))

false)))

(if (null? (cdr exp))

true

(aux (cdr exp))))

2.3 Oefening: and als afgeleide expressie

Implementeer nu deze manier.

In de and-tak van de eval-procedure moet nu de vertaal procedure and->if opgeroepen worden en de nieuwe expressie moet worden geevalueerd:

> (define (eval exp env)     (cond ((self-evaluating? exp) exp)           ((variable? exp) (lookup-variable-value exp env))           ((quoted? exp) (text-of-quotation exp))           ((assignment? exp) (eval-assignment exp env))           ((definition? exp) (eval-definition exp env))           ((if? exp) (eval-if exp env))           ((lambda? exp)(make-procedure (lambda-parameters exp)                                         (lambda-body exp)                                         env))           ((begin? exp)            (eval-sequence (begin-actions exp) env))           ((cond? exp) (eval (cond->if exp) env))           ((and? exp) (eval (and->if exp) env))           ((application? exp)            (apply (eval (operator exp) env)                   (list-of-values (operands exp) env)))           (else            (error "Unknown expression type -- eval" exp))))

Waarbij and->if als volgt gedefinieerd is:

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

> (define (and-args->if exps)     (cond       ((null? exps)'true)       ((null? (cdr exps))(car exps))       (else (make-if (car exps)                      (and-args->if (cdr exps))                      'false))))

> (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

2.4 Oefening: or als afgeleide expressie

Pas de evaluator aan zodat de evaluator een or-expressie kan evalueren. Doe dit eerste als afgeleide expressie.

> (define (or? exp) (tagged-list? exp 'or))

> (define or-args cdr)

> (define (eval-or exp env)       (define (evaluate-arguments args)         (if (null? args)             false             (let ((res (eval (car args) env)))               (if (true? res)                   res                   (evaluate-arguments (cdr args))))))     (evaluate-arguments (or-args exp)))

> (define (eval exp env)     (cond ((self-evaluating? exp) exp)           ((variable? exp) (lookup-variable-value exp env))           ((quoted? exp) (text-of-quotation exp))           ((assignment? exp) (eval-assignment exp env))           ((definition? exp) (eval-definition exp env))           ((if? exp) (eval-if exp env))           ((lambda? exp)(make-procedure (lambda-parameters exp)                                         (lambda-body exp)                                         env))           ((begin? exp)            (eval-sequence (begin-actions exp) env))           ((cond? exp) (eval (cond->if exp) env))           ((and? exp) (eval (and->if exp) env))              ((or? exp) (eval-or exp env))              ((application? exp)            (apply (eval (operator exp) env)                   (list-of-values (operands exp) env)))           (else            (error "Unknown expression type -- eval" exp))))

> (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.5 Oefening: or als special form

Doe nu hetzelfde, maar met or als special form.

> (define (or? exp) (tagged-list? exp 'or))

> (define or-args cdr)

> (define (eval exp env)     (cond ((self-evaluating? exp) exp)           ((variable? exp) (lookup-variable-value exp env))           ((quoted? exp) (text-of-quotation exp))           ((assignment? exp) (eval-assignment exp env))           ((definition? exp) (eval-definition exp env))           ((if? exp) (eval-if exp env))           ((lambda? exp)(make-procedure (lambda-parameters exp)                                         (lambda-body exp)                                         env))           ((begin? exp)            (eval-sequence (begin-actions exp) env))           ((cond? exp) (eval (cond->if exp) env))           ((and? exp) (eval (and->if exp) env))           ((let? exp) (eval (let->applied-lambda exp) env))           ((let*? exp) (eval-let* exp env))              ((or? exp) (eval (or->if exp) env))              ((application? exp)            (apply (eval (operator exp) env)                   (list-of-values (operands exp) env)))           (else            (error "Unknown expression type -- eval" exp))))

Of:

> (define (or->if exp)   (if (null? (cdr exp))       'false       (or-args->if (cdr exp))))

> (define (or-args->if exps)     (if (null? exps)           'false           (let ((res (car exps))                 (rest (cdr exps)))             (make-if res                      res                      (or-args->if rest)))))

Zodat:

> (or->if '(or (< 1 2) true false (> 14 2)))

(if (< 1 2) (< 1 2) (if true true (if false false (if (> 14 2) (> 14 2) false))))

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 (let? exp)     (tagged-list? exp 'let))

> (define (let-var-val-list exp)     (cadr exp))

> (define (let-vars exp)     (map car (let-var-val-list exp)))

> (define (let-vals exp)     (map cadr (let-var-val-list exp)))

> (define (let-body exp)     (cddr exp))

(define (eval-let exp env)

...)

> (define (eval-let exp env)     (eval-sequence (let-body exp)                    (extend-environment                     (let-vars exp)                     (list-of-values (let-vals exp) env)                     env)))

> (define (eval exp env)     (cond ((self-evaluating? exp) exp)           ((variable? exp) (lookup-variable-value exp env))           ((quoted? exp) (text-of-quotation exp))           ((assignment? exp) (eval-assignment exp env))           ((definition? exp) (eval-definition exp env))           ((if? exp) (eval-if exp env))           ((lambda? exp)(make-procedure (lambda-parameters exp)                                         (lambda-body exp)                                         env))           ((begin? exp)            (eval-sequence (begin-actions exp) env))           ((cond? exp) (eval (cond->if exp) env))           ((and? exp) (eval-and exp env))              ((let? exp) (eval-let exp env))              ((application? exp)            (apply (eval (operator exp) env)                   (list-of-values (operands exp) env)))           (else            (error "Unknown expression type -- eval" exp))))

(define (let->applied-lambda exp)

...)

> (define (make-application procedure arguments)     (cons procedure arguments))

> (define (let->applied-lambda exp)     (make-application (make-lambda (let-vars exp) (let-body exp))                       (let-vals exp)))

> (define (eval exp env)     (cond ((self-evaluating? exp) exp)           ((variable? exp) (lookup-variable-value exp env))           ((quoted? exp) (text-of-quotation exp))           ((assignment? exp) (eval-assignment exp env))           ((definition? exp) (eval-definition exp env))           ((if? exp) (eval-if exp env))           ((lambda? exp)(make-procedure (lambda-parameters exp)                                         (lambda-body exp)                                         env))           ((begin? exp)            (eval-sequence (begin-actions exp) env))           ((cond? exp) (eval (cond->if exp) env))           ((and? exp) (eval (and->if exp) env))              ((let? exp) (eval (let->applied-lambda exp) env))              ((application? exp)            (apply (eval (operator exp) env)                   (list-of-values (operands exp) env)))           (else            (error "Unknown expression type -- eval" 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.

> (define (make-application procedure arguments)     (cons procedure arguments))

> (define (let->applied-lambda exp)     (make-application (make-lambda (let-vars exp) (let-body exp))                       (let-vals exp)))

> (define (eval exp env)     (cond ((self-evaluating? exp) exp)           ((variable? exp) (lookup-variable-value exp env))           ((quoted? exp) (text-of-quotation exp))           ((assignment? exp) (eval-assignment exp env))           ((definition? exp) (eval-definition exp env))           ((if? exp) (eval-if exp env))           ((lambda? exp)(make-procedure (lambda-parameters exp)                                         (lambda-body exp)                                         env))           ((begin? exp)            (eval-sequence (begin-actions exp) env))           ((cond? exp) (eval (cond->if exp) env))           ((and? exp) (eval (and->if exp) env))           ((let? exp) (eval (let->applied-lambda exp) env))              ((let*? exp) (eval (let*->lets exp) env))              ((application? exp)            (apply (eval (operator exp) env)                   (list-of-values (operands exp) env)))           (else            (error "Unknown expression type -- eval" exp))))

> (define (let*? exp)     (tagged-list? exp 'let*))

> (define let*-var-val-list cadr)

> (define let*-body cddr)

> (define (make-let var-val-list body)     (cons 'let (cons var-val-list body)))

> (define (let*->lets exp)     (let loop ((var-val-list (let*-var-val-list exp)))       (if (or (null? var-val-list)(null? (cdr var-val-list)))           (make-let var-val-list (let*-body exp))           (make-let (list (car var-val-list)) (list (loop (cdr var-val-list)))))))

Zodat een let*-expressie alsvolgt wordt vertaald:

> (let*->lets '(let* ((a 3)                       (b (cons 2 a)))                  (cons 1 b)))

(let ((a 3)) (let ((b (cons 2 a))) (cons 1 b)))

> (let* ((a 3)          (b (cons 2 a)))     (cons 1 b))

;;; M-eval value: (1 2 . 3)

2.8 Oefening: let* als speciale vorm

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

> (define (eval exp env)     (cond ((self-evaluating? exp) exp)           ((variable? exp) (lookup-variable-value exp env))           ((quoted? exp) (text-of-quotation exp))           ((assignment? exp) (eval-assignment exp env))           ((definition? exp) (eval-definition exp env))           ((if? exp) (eval-if exp env))           ((lambda? exp)(make-procedure (lambda-parameters exp)                                         (lambda-body exp)                                         env))           ((begin? exp)            (eval-sequence (begin-actions exp) env))           ((cond? exp) (eval (cond->if exp) env))           ((and? exp) (eval (and->if exp) env))           ((let? exp) (eval (let->applied-lambda exp) env))              ((let*? exp) (eval-let* exp env))              ((application? exp)            (apply (eval (operator exp) env)                   (list-of-values (operands exp) env)))           (else            (error "Unknown expression type -- eval" exp))))

> (define (eval-let* exp env)     (eval-sequence (let*-body exp)                    (extend-environment*                     env                     (let*-var-val-list exp))))

> (define (extend-environment* env var-val-list)     (if (null? var-val-list)         env         (let ((var (caar var-val-list))               (val (cadar var-val-list)))         (extend-environment* (extend-environment (list var)                                                  (list (eval val env))                                                  env)                              (cdr var-val-list)))))

> (let* ((a 3)          (b (cons 2 a)))     (cons 1 b))

;;; M-eval value: (1 2 . 3)

2.9 Oefening: map

Schrijf zelf een hogere-orde my-map-functie en test deze uit in de meta-circulaire evaluator. Onderstaande interactie licht dit toe:

> (my-map (lambda (x) (cons x x)) '(1 2 3))

((1 . 1) (2 . 2) (3 . 3))

> (define (my-map f lst)     (if (null? lst)         '()         (cons (f (car lst))               (my-map f (cdr lst)))))

;;; M-eval value: ok

> (my-map (lambda (x) (cons x x)) '(1 2 3))

;;; M-eval value: ((1 . 1) (2 . 2) (3 . 3))

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.

> (define primitive-procedures     (list (list 'car car)           (list 'cdr cdr)           (list 'cons cons)           (list 'null? null?)           (list 'pair? pair?)           (list 'display display)           (list 'newline newline)           (list 'number->string number->string)              (list 'map map)))

Wat gebeurt er als je deze map uittest? Verklaar.

> (map (lambda (x) (cons x x)) '(1 2 3))

application: not a procedure;

expected a procedure that can be applied to arguments

given: (mcons 'procedure (mcons (mcons 'x '()) (mcons

(mcons (mcons 'cons (mcons 'x (mcons 'x '()))) '()) (mcons

(mcons (mcons (mcons 'false (mcons 'true (mcons 'car (mcons

'cdr (mcons 'cons (mcons 'null? (mcons 'pair? (mcons

'display (mcons 'newline (mcons 'n...

De meta-circulaire evaluator vertrouwt voor de evaluatie van deze applicatie namelijk op de map uit de onderliggende Scheme-omgeving. Zoals je kan afleiden uit de foutmelding, representeert de meta-circulaire evaluator procedures intern echter aan de hand van door een procedure-tag gekwalificeerde lijst gevolgd door parameters, body en de environment. Deze voorstelling is uiteraard incompatibel met de voorstelling die DrRacket verwacht als eerste argument voor een map-applicatie.

2.10 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.

De oplossing bestaat uit een reeks diagrammen. Merk op dat we, hoewel we een diagram van de omgevingen aan het maken zijn, geen "omgevingsdiagram" zoals bij Structuur 1 meer aan het maken zijn. In plaats daarvan hebben we hier te maken met een hele boom cons-cellen. Om zeker te zijn dat er geen verwarring is beschrijf ik hier nog eens expliciet de notatie-conventies: een cons-cel wordt weergegeven door twee vierkantjes die tegen elkaar geplakt zijn. Één van beide vierkanten is de car, het andere vierkant is de cdr. In zowel de car als de cdr staat een bolletje van waaruit een pijl vertrekt. Die pijl wijst naar wat ’in’ de car of cdr ’zit’. Dit kan een cijfer zijn, een symbool, een ingebouwde (DrRacket-) procedure zoals "#<procedure:+>", een cons-cel of een lijst van symbolen en cijfers.

Weet dat zo’n gequote lijst eigenlijk gewoon meer cons-cellen zijn; ik schrijf ze enkel verkort op als het mij lijkt dat het jullie alleen maar méér gaat verwarren om nog meer cons-cellen te tekenen. Cruciaal is echter dat in Scheme zo’n pijl niet kan wijzen naar een car of een cdr van een cons-cel: als de pijl naar een cons-cel wijst, wijst die altijd naar de gehele cons-cel, zelfs als de pijl in het diagram toekomt in de car of de cdr.

Sommige cons-cellen in de diagrammen hebben een kleur. Die kleur betekent natuurlijk niets voor Scheme; en wordt enkel gebruikt om het diagram voor jullie overzichtelijker te maken. Deze legende verklaart hoe de kleuren gebruikt worden:

De kleuren hebben natuurlijk geen invloed op de betekenis of op het gedrag. Om het verschil tussen de "omgevingen" en "frames" enerzijds, en het verschil tussen de verschillende omgevingen anderzijds, zo duidelijk mogelijk te maken, worden alle cellen die bij één omgeving horen, omvat door een lichtblauwe kader. Alle cellen die bij één frame horen, worden omgeven door een lichtrode kader.

Initieel, voordat de eerste expressie hieronder uitgevoerd wordt, ziet de globale omgeving er dus zo uit:

1. (define x 4)

   Een definitie voegt een nieuwe binding toe in de huidige omgeving. Voor een top-level definitie wordt een nieuwe binding in de globale omgeving toegevoegd.

   Het volledige diagram ziet er dan als volgt uit:

   

2. (set! x 4)

   Een assignment wijzigt een bestaande binding. De waarde van x wordt dus vervangen van 4 naar... opnieuw 4.

   Het volledige diagram ziet er dan als volgt uit:

   

3. ((lambda (x)

   (define (f a b)

   (+ a b b))

   (define (g x)

   (let ((y (+ x 1)))

   (f x y)))

   (g x))

   123)

   De video-opname op Panopto besprekt deze derde expressie gedetailleerd. Het volledige diagram ziet er dan als volgt uit:

4. (let ((a 1)

   (b (* a 2)))

   b)

   In deze let-expressie staat natuurlijk een fout: a is niet gebonden in de omgeving waarin de expressie voor b uitgerekend wordt. Dat zou zeer concreet moeten geworden zijn wanneer je de stappen zette om de omgevingen te maken: de huidige omgeving bij die expressie is nl. de globale omgeving. Daar staat intussen sinds expressie 1 ook een x in, maar geen a.

   We kunnen wel uittekenen hoe de omgevingen er uit hadden gezien, moest de waarde van b berekend kunnen worden:

   

5. (let* ((a 1)

   (b (* a 2)))

   b)

   Bij een let* kan iets equivalent natuurlijk wél: a wordt gebonden in een nieuwe omgeving, en die omgeving wordt als huidige omgeving gebruikt bij het uitrekenen van de expressie voor b.

   De boom van cons-cellen waarmee de omgevingen bijgehouden worden, zien er bijgevolg als volgt uit:

   

6. (define (f n)

   (define (g m)

   (f (+ m 1)))

   (g n))

   (f 1)

   Bij deze 6e expressie roepen twee procedures elkaar recursief aan in een oneindige lus. Dit programma stopt dan ook nooit. Toch kan je nagaan hoe de omgevingen geconstrueerd worden bij de evaluatie van dit programma.

   De procedure-definitie van f zorgt er voor dat een nieuw procedure-object gebonden wordt in de globale omgeving. De omliggende omgeving van die procedure, d.w.z. de lexicale scope van f, is natuurlijk de globale omgeving zelf. Na de definitie van f worden de omgevingen dus als volgt voorgesteld:

   

   Voor de aanroep van (f 1) wordt een nieuwe omgeving aangemaakt, die als parent omgeving de omliggende omgeving gebruikt van het procedure-objecte gebonden aan f. Dat ziet er dan zo uit:

   

   Wanneer in de body van f de aanroep (g n) uitgevoerd wordt, groeit het omgevingsmodel als volgt:

   

   Merk op dat de nieuwe omgeving een child-omgeving is van de omgeving van de oproep van (f 1): het procedure-object gebonden aan variabele g heeft als omliggende omgeving nl. die omgeving van de oproep van (f 1) bijgehouden.

   Wanneer in de body van g dan een recursieve oproep naar f gebeurt, groeit de boom van cons-cellen verder. In een lus worden telkens nieuwe omgevingen voor aanroepen van f en g aangemaakt. Merk op: die eerste soort omgevingen zijn telkens child-omgevingen van de globale omgeving; die tweede soort omgevingen zijn telkens child-omgevingen van een omgeving van de aanroep van f.

   Na twee iteraties door de lus ziet het diagram er bv. als volgt uit:

7. (define (h)

   (define (i n)

   (j n))

   (define (j m)

   (i (+ m 1)))

   (i 2))

   (h)

   Deze expressie is heel gelijkaardig, maar ook substantieel verschillend van de vorige. Nadat de definitie van h voltooid is, (h) aangeroepen is, en de definities van i en j in de body voltooid zijn, worden de omgevingen als volgt voorgesteld:

   

   Daarna begint de lus. Het verschil in gedrag t.o.v. expressie 6, zit zich voornamelijk in de pijlen ’terug naar boven’ naar de parent-omgevingen vergelijk bv. dit diagram van de situatie na twee iteraties:

   

2.11 Oefening: tab (examenoefening)

Breid de meta-circulaire evaluator uit met ondersteuning voor zogenaamde tab expressies. De syntax van deze expressies is als volgt: (tab <size-exp> <filler-exp>)

Zulk een tab expressie evalueert naar een nieuwe vector. Hiertoe neemt zij als eerste argument een expressie die eenmaal geëvalueerd wordt om de grootte van de aan te maken vector te bekomen. Om de elementen van de vector op te vullen, neemt zij als tweede argument een expressie. Deze expressie wordt meermaals geëvalueerd; één evaluatie per element van de vector (van links naar rechts). Volgend transcript licht het gebruik van tab verder toe:

De volgende procedures laten toe om tab en inc te herkennen en te ontleden. Zorg er daarbij ook zeker voor dat + in de lijst van primitieve procedures staat:

> (define (tab? exp)   (tagged-list? exp 'tab))

> (define (tab-size exp)     (cadr exp))

> (define (tab-generator exp)     (caddr exp))

> (define (eval-tab expr env)     (let ((size (eval (tab-size expr) env)))       (define (fill-vector-loop v i)         (if (< i size)             (begin               (vector-set! v i  (eval (tab-generator expr) env))               (fill-vector-loop v (+ i 1))))         v)       (fill-vector-loop (make-vector size) 0)))

> (define (inc? exp) (tagged-list? exp 'inc))

> (define inc-var-name cadr)

> (define (inc->begin exp)       `(begin (set! ,(inc-var-name exp) (+ 1 ,(inc-var-name exp)))               ,(inc-var-name exp)))

> (define primitive-procedures    (list (list 'car car)          (list 'cdr cdr)          (list 'cons cons)          (list 'null? null?)          (list '* *)          (list '/ /)          (list '= =)          (list 'list list)          (list 'display display)          (list 'newline newline)          (list '+ +)))

Vervolgens moeten we eval uitbreiden:

> (define (eval exp env)     (cond ((self-evaluating? exp) exp)           ((variable? exp) (lookup-variable-value exp env))           ((quoted? exp) (text-of-quotation exp))           ((assignment? exp) (eval-assignment exp env))           ((definition? exp) (eval-definition exp env))           ((if? exp) (eval-if exp env))           ((lambda? exp)(make-procedure (lambda-parameters exp)                                         (lambda-body exp)                                         env))           ((begin? exp)            (eval-sequence (begin-actions exp) env))           ((cond? exp) (eval (cond->if exp) env))           ((and? exp) (eval (and->if exp) env))           ((let? exp) (eval (let->applied-lambda exp) env))           ((let*? exp) (eval (let*->lets exp) env))              ((tab? exp) (eval-tab exp env))           ((inc? exp) (eval (inc->begin exp) env))              ((application? exp)            (apply (eval (operator exp) env)                   (list-of-values (operands exp) env)))           (else            (error "Unknown expression type -- eval" exp))))

> (define x 5)

;;; M-eval value: ok

> (tab 3 (begin (set! x (+ x 1)) x))

;;; M-eval value: #(6 7 8)

> x

;;; M-eval value: 8

Breid nu de meta-circulaire evaluator uit met ondersteuning voor zogenaamde inc (“increment”) expressies. De syntax van deze expressies is als volgt: (inc <var-name>).

Zulk een inc expressie neemt als enige argument een aan een getal gebonden variabele, verhoogt hiervan destructief de waarde met 1, en geeft de nieuwe waarde van de variabele terug.

Volgend transcript volgt op het vorige en licht het gebruik van inc verder toe:

> (inc x)

;;; M-eval value: 9

> (tab 4 (inc x))

;;; M-eval value: #(10 11 12 13)

Implementeer inc als een afgeleide expressie a.d.h.v een procedure inc->begin.

2.12 Oefening: freeze (examenoefening)

Voeg aan de meta-circulaire evaluator van Scheme de special form freeze toe a.d.h.v. een predikaat freeze? en een procedure eval-freeze?. Als je deze operatie toepast op een variabele, wordt het onmogelijk om die variabele destructief aan te passen. Bijvoorbeeld, na een (freeze a) op een bestaande variabele a krijg je een foutmelding bij (set! a 42).

Let op dat de scoping regels gerespecteerd blijven; het volgende voorbeeld mag geen fout melden.

> (define (freeze? exp)   (tagged-list? exp 'freeze))

> (define (eval-freeze exp env)   (let ((var (cadr exp)))   (freeze-variable! var env)   'done))

> (define (freeze-variable! var env)   (define (env-loop env)   (define (scan vars frozen?s)   (cond ((null? vars)          (env-loop (enclosing-environment env)))    ((eq? var (car vars))     (set-car! frozen?s #t))    (else (scan (cdr vars) (cdr frozen?s)))))   (if (eq? env the-empty-environment)       (error "Unbound variable -- FREEZE!" var)       (let ((frame (first-frame env)))   (scan (frame-variables frame)         (frame-frozen?s frame)))))   (env-loop env))

> (define (make-frame variables values)        (vector variables             values             (map (lambda (any) #f) values)))

> (define (frame-variables frame) (vector-ref frame 0))

> (define (frame-values frame) (vector-ref frame 1))

> (define (frame-frozen?s frame) (vector-ref frame 2))

> (define (add-binding-to-frame! var val frame)     (vector-set! frame 0 (cons var (frame-variables frame)))     (vector-set! frame 1 (cons val (frame-values frame)))        (vector-set! frame 2 (cons #f (frame-frozen?s frame))))

> (define (set-variable-value! var val env)    (define (env-loop env)     (define (scan vars vals frozen?s)      (cond ((null? vars)             (env-loop (enclosing-environment env)))       ((eq? var (car vars))        (if (car frozen?s)         (error "Trying to assign a frozen variable -- SET!" var)         (set-car! vals val)))       (else (scan (cdr vars) (cdr vals) (cdr frozen?s)))))     (if (eq? env the-empty-environment)      (error "Unbound variable -- SET!" var)      (let ((frame (first-frame env)))       (scan (frame-variables frame)        (frame-values frame)        (frame-frozen?s frame)))))    (env-loop env))

Vervolgens moeten we eval uitbreiden:

> (define (eval exp env)     (cond ((self-evaluating? exp) exp)           ((variable? exp) (lookup-variable-value exp env))           ((quoted? exp) (text-of-quotation exp))           ((assignment? exp) (eval-assignment exp env))           ((definition? exp) (eval-definition exp env))           ((if? exp) (eval-if exp env))           ((lambda? exp)(make-procedure (lambda-parameters exp)                                         (lambda-body exp)                                         env))           ((begin? exp)            (eval-sequence (begin-actions exp) env))           ((cond? exp) (eval (cond->if exp) env))           ((and? exp) (eval (and->if exp) env))           ((let? exp) (eval (let->applied-lambda exp) env))           ((let*? exp) (eval (let*->lets exp) env))              ((freeze? exp) (eval-freeze exp env))                 ((application? exp)            (apply (eval (operator exp) env)                   (list-of-values (operands exp) env)))           (else            (error "Unknown expression type -- eval" exp))))