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)
222 (list 'display display)))
223 (define (primitive-procedure-names)
225 primitive-procedures))
227 (define (primitive-procedure-objects)
228 (map (lambda (proc) (list 'primitive (cadr proc)))
229 primitive-procedures))
230 (define (apply-primitive-procedure proc args)
231 (apply-in-underlying-scheme
232 (primitive-implementation proc) args))
233 (define input-prompt ";;; M-Eval input:")
234 (define output-prompt ";;; M-Eval value:")
235 (define (driver-loop)
236 (prompt-for-input input-prompt)
237 (let ((input (read)))
238 (let ((output (eval input the-global-environment)))
239 (announce-output output-prompt)
240 (user-print output)))
242 (define (prompt-for-input string)
243 (newline) (newline) (display string) (newline))
245 (define (announce-output string)
246 (newline) (display string) (newline))
247 (define (user-print object)
248 (if (compound-procedure? object)
249 (display (list 'compound-procedure
250 (procedure-parameters object)
251 (procedure-body object)
254 (define (setup-environment)
256 (extend-environment (primitive-procedure-names)
257 (primitive-procedure-objects)
258 the-empty-environment)))
259 (define-variable! 'true true initial-env)
260 (define-variable! 'false false initial-env)
262 (define the-global-environment (setup-environment))
265 (tagged-list? exp 'let))
266 (define (let-vars exp)
267 (map car (cadr exp)))
268 (define (let-vals exp)
269 (map cadr (cadr exp)))
270 (define (let-body exp)
272 (define (let->combination exp)
273 (make-application (make-lambda (let-vars exp) (let-body exp))
275 (define (make-application op args)
278 (define (test-case actual expected)
283 (display "Expected: ")
287 (define (geval exp) ;; eval globally
288 (eval exp the-global-environment))
290 ;; Exercise 4.2. Louis Reasoner plans to reorder the cond clauses in eval so that the clause for procedure applications appears before the clause for assignments. He argues that this will make the interpreter more efficient: Since programs usually contain more applications than assignments, definitions, and so on, his modified eval will usually check fewer clauses than the original eval before identifying the type of an expression.
292 ;; a. What is wrong with Louis's plan? (Hint: What will Louis's evaluator do with the expression (define x 3)?)
294 ;; the define special form will be interpreted as an application because the only requirement is that the expression be a pair
296 ;; b. Louis is upset that his plan didn't work. He is willing to go to any lengths to make his evaluator recognize procedure applications before it checks for most other kinds of expressions. Help him by changing the syntax of the evaluated language so that procedure applications start with call. For example, instead of (factorial 3) we will now have to write (call factorial 3) and instead of (+ 1 2) we will have to write (call + 1 2).
298 (define (application? exp) (tagged-list? exp 'call))
299 (define (operator exp) (cadr exp))
300 (define (operands exp) (cddr exp))
301 (define (make-application op args)
302 (cons 'call (cons op args)))
304 '(define (factorial n)
307 (call * n (call factorial (call - n 1))))))
308 (test-case (geval '(call factorial 5)) 120)
312 (call + x y (call * x y))))
