Massachusetts Institute of Technology | Handout 3 |

6.044J/18.423J: Computability Theory of and with Scheme | September 15, 1998 |

Professor Albert R. Meyer |

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

(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.e* (f+g)) = ((e*f) + (e*g)),

((f+g) *e) = ((f*e) + (g*e)),

**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, `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{Then termination follows from the observation that the measure of any expression is always an integer > 1, and ifn} = 2, for any numbern,

mu{v} = 2, for any variablev,

mu{(e+f)} = mu{e} + mu{f} + 1,

mu{(e*f)} = mu{e} * mu{f}.

thenh==>h'

mu{Prove these facts.h} > mu{h'}.

Hint: It's easy verify that

mu{(but termination does not follow solely from this fact, since the subexpression (e* (f+g))} > mu{((e*f) + (e*g))},

**Problem 3**: Now we extend the directed distributivity
rules to handle arithmetic expressions with the **unary**
minus operator, -, as well as + and *:

-(-Define mu{-e) =e,

-(f+g) = ((-f) + (-g)),

-(f*g) = ((-f) * g).

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