Page History

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 {{boolExp}}s.

The provided function {{parse: input -> boolExp}} takes a Scheme expression and returns the corresponding {{boolExp}}.

----+h1. 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=

is not a ={{norm-ifExp=}} because it has an ={{If=}} construction in test
 position.
  In contrast, the equivalent ={{ifExp=}}

is normalized and hence is an ={{norm-ifExp=}}.

The normalization process, implemented by the function
=normalize: ifExp -> norm-ifExp= eliminates all =if= constructions that
appear in the _test_ position of other =if= constructions.
We perform this transformation by
repeatedly applying the following rewrite rule
(to any portion of the expression) until it is inapplicable:

This transformation always terminates and yields a unique answer
independent of the order in which rewrites are performed.
The proof of this fact is left as an optional exercise.

In the ={{normalize=}} function, it is critically important not to duplicate any work, so
the order in which reductions are made really matters.  Do *NOT* apply
the normalization rule above unless ={{U=}} and ={{V=}} are already
normalized, because the rule duplicates both ={{U=}} and ={{V=}}.  If you
reduce the _consequent_ and the _alternative_ (=U= and =V= in the left
hand side of the rule above) before reducing the _test_, =normalize=
runs in linear time (in the number of nodes in the input); if done in
the wrong order it runs in exponential time in the worst case.  (And
some of our test cases will exhibit this worst case behavior.)

Hint: define a sub-function head-normalize that takes three =norm-ifExp=s =X=, =Y=, and =Z=
and constructs a =norm-ifExp= equivalent to =(makeIf X Y Z)=.  This help function processes
=X= because the =test= position must be a variable or a constant, yet =X= can be an
arbitrary =norm-ifExp=. In contrast, =(head-normalize X Y Z)= never even inspects =Y=
and =Z= because they are already normalized and the normalizing transformations performed
in =head-normalize= never place these expressions in =test= position.

The following examples illustrate how the =normalize= and =head-normalize= functions behave: