1 12687dd9 2023-08-04 jrmu ;; The first three lines of this file were inserted by DrScheme. They record metadata
2 12687dd9 2023-08-04 jrmu ;; about the language level of this file in a form that our tools can easily process.
3 12687dd9 2023-08-04 jrmu #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 12687dd9 2023-08-04 jrmu ;A SchemeData (a representation of a Scheme expression) is either
5 12687dd9 2023-08-04 jrmu ;1. a number,
6 12687dd9 2023-08-04 jrmu ;2. a symbol,
7 12687dd9 2023-08-04 jrmu ;3. an operator structure, or
8 12687dd9 2023-08-04 jrmu ;4. a function structure.
10 12687dd9 2023-08-04 jrmu (define-struct add (left right))
11 12687dd9 2023-08-04 jrmu (define-struct sub (left right))
12 12687dd9 2023-08-04 jrmu (define-struct mul (left right))
13 12687dd9 2023-08-04 jrmu (define-struct div (left right))
15 12687dd9 2023-08-04 jrmu ;An operator is a structure
16 12687dd9 2023-08-04 jrmu ;(make-operator left right)
17 12687dd9 2023-08-04 jrmu ;where operator is replaced by one of the four operators:
18 12687dd9 2023-08-04 jrmu ;1. add (addition)
19 12687dd9 2023-08-04 jrmu ;2. sub (subtraction)
20 12687dd9 2023-08-04 jrmu ;3. mul (multiplication)
21 12687dd9 2023-08-04 jrmu ;4. div (division)
22 12687dd9 2023-08-04 jrmu ;and left and right are SchemeData.
26 12687dd9 2023-08-04 jrmu ;An operator structure
28 12687dd9 2023-08-04 jrmu ;(make-operator left right)
30 12687dd9 2023-08-04 jrmu ;represents the expression
32 12687dd9 2023-08-04 jrmu ;(operator left right)
38 12687dd9 2023-08-04 jrmu (define-struct function (name arg))
42 12687dd9 2023-08-04 jrmu ;A function is a structure
44 12687dd9 2023-08-04 jrmu ;(make-function name arg)
46 12687dd9 2023-08-04 jrmu ;where name is a symbol and arg is a SchemeData.
50 12687dd9 2023-08-04 jrmu ;A function structure
52 12687dd9 2023-08-04 jrmu ;(make-function name arg)
54 12687dd9 2023-08-04 jrmu ;represents the expression
60 12687dd9 2023-08-04 jrmu (define-struct definition (function parameter body))
64 12687dd9 2023-08-04 jrmu ;A definition is a structure
66 12687dd9 2023-08-04 jrmu ;(make-definition function parameter body)
68 12687dd9 2023-08-04 jrmu ;where function and parameter are symbols and body is a SchemeData.
70 12687dd9 2023-08-04 jrmu ;numeric? : SchemeData -> boolean
72 12687dd9 2023-08-04 jrmu ;Given a-data, determine if the expression it
74 12687dd9 2023-08-04 jrmu ;represents is numeric. That is,
76 12687dd9 2023-08-04 jrmu ;numeric? evaluates true if the SchemeData lacks symbols,
78 12687dd9 2023-08-04 jrmu ;which represents an expression which
80 12687dd9 2023-08-04 jrmu ;lacks variables.
84 12687dd9 2023-08-04 jrmu (define (numeric? a-data)
88 12687dd9 2023-08-04 jrmu [(number? a-data) true]
90 12687dd9 2023-08-04 jrmu [(add? a-data) (and (numeric? (add-left a-data))
92 12687dd9 2023-08-04 jrmu (numeric?(add-right a-data)))]
94 12687dd9 2023-08-04 jrmu [(sub? a-data) (and (numeric? (sub-left a-data))
96 12687dd9 2023-08-04 jrmu (numeric? (sub-right a-data)))]
98 12687dd9 2023-08-04 jrmu [(mul? a-data) (and (numeric? (mul-left a-data))
100 12687dd9 2023-08-04 jrmu (numeric? (mul-right a-data)))]
102 12687dd9 2023-08-04 jrmu [(div? a-data) (and (numeric? (div-left a-data))
104 12687dd9 2023-08-04 jrmu (numeric? (div-right a-data)))]
106 12687dd9 2023-08-04 jrmu [else false]))
110 12687dd9 2023-08-04 jrmu ;evaluate-expression : SchemeData -> number
112 12687dd9 2023-08-04 jrmu ;Given a-data, evaluates the numeric expression it represents
114 12687dd9 2023-08-04 jrmu ;and returns the value.
118 12687dd9 2023-08-04 jrmu (define (evaluate-expression a-data)
122 12687dd9 2023-08-04 jrmu [(number? a-data) a-data]
124 12687dd9 2023-08-04 jrmu [(add? a-data) (+ (evaluate-expression (add-left a-data))
126 12687dd9 2023-08-04 jrmu (evaluate-expression (add-right a-data)))]
128 12687dd9 2023-08-04 jrmu [(sub? a-data) (- (evaluate-expression (sub-left a-data))
130 12687dd9 2023-08-04 jrmu (evaluate-expression (sub-right a-data)))]
132 12687dd9 2023-08-04 jrmu [(mul? a-data) (* (evaluate-expression (mul-left a-data))
134 12687dd9 2023-08-04 jrmu (evaluate-expression (mul-right a-data)))]
136 12687dd9 2023-08-04 jrmu [(div? a-data) (/ (evaluate-expression (div-left a-data))
138 12687dd9 2023-08-04 jrmu (evaluate-expression (div-right a-data)))]))
142 12687dd9 2023-08-04 jrmu ;subst : symbol number SchemeData -> SchemeData
144 12687dd9 2023-08-04 jrmu ;Given the representation of a variable V (symbol),
146 12687dd9 2023-08-04 jrmu ;the number N, and a SchemeData which represents an expression,
148 12687dd9 2023-08-04 jrmu ;produce a new SchemeData representing an expression
150 12687dd9 2023-08-04 jrmu ;where all occurrences of the variable V (symbol)
152 12687dd9 2023-08-04 jrmu ;have been replaced with the number N.
156 12687dd9 2023-08-04 jrmu (define (subst V N a-data)
160 12687dd9 2023-08-04 jrmu [(number? a-data) a-data]
162 12687dd9 2023-08-04 jrmu [(symbol? a-data) (cond
164 12687dd9 2023-08-04 jrmu [(symbol=? a-data V) N]
166 12687dd9 2023-08-04 jrmu [else a-data])]
168 12687dd9 2023-08-04 jrmu [(add? a-data) (make-add (subst V N (add-left a-data))
170 12687dd9 2023-08-04 jrmu (subst V N (add-right a-data)))]
172 12687dd9 2023-08-04 jrmu [(sub? a-data) (make-sub (subst V N (sub-left a-data))
174 12687dd9 2023-08-04 jrmu (subst V N (sub-right a-data)))]
176 12687dd9 2023-08-04 jrmu [(mul? a-data) (make-mul (subst V N (mul-left a-data))
178 12687dd9 2023-08-04 jrmu (subst V N (mul-right a-data)))]
180 12687dd9 2023-08-04 jrmu [(div? a-data) (make-div (subst V N (div-left a-data))
182 12687dd9 2023-08-04 jrmu (subst V N (div-right a-data)))]
184 12687dd9 2023-08-04 jrmu [else a-data]))
188 12687dd9 2023-08-04 jrmu ;evaluate-with-one-def : SchemeData definition -> number
190 12687dd9 2023-08-04 jrmu ;Given an-exp and P, evaluate the argument an-exp, substitute that for the parameter in P, and then evaluate the body of P.
194 12687dd9 2023-08-04 jrmu (define (evaluate-with-one-def an-exp P)
198 12687dd9 2023-08-04 jrmu [(and (definition? P)
200 12687dd9 2023-08-04 jrmu (numeric? an-exp)) (evaluate-expression (subst (definition-parameter P)
202 12687dd9 2023-08-04 jrmu (evaluate-expression an-exp)
204 12687dd9 2023-08-04 jrmu (definition-body P)))]
206 12687dd9 2023-08-04 jrmu [else (error 'evaluate-with-one-def "unexpected error")]))
210 12687dd9 2023-08-04 jrmu ;evaluate-with-defs : SchemeData list-of-definitions -> list-of-numbers
212 12687dd9 2023-08-04 jrmu ;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.
214 12687dd9 2023-08-04 jrmu (define (evaluate-with-defs an-exp defs)
218 12687dd9 2023-08-04 jrmu [(empty? defs) empty]
220 12687dd9 2023-08-04 jrmu [(cons? defs) (cons (evaluate-with-one-def an-exp (first defs))
222 12687dd9 2023-08-04 jrmu (evaluate-with-defs an-exp (rest defs)))]))
228 12687dd9 2023-08-04 jrmu ;test-evaluate SchemeData list-of-definitions list-of-numbers -> boolean
230 12687dd9 2023-08-04 jrmu ;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.
234 12687dd9 2023-08-04 jrmu (define (test-evaluate an-exp defs expected-result)
236 12687dd9 2023-08-04 jrmu (equal? (evaluate-with-defs an-exp defs) expected-result))