Sun Aug 23 19:52:08 EDT 2015

CPS Monad revisited

By construction:

A continuation resembles a function in that it takes an argument, but
does not return (e.g. it returns bottom).

   k = r -> b

   r: result type of function in CPS form. will be passed to the
   b: bottom (or for terminating embeddings, any other Haskell term)

A CPS computation is then a function that takes a continuation and
produces the embedding type of the computation.

   c = k -> b
     = (r -> b) -> b

c is Monadic in its r parameter, with

   return :: r -> ((r -> b) -> b)
   return r = \k -> k r

bind :: ((r -> b) -> b)
        -> (r -> ((r' -> b) -> b))
        -> ((r' -> b) -> b)
   bind c f = \k -> c (\r -> f r k)

With return trivially invoking k, bind means:
   - create a new CPS computation from c and k, by:
   - first running c with continuation k', which
   - takes the value computed by c and,
   - uses it to unlock a new CPS computation from f
   - which is then executed by passing it the final continuation k

Note that 'bind' and 'return' mimick variable binding and value return
in a functional language.

b is an effect of the embedding.  When running a CPS computation, a
value of type b will be produced.  b is irrelevant for the CPS Monad

However, in a CPS computation, b is likely constrained by other
operations that modify continuations directly.