Sat May 8 12:46:05 EDT 2010

Flattening Term graphs (SSA)

I'm having difficulty modularizing the compilation step.  The problem
is keeping track of inputs and outputs.

Maybe this should all be collapsed into one function that converts a
Term structure into a flat structure, introducing names.

Practically: separating sharing and naming might not be a good idea,
they are somewhat connected.  The main idea seems to be that the
flattening fold should know about variable names of the term


  * Through abstract interpretation, a Tree structure parameterized by
    input nodes (i.e. The Term Var constructor.) associated to output
  * an intermediate node allocation function (a lazy list)


  * flattened dictionary (SSA form)

  * List of intermediate nodes  (for allocating intermediate storage)

Let's make this abstraction functional, so we don't need to deal with
generating input/output names.

This gives a family of functions.  Let's take the 2->2 one, and
generalize later.

   f :: (a,a) -> (a,a)

   compile_2_2 :: ((a,a) -> (a,a)) -> (Var a, Var a) -> (Var a, Var a) -> Proc

So, what is the type of compilation?  Start with a function

  f :: a -> b

The compiler takes a function, two sets of variables, and produces a
code segment.

  compile :: (a->b) -> [Tmp] -> Out b -> In a -> Procedure

Important remarks: 

  `compile' doesn't know how many temporaries are generated, so tmp is
  a list tmp = [Node].

  The output and inputs are directly related to the base types:

    a               In a
    Float           Term Float
    (Float, Float   (Term Float, Term Float)

Starting from functions like (a->b), I'm constantly being pulled into
not naming outputs.  I.e. lifting to (Ins a -> Outs b).

There is something wrong with my intuition here.  (a->b) and Proc (Ins
a) (Ins b) are different beasts.

Another question.  Given an opaque function ([a] -> [a]), can we
convert it to the following?

           :: [Node] -> Outs -> Ins -> Procedure

Where the Procedure is filled in properly, I.e. it contains a finite
list of temp nodes, and finite lists of input/output variables.