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-intermediate-reader.ss" "lang")((modname 17.8.12) (read-case-sensitive #t) (teachpacks ((lib "draw.ss" "teachpack" "htdp") (lib "arrow.ss" "teachpack" "htdp") (lib "dir.ss" "teachpack" "htdp") (lib "hangman.ss" "teachpack" "htdp"))) (htdp-settings #(#t constructor repeating-decimal #f #t none #f ((lib "draw.ss" "teachpack" "htdp") (lib "arrow.ss" "teachpack" "htdp") (lib "dir.ss" "teachpack" "htdp") (lib "hangman.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.
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 ;An operator structure
25 ;(make-operator left right)
26 ;represents the expression
27 ;(operator left right)
28 ;in Scheme.
29 
30 (define-struct function (name arg))
31 
32 ;A function is a structure
33 ;(make-function name arg)
34 ;where name is a symbol and arg is a SchemeData.
35 ;
36 ;A function structure
37 ;(make-function name arg)
38 ;represents the expression
39 ;(name arg)
40 
41 (define-struct definition (function parameter body))
42 
43 ;A definition is a structure
44 ;(make-definition function parameter body)
45 ;where function and parameter are symbols and body is a SchemeData.
46 ;numeric? : SchemeData -> boolean
47 ;Given a-data, determine if the expression it
48 ;represents is numeric. That is,
49 ;numeric? evaluates true if the SchemeData lacks symbols,
50 ;which represents an expression which
51 ;lacks variables.
52 
53 (define (numeric? a-data)
54   (cond
55     [(number? a-data) true]
56     [(add? a-data) (and (numeric? (add-left a-data))
57                         (numeric?(add-right a-data)))]
58     [(sub? a-data) (and (numeric? (sub-left a-data)) 
59                         (numeric? (sub-right a-data)))]
60     [(mul? a-data) (and (numeric? (mul-left a-data)) 
61                         (numeric? (mul-right a-data)))]
62     [(div? a-data) (and (numeric? (div-left a-data)) 
63                         (numeric? (div-right a-data)))]
64     [else false]))
65 
66 ;evaluate-expression : SchemeData -> number
67 ;Given a-data, evaluates the numeric expression it represents
68 ;and returns the value.
69 
70 (define (evaluate-expression a-data)
71   (cond
72     [(number? a-data) a-data]
73     [(add? a-data) (+ (evaluate-expression (add-left a-data))
74                       (evaluate-expression (add-right a-data)))]
75     [(sub? a-data) (- (evaluate-expression (sub-left a-data))
76                       (evaluate-expression (sub-right a-data)))]
77     [(mul? a-data) (* (evaluate-expression (mul-left a-data))
78                       (evaluate-expression (mul-right a-data)))]
79     [(div? a-data) (/ (evaluate-expression (div-left a-data))
80                       (evaluate-expression (div-right a-data)))]))
81 
82 ;subst : symbol number SchemeData -> SchemeData
83 ;Given the representation of a variable V (symbol),
84 ;the number N, and a SchemeData which represents an expression,
85 ;produce a new SchemeData representing an expression
86 ;where all occurrences of the variable V (symbol)
87 ;have been replaced with the number N.
88 
89 (define (subst V N a-data)
90   (cond
91     [(number? a-data) a-data]
92     [(symbol? a-data) (cond
93                         [(symbol=? a-data V) N]
94                         [else a-data])]
95     [(add? a-data) (make-add (subst V N (add-left a-data)) 
96                              (subst V N (add-right a-data)))]
97     [(sub? a-data) (make-sub (subst V N (sub-left a-data)) 
98                              (subst V N (sub-right a-data)))]
99     [(mul? a-data) (make-mul (subst V N (mul-left a-data)) 
100                              (subst V N (mul-right a-data)))]
101     [(div? a-data) (make-div (subst V N (div-left a-data)) 
102                              (subst V N (div-right a-data)))]
103     [else a-data]))
104 
105 ;evaluate-with-one-def : SchemeData definition -> number
106 ;Given an-exp and P, evaluate the argument an-exp, substitute that for the parameter in P, and then evaluate the body of P.
107 
108 (define (evaluate-with-one-def an-exp P)
109   (cond
110     [(and (definition? P)
111           (numeric? an-exp)) (evaluate-expression (subst (definition-parameter P)
112                                                          (evaluate-expression an-exp)
113                                                          (definition-body P)))]
114     [else (error 'evaluate-with-one-def "unexpected error")]))
115 
116 ;evaluate-with-defs : SchemeData list-of-definitions -> list-of-numbers
117 ;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. 
118 (define (evaluate-with-defs an-exp defs)
119   (cond
120     [(empty? defs) empty]
121     [(cons? defs) (cons (evaluate-with-one-def an-exp (first defs))
122                         (evaluate-with-defs an-exp (rest defs)))]))
123 
124 
125 ;test-evaluate SchemeData list-of-definitions list-of-numbers -> boolean
126 ;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.
127 
128 (define (test-evaluate an-exp defs expected-result)
129   (equal? (evaluate-with-defs an-exp defs) expected-result))
130 
131 ;mydefine : number -> number
132 (define (mydefine x)
133   (* (* (+ 4 x)
134         (/ 3 x))
135      (- x 1)))
136 (define (myotherdefine x)
137   (/ (+ (* 5 x)
138         (* x 4))
139      (* (+ 4 x)
140         (+ 3 x))))
141 
142 (define mydefine! (make-definition 'mydefine
143                                    'x
144                                    (make-mul (make-mul (make-add 4 'x)
145                                                        (make-div 3 'x))
146                                              (make-sub 'x 1))))
147 (define myotherdefine!
148   (make-definition 'myotherdefine!
149                    'x
150                    (make-div (make-add (make-mul 5 'x)
151                                        (make-mul 'x 4))
152                              (make-mul (make-add 4 'x)
153                                        (make-add 3 'x)))))
154 (define myexp (+ (* 3 4)
155                  (/ 6 3)))
156 (define myexp! (make-add (make-mul 3 4)
157                          (make-div 6 3)))
158 
159 (test-evaluate myexp! (list mydefine! myotherdefine!) (list (mydefine myexp) (myotherdefine myexp)))
160