Thu May 6 10:20:41 EDT 2010

Living without intrinsic object identity : Shared.hs

How this should work: intermediate node allocation (naming) is an
integral part of Expression -> SSA conversion.  This is what Shared.hs
should do: construct a Term structure with intermediate _names_,
i.e. Var.

Currently in the code it is a bit unclear to me where exactly the
names get generated.  It is done in `nameNodes', separate from the
Shared.hs functionality.

Conclusion: constructing datastructures where object identity is a
property is not a good idea.  In Haskell, object identity _always_
needs to be made explicit.  This means that Shared.hs is better
rewritten as a simple SSA convertor directly, such that intrinisc
object identity (which _is_ used in the _implementation_) is not
observable outside the module.

Goal: given a list of (Sym, Term) pairs, construct a list of (Sym,
Term) pairs where each Term is simple, and additional variables are
introduced from a list of Sym temp nodes.

This would hide the Shared data structure from the outside world, and
only return Term -> Term maps.

It does look like the external behaviour of Shared.hs is based only on
(==), so there really shouldn't be a problem.

`nameShared' builds a dictionary of Terms to index types.  However,
what is needed is:

     - nestedTerm -> Shared

     - Shared -> uniqueTerms  (or abstractly as fold)

     - a memoized equality relation

Practically, this function can be reused: it just combines recursive
Term structure with memoized (==) to build a list of representative
terms and a dictionary of unique nodes.

type Env a = Shared (Term a)
envFold :: (Eq a) => [Term a] -> Env a -> ([Term a], Env a)

That structure then needs to be operated on, by mapping the [Term a]
list to provided output names, and the remaining nodes in Env a to
intermediate nodes.

OK.  Difficult part is done: output names get properly woven into the
register naming code.  It was straightforward in hindsight ; haskell
code does tend to become quite dense.

Next: get rid of Function.hs by porting all C gen code to Procedure.hs