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 ((do? exp) (eval (do->combination exp) env))
25 (apply (eval (operator exp) env)
26 (list-of-values (operands exp) env)))
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)
34 (procedure-body procedure)
36 (procedure-parameters procedure)
38 (procedure-environment procedure))))
41 "Unknown procedure type -- APPLY" procedure))))
43 (define (list-of-values exps env)
44 (if (no-operands? exps)
46 (cons (eval (first-operand exps) env)
47 (list-of-values (rest-operands exps) env))))
49 (define (tagged-list? exp tag)
54 ;; self-evaluating/variable/quoted
55 (define (self-evaluating? exp)
56 (cond ((number? exp) true)
59 (define (variable? exp) (symbol? exp))
61 (tagged-list? exp 'quote))
62 (define (text-of-quotation exp) (cadr exp))
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))
75 (define (definition-value exp)
76 (if (symbol? (cadr exp))
78 (make-lambda (cdadr exp) ; formal parameters
80 (define (eval-assignment exp env)
81 (set-variable-value! (assignment-variable exp)
82 (eval (assignment-value exp) env)
85 (define (eval-definition exp env)
86 (define-variable! (definition-variable exp)
87 (eval (definition-value exp) env)
90 (define (make-definition var val)
95 (define (unbound? exp)
96 (tagged-list? exp 'make-unbound!))
97 (define (unbound-var exp)
99 (define (eval-unbound exp env)
100 (remove-binding-from-frame! (unbound-var exp) (first-frame env)))
101 (define (remove-binding-from-frame! var frame)
102 (define (scan vars vals)
103 (cond ((null? (cdr vars))
104 (error "Binding not found -- REMOVE-BINDING-FROM-FRAME!" var))
105 ((eq? var (cadr vars))
106 (set-cdr! vars (cddr vars))
107 (set-cdr! vals (cddr vals)))
108 (else (scan (cdr vars) (cdr vals)))))
109 (let ((vars (frame-variables frame))
110 (vals (frame-values frame)))
111 (if (eq? var (car vars))
112 (begin (set-car! frame (cdr vars))
113 (set-cdr! frame (cdr vals)))
117 (define (if? exp) (tagged-list? exp 'if))
118 (define (if-predicate exp) (cadr exp))
119 (define (if-consequent exp) (caddr exp))
120 (define (if-alternative exp)
121 (if (not (null? (cdddr exp)))
124 (define (make-if predicate consequent alternative)
125 (list 'if predicate consequent alternative))
126 (define (eval-if exp env)
127 (if (true? (eval (if-predicate exp) env))
128 (eval (if-consequent exp) env)
129 (eval (if-alternative exp) env)))
132 (tagged-list? exp 'and))
133 (define (and-clauses exp)
136 (tagged-list? exp 'or))
137 (define (or-clauses exp)
139 (define (eval-and exp env)
140 (define (eval-clauses clauses)
141 (cond ((null? clauses) true)
142 ((null? (cdr clauses)) (eval (car clauses) env))
143 (else (and (eval (car clauses) env)
144 (eval-clauses (cdr clauses))))))
145 (eval-clauses (and-clauses exp)))
146 (define (eval-or exp env)
147 (define (eval-clauses clauses)
150 (or (eval (car clauses) env)
151 (eval-clauses (cdr clauses)))))
152 (eval-clauses (or-clauses exp)))
156 (define (lambda? exp) (tagged-list? exp 'lambda))
157 (define (lambda-parameters exp) (cadr exp))
158 (define (lambda-body exp) (cddr exp))
159 (define (make-lambda parameters body)
160 (cons 'lambda (cons parameters body)))
162 (define (make-let vars vals body)
164 (cons (map list vars vals)
167 (and (tagged-list? exp 'let)
168 (not (symbol? (cadr exp)))))
169 (define (let-vars exp)
170 (map car (cadr exp)))
171 (define (let-vals exp)
172 (map cadr (cadr exp)))
173 (define (let-body exp)
175 (define (let->combination exp)
176 (make-application (make-lambda (let-vars exp) (let-body exp))
178 (define (named-let? exp)
179 (and (tagged-list? exp 'let)
180 (symbol? (cadr exp))))
181 (define (named-let-name exp)
183 (define (named-let-vars exp)
184 (map car (caddr exp)))
185 (define (named-let-vals exp)
186 (map cadr (caddr exp)))
187 (define (named-let-body exp)
189 (define (named-let->combination exp)
191 (list (make-definition (named-let-name exp)
192 (make-lambda (named-let-vars exp)
193 (named-let-body exp)))
194 (make-application (named-let-name exp)
195 (named-let-vals exp)))))
196 (define (make-named-let name vars vals body)
199 (cons (map list vars vals)
202 (define (make-application op args)
206 (tagged-list? exp 'let*))
207 (define let*-vars let-vars)
208 (define let*-vals let-vals)
209 (define let*-body let-body)
210 (define (let*->nested-lets exp)
211 (define (expand-lets vars vals)
212 (if (null? (cdr vars))
213 (make-let (list (car vars))
216 (make-let (list (car vars))
218 (list (expand-lets (cdr vars) (cdr vals))))))
219 (let ((vars (let*-vars exp))
220 (vals (let*-vals exp)))
222 (sequence->exp (let*-body exp))
223 (expand-lets vars vals))))
227 (tagged-list? exp 'do))
228 (define (do-vars exp)
229 (map car (cadr exp)))
230 (define (do-inits exp)
231 (map cadr (cadr exp)))
232 (define (do-steps exp)
233 (map (lambda (var-init-step)
234 (if (null? (cddr var-init-step))
236 (caddr var-init-step)))
238 (define (do-test exp)
240 (define (do-expressions exp)
241 (if (null? (cdaddr exp))
244 (define (do-commands exp)
246 (define (do->combination exp)
254 (sequence->exp (do-expressions exp))
256 (append (do-commands exp)
257 (list (make-application
259 (do-steps exp)))))))))
263 (define (begin? exp) (tagged-list? exp 'begin))
264 (define (begin-actions exp) (cdr exp))
265 (define (last-exp? seq) (null? (cdr seq)))
266 (define (first-exp seq) (car seq))
267 (define (rest-exps seq) (cdr seq))
268 (define (sequence->exp seq)
269 (cond ((null? seq) seq)
270 ((last-exp? seq) (first-exp seq))
271 (else (make-begin seq))))
272 (define (make-begin seq) (cons 'begin seq))
273 (define (eval-sequence exps env)
274 (cond ((last-exp? exps) (eval (first-exp exps) env))
275 (else (eval (first-exp exps) env)
276 (eval-sequence (rest-exps exps) env))))
279 (define (application? exp) (pair? exp))
280 (define (operator exp) (car exp))
281 (define (operands exp) (cdr exp))
282 (define (no-operands? ops) (null? ops))
283 (define (first-operand ops) (car ops))
284 (define (rest-operands ops) (cdr ops))
287 (define (cond? exp) (tagged-list? exp 'cond))
288 (define (cond-clauses exp) (cdr exp))
289 (define (cond-else-clause? clause)
290 (eq? (cond-predicate clause) 'else))
291 (define (cond-predicate clause) (car clause))
292 (define (cond-actions clause) (cdr clause))
293 (define (cond-extended-clause? clause)
294 (and (not (null? (cdr clause))) (eq? (cadr clause) '=>)))
295 (define (cond-extended-proc clause)
297 (define (cond->if exp)
298 (expand-clauses (cond-clauses exp)))
299 (define (expand-clauses clauses)
301 'false ; no else clause
302 (let ((first (car clauses))
303 (rest (cdr clauses)))
304 (if (cond-else-clause? first)
306 (sequence->exp (cond-actions first))
307 (error "ELSE clause isn't last -- COND->IF"
309 (if (cond-extended-clause? first)
310 (make-if (cond-predicate first)
312 (cond-extended-proc first)
313 (list (cond-predicate first)))
314 (expand-clauses rest))
315 (make-if (cond-predicate first)
316 (sequence->exp (cond-actions first))
317 (expand-clauses rest)))))))
324 (define (make-procedure parameters body env)
325 (list 'procedure parameters body env))
326 (define (compound-procedure? p)
327 (tagged-list? p 'procedure))
328 (define (procedure-parameters p) (cadr p))
329 (define (procedure-body p) (caddr p))
330 (define (procedure-environment p) (cadddr p))
333 (define (enclosing-environment env) (cdr env))
334 (define (first-frame env) (car env))
335 (define the-empty-environment '())
336 (define (make-frame variables values)
337 (cons variables values))
338 (define (frame-variables frame) (car frame))
339 (define (frame-values frame) (cdr frame))
340 (define (add-binding-to-frame! var val frame)
341 (set-car! frame (cons var (car frame)))
342 (set-cdr! frame (cons val (cdr frame))))
343 (define (extend-environment vars vals base-env)
344 (if (= (length vars) (length vals))
345 (cons (make-frame vars vals) base-env)
346 (if (< (length vars) (length vals))
347 (error "Too many arguments supplied" vars vals)
348 (error "Too few arguments supplied" vars vals))))
349 (define (lookup-variable-value var env)
350 (define (env-loop env)
351 (define (scan vars vals)
353 (env-loop (enclosing-environment env)))
354 ((eq? var (car vars))
356 (else (scan (cdr vars) (cdr vals)))))
357 (if (eq? env the-empty-environment)
358 (error "Unbound variable" var)
359 (let ((frame (first-frame env)))
360 (scan (frame-variables frame)
361 (frame-values frame)))))
363 (define (set-variable-value! var val env)
364 (define (env-loop env)
365 (define (scan vars vals)
367 (env-loop (enclosing-environment env)))
368 ((eq? var (car vars))
370 (else (scan (cdr vars) (cdr vals)))))
371 (if (eq? env the-empty-environment)
372 (error "Unbound variable -- SET!" var)
373 (let ((frame (first-frame env)))
374 (scan (frame-variables frame)
375 (frame-values frame)))))
377 (define (define-variable! var val env)
378 (let ((frame (first-frame env)))
379 (define (scan vars vals)
381 (add-binding-to-frame! var val frame))
382 ((eq? var (car vars))
384 (else (scan (cdr vars) (cdr vals)))))
385 (scan (frame-variables frame)
386 (frame-values frame))))
389 (define (primitive-procedure? proc)
390 (tagged-list? proc 'primitive))
391 (define (primitive-implementation proc) (cadr proc))
392 (define primitive-procedures
393 (list (list 'car car)
409 (list 'remainder remainder)
411 (list 'equal? equal?)
412 (list 'display display)))
413 (define (primitive-procedure-names)
415 primitive-procedures))
416 (define (primitive-procedure-objects)
417 (map (lambda (proc) (list 'primitive (cadr proc)))
418 primitive-procedures))
419 (define (apply-primitive-procedure proc args)
420 (apply-in-underlying-scheme
421 (primitive-implementation proc) args))
424 (define input-prompt ";;; M-Eval input:")
425 (define output-prompt ";;; M-Eval value:")
426 (define (driver-loop)
427 (prompt-for-input input-prompt)
428 (let ((input (read)))
429 (let ((output (eval input the-global-environment)))
430 (announce-output output-prompt)
431 (user-print output)))
433 (define (prompt-for-input string)
434 (newline) (newline) (display string) (newline))
436 (define (announce-output string)
437 (newline) (display string) (newline))
438 (define (user-print object)
439 (if (compound-procedure? object)
440 (display (list 'compound-procedure
441 (procedure-parameters object)
442 (procedure-body object)
445 (define (setup-environment)
447 (extend-environment (primitive-procedure-names)
448 (primitive-procedure-objects)
449 the-empty-environment)))
450 (define-variable! 'true true initial-env)
451 (define-variable! 'false false initial-env)
453 (define the-global-environment (setup-environment))
456 (define (test-case actual expected)
461 (display "Expected: ")
464 (define (geval exp) ;; eval globally
465 (eval exp the-global-environment))
466 (define (test-eval exp expected)
467 (test-case (geval exp) expected))
469 ;; Exercise 4.15. Given a one-argument procedure p and an object a, p is said to ``halt'' on a if evaluating the expression (p a) returns a value (as opposed to terminating with an error message or running forever). Show that it is impossible to write a procedure halts? that correctly determines whether p halts on a for any procedure p and object a. Use the following reasoning: If you had such a procedure halts?, you could implement the following program:
471 (define (run-forever) (run-forever))
478 ;; Now consider evaluating the expression (try try) and show that any possible outcome (either halting or running forever) violates the intended behavior of halts?.23
480 ;; If (try try) halts, (halts? try try) will be true. But then, according to the definition of try above, (try try) will run forever.
482 ;; On the other hand, if (try try) does not halt, then (halts? try try) will be false. However, according to the definition of try above, this means that (try try) will return 'halted and therefore halt.
486 ;; procedure definitions
489 '(define (assoc key records)
490 (cond ((null? records) false)
491 ((equal? key (caar records)) (car records))
492 (else (assoc key (cdr records))))))
495 '(define (map proc list)
498 (cons (proc (car list))
499 (map proc (cdr list))))))
502 '(define (accumulate op initial sequence)
506 (accumulate op initial (cdr sequence))))))
509 (test-eval '(begin 5 6) 6)
511 (geval '(define x 3))
513 (test-eval '(set! x -25) 'ok)
515 (geval '(define z (lambda (x y) (+ x (* x y)))))
516 (test-eval '(z 3 4) 15)
517 (test-eval '(cond ((= x -2) 'x=-2)
521 (test-eval '(if true false true) false)
529 (geval '(define x (+ 3 8)))
530 (test-eval '(and 0 true x) 11)
531 (test-eval '(and 0 true x false) false)
532 (test-eval '(and 0 true x (set! x -2) false) false)
534 (test-eval '(and 0 true x false (set! x -5)) false)
536 (test-eval '(or false (set! x 25)) 'ok)
538 (test-eval '(or (set! x 2) (set! x 4)) 'ok)
540 (test-eval '(or false (set! x 25) true false) 'ok)
542 (test-eval '(or ((lambda (x) x) 5)) 5)
543 (test-eval '(or (begin (set! x (+ x 1)) x)) 26)
549 '(cond ((assoc 'b '((a 1) (b 2))) => cadr)
554 '(cond ((= 3 4) 'not-true)
555 ((= (* 2 4) 3) 'also-false)
567 ;; procedure definition and application
569 '(define (factorial n)
572 (* n (factorial (- n 1))))))
573 (test-eval '(factorial 5) 120)
585 '(accumulate + 0 '(1 2 3 4 5))
590 (make-let '(x y) '(3 5) '((+ x y)))
617 (z (let ((a (* 3 2)))
645 (+ (let* ((x (+ y 2))
653 (a (let* ((x (* 3 x)))
669 '(let loop ((count 0))
676 (let prime-iter ((i 2))
677 (cond ((> (* i i) x) true)
678 ((= (remainder x i) 0) false)
679 (else (prime-iter (+ i 1)))))))
686 (primes (+ x 1) (- n 1))))
687 (else (primes (+ x 1) n))))
688 '(2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71))
697 (fib-iter (+ a b) a (- count 1))))))
698 (test-eval '(fib 19) 4181)
723 '(do ((y '(1 2 3 4)))
734 '(let ((x '(1 3 5 7 9)))
736 (sum 0 (+ sum (car x))))
741 (do ((x '(1 2 3 4) (cdr x))
742 (y '(1 2 3 4 5 6 7 8) (cddr y)))
744 (set! z (cons (car x) z))))
782 '(let ((a 1) (b 2) (c 3) (d 4))
789 (let ((a 1) (b 2) (c 3))
790 (let ((x (+ a b)) (y (+ c a)))
792 (let ((a x) (b (+ x y)))