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