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 (lambda (var val)
140 		     (list var val))
141 		   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 
174 
175 (define (make-application op args)
176   (cons op args))
177 
178 (define (let*? exp)
179   (tagged-list? exp 'let*))
180 (define let*-vars let-vars)
181 (define let*-vals let-vals)
182 (define let*-body let-body)
183 (define (let*->nested-lets exp)
184   (define (expand-lets vars vals)
185     (if (null? (cdr vars))
186 	(make-let (list (car vars)) 
187 		  (list (car vals))
188 		  (let*-body exp))
189 	(make-let (list (car vars))
190 		  (list (car vals))
191 		  (list (expand-lets (cdr vars) (cdr vals))))))
192   (let ((vars (let*-vars exp))
193 	(vals (let*-vals exp)))
194     (if (null? vars)
195 	(sequence->exp (let*-body exp))
196 	(expand-lets vars vals))))
197 
198 
199 ;; begin/sequence
200 (define (begin? exp) (tagged-list? exp 'begin))
201 (define (begin-actions exp) (cdr exp))
202 (define (last-exp? seq) (null? (cdr seq)))
203 (define (first-exp seq) (car seq))
204 (define (rest-exps seq) (cdr seq))
205 (define (sequence->exp seq)
206   (cond ((null? seq) seq)
207         ((last-exp? seq) (first-exp seq))
208         (else (make-begin seq))))
209 (define (make-begin seq) (cons 'begin seq))
210 (define (eval-sequence exps env)
211   (cond ((last-exp? exps) (eval (first-exp exps) env))
212         (else (eval (first-exp exps) env)
213               (eval-sequence (rest-exps exps) env))))
214 
215 ;; application
216 (define (application? exp) (pair? exp))
217 (define (operator exp) (car exp))
218 (define (operands exp) (cdr exp))
219 (define (no-operands? ops) (null? ops))
220 (define (first-operand ops) (car ops))
221 (define (rest-operands ops) (cdr ops))
222 
223 ;; cond
224 (define (cond? exp) (tagged-list? exp 'cond))
225 (define (cond-clauses exp) (cdr exp))
226 (define (cond-else-clause? clause)
227   (eq? (cond-predicate clause) 'else))
228 (define (cond-predicate clause) (car clause))
229 (define (cond-actions clause) (cdr clause))
230 (define (cond-extended-clause? clause)
231   (and (not (null? (cdr clause))) (eq? (cadr clause) '=>)))
232 (define (cond-extended-proc clause)
233   (caddr clause))
234 (define (cond->if exp)
235   (expand-clauses (cond-clauses exp)))
236 (define (expand-clauses clauses)
237   (if (null? clauses)
238       'false                          ; no else clause
239       (let ((first (car clauses))
240             (rest (cdr clauses)))
241         (if (cond-else-clause? first)
242             (if (null? rest)
243                 (sequence->exp (cond-actions first))
244                 (error "ELSE clause isn't last -- COND->IF"
245                        clauses))
246 	    (if (cond-extended-clause? first)
247 		(make-if (cond-predicate first)
248 			 (make-application
249 			  (cond-extended-proc first)
250 			  (list (cond-predicate first)))
251 			 (expand-clauses rest))
252 		(make-if (cond-predicate first)
253 			 (sequence->exp (cond-actions first))
254 			 (expand-clauses rest)))))))
255 (define (true? x)
256   (not (eq? x false)))
257 (define (false? x)
258   (eq? x false))
259 
260 ;; procedure
261 (define (make-procedure parameters body env)
262   (list 'procedure parameters body env))
263 (define (compound-procedure? p)
264   (tagged-list? p 'procedure))
265 (define (procedure-parameters p) (cadr p))
266 (define (procedure-body p) (caddr p))
267 (define (procedure-environment p) (cadddr p))
268 
269 ;; environment
270 (define (enclosing-environment env) (cdr env))
271 (define (first-frame env) (car env))
272 (define the-empty-environment '())
273 (define (make-frame variables values)
274   (cons variables values))
275 (define (frame-variables frame) (car frame))
276 (define (frame-values frame) (cdr frame))
277 (define (add-binding-to-frame! var val frame)
278   (set-car! frame (cons var (car frame)))
279   (set-cdr! frame (cons val (cdr frame))))
280 (define (extend-environment vars vals base-env)
281   (if (= (length vars) (length vals))
282       (cons (make-frame vars vals) base-env)
283       (if (< (length vars) (length vals))
284           (error "Too many arguments supplied" vars vals)
285           (error "Too few arguments supplied" vars vals))))
286 (define (lookup-variable-value var env)
287   (define (env-loop env)
288     (define (scan vars vals)
289       (cond ((null? vars)
290              (env-loop (enclosing-environment env)))
291             ((eq? var (car vars))
292              (car vals))
293             (else (scan (cdr vars) (cdr vals)))))
294     (if (eq? env the-empty-environment)
295         (error "Unbound variable" var)
296         (let ((frame (first-frame env)))
297           (scan (frame-variables frame)
298                 (frame-values frame)))))
299   (env-loop env))
300 (define (set-variable-value! var val env)
301   (define (env-loop env)
302     (define (scan vars vals)
303       (cond ((null? vars)
304              (env-loop (enclosing-environment env)))
305             ((eq? var (car vars))
306              (set-car! vals val))
307             (else (scan (cdr vars) (cdr vals)))))
308     (if (eq? env the-empty-environment)
309         (error "Unbound variable -- SET!" var)
310         (let ((frame (first-frame env)))
311           (scan (frame-variables frame)
312                 (frame-values frame)))))
313   (env-loop env))
314 (define (define-variable! var val env)
315   (let ((frame (first-frame env)))
316     (define (scan vars vals)
317       (cond ((null? vars)
318              (add-binding-to-frame! var val frame))
319             ((eq? var (car vars))
320              (set-car! vals val))
321             (else (scan (cdr vars) (cdr vals)))))
322     (scan (frame-variables frame)
323           (frame-values frame))))
324 
325 ;; primitives
326 (define (primitive-procedure? proc)
327   (tagged-list? proc 'primitive))
328 (define (primitive-implementation proc) (cadr proc))
329 (define primitive-procedures
330   (list (list 'car car)
331         (list 'cdr cdr)
332 	(list 'caar caar)
333 	(list 'cadr cadr)
334 	(list 'cddr cddr)
335         (list 'cons cons)
336         (list 'null? null?)
337 	(list '* *)
338 	(list '/ /)
339 	(list '+ +)
340 	(list '- -)
341 	(list '= =)
342 	(list '< <)
343 	(list '> >)
344 	(list '<= <=)
345 	(list '>= >=)
346 	(list 'remainder remainder)
347 	(list 'eq? eq?)
348 	(list 'equal? equal?)
349 	(list 'display display)))
350 (define (primitive-procedure-names)
351   (map car
352        primitive-procedures))
353 (define (primitive-procedure-objects)
354   (map (lambda (proc) (list 'primitive (cadr proc)))
355        primitive-procedures))
356 (define (apply-primitive-procedure proc args)
357   (apply-in-underlying-scheme
358    (primitive-implementation proc) args))
359 
360 ;; driver-loop
361 (define input-prompt ";;; M-Eval input:")
362 (define output-prompt ";;; M-Eval value:")
363 (define (driver-loop)
364   (prompt-for-input input-prompt)
365   (let ((input (read)))
366     (let ((output (eval input the-global-environment)))
367       (announce-output output-prompt)
368       (user-print output)))
369   (driver-loop))
370 (define (prompt-for-input string)
371   (newline) (newline) (display string) (newline))
372 
373 (define (announce-output string)
374   (newline) (display string) (newline))
375 (define (user-print object)
376   (if (compound-procedure? object)
377       (display (list 'compound-procedure
378                      (procedure-parameters object)
379                      (procedure-body object)
380                      '<procedure-env>))
381       (display object)))
382 (define (setup-environment)
383   (let ((initial-env
384          (extend-environment (primitive-procedure-names)
385                              (primitive-procedure-objects)
386                              the-empty-environment)))
387     (define-variable! 'true true initial-env)
388     (define-variable! 'false false initial-env)
389     initial-env))
390 (define the-global-environment (setup-environment))
391 
392 ;; auxiliary
393 (define (test-case actual expected)
394   (newline)
395   (display "Actual:   ")
396   (display actual)
397   (newline)
398   (display "Expected: ")
399   (display expected)
400   (newline))
401 (define (geval exp) ;; eval globally
402   (eval exp the-global-environment))
403 (define (test-eval exp expected)
404   (test-case (geval exp) expected))
405 
406 ;; 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. 
407 
408 ;; Implemented according to this spec:
409 ;; http://www.gnu.org/software/mit-scheme/documentation/mit-scheme-ref/Iteration.html
410 
411 
412 ;; (do ((vec (make-vector 5))
413 ;;      (i 0 (+ i 1)))
414 ;;     ((= i 5) vec)
415 ;;   (vector-set! vec i i))               =>  #(0 1 2 3 4)
416 
417 (define (do? exp)
418   (tagged-list? exp 'do))
419 (define (do-vars exp)
420   (map car (cadr exp)))
421 (define (do-inits exp)
422   (map cadr (cadr exp)))
423 (define (do-steps exp)
424   (map (lambda (var-init-step)
425 	 (if (null? (cddr var-init-step))
426 	     (car var-init-step)
427 	     (caddr var-init-step)))
428        (cadr exp)))
429 (define (do-test exp)
430   (caaddr exp))
431 (define (do-expressions exp)
432   (if (null? (cdaddr exp))
433       (caddr exp)
434       (cdaddr exp)))
435 (define (do-commands exp)
436   (cdddr exp))
437 (define (do->combination exp)
438   (sequence->exp
439    (list 
440     (make-definition 
441      'do-iter
442      (make-lambda
443       (do-vars exp)
444       (list 
445        (make-if 
446 	(do-test exp)
447 	(sequence->exp (do-expressions exp))
448 	(sequence->exp 
449 	 (append (do-commands exp)
450 		 (list (make-application
451 			'do-iter
452 			(do-steps exp)))))))))
453     (make-application 'do-iter (do-inits exp)))))
454 
455 
456 ;; (define do-name 
457 ;;   (lambda (x y)
458 ;;     (if (null? x)
459 ;; 	(begin y x (car y)) ;; if there are no expressions, then (null? x) would be returned
460 ;; 	(begin (display 'command)
461 ;; 	       (display 'another)
462 ;; 	       (do-name (cdr x) (cddr y))) ;; if the step is omitted, it is simply x y
463 ;; (do-name '(1 2 3 4)
464 ;; 	 '(1 2 3 4 5 6 7 8))
465 
466 (test-eval
467  '(do ()
468       (true))
469  true)
470 (test-eval
471  '(do ()
472       (true 5))
473  5)
474 (test-eval
475  '(let ((y 0))
476     (do ()
477 	((= y 5) y)
478       (set! y (+ y 1))))
479  5)
480 (test-eval
481  (do ((y '(1 2 3 4)))
482      ((null? y))
483    (set! y (cdr y)))
484  true)
485 (test-eval
486  '(let ((y 0))
487     (do ((x 0 (+ x 1)))
488 	((= x 5) y)
489       (set! y (+ y 1))))
490  5)
491 (test-eval
492  '(let ((x '(1 3 5 7 9)))
493     (do ((x x (cdr x))
494 	 (sum 0 (+ sum (car x))))
495 	((null? x) sum)))
496  25)
497 (test-eval 
498  '(let ((z '()))
499     (do ((x '(1 2 3 4) (cdr x))
500 	 (y '(1 2 3 4 5 6 7 8) (cddr y)))
501 	((null? x) y x z)
502       (set! z (cons (car x) z))))
503  '(4 3 2 1))
504 (begin
505   (define do-iter 
506     (lambda (x) 
507       (if (= x 5)
508 	  y
509 	  (begin 
510 	    (set! y (+ y 1))
511 	    (do-iter (+ x 1))))))
512   (do-iter 0))
513 somehow we are evaluating true and not 'true
514 
515 we could actually rewrite this as a named-let
516 (let do-iter ((x 0))
517   (if (= x 5)
518       y
519       (begin
520 	(set! y (+ y 1))
521 	(do-iter (+ x 1)))))
522 
523 
524 ;; test-suite
525 
526 ;; procedure definitions
527 
528 (geval 
529  '(define (assoc key records)
530     (cond ((null? records) false)
531 	  ((equal? key (caar records)) (car records))
532 	  (else (assoc key (cdr records))))))
533 
534 (geval
535  '(define (map proc list)
536     (if (null? list)
537 	'()
538 	(cons (proc (car list))
539 	      (map proc (cdr list))))))
540 
541 (geval 
542  '(define (accumulate op initial sequence)
543     (if (null? sequence)
544 	initial
545 	(op (car sequence)
546 	    (accumulate op initial (cdr sequence))))))
547 
548 ;; all special forms
549 (test-eval '(begin 5 6) 6)
550 (test-eval '10 10)
551 (geval '(define x 3))
552 (test-eval 'x 3)
553 (test-eval '(set! x -25) 'ok)
554 (test-eval 'x -25)
555 (geval '(define z (lambda (x y) (+ x (* x y)))))
556 (test-eval '(z 3 4) 15)
557 (test-eval '(cond ((= x -2) 'x=-2)
558 		  ((= x -25) 'x=-25)
559 		  (else 'failed))
560 	   'x=-25)
561 (test-eval '(if true false true) false)
562 (test-eval 
563  '(let ((x 4) (y 7))
564     (+ x y (* x y)))
565  (+ 4 7 (* 4 7)))
566 
567 
568 ;; and/or
569 (geval '(define x (+ 3 8)))
570 (test-eval '(and 0 true x) 11)
571 (test-eval '(and 0 true x false) false)
572 (test-eval '(and 0 true x (set! x -2) false) false)
573 (test-eval 'x -2)
574 (test-eval '(and 0 true x false (set! x -5)) false)
575 (test-eval 'x -2)
576 (test-eval '(or false (set! x 25)) 'ok)
577 (test-eval 'x 25)
578 (test-eval '(or (set! x 2) (set! x 4)) 'ok)
579 (test-eval 'x 2)
580 (test-eval '(or false (set! x 25) true false) 'ok)
581 (test-eval 'x 25)
582 (test-eval '(or ((lambda (x) x) 5)) 5)
583 (test-eval '(or (begin (set! x (+ x 1)) x)) 26)
584 
585 
586 ;; cond
587 
588 (test-eval 
589  '(cond ((assoc 'b '((a 1) (b 2))) => cadr)
590 	(else false))
591  2)
592 
593 (test-eval
594  '(cond ((= 3 4) 'not-true)
595 	((= (* 2 4) 3) 'also-false)
596 	((map (lambda (x)
597 		(* x (+ x 1)))
598 	      '(2 4 1 9))
599 	 =>
600 	 (lambda (x)
601 	   (accumulate + 0 x)))
602 	(else 'never-reach))
603  118)
604 ;; '(6 20 2 90)
605 
606 
607 ;; procedure definition and application
608 (geval
609  '(define (factorial n)
610     (if (= n 0)
611 	1
612 	(* n (factorial (- n 1))))))
613 (test-eval '(factorial 5) 120)
614 
615 ;; map
616 
617 (test-eval
618  '(map (lambda (x)
619 	 (* x (+ x 1)))
620        '(2 1 4 2 8 3))
621  '(6 2 20 6 72 12))
622 ;; accumulate
623 
624 (test-eval
625  '(accumulate + 0 '(1 2 3 4 5))
626  15)
627 
628 ;; make-let
629 (test-eval 
630  (make-let '(x y) '(3 5) '((+ x y)))
631  8)
632 (test-eval 
633  '(let ()
634     5)
635  5)
636 (test-eval
637  '(let ((x 3))
638     x)
639  3)
640 (test-eval
641  '(let ((x 3)
642 	(y 5))
643     (+ x y))
644  8)
645 (test-eval 
646  '(let ((x 3)
647 	(y 2))
648     (+ (let ((x (+ y 2))
649 	     (y x))
650 	 (* x y))
651        x y))
652  (+ (* 4 3) 3 2))
653 (test-eval
654  '(let ((x 6)
655 	(y (let ((x 2))
656 	     (+ x 3)))
657 	(z (let ((a (* 3 2)))
658 	     (+ a 3))))
659     (+ x y z))
660  (+ 6 5 9))
661     
662 
663 ;; let*
664 
665 (test-eval
666  '(let* ((x 3)
667 	 (y (+ x 2))
668 	 (z (+ x y 5)))
669     (* x z))
670  39)
671 
672 (test-eval
673  '(let* ()
674     5)
675  5)
676 (test-eval
677  '(let* ((x 3))
678     (let* ((y 5))
679       (+ x y)))
680  8)
681 
682 (test-eval 
683  '(let* ((x 3)
684 	 (y (+ x 1)))
685     (+ (let* ((x (+ y 2))
686 	      (y x))
687 	 (* x y))
688        x y))
689  (+ (* 6 6) 3 4))
690 (test-eval
691  '(let* ((x 6)
692 	 (y (let* ((x 2)
693 		   (a (let* ((x (* 3 x)))
694 			(+ x 2))))       
695 	      (+ x a)))                  
696 	 (z (+ x y)))                    
697     (+ x y z))
698  32)
699 
700 ;; named-let
701 
702 (test-eval
703  '(let eight ()
704     5
705     7
706     8)
707  8)
708 (test-eval
709  '(let loop ((count 0))
710     (if (= 100 count)
711 	count
712 	(loop (+ count 1))))
713  100)
714 (geval
715  '(define (prime? x)
716     (let prime-iter ((i 2))
717       (cond ((> (* i i) x) true)
718 	    ((= (remainder x i) 0) false)
719 	    (else (prime-iter (+ i 1)))))))
720 (test-eval
721  '(let primes ((x 2)
722 	       (n 20))
723     (cond ((= n 0) '())
724 	  ((prime? x) 
725 	   (cons x
726 		 (primes (+ x 1) (- n 1))))
727 	  (else (primes (+ x 1) n))))
728  '(2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71))
729 
730 (geval
731  '(define (fib n)
732     (let fib-iter ((a 1)
733 		   (b 0)
734 		   (count n))
735       (if (= count 0)
736 	  b
737 	  (fib-iter (+ a b) a (- count 1))))))
738 (test-eval '(fib 19) 4181)
739 
740