1 ;; The first three lines of this file were inserted by DrScheme. They record metadata
2 ;; about the language level of this file in a form that our tools can easily process.
3 #reader(lib "htdp-advanced-reader.ss" "lang")((modname |32.1|) (read-case-sensitive #t) (teachpacks ((lib "draw.ss" "teachpack" "htdp") (lib "arrow.ss" "teachpack" "htdp") (lib "gui.ss" "teachpack" "htdp"))) (htdp-settings #(#t constructor repeating-decimal #t #t none #f ((lib "draw.ss" "teachpack" "htdp") (lib "arrow.ss" "teachpack" "htdp") (lib "gui.ss" "teachpack" "htdp")))))
4 ;A SchemeData (a representation of a Scheme expression) is either
5 ;1. a number,
6 ;2. a symbol,
7 ;3. an operator structure, or
8 ;4. a function structure.
9 
10 (define-struct add (left right))
11 (define-struct sub (left right))
12 (define-struct mul (left right))
13 (define-struct div (left right))
14 
15 ;An operator is a structure
16 ;(make-operator left right)
17 ;where operator is replaced by one of the four operators:
18 ;1. add (addition)
19 ;2. sub (subtraction)
20 ;3. mul (multiplication)
21 ;4. div (division)
22 ;and left and right are SchemeData.
23 
24 ;
25 
26 ;An operator structure
27 
28 ;(make-operator left right)
29 
30 ;represents the expression
31 
32 ;(operator left right)
33 
34 ;in Scheme.
35 
36 
37 
38 (define-struct function (name arg))
39 
40 
41 
42 ;A function is a structure
43 
44 ;(make-function name arg)
45 
46 ;where name is a symbol and arg is a SchemeData.
47 
48 ;
49 
50 ;A function structure
51 
52 ;(make-function name arg)
53 
54 ;represents the expression
55 
56 ;(name arg)
57 
58 
59 
60 (define-struct definition (function parameter body))
61 
62 
63 
64 ;A definition is a structure
65 
66 ;(make-definition function parameter body)
67 
68 ;where function and parameter are symbols and body is a SchemeData.
69 
70 ;numeric? : SchemeData -> boolean
71 
72 ;Given a-data, determine if the expression it
73 
74 ;represents is numeric. That is,
75 
76 ;numeric? evaluates true if the SchemeData lacks symbols,
77 
78 ;which represents an expression which
79 
80 ;lacks variables.
81 
82 
83 
84 (define (numeric? a-data)
85 
86   (cond
87 
88     [(number? a-data) true]
89 
90     [(add? a-data) (and (numeric? (add-left a-data))
91 
92                         (numeric?(add-right a-data)))]
93 
94     [(sub? a-data) (and (numeric? (sub-left a-data)) 
95 
96                         (numeric? (sub-right a-data)))]
97 
98     [(mul? a-data) (and (numeric? (mul-left a-data)) 
99 
100                         (numeric? (mul-right a-data)))]
101 
102     [(div? a-data) (and (numeric? (div-left a-data)) 
103 
104                         (numeric? (div-right a-data)))]
105 
106     [else false]))
107 
108 
109 
110 ;evaluate-expression : SchemeData -> number
111 
112 ;Given a-data, evaluates the numeric expression it represents
113 
114 ;and returns the value.
115 
116 
117 
118 (define (evaluate-expression a-data)
119 
120   (cond
121 
122     [(number? a-data) a-data]
123 
124     [(add? a-data) (+ (evaluate-expression (add-left a-data))
125 
126                       (evaluate-expression (add-right a-data)))]
127 
128     [(sub? a-data) (- (evaluate-expression (sub-left a-data))
129 
130                       (evaluate-expression (sub-right a-data)))]
131 
132     [(mul? a-data) (* (evaluate-expression (mul-left a-data))
133 
134                       (evaluate-expression (mul-right a-data)))]
135 
136     [(div? a-data) (/ (evaluate-expression (div-left a-data))
137 
138                       (evaluate-expression (div-right a-data)))]))
139 
140 
141 
142 ;subst : symbol number SchemeData -> SchemeData
143 
144 ;Given the representation of a variable V (symbol),
145 
146 ;the number N, and a SchemeData which represents an expression,
147 
148 ;produce a new SchemeData representing an expression
149 
150 ;where all occurrences of the variable V (symbol)
151 
152 ;have been replaced with the number N.
153 
154 
155 
156 (define (subst V N a-data)
157 
158   (cond
159 
160     [(number? a-data) a-data]
161 
162     [(symbol? a-data) (cond
163 
164                         [(symbol=? a-data V) N]
165 
166                         [else a-data])]
167 
168     [(add? a-data) (make-add (subst V N (add-left a-data)) 
169 
170                              (subst V N (add-right a-data)))]
171 
172     [(sub? a-data) (make-sub (subst V N (sub-left a-data)) 
173 
174                              (subst V N (sub-right a-data)))]
175 
176     [(mul? a-data) (make-mul (subst V N (mul-left a-data)) 
177 
178                              (subst V N (mul-right a-data)))]
179 
180     [(div? a-data) (make-div (subst V N (div-left a-data)) 
181 
182                              (subst V N (div-right a-data)))]
183 
184     [else a-data]))
185 
186 
187 
188 ;evaluate-with-one-def : SchemeData definition -> number
189 
190 ;Given an-exp and P, evaluate the argument an-exp, substitute that for the parameter in P, and then evaluate the body of P.
191 
192 
193 
194 (define (evaluate-with-one-def an-exp P)
195 
196   (cond
197 
198     [(and (definition? P)
199 
200           (numeric? an-exp)) (evaluate-expression (subst (definition-parameter P)
201 
202                                                          (evaluate-expression an-exp)
203 
204                                                          (definition-body P)))]
205 
206     [else (error 'evaluate-with-one-def "unexpected error")]))
207 
208 
209 
210 ;evaluate-with-defs : SchemeData list-of-definitions -> list-of-numbers
211 
212 ;Given an-exp and defs, evaluate an-exp, substitute this value in the body for each definition in the list-of-definitions in place of each one's parameter and evaluate the resulting body. 
213 
214 (define (evaluate-with-defs an-exp defs)
215 
216   (cond
217 
218     [(empty? defs) empty]
219 
220     [(cons? defs) (cons (evaluate-with-one-def an-exp (first defs))
221 
222                         (evaluate-with-defs an-exp (rest defs)))]))
223 
224 
225 
226 
227 
228 ;test-evaluate SchemeData list-of-definitions list-of-numbers -> boolean
229 
230 ;Given an-exp, defs, and expected-result, evaluate an-exp, substitute it for the parameter for the body of each of the function definitions in defs, evaluate the resulting expressions, and compare that with expected-result.  Return true if the two list-of-numbers are identical, false otherwise.
231 
232 
233 
234 (define (test-evaluate an-exp defs expected-result)
235 
236   (equal? (evaluate-with-defs an-exp defs) expected-result))
237