Problem/Notes on Flattening Arithmetic Expressions
THIS IS NOT A PROBLEM SET. I'LL ACCEPT VOLUNTEERS (WHO ARE WELCOME TO
COLLABORATE) TO WRITE CAREFUL SOLUTIONS.
The procedure for reducing arithmetic expressions to a sum of
products can be described by rewrite rules, the main ones being
left and right distributivity
(e * (f + g)) = ((e * f) + (e * g)),
((f + g) * e) = ((f * e) + (g * e)),
which we intend to be applied as left-to-right rewrite rules.
We'll say an expression is ``flat'' when neither rule is applicable anywhere
in the expression.
PROBLEM 1: Assuming for the moment that the only operations in expressions
are + and *, give an illustrative example of the general form of a flat
expression.
PROBLEM 2: The distributivity rules are are "terminating": starting with
any expression, *no matter where the rules are successively applied*,
a flattened expression will be reached. This fact is not obvious because
if e is a ``large'' subexpression with many non-flat subexpressions, then
the righthand side of the rule with two occurrences of e may be larger,
have more redexes, etc., than the lefthand side with only one e.
There is an ingenious, simple way to verify this termination claim.
Define the measure, meas{h}, of an arithmetic expression, h, by induction
(again, for simplicity assume the only operations are + and *):
meas{n} = 2, for any number n,
meas{v} = 2, for any variable v,
meas{(e + f)} = meas{e} + meas{f} + 1,
meas{(e * f)} = meas{e} * \meas{f}.
Then termination follows from the observation that the measure of any
expression is always an integer > 1, and if h can be rewritten by one
application of a distributivity rule into an expression h', in symbols,
h ==> h'
then
meas{h} > meas{h'}.
Prove these facts.
Hint: It's easy verify that
meas{(e * (f + g))} > meas{((e * f) + (e * g))},
but termination does not follow solely from this fact, since the
subexpression (e * (f + g)) which gets rewritten may not the whole of h.
Think about a proof by induction on the size of an expression.
PROBLEM 3: Now we extend the directed distributivity rules to handle
arithmetic expressions with the UNARY minus operator, -, as
well as + and *:
-(-e) = e,
-(f + g) = ((-f) + (-g)),
-(f * g) = ((-f) * g).
Define meas{-h} so the previous argument extends to show that repeatedly
using any of the distributivity rules and the three rules above for minus
as left to right rewriting rules will eventually terminate on any
arithmetic expression.