1 (define apply-in-underlying-scheme apply)
2 
3 (define (eval exp env)
4   (cond ((self-evaluating? exp) exp)
5         ((variable? exp) (lookup-variable-value exp env))
6         ((quoted? exp) (text-of-quotation exp))
7         ((assignment? exp) (eval-assignment exp env))
8         ((definition? exp) (eval-definition exp env))
9         ((if? exp) (eval-if exp env))
10 	((and? exp) (eval-and exp env))
11 	((or? exp) (eval-or exp env))
12         ((lambda? exp)
13          (make-procedure (lambda-parameters exp)
14                          (lambda-body exp)
15                          env))
16         ((begin? exp) 
17          (eval-sequence (begin-actions exp) env))
18         ((cond? exp) (eval (cond->if exp) env))
19 	((let? exp) (eval (let->combination exp) env))
20 	((let*? exp) (eval (let*->nested-lets exp) env))
21 	((named-let? exp) (eval (named-let->combination exp) env))
22 	((do? exp) (eval (do->combination exp) env))
23         ((application? exp)
24          (apply (eval (operator exp) env)
25                 (list-of-values (operands exp) env)))
26         (else
27          (error "Unknown expression type -- EVAL" exp))))
28 (define (apply procedure arguments)
29   (cond ((primitive-procedure? procedure)
30          (apply-primitive-procedure procedure arguments))
31         ((compound-procedure? procedure)
32          (eval-sequence
33            (procedure-body procedure)
34            (extend-environment
35              (procedure-parameters procedure)
36              arguments
37              (procedure-environment procedure))))
38         (else
39          (error
40           "Unknown procedure type -- APPLY" procedure))))
41 
42 (define (list-of-values exps env)
43   (if (no-operands? exps)
44       '()
45       (cons (eval (first-operand exps) env)
46             (list-of-values (rest-operands exps) env))))
47 
48 (define (tagged-list? exp tag)
49   (if (pair? exp)
50       (eq? (car exp) tag)
51       false))
52 
53 ;; self-evaluating/variable/quoted
54 (define (self-evaluating? exp)
55   (cond ((number? exp) true)
56         ((string? exp) true)
57         (else false)))
58 (define (variable? exp) (symbol? exp))
59 (define (quoted? exp)
60   (tagged-list? exp 'quote))
61 (define (text-of-quotation exp) (cadr exp))
62 
63 ;; assignment/definition
64 (define (assignment? exp)
65   (tagged-list? exp 'set!))
66 (define (assignment-variable exp) (cadr exp))
67 (define (assignment-value exp) (caddr exp))
68 (define (definition? exp)
69   (tagged-list? exp 'define))
70 (define (definition-variable exp)
71   (if (symbol? (cadr exp))
72       (cadr exp)
73       (caadr exp)))
74 (define (definition-value exp)
75   (if (symbol? (cadr exp))
76       (caddr exp)
77       (make-lambda (cdadr exp)   ; formal parameters
78                    (cddr exp)))) ; body
79 (define (eval-assignment exp env)
80   (set-variable-value! (assignment-variable exp)
81                        (eval (assignment-value exp) env)
82                        env)
83   'ok)
84 (define (eval-definition exp env)
85   (define-variable! (definition-variable exp)
86                     (eval (definition-value exp) env)
87                     env)
88   'ok)
89 (define (make-definition var val)
90   `(define ,var ,val))
91 
92 
93 ;; if/and/or
94 (define (if? exp) (tagged-list? exp 'if))
95 (define (if-predicate exp) (cadr exp))
96 (define (if-consequent exp) (caddr exp))
97 (define (if-alternative exp)
98   (if (not (null? (cdddr exp)))
99       (cadddr exp)
100       'false))
101 (define (make-if predicate consequent alternative)
102   (list 'if predicate consequent alternative))
103 (define (eval-if exp env)
104   (if (true? (eval (if-predicate exp) env))
105       (eval (if-consequent exp) env)
106       (eval (if-alternative exp) env)))
107 
108 (define (and? exp)
109   (tagged-list? exp 'and))
110 (define (and-clauses exp)
111   (cdr exp))
112 (define (or? exp)
113   (tagged-list? exp 'or))
114 (define (or-clauses exp)
115   (cdr exp))
116 (define (eval-and exp env)
117   (define (eval-clauses clauses)
118     (cond ((null? clauses) true)
119 	  ((null? (cdr clauses)) (eval (car clauses) env))
120 	  (else (and (eval (car clauses) env)
121 		     (eval-clauses (cdr clauses))))))
122   (eval-clauses (and-clauses exp)))
123 (define (eval-or exp env)
124   (define (eval-clauses clauses)
125     (if (null? clauses)
126 	false
127 	(or (eval (car clauses) env)
128 	    (eval-clauses (cdr clauses)))))
129   (eval-clauses (or-clauses exp)))
130 
131 
132 ;; lambda/let/let*
133 (define (lambda? exp) (tagged-list? exp 'lambda))
134 (define (lambda-parameters exp) (cadr exp))
135 (define (lambda-body exp) (cddr exp))
136 (define (make-lambda parameters body)
137   (cons 'lambda (cons parameters body)))
138 
139 (define (make-let vars vals body)
140   (cons 'let
141 	(cons (map list vars vals)
142 	      body)))
143 (define (let? exp)
144   (and (tagged-list? exp 'let)
145        (not (symbol? (cadr exp)))))
146 (define (let-vars exp)
147   (map car (cadr exp)))
148 (define (let-vals exp)
149   (map cadr (cadr exp)))
150 (define (let-body exp)
151   (cddr exp))
152 (define (let->combination exp)
153   (make-application (make-lambda (let-vars exp) (let-body exp))
154 		    (let-vals exp)))
155 (define (named-let? exp)
156   (and (tagged-list? exp 'let)
157        (symbol? (cadr exp))))
158 (define (named-let-name exp)
159   (cadr exp))
160 (define (named-let-vars exp)
161   (map car (caddr exp)))
162 (define (named-let-vals exp)
163   (map cadr (caddr exp)))
164 (define (named-let-body exp)
165   (cdddr exp))
166 (define (named-let->combination exp)
167   (sequence->exp
168    (list (make-definition (named-let-name exp)
169 			  (make-lambda (named-let-vars exp)
170 				       (named-let-body exp)))
171 	 (make-application (named-let-name exp)
172 			   (named-let-vals exp)))))
173 (define (make-named-let name vars vals body)
174   (cons 'let 
175 	(cons name
176 	      (cons (map list vars vals)
177 		    body))))
178 
179 (define (make-application op args)
180   (cons op args))
181 
182 (define (let*? exp)
183   (tagged-list? exp 'let*))
184 (define let*-vars let-vars)
185 (define let*-vals let-vals)
186 (define let*-body let-body)
187 (define (let*->nested-lets exp)
188   (define (expand-lets vars vals)
189     (if (null? (cdr vars))
190 	(make-let (list (car vars)) 
191 		  (list (car vals))
192 		  (let*-body exp))
193 	(make-let (list (car vars))
194 		  (list (car vals))
195 		  (list (expand-lets (cdr vars) (cdr vals))))))
196   (let ((vars (let*-vars exp))
197 	(vals (let*-vals exp)))
198     (if (null? vars)
199 	(sequence->exp (let*-body exp))
200 	(expand-lets vars vals))))
201 
202 ;; do loop
203 (define (do? exp)
204   (tagged-list? exp 'do))
205 (define (do-vars exp)
206   (map car (cadr exp)))
207 (define (do-inits exp)
208   (map cadr (cadr exp)))
209 (define (do-steps exp)
210   (map (lambda (var-init-step)
211 	 (if (null? (cddr var-init-step))
212 	     (car var-init-step)
213 	     (caddr var-init-step)))
214        (cadr exp)))
215 (define (do-test exp)
216   (caaddr exp))
217 (define (do-expressions exp)
218   (if (null? (cdaddr exp))
219       (caddr exp)
220       (cdaddr exp)))
221 (define (do-commands exp)
222   (cdddr exp))
223 (define (do->combination exp)
224   (make-named-let
225    'do-iter
226    (do-vars exp)
227    (do-inits exp)
228    (list
229     (make-if
230      (do-test exp)
231      (sequence->exp (do-expressions exp))
232      (sequence->exp
233       (append (do-commands exp)
234 	      (list (make-application
235 		     'do-iter
236 		     (do-steps exp)))))))))
237 
238 
239 ;; begin/sequence
240 (define (begin? exp) (tagged-list? exp 'begin))
241 (define (begin-actions exp) (cdr exp))
242 (define (last-exp? seq) (null? (cdr seq)))
243 (define (first-exp seq) (car seq))
244 (define (rest-exps seq) (cdr seq))
245 (define (sequence->exp seq)
246   (cond ((null? seq) seq)
247         ((last-exp? seq) (first-exp seq))
248         (else (make-begin seq))))
249 (define (make-begin seq) (cons 'begin seq))
250 (define (eval-sequence exps env)
251   (cond ((last-exp? exps) (eval (first-exp exps) env))
252         (else (eval (first-exp exps) env)
253               (eval-sequence (rest-exps exps) env))))
254 
255 ;; application
256 (define (application? exp) (pair? exp))
257 (define (operator exp) (car exp))
258 (define (operands exp) (cdr exp))
259 (define (no-operands? ops) (null? ops))
260 (define (first-operand ops) (car ops))
261 (define (rest-operands ops) (cdr ops))
262 
263 ;; cond
264 (define (cond? exp) (tagged-list? exp 'cond))
265 (define (cond-clauses exp) (cdr exp))
266 (define (cond-else-clause? clause)
267   (eq? (cond-predicate clause) 'else))
268 (define (cond-predicate clause) (car clause))
269 (define (cond-actions clause) (cdr clause))
270 (define (cond-extended-clause? clause)
271   (and (not (null? (cdr clause))) (eq? (cadr clause) '=>)))
272 (define (cond-extended-proc clause)
273   (caddr clause))
274 (define (cond->if exp)
275   (expand-clauses (cond-clauses exp)))
276 (define (expand-clauses clauses)
277   (if (null? clauses)
278       'false                          ; no else clause
279       (let ((first (car clauses))
280             (rest (cdr clauses)))
281         (if (cond-else-clause? first)
282             (if (null? rest)
283                 (sequence->exp (cond-actions first))
284                 (error "ELSE clause isn't last -- COND->IF"
285                        clauses))
286 	    (if (cond-extended-clause? first)
287 		(make-if (cond-predicate first)
288 			 (make-application
289 			  (cond-extended-proc first)
290 			  (list (cond-predicate first)))
291 			 (expand-clauses rest))
292 		(make-if (cond-predicate first)
293 			 (sequence->exp (cond-actions first))
294 			 (expand-clauses rest)))))))
295 (define (true? x)
296   (not (eq? x false)))
297 (define (false? x)
298   (eq? x false))
299 
300 ;; procedure
301 (define (make-procedure parameters body env)
302   (list 'procedure parameters body env))
303 (define (compound-procedure? p)
304   (tagged-list? p 'procedure))
305 (define (procedure-parameters p) (cadr p))
306 (define (procedure-body p) (caddr p))
307 (define (procedure-environment p) (cadddr p))
308 
309 ;; environment
310 (define (enclosing-environment env) (cdr env))
311 (define (first-frame env) (car env))
312 (define the-empty-environment '())
313 (define (make-frame variables values)
314   (cons variables values))
315 (define (frame-variables frame) (car frame))
316 (define (frame-values frame) (cdr frame))
317 (define (add-binding-to-frame! var val frame)
318   (set-car! frame (cons var (car frame)))
319   (set-cdr! frame (cons val (cdr frame))))
320 (define (extend-environment vars vals base-env)
321   (if (= (length vars) (length vals))
322       (cons (make-frame vars vals) base-env)
323       (if (< (length vars) (length vals))
324           (error "Too many arguments supplied" vars vals)
325           (error "Too few arguments supplied" vars vals))))
326 (define (lookup-variable-value var env)
327   (define (env-loop env)
328     (define (scan vars vals)
329       (cond ((null? vars)
330              (env-loop (enclosing-environment env)))
331             ((eq? var (car vars))
332              (car vals))
333             (else (scan (cdr vars) (cdr vals)))))
334     (if (eq? env the-empty-environment)
335         (error "Unbound variable" var)
336         (let ((frame (first-frame env)))
337           (scan (frame-variables frame)
338                 (frame-values frame)))))
339   (env-loop env))
340 (define (set-variable-value! var val env)
341   (define (env-loop env)
342     (define (scan vars vals)
343       (cond ((null? vars)
344              (env-loop (enclosing-environment env)))
345             ((eq? var (car vars))
346              (set-car! vals val))
347             (else (scan (cdr vars) (cdr vals)))))
348     (if (eq? env the-empty-environment)
349         (error "Unbound variable -- SET!" var)
350         (let ((frame (first-frame env)))
351           (scan (frame-variables frame)
352                 (frame-values frame)))))
353   (env-loop env))
354 (define (define-variable! var val env)
355   (let ((frame (first-frame env)))
356     (define (scan vars vals)
357       (cond ((null? vars)
358              (add-binding-to-frame! var val frame))
359             ((eq? var (car vars))
360              (set-car! vals val))
361             (else (scan (cdr vars) (cdr vals)))))
362     (scan (frame-variables frame)
363           (frame-values frame))))
364 
365 ;; primitives
366 (define (primitive-procedure? proc)
367   (tagged-list? proc 'primitive))
368 (define (primitive-implementation proc) (cadr proc))
369 (define primitive-procedures
370   (list (list 'car car)
371         (list 'cdr cdr)
372 	(list 'caar caar)
373 	(list 'cadr cadr)
374 	(list 'cddr cddr)
375         (list 'cons cons)
376         (list 'null? null?)
377 	(list '* *)
378 	(list '/ /)
379 	(list '+ +)
380 	(list '- -)
381 	(list '= =)
382 	(list '< <)
383 	(list '> >)
384 	(list '<= <=)
385 	(list '>= >=)
386 	(list 'remainder remainder)
387 	(list 'eq? eq?)
388 	(list 'equal? equal?)
389 	(list 'display display)))
390 (define (primitive-procedure-names)
391   (map car
392        primitive-procedures))
393 (define (primitive-procedure-objects)
394   (map (lambda (proc) (list 'primitive (cadr proc)))
395        primitive-procedures))
396 (define (apply-primitive-procedure proc args)
397   (apply-in-underlying-scheme
398    (primitive-implementation proc) args))
399 
400 ;; driver-loop
401 (define input-prompt ";;; M-Eval input:")
402 (define output-prompt ";;; M-Eval value:")
403 (define (driver-loop)
404   (prompt-for-input input-prompt)
405   (let ((input (read)))
406     (let ((output (eval input the-global-environment)))
407       (announce-output output-prompt)
408       (user-print output)))
409   (driver-loop))
410 (define (prompt-for-input string)
411   (newline) (newline) (display string) (newline))
412 
413 (define (announce-output string)
414   (newline) (display string) (newline))
415 (define (user-print object)
416   (if (compound-procedure? object)
417       (display (list 'compound-procedure
418                      (procedure-parameters object)
419                      (procedure-body object)
420                      '<procedure-env>))
421       (display object)))
422 (define (setup-environment)
423   (let ((initial-env
424          (extend-environment (primitive-procedure-names)
425                              (primitive-procedure-objects)
426                              the-empty-environment)))
427     (define-variable! 'true true initial-env)
428     (define-variable! 'false false initial-env)
429     initial-env))
430 (define the-global-environment (setup-environment))
431 
432 ;; auxiliary
433 (define (test-case actual expected)
434   (newline)
435   (display "Actual:   ")
436   (display actual)
437   (newline)
438   (display "Expected: ")
439   (display expected)
440   (newline))
441 (define (geval exp) ;; eval globally
442   (eval exp the-global-environment))
443 (define (test-eval exp expected)
444   (test-case (geval exp) expected))
445 
446 ;; Exercise 4.13.  Scheme allows us to create new bindings for variables by means of define, but provides no way to get rid of bindings. Implement for the evaluator a special form make-unbound! that removes the binding of a given symbol from the environment in which the make-unbound! expression is evaluated. This problem is not completely specified. For example, should we remove only the binding in the first frame of the environment? Complete the specification and justify any choices you make. 
447 
448 ;; test-suite
449 
450 ;; procedure definitions
451 
452 (geval 
453  '(define (assoc key records)
454     (cond ((null? records) false)
455 	  ((equal? key (caar records)) (car records))
456 	  (else (assoc key (cdr records))))))
457 
458 (geval
459  '(define (map proc list)
460     (if (null? list)
461 	'()
462 	(cons (proc (car list))
463 	      (map proc (cdr list))))))
464 
465 (geval 
466  '(define (accumulate op initial sequence)
467     (if (null? sequence)
468 	initial
469 	(op (car sequence)
470 	    (accumulate op initial (cdr sequence))))))
471 
472 ;; all special forms
473 (test-eval '(begin 5 6) 6)
474 (test-eval '10 10)
475 (geval '(define x 3))
476 (test-eval 'x 3)
477 (test-eval '(set! x -25) 'ok)
478 (test-eval 'x -25)
479 (geval '(define z (lambda (x y) (+ x (* x y)))))
480 (test-eval '(z 3 4) 15)
481 (test-eval '(cond ((= x -2) 'x=-2)
482 		  ((= x -25) 'x=-25)
483 		  (else 'failed))
484 	   'x=-25)
485 (test-eval '(if true false true) false)
486 (test-eval 
487  '(let ((x 4) (y 7))
488     (+ x y (* x y)))
489  (+ 4 7 (* 4 7)))
490 
491 
492 ;; and/or
493 (geval '(define x (+ 3 8)))
494 (test-eval '(and 0 true x) 11)
495 (test-eval '(and 0 true x false) false)
496 (test-eval '(and 0 true x (set! x -2) false) false)
497 (test-eval 'x -2)
498 (test-eval '(and 0 true x false (set! x -5)) false)
499 (test-eval 'x -2)
500 (test-eval '(or false (set! x 25)) 'ok)
501 (test-eval 'x 25)
502 (test-eval '(or (set! x 2) (set! x 4)) 'ok)
503 (test-eval 'x 2)
504 (test-eval '(or false (set! x 25) true false) 'ok)
505 (test-eval 'x 25)
506 (test-eval '(or ((lambda (x) x) 5)) 5)
507 (test-eval '(or (begin (set! x (+ x 1)) x)) 26)
508 
509 
510 ;; cond
511 
512 (test-eval 
513  '(cond ((assoc 'b '((a 1) (b 2))) => cadr)
514 	(else false))
515  2)
516 
517 (test-eval
518  '(cond ((= 3 4) 'not-true)
519 	((= (* 2 4) 3) 'also-false)
520 	((map (lambda (x)
521 		(* x (+ x 1)))
522 	      '(2 4 1 9))
523 	 =>
524 	 (lambda (x)
525 	   (accumulate + 0 x)))
526 	(else 'never-reach))
527  118)
528 ;; '(6 20 2 90)
529 
530 
531 ;; procedure definition and application
532 (geval
533  '(define (factorial n)
534     (if (= n 0)
535 	1
536 	(* n (factorial (- n 1))))))
537 (test-eval '(factorial 5) 120)
538 
539 ;; map
540 
541 (test-eval
542  '(map (lambda (x)
543 	 (* x (+ x 1)))
544        '(2 1 4 2 8 3))
545  '(6 2 20 6 72 12))
546 ;; accumulate
547 
548 (test-eval
549  '(accumulate + 0 '(1 2 3 4 5))
550  15)
551 
552 ;; make-let
553 (test-eval 
554  (make-let '(x y) '(3 5) '((+ x y)))
555  8)
556 (test-eval 
557  '(let ()
558     5)
559  5)
560 (test-eval
561  '(let ((x 3))
562     x)
563  3)
564 (test-eval
565  '(let ((x 3)
566 	(y 5))
567     (+ x y))
568  8)
569 (test-eval 
570  '(let ((x 3)
571 	(y 2))
572     (+ (let ((x (+ y 2))
573 	     (y x))
574 	 (* x y))
575        x y))
576  (+ (* 4 3) 3 2))
577 (test-eval
578  '(let ((x 6)
579 	(y (let ((x 2))
580 	     (+ x 3)))
581 	(z (let ((a (* 3 2)))
582 	     (+ a 3))))
583     (+ x y z))
584  (+ 6 5 9))
585     
586 
587 ;; let*
588 
589 (test-eval
590  '(let* ((x 3)
591 	 (y (+ x 2))
592 	 (z (+ x y 5)))
593     (* x z))
594  39)
595 
596 (test-eval
597  '(let* ()
598     5)
599  5)
600 (test-eval
601  '(let* ((x 3))
602     (let* ((y 5))
603       (+ x y)))
604  8)
605 
606 (test-eval 
607  '(let* ((x 3)
608 	 (y (+ x 1)))
609     (+ (let* ((x (+ y 2))
610 	      (y x))
611 	 (* x y))
612        x y))
613  (+ (* 6 6) 3 4))
614 (test-eval
615  '(let* ((x 6)
616 	 (y (let* ((x 2)
617 		   (a (let* ((x (* 3 x)))
618 			(+ x 2))))       
619 	      (+ x a)))                  
620 	 (z (+ x y)))                    
621     (+ x y z))
622  32)
623 
624 ;; named-let
625 
626 (test-eval
627  '(let eight ()
628     5
629     7
630     8)
631  8)
632 (test-eval
633  '(let loop ((count 0))
634     (if (= 100 count)
635 	count
636 	(loop (+ count 1))))
637  100)
638 (geval
639  '(define (prime? x)
640     (let prime-iter ((i 2))
641       (cond ((> (* i i) x) true)
642 	    ((= (remainder x i) 0) false)
643 	    (else (prime-iter (+ i 1)))))))
644 (test-eval
645  '(let primes ((x 2)
646 	       (n 20))
647     (cond ((= n 0) '())
648 	  ((prime? x) 
649 	   (cons x
650 		 (primes (+ x 1) (- n 1))))
651 	  (else (primes (+ x 1) n))))
652  '(2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71))
653 
654 (geval
655  '(define (fib n)
656     (let fib-iter ((a 1)
657 		   (b 0)
658 		   (count n))
659       (if (= count 0)
660 	  b
661 	  (fib-iter (+ a b) a (- count 1))))))
662 (test-eval '(fib 19) 4181)
663 
664 ;; do-loop	  
665 (test-eval
666  '(let ((y 0))
667     (do ((x 0 (+ x 1)))
668 	((= x 5) y)
669       (set! y (+ y 1))))
670  5)
671 (test-eval
672  '(do ()
673       (true))
674  true)
675 (test-eval
676  '(do ()
677       (true 5))
678  5)
679 (test-eval
680  '(let ((y 0))
681     (do ()
682 	((= y 5) y)
683       (set! y (+ y 1))))
684  5)
685 
686 (test-eval
687  '(do ((y '(1 2 3 4)))
688       ((null? y))
689     (set! y (cdr y)))
690  true)
691 (test-eval
692  '(let ((y 0))
693     (do ((x 0 (+ x 1)))
694 	((= x 5) y)
695       (set! y (+ y 1))))
696  5)
697 (test-eval
698  '(let ((x '(1 3 5 7 9)))
699     (do ((x x (cdr x))
700 	 (sum 0 (+ sum (car x))))
701 	((null? x) sum)))
702  25)
703 (test-eval 
704  '(let ((z '()))
705     (do ((x '(1 2 3 4) (cdr x))
706 	 (y '(1 2 3 4 5 6 7 8) (cddr y)))
707 	((null? x) y x z)
708       (set! z (cons (car x) z))))
709  '(4 3 2 1))
710 
711 
712