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))
12 (make-procedure (lambda-parameters exp)
16 (eval-sequence (begin-actions exp) env))
17 ((cond? exp) (eval (cond->if exp) env))
18 ((let? exp) (eval (let->combination exp) env))
20 (apply (eval (operator exp) env)
21 (list-of-values (operands exp) env)))
23 (error "Unknown expression type -- EVAL" exp))))
25 (define (apply procedure arguments)
26 (cond ((primitive-procedure? procedure)
27 (apply-primitive-procedure procedure arguments))
28 ((compound-procedure? procedure)
30 (procedure-body procedure)
32 (procedure-parameters procedure)
34 (procedure-environment procedure))))
37 "Unknown procedure type -- APPLY" procedure))))
38 (define (list-of-values exps env)
39 (if (no-operands? exps)
41 (cons (eval (first-operand exps) env)
42 (list-of-values (rest-operands exps) env))))
44 (define (eval-if exp env)
45 (if (true? (eval (if-predicate exp) env))
46 (eval (if-consequent exp) env)
47 (eval (if-alternative exp) env)))
48 (define (eval-sequence exps env)
49 (cond ((last-exp? exps) (eval (first-exp exps) env))
50 (else (eval (first-exp exps) env)
51 (eval-sequence (rest-exps exps) env))))
52 (define (eval-assignment exp env)
53 (set-variable-value! (assignment-variable exp)
54 (eval (assignment-value exp) env)
57 (define (eval-definition exp env)
58 (define-variable! (definition-variable exp)
59 (eval (definition-value exp) env)
62 (define (self-evaluating? exp)
63 (cond ((number? exp) true)
66 (define (variable? exp) (symbol? exp))
68 (tagged-list? exp 'quote))
70 (define (text-of-quotation exp) (cadr exp))
71 (define (tagged-list? exp tag)
75 (define (assignment? exp)
76 (tagged-list? exp 'set!))
77 (define (assignment-variable exp) (cadr exp))
78 (define (assignment-value exp) (caddr exp))
79 (define (definition? exp)
80 (tagged-list? exp 'define))
81 (define (definition-variable exp)
82 (if (symbol? (cadr exp))
85 (define (definition-value exp)
86 (if (symbol? (cadr exp))
88 (make-lambda (cdadr exp) ; formal parameters
90 (define (lambda? exp) (tagged-list? exp 'lambda))
91 (define (lambda-parameters exp) (cadr exp))
92 (define (lambda-body exp) (cddr exp))
93 (define (make-lambda parameters body)
94 (cons 'lambda (cons parameters body)))
95 (define (if? exp) (tagged-list? exp 'if))
96 (define (if-predicate exp) (cadr exp))
97 (define (if-consequent exp) (caddr exp))
98 (define (if-alternative exp)
99 (if (not (null? (cdddr exp)))
102 (define (make-if predicate consequent alternative)
103 (list 'if predicate consequent alternative))
104 (define (begin? exp) (tagged-list? exp 'begin))
105 (define (begin-actions exp) (cdr exp))
106 (define (last-exp? seq) (null? (cdr seq)))
107 (define (first-exp seq) (car seq))
108 (define (rest-exps seq) (cdr seq))
110 (define (sequence->exp seq)
111 (cond ((null? seq) seq)
112 ((last-exp? seq) (first-exp seq))
113 (else (make-begin seq))))
114 (define (make-begin seq) (cons 'begin seq))
115 (define (application? exp) (pair? exp))
116 (define (operator exp) (car exp))
117 (define (operands exp) (cdr exp))
118 (define (no-operands? ops) (null? ops))
119 (define (first-operand ops) (car ops))
120 (define (rest-operands ops) (cdr ops))
121 (define (cond? exp) (tagged-list? exp 'cond))
122 (define (cond-clauses exp) (cdr exp))
123 (define (cond-else-clause? clause)
124 (eq? (cond-predicate clause) 'else))
125 (define (cond-predicate clause) (car clause))
126 (define (cond-actions clause) (cdr clause))
127 (define (cond->if exp)
128 (expand-clauses (cond-clauses exp)))
130 (define (expand-clauses clauses)
132 'false ; no else clause
133 (let ((first (car clauses))
134 (rest (cdr clauses)))
135 (if (cond-else-clause? first)
137 (sequence->exp (cond-actions first))
138 (error "ELSE clause isn't last -- COND->IF"
140 (make-if (cond-predicate first)
141 (sequence->exp (cond-actions first))
142 (expand-clauses rest))))))
147 (define (make-procedure parameters body env)
148 (list 'procedure parameters body env))
149 (define (compound-procedure? p)
150 (tagged-list? p 'procedure))
151 (define (procedure-parameters p) (cadr p))
152 (define (procedure-body p) (caddr p))
153 (define (procedure-environment p) (cadddr p))
154 (define (enclosing-environment env) (cdr env))
155 (define (first-frame env) (car env))
156 (define the-empty-environment '())
157 (define (make-frame variables values)
158 (cons variables values))
159 (define (frame-variables frame) (car frame))
160 (define (frame-values frame) (cdr frame))
161 (define (add-binding-to-frame! var val frame)
162 (set-car! frame (cons var (car frame)))
163 (set-cdr! frame (cons val (cdr frame))))
164 (define (extend-environment vars vals base-env)
165 (if (= (length vars) (length vals))
166 (cons (make-frame vars vals) base-env)
167 (if (< (length vars) (length vals))
168 (error "Too many arguments supplied" vars vals)
169 (error "Too few arguments supplied" vars vals))))
170 (define (lookup-variable-value var env)
171 (define (env-loop env)
172 (define (scan vars vals)
174 (env-loop (enclosing-environment env)))
175 ((eq? var (car vars))
177 (else (scan (cdr vars) (cdr vals)))))
178 (if (eq? env the-empty-environment)
179 (error "Unbound variable" var)
180 (let ((frame (first-frame env)))
181 (scan (frame-variables frame)
182 (frame-values frame)))))
184 (define (set-variable-value! var val env)
185 (define (env-loop env)
186 (define (scan vars vals)
188 (env-loop (enclosing-environment env)))
189 ((eq? var (car vars))
191 (else (scan (cdr vars) (cdr vals)))))
192 (if (eq? env the-empty-environment)
193 (error "Unbound variable -- SET!" var)
194 (let ((frame (first-frame env)))
195 (scan (frame-variables frame)
196 (frame-values frame)))))
198 (define (define-variable! var val env)
199 (let ((frame (first-frame env)))
200 (define (scan vars vals)
202 (add-binding-to-frame! var val frame))
203 ((eq? var (car vars))
205 (else (scan (cdr vars) (cdr vals)))))
206 (scan (frame-variables frame)
207 (frame-values frame))))
208 (define (primitive-procedure? proc)
209 (tagged-list? proc 'primitive))
211 (define (primitive-implementation proc) (cadr proc))
212 (define primitive-procedures
213 (list (list 'car car)
221 (define (primitive-procedure-names)
223 primitive-procedures))
225 (define (primitive-procedure-objects)
226 (map (lambda (proc) (list 'primitive (cadr proc)))
227 primitive-procedures))
228 (define (apply-primitive-procedure proc args)
229 (apply-in-underlying-scheme
230 (primitive-implementation proc) args))
231 (define input-prompt ";;; M-Eval input:")
232 (define output-prompt ";;; M-Eval value:")
233 (define (driver-loop)
234 (prompt-for-input input-prompt)
235 (let ((input (read)))
236 (let ((output (eval input the-global-environment)))
237 (announce-output output-prompt)
238 (user-print output)))
240 (define (prompt-for-input string)
241 (newline) (newline) (display string) (newline))
243 (define (announce-output string)
244 (newline) (display string) (newline))
245 (define (user-print object)
246 (if (compound-procedure? object)
247 (display (list 'compound-procedure
248 (procedure-parameters object)
249 (procedure-body object)
252 (define (setup-environment)
254 (extend-environment (primitive-procedure-names)
255 (primitive-procedure-objects)
256 the-empty-environment)))
257 (define-variable! 'true true initial-env)
258 (define-variable! 'false false initial-env)
260 (define the-global-environment (setup-environment))
262 ;; Exercise 4.1. Notice that we cannot tell whether the metacircular evaluator evaluates operands from left to right or from right to left. Its evaluation order is inherited from the underlying Lisp: If the arguments to cons in list-of-values are evaluated from left to right, then list-of-values will evaluate operands from left to right; and if the arguments to cons are evaluated from right to left, then list-of-values will evaluate operands from right to left.
264 ;; Write a version of list-of-values that evaluates operands from left to right regardless of the order of evaluation in the underlying Lisp. Also write a version of list-of-values that evaluates operands from right to left.
266 ;; Exercise 4.6. Let expressions are derived expressions, because
268 ;; (let ((<var1> <exp1>) ... (<varn> <expn>))
273 ;; ((lambda (<var1> ... <varn>)
279 ;; Implement a syntactic transformation let->combination that reduces evaluating let expressions to evaluating combinations of the type shown above, and add the appropriate clause to eval to handle let expressions.
282 (tagged-list? exp 'let))
283 (define (let-vars exp)
284 (map car (cadr exp)))
285 (define (let-vals exp)
286 (map cadr (cadr exp)))
287 (define (let-body exp)
289 (define (let->combination exp)
290 (cons (make-lambda (let-vars exp) (let-body exp))
293 (define (test-case actual expected)
298 (display "Expected: ")
305 the-global-environment)
308 ;; '(define old-value
314 ;; the-global-environment)
318 ;; (eval-test-case '((old-value 5) (old-value 3)