1 ;; (define apply-in-underlying-scheme apply)
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))
14 (make-procedure (lambda-parameters 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))
26 (apply (actual-value (operator exp) env)
30 (error "Unknown expression type -- EVAL" exp))))
31 (define (apply procedure arguments env)
32 (cond ((primitive-procedure? procedure)
33 (apply-primitive-procedure
35 (list-of-arg-values arguments env)))
36 ((compound-procedure? procedure)
38 (procedure-body procedure)
40 (procedure-parameters procedure)
41 (list-of-delayed-args arguments env)
42 (procedure-environment procedure))))
45 "Unknown procedure type -- APPLY" procedure))))
48 (tagged-list? obj 'thunk))
49 (define (thunk-exp thunk)
51 (define (thunk-env thunk)
53 (define (evaluated-thunk? obj)
54 (tagged-list? obj 'evaluated-thunk))
55 (define (thunk-value evaluated-thunk)
56 (cadr evaluated-thunk))
57 (define (delay-it exp env)
59 (define (actual-value exp env)
60 (force-it (eval exp env)))
61 (define (force-it obj)
63 (let ((result (actual-value
66 (set-car! obj 'evaluated-thunk)
67 (set-car! (cdr obj) result)
68 (set-cdr! (cdr obj) '())
70 ((evaluated-thunk? obj)
74 (define (list-of-arg-values exps env)
75 (if (no-operands? exps)
77 (cons (actual-value (first-operand exps) env)
78 (list-of-arg-values (rest-operands exps) env))))
79 (define (list-of-delayed-args exps env)
80 (if (no-operands? exps)
82 (cons (delay-it (first-operand exps) env)
83 (list-of-delayed-args (rest-operands exps) env))))
85 (define (tagged-list? exp tag)
90 ;; self-evaluating/variable/quoted
91 (define (self-evaluating? exp)
92 (cond ((number? exp) true)
95 (define (variable? exp) (symbol? exp))
97 (tagged-list? exp 'quote))
98 (define (text-of-quotation exp) (cadr exp))
100 ;; assignment/definition
101 (define (assignment? exp)
102 (tagged-list? exp 'set!))
103 (define (assignment-variable exp) (cadr exp))
104 (define (assignment-value exp) (caddr exp))
105 (define (make-assignment var val)
106 (list 'set! var val))
107 (define (definition? exp)
108 (tagged-list? exp 'define))
109 (define (definition-variable exp)
110 (if (symbol? (cadr exp))
113 (define (definition-value exp)
114 (if (symbol? (cadr exp))
116 (make-lambda (cdadr exp) ; formal parameters
118 (define (eval-assignment exp env)
119 (set-variable-value! (assignment-variable exp)
120 (eval (assignment-value exp) env)
123 (define (eval-definition exp env)
124 (define-variable! (definition-variable exp)
125 (eval (definition-value exp) env)
128 (define (make-definition var val)
133 ;; (define (unbound? exp)
134 ;; (tagged-list? exp 'make-unbound!))
135 ;; (define (unbound-var exp)
137 ;; (define (eval-unbound exp env)
138 ;; (remove-binding-from-frame! (unbound-var exp) (first-frame env)))
143 (define (if? exp) (tagged-list? exp 'if))
144 (define (if-predicate exp) (cadr exp))
145 (define (if-consequent exp) (caddr exp))
146 (define (if-alternative exp)
147 (if (not (null? (cdddr exp)))
150 (define (make-if predicate consequent alternative)
151 (list 'if predicate consequent alternative))
152 (define (eval-if exp env)
153 (if (true? (actual-value (if-predicate exp) env))
154 (eval (if-consequent exp) env)
155 (eval (if-alternative exp) env)))
158 (tagged-list? exp 'and))
159 (define (and-clauses exp)
162 (tagged-list? exp 'or))
163 (define (or-clauses exp)
165 (define (eval-and exp env)
166 (define (eval-clauses clauses)
167 (cond ((null? clauses) true)
168 ((null? (cdr clauses)) (eval (car clauses) env))
169 (else (and (eval (car clauses) env)
170 (eval-clauses (cdr clauses))))))
171 (eval-clauses (and-clauses exp)))
172 (define (eval-or exp env)
173 (define (eval-clauses clauses)
176 (or (eval (car clauses) env)
177 (eval-clauses (cdr clauses)))))
178 (eval-clauses (or-clauses exp)))
181 ;; lambda/let/let*/letrec
182 (define (lambda? exp) (tagged-list? exp 'lambda))
183 (define (lambda-parameters exp) (cadr exp))
184 (define (lambda-body exp) (cddr exp))
185 (define (make-lambda parameters body)
186 (cons 'lambda (cons parameters body)))
188 (define (make-let vars vals body)
190 (cons (map list vars vals)
193 (and (tagged-list? exp 'let)
194 (not (symbol? (cadr exp)))))
195 (define (let-vars exp)
196 (map car (cadr exp)))
197 (define (let-vals exp)
198 (map cadr (cadr exp)))
199 (define (let-body exp)
201 (define (let->combination exp)
202 (make-application (make-lambda (let-vars exp) (let-body exp))
204 (define (named-let? exp)
205 (and (tagged-list? exp 'let)
206 (symbol? (cadr exp))))
207 (define (named-let-name exp)
209 (define (named-let-vars exp)
210 (map car (caddr exp)))
211 (define (named-let-vals exp)
212 (map cadr (caddr exp)))
213 (define (named-let-body exp)
215 (define (named-let->combination exp)
217 (list (make-definition (named-let-name exp)
218 (make-lambda (named-let-vars exp)
219 (named-let-body exp)))
220 (make-application (named-let-name exp)
221 (named-let-vals exp)))))
222 (define (make-named-let name vars vals body)
225 (cons (map list vars vals)
228 (define (letrec? exp)
229 (tagged-list? exp 'letrec))
231 (define (letrec-vars exp)
232 (map car (cadr exp)))
233 (define (letrec-vals exp)
234 (map cadr (cadr exp)))
235 (define (letrec-body exp)
237 (define (letrec->let exp)
238 (let* ((vars (letrec-vars exp))
239 (unassigneds (map (lambda (var) ''*unassigned*)
241 (vals (letrec-vals exp))
242 (assignments (map (lambda (var val)
243 (make-assignment var val))
246 (body (letrec-body exp)))
249 (append assignments body))))
255 (tagged-list? exp 'let*))
256 (define let*-vars let-vars)
257 (define let*-vals let-vals)
258 (define let*-body let-body)
259 (define (let*->nested-lets exp)
260 (define (expand-lets vars vals)
261 (if (null? (cdr vars))
262 (make-let (list (car vars))
265 (make-let (list (car vars))
267 (list (expand-lets (cdr vars) (cdr vals))))))
268 (let ((vars (let*-vars exp))
269 (vals (let*-vals exp)))
271 (sequence->exp (let*-body exp))
272 (expand-lets vars vals))))
276 (tagged-list? exp 'do))
277 (define (do-vars exp)
278 (map car (cadr exp)))
279 (define (do-inits exp)
280 (map cadr (cadr exp)))
281 (define (do-steps exp)
282 (map (lambda (var-init-step)
283 (if (null? (cddr var-init-step))
285 (caddr var-init-step)))
287 (define (do-test exp)
289 (define (do-expressions exp)
290 (if (null? (cdaddr exp))
293 (define (do-commands exp)
295 (define (do->combination exp)
303 (sequence->exp (do-expressions exp))
305 (append (do-commands exp)
306 (list (make-application
308 (do-steps exp)))))))))
312 (define (begin? exp) (tagged-list? exp 'begin))
313 (define (begin-actions exp) (cdr exp))
314 (define (last-exp? seq) (null? (cdr seq)))
315 (define (first-exp seq) (car seq))
316 (define (rest-exps seq) (cdr seq))
317 (define (sequence->exp seq)
318 (cond ((null? seq) seq)
319 ((last-exp? seq) (first-exp seq))
320 (else (make-begin seq))))
321 (define (make-begin seq) (cons 'begin seq))
322 (define (eval-sequence exps env)
323 (cond ((last-exp? exps) (eval (first-exp exps) env))
324 (else (eval (first-exp exps) env)
325 (eval-sequence (rest-exps exps) env))))
328 (define (make-application op args)
330 (define (application? exp) (pair? exp))
331 (define (operator exp) (car exp))
332 (define (operands exp) (cdr exp))
333 (define (no-operands? ops) (null? ops))
334 (define (first-operand ops) (car ops))
335 (define (rest-operands ops) (cdr ops))
338 (define (cond? exp) (tagged-list? exp 'cond))
339 (define (cond-clauses exp) (cdr exp))
340 (define (cond-else-clause? clause)
341 (eq? (cond-predicate clause) 'else))
342 (define (cond-predicate clause) (car clause))
343 (define (cond-actions clause) (cdr clause))
344 (define (cond-extended-clause? clause)
345 (and (not (null? (cdr clause))) (eq? (cadr clause) '=>)))
346 (define (cond-extended-proc clause)
348 (define (cond->if exp)
349 (expand-clauses (cond-clauses exp)))
350 (define (expand-clauses clauses)
352 'false ; no else clause
353 (let ((first (car clauses))
354 (rest (cdr clauses)))
355 (if (cond-else-clause? first)
357 (sequence->exp (cond-actions first))
358 (error "ELSE clause isn't last -- COND->IF"
360 (if (cond-extended-clause? first)
361 (make-if (cond-predicate first)
363 (cond-extended-proc first)
364 (list (cond-predicate first)))
365 (expand-clauses rest))
366 (make-if (cond-predicate first)
367 (sequence->exp (cond-actions first))
368 (expand-clauses rest)))))))
375 (define (make-procedure parameters body env)
376 (list 'procedure parameters body env))
377 ;; (define (scan-out-defines body)
378 ;; (let* ((definitions (filter definition? body))
379 ;; (vars (map definition-variable definitions))
380 ;; (unassigneds (map (lambda (var) ''*unassigned*)
382 ;; (vals (map definition-value definitions))
384 ;; (map (lambda (var val)
385 ;; (make-assignment var val))
387 ;; (exps (remove definition? body)))
388 ;; (if (null? definitions)
393 ;; (append assignments exps))))))
394 (define (compound-procedure? p)
395 (tagged-list? p 'procedure))
396 (define (procedure-parameters p) (cadr p))
397 (define (procedure-body p) (caddr p))
398 (define (procedure-environment p) (cadddr p))
401 (define (enclosing-environment env) (cdr env))
402 (define (first-frame env) (car env))
403 (define the-empty-environment '())
404 (define (make-frame variables values)
405 (cons variables values))
406 (define (frame-variables frame) (car frame))
407 (define (frame-values frame) (cdr frame))
408 (define (add-binding-to-frame! var val frame)
409 (set-car! frame (cons var (car frame)))
410 (set-cdr! frame (cons val (cdr frame))))
411 (define (extend-environment vars vals base-env)
412 (if (= (length vars) (length vals))
413 (cons (make-frame vars vals) base-env)
414 (if (< (length vars) (length vals))
415 (error "Too many arguments supplied" vars vals)
416 (error "Too few arguments supplied" vars vals))))
417 (define (lookup-variable-value var env)
418 (define (env-loop env)
419 (define (scan vars vals)
421 (env-loop (enclosing-environment env)))
422 ((eq? var (car vars))
423 (let ((val (car vals)))
424 (if (eq? val '*unassigned*)
425 (error "Var not yet defined -- LOOKUP-VARIABLE-VALUE" var)
427 (else (scan (cdr vars) (cdr vals)))))
428 (if (eq? env the-empty-environment)
429 (error "Unbound variable" var)
430 (let ((frame (first-frame env)))
431 (scan (frame-variables frame)
432 (frame-values frame)))))
434 (define (set-variable-value! var val env)
435 (define (env-loop env)
436 (define (scan vars vals)
438 (env-loop (enclosing-environment env)))
439 ((eq? var (car vars))
441 (else (scan (cdr vars) (cdr vals)))))
442 (if (eq? env the-empty-environment)
443 (error "Unbound variable -- SET!" var)
444 (let ((frame (first-frame env)))
445 (scan (frame-variables frame)
446 (frame-values frame)))))
448 (define (define-variable! var val env)
449 (let ((frame (first-frame env)))
450 (define (scan vars vals)
452 (add-binding-to-frame! var val frame))
453 ((eq? var (car vars))
455 (else (scan (cdr vars) (cdr vals)))))
456 (scan (frame-variables frame)
457 (frame-values frame))))
459 (define (remove-binding-from-frame! var frame)
460 (define (scan vars vals)
461 (cond ((null? (cdr vars))
462 (error "Binding not found -- REMOVE-BINDING-FROM-FRAME!" var))
463 ((eq? var (cadr vars))
464 (set-cdr! vars (cddr vars))
465 (set-cdr! vals (cddr vals)))
466 (else (scan (cdr vars) (cdr vals)))))
467 (let ((vars (frame-variables frame))
468 (vals (frame-values frame)))
469 (if (eq? var (car vars))
470 (begin (set-car! frame (cdr vars))
471 (set-cdr! frame (cdr vals)))
475 (define (primitive-procedure? proc)
476 (tagged-list? proc 'primitive))
477 (define (primitive-implementation proc) (cadr proc))
478 (define primitive-procedures
479 (list (list 'car car)
495 (list 'remainder remainder)
497 (list 'equal? equal?)
498 (list 'display display)))
499 (define (primitive-procedure-names)
501 primitive-procedures))
502 (define (primitive-procedure-objects)
503 (map (lambda (proc) (list 'primitive (cadr proc)))
504 primitive-procedures))
505 (define (apply-primitive-procedure proc args)
506 (apply-in-underlying-scheme
507 (primitive-implementation proc) args))
510 (define input-prompt ";;; M-Eval input:")
511 (define output-prompt ";;; M-Eval value:")
512 (define (driver-loop)
513 (prompt-for-input input-prompt)
514 (let ((input (read)))
515 (let ((output (actual-value input the-global-environment)))
516 (announce-output output-prompt)
517 (user-print output)))
519 (define (prompt-for-input string)
520 (newline) (newline) (display string) (newline))
522 (define (announce-output string)
523 (newline) (display string) (newline))
524 (define (user-print object)
525 (if (compound-procedure? object)
526 (display (list 'compound-procedure
527 (procedure-parameters object)
528 (procedure-body object)
531 (define (setup-environment)
533 (extend-environment (primitive-procedure-names)
534 (primitive-procedure-objects)
535 the-empty-environment)))
536 (define-variable! 'true true initial-env)
537 (define-variable! 'false false initial-env)
539 (define the-global-environment (setup-environment))
542 (define (test-case actual expected)
547 (display "Expected: ")
550 (define (geval exp) ;; eval globally
551 (eval exp the-global-environment))
552 (define (test-eval exp expected)
553 (test-case (force-it (geval exp)) expected))
556 ;; Exercise 4.30. Cy D. Fect, a reformed C programmer, is worried that some side effects may never take place, because the lazy evaluator doesn't force the expressions in a sequence. Since the value of an expression in a sequence other than the last one is not used (the expression is there only for its effect, such as assigning to a variable or printing), there can be no subsequent use of this value (e.g., as an argument to a primitive procedure) that will cause it to be forced. Cy thus thinks that when evaluating sequences, we must force all expressions in the sequence except the final one. He proposes to modify eval-sequence from section 4.1.1 to use actual-value rather than eval:
558 ;; (define (eval-sequence exps env)
559 ;; (cond ((last-exp? exps) (eval (first-exp exps) env))
560 ;; (else (actual-value (first-exp exps) env)
561 ;; (eval-sequence (rest-exps exps) env))))
563 ;; a. Ben Bitdiddle thinks Cy is wrong. He shows Cy the for-each procedure described in exercise 2.23, which gives an important example of a sequence with side effects:
565 ;; (define (for-each proc items)
568 ;; (begin (proc (car items))
569 ;; (for-each proc (cdr items)))))
571 ;; He claims that the evaluator in the text (with the original eval-sequence) handles this correctly:
574 ;; (for-each (lambda (x) (newline) (display x))
582 ;; Explain why Ben is right about the behavior of for-each.
584 ;; proc is an operator and hence the thunk will be forced for proc
585 ;; display is a primitive and this will therefore force the thunk for (car items)
587 ;; b. Cy agrees that Ben is right about the for-each example, but says that that's not the kind of program he was thinking about when he proposed his change to eval-sequence. He defines the following two procedures in the lazy evaluator:
591 (set! x (cons x '(2)))
598 (p (set! x (cons x '(2))))))
599 (test-eval '(p1 1) '(1 2))
600 (test-eval '(p2 1) 1)
602 ;; What are the values of (p1 1) and (p2 1) with the original eval-sequence? What would the values be with Cy's proposed change to eval-sequence?
604 ;; with Cy's change, it would be '(1 2) for both
606 ;; c. Cy also points out that changing eval-sequence as he proposes does not affect the behavior of the example in part a. Explain why this is true.
608 ;; the primitives were forcing the evaluation of the thunks anyway
610 ;; d. How do you think sequences ought to be treated in the lazy evaluator? Do you like Cy's approach, the approach in the text, or some other approach?
612 ;; The one in the text is better. Cy's approach would partially defeat the whole purpose of delayed evaluation.
617 ;; procedure definitions
620 '(define (assoc key records)
621 (cond ((null? records) false)
622 ((equal? key (caar records)) (car records))
623 (else (assoc key (cdr records))))))
626 '(define (map proc list)
629 (cons (proc (car list))
630 (map proc (cdr list))))))
633 '(define (accumulate op initial sequence)
637 (accumulate op initial (cdr sequence))))))
640 (test-eval '(begin 5 6) 6)
642 (geval '(define x 3))
644 (test-eval '(set! x -25) 'ok)
646 (geval '(define z (lambda (x y) (+ x (* x y)))))
647 (test-eval '(z 3 4) 15)
648 (test-eval '(cond ((= x -2) 'x=-2)
652 (test-eval '(if true false true) false)
661 (geval '(define x (+ 3 8)))
662 (test-eval '(and 0 true x) 11)
663 (test-eval '(and 0 true x false) false)
664 (test-eval '(and 0 true x (set! x -2) false) false)
666 (test-eval '(and 0 true x false (set! x -5)) false)
668 (test-eval '(or false (set! x 25)) 'ok)
670 (test-eval '(or (set! x 2) (set! x 4)) 'ok)
672 (test-eval '(or false (set! x 25) true false) 'ok)
674 (test-eval '(or ((lambda (x) x) 5)) 5)
675 (test-eval '(or (begin (set! x (+ x 1)) x)) 26)
681 '(cond ((assoc 'b '((a 1) (b 2))) => cadr)
686 '(cond ((= 3 4) 'not-true)
687 ((= (* 2 4) 3) 'also-false)
699 ;; procedure definition and application
701 '(define (factorial n)
704 (* n (factorial (- n 1))))))
705 (test-eval '(factorial 5) 120)
717 '(accumulate + 0 '(1 2 3 4 5))
722 (make-let '(x y) '(3 5) '((+ x y)))
749 (z (let ((a (* 3 2)))
777 (+ (let* ((x (+ y 2))
785 (a (let* ((x (* 3 x)))
801 '(let loop ((count 0))
808 (let prime-iter ((i 2))
809 (cond ((> (* i i) x) true)
810 ((= (remainder x i) 0) false)
811 (else (prime-iter (+ i 1)))))))
818 (primes (+ x 1) (- n 1))))
819 (else (primes (+ x 1) n))))
820 '(2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71))
829 (fib-iter (+ a b) a (- count 1))))))
830 (test-eval '(fib 19) 4181)
855 '(do ((y '(1 2 3 4)))
866 '(let ((x '(1 3 5 7 9)))
868 (sum 0 (+ sum (car x))))
873 (do ((x '(1 2 3 4) (cdr x))
874 (y '(1 2 3 4 5 6 7 8) (cddr y)))
876 (set! z (cons (car x) z))))
882 ;; broken now due to scan-out-defines
900 ;; '(let ((y -1) (x 3))
901 ;; (let ((y 0.5) (x 5))
910 ;; '(let ((x 3) (y 4))
917 ;; '(let ((a 1) (b 2) (c 3) (d 4))
923 ;; '(let ((x 4) (y 5))
924 ;; (let ((a 1) (b 2) (c 3))
925 ;; (let ((x (+ a b)) (y (+ c a)))
927 ;; (let ((a x) (b (+ x y)))
953 (test-eval '(f 5) false)
954 (test-eval '(f 10) true)
961 ;; signal an error because x is undefined if variables are scanned out
978 (test-eval '(f 11) false)
979 (test-eval '(f 16) true)
986 (* n (fact (- n 1)))))))
991 ;; delayed-evaluation
996 (test-eval '(try 0 (/ 1 0)) 1)
999 '(define (unless condition usual-value exceptional-value)
1000 (if condition exceptional-value usual-value)))
1005 (begin (display "exception: returning 0")
1012 (begin (display "exception: returning 0")
1017 '(define (factorial n)
1019 (* n (factorial (- n 1)))
1025 (geval '(define count 0))
1026 (geval '(define (id x)
1027 (set! count (+ count 1))
1030 (geval '(define w (id (id 10))))
1031 (test-eval 'count 1)
1033 (test-eval 'count 2)
1035 '(let ((f (lambda (x) (+ x 1))))
1038 (geval '(define count 0))
1039 (geval '(define (id x)
1040 (set! count (+ count 1))
1048 (test-eval 'count 1)
1049 ;; would be 2 without memoization