Wed Feb 10 11:34:58 CET 2010

One-pass generation

Maybe it's better to stay a bit closer to [1]:

  ``Can we generate optimal code in one pass, without further
  transformations such as common-subexpression-elimination, without
  looking into the code at all after it has been generated?''

Next to abstract evaluation, memoization is really an essential part
of the deal: generate code with let expressions, and don't try to fish
them out later.

So, can they be separated?  Can we have a language that can be
abstractly evaluated and memoized separately?

Wow.. This stirs up a lot.  For one: the rewrite rules for the
abstract evaluation seem ill factored:

asum (Lit l1) (Lit l2) = Lit (l1 + l2)
asum (Lit l1) (LitAdd l2 t) = LitAdd (l1 + l2) t
asum (LitAdd l1 t) (Lit l2) = LitAdd (l1 + l2) t
asum t Zero = t
asum Zero t = t
asum (LitAdd l t1) t2 = LitAdd l (t1 + t2)
asum t1 (LitAdd l t2) = LitAdd l (t1 + t2)

I don't see how to factor patterns in the pattern matching rules;
i.e. commutativity is duplicated in the rules above.

Syntactic abstraction is so easy in Scheme -- not having it and having
to express a problem differently is a challenge.

[1] http://okmij.org/ftp/Computation/Generative.html#framework