...
The course staff is providing function parse and unparse in the file parse.ss that convert boolean expressions in Scheme notation to a simple inductively defined type called boolExp and vice-versa. The coding of parse and unparse is not difficult, but it is tedious (like most parsing) so the course staff is providing this code rather than asking students to write it. The Scheme primitive read: -> SchemeExp is a procedure of no arguments that reads a Scheme expression from the console. DrScheme pops up an input box to serve as the console when (read) is executed.
These parsing functions rely on the following Scheme data definitions:
...
A boolean expression can be converted to if form by repeatedly
applying repeatedlyapplying the following
rewrite rules in any order until no rule is applicable.
...
| Code Block |
|---|
a {{boolExp}} is either:
* a boolean value {{true}} and {{false}};
* a symbol {{s}} representing a boolean variable;
* {{(make-Not M)}} where {{M}} is a {{boolExp}};
* {{(make-And M N)}} where {{M}} and {{N}} are {{boolExps}};
* {{(make-Or M N)}} where {{M}} and {{N}} are {{boolExps}};
* ={{(make-Implies M N)}} where ={{M=}} and ={{N=}} are ={{boolExps=; or
* ={{(make-If M N P)=}} where ={{M=}}, ={{N=}}, and ={{P=}} are =boolExps={{boolExp}}s.
The provided function {{parse: input -> boolExp}} takes a Scheme expression and returns the corresponding {{boolExp}}.
----+Normalization
An =ifExp= is _normalized_ iff every sub-expression in =test= position is either
a variable (symbol) or a constant (=true= or =false=). We call this type =norm-ifExp=.
For example, the =ifExp=
|
...