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 	((and? exp) (eval-and exp env))
12 	((or? exp) (eval-or exp env))
13         ((lambda? exp)
14          (make-procedure (lambda-parameters exp)
15                          (lambda-body exp)
16                          env))
17         ((begin? exp) 
18          (eval-sequence (begin-actions exp) env))
19         ((cond? exp) (eval (cond->if exp) env))
20 	((let? exp) (eval (let->combination exp) env))
21         ((application? exp)
22          (apply (eval (operator exp) env)
23                 (list-of-values (operands exp) env)))
24         (else
25          (error "Unknown expression type -- EVAL" exp))))
26 
27 (define (apply procedure arguments)
28   (cond ((primitive-procedure? procedure)
29          (apply-primitive-procedure procedure arguments))
30         ((compound-procedure? procedure)
31          (eval-sequence
32            (procedure-body procedure)
33            (extend-environment
34              (procedure-parameters procedure)
35              arguments
36              (procedure-environment procedure))))
37         (else
38          (error
39           "Unknown procedure type -- APPLY" procedure))))
40 (define (list-of-values exps env)
41   (if (no-operands? exps)
42       '()
43       (cons (eval (first-operand exps) env)
44             (list-of-values (rest-operands exps) env))))
45 
46 (define (eval-if exp env)
47   (if (true? (eval (if-predicate exp) env))
48       (eval (if-consequent exp) env)
49       (eval (if-alternative exp) env)))
50 (define (eval-sequence exps env)
51   (cond ((last-exp? exps) (eval (first-exp exps) env))
52         (else (eval (first-exp exps) env)
53               (eval-sequence (rest-exps exps) env))))
54 (define (eval-assignment exp env)
55   (set-variable-value! (assignment-variable exp)
56                        (eval (assignment-value exp) env)
57                        env)
58   'ok)
59 (define (eval-definition exp env)
60   (define-variable! (definition-variable exp)
61                     (eval (definition-value exp) env)
62                     env)
63   'ok)
64 (define (self-evaluating? exp)
65   (cond ((number? exp) true)
66         ((string? exp) true)
67         (else false)))
68 (define (variable? exp) (symbol? exp))
69 (define (quoted? exp)
70   (tagged-list? exp 'quote))
71 
72 (define (text-of-quotation exp) (cadr exp))
73 (define (tagged-list? exp tag)
74   (if (pair? exp)
75       (eq? (car exp) tag)
76       false))
77 (define (assignment? exp)
78   (tagged-list? exp 'set!))
79 (define (assignment-variable exp) (cadr exp))
80 (define (assignment-value exp) (caddr exp))
81 (define (definition? exp)
82   (tagged-list? exp 'define))
83 (define (definition-variable exp)
84   (if (symbol? (cadr exp))
85       (cadr exp)
86       (caadr exp)))
87 (define (definition-value exp)
88   (if (symbol? (cadr exp))
89       (caddr exp)
90       (make-lambda (cdadr exp)   ; formal parameters
91                    (cddr exp)))) ; body
92 (define (lambda? exp) (tagged-list? exp 'lambda))
93 (define (lambda-parameters exp) (cadr exp))
94 (define (lambda-body exp) (cddr exp))
95 (define (make-lambda parameters body)
96   (cons 'lambda (cons parameters body)))
97 (define (if? exp) (tagged-list? exp 'if))
98 (define (if-predicate exp) (cadr exp))
99 (define (if-consequent exp) (caddr exp))
100 (define (if-alternative exp)
101   (if (not (null? (cdddr exp)))
102       (cadddr exp)
103       'false))
104 (define (make-if predicate consequent alternative)
105   (list 'if predicate consequent alternative))
106 (define (begin? exp) (tagged-list? exp 'begin))
107 (define (begin-actions exp) (cdr exp))
108 (define (last-exp? seq) (null? (cdr seq)))
109 (define (first-exp seq) (car seq))
110 (define (rest-exps seq) (cdr seq))
111 
112 (define (sequence->exp seq)
113   (cond ((null? seq) seq)
114         ((last-exp? seq) (first-exp seq))
115         (else (make-begin seq))))
116 (define (make-begin seq) (cons 'begin seq))
117 (define (application? exp) (pair? exp))
118 (define (operator exp) (car exp))
119 (define (operands exp) (cdr exp))
120 (define (no-operands? ops) (null? ops))
121 (define (first-operand ops) (car ops))
122 (define (rest-operands ops) (cdr ops))
123 (define (cond? exp) (tagged-list? exp 'cond))
124 (define (cond-clauses exp) (cdr exp))
125 (define (cond-else-clause? clause)
126   (eq? (cond-predicate clause) 'else))
127 (define (cond-predicate clause) (car clause))
128 (define (cond-actions clause) (cdr clause))
129 (define (cond->if exp)
130   (expand-clauses (cond-clauses exp)))
131 
132 (define (expand-clauses clauses)
133   (if (null? clauses)
134       'false                          ; no else clause
135       (let ((first (car clauses))
136             (rest (cdr clauses)))
137         (if (cond-else-clause? first)
138             (if (null? rest)
139                 (sequence->exp (cond-actions first))
140                 (error "ELSE clause isn't last -- COND->IF"
141                        clauses))
142             (make-if (cond-predicate first)
143                      (sequence->exp (cond-actions first))
144                      (expand-clauses rest))))))
145 (define (true? x)
146   (not (eq? x false)))
147 (define (false? x)
148   (eq? x false))
149 (define (make-procedure parameters body env)
150   (list 'procedure parameters body env))
151 (define (compound-procedure? p)
152   (tagged-list? p 'procedure))
153 (define (procedure-parameters p) (cadr p))
154 (define (procedure-body p) (caddr p))
155 (define (procedure-environment p) (cadddr p))
156 (define (enclosing-environment env) (cdr env))
157 (define (first-frame env) (car env))
158 (define the-empty-environment '())
159 (define (make-frame variables values)
160   (cons variables values))
161 (define (frame-variables frame) (car frame))
162 (define (frame-values frame) (cdr frame))
163 (define (add-binding-to-frame! var val frame)
164   (set-car! frame (cons var (car frame)))
165   (set-cdr! frame (cons val (cdr frame))))
166 (define (extend-environment vars vals base-env)
167   (if (= (length vars) (length vals))
168       (cons (make-frame vars vals) base-env)
169       (if (< (length vars) (length vals))
170           (error "Too many arguments supplied" vars vals)
171           (error "Too few arguments supplied" vars vals))))
172 (define (lookup-variable-value var env)
173   (define (env-loop env)
174     (define (scan vars vals)
175       (cond ((null? vars)
176              (env-loop (enclosing-environment env)))
177             ((eq? var (car vars))
178              (car vals))
179             (else (scan (cdr vars) (cdr vals)))))
180     (if (eq? env the-empty-environment)
181         (error "Unbound variable" var)
182         (let ((frame (first-frame env)))
183           (scan (frame-variables frame)
184                 (frame-values frame)))))
185   (env-loop env))
186 (define (set-variable-value! var val env)
187   (define (env-loop env)
188     (define (scan vars vals)
189       (cond ((null? vars)
190              (env-loop (enclosing-environment env)))
191             ((eq? var (car vars))
192              (set-car! vals val))
193             (else (scan (cdr vars) (cdr vals)))))
194     (if (eq? env the-empty-environment)
195         (error "Unbound variable -- SET!" var)
196         (let ((frame (first-frame env)))
197           (scan (frame-variables frame)
198                 (frame-values frame)))))
199   (env-loop env))
200 (define (define-variable! var val env)
201   (let ((frame (first-frame env)))
202     (define (scan vars vals)
203       (cond ((null? vars)
204              (add-binding-to-frame! var val frame))
205             ((eq? var (car vars))
206              (set-car! vals val))
207             (else (scan (cdr vars) (cdr vals)))))
208     (scan (frame-variables frame)
209           (frame-values frame))))
210 (define (primitive-procedure? proc)
211   (tagged-list? proc 'primitive))
212 
213 (define (primitive-implementation proc) (cadr proc))
214 (define primitive-procedures
215   (list (list 'car car)
216         (list 'cdr cdr)
217         (list 'cons cons)
218         (list 'null? null?)
219 	(list '* *)
220 	(list '/ /)
221 	(list '+ +)
222 	(list '- -)
223 	(list '= =)
224 	(list 'display display)))
225 (define (primitive-procedure-names)
226   (map car
227        primitive-procedures))
228 
229 (define (primitive-procedure-objects)
230   (map (lambda (proc) (list 'primitive (cadr proc)))
231        primitive-procedures))
232 (define (apply-primitive-procedure proc args)
233   (apply-in-underlying-scheme
234    (primitive-implementation proc) args))
235 (define input-prompt ";;; M-Eval input:")
236 (define output-prompt ";;; M-Eval value:")
237 (define (driver-loop)
238   (prompt-for-input input-prompt)
239   (let ((input (read)))
240     (let ((output (eval input the-global-environment)))
241       (announce-output output-prompt)
242       (user-print output)))
243   (driver-loop))
244 (define (prompt-for-input string)
245   (newline) (newline) (display string) (newline))
246 
247 (define (announce-output string)
248   (newline) (display string) (newline))
249 (define (user-print object)
250   (if (compound-procedure? object)
251       (display (list 'compound-procedure
252                      (procedure-parameters object)
253                      (procedure-body object)
254                      '<procedure-env>))
255       (display object)))
256 (define (setup-environment)
257   (let ((initial-env
258          (extend-environment (primitive-procedure-names)
259                              (primitive-procedure-objects)
260                              the-empty-environment)))
261     (define-variable! 'true true initial-env)
262     (define-variable! 'false false initial-env)
263     initial-env))
264 (define the-global-environment (setup-environment))
265 
266 (define (make-let vars vals body)
267   (cons 'let
268 	(cons (map (lambda (var val)
269 		     (list var val))
270 		   vars vals)
271 	      body)))
272 (define (let? exp)
273   (tagged-list? exp 'let))
274 (define (let-vars exp)
275   (map car (cadr exp)))
276 (define (let-vals exp)
277   (map cadr (cadr exp)))
278 (define (let-body exp)
279   (cddr exp))
280 (define (let->combination exp)
281   (make-application (make-lambda (let-vars exp) (let-body exp))
282 		    (let-vals exp)))
283 (define (make-application op args)
284   (cons op args))
285 
286 (define (test-case actual expected)
287   (newline)
288   (display "Actual:   ")
289   (display actual)
290   (newline)
291   (display "Expected: ")
292   (display expected)
293   (newline))
294 
295 (define (geval exp) ;; eval globally
296   (eval exp the-global-environment))
297 
298 ;; Exercise 4.4.  Recall the definitions of the special forms and and or from chapter 1:
299 
300 ;;    and: The expressions are evaluated from left to right. If any expression evaluates to false, false is returned; any remaining expressions are not evaluated. If all the expressions evaluate to true values, the value of the last expression is returned. If there are no expressions then true is returned.
301 
302 ;;    or: The expressions are evaluated from left to right. If any expression evaluates to a true value, that value is returned; any remaining expressions are not evaluated. If all expressions evaluate to false, or if there are no expressions, then false is returned. 
303 
304 ;; Install and and or as new special forms for the evaluator by defining appropriate syntax procedures and evaluation procedures eval-and and eval-or. Alternatively, show how to implement and and or as derived expressions. 
305 
306 (define (and? exp)
307   (tagged-list? exp 'and))
308 (define (and-clauses exp)
309   (cdr exp))
310 ;; (define (and->if exp)
311 ;;   (define (expand-clauses clauses)
312 ;;     (cond ((null? clauses) 'true)
313 ;; 	  ((null? (cdr clauses)) (car clauses))
314 ;; 	  (else (make-if (car clauses)
315 ;; 			 (expand-clauses (cdr clauses))
316 ;; 			 'false))))
317 ;;   (expand-clauses (and-clauses exp)))
318 (define (or? exp)
319   (tagged-list? exp 'or))
320 (define (or-clauses exp)
321   (cdr exp))
322 ;; the problem with this definition is that each clause will be evaluated twice; this is unacceptable if there are side effects
323 ;; (define (or->if exp)
324 ;;   (define (expand-clauses clauses)
325 ;;     (if (null? clauses)
326 ;; 	'false
327 ;;         (make-if (car clauses)
328 ;; 		 (car clauses)
329 ;; 		 (expand-clauses (cdr clauses)))))
330 ;;   (expand-clauses (or-clauses exp)))
331 
332 
333 ;; we can also install and/or as special forms
334 
335 (define (eval-and exp env)
336   (define (eval-clauses clauses)
337     (cond ((null? clauses) true)
338 	  ((null? (cdr clauses)) (eval (car clauses) env))
339 	  (else (and (eval (car clauses) env)
340 		     (eval-clauses (cdr clauses))))))
341   (eval-clauses (and-clauses exp)))
342 (define (eval-or exp env)
343   (define (eval-clauses clauses)
344     (if (null? clauses)
345 	false
346 	(or (eval (car clauses) env)
347 	    (eval-clauses (cdr clauses)))))
348   (eval-clauses (or-clauses exp)))
349 
350 
351 ;; Exercise 4.5.  Scheme allows an additional syntax for cond clauses, (<test> => <recipient>). If <test> evaluates to a true value, then <recipient> is evaluated. Its value must be a procedure of one argument; this procedure is then invoked on the value of the <test>, and the result is returned as the value of the cond expression. For example
352 
353 ;; (cond ((assoc 'b '((a 1) (b 2))) => cadr)
354 ;;       (else false))
355 
356 ;; returns 2. Modify the handling of cond so that it supports this extended syntax. 
357 
358 (geval 
359  '(define (assoc key records)
360     (cond ((null? records) false)
361 	  ((equal? key (car (car records))) (car records))
362 	  (else (assoc key (cdr records))))))
363 
364 ;; (test-case
365 ;;  (geval 
366 ;;   '(cond ((assoc 'b '((a 1) (b 2))) => cadr)
367 ;; 	 (else false)))
368 ;;  2)
369 
370 (geval
371  '(define (map proc . lists)
372     (define (inner-map proc list)
373       (if (null? list)
374 	  '()
375 	  (cons (proc (car list))
376 		(inner-map proc (cdr list)))))
377     (if (null? lists)
378 	'()
379 	(cons (inner-map proc (inner-map car lists))
380 	      (map proc (inner-map cdr lists))))))
381 (test-case
382  (geval '(map (lambda (x y)
383 		(* x y))
384 	      '(2 1 4 2 8 3)
385 	      '(3 7 1 0 7 8)))
386  '(6 7 4 0 56 24))
387        
388 
389 ;; (test-case 
390 ;;  (geval
391 ;;   '(cond ((= 3 4) 'not-true)
392 ;; 	 ((= (* 2 4) 3) 'also-false)
393 ;; 	 ((assoc '
394 
395 ;; test-suite
396 
397 ;; make-let
398 (test-case (geval (make-let '(x y) '(3 5) '((+ x y))))
399 	   8)
400 
401 ;; and/or
402 (geval '(define x (+ 3 8)))
403 (test-case (geval '(and 0 true x)) 11)
404 (test-case (geval '(and 0 true x false)) false)
405 (test-case (geval '(and 0 true x (set! x -2) false)) false)
406 (test-case (geval 'x) -2)
407 (test-case (geval '(and 0 true x false (set! x -5))) false)
408 (test-case (geval 'x) -2)
409 (test-case (geval '(or false (set! x 25))) 'ok)
410 (test-case (geval 'x) 25)
411 (test-case (geval '(or (set! x 2) (set! x 4))) 'ok)
412 (test-case (geval 'x) 2)
413 (test-case (geval '(or false (set! x 25) true false)) 'ok)
414 (test-case (geval 'x) 25)
415 (test-case (geval '(or ((lambda (x) x) 5))) 5)
416 (test-case (geval '(or (begin (set! x (+ x 1)) x))) 26)
417 
418 
419 ;; all special forms
420 (test-case (geval '(begin 5 6)) 6)
421 (test-case (geval '10) 10)
422 (geval '(define x 3))
423 (test-case (geval 'x) 3)
424 (test-case (geval '(set! x -25)) 'ok)
425 (test-case (geval 'x) -25)
426 (geval '(define z (lambda (x y) (+ x (* x y)))))
427 (test-case (geval '(z 3 4)) 15)
428 (test-case (geval '(cond ((= x -2) 'x=-2)
429 			 ((= x -25) 'x=-25)
430 			 (else 'failed)))
431 	   'x=-25)
432 (test-case (geval '(if true false true)) false)
433 (test-case (geval 
434 	    '(let ((x 4) (y 7))
435 	       (+ x y (* x y))))
436 	   (+ 4 7 (* 4 7)))
437 
438 ;; procedure definition and application
439 (geval
440  '(define (factorial n)
441     (if (= n 0)
442 	1
443 	(* n (factorial (- n 1))))))
444 (test-case (geval '(factorial 5)) 120)
445 
446