Fri Feb 5 07:55:22 CET 2010

Combining environments

When combining two expressions in a binary operation, the environments
need to be joined.  In order to make this operation simpler, it's
probably best to model the environments as sets and not allow shadowing.

I'm thinking about why this problem of joining environments didn't
happen in the Scheme version.  Probably because it was implemented
using context (Scheme parameters).

In the haskell approach I would like to represent context locally,
i.e. make each term self-contained (a closure).  It seems this would
make it easier to use type classes: to define algebraic operations as
pure functions instead of contextual functions.

So, let's stick to environments as finite functions, and the join
operation obtained by the relational union of both functions,
requiring that the result is again a function.

Conclusion: purity requires self-contained terms.

Something doesn't add up though

 S) One the one hand there is a sequential view (ANF or CPS).  Here the
    environemnt is incrementally built up moving from expression to
 L) On the other hand there is a local view where each term has an
    environment connected, and both environments are not necessarily
    the same.

How can both be connected?

Can we assume in first approximation that for L) both environments are
the same?

Suppose we want to evaluate (+ a b) in an initial environment that
contains {a, b}.  Writing both terms `a' and `b' as closed terms gives:

   (a, [(a, #arg), (b, #arg)])
   (b, [(a, #arg), (b, #arg)])

Where #arg means this variable is a C function argument and will be
initialized at run time when the function is called.

Adding both numbers gives:

   (r1, [(r1 (+ a b)), (a, #arg), (b, #arg)])

Now the trouble begins when we want to do something like:
    (* (+ a b) (- a b))

Both sides can be executed independently, giving:

    ((* r1 r2), [(r1 (+ a b)), 
                 (r2 (- a b)),
                 (a, #arg), 
                 (b, #arg)])

The trouble is that r1 and r2 need to be unique.  If this is the case,
joining the two environments isn't such a problem.