Sun Aug 23 19:52:08 EDT 2015
CPS Monad revisited
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.