Reeks 7 : De Expliciete Controle-Evaluator
Deze oefeningenreeks behandelt de implementatie van de expliciete controle-evaluator, een vertaling naar een registermachine van de metacirculaire interpreter voor Scheme. In Structure and Interpretation of Computer Programs vind je deze in hoofdstuk 5.4. De code van de evaluator vind je in het bestand icp_7_eceval.scm.
1 Toevoegen van cond aan EC-Eval als afgeleide expressie
EC-Eval ondersteunt momenteel nog geen cond expressies:
;;; EC-Eval input: (define a 2) ;;; EC-Eval value: ok ;;; EC-Eval input: (cond ((= a 1) -1) ((= a 2) -2) (else 100)) ❌ Unbound variable cond
We zullen cond toevoegen aan EC-Eval als een afgeleide expressie. Om dit te verwezenlijken, werken we met een cond->if Scheme procedure. Deze werkt als volgt:
(cond->if '(cond ((= a 1) -1) ((= a 2) -2) (else 100))) > '(if (= a 1) (begin -1) (if (= a 2) (begin -2) (begin 100)))
(cond->if '(cond ((= a 1) -1) ((= a 2) -2))) > '(if (= a 1) (begin -1) (if (= a 2) (begin -2) 'ok))
Indien er geen else clausule is en geen enkele test evalueert naar true, dan geeft cond het symbool 'ok terug. Het implementeren van cond->if zou je ondertussen zelf reeds onder de knie moeten hebben. Om op de EC-Eval wijzigingen te focussen, wordt hier reeds een implementatie voorzien.
(define (cond-clauses cond) (cdr cond)) (define (clause-predicate clause) (car clause)) (define (clause-actions clause) (cdr clause)) (define (cond-else-clause? clause) (equal? (car clause) 'else)) (define (cond->if cond) (define (clauses->if clauses) (if (null? clauses) ''ok (let ((clause (car clauses)) (rest (cdr clauses))) (if (cond-else-clause? clause) (cons 'begin (clause-actions clause)) (list 'if (clause-predicate clause) (cons 'begin (clause-actions clause)) (clauses->if rest)))))) (clauses->if (cond-clauses cond)))
Hoe maak je een predicaat om cond-expressies te detecteren?
In welk register heeft de machine telkens de Scheme-expressie die wordt geëvalueerd?
Waar worden alle Scheme-procedures die in de registermachine gebruikt kunnen worden opgelijst?
Hoe detecteert de registermachine het type van de Scheme-expressie die zij aan het evalueren is?
2 Toevoegen van not aan EC-Eval
Voeg de not toe als een special form.
;;; EC-Eval input: (not 1) ;;; EC-Eval value: #f ;;; EC-Eval input: (not 0) ;;; EC-Eval value: #f ;;; EC-Eval input: (not true) ;;; EC-Eval value: #f ;;; EC-Eval input: (not false) ;;; EC-Eval value: #t
3 Toevoegen van and aan EC-Eval
Voeg and toe aan de EC-Eval als een special form. De and gedraagt zich als volgt.
;;; EC-Eval input: (and 1 2 3) ;;; EC-Eval value: #t ;;; EC-Eval input: (and 1 false 10) ;;; EC-Eval value: #f ;;; EC-Eval input: (and) ;;; EC-Eval value: #t ;;; EC-Eval input: (and 1 false (/ 1 0)) ;;; EC-Eval value: #f ;;; EC-Eval input: (and 1 true (/ 1 0)) ❌ Unbound variable /
4 Toevoegen van doto aan EC-Eval
Voeg doto toe aan de EC-Eval als special form. De syntax van deze expressie is als volgt.
(doto <exp> (<operator 1> <operand 11> ... <operand 1x>) ... (<operator n> <operand n1> ... <operand ny>))
Zulk een doto neemt een expressie <exp> als argument gevolgd door een aantal applicatie expressies. Bij evaluatie krijgt elk van de applicatie expressies het resultaat van de voorgaande expressie als extra, eerste, operand. Volgend transcript ligt het gebruik van doto toe.
(doto 5) 5 (doto 5 (+ 1)) 6 (doto 5 (+ 1) (* 2) (= 12)) #t
Merk op dat doto zelf evalueert naar het resultaat van de laatste applicatie expressie of naar <exp> indien er geen expressies zijn.
5 Toevoegen van tab aan EC-Eval
Voeg tab toe aan de EC-Eval als special form. De syntax van deze expressie 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:
;;; EC-Eval input: (define x 5) ;;; EC-Eval value: ok ;;; EC-Eval input: (tab 3 (begin (set! x (+ x 1)) x)) ;;; EC-Eval value: #(6 7 8) ;;; EC-Eval input: x ;;; EC-Eval value: 8
Implementeer tab als een special form.
Je gaat met een vector moeten werken in de registermachinecode. Je kan voor de gemakkelijkheid gewoon enkele vector operaties direct toevoegen aan de operaties.
We hebben best wat registers nodig. Voor jouw oplossing mag je unev en argl gebruiken hoe je wilt.
6 Toevoegen van let aan EC-Eval
Voeg let toe aan de EC-Eval als een special form. Voeg hiervoor eerst enkele Scheme functies toe waarmee je de verschillende syntactische delen van een let kan ontleden.
7 Toevoegen van cond aan EC-Eval als special form
Implementeer nu cond niet als een afgeleide expressie, maar als een special form. Dat wilt zeggen dat je de registermachine alle tests van de cond-clauses laat doorlopen tot een test naar true evalueert, of tot je een else-clause tegenkomt. Dan kun je de subroutine ev-sequence van de registermachine hergebruiken om de clause-actions evalueren.
Kijk voor inspiratie goed naar de implementatie van if en begin. Voeg om het jezelf makkelijker te maken de eerder geschreven procedures cond-clauses, clause-predicate, clause-actions en cond-else-clause? toe als operaties aan de registermachine.