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 ;5. a Lam structure.
10 
11 (define-struct add (left right))
12 (define-struct sub (left right))
13 (define-struct mul (left right))
14 (define-struct div (left right))
15 (define-struct function (name arg))
16 (define-struct definition (function parameter body))
17 (define-struct Lam (parameter body))
18 
19 ;An operator is a structure
20 ;(make-operator left right)
21 ;where operator is replaced by one of the four operators:
22 ;1. add (addition)
23 ;2. sub (subtraction)
24 ;3. mul (multiplication)
25 ;4. div (division)
26 ;and left and right are SchemeData. It represents the expression
27 ;(operator left right)
28 ;in Scheme.
29 
30 ;A function is a structure
31 ;(make-function name arg)
32 ;where name is a symbol and arg is a SchemeData.  It represents the expression
33 ;(name arg)
34 
35 ;A definition is a structure
36 ;(make-definition function parameter body)
37 ;where function and parameter are symbols and body is a SchemeData.
38 
39 ;A Lam is a structure
40 ;(make-Lam p b)
41 ;where p is a symbol (representing a variable) and b is a SchemeData (representing an expression).
42 
43 ;numeric? : SchemeData -> boolean
44 ;Given a-data, determine if the expression it represents is numeric. That is, numeric? evaluates true if the SchemeData lacks symbols, which corresponds to an expression which lacks variables.
45 
46 (define (numeric? a-data)
47   (cond
48     [(number? a-data) true]
49     [(add? a-data) (and (numeric? (add-left a-data))
50                         (numeric? (add-right a-data)))]
51     [(sub? a-data) (and (numeric? (sub-left a-data)) 
52                         (numeric? (sub-right a-data)))]
53     [(mul? a-data) (and (numeric? (mul-left a-data)) 
54                         (numeric? (mul-right a-data)))]
55     [(div? a-data) (and (numeric? (div-left a-data)) 
56                         (numeric? (div-right a-data)))]
57     [else false]))
58 
59 ;evaluate-expression : SchemeData -> number
60 ;Given a-data, evaluates the numeric expression it represents and returns the value.
61 
62 (define (evaluate-expression a-data)
63   (cond
64     [(number? a-data) a-data]
65     [(add? a-data) (+ (evaluate-expression (add-left a-data))
66                       (evaluate-expression (add-right a-data)))]
67     [(sub? a-data) (- (evaluate-expression (sub-left a-data))
68                       (evaluate-expression (sub-right a-data)))]
69     [(mul? a-data) (* (evaluate-expression (mul-left a-data))
70                       (evaluate-expression (mul-right a-data)))]
71     [(div? a-data) (/ (evaluate-expression (div-left a-data))
72                       (evaluate-expression (div-right a-data)))]))
73 
74 ;subst : symbol SchemeData SchemeData -> SchemeData
75 ;Given the representation of a variable V (symbol), the expression E, and a SchemeData which represents an expression, produce a new SchemeData representing an expression where all occurrences of the variable V (symbol) have been replaced with the expression E.
76 
77 (define (subst V E a-data)
78   (cond
79     [(number? a-data) a-data]
80     [(symbol? a-data) (cond
81                         [(symbol=? a-data V) E]
82                         [else 'free])]
83     [(add? a-data) (make-add (subst V E (add-left a-data)) 
84                              (subst V E (add-right a-data)))]
85     [(sub? a-data) (make-sub (subst V E (sub-left a-data)) 
86                              (subst V E (sub-right a-data)))]
87     [(mul? a-data) (make-mul (subst V E (mul-left a-data)) 
88                              (subst V E (mul-right a-data)))]
89     [(div? a-data) (make-div (subst V E (div-left a-data)) 
90                              (subst V E (div-right a-data)))]
91     [(Lam? a-data) (make-Lam (Lam-parameter a-data)
92                              (subst V E (Lam-body a-data)))]
93     [else a-data]))
94 
95 ;evaluate-with-one-def : SchemeData definition -> number
96 ;Given an-exp and P, evaluate the argument an-exp, substitute that for the parameter in P, and then evaluate the body of P.
97 
98 (define (evaluate-with-one-def an-exp P)
99   (cond
100     [(and (definition? P)
101           (numeric? an-exp)) (evaluate-expression (subst (definition-parameter P)
102                                                          (evaluate-expression an-exp)
103                                                          (definition-body P)))]
104     [else (error 'evaluate-with-one-def "unexpected error")]))
105 
106 ;evaluate-with-defs : SchemeData list-of-definitions -> list-of-numbers
107 ;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. 
108 
109 (define (evaluate-with-defs an-exp defs)
110   (cond
111     [(empty? defs) empty]  
112     [(cons? defs) (cons (evaluate-with-one-def an-exp (first defs))                        
113                         (evaluate-with-defs an-exp (rest defs)))]))
114 
115 ;test-evaluate SchemeData list-of-definitions list-of-numbers -> boolean
116 
117 ;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.
118 
119 (define (test-evaluate an-exp defs expected-result)
120   (equal? (evaluate-with-defs an-exp defs) expected-result))
121 
122 ;Exercise 32.1.1
123 
124 ;(make-Lam 'y 'x)
125 ;(make-Lam 'x 'x)
126 ;
127 ;(lambda (y) ((lambda (x) x) x))
128 ;
129 ;((lambda (y) x)
130 ; (lambda (x) x))
131 
132 ;Exercise 32.1.2.   Develop the function
133 
134 ;; free-or-bound : Lam  ->  Lam 
135 ;; to replace each non-binding occurrence of a variable in a-lam 
136 ;; with 'free or 'bound, depending on whether the 
137 ;; occurrence is bound or not.
138 (define (free-or-bound a-lam)
139   (subst (Lam-parameter a-lam) 'bound a-lam))
140 
141 ;Tests
142 ;(equal? (free-or-bound (make-Lam 'x 'x)) (make-Lam 'x 'bound))
143 ;(equal? (free-or-bound (make-Lam 'x 'y)) (make-Lam 'x 'free))
144 
145 ;;Exercise 32.1.3.   Develop the function
146 
147 ;; unique-binding : Lam  ->  Lam 
148 ;; to replace variables names of binding occurrences and their bound
149 ;; counterparts so that no name is used twice in a binding occurrence
150 (define (unique-binding a-lam)
151   (local ;; the accumulator contains the name of the parameter whose scope is the current expression
152     ((define (unique-binding-accu a-lam accu)
153        (cond
154          [(not (Lam? a-lam)) ...]
155          [else
156           (local ((define new-sym (gensym (Lam-parameter a-lam))))
157             (make-Lam new-sym
158                       (unique-binding (Lam-body a-lam))))])))
159     (unique-binding-accu a-lam ...)))
160 
161 gensym