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