Homework 6: Symbolic Evaluation of Boolean Expressions
Due: Monday Wednesday, Mar. 79, 2011
Extra Credit (100 pts.)
...
Code Block |
---|
(make-If true X Y) => X (make-If false X Y) => Y (make-If X true false) => X (make-If X Y Y) => Y (make-If X Y Z) => (make-If X Y\[X <\- true\] Z\[X <\- false\]) |
...
The notation {{M
\[X
<
\-
N
\]
}} means {{M
}} with all occurrences of the symbol {{X
}} replaced by the expression {{N
}}. It is very costly to actually perform these subtitutions on =norm-if-form= data. To avoid this computational expense, we simply maintain a list of bindings which are pairs consisting of symbols (variable names) and boolean values { {{true
}}, {{false
}}. The following data definition definition formally defines the {{binding
}} type.
A binding
is a pair (make-binding s v)
where s is a symbol (a variable) and v
is a boolean value (an element of { true
, false
}.
...
The final phase converts an expression in (not necessarily reduced or normalized) If
form to an equivalent expression constructed from variables and { true
, false
, And
, Or
, Not
, Implies
, If
. This process eliminates every expression of the form
...