Sun Jul 24 11:10:36 CEST 2011

Merging HOAS & Sharing monad

Now for the real problem: how to merge the state-continuation monad
and the higher order syntax approach?  They seem to live in different

Probably writing the sharing code more abstractly as a class would
help a bit.

Looking at the type of returnN :: TExpr -> SC r Bindings TExpr it
seems that making TExpr generic here would work.  This would then
probably be (repr Tfloat) and (repr Tint).

Is this the trick? : Represent a generated variable as a "hole",
i.e. a function.

Anyways, this compiles:

data Bindings t = Bindings [(t,t)]
                  deriving (Show,Eq)
class SSA t where
  tmpvar :: Int -> t -> t

-- Note that returnN is not as generic as return.
returnN :: SSA t => t -> SC r (Bindings t) t
returnN val = SC c where  
  c (Bindings table) k = k (Bindings table') ref where 
    table' = (ref,val):table
    ref = tmpvar (length table) val

Then I tried to abstract this into a monad but ran into a problem.
Apparently that constraint on the type of returnN makes it impossible
to have generic monad behaviour.  

-- Abstract SSA as a monad
data SSA r t = SSA { unSSA :: SC r (Bindings t) t }

instance Monad (SSA r) where
  return = SSA . returnN
  (SSA sc) >>= f  = SSA (sc >>= (unSSA . f))

So this needs a different type class.  Maybe just add the sharing
return to the letN type class (renamed from SSA / tmpvar)

-- The Let class abstracts term naming.  Given a unique number and a
-- term, it returns a term unique to that number that can be used as a
-- name.
class LetN term where
  letN    :: Int -> term -> term
  returnN :: term -> SC r (Bindings term) term

  -- Default implementation inserts into the table.
  returnN val = SC c where  
    c (Bindings table) k = k (Bindings table') ref where 
      table' = (ref,val):table
      ref = letN (length table) val

The problem is now how to combine this with Symantics.  I don't feel
any understanding bubbling up here..

A problem I ran into before is the type of the bindings list that is
threaded through.  This type has to be constant if it's to serve as a
state parameter for the SC monad.

Is there really a problem?  Essentially there are only 2 types the
store needs to take.  This could go into two lists.

Maybe the store should also be a typeclass then?