Talk:Haskell/Continuation passing style

From Wikibooks, the open-content textbooks collection

Here's everything I've written for this module so far, before running out of stamina:

---

Continuation passing style (CPS) in Haskell is, like monads, rather difficult to understand.

What makes a CPS value a CPS value is the fact that it takes an extra parameter, called a continuation. The continuation represents the function being applied to the value: the CPS value simply has to apply the continuation to the value within it. A very simple example:

cps3 cont = cont 3

The consequence of this taking a continuation is a biggie: the CPS value has access to the function being applied to it. This allows values to do weird things: for example, it's easy to make a value that ignores the continuation and returns a different value instead. This is similar to the Maybe monad, where Nothing has the effect of ignoring whatever functions are applied to its "contained value".

The type of a CPS value is simple:

(a -> r) -> r

Here, a represents the CPS value's "inner type". (a -> r) is the function applied to the CPS value, and r is of course the return type of this function.

Note that there is nothing preventing the CPS value from imposing restrictions on r as well as a; a function like const 'a' can be used as a CPS value:

const 'a' :: (a -> Char) -> Char

Since const 'a' ignores any function passed to it, it doesn't matter what this function takes. However, const 'a' will always return a Char, so this must be the function's return type, to "disguise" the fact that the Char is not being pulled from the continuation. This restriction is imposed by the fact that a CPS value has to return the same type as its continuation--even if the continuation is not used.

CPS values aren't often used alone: continuation passing style programming often contains them in great quantities. To make things easier to understand, there's a type with a data constructor that works on CPS values:

newtype Cont r a = Cont { runCont :: ((a -> r) -> r) }

Here r represents the restrictions on return type imposed by the CPS value, and a represents the value contained within the CPS value. The data constructor Cont turns a CPS value into a Cont value, and runCont turns it back again.

Adding Cont to Monad allows us to stitch together continuations:

instance Monad (Cont r) where
    return a                 =  Cont $ \k -> k a
    (Cont c) >>= f           =  Cont $ \k -> c (\a -> runCont (f a) k)

First of all, notice that (Cont r), and not Cont, is being defined here as an instance of Monad. This is because it is what (Cont r) is "applied" to that defines what's "contained within" the CPS value.

Now, it's not necessary to understand just what >>= does and how it does it. It just feeds a CPS value into a CPS function and returns a CPS value.

In case you're getting into the "gimme some CODE": we're getting there.

Now, we can define an exit function. It is the same as the usage of const above, except making a Cont value rather than simply a CPS value.

exit x = Cont (const x)

Also, we'll make a finish function that takes the value "inside" a Cont value and returns it:

finish x = runCont x id

This turns its Cont argument into a normal continuation, then applies it to id, ending the computation.

Finally, we'll note that return () acts as a "nop" in any do-block. Here's a basic example of division:

divide x y = finish (do if y == 0
                          then exit (error "Division by zero")
                          else return ()
                        return (x / y))

This does seem very useless, but many imperative constructs can be simulated in the Cont monad.

This leaves the open question: how do I simulate the inarguably imperative monad that is IO? Well, Cont is, in fact, the most general of the monads, in that any monadic value can be turned into a Cont monadic value and back again.

Looking again at the type of >>=:

(>>=) :: m a -> (a -> m b) -> m b

Wait. Did I see a CPS value there? Yep: >>= can be thought of as taking a monadic value and making a CPS value out of it. Simply apply Cont to this value, and we have a fully functional value in the Cont monad!

monadToCPS :: m a -> Cont (m b) a
monadToCPS x = Cont (x >>=)

And the inverse:

cpsToMonad :: Cont (m a) a -> m a
cpsToMonad x = runCont x return

One nice thing about this is that it will work on any Cont value with the appropriate type: it doesn't have to be one generated by monadToCPS. This allows us to mix other monads with Cont quite easily, though it's against the rules to combine other monads with each other. (Note that cpsToMonad is also the intuitive definition of a finishMonad function, that returns a monadic value instead of "just any value".)

---

Much stuff. Go insane with it. --Ihope127 18:27, 29 January 2006 (UTC)

[edit] Haskell's self-defeating authors

