1. Arithmetic calculator 6 (define (eval exp) 8 ((number? exp) exp) ((sum? exp (eval-sum exp)) 10 (el (error unknown expression exp)))) 12 13(define (eval exp) (+(eval (cadr exp))(eval (caddr exp)))) 16 17(eva1'(p1us*24(p1us*56)))
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 1. Arithmetic calculator (define (tag-check e sym) (and (pair? e) (eq? (car e) sym))) (define (sum? e) (tag-check e 'plus*)) (define (eval exp) (cond ((number? exp) exp) ((sum? exp) (eval-sum exp)) (else (error "unknown expression " exp)))) (define (eval-sum exp) (+ (eval (cadr exp)) (eval (caddr exp)))) (eval '(plus* 24 (plus* 5 6)))
2. Names 3(define (define? exp)(tag-check exp 'define*)) 5 (define (eval exp) (cond ((number? exp)exp ((sum? exp) 789012345 (eval-sum exp)) ((symbol? exp)(lookup exp) ((define? exp)(eval-define exp)) (error unknown expression exp)))) 14 variation on table Adt from March 2 lecture (only difference is 15 i that table-get returns a binding, while original version 16 returned a value) make-table void -> table 18 i table-get table, symbol ->(binding I null table-put! table, symbol, anytype - undef 20 i binding-value binding -> anytype 22(define environment (make-table)) 24 (define (lookup name) (let ((bind (table-get environment name))) (if (null? binding) (error "unbound variable: name) (binding-value binding))) 8901234 (define (eval-define exp (let ((name (cadr exp)) (defined-to-be (cadd exp))) (table-put! environment name (eval defined-to-be)) undefined)) 36 (eval (define* x* (plus*4 5))) 37(eva1'(P1u8*x*2)) 89042345 Index to procedures that have not changed procedure page eval-sum 13
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 2. Names (define (define? exp) (tag-check exp 'define*)) (define (eval exp) (cond ((number? exp) exp) ((sum? exp) (eval-sum exp)) ((symbol? exp) (lookup exp)) ((define? exp) (eval-define exp)) (else (error "unknown expression " exp)))) ; variation on table ADT from March 2 lecture (only difference is ; that table-get returns a binding, while original version ; returned a value): ; make-table void -> table ; table-get table, symbol -> (binding | null) ; table-put! table, symbol, anytype -> undef ; binding-value binding -> anytype (define environment (make-table)) (define (lookup name) (let ((binding (table-get environment name))) (if (null? binding) (error "unbound variable: " name) (binding-value binding)))) (define (eval-define exp) (let ((name (cadr exp)) (defined-to-be (caddr exp))) (table-put! environment name (eval defined-to-be)) 'undefined)) (eval '(define* x* (plus* 4 5))) (eval '(plus* x* 2)) ; Index to procedures that have not changed: ; procedure page line ; sum? 1 4 ; eval-sum 1 13
3. Conditionals and if 3(define (greater? exp)(tag-check exp ' greater*)) 4 (define (if? exp (tag-check exp 'if*)) (define (eval exp) (cond 8 ((number? exp) exp) ((sum? (eval-sum exp)) ((symbol? exp) (lookup exp)) 01234 (define? )(eval-define exp ((greater? exp)(eval-greater exp)) ((if? exp) (eval-if exp)) (else (error unknown expression exp))) 56789 (define (eval-greater exp) ((eval (cadr exp))(eval (caddr exp)))) 20 (define (eval-if exp) (let ((predicate (cadr exp)) (consequent (caddr exp)) 23456 (alternative (cadddr exp))) fs ((test (eval predicate))) (let ((eq? test #t) (eval consequent) ((eg? test #f) (eval alternative) (else (error "predicate not a conditional: dicate)))))) 31 (eval (define* y* 9)) 5)) 35 i Index to procedures that have not changed 36 procedure page line sum? eval-sum 1 13 lookup define? 2 3 42
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 3. Conditionals and if (define (greater? exp) (tag-check exp 'greater*)) (define (if? exp) (tag-check exp 'if*)) (define (eval exp) (cond ((number? exp) exp) ((sum? exp) (eval-sum exp)) ((symbol? exp) (lookup exp)) ((define? exp) (eval-define exp)) ((greater? exp) (eval-greater exp)) ((if? exp) (eval-if exp)) (else (error "unknown expression " exp)))) (define (eval-greater exp) (> (eval (cadr exp)) (eval (caddr exp)))) (define (eval-if exp) (let ((predicate (cadr exp)) (consequent (caddr exp)) (alternative (cadddr exp))) (let ((test (eval predicate))) (cond ((eq? test #t) (eval consequent)) ((eq? test #f) (eval alternative)) (else (error "predicate not a conditional: " predicate)))))) (eval '(define* y* 9)) (eval '(if* (greater* y* 6) (plus* y* 2) 15)) ; Index to procedures that have not changed: ; procedure page line ; sum? 1 4 ; eval-sum 1 13 ; lookup 2 22 ; define? 2 3 ; eval-define 2 28
I 4. Store operators in the environment 3 (define (application? e) (pair? e)) 4 5 (define (eval exp) 6 7 ((number? exp) exp) 8 ((sym (lookup exp)) (define? exp) (eval-define exp)) 10 ((if? exp) (eval-if ((application? exp)(apply (eval (car exp) 12 (map eval (cdr exp)))) (else 14 (error unknown expression exp))) 16 ;i rename scheme's apply so we can reuse the name 17 (define scheme -applyapply) 18 19 (define (apply operator operands) (if (primitive? operator) apply (get-scheme-procedure operator) operands) (error "operator not a procedure: operator))) 24 ;i primitive: an ADT that stores scheme procedure 26 (define prim-tag ' primitive) 2g (define (make-primitive scheme-proc)(list prim-tag scheme -proc)) 28 (define (primitive? e) (tag-check e prim-tag) 9(define (get-scheme-procedure prim)(cadr prim) 03234 (define environment (make-table)) (table-put! environment ' plus* (make-primitive +) 33 (table-put! environment 'greater*(make-primitive >) (table-put! environment 'true*#t 36(eval '(define* z* 9)) (eva1'(p1us*96)) 38 (eval i(if* true* 10 15)) 41 Index to procedures that have not change procedure evaluator line lookup def eval-defi 2 28
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 4. Store operators in the environment (define (application? e) (pair? e)) (define (eval exp) (cond ((number? exp) exp) ((symbol? exp) (lookup exp)) ((define? exp) (eval-define exp)) ((if? exp) (eval-if exp)) ((application? exp) (apply (eval (car exp)) (map eval (cdr exp)))) (else (error "unknown expression " exp)))) ;; rename scheme’s apply so we can reuse the name (define scheme-apply apply) (define (apply operator operands) (if (primitive? operator) (scheme-apply (get-scheme-procedure operator) operands) (error "operator not a procedure: " operator))) ;; primitive: an ADT that stores scheme procedures (define prim-tag 'primitive) (define (make-primitive scheme-proc)(list prim-tag scheme-proc)) (define (primitive? e) (tag-check e prim-tag)) (define (get-scheme-procedure prim) (cadr prim)) (define environment (make-table)) (table-put! environment 'plus* (make-primitive +)) (table-put! environment 'greater* (make-primitive >)) (table-put! environment 'true* #t) (eval '(define* z* 9)) (eval '(plus* 9 6)) (eval '(if* true* 10 15)) ; Index to procedures that have not changed: ; procedure evaluator line ; ; lookup define? 2 2 22 3 ; eval-define 2 28 ; if? 3 4 ; eval-if 3 20
I 5. Environment as explicit parameter 2 3 This change is boring! Exactly the same functionality as #4. 5 (define (eval exp env (cond ((number? exp exp) (look (define? exp) (eval-define exp env)) 10 ((if? exp) (eval-if exp env)) ((application? exp)(apply (eval (car exp) env) (map (lambda (e)(eval 14 (else 15 (error unknown expression exp)) 16 17 (define (lookup name env) 18 (let ((binding (tal (if (null? binding) 20 unbound variable (binding-value binding)))) 23 (define (eval-define exp env) (let ((name (cadr exp)) adar eX (table-put! env name (eval defined-to-be env)) 29(define (eval-if exp env (let ((predicate (cadr exp) (consequent (caddr exp) (alternative (cadddr exp))) (let ((test (eval predicate env))) 0123436789042345678901 ((eq? test #t)(eval consequent env)) ((eq? test #f)(eval alternative env)) (else (error val not boolean: predicate)))))) (eval '(define* z*(plus* 4 5))environment (eval ' (if*(greater* z* 6)10 15)environment Index to procedures that have not changed procedure evaluator line define 3 pplication? 2344 3 apply
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 5. Environment as explicit parameter ;This change is boring! Exactly the same functionality as #4. (define (eval exp env) (cond ((number? exp) exp) ((symbol? exp) (lookup exp env)) ((define? exp) (eval-define exp env)) ((if? exp) (eval-if exp env)) ((application? exp) (apply (eval (car exp) env) (map (lambda (e) (eval e env)) (cdr exp)))) (else (error "unknown expression " exp)))) (define (lookup name env) (let ((binding (table-get env name))) (if (null? binding) (error "unbound variable: " name) (binding-value binding)))) (define (eval-define exp env) (let ((name (cadr exp)) (defined-to-be (caddr exp))) (table-put! env name (eval defined-to-be env)) 'undefined)) (define (eval-if exp env) (let ((predicate (cadr exp)) (consequent (caddr exp)) (alternative (cadddr exp))) (let ((test (eval predicate env))) (cond ((eq? test #t) (eval consequent env)) ((eq? test #f) (eval alternative env)) (else (error "val not boolean: " predicate)))))) (eval '(define* z* (plus* 4 5)) environment) (eval '(if* (greater* z* 6) 10 15) environment) Index to procedures that have not changed: procedure define? evaluator 2 line 3 if? 3 4 application? apply 4 4 3 19