Fri Feb 5 08:34:26 CET 2010

Haskell: generating unique tags

I.e. gensym for haskell.  Alternatively, we could just work with
object equality.  This would give common subexpression elimination for

So the real question: when are two terms equal?

The answer would be: when they expand to the same original expression
modulo some transformation rules like associativity or commutativity.

This probably gives quite a combinatorial explosion.

The next questions are then: 

    - Can equality tests be memoized?

    - For associative operators: can the association pattern be
      computed lazily?

For lazy association, the point being that intermediate results that
are not observed are not needed in the rest of the computation.

I.e. suppose we have (+ a b c) and factor this to (+ (+ a b) c).  If
(+ a b) is never observed, the decision to factor the original sum in
one of three ways can be postponed until another constraint pops up
that makes it obvious, i.e. the appearance of either (+ a b), (+ a c)
or (+ b c) or their commutations.

How do you express that?