Mon Aug 1 09:30:47 CEST 2011

Joining dictionaries

Is the following correct?  The `codeLet' operation is relatively
trivial: create binding and propagate binding and augmented
dictionary.  Since let_ is always strictly nested there is no
confusion about how to propagate the dictionary.

The confusion starts with multi-input operations.  Since the
dictionary travels with the variable instead of being stored in a
global state object, it is necessary to reconstruct that state object.
Because we know that dictionaries have to be nested, reconstruction
can be done by just inspecting dictionary size:

dictJoin d1 d2 =
  if (length d1) > (length d2) then d1 else d2

code' x = Code (show x) []

code1 op (Code x d)
  = Code (codeApp [op,x]) d

code2 op (Code x d) (Code y d')
  = Code (codeApp [op,x,y]) d'' where
  d'' = dictJoin d d'

code3 op (Code x d) (Code y d') (Code z d'')
  = Code (codeApp [op,x,y,z]) d''' where
  d''' = dictJoin (dictJoin d d') d''

codeLet (Code term dict) body = body (Code var dict') where
  var = "R" ++ (show $ length dict)
  dict' = (var,term):dict       

So what happens when dictionaries are not nested, i.e. when scopes fan
out?  I.e. is that assumption actually correct?  Nope, it's not.  In
the following, one of the dictionaries is lost,

expr9  = let_ (int 1) (\x -> (x * x))
expr10 = let_ (int 2) (\x -> (x * x))

*Final> expr9 :: Code Tint
Code {code = "(imul R0 R0)", dict = [("R0","1")]}
*Final> expr10 :: Code Tint
Code {code = "(imul R0 R0)", dict = [("R0","2")]}
*Final> (expr9 * expr10) :: Code Tint
Code {code = "(imul (imul R0 R0) (imul R0 R0))", dict = [("R0","2")]}

There is no way around threading a single state == CPS conversion.

No free lunch.

So it shouldn't be that hard, but the "data rep" should be a state
continuation monad.