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 	((unbound? exp) (eval-unbound 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 	((let*? exp) (eval (let*->nested-lets exp) env))
22 	((named-let? exp) (eval (named-let->combination exp) env))
23 	((do? exp) (eval (do->combination exp) env))
24         ((application? exp)
25          (apply (eval (operator exp) env)
26                 (list-of-values (operands exp) env)))
27         (else
28          (error "Unknown expression type -- EVAL" exp))))
29 (define (apply procedure arguments)
30   (cond ((primitive-procedure? procedure)
31          (apply-primitive-procedure procedure arguments))
32         ((compound-procedure? procedure)
33          (eval-sequence
34            (procedure-body procedure)
35            (extend-environment
36              (procedure-parameters procedure)
37              arguments
38              (procedure-environment procedure))))
39         (else
40          (error
41           "Unknown procedure type -- APPLY" procedure))))
42 
43 (define (list-of-values exps env)
44   (if (no-operands? exps)
45       '()
46       (cons (eval (first-operand exps) env)
47             (list-of-values (rest-operands exps) env))))
48 
49 (define (tagged-list? exp tag)
50   (if (pair? exp)
51       (eq? (car exp) tag)
52       false))
53 
54 ;; self-evaluating/variable/quoted
55 (define (self-evaluating? exp)
56   (cond ((number? exp) true)
57         ((string? exp) true)
58         (else false)))
59 (define (variable? exp) (symbol? exp))
60 (define (quoted? exp)
61   (tagged-list? exp 'quote))
62 (define (text-of-quotation exp) (cadr exp))
63 
64 ;; assignment/definition
65 (define (assignment? exp)
66   (tagged-list? exp 'set!))
67 (define (assignment-variable exp) (cadr exp))
68 (define (assignment-value exp) (caddr exp))
69 (define (definition? exp)
70   (tagged-list? exp 'define))
71 (define (definition-variable exp)
72   (if (symbol? (cadr exp))
73       (cadr exp)
74       (caadr exp)))
75 (define (definition-value exp)
76   (if (symbol? (cadr exp))
77       (caddr exp)
78       (make-lambda (cdadr exp)   ; formal parameters
79                    (cddr exp)))) ; body
80 (define (eval-assignment exp env)
81   (set-variable-value! (assignment-variable exp)
82                        (eval (assignment-value exp) env)
83                        env)
84   'ok)
85 (define (eval-definition exp env)
86   (define-variable! (definition-variable exp)
87                     (eval (definition-value exp) env)
88                     env)
89   'ok)
90 (define (make-definition var val)
91   `(define ,var ,val))
92 
93 ;; make-unbound!
94 
95 (define (unbound? exp)
96   (tagged-list? exp 'make-unbound!))
97 (define (unbound-var exp)
98   (cadr exp))
99 (define (eval-unbound exp env)
100   (remove-binding-from-frame! (unbound-var exp) (first-frame env)))
101 
102 
103 
104 ;; if/and/or
105 (define (if? exp) (tagged-list? exp 'if))
106 (define (if-predicate exp) (cadr exp))
107 (define (if-consequent exp) (caddr exp))
108 (define (if-alternative exp)
109   (if (not (null? (cdddr exp)))
110       (cadddr exp)
111       'false))
112 (define (make-if predicate consequent alternative)
113   (list 'if predicate consequent alternative))
114 (define (eval-if exp env)
115   (if (true? (eval (if-predicate exp) env))
116       (eval (if-consequent exp) env)
117       (eval (if-alternative exp) env)))
118 
119 (define (and? exp)
120   (tagged-list? exp 'and))
121 (define (and-clauses exp)
122   (cdr exp))
123 (define (or? exp)
124   (tagged-list? exp 'or))
125 (define (or-clauses exp)
126   (cdr exp))
127 (define (eval-and exp env)
128   (define (eval-clauses clauses)
129     (cond ((null? clauses) true)
130 	  ((null? (cdr clauses)) (eval (car clauses) env))
131 	  (else (and (eval (car clauses) env)
132 		     (eval-clauses (cdr clauses))))))
133   (eval-clauses (and-clauses exp)))
134 (define (eval-or exp env)
135   (define (eval-clauses clauses)
136     (if (null? clauses)
137 	false
138 	(or (eval (car clauses) env)
139 	    (eval-clauses (cdr clauses)))))
140   (eval-clauses (or-clauses exp)))
141 
142 
143 ;; lambda/let/let*
144 (define (lambda? exp) (tagged-list? exp 'lambda))
145 (define (lambda-parameters exp) (cadr exp))
146 (define (lambda-body exp) (cddr exp))
147 (define (make-lambda parameters body)
148   (cons 'lambda (cons parameters body)))
149 
150 (define (make-let vars vals body)
151   (cons 'let
152 	(cons (map list vars vals)
153 	      body)))
154 (define (let? exp)
155   (and (tagged-list? exp 'let)
156        (not (symbol? (cadr exp)))))
157 (define (let-vars exp)
158   (map car (cadr exp)))
159 (define (let-vals exp)
160   (map cadr (cadr exp)))
161 (define (let-body exp)
162   (cddr exp))
163 (define (let->combination exp)
164   (make-application (make-lambda (let-vars exp) (let-body exp))
165 		    (let-vals exp)))
166 (define (named-let? exp)
167   (and (tagged-list? exp 'let)
168        (symbol? (cadr exp))))
169 (define (named-let-name exp)
170   (cadr exp))
171 (define (named-let-vars exp)
172   (map car (caddr exp)))
173 (define (named-let-vals exp)
174   (map cadr (caddr exp)))
175 (define (named-let-body exp)
176   (cdddr exp))
177 (define (named-let->combination exp)
178   (sequence->exp
179    (list (make-definition (named-let-name exp)
180 			  (make-lambda (named-let-vars exp)
181 				       (named-let-body exp)))
182 	 (make-application (named-let-name exp)
183 			   (named-let-vals exp)))))
184 (define (make-named-let name vars vals body)
185   (cons 'let 
186 	(cons name
187 	      (cons (map list vars vals)
188 		    body))))
189 
190 (define (make-application op args)
191   (cons op args))
192 
193 (define (let*? exp)
194   (tagged-list? exp 'let*))
195 (define let*-vars let-vars)
196 (define let*-vals let-vals)
197 (define let*-body let-body)
198 (define (let*->nested-lets exp)
199   (define (expand-lets vars vals)
200     (if (null? (cdr vars))
201 	(make-let (list (car vars)) 
202 		  (list (car vals))
203 		  (let*-body exp))
204 	(make-let (list (car vars))
205 		  (list (car vals))
206 		  (list (expand-lets (cdr vars) (cdr vals))))))
207   (let ((vars (let*-vars exp))
208 	(vals (let*-vals exp)))
209     (if (null? vars)
210 	(sequence->exp (let*-body exp))
211 	(expand-lets vars vals))))
212 
213 ;; do loop
214 (define (do? exp)
215   (tagged-list? exp 'do))
216 (define (do-vars exp)
217   (map car (cadr exp)))
218 (define (do-inits exp)
219   (map cadr (cadr exp)))
220 (define (do-steps exp)
221   (map (lambda (var-init-step)
222 	 (if (null? (cddr var-init-step))
223 	     (car var-init-step)
224 	     (caddr var-init-step)))
225        (cadr exp)))
226 (define (do-test exp)
227   (caaddr exp))
228 (define (do-expressions exp)
229   (if (null? (cdaddr exp))
230       (caddr exp)
231       (cdaddr exp)))
232 (define (do-commands exp)
233   (cdddr exp))
234 (define (do->combination exp)
235   (make-named-let
236    'do-iter
237    (do-vars exp)
238    (do-inits exp)
239    (list
240     (make-if
241      (do-test exp)
242      (sequence->exp (do-expressions exp))
243      (sequence->exp
244       (append (do-commands exp)
245 	      (list (make-application
246 		     'do-iter
247 		     (do-steps exp)))))))))
248 
249 
250 ;; begin/sequence
251 (define (begin? exp) (tagged-list? exp 'begin))
252 (define (begin-actions exp) (cdr exp))
253 (define (last-exp? seq) (null? (cdr seq)))
254 (define (first-exp seq) (car seq))
255 (define (rest-exps seq) (cdr seq))
256 (define (sequence->exp seq)
257   (cond ((null? seq) seq)
258         ((last-exp? seq) (first-exp seq))
259         (else (make-begin seq))))
260 (define (make-begin seq) (cons 'begin seq))
261 (define (eval-sequence exps env)
262   (cond ((last-exp? exps) (eval (first-exp exps) env))
263         (else (eval (first-exp exps) env)
264               (eval-sequence (rest-exps exps) env))))
265 
266 ;; application
267 (define (application? exp) (pair? exp))
268 (define (operator exp) (car exp))
269 (define (operands exp) (cdr exp))
270 (define (no-operands? ops) (null? ops))
271 (define (first-operand ops) (car ops))
272 (define (rest-operands ops) (cdr ops))
273 
274 ;; cond
275 (define (cond? exp) (tagged-list? exp 'cond))
276 (define (cond-clauses exp) (cdr exp))
277 (define (cond-else-clause? clause)
278   (eq? (cond-predicate clause) 'else))
279 (define (cond-predicate clause) (car clause))
280 (define (cond-actions clause) (cdr clause))
281 (define (cond-extended-clause? clause)
282   (and (not (null? (cdr clause))) (eq? (cadr clause) '=>)))
283 (define (cond-extended-proc clause)
284   (caddr clause))
285 (define (cond->if exp)
286   (expand-clauses (cond-clauses exp)))
287 (define (expand-clauses clauses)
288   (if (null? clauses)
289       'false                          ; no else clause
290       (let ((first (car clauses))
291             (rest (cdr clauses)))
292         (if (cond-else-clause? first)
293             (if (null? rest)
294                 (sequence->exp (cond-actions first))
295                 (error "ELSE clause isn't last -- COND->IF"
296                        clauses))
297 	    (if (cond-extended-clause? first)
298 		(make-if (cond-predicate first)
299 			 (make-application
300 			  (cond-extended-proc first)
301 			  (list (cond-predicate first)))
302 			 (expand-clauses rest))
303 		(make-if (cond-predicate first)
304 			 (sequence->exp (cond-actions first))
305 			 (expand-clauses rest)))))))
306 (define (true? x)
307   (not (eq? x false)))
308 (define (false? x)
309   (eq? x false))
310 
311 ;; procedure
312 (define (make-procedure parameters body env)
313   (list 'procedure parameters (scan-out-defines body) env))
314 (define (compound-procedure? p)
315   (tagged-list? p 'procedure))
316 (define (procedure-parameters p) (cadr p))
317 (define (procedure-body p) (caddr p))
318 (define (procedure-environment p) (cadddr p))
319 
320 ;; environment
321 (define (enclosing-environment env) (cdr env))
322 (define (first-frame env) (car env))
323 (define the-empty-environment '())
324 (define (make-frame variables values)
325   (cons variables values))
326 (define (frame-variables frame) (car frame))
327 (define (frame-values frame) (cdr frame))
328 (define (add-binding-to-frame! var val frame)
329   (set-car! frame (cons var (car frame)))
330   (set-cdr! frame (cons val (cdr frame))))
331 (define (extend-environment vars vals base-env)
332   (if (= (length vars) (length vals))
333       (cons (make-frame vars vals) base-env)
334       (if (< (length vars) (length vals))
335           (error "Too many arguments supplied" vars vals)
336           (error "Too few arguments supplied" vars vals))))
337 (define (lookup-variable-value var env)
338   (define (env-loop env)
339     (define (scan vars vals)
340       (cond ((null? vars)
341              (env-loop (enclosing-environment env)))
342             ((eq? var (car vars))
343 	     (let ((val (car vals)))
344 	       (if (eq? val '*unassigned*)
345 		   (error "Var not yet defined -- LOOKUP-VARIABLE-VALUE" var)
346 		   val)))
347             (else (scan (cdr vars) (cdr vals)))))
348     (if (eq? env the-empty-environment)
349         (error "Unbound variable" var)
350         (let ((frame (first-frame env)))
351           (scan (frame-variables frame)
352                 (frame-values frame)))))
353   (env-loop env))
354 (define (set-variable-value! var val env)
355   (define (env-loop env)
356     (define (scan vars vals)
357       (cond ((null? vars)
358              (env-loop (enclosing-environment env)))
359             ((eq? var (car vars))
360              (set-car! vals val))
361             (else (scan (cdr vars) (cdr vals)))))
362     (if (eq? env the-empty-environment)
363         (error "Unbound variable -- SET!" var)
364         (let ((frame (first-frame env)))
365           (scan (frame-variables frame)
366                 (frame-values frame)))))
367   (env-loop env))
368 (define (define-variable! var val env)
369   (let ((frame (first-frame env)))
370     (define (scan vars vals)
371       (cond ((null? vars)
372              (add-binding-to-frame! var val frame))
373             ((eq? var (car vars))
374              (set-car! vals val))
375             (else (scan (cdr vars) (cdr vals)))))
376     (scan (frame-variables frame)
377           (frame-values frame))))
378 
379 (define (remove-binding-from-frame! var frame)
380   (define (scan vars vals)
381     (cond ((null? (cdr vars))
382 	   (error "Binding not found -- REMOVE-BINDING-FROM-FRAME!" var))
383 	  ((eq? var (cadr vars))
384 	   (set-cdr! vars (cddr vars))
385 	   (set-cdr! vals (cddr vals)))
386 	  (else (scan (cdr vars) (cdr vals)))))
387   (let ((vars (frame-variables frame))
388 	(vals (frame-values frame)))
389     (if (eq? var (car vars))
390 	(begin (set-car! frame (cdr vars))
391 	       (set-cdr! frame (cdr vals)))
392 	(scan vars vals))))
393 
394 ;; primitives
395 (define (primitive-procedure? proc)
396   (tagged-list? proc 'primitive))
397 (define (primitive-implementation proc) (cadr proc))
398 (define primitive-procedures
399   (list (list 'car car)
400         (list 'cdr cdr)
401 	(list 'caar caar)
402 	(list 'cadr cadr)
403 	(list 'cddr cddr)
404         (list 'cons cons)
405         (list 'null? null?)
406 	(list '* *)
407 	(list '/ /)
408 	(list '+ +)
409 	(list '- -)
410 	(list '= =)
411 	(list '< <)
412 	(list '> >)
413 	(list '<= <=)
414 	(list '>= >=)
415 	(list 'remainder remainder)
416 	(list 'eq? eq?)
417 	(list 'equal? equal?)
418 	(list 'display display)))
419 (define (primitive-procedure-names)
420   (map car
421        primitive-procedures))
422 (define (primitive-procedure-objects)
423   (map (lambda (proc) (list 'primitive (cadr proc)))
424        primitive-procedures))
425 (define (apply-primitive-procedure proc args)
426   (apply-in-underlying-scheme
427    (primitive-implementation proc) args))
428 
429 ;; driver-loop
430 (define input-prompt ";;; M-Eval input:")
431 (define output-prompt ";;; M-Eval value:")
432 (define (driver-loop)
433   (prompt-for-input input-prompt)
434   (let ((input (read)))
435     (let ((output (eval input the-global-environment)))
436       (announce-output output-prompt)
437       (user-print output)))
438   (driver-loop))
439 (define (prompt-for-input string)
440   (newline) (newline) (display string) (newline))
441 
442 (define (announce-output string)
443   (newline) (display string) (newline))
444 (define (user-print object)
445   (if (compound-procedure? object)
446       (display (list 'compound-procedure
447                      (procedure-parameters object)
448                      (procedure-body object)
449                      '<procedure-env>))
450       (display object)))
451 (define (setup-environment)
452   (let ((initial-env
453          (extend-environment (primitive-procedure-names)
454                              (primitive-procedure-objects)
455                              the-empty-environment)))
456     (define-variable! 'true true initial-env)
457     (define-variable! 'false false initial-env)
458     initial-env))
459 (define the-global-environment (setup-environment))
460 
461 ;; auxiliary
462 (define (test-case actual expected)
463   (newline)
464   (display "Actual:   ")
465   (display actual)
466   (newline)
467   (display "Expected: ")
468   (display expected)
469   (newline))
470 (define (geval exp) ;; eval globally
471   (eval exp the-global-environment))
472 (define (test-eval exp expected)
473   (test-case (geval exp) expected))
474 
475 
476 ;;  Exercise 4.16.  In this exercise we implement the method just described for interpreting internal definitions. We assume that the evaluator supports let (see exercise 4.6).
477 
478 ;; a.  Change lookup-variable-value (section 4.1.3) to signal an error if the value it finds is the symbol *unassigned*.
479 
480 ;; see above
481 
482 ;; b.  Write a procedure scan-out-defines that takes a procedure body and returns an equivalent one that has no internal definitions, by making the transformation described above.
483 
484 ;; (lambda <vars>
485 ;;   (define u <e1>)
486 ;;   (define v <e2>)
487 ;;   <e3>)
488 
489 ;; would be transformed into
490 
491 ;; (lambda <vars>
492 ;;   (let ((u '*unassigned*)
493 ;;         (v '*unassigned*))
494 ;;     (set! u <e1>)
495 ;;     (set! v <e2>)
496 ;;     <e3>))
497 
498 ;; (newline)
499 ;; (display "test")
500 ;; (newline)
501 
502 (define (make-assignment var val)
503   (list 'set! var val))
504 
505 ;; (define (scan-out-defines body)
506 ;;   (define (scan-exps remaining-exps scanned-exps vars vals)
507 ;;     (if (null? remaining-exps) 
508 ;; 	(list (make-let vars 
509 ;; 		  (map (lambda (var)
510 ;; 			 ''*unassigned*)
511 ;; 		       vars)
512 ;; 		  (append 
513 ;; 		   (map (lambda (var val)
514 ;; 			  (make-assignment var val))
515 ;; 			vars 
516 ;; 			vals)
517 ;; 		   scanned-exps)))
518 ;; 	(let ((first (car remaining-exps))
519 ;; 	      (rest (cdr remaining-exps)))
520 ;; 	  (if (definition? first)
521 ;; 	      (scan-exps rest
522 ;; 			 scanned-exps
523 ;; 			 (append vars (list (definition-variable first)))
524 ;; 			 (append vals (list (definition-value first))))			 
525 ;; 	      (scan-exps rest
526 ;; 			 (append scanned-exps (list first))
527 ;; 			 vars
528 ;; 			 vals)))))
529 ;;   (scan-exps body '() '() '()))
530 
531 (define (scan-out-defines body)
532   (let* ((definitions (filter definition? body))
533 	 (vars (map definition-variable definitions))
534 	 (unassigneds (map (lambda (var) ''*unassigned*) 
535 			   vars))
536 	 (vals (map definition-value definitions))
537 	 (assignments 
538 	  (map (lambda (var val)
539 		 (make-assignment var val))
540 	       vars vals))
541 	 (exps (remove definition? body)))
542     (list
543      (make-let vars
544 	       unassigneds
545 	       (append assignments exps)))))
546 
547 
548 ;; ((let ((even? (quote *unassigned))
549 ;;        (odd? (quote *unassigned)))
550 ;;    (set! even? 
551 ;; 	 (lambda (n) (if (= n 0) true (odd? (- n 1)))))
552 ;;    (set! odd? 
553 ;; 	 (lambda (n) (if (= n 0) false (even? (- n 1)))))
554 ;;    (even? x)))
555 
556 
557 
558 ;; (define (make-let vars vals body)
559 ;;   (cons 'let
560 ;; 	(cons (map list vars vals)
561 ;; 	      body)))
562 
563 
564 ;; c.  Install scan-out-defines in the interpreter, either in make-procedure or in procedure-body (see section 4.1.3). Which place is better? Why? 
565 
566 ;; better to put it in make-procedure. Otherwise, every time the procedure-body is requested for an application, we'd have to repeat the scanning. This would make applications quite slow and would be very inefficient.
567 
568 ;; scan-out-defines
569 
570 ;; (geval
571 ;;  '(define (f x)
572 ;;     (define (even? n)
573 ;;       (if (= n 0)
574 ;; 	  true
575 ;; 	  (odd? (- n 1))))
576 ;;     (define (odd? n)
577 ;;       (if (= n 0)
578 ;; 	  false
579 ;; 	  (even? (- n 1))))
580 ;;     (even? x)))
581 ;; (test-eval '(f 5) false)
582 ;; (test-eval '(f 10) true)
583 
584 ;; (test-case
585 ;;  (scan-out-defines 
586 ;;   '((define (even? n)
587 ;;       (if (= n 0)
588 ;; 	  true
589 ;; 	  (odd? (- n 1))))
590 ;;     (define (odd? n)
591 ;;       (if (= n 0)
592 ;; 	  false
593 ;; 	  (even? (- n 1))))
594 ;;     (even? x)))
595 ;;  '(let ((even? '*unassigned*)
596 ;; 	(odd? '*unassigned*))
597 ;;     (set! even? 
598 ;; 	  (lambda (n) 
599 ;; 	    (if (= n 0)
600 ;; 		true
601 ;; 		(odd? (- n 1)))))
602 ;;     (set! odd? 
603 ;; 	  (lambda (n)
604 ;; 	    (if (= n 0)
605 ;; 		false
606 ;; 		(even? (- n 1)))))
607 ;;     (even? x)))
608 
609 ;; ((let ((even? (quote *unassigned*))
610 ;;        (odd? (quote *unassigned*)))
611 ;;    (set! even? 
612 ;; 	 (lambda (n) (if (= n 0) true (odd? (- n 1)))))
613 ;;    (set! odd? 
614 ;; 	 (lambda (n) (if (= n 0) false (even? (- n 1)))))
615 ;;    (even? x)))
616 
617 ;; (geval
618 ;;  '(let ((x 5))
619 ;;     (define y x)
620 ;;     (define x 3)
621 ;;     (+ x y)))
622 ;; signal an error because x is undefined if variables are scanned out
623 
624 
625 
626 
627 ;; test-suite
628 
629 ;; procedure definitions
630 
631 (geval 
632  '(define (assoc key records)
633     (cond ((null? records) false)
634 	  ((equal? key (caar records)) (car records))
635 	  (else (assoc key (cdr records))))))
636 
637 (geval
638  '(define (map proc list)
639     (if (null? list)
640 	'()
641 	(cons (proc (car list))
642 	      (map proc (cdr list))))))
643 
644 (geval 
645  '(define (accumulate op initial sequence)
646     (if (null? sequence)
647 	initial
648 	(op (car sequence)
649 	    (accumulate op initial (cdr sequence))))))
650 
651 ;; all special forms
652 (test-eval '(begin 5 6) 6)
653 (test-eval '10 10)
654 (geval '(define x 3))
655 (test-eval 'x 3)
656 (test-eval '(set! x -25) 'ok)
657 (test-eval 'x -25)
658 (geval '(define z (lambda (x y) (+ x (* x y)))))
659 (test-eval '(z 3 4) 15)
660 (test-eval '(cond ((= x -2) 'x=-2)
661 		  ((= x -25) 'x=-25)
662 		  (else 'failed))
663 	   'x=-25)
664 (test-eval '(if true false true) false)
665 (test-eval 
666  '(let ((x 4) (y 7))
667     (+ x y (* x y)))
668  (+ 4 7 (* 4 7)))
669 
670 
671 ;; and/or
672 (geval '(define x (+ 3 8)))
673 (test-eval '(and 0 true x) 11)
674 (test-eval '(and 0 true x false) false)
675 (test-eval '(and 0 true x (set! x -2) false) false)
676 (test-eval 'x -2)
677 (test-eval '(and 0 true x false (set! x -5)) false)
678 (test-eval 'x -2)
679 (test-eval '(or false (set! x 25)) 'ok)
680 (test-eval 'x 25)
681 (test-eval '(or (set! x 2) (set! x 4)) 'ok)
682 (test-eval 'x 2)
683 (test-eval '(or false (set! x 25) true false) 'ok)
684 (test-eval 'x 25)
685 (test-eval '(or ((lambda (x) x) 5)) 5)
686 (test-eval '(or (begin (set! x (+ x 1)) x)) 26)
687 
688 
689 ;; cond
690 
691 (test-eval 
692  '(cond ((assoc 'b '((a 1) (b 2))) => cadr)
693 	(else false))
694  2)
695 
696 (test-eval
697  '(cond ((= 3 4) 'not-true)
698 	((= (* 2 4) 3) 'also-false)
699 	((map (lambda (x)
700 		(* x (+ x 1)))
701 	      '(2 4 1 9))
702 	 =>
703 	 (lambda (x)
704 	   (accumulate + 0 x)))
705 	(else 'never-reach))
706  118)
707 ;; '(6 20 2 90)
708 
709 
710 ;; procedure definition and application
711 (geval
712  '(define (factorial n)
713     (if (= n 0)
714 	1
715 	(* n (factorial (- n 1))))))
716 (test-eval '(factorial 5) 120)
717 
718 ;; map
719 
720 (test-eval
721  '(map (lambda (x)
722 	 (* x (+ x 1)))
723        '(2 1 4 2 8 3))
724  '(6 2 20 6 72 12))
725 ;; accumulate
726 
727 (test-eval
728  '(accumulate + 0 '(1 2 3 4 5))
729  15)
730 
731 ;; make-let
732 (test-eval 
733  (make-let '(x y) '(3 5) '((+ x y)))
734  8)
735 (test-eval 
736  '(let ()
737     5)
738  5)
739 (test-eval
740  '(let ((x 3))
741     x)
742  3)
743 (test-eval
744  '(let ((x 3)
745 	(y 5))
746     (+ x y))
747  8)
748 (test-eval 
749  '(let ((x 3)
750 	(y 2))
751     (+ (let ((x (+ y 2))
752 	     (y x))
753 	 (* x y))
754        x y))
755  (+ (* 4 3) 3 2))
756 (test-eval
757  '(let ((x 6)
758 	(y (let ((x 2))
759 	     (+ x 3)))
760 	(z (let ((a (* 3 2)))
761 	     (+ a 3))))
762     (+ x y z))
763  (+ 6 5 9))
764     
765 
766 ;; let*
767 
768 (test-eval
769  '(let* ((x 3)
770 	 (y (+ x 2))
771 	 (z (+ x y 5)))
772     (* x z))
773  39)
774 
775 (test-eval
776  '(let* ()
777     5)
778  5)
779 (test-eval
780  '(let* ((x 3))
781     (let* ((y 5))
782       (+ x y)))
783  8)
784 
785 (test-eval 
786  '(let* ((x 3)
787 	 (y (+ x 1)))
788     (+ (let* ((x (+ y 2))
789 	      (y x))
790 	 (* x y))
791        x y))
792  (+ (* 6 6) 3 4))
793 (test-eval
794  '(let* ((x 6)
795 	 (y (let* ((x 2)
796 		   (a (let* ((x (* 3 x)))
797 			(+ x 2))))       
798 	      (+ x a)))                  
799 	 (z (+ x y)))                    
800     (+ x y z))
801  32)
802 
803 ;; named-let
804 
805 (test-eval
806  '(let eight ()
807     5
808     7
809     8)
810  8)
811 (test-eval
812  '(let loop ((count 0))
813     (if (= 100 count)
814 	count
815 	(loop (+ count 1))))
816  100)
817 (geval
818  '(define (prime? x)
819     (let prime-iter ((i 2))
820       (cond ((> (* i i) x) true)
821 	    ((= (remainder x i) 0) false)
822 	    (else (prime-iter (+ i 1)))))))
823 (test-eval
824  '(let primes ((x 2)
825 	       (n 20))
826     (cond ((= n 0) '())
827 	  ((prime? x) 
828 	   (cons x
829 		 (primes (+ x 1) (- n 1))))
830 	  (else (primes (+ x 1) n))))
831  '(2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71))
832 
833 (geval
834  '(define (fib n)
835     (let fib-iter ((a 1)
836 		   (b 0)
837 		   (count n))
838       (if (= count 0)
839 	  b
840 	  (fib-iter (+ a b) a (- count 1))))))
841 (test-eval '(fib 19) 4181)
842 
843 ;; do-loop	  
844 (test-eval
845  '(let ((y 0))
846     (do ((x 0 (+ x 1)))
847 	((= x 5) y)
848       (set! y (+ y 1))))
849  5)
850 (test-eval
851  '(do ()
852       (true))
853  true)
854 (test-eval
855  '(do ()
856       (true 5))
857  5)
858 (test-eval
859  '(let ((y 0))
860     (do ()
861 	((= y 5) y)
862       (set! y (+ y 1))))
863  5)
864 
865 (test-eval
866  '(do ((y '(1 2 3 4)))
867       ((null? y))
868     (set! y (cdr y)))
869  true)
870 (test-eval
871  '(let ((y 0))
872     (do ((x 0 (+ x 1)))
873 	((= x 5) y)
874       (set! y (+ y 1))))
875  5)
876 (test-eval
877  '(let ((x '(1 3 5 7 9)))
878     (do ((x x (cdr x))
879 	 (sum 0 (+ sum (car x))))
880 	((null? x) sum)))
881  25)
882 (test-eval 
883  '(let ((z '()))
884     (do ((x '(1 2 3 4) (cdr x))
885 	 (y '(1 2 3 4 5 6 7 8) (cddr y)))
886 	((null? x) y x z)
887       (set! z (cons (car x) z))))
888  '(4 3 2 1))
889 
890 
891 
892 ;; make-unbound!
893 
894 (test-eval
895  '(let ((x 3))
896     (let ((x 5))
897       (make-unbound! x)
898       (* x x)))
899  9)
900 
901 (test-eval
902  '(let ((x 3))
903     (let ((x 5))
904       (define y x)
905       (make-unbound! x)
906       (* y x)))
907  15)
908 
909 (test-eval
910  '(let ((y -1) (x 3))
911     (let ((y 0.5) (x 5))
912       (define a x)
913       (define b y)
914       (make-unbound! x)
915       (make-unbound! y)
916       (* a b x y)))
917  (* 5 3 -1 0.5))
918 
919 (test-eval
920  '(let ((x 3) (y 4))
921     (let ((x 5))
922       (make-unbound! x)
923       (+ x 4)))
924  7)
925 
926 (test-eval 
927  '(let ((a 1) (b 2) (c 3) (d 4))
928     (make-unbound! b)
929     (+ a c d))
930  (+ 1 3 4))
931 
932 (test-eval
933  '(let ((x 4) (y 5))
934     (let ((a 1) (b 2) (c 3))
935       (let ((x (+ a b)) (y (+ c a)))
936 	(make-unbound! x)
937 	(let ((a x) (b (+ x y)))
938 	  (define z b)
939 	  (make-unbound! b)
940 	  (* (+ a z)
941 	     (+ a b y))))))
942  (* (+ 4 8)
943     (+ 4 2 4)))
944  
945 ;; x 3 -- y 4
946 ;; x 4 -- y 4
947 ;; a 4 -- b 4
948 ;; a 4 -- b 2