1 ;; (define apply-in-underlying-scheme apply)
2 ;; (define eval-in-underlying-scheme eval)
5 (cond ((self-evaluating? exp) exp)
6 ((variable? exp) (lookup-variable-value exp env))
7 ((quoted? exp) (text-of-quotation exp))
8 ((assignment? exp) (eval-assignment exp env))
9 ((definition? exp) (eval-definition 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))
22 (apply (eval (operator exp) env)
23 (list-of-values (operands exp) env)))
25 (error "Unknown expression type -- EVAL" exp))))
27 (define (apply procedure arguments)
28 (cond ((primitive-procedure? procedure)
29 (apply-primitive-procedure procedure arguments))
30 ((compound-procedure? procedure)
32 (procedure-body procedure)
34 (procedure-parameters procedure)
36 (procedure-environment procedure))))
39 "Unknown procedure type -- APPLY" procedure))))
40 (define (list-of-values exps env)
41 (if (no-operands? exps)
43 (cons (eval (first-operand exps) env)
44 (list-of-values (rest-operands exps) env))))
46 (define (eval-if exp env)
47 (if (true? (eval (if-predicate exp) env))
48 (eval (if-consequent exp) env)
49 (eval (if-alternative exp) env)))
50 (define (eval-sequence exps env)
51 (cond ((last-exp? exps) (eval (first-exp exps) env))
52 (else (eval (first-exp exps) env)
53 (eval-sequence (rest-exps exps) env))))
54 (define (eval-assignment exp env)
55 (set-variable-value! (assignment-variable exp)
56 (eval (assignment-value exp) env)
59 (define (eval-definition exp env)
60 (define-variable! (definition-variable exp)
61 (eval (definition-value exp) env)
64 (define (self-evaluating? exp)
65 (cond ((number? exp) true)
68 (define (variable? exp) (symbol? exp))
70 (tagged-list? exp 'quote))
72 (define (text-of-quotation exp) (cadr exp))
73 (define (tagged-list? exp tag)
77 (define (assignment? exp)
78 (tagged-list? exp 'set!))
79 (define (assignment-variable exp) (cadr exp))
80 (define (assignment-value exp) (caddr exp))
81 (define (definition? exp)
82 (tagged-list? exp 'define))
83 (define (definition-variable exp)
84 (if (symbol? (cadr exp))
87 (define (definition-value exp)
88 (if (symbol? (cadr exp))
90 (make-lambda (cdadr exp) ; formal parameters
92 (define (lambda? exp) (tagged-list? exp 'lambda))
93 (define (lambda-parameters exp) (cadr exp))
94 (define (lambda-body exp) (cddr exp))
95 (define (make-lambda parameters body)
96 (cons 'lambda (cons parameters body)))
97 (define (if? exp) (tagged-list? exp 'if))
98 (define (if-predicate exp) (cadr exp))
99 (define (if-consequent exp) (caddr exp))
100 (define (if-alternative exp)
101 (if (not (null? (cdddr exp)))
104 (define (make-if predicate consequent alternative)
105 (list 'if predicate consequent alternative))
106 (define (begin? exp) (tagged-list? exp 'begin))
107 (define (begin-actions exp) (cdr exp))
108 (define (last-exp? seq) (null? (cdr seq)))
109 (define (first-exp seq) (car seq))
110 (define (rest-exps seq) (cdr seq))
112 (define (sequence->exp seq)
113 (cond ((null? seq) seq)
114 ((last-exp? seq) (first-exp seq))
115 (else (make-begin seq))))
116 (define (make-begin seq) (cons 'begin seq))
117 (define (application? exp) (pair? exp))
118 (define (operator exp) (car exp))
119 (define (operands exp) (cdr exp))
120 (define (no-operands? ops) (null? ops))
121 (define (first-operand ops) (car ops))
122 (define (rest-operands ops) (cdr ops))
127 (define (make-procedure parameters body env)
128 (list 'procedure parameters body env))
129 (define (compound-procedure? p)
130 (tagged-list? p 'procedure))
131 (define (procedure-parameters p) (cadr p))
132 (define (procedure-body p) (caddr p))
133 (define (procedure-environment p) (cadddr p))
134 (define (enclosing-environment env) (cdr env))
135 (define (first-frame env) (car env))
136 (define the-empty-environment '())
137 (define (make-frame variables values)
138 (cons variables values))
139 (define (frame-variables frame) (car frame))
140 (define (frame-values frame) (cdr frame))
141 (define (add-binding-to-frame! var val frame)
142 (set-car! frame (cons var (car frame)))
143 (set-cdr! frame (cons val (cdr frame))))
144 (define (extend-environment vars vals base-env)
145 (if (= (length vars) (length vals))
146 (cons (make-frame vars vals) base-env)
147 (if (< (length vars) (length vals))
148 (error "Too many arguments supplied" vars vals)
149 (error "Too few arguments supplied" vars vals))))
150 (define (lookup-variable-value var env)
151 (define (env-loop env)
152 (define (scan vars vals)
154 (env-loop (enclosing-environment env)))
155 ((eq? var (car vars))
157 (else (scan (cdr vars) (cdr vals)))))
158 (if (eq? env the-empty-environment)
159 (error "Unbound variable" var)
160 (let ((frame (first-frame env)))
161 (scan (frame-variables frame)
162 (frame-values frame)))))
164 (define (set-variable-value! var val env)
165 (define (env-loop env)
166 (define (scan vars vals)
168 (env-loop (enclosing-environment env)))
169 ((eq? var (car vars))
171 (else (scan (cdr vars) (cdr vals)))))
172 (if (eq? env the-empty-environment)
173 (error "Unbound variable -- SET!" var)
174 (let ((frame (first-frame env)))
175 (scan (frame-variables frame)
176 (frame-values frame)))))
178 (define (define-variable! var val env)
179 (let ((frame (first-frame env)))
180 (define (scan vars vals)
182 (add-binding-to-frame! var val frame))
183 ((eq? var (car vars))
185 (else (scan (cdr vars) (cdr vals)))))
186 (scan (frame-variables frame)
187 (frame-values frame))))
188 (define (primitive-procedure? proc)
189 (tagged-list? proc 'primitive))
191 (define (primitive-implementation proc) (cadr proc))
192 (define primitive-procedures
193 (list (list 'car car)
206 (list 'equal? equal?)
207 (list 'display display)))
208 (define (primitive-procedure-names)
210 primitive-procedures))
212 (define (primitive-procedure-objects)
213 (map (lambda (proc) (list 'primitive (cadr proc)))
214 primitive-procedures))
215 (define (apply-primitive-procedure proc args)
216 (apply-in-underlying-scheme
217 (primitive-implementation proc) args))
218 (define input-prompt ";;; M-Eval input:")
219 (define output-prompt ";;; M-Eval value:")
220 (define (driver-loop)
221 (prompt-for-input input-prompt)
222 (let ((input (read)))
223 (let ((output (eval input the-global-environment)))
224 (announce-output output-prompt)
225 (user-print output)))
227 (define (prompt-for-input string)
228 (newline) (newline) (display string) (newline))
230 (define (announce-output string)
231 (newline) (display string) (newline))
232 (define (user-print object)
233 (if (compound-procedure? object)
234 (display (list 'compound-procedure
235 (procedure-parameters object)
236 (procedure-body object)
239 (define (setup-environment)
241 (extend-environment (primitive-procedure-names)
242 (primitive-procedure-objects)
243 the-empty-environment)))
244 (define-variable! 'true true initial-env)
245 (define-variable! 'false false initial-env)
247 (define the-global-environment (setup-environment))
249 (define (make-let vars vals body)
251 (cons (map (lambda (var val)
256 (tagged-list? exp 'let))
257 (define (let-vars exp)
258 (map car (cadr exp)))
259 (define (let-vals exp)
260 (map cadr (cadr exp)))
261 (define (let-body exp)
263 (define (let->combination exp)
264 (make-application (make-lambda (let-vars exp) (let-body exp))
266 (define (make-application op args)
269 (define (test-case actual expected)
274 (display "Expected: ")
278 (define (geval exp) ;; eval globally
279 (eval exp the-global-environment))
281 ;; Exercise 4.4. Recall the definitions of the special forms and and or from chapter 1:
283 ;; and: The expressions are evaluated from left to right. If any expression evaluates to false, false is returned; any remaining expressions are not evaluated. If all the expressions evaluate to true values, the value of the last expression is returned. If there are no expressions then true is returned.
285 ;; or: The expressions are evaluated from left to right. If any expression evaluates to a true value, that value is returned; any remaining expressions are not evaluated. If all expressions evaluate to false, or if there are no expressions, then false is returned.
287 ;; Install and and or as new special forms for the evaluator by defining appropriate syntax procedures and evaluation procedures eval-and and eval-or. Alternatively, show how to implement and and or as derived expressions.
290 (tagged-list? exp 'and))
291 (define (and-clauses exp)
293 ;; (define (and->if exp)
294 ;; (define (expand-clauses clauses)
295 ;; (cond ((null? clauses) 'true)
296 ;; ((null? (cdr clauses)) (car clauses))
297 ;; (else (make-if (car clauses)
298 ;; (expand-clauses (cdr clauses))
300 ;; (expand-clauses (and-clauses exp)))
302 (tagged-list? exp 'or))
303 (define (or-clauses exp)
305 ;; the problem with this definition is that each clause will be evaluated twice; this is unacceptable if there are side effects
306 ;; (define (or->if exp)
307 ;; (define (expand-clauses clauses)
308 ;; (if (null? clauses)
310 ;; (make-if (car clauses)
312 ;; (expand-clauses (cdr clauses)))))
313 ;; (expand-clauses (or-clauses exp)))
316 ;; we can also install and/or as special forms
318 (define (eval-and exp env)
319 (define (eval-clauses clauses)
320 (cond ((null? clauses) true)
321 ((null? (cdr clauses)) (eval (car clauses) env))
322 (else (and (eval (car clauses) env)
323 (eval-clauses (cdr clauses))))))
324 (eval-clauses (and-clauses exp)))
325 (define (eval-or exp env)
326 (define (eval-clauses clauses)
329 (or (eval (car clauses) env)
330 (eval-clauses (cdr clauses)))))
331 (eval-clauses (or-clauses exp)))
334 ;; Exercise 4.5. Scheme allows an additional syntax for cond clauses, (<test> => <recipient>). If <test> evaluates to a true value, then <recipient> is evaluated. Its value must be a procedure of one argument; this procedure is then invoked on the value of the <test>, and the result is returned as the value of the cond expression. For example
336 ;; (cond ((assoc 'b '((a 1) (b 2))) => cadr)
339 ;; returns 2. Modify the handling of cond so that it supports this extended syntax.
341 (define (cond? exp) (tagged-list? exp 'cond))
342 (define (cond-clauses exp) (cdr exp))
343 (define (cond-else-clause? clause)
344 (eq? (cond-predicate clause) 'else))
345 (define (cond-predicate clause) (car clause))
346 (define (cond-actions clause) (cdr clause))
347 (define (cond-extended-clause? clause)
348 (and (not (null? (cdr clause))) (eq? (cadr clause) '=>)))
349 (define (cond-extended-proc clause)
351 (define (cond->if exp)
352 (expand-clauses (cond-clauses exp)))
354 (define (expand-clauses clauses)
356 'false ; no else clause
357 (let ((first (car clauses))
358 (rest (cdr clauses)))
359 (if (cond-else-clause? first)
361 (sequence->exp (cond-actions first))
362 (error "ELSE clause isn't last -- COND->IF"
364 (if (cond-extended-clause? first)
365 (make-if (cond-predicate first)
367 (cond-extended-proc first)
368 (list (cond-predicate first)))
369 (expand-clauses rest))
370 (make-if (cond-predicate first)
371 (sequence->exp (cond-actions first))
372 (expand-clauses rest)))))))
375 ;; procedure definitions
378 '(define (assoc key records)
379 (cond ((null? records) false)
380 ((equal? key (caar records)) (car records))
381 (else (assoc key (cdr records))))))
384 '(define (map proc list)
387 (cons (proc (car list))
388 (map proc (cdr list))))))
391 '(define (accumulate op initial sequence)
395 (accumulate op initial (cdr sequence))))))
401 '(cond ((assoc 'b '((a 1) (b 2))) => cadr)
415 '(cond ((= 3 4) 'not-true)
416 ((= (* 2 4) 3) 'also-false)
423 (else 'never-reach)))
431 (test-case (geval (make-let '(x y) '(3 5) '((+ x y))))
435 (geval '(define x (+ 3 8)))
436 (test-case (geval '(and 0 true x)) 11)
437 (test-case (geval '(and 0 true x false)) false)
438 (test-case (geval '(and 0 true x (set! x -2) false)) false)
439 (test-case (geval 'x) -2)
440 (test-case (geval '(and 0 true x false (set! x -5))) false)
441 (test-case (geval 'x) -2)
442 (test-case (geval '(or false (set! x 25))) 'ok)
443 (test-case (geval 'x) 25)
444 (test-case (geval '(or (set! x 2) (set! x 4))) 'ok)
445 (test-case (geval 'x) 2)
446 (test-case (geval '(or false (set! x 25) true false)) 'ok)
447 (test-case (geval 'x) 25)
448 (test-case (geval '(or ((lambda (x) x) 5))) 5)
449 (test-case (geval '(or (begin (set! x (+ x 1)) x))) 26)
453 (test-case (geval '(begin 5 6)) 6)
454 (test-case (geval '10) 10)
455 (geval '(define x 3))
456 (test-case (geval 'x) 3)
457 (test-case (geval '(set! x -25)) 'ok)
458 (test-case (geval 'x) -25)
459 (geval '(define z (lambda (x y) (+ x (* x y)))))
460 (test-case (geval '(z 3 4)) 15)
461 (test-case (geval '(cond ((= x -2) 'x=-2)
465 (test-case (geval '(if true false true)) false)
471 ;; procedure definition and application
473 '(define (factorial n)
476 (* n (factorial (- n 1))))))
477 (test-case (geval '(factorial 5)) 120)
482 (geval '(map (lambda (x)
490 '(accumulate + 0 '(1 2 3 4 5)))