Mon Feb 8 15:10:22 CET 2010
* Compile time reductions are of the type:
[Lit] -> Lit
[Prim,Lit,Var] -> Prim
How can computations on these expressions be lifted to
computations that have an associated environment (for memoization
* The resulting program is sequential. Can this be exploited?
I'm asking the wrong question. Why is it so straightforward in
Scheme? The order of evaluation was fixed by Scheme's: the
environment is a stack. Once an operation is added it won't be
removed. In the current implementation, expressions are independent
+ An environment is necessary to be able to not lose sharing that's
+ The current implementation implements this by implementing common
subexpression elimination wrt. term equivalence (i.e. taking into
- Complexity is too high: term equality is defined recursively, as
is subexpression elimination.
It might be best to simplify the environment model. But how to do
this without loosing the nice type class implementation
(i.e. no shared context).
Are there any hard constraints?
1. Code is self-contained (closed).
2. Complexity needs to be minimal (i.e. definitely not 2^N and
N^2 only if necessary.)
Conclusions for implementation:
1. A monadic approach might be useful for implementing the abstract
evaluation rules with an implicit environment join, but the end
user cannot be exposed to any form of shared context.
2. Currrent approach is OK but needs memoization of the term
equality function since it is recursive.