Wed Feb 10 18:33:52 CET 2010

Memoization and Control

So, with practical use of abstract interpretation +- understood, it's
time to work on the code graph problem.  Create a monad for sharing,
and try to express an algorithm in it, i.e. using the FFT described in

Monadic multistage programming[2].

The monad suggested is the state-continuation monad:

  'a monad     = state -> (state -> 'a -> answer) -> answer

  let ret a    = fun s k -> k s a
  let bind a f = fun s k -> a s (fun s' x -> f x s' k)

and a staged version:

  let retN a    = fun s k -> .<let z = .~a in .~(k s .<z>. )>.
  let bindN a f = bind a (fun x -> bind (retN x) f)

The state is used for threading the memo table through the code at
compile time.  This table contains variable names like .<z>. above
that represent cached function outputs, and is hashed by the input
arguments of functions.

In MetaOCaml the generated variable z in the code template will be
automatically renamed to make it unique.  If this renaming is desired
in Hasell code that uses direct syntax trees, uniqueness needs to be
guaranteed in a different way.

In a first attempt it might be interesting to forget about the
memo-Y-combinator, and use the state monad only for passing variable

[1] http://www.cs.rice.edu/~taha/publications/conference/emsoft04.pdf
[2] http://citeseerx.ist.psu.edu/viewdoc/download?doi=