Thu May 6 14:11:52 EDT 2010

Memoization of (==), the right way

What I should have done instead is to write the algorithms
without memoization based purely on (==), then define 

  (==) :: Memo a -> a -> a -> (Bool, Memo a)

and thread this through the computations.  This allows one to
keep the memo tables hidden, but keep them around as long as they
are needed.

The probem is that the (.==) used in nameShared does not use the
equvalence table used to build up the environment.  Maybe it should
just use extendShared followed by pointer equivalence?

The problem is currently that the tmpNames passed into nameShared
trigger recursive (==) to be invoked on misses, which is definitely
not what we want to accomplish.

It seems that the easiest way to do this is to wrap the whole
computation in an IO monad such that `makeStableName' can be used, and
then use `unsafePerformIO' to perform any kind of operation that might
use pointer equality to produce a datastructure that no longer relies
on sharing.

The real, deeper problem seems to be that I'm trying to separate tree
traversal and caching of (==), while what I really want to do is to
"compact" a tree according to the equivalence relation, and also
"decouple" it by creating _explicit_ indirections in the form of node
names, without resorting to impicit pointer equalities in further

Conclusion: find a way to abstract "tree unpack", where a recursive
structure is converted into a flat dictionary by adding node
references (i.e. natural numbers).

To implement this, the unique naming could be bootstrapped by using
makeStableName inside an unsafePerformIO.