Sat Jul 16 15:29:03 CEST 2011

CPS + memoization

What needs to happen is this:

  - intercept "return value" == value passed to continuation by
    modifying the bind method of the CPS monad.
  - create a new variable in the store and associate it to this binding.

  - pass the variable reference to the real continuation.

What does bind look like in that case?  The problem is types..  Time
for looking at the cheat sheet.

Lets first try to pass an opaque state object along with the CPS
control flow.  This requires a modification from the original pure

    bindSC (SC c) f = SC c' where
      c' k = c (\v -> cpsComp (f v) k)

which in non-tagged form looks like

    bindSC c f = c' where
      c' k = c (\v -> (f v) k)

What we need to do here is to allow a state s to travel along side the
value v.  I.e. to complete the following such that s is properly

(!) bindSC c f = c' where
      c' k = c (\v s -> (f v) k)

The only way to pass this correctly is to pass it to the computation,

    bindSC c f = c' where
      c' k s = c k' s where
        k' v s' = c'' k s' where
          c'' = f v
Which changes the type from (v -> r) -> r for the CPS monad to

      k -> s -> r
      k = (v -> s -> r)

for the SC monad.  The operation of bind is as follows: a composition
of two SC computations c and one generated by f is a computation c'
which takes two arguments: the overall return point and the input
state.  The composite computation c' first invokes the computation c,
passing it the input state s and a new contuation k' which determines
what happens after c is finished.  The continuation k' takes the value
produced by computation c and the updated state s'.  It uses the value
to construct a new computation c'' from f.  This computation c'' is
then passed the state as it was after c', and the overall continuation
= return point of the value and state produced by c''.

In lambda notation without intermediate names:

   bindSC c f = c' where
     c' k s = c (\v s' -> (f v) k s') s

It seems to be a bit more readable if the state is passed as the first
parameter for both the CPS computation c,c' as the continuation.

   bindSC c f = c' where
     c' s k = c s (\s' v -> (f v) s' k)