Mon Feb 8 15:10:22 CET 2010

Threading environment

Some remarks:

   * 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
     modulo equivalence).

   * 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
(no context).

Current ideas:

  + An environment is necessary to be able to not lose sharing that's
    already present.

  + The current implementation implements this by implementing common
    subexpression elimination wrt. term equivalence (i.e. taking into
    account commutativity).

  - 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.