Massachusetts Institute of Technology Handout 3
6.044J/18.423J: Computability Theory of and with Scheme September 15, 1998
Professor Albert R. Meyer

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 ``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, mu{h}, of an arithmetic expression, h, by induction (again, for simplicity assume the only operations are + and *):

mu{n} = 2, for any number n,
mu{v} = 2, for any variable v,
mu{(e + f)} = mu{e} + mu{f} + 1,
mu{(e * f)} = mu{e} * mu{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'
mu{h} > mu{h'}.
Prove these facts.

Hint: It's easy verify that

mu{(e * (f + g))} > mu{((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 mu{-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.

Copyright © 1998. All rights reserved. Last updated 10/18/98