Sun Feb 14 11:50:43 CET 2010
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
- 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.