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