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
6. Defining new procedures 3(define (lambda? e)(tag-check e 'lambda*)) 5 (define (eval exp env. (cond 789 ((number? exp exp (lookup exp env)) ((define? exp) (eval-define exp env)) ((if? exp) (eval-if exp env)) ((lambda? ex (eval-lambda exp env)) ((application? exp)(apply (eval (car exp) env) (map (lambda (e)(eval e env (cdr exp)))) (else 456789012 (error unknown expression exp))) (define (eval-lambda exp env) (let ((args (cadr exp)) (body (caddr exp))) (make-compound args body env))) 23 (define (apply operator operands) 24 (cond ((primitive? operator (scheme-apply (get-scheme -procedure operator 26 ((compound? operator) eval (body operator) (extend-env-with-new-frame 30 (parameters operator) 31 operands (env operator)))) (else (error operator not a procedure:operator)))) 36 38 ADt that implements the "double bubble" 40 (define compound-tag 'compound) 41 (define (make-compound parameters body en 42 (list compound-tag parameters body env) 43(define (compound? exp) (tag-check exp compound-tag)) 45 (define (parameters compound) (cadr compound) 46 (define (body compound) (cadd compound)) define (env compound) (cadddr compound))
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 6. Defining new procedures (define (lambda? e) (tag-check e 'lambda*)) (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)) ((lambda? exp) (eval-lambda exp env)) ((application? exp) (apply (eval (car exp) env) (map (lambda (e) (eval e env)) (cdr exp)))) (else (error "unknown expression " exp)))) (define (eval-lambda exp env) (let ((args (cadr exp)) (body (caddr exp))) (make-compound args body env))) (define (apply operator operands) (cond ((primitive? operator) (scheme-apply (get-scheme-procedure operator) operands)) ((compound? operator) (eval (body operator) (extend-env-with-new-frame (parameters operator) operands (env operator)))) (else (error "operator not a procedure: " operator)))) ;; ADT that implements the “double bubble” (define compound-tag 'compound) (define (make-compound parameters body env) (list compound-tag parameters body env)) (define (compound? exp) (tag-check exp compound-tag)) (define (parameters compound) (cadr compound)) (define (body compound) (caddr compound)) (define (env compound) (cadddr compound))
Environment model code(part of eval 6) 234567 Environment list (define (extend-env-with-new-frame names values env) (let ((new-frame (make-table))) (make-bindings! names values new-frame 8 c。 ns new- frame env))) 10(define (make-bindings! names values table) f。x-each (lambda (name value)(table-put! table name value) names values)) 456789022 the initial global environment (define GE (extend-env-with-new-frame (list 'plus* 'greater (list (make-primitive +)(make-primitive >) ni1)) lookup searches the list of frames for the first match (if (null? env) 26 (error "unbound variable: name) (let ((binding (table-get (car env) name))) (if (null? binding) lookup name (cdr env)) (binding 9012345678904 define changes the first frame in the envi (let ((name (cadr exp)) (defined-to-be (caddr exp))) (table-put! (car env) name (eval defined-to-be env)) undefined)) 40(eval (define* twice* (lambda*(x*)(plus* x*x*)))GE) (eval '(twice* 4)GE) 43 Index to procedures that have not changed: procedure evaluator line 45 2 47 eval-i
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 ; Environment model code (part of eval 6) ; Environment = list (define (extend-env-with-new-frame names values env) (let ((new-frame (make-table))) (make-bindings! names values new-frame) (cons new-frame env))) (define (make-bindings! names values table) (for-each (lambda (name value) (table-put! table name value)) names values)) ; the initial global environment (define GE (extend-env-with-new-frame (list 'plus* 'greater*) (list (make-primitive +) (make-primitive >)) nil)) ; lookup searches the list of frames for the first match (define (lookup name env) (if (null? env) (error "unbound variable: " name) (let ((binding (table-get (car env) name))) (if (null? binding) (lookup name (cdr env)) (binding-value binding))))) ; define changes the first frame in the environment (define (eval-define exp env) (let ((name (cadr exp)) (defined-to-be (caddr exp))) (table-put! (car env) name (eval defined-to-be env)) 'undefined)) (eval '(define* twice* (lambda* (x*) (plus* x* x*))) GE) (eval '(twice* 4) GE) Index to procedures that have not changed: procedure evaluator line define? 2 3 if? 3 4 application? 4 3 eval-i