Sun Feb 14 11:50:43 CET 2010

Merging environments

Let's extend the join-term-to-environment to the more interesting
operation of joinging environments.  This could also benefit from some
pointer-equality: merging two environments can be done up to the point
where the memotables are equal. i.e. finding the common list tails,
and concatenating the remainder.

( This has a lot in common with merging in source control! )

The incentive to accelerate join by finding common roots follows from
these assumptions:

   - big environments probably share data i.e. through explicit
     memoization in the code that produced the expression.

     => rebuilding the cache tables would be expensive

   - non-shared environments tend to be small (independent

     => finding a common root fails, but won't take much time.


  - 1st order: term equivalence (==) is cached using memotables
    embedded in an Env datastructure.

  - 2nd order: Env equivalence, or equivalence/sharing of the
    memotables themselves might also be accelerated.