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.7.1) (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 ;Examples:
42 ;
43 ;(f (+ 1 1))
44 ;(make-function 'f (make-add (1 1)))
45 ;
46 ;(* 3 (g 2))
47 ;(make-mul 3 (make-function 'g 2))
48 
49 (define-struct definition (function parameter body))
50 
51 ;A definition is a structure
52 ;(make-definition function parameter body)
53 ;where function and parameter are symbols and body is a SchemeData.
54 
55 ;Examples:
56 ;(define (f x) (+ 3 x))
57 ;(make-definition ('f 'x (make-add 3 'x)))
58 ;
59 ;(define (g x) (* 3 x))
60 ;(make-definition ('g 'x (make-mul 3 'x)))
61 ;
62 ;(define (h u) (f (* 2 u)))
63 ;(make-definition ('h 'u (make-function 'f (make-mul 2 u))))
64 ;
65 ;(define (i v) (+ (* v v) (* v v)))
66 ;(make-definition ('i 'v (make-add (make-mul v v)
67 ;                                  (make-mul v v))))
68 ;
69 ;(define (k w) (* (h w) (i w)))
70 ;(make-definition ('k 'w (make-mul (make-function 'h 'w)
71 ;                                  (make-function 'i 'w))))
72 
73 ;numeric? : SchemeData -> boolean
74 ;Given a-data, determine if the expression it
75 ;represents is numeric. That is,
76 ;numeric? evaluates true if the SchemeData lacks symbols,
77 ;which represents an expression which
78 ;lacks variables.
79 
80 (define (numeric? a-data)
81   (cond
82     [(number? a-data) true]
83     [(add? a-data) (and (numeric? (add-left a-data))
84                         (numeric?(add-right a-data)))]
85     [(sub? a-data) (and (numeric? (sub-left a-data)) 
86                         (numeric? (sub-right a-data)))]
87     [(mul? a-data) (and (numeric? (mul-left a-data)) 
88                         (numeric? (mul-right a-data)))]
89     [(div? a-data) (and (numeric? (div-left a-data)) 
90                         (numeric? (div-right a-data)))]
91     [else false]))
92 
93 ;evaluate-expression : SchemeData -> number
94 ;Given a-data, evaluates the numeric expression it represents
95 ;and returns the value.
96 
97 (define (evaluate-expression a-data)
98   (cond
99     [(number? a-data) a-data]
100     [(add? a-data) (+ (evaluate-expression (add-left a-data))
101                       (evaluate-expression (add-right a-data)))]
102     [(sub? a-data) (- (evaluate-expression (sub-left a-data))
103                       (evaluate-expression (sub-right a-data)))]
104     [(mul? a-data) (* (evaluate-expression (mul-left a-data))
105                       (evaluate-expression (mul-right a-data)))]
106     [(div? a-data) (/ (evaluate-expression (div-left a-data))
107                       (evaluate-expression (div-right a-data)))]))
108 
109 ;subst : symbol number SchemeData -> SchemeData
110 ;Given the representation of a variable V (symbol),
111 ;the number N, and a SchemeData which represents an expression,
112 ;produce a new SchemeData representing an expression
113 ;where all occurrences of the variable V (symbol)
114 ;have been replaced with the number N.
115 
116 (define (subst V N a-data)
117   (cond
118     [(number? a-data) a-data]
119     [(symbol? a-data) (cond
120                         [(symbol=? a-data V) N]
121                         [else a-data])]
122     [(add? a-data) (make-add (subst V N (add-left a-data)) 
123                              (subst V N (add-right a-data)))]
124     [(sub? a-data) (make-sub (subst V N (sub-left a-data)) 
125                              (subst V N (sub-right a-data)))]
126     [(mul? a-data) (make-mul (subst V N (mul-left a-data)) 
127                              (subst V N (mul-right a-data)))]
128     [(div? a-data) (make-div (subst V N (div-left a-data)) 
129                              (subst V N (div-right a-data)))]
130     [else a-data]))
131 
132 ;evaluate-with-one-def : SchemeData definition -> number
133 ;Given an-exp and P, evaluate the argument an-exp, substitute that for the parameter in P, and then evaluate the body of P.
134 
135 (define (evaluate-with-one-def an-exp P)
136   (cond
137     [(and (definition? P)
138           (numeric? an-exp)) (evaluate-expression (subst (definition-parameter P)
139                                                          (evaluate-expression an-exp)
140                                                          (definition-body P)))]
141     [else (error 'evaluate-with-one-def "unexpected error")]))
142 
143 ;evaluate-with-defs : SchemeData list-of-definitions -> list-of-numbers
144 ;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. 
145 (define (evaluate-with-defs an-exp defs)
146   (cond
147     [(empty? defs) empty]
148     [(cons? defs) (cons (evaluate-with-one-def an-exp (first defs))
149                         (evaluate-with-defs an-exp (rest defs)))]))
150 
151 ;mydefine : number -> number
152 ;(define (mydefine x)
153 ;  (* (* (+ 4 x)
154 ;        (/ 3 x))
155 ;     (- x 1)))
156 ;(define (myotherdefine x)
157 ;  (/ (+ (* 5 x)
158 ;        (* x 4))
159 ;     (* (+ 4 x)
160 ;        (+ 3 x))))
161 ;
162 ;(define mydefine! (make-definition 'mydefine
163 ;                                   'x
164 ;                                   (make-mul (make-mul (make-add 4 'x)
165 ;                                                       (make-div 3 'x))
166 ;                                             (make-sub 'x 1))))
167 ;(define myotherdefine!
168 ;  (make-definition 'myotherdefine!
169 ;                   'x
170 ;                   (make-div (make-add (make-mul 5 'x)
171 ;                                       (make-mul 'x 4))
172 ;                             (make-mul (make-add 4 'x)
173 ;                                       (make-add 3 'x)))))
174 ;(define myexp (+ (* 3 4)
175 ;                 (/ 6 3)))
176 ;(define myexp! (make-add (make-mul 3 4)
177 ;                         (make-div 6 3)))
178 ;
179 ;(evaluate-with-defs myexp! (list mydefine! myotherdefine!))
180 ;(list (mydefine myexp) (myotherdefine myexp))