Wed Feb 10 11:34:58 CET 2010
Maybe it's better to stay a bit closer to :
``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.