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.
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