1 ;; (define apply-in-underlying-scheme apply)
2 ;; (define eval-in-underlying-scheme eval)
3 
4 (define (eval exp env)
5   (cond ((self-evaluating? exp) exp)
6         ((variable? exp) (lookup-variable-value exp env))
7         ((quoted? exp) (text-of-quotation exp))
8         ((assignment? exp) (eval-assignment exp env))
9         ((definition? exp) (eval-definition exp env))
10         ((if? exp) (eval-if exp env))
11         ((lambda? exp)
12          (make-procedure (lambda-parameters exp)
13                          (lambda-body exp)
14                          env))
15         ((begin? exp) 
16          (eval-sequence (begin-actions exp) env))
17         ((cond? exp) (eval (cond->if exp) env))
18 	((let? exp) (eval (let->combination exp) env))
19         ((application? exp)
20          (apply (eval (operator exp) env)
21                 (list-of-values (operands exp) env)))
22         (else
23          (error "Unknown expression type -- EVAL" exp))))
24 
25 (define (apply procedure arguments)
26   (cond ((primitive-procedure? procedure)
27          (apply-primitive-procedure procedure arguments))
28         ((compound-procedure? procedure)
29          (eval-sequence
30            (procedure-body procedure)
31            (extend-environment
32              (procedure-parameters procedure)
33              arguments
34              (procedure-environment procedure))))
35         (else
36          (error
37           "Unknown procedure type -- APPLY" procedure))))
38 (define (list-of-values exps env)
39   (if (no-operands? exps)
40       '()
41       (cons (eval (first-operand exps) env)
42             (list-of-values (rest-operands exps) env))))
43 
44 (define (eval-if exp env)
45   (if (true? (eval (if-predicate exp) env))
46       (eval (if-consequent exp) env)
47       (eval (if-alternative exp) env)))
48 (define (eval-sequence exps env)
49   (cond ((last-exp? exps) (eval (first-exp exps) env))
50         (else (eval (first-exp exps) env)
51               (eval-sequence (rest-exps exps) env))))
52 (define (eval-assignment exp env)
53   (set-variable-value! (assignment-variable exp)
54                        (eval (assignment-value exp) env)
55                        env)
56   'ok)
57 (define (eval-definition exp env)
58   (define-variable! (definition-variable exp)
59                     (eval (definition-value exp) env)
60                     env)
61   'ok)
62 (define (self-evaluating? exp)
63   (cond ((number? exp) true)
64         ((string? exp) true)
65         (else false)))
66 (define (variable? exp) (symbol? exp))
67 (define (quoted? exp)
68   (tagged-list? exp 'quote))
69 
70 (define (text-of-quotation exp) (cadr exp))
71 (define (tagged-list? exp tag)
72   (if (pair? exp)
73       (eq? (car exp) tag)
74       false))
75 (define (assignment? exp)
76   (tagged-list? exp 'set!))
77 (define (assignment-variable exp) (cadr exp))
78 (define (assignment-value exp) (caddr exp))
79 (define (definition? exp)
80   (tagged-list? exp 'define))
81 (define (definition-variable exp)
82   (if (symbol? (cadr exp))
83       (cadr exp)
84       (caadr exp)))
85 (define (definition-value exp)
86   (if (symbol? (cadr exp))
87       (caddr exp)
88       (make-lambda (cdadr exp)   ; formal parameters
89                    (cddr exp)))) ; body
90 (define (lambda? exp) (tagged-list? exp 'lambda))
91 (define (lambda-parameters exp) (cadr exp))
92 (define (lambda-body exp) (cddr exp))
93 (define (make-lambda parameters body)
94   (cons 'lambda (cons parameters body)))
95 (define (if? exp) (tagged-list? exp 'if))
96 (define (if-predicate exp) (cadr exp))
97 (define (if-consequent exp) (caddr exp))
98 (define (if-alternative exp)
99   (if (not (null? (cdddr exp)))
100       (cadddr exp)
101       'false))
102 (define (make-if predicate consequent alternative)
103   (list 'if predicate consequent alternative))
104 (define (begin? exp) (tagged-list? exp 'begin))
105 (define (begin-actions exp) (cdr exp))
106 (define (last-exp? seq) (null? (cdr seq)))
107 (define (first-exp seq) (car seq))
108 (define (rest-exps seq) (cdr seq))
109 
110 (define (sequence->exp seq)
111   (cond ((null? seq) seq)
112         ((last-exp? seq) (first-exp seq))
113         (else (make-begin seq))))
114 (define (make-begin seq) (cons 'begin seq))
115 (define (application? exp) (pair? exp))
116 (define (operator exp) (car exp))
117 (define (operands exp) (cdr exp))
118 (define (no-operands? ops) (null? ops))
119 (define (first-operand ops) (car ops))
120 (define (rest-operands ops) (cdr ops))
121 (define (cond? exp) (tagged-list? exp 'cond))
122 (define (cond-clauses exp) (cdr exp))
123 (define (cond-else-clause? clause)
124   (eq? (cond-predicate clause) 'else))
125 (define (cond-predicate clause) (car clause))
126 (define (cond-actions clause) (cdr clause))
127 (define (cond->if exp)
128   (expand-clauses (cond-clauses exp)))
129 
130 (define (expand-clauses clauses)
131   (if (null? clauses)
132       'false                          ; no else clause
133       (let ((first (car clauses))
134             (rest (cdr clauses)))
135         (if (cond-else-clause? first)
136             (if (null? rest)
137                 (sequence->exp (cond-actions first))
138                 (error "ELSE clause isn't last -- COND->IF"
139                        clauses))
140             (make-if (cond-predicate first)
141                      (sequence->exp (cond-actions first))
142                      (expand-clauses rest))))))
143 (define (true? x)
144   (not (eq? x false)))
145 (define (false? x)
146   (eq? x false))
147 (define (make-procedure parameters body env)
148   (list 'procedure parameters body env))
149 (define (compound-procedure? p)
150   (tagged-list? p 'procedure))
151 (define (procedure-parameters p) (cadr p))
152 (define (procedure-body p) (caddr p))
153 (define (procedure-environment p) (cadddr p))
154 (define (enclosing-environment env) (cdr env))
155 (define (first-frame env) (car env))
156 (define the-empty-environment '())
157 (define (make-frame variables values)
158   (cons variables values))
159 (define (frame-variables frame) (car frame))
160 (define (frame-values frame) (cdr frame))
161 (define (add-binding-to-frame! var val frame)
162   (set-car! frame (cons var (car frame)))
163   (set-cdr! frame (cons val (cdr frame))))
164 (define (extend-environment vars vals base-env)
165   (if (= (length vars) (length vals))
166       (cons (make-frame vars vals) base-env)
167       (if (< (length vars) (length vals))
168           (error "Too many arguments supplied" vars vals)
169           (error "Too few arguments supplied" vars vals))))
170 (define (lookup-variable-value var env)
171   (define (env-loop env)
172     (define (scan vars vals)
173       (cond ((null? vars)
174              (env-loop (enclosing-environment env)))
175             ((eq? var (car vars))
176              (car vals))
177             (else (scan (cdr vars) (cdr vals)))))
178     (if (eq? env the-empty-environment)
179         (error "Unbound variable" var)
180         (let ((frame (first-frame env)))
181           (scan (frame-variables frame)
182                 (frame-values frame)))))
183   (env-loop env))
184 (define (set-variable-value! var val env)
185   (define (env-loop env)
186     (define (scan vars vals)
187       (cond ((null? vars)
188              (env-loop (enclosing-environment env)))
189             ((eq? var (car vars))
190              (set-car! vals val))
191             (else (scan (cdr vars) (cdr vals)))))
192     (if (eq? env the-empty-environment)
193         (error "Unbound variable -- SET!" var)
194         (let ((frame (first-frame env)))
195           (scan (frame-variables frame)
196                 (frame-values frame)))))
197   (env-loop env))
198 (define (define-variable! var val env)
199   (let ((frame (first-frame env)))
200     (define (scan vars vals)
201       (cond ((null? vars)
202              (add-binding-to-frame! var val frame))
203             ((eq? var (car vars))
204              (set-car! vals val))
205             (else (scan (cdr vars) (cdr vals)))))
206     (scan (frame-variables frame)
207           (frame-values frame))))
208 (define (primitive-procedure? proc)
209   (tagged-list? proc 'primitive))
210 
211 (define (primitive-implementation proc) (cadr proc))
212 (define primitive-procedures
213   (list (list 'car car)
214         (list 'cdr cdr)
215         (list 'cons cons)
216         (list 'null? null?)
217 	(list '* *)
218 	(list '/ /)
219 	(list '+ +)
220 	(list '- -)
221 	(list 'display display)))
222 (define (primitive-procedure-names)
223   (map car
224        primitive-procedures))
225 
226 (define (primitive-procedure-objects)
227   (map (lambda (proc) (list 'primitive (cadr proc)))
228        primitive-procedures))
229 (define (apply-primitive-procedure proc args)
230   (apply-in-underlying-scheme
231    (primitive-implementation proc) args))
232 (define input-prompt ";;; M-Eval input:")
233 (define output-prompt ";;; M-Eval value:")
234 (define (driver-loop)
235   (prompt-for-input input-prompt)
236   (let ((input (read)))
237     (let ((output (eval input the-global-environment)))
238       (announce-output output-prompt)
239       (user-print output)))
240   (driver-loop))
241 (define (prompt-for-input string)
242   (newline) (newline) (display string) (newline))
243 
244 (define (announce-output string)
245   (newline) (display string) (newline))
246 (define (user-print object)
247   (if (compound-procedure? object)
248       (display (list 'compound-procedure
249                      (procedure-parameters object)
250                      (procedure-body object)
251                      '<procedure-env>))
252       (display object)))
253 (define (setup-environment)
254   (let ((initial-env
255          (extend-environment (primitive-procedure-names)
256                              (primitive-procedure-objects)
257                              the-empty-environment)))
258     (define-variable! 'true true initial-env)
259     (define-variable! 'false false initial-env)
260     initial-env))
261 (define the-global-environment (setup-environment))
262 
263 (define (let? exp)
264   (tagged-list? exp 'let))
265 (define (let-vars exp)
266   (map car (cadr exp)))
267 (define (let-vals exp)
268   (map cadr (cadr exp)))
269 (define (let-body exp)
270   (cddr exp))
271 (define (let->combination exp)
272   (cons (make-lambda (let-vars exp) (let-body exp))
273 	(let-vals exp)))
274 
275 (define (test-case actual expected)
276   (newline)
277   (display "Actual:   ")
278   (display actual)
279   (newline)
280   (display "Expected: ")
281   (display expected)
282   (newline))
283 
284 (define (geval exp) ;; eval globally
285   (eval exp the-global-environment))
286 
287 
288 ;; Exercise 4.1.  Notice that we cannot tell whether the metacircular evaluator evaluates operands from left to right or from right to left. Its evaluation order is inherited from the underlying Lisp: If the arguments to cons in list-of-values are evaluated from left to right, then list-of-values will evaluate operands from left to right; and if the arguments to cons are evaluated from right to left, then list-of-values will evaluate operands from right to left.
289 
290 ;; Write a version of list-of-values that evaluates operands from left to right regardless of the order of evaluation in the underlying Lisp. Also write a version of list-of-values that evaluates operands from right to left. 
291 
292 (define (list-of-values-l->r exps env)
293   (if (no-operands? exps)
294       '()
295       (let* ((first (eval (first-operand exps) env))
296 	     (rest (list-of-values (rest-operands exps) env)))
297       (cons first rest))))
298 (define (list-of-values-r->l exps env)
299   (if (no-operands? exps)
300       '()
301       (let* ((rest (list-of-values (rest-operands exps) env))
302 	     (first (eval (first-operand exps) env)))
303       (cons first rest))))
304 
305 (geval 
306  '(define old-value
307     (let ((x 0))
308       (lambda (y)
309 	(let ((z x))
310 	  (set! x y)
311 	  z)))))
312 
313 (define list-of-values list-of-values-l->r)
314 (test-case (geval '(+ (old-value 4) (old-value 5)))
315 	   4)
316 (test-case (geval '(- (old-value 2) (old-value 8)))
317 	   3)
318 (define list-of-values list-of-values-r->l)
319 (test-case (geval '(+ (old-value 4) (old-value 5)))
320 	   13)
321 (test-case (geval '(- (old-value 2) (old-value 8)))
322 	   4)
323 
324 
325 ;; eval test suite
326 ;; (test-case (geval 
327 ;; 	    '(let ((x 4) (y 7))
328 ;; 	       (+ x y (* x y))))
329 ;; 	   (+ 4 7 (* 4 7)))