Sat Aug 27 12:54:16 CEST 2011

Sharing monad

I keep making mistakes wrt. the sharing monad so the idea is to build
a DSL that is monadic from the start so we have a proper binding
mechanism that allows the implementation of sharing and maybe other
side effects.

  class Monad m => DSPM r m where
    add  :: r t -> r t -> m (r t) 
    mul  :: r t -> r t -> m (r t)
    lit  :: t -> r t

Here r is the representation type and m is an explicit monad wrapper
to allow expressions such as:

  f a b = do  
    c <- mul a a
    d <- mul b b
    add c d
Is the monad fixed?
Can it be part of r?

The first problem I run into is managing the types in a shared
context.  Maybe now's a good time to use a different approach to
storing collections of different types.

Step 1: got something working without sharing on top of the SC monad:

  data Asm t = Var String
             | Op  String [Asm t]

  instance Show t => Show (Asm t) where
    show (Var v) = v
    show (Op opc as) =  opc ++ (show as)

  op2 opc a b = return (Op opc [a,b])

  instance (DSPM Asm (SC r e)) where  
    add = op2 "add"
    mul = op2 "mul"
    ivar = return . Var

  f1 a b = do  
    c <- mul a a
    d <- mul b b
    add c d
  f2 = do  
    a <- ivar "a"
    b <- ivar "b"
    f1 a b

  asm (SC c) = putStrLn $ c () $ \e t -> "env: " ++ show e ++ ", term: " ++ show t
  type Rv = SC String () (Asm Tint)
  asm (f2 :: Rv)

  env: (), term: add[mul[a,a],mul[b,b]]

Let's fix that first so the type annotation is kept.  Hmm this is not
so simple.  Also running into another such problem after implementing

  returnN :: (Asm t) -> SC r Env (Asm t)
  returnN t = SC c where  
    c e k = k e' (Var v) where
      v = "R" ++ (show $ length e)
      e' = (v, "<dummy>") : e
Can't seem to propagate the show constraint into returnN.  Maybe best
to solve another problem first: the Env type needs to be heterogenous.
Existentials or dynamics?  Was quite straightforward

  data Bind = forall t. Show t => Bind String t
  instance (Show Bind) where
    show (Bind v t) = v ++ " <- " ++ (show t) ++ "\n"

  newtype Env = Env [Bind]
  instance (Show Env) where
    show (Env e) = concat $ map show (reverse e)

I was able to work around the typing issue by reducing generality:

  op2 opc a b = returnN (Op opc [a,b])
  type TypedOp2 r t = String -> (Term t) -> (Term t) -> SC r Env (Term t)

  op2i = op2 :: TypedOp2 r Tint
  op2f = op2 :: TypedOp2 r Tfloat

and making the DSPM methods more specific, like the Sym before:

  class Monad m => DSPM r m where
    iadd  :: r Tint -> r Tint -> m (r Tint) 

  instance DSPM Term (SC r Env) where  
    iadd = op2i "add"