From HaskellWiki

Revision as of 02:41, 24 July 2010 (edit) Ods94043 (Talk | contribs) m ← Previous diff		Revision as of 02:43, 24 July 2010 (edit) (undo) Ods94043 (Talk | contribs) m Next diff →
Line 20:		Line 20:
	* <hask>F3</hask> needs to invoke <hask>C3</hask>when it's done		* <hask>F3</hask> needs to invoke <hask>C3</hask>when it's done
-	* <hask>F2</hask> needs to invoke a continuation <hask>C2</hask>that will invoke <hask>F3</hask>	+	* <hask>F2</hask> needs to invoke a continuation <hask>C2</hask> that will invoke <hask>F3</hask>, which will invoke <hask>C3</hask>.
-	* <hask>F1</hask> needs to invoke a continuation <hask>C1</hask> that will invoke <hask>F2</hask>, then <hask>F3</hask>, then <hask>C3</hask>.	+	* <hask>F1</hask> needs to invoke a continuation <hask>C1</hask> which will invoke <hask>F2</hask>, which will invoke <hask>F3</hask>, which will invoke <hask>C3</hask>.
-	What I've described so far is the <hask>Applicative</hask> operation of continuations.	+	What I've described so far is the ''applicative'' operation of continuations.
	==Extending to Monad==		==Extending to Monad==

---

Revision as of 02:43, 24 July 2010

This tutorial is a response to the following Stack Overflow question. There's a short but useful description of Cont and MonadCont in the Control.Monad.Cont documentation, but it doesn't really describe how the continuation monad works. This is an attempt at much more detailed explanation of what Cont and MonadCont are doing, particularly below the hood.

This tutorial assumes a working knowledge of Haskell, though of course it doesn't assume that you understood the implementation of the first time you read it!

Contents 1 Continuations and the Cont monad 2 Sequencing Continuation-Style Computations 2.1 Applicative Sequencing 2.2 Extending to Monad 3 Understanding the Monad 3.1 Return 3.2 Bind 4 Applying the Monad 5 Understanding MonadCont and callCC

1 Continuations and the Cont monad

Continuations are functions that represent "the remaining computation to do." Their representation here is , which is simply a function that takes some value produced by the current computation, of some type , and returns the final result of type from it. The type (instances of which I will, in this tutorial, refer to as Cont objects) represents a continuation-passing-style function that takes a single continuation as its only input. In other words, its guts are a function that:

1. takes a continuation as an argument 2. does whatever it needs to do

3. produces a value of type at the end, presumably by invoking the continuation. Note that whatever it needs to do, i.e. whatever values it needs to be able to use to do its thing, must already be bound up into the object. So, generally, we won't be dealing with objects directly, but with functions that can ultimately produce one.

2 Sequencing Continuation-Style Computations

2.1 Applicative Sequencing

objects can be chained together, so that the continuation you pass in threads through the guts of all the objects in the chain before it's finally invoked. The way they chain is the way works: each object in the chain invokes a continuation that has the next object's computation prepended to the final continuation. Let's say we have a chain of objects , and let's say you had a continuation that you want to pass to the chain. Then:

• F3
  needs to invoke
  C3
  when it's done
• F2
  needs to invoke a continuation
  C2
  that will invoke
  F3
  , which will invoke
  C3
  .
• F1
  needs to invoke a continuation
  C1
  which will invoke
  F2
  , which will invoke
  F3
  , which will invoke
  C3
  .

What I've described so far is the applicative operation of continuations.

2.2 Extending to Monad

With the operation there's an extra wrinkle: we allow for the value of one computation to affect which object gets invoked next. In this world:

• return
  takes a value and produces a
  Cont
  object that just passes that value to its continuation.
• bind
  takes a
  Cont
  object, and a function that produces another
  Cont
  object given a value from the first, and chains them together into one
  Cont
  object. That object, when invoked, is going to:
  • take a single continuation object
    C
    ,
  • produce an intermediate value,
  • use that intermediate value to select/create the next
    Cont
    object to invoke,
  • invoke that
    Cont
    object with
    C

3 Understanding the Monad

3.1 Return

The code:

is equivalent to the following code:

Why? The code is a slice of the operator , which represents application. In other words, can be equivalently written , or "take a function as input and apply it to a."

3.2 Bind

The code:

is a terse way of saying the following:

Do you see what's happening? (k a) has become part of the continuation that m is given, and m passes its value to k simply by passing its value to its continuation. The objects are being created "just in time" to be used, based on the computation so far.

4 Applying the Monad

Here's a simple example I've cooked up that should help illustrate the monad in action:

These are simple functions that produce objects, given an intermediate value . You can see that the value being passed to the continuation is an Int, though we don't put any restrictions on what that continuation can ultimately produce.

BTW, they can be equivalently written as:

where they look very similar to normal functions. I'm writing them longhand to show you explicitly what the functions are doing.

This is a more complicated function that chooses between two other objects, based on the input it's given. Now let's create a top-level object that does some chaining:

And we'll invoke it like this:

Note that produces a function of type , which is invoked on a continuation of type , which reduces in this context to . The final value produced will be a . Can you guess what it will say? What if you changed to ?

Let's see if you're right:

produces a object that basically looks like this: . So that part is easy. is a function that takes a value and produces a object depending on the value it's given. Lemma: effectively cancels out, i.e. is simply the function . This is because is a field selector of objects, and objects only have that one field. Therefore, expands and simplifies to: And finally, evaluates to:

   runCont doC finalC
   => runCont (Cont $ \c -> s (t c)) finalC  -- unfold doC
   => s (t finalC)                        -- simplify with lemma and apply to finalC
   => (t finalC) 5                        -- unfold s
   => (\a -> runCont (h a) finalC) 5      -- unfold t
   => runCont (h 5) finalC                -- apply \a... to 5
   => runCont (f 5) finalC                -- unfold h
   => runCont (Cont $ \c -> c (5*3)) finalC  -- unfold f
   => (\c -> c (5*3)) finalC              -- simplify with lemma
   => finalC (5*3)                        -- apply \c... to finalC
   => "Done: 15"                          -- apply *; apply finalC to final value!

5 Understanding MonadCont and callCC

One final extension to this which is frequently used is the class, which provides a operation. creates a object that invokes the function it's given, but provides a second continuation to that function that can be invoked to "break out" of the computation and simply pass a value to the continuation that was active when was invoked. This function's operation is definitely easier to understand by seeing it in action. Evaluate the following code, replacing the corresponding functions above: Run . h should invoke f, and g will be invoked afterward, so you should get 13 as the final answer. Now change to . In this case, h will call abort, which passes -1 to g. -3 should be the final answer. Now change to move g inside the callCC abort context: and run with . In this case, h invokes abort and g is never invoked! -1 is the final answer. Once you've converted all your operations to continuation-passing style by putting them in the monad, and have a handle on how works in that monad, understanding how works is surprisingly simple:

can be written as

The key is , which takes whatever "inner" continuation is active when backtrack is invoked, completely ignores it, and simply passes its value to the "outer" continuation . (Compare this to the definition of , which always uses the continuation it's given.) is the function passed to , whose extent provides the context under which can be used.

Categories: Monad | Tutorials