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   (display "Evaluating: ")
263   (newline)
264   (user-print exps)
265   (cond ((last-exp? exps) (eval (first-exp exps) env))
266         (else (eval (first-exp exps) env)
267               (eval-sequence (rest-exps exps) env))))
268 
269 ;; application
270 (define (application? exp) (pair? exp))
271 (define (operator exp) (car exp))
272 (define (operands exp) (cdr exp))
273 (define (no-operands? ops) (null? ops))
274 (define (first-operand ops) (car ops))
275 (define (rest-operands ops) (cdr ops))
276 
277 ;; cond
278 (define (cond? exp) (tagged-list? exp 'cond))
279 (define (cond-clauses exp) (cdr exp))
280 (define (cond-else-clause? clause)
281   (eq? (cond-predicate clause) 'else))
282 (define (cond-predicate clause) (car clause))
283 (define (cond-actions clause) (cdr clause))
284 (define (cond-extended-clause? clause)
285   (and (not (null? (cdr clause))) (eq? (cadr clause) '=>)))
286 (define (cond-extended-proc clause)
287   (caddr clause))
288 (define (cond->if exp)
289   (expand-clauses (cond-clauses exp)))
290 (define (expand-clauses clauses)
291   (if (null? clauses)
292       'false                          ; no else clause
293       (let ((first (car clauses))
294             (rest (cdr clauses)))
295         (if (cond-else-clause? first)
296             (if (null? rest)
297                 (sequence->exp (cond-actions first))
298                 (error "ELSE clause isn't last -- COND->IF"
299                        clauses))
300 	    (if (cond-extended-clause? first)
301 		(make-if (cond-predicate first)
302 			 (make-application
303 			  (cond-extended-proc first)
304 			  (list (cond-predicate first)))
305 			 (expand-clauses rest))
306 		(make-if (cond-predicate first)
307 			 (sequence->exp (cond-actions first))
308 			 (expand-clauses rest)))))))
309 (define (true? x)
310   (not (eq? x false)))
311 (define (false? x)
312   (eq? x false))
313 
314 ;; procedure
315 (define (make-procedure parameters body env)
316   (list 'procedure parameters (scan-out-defines body) env))
317 (define (compound-procedure? p)
318   (tagged-list? p 'procedure))
319 (define (procedure-parameters p) (cadr p))
320 (define (procedure-body p) (caddr p))
321 (define (procedure-environment p) (cadddr p))
322 
323 ;; environment
324 (define (enclosing-environment env) (cdr env))
325 (define (first-frame env) (car env))
326 (define the-empty-environment '())
327 (define (make-frame variables values)
328   (cons variables values))
329 (define (frame-variables frame) (car frame))
330 (define (frame-values frame) (cdr frame))
331 (define (add-binding-to-frame! var val frame)
332   (set-car! frame (cons var (car frame)))
333   (set-cdr! frame (cons val (cdr frame))))
334 (define (extend-environment vars vals base-env)
335   (if (= (length vars) (length vals))
336       (cons (make-frame vars vals) base-env)
337       (if (< (length vars) (length vals))
338           (error "Too many arguments supplied" vars vals)
339           (error "Too few arguments supplied" vars vals))))
340 (define (lookup-variable-value var 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 	     (let ((val (car vals)))
347 	       (if (eq? val '*unassigned*)
348 		   (error "Var not yet defined -- LOOKUP-VARIABLE-VALUE" var)
349 		   val)))
350             (else (scan (cdr vars) (cdr vals)))))
351     (if (eq? env the-empty-environment)
352         (error "Unbound variable" var)
353         (let ((frame (first-frame env)))
354           (scan (frame-variables frame)
355                 (frame-values frame)))))
356   (env-loop env))
357 (define (set-variable-value! var val env)
358   (define (env-loop env)
359     (define (scan vars vals)
360       (cond ((null? vars)
361              (env-loop (enclosing-environment env)))
362             ((eq? var (car vars))
363              (set-car! vals val))
364             (else (scan (cdr vars) (cdr vals)))))
365     (if (eq? env the-empty-environment)
366         (error "Unbound variable -- SET!" var)
367         (let ((frame (first-frame env)))
368           (scan (frame-variables frame)
369                 (frame-values frame)))))
370   (env-loop env))
371 (define (define-variable! var val env)
372   (let ((frame (first-frame env)))
373     (define (scan vars vals)
374       (cond ((null? vars)
375              (add-binding-to-frame! var val frame))
376             ((eq? var (car vars))
377              (set-car! vals val))
378             (else (scan (cdr vars) (cdr vals)))))
379     (scan (frame-variables frame)
380           (frame-values frame))))
381 
382 (define (remove-binding-from-frame! var frame)
383   (define (scan vars vals)
384     (cond ((null? (cdr vars))
385 	   (error "Binding not found -- REMOVE-BINDING-FROM-FRAME!" var))
386 	  ((eq? var (cadr vars))
387 	   (set-cdr! vars (cddr vars))
388 	   (set-cdr! vals (cddr vals)))
389 	  (else (scan (cdr vars) (cdr vals)))))
390   (let ((vars (frame-variables frame))
391 	(vals (frame-values frame)))
392     (if (eq? var (car vars))
393 	(begin (set-car! frame (cdr vars))
394 	       (set-cdr! frame (cdr vals)))
395 	(scan vars vals))))
396 
397 ;; primitives
398 (define (primitive-procedure? proc)
399   (tagged-list? proc 'primitive))
400 (define (primitive-implementation proc) (cadr proc))
401 (define primitive-procedures
402   (list (list 'car car)
403         (list 'cdr cdr)
404 	(list 'caar caar)
405 	(list 'cadr cadr)
406 	(list 'cddr cddr)
407         (list 'cons cons)
408         (list 'null? null?)
409 	(list '* *)
410 	(list '/ /)
411 	(list '+ +)
412 	(list '- -)
413 	(list '= =)
414 	(list '< <)
415 	(list '> >)
416 	(list '<= <=)
417 	(list '>= >=)
418 	(list 'remainder remainder)
419 	(list 'eq? eq?)
420 	(list 'equal? equal?)
421 	(list 'display display)))
422 (define (primitive-procedure-names)
423   (map car
424        primitive-procedures))
425 (define (primitive-procedure-objects)
426   (map (lambda (proc) (list 'primitive (cadr proc)))
427        primitive-procedures))
428 (define (apply-primitive-procedure proc args)
429   (apply-in-underlying-scheme
430    (primitive-implementation proc) args))
431 
432 ;; driver-loop
433 (define input-prompt ";;; M-Eval input:")
434 (define output-prompt ";;; M-Eval value:")
435 (define (driver-loop)
436   (prompt-for-input input-prompt)
437   (let ((input (read)))
438     (let ((output (eval input the-global-environment)))
439       (announce-output output-prompt)
440       (user-print output)))
441   (driver-loop))
442 (define (prompt-for-input string)
443   (newline) (newline) (display string) (newline))
444 
445 (define (announce-output string)
446   (newline) (display string) (newline))
447 (define (user-print object)
448   (if (compound-procedure? object)
449       (display (list 'compound-procedure
450                      (procedure-parameters object)
451                      (procedure-body object)
452                      '<procedure-env>))
453       (display object)))
454 (define (setup-environment)
455   (let ((initial-env
456          (extend-environment (primitive-procedure-names)
457                              (primitive-procedure-objects)
458                              the-empty-environment)))
459     (define-variable! 'true true initial-env)
460     (define-variable! 'false false initial-env)
461     initial-env))
462 (define the-global-environment (setup-environment))
463 
464 ;; auxiliary
465 (define (test-case actual expected)
466   (newline)
467   (display "Actual:   ")
468   (display actual)
469   (newline)
470   (display "Expected: ")
471   (display expected)
472   (newline))
473 (define (geval exp) ;; eval globally
474   (eval exp the-global-environment))
475 (define (test-eval exp expected)
476   (test-case (geval exp) expected))
477 
478 
479 ;;  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).
480 
481 ;; a.  Change lookup-variable-value (section 4.1.3) to signal an error if the value it finds is the symbol *unassigned*.
482 
483 ;; see above
484 
485 ;; 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.
486 
487 ;; (lambda <vars>
488 ;;   (define u <e1>)
489 ;;   (define v <e2>)
490 ;;   <e3>)
491 
492 ;; would be transformed into
493 
494 ;; (lambda <vars>
495 ;;   (let ((u '*unassigned*)
496 ;;         (v '*unassigned*))
497 ;;     (set! u <e1>)
498 ;;     (set! v <e2>)
499 ;;     <e3>))
500 
501 ;; (newline)
502 ;; (display "test")
503 ;; (newline)
504 
505 
506 (define (make-assignment var val)
507   (list 'set! var val))
508 
509 (define (scan-out-defines body)
510   (let* ((definitions (filter definition? body))
511 	 (vars (map definition-variable definitions))
512 	 (unassigneds (map (lambda (var) ''*unassigned*) 
513 			   vars))
514 	 (vals (map definition-value definitions))
515 	 (assignments 
516 	  (map (lambda (var val)
517 		 (make-assignment var val))
518 	       vars vals))
519 	 (exps (remove definition? body)))
520     (if (null? definitions)
521 	body
522 	(list
523 	 (make-let vars
524 		   unassigneds
525 		   (append assignments exps))))))
526 
527 ;; ((let ((even? (quote *unassigned*))
528 ;;        (odd? (quote *unassigned*)))
529 ;;    (set! even?
530 ;; 	 (lambda (n) 
531 
532 ;; 	   (if (= n 0) 
533 ;; 	       true
534 ;; 	       (odd? (- n 1)))))
535 ;;    (set! odd? 
536 ;; 	 (lambda (n)
537 ;; 	   (if (= n 0)
538 ;; 	       false
539 ;; 	       (even? (- n 1)))))
540 ;;    (even? x)))
541 
542 
543 
544 
545 ;; 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? 
546 
547 ;; 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.
548 
549 ;; scan-out-defines
550 
551 (geval
552  '(define (f x)
553     (define (even? n)
554       (if (= n 0)
555 	  true
556 	  (odd? (- n 1))))
557     (define (odd? n)
558       (if (= n 0)
559 	  false
560 	  (even? (- n 1))))
561     (even? x)))
562 (test-eval '(f 5) false)
563 (test-eval '(f 10) true)
564 
565 ;; (define f-proc (eval 'f the-global-environment))
566 ;; (procedure-body f-proc)
567 ;; ((let ((even? (quote *unassigned*)) (odd? (quote *unassigned*))) (set! even? (lambda (n) (if (= n 0) true (odd? (- n 1))))) (set! odd? (lambda (n) (if (= n 0) false (even? (- n 1))))) (even? x)))
568 ;; (user-print (procedure-body f-proc))
569 ;; ((let ((even? (quote *unassigned*)) (odd? (quote *unassigned*))) (set! even? (lambda (n) (if (= n 0) true (odd? (- n 1))))) (set! odd? (lambda (n) (if (= n 0) false (even? (- n 1))))) (even? x)))
570 ;; (first-exp (procedure-body f-proc))
571 ;; (let? (first-exp (procedure-body f-proc)))
572 
573 ;Value: #t
574 
575 ;; 1 ]=> (let->combination (first-exp (procedure-body f-proc)))
576 
577 ;Value 14: ((lambda (even? odd?) (set! even? (lambda (n) (if (= n 0) true (odd? (- n 1))))) (set! odd? (lambda (n) (if (= n 0) false (even? (- n 1))))) (even? x)) (quote *unassigned*) (quote *unassigned*))
578 
579 
580 ;Value 13: (let ((even? (quote *unassigned*)) (odd? (quote *unassigned*))) (set! even? (lambda (n) (if (= n 0) true (odd? (- n 1))))) (set! odd? (lambda (n) (if (= n 0) false (even? (- n 1))))) (even? x))
581 
582 ;; (operator (let->combination (first-exp (procedure-body f-proc))))
583 
584 ;Value 15: (lambda (even? odd?) (set! even? (lambda (n) (if (= n 0) true (odd? (- n 1))))) (set! odd? (lambda (n) (if (= n 0) false (even? (- n 1))))) (even? x))
585 
586 ;; 1 ]=> (lambda-parameters (operator (let->combination (first-exp (procedure-body f-proc)))))
587 
588 ;Value 16: (even? odd?)
589 
590 ;; ((set! even? (lambda (n) (if (= n 0) true (odd? (- n 1))))) (set! odd? (lambda (n) (if (= n 0) false (even? (- n 1))))) (even? x))
591 
592 ;; there is an infinite loop going on
593 ;; the problem is that we scan out definitions and construct a let
594 ;; but, the let itself implies another lambda expression. To
595 ;; evaluate that lambda expression, we must construct another procedure.
596 ;; But then, we have to scan out *that* procedure. It never ends...
597 
598 ;; (test-case
599 ;;  (scan-out-defines 
600 ;;   '((define (even? n)
601 ;;       (if (= n 0)
602 ;; 	  true
603 ;; 	  (odd? (- n 1))))
604 ;;     (define (odd? n)
605 ;;       (if (= n 0)
606 ;; 	  false
607 ;; 	  (even? (- n 1))))
608 ;;     (even? x)))
609 ;;  '(let ((even? '*unassigned*)
610 ;; 	(odd? '*unassigned*))
611 ;;     (set! even? 
612 ;; 	  (lambda (n) 
613 ;; 	    (if (= n 0)
614 ;; 		true
615 ;; 		(odd? (- n 1)))))
616 ;;     (set! odd? 
617 ;; 	  (lambda (n)
618 ;; 	    (if (= n 0)
619 ;; 		false
620 ;; 		(even? (- n 1)))))
621 ;;     (even? x)))
622 
623 ;; ((let ((even? (quote *unassigned*))
624 ;;        (odd? (quote *unassigned*)))
625 ;;    (set! even? 
626 ;; 	 (lambda (n) (if (= n 0) true (odd? (- n 1)))))
627 ;;    (set! odd? 
628 ;; 	 (lambda (n) (if (= n 0) false (even? (- n 1)))))
629 ;;    (even? x)))
630 
631 ;; (geval
632 ;;  '(let ((x 5))
633 ;;     (define y x)
634 ;;     (define x 3)
635 ;;     (+ x y)))
636 ;; signal an error because x is undefined if variables are scanned out
637 
638 
639 
640 
641 ;; test-suite
642 
643 ;; procedure definitions
644 
645 (geval 
646  '(define (assoc key records)
647     (cond ((null? records) false)
648 	  ((equal? key (caar records)) (car records))
649 	  (else (assoc key (cdr records))))))
650 
651 (geval
652  '(define (map proc list)
653     (if (null? list)
654 	'()
655 	(cons (proc (car list))
656 	      (map proc (cdr list))))))
657 
658 (geval 
659  '(define (accumulate op initial sequence)
660     (if (null? sequence)
661 	initial
662 	(op (car sequence)
663 	    (accumulate op initial (cdr sequence))))))
664 
665 ;; all special forms
666 (test-eval '(begin 5 6) 6)
667 (test-eval '10 10)
668 (geval '(define x 3))
669 (test-eval 'x 3)
670 (test-eval '(set! x -25) 'ok)
671 (test-eval 'x -25)
672 (geval '(define z (lambda (x y) (+ x (* x y)))))
673 (test-eval '(z 3 4) 15)
674 (test-eval '(cond ((= x -2) 'x=-2)
675 		  ((= x -25) 'x=-25)
676 		  (else 'failed))
677 	   'x=-25)
678 (test-eval '(if true false true) false)
679 (test-eval 
680  '(let ((x 4) (y 7))
681     (+ x y (* x y)))
682  (+ 4 7 (* 4 7)))
683 
684 
685 ;; and/or
686 (geval '(define x (+ 3 8)))
687 (test-eval '(and 0 true x) 11)
688 (test-eval '(and 0 true x false) false)
689 (test-eval '(and 0 true x (set! x -2) false) false)
690 (test-eval 'x -2)
691 (test-eval '(and 0 true x false (set! x -5)) false)
692 (test-eval 'x -2)
693 (test-eval '(or false (set! x 25)) 'ok)
694 (test-eval 'x 25)
695 (test-eval '(or (set! x 2) (set! x 4)) 'ok)
696 (test-eval 'x 2)
697 (test-eval '(or false (set! x 25) true false) 'ok)
698 (test-eval 'x 25)
699 (test-eval '(or ((lambda (x) x) 5)) 5)
700 (test-eval '(or (begin (set! x (+ x 1)) x)) 26)
701 
702 
703 ;; cond
704 
705 (test-eval 
706  '(cond ((assoc 'b '((a 1) (b 2))) => cadr)
707 	(else false))
708  2)
709 
710 (test-eval
711  '(cond ((= 3 4) 'not-true)
712 	((= (* 2 4) 3) 'also-false)
713 	((map (lambda (x)
714 		(* x (+ x 1)))
715 	      '(2 4 1 9))
716 	 =>
717 	 (lambda (x)
718 	   (accumulate + 0 x)))
719 	(else 'never-reach))
720  118)
721 ;; '(6 20 2 90)
722 
723 
724 ;; procedure definition and application
725 (geval
726  '(define (factorial n)
727     (if (= n 0)
728 	1
729 	(* n (factorial (- n 1))))))
730 (test-eval '(factorial 5) 120)
731 
732 ;; map
733 
734 (test-eval
735  '(map (lambda (x)
736 	 (* x (+ x 1)))
737        '(2 1 4 2 8 3))
738  '(6 2 20 6 72 12))
739 ;; accumulate
740 
741 (test-eval
742  '(accumulate + 0 '(1 2 3 4 5))
743  15)
744 
745 ;; make-let
746 (test-eval 
747  (make-let '(x y) '(3 5) '((+ x y)))
748  8)
749 (test-eval 
750  '(let ()
751     5)
752  5)
753 (test-eval
754  '(let ((x 3))
755     x)
756  3)
757 (test-eval
758  '(let ((x 3)
759 	(y 5))
760     (+ x y))
761  8)
762 (test-eval 
763  '(let ((x 3)
764 	(y 2))
765     (+ (let ((x (+ y 2))
766 	     (y x))
767 	 (* x y))
768        x y))
769  (+ (* 4 3) 3 2))
770 (test-eval
771  '(let ((x 6)
772 	(y (let ((x 2))
773 	     (+ x 3)))
774 	(z (let ((a (* 3 2)))
775 	     (+ a 3))))
776     (+ x y z))
777  (+ 6 5 9))
778     
779 
780 ;; let*
781 
782 (test-eval
783  '(let* ((x 3)
784 	 (y (+ x 2))
785 	 (z (+ x y 5)))
786     (* x z))
787  39)
788 
789 (test-eval
790  '(let* ()
791     5)
792  5)
793 (test-eval
794  '(let* ((x 3))
795     (let* ((y 5))
796       (+ x y)))
797  8)
798 
799 (test-eval 
800  '(let* ((x 3)
801 	 (y (+ x 1)))
802     (+ (let* ((x (+ y 2))
803 	      (y x))
804 	 (* x y))
805        x y))
806  (+ (* 6 6) 3 4))
807 (test-eval
808  '(let* ((x 6)
809 	 (y (let* ((x 2)
810 		   (a (let* ((x (* 3 x)))
811 			(+ x 2))))       
812 	      (+ x a)))                  
813 	 (z (+ x y)))                    
814     (+ x y z))
815  32)
816 
817 ;; named-let
818 
819 (test-eval
820  '(let eight ()
821     5
822     7
823     8)
824  8)
825 (test-eval
826  '(let loop ((count 0))
827     (if (= 100 count)
828 	count
829 	(loop (+ count 1))))
830  100)
831 (geval
832  '(define (prime? x)
833     (let prime-iter ((i 2))
834       (cond ((> (* i i) x) true)
835 	    ((= (remainder x i) 0) false)
836 	    (else (prime-iter (+ i 1)))))))
837 (test-eval
838  '(let primes ((x 2)
839 	       (n 20))
840     (cond ((= n 0) '())
841 	  ((prime? x) 
842 	   (cons x
843 		 (primes (+ x 1) (- n 1))))
844 	  (else (primes (+ x 1) n))))
845  '(2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71))
846 
847 (geval
848  '(define (fib n)
849     (let fib-iter ((a 1)
850 		   (b 0)
851 		   (count n))
852       (if (= count 0)
853 	  b
854 	  (fib-iter (+ a b) a (- count 1))))))
855 (test-eval '(fib 19) 4181)
856 
857 ;; do-loop	  
858 (test-eval
859  '(let ((y 0))
860     (do ((x 0 (+ x 1)))
861 	((= x 5) y)
862       (set! y (+ y 1))))
863  5)
864 (test-eval
865  '(do ()
866       (true))
867  true)
868 (test-eval
869  '(do ()
870       (true 5))
871  5)
872 (test-eval
873  '(let ((y 0))
874     (do ()
875 	((= y 5) y)
876       (set! y (+ y 1))))
877  5)
878 
879 (test-eval
880  '(do ((y '(1 2 3 4)))
881       ((null? y))
882     (set! y (cdr y)))
883  true)
884 (test-eval
885  '(let ((y 0))
886     (do ((x 0 (+ x 1)))
887 	((= x 5) y)
888       (set! y (+ y 1))))
889  5)
890 (test-eval
891  '(let ((x '(1 3 5 7 9)))
892     (do ((x x (cdr x))
893 	 (sum 0 (+ sum (car x))))
894 	((null? x) sum)))
895  25)
896 (test-eval 
897  '(let ((z '()))
898     (do ((x '(1 2 3 4) (cdr x))
899 	 (y '(1 2 3 4 5 6 7 8) (cddr y)))
900 	((null? x) y x z)
901       (set! z (cons (car x) z))))
902  '(4 3 2 1))
903 
904 
905 
906 ;; make-unbound!
907 
908 (test-eval
909  '(let ((x 3))
910     (let ((x 5))
911       (make-unbound! x)
912       (* x x)))
913  9)
914 
915 (test-eval
916  '(let ((x 3))
917     (let ((x 5))
918       (define y x)
919       (make-unbound! x)
920       (* y x)))
921  15)
922 
923 (test-eval
924  '(let ((y -1) (x 3))
925     (let ((y 0.5) (x 5))
926       (define a x)
927       (define b y)
928       (make-unbound! x)
929       (make-unbound! y)
930       (* a b x y)))
931  (* 5 3 -1 0.5))
932 
933 (test-eval
934  '(let ((x 3) (y 4))
935     (let ((x 5))
936       (make-unbound! x)
937       (+ x 4)))
938  7)
939 
940 (test-eval 
941  '(let ((a 1) (b 2) (c 3) (d 4))
942     (make-unbound! b)
943     (+ a c d))
944  (+ 1 3 4))
945 
946 (test-eval
947  '(let ((x 4) (y 5))
948     (let ((a 1) (b 2) (c 3))
949       (let ((x (+ a b)) (y (+ c a)))
950 	(make-unbound! x)
951 	(let ((a x) (b (+ x y)))
952 	  (define z b)
953 	  (make-unbound! b)
954 	  (* (+ a z)
955 	     (+ a b y))))))
956  (* (+ 4 8)
957     (+ 4 2 4)))
958  
959 ;; x 3 -- y 4
960 ;; x 4 -- y 4
961 ;; a 4 -- b 4
962 ;; a 4 -- b 2