Why the fixation amongst haskellers on mathematics? I mean, you all couldn't think of a better example for CPS than the quadratic formula? There's simply no need to be adding to the complexity of this, it only serves to steepen the learning curve for us non-math-gurus... seriously...

I can only encourage you to strengthen your math skills, the quadratic formula is like 9th grade... and a good example, mainly because the "classic" example of error continuations is uncommon in Haskell, since we have Maybe and Either.

-- apfeλmus 09:32, 17 May 2008 (UTC)

[edit] Error in "a note of typing"

As it appears to me, almost all explanation in this chapter is wrong.

Concerning type of k:

 k :: a -> Cont r b

The b type isn't arbitrary because of we don't do anything with result of k. It's arbitrary because we don't do anything with continuation supplied to Cont r b.

Explanation: The return type of k is a Cont Monad which has type signature ((a->r)->r).

As it stands in definition of callCC:

 class (Monad m) => MonadCont m where 
   callCC :: ((a -> m b) -> m a) -> m a 

 instance MonadCont (Cont r) where 
   callCC f = Cont $ \h -> runCont (f (\a -> Cont $ \_ -> h a)) h

As we can see, our k is

 (\a -> Cont $ \_ -> h a) 

It ignores it's parameter which is of type (a->r) where type of expression is Cont r a

As we can see, because input function is ignored, the "a" type is arbitrary, and thats the real reason for k signature.

Also, the reason we must use "return" at the end of callCC instead of k lies elsewhere.

As we know

 x<-m1
 m2

really means

 m1 >>= (\x->m2) and type of this is 
 m1 :: m a 
 (\x->m2) :: (a -> m b)

Substituting this for our example:

 x = Msg :: String
 m1 = callCC
 m2 = return (length Msg)

If we use return at the end of callCC, it returns Cont Monad of type Cont r String and it matches type of Msg. If we use k instead of return, type of k is already binded to () by use in "when" so it has type Cont r () and this is mismatch with String in definition of

 callCC >>= (Msg -> return (length Msg)).

I don't quite understand. Strictly speaking, the explanation in the article is correct, if very unclear. The problem is that while the b in k :: a -> Cont r b is indeed arbitrary, you cannot have both b=String and b=() as you point out as well.

The advice of always ending a do-block in callCC with return is wrong. The proper solution is to give callCC a rank-3 type:

callCC :: ((forall b. a -> Cont r b) -> Cont r a) -> Cont r a

-- apfeλmus 09:17, 11 September 2008 (UTC)

After reading explanation from article many more times and giving it Deep Thought, I must admit it is correct. Probably my tendency to be very precise and the fact that I was still learning all of that made me unable to understand the text appropriately.

However, I don't understand why advice about "return" is bad. The type You gave is the same as in actual definition, unless explicit "forall" changes something (what? :).

-- Spawarotti 13-IX-2008

Ah, after some Deep Thought on my part, there are actually two issues here and the advice about return is partly right and partly wrong.

To see why return is no panacea against type errors with k, consider the following

  foo :: Cont r Int
  foo = callCC $ \k -> do
     x <- k 41
     let z = (x + 2) :: Int
     when True $ k 42
     return 43

What type does k have? The first two lines in the do-block force it to be of type Int -> Cont r Int while the third line forces it to be of type Int -> Cont r (). In other words, the b from the type of callCC should be both Int and () which is clearly not possible. (Well, unless you use the type I gave with the explicit "forall". Look at its position, it's not just an explicit forall. The chapter Haskell/Polymorphism ought to explain this. Meanwhile, have a look at GHC's Users Guide, Arbitrary rank polymorphism and/or ask a haskell mailing list or #haskell. Basically, you can use several b now.) The return didn't help here.

On the other hand, I think the advice was meant to mean that you should not use k as the last statement, like in

 bar :: Cont r Int
 bar = callCC $ \k -> do
   let n = 5
   when True $ k n
   k 25

In this case, replacing the final k with return helps. But arguably, using the rank-3-type for callCC is the correct solution in this case as well.

-- apfeλmus 20:51, 16 September 2008 (UTC)

Many thanks for Your explanation. That makes everything clear for me :)

-- Spawarotti 19-IX-2008