This tutorial is a response to the following [http://stackoverflow.com/questions/3322540/tutorial-to-disassemble-the-haskell-cont-monad/3323283#3323283 Stack Overflow question]. There's a short but useful description of <tt>Cont</tt> and <tt>MonadCont</tt> in the [http://hackage.haskell.org/packages/archive/mtl/1.1.0.2/doc/html/Control-Monad-Cont.html 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 is a response to the following [http://stackoverflow.com/questions/3322540/tutorial-to-disassemble-the-haskell-cont-monad Stack Overflow question]. There's a short but useful description of <tt>Cont</tt> and <tt>MonadCont</tt> operations in the [http://hackage.haskell.org/packages/archive/mtl/1.1.0.2/doc/html/Control-Monad-Cont.html Control.Monad.Cont documentation], but it doesn't really describe how the continuation monad does its thing. This is an attempt at much more detailed explanation of what Cont and MonadCont are doing under the hood.

This tutorial assumes a working knowledge of Haskell, though of course it doesn't assume that you understood the implementation of <hask>Control.Monad.Cont</hask> the first time you read it!

This tutorial assumes a working knowledge of Haskell, though of course it doesn't assume that you understood the implementation of <hask>Control.Monad.Cont</hask> the first time you read it!

−

=Continuations and the Cont monad=

+

=Introducing Continuations and the Cont type=

Continuations are functions that represent "the remaining computation to do." Their representation here is <hask>a -> r</hask>, which is simply a function that takes some value produced by the current computation, of some type <hask>a</hask>, and returns the final result of type <hask>r</hask> from it.

Continuations are functions that represent "the remaining computation to do." Their representation here is <hask>a -> r</hask>, which is simply a function that takes some value produced by the current computation, of some type <hask>a</hask>, and returns the final result of type <hask>r</hask> from it.

Line 9:

Line 9:

The type <hask>Cont r a</hask> (instances of which I will, in this tutorial, refer to as <tt>Cont</tt>'' 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:

The type <hask>Cont r a</hask> (instances of which I will, in this tutorial, refer to as <tt>Cont</tt>'' 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

+

# takes a continuation as an argument

−

2. does whatever it needs to do

+

# does whatever it needs to do

−

3. produces a value of type <hask>r</hask> at the end, presumably by invoking the continuation.

+

# produces a value of type <hask>r</hask> 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 <hask>Cont</hask> object. So, generally, we won't be dealing with <hask>Cont</hask> objects directly, but with functions that can ultimately produce one.

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 <hask>Cont</hask> object. So, generally, we won't be dealing with <hask>Cont</hask> objects directly, but with functions that can ultimately produce one.

=Sequencing Continuation-Style Computations=

=Sequencing Continuation-Style Computations=

−

==Applicative Sequencing==

+

==Basic Sequencing==

−

<hask>Cont</hask> objects can be chained together, so that the continuation you pass in threads through the guts of all the <hask>Cont</hask> objects in the chain before it's finally invoked. The way they chain is the way <hask>Cont</hask> 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 <hask>Cont</hask> objects <hask>F1 -> F2 -> F3</hask>, and let's say you had a continuation <hask>C3</hask> that you want to pass to the chain. Then:

+

<hask>Cont</hask> objects can be chained together, so that the continuation you pass in threads through the guts of all the <hask>Cont</hask> objects in the chain before it's finally invoked. The way they chain is the way <hask>Cont</hask> 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 <hask>Cont</hask> objects <hask>f1 -> f2 -> f3</hask>, and let's say you had a continuation <hask>c3</hask> that you want to pass to the chain. Then:

−

* <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>, which will invoke <hask>C3</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> 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 ''applicative'' operation of continuations.

+

To chain the <hask>Cont</hask> objects together, then, we need to create the appropriate continuation functions <hask>c1</hask> and <hask>c2</hask> and make sure they get passed as the continuation argument to <hask>f1</hask> and <hask>f2</hask> respectively.

==Extending to Monad==

==Extending to Monad==

−

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

+

Extending this idea to the <hask>Monad</hask> class in general, there's an extra wrinkle: we allow for the value of one computation to affect ''which'' <hask>Cont</hask> object gets invoked next. In this world:

* <hask>return</hask> takes a value and produces a <hask>Cont</hask> object that just passes that value to its continuation.

* <hask>return</hask> takes a value and produces a <hask>Cont</hask> object that just passes that value to its continuation.

−

* <hask>bind</hask> takes a <hask>Cont</hask> object, and a ''function that produces another <hask>Cont</hask> object given a value from the first'', and chains them together into one <hask>Cont</hask> object. That object, when invoked, is going to:

+

* The bind operator <hask>(>>=)</hask> takes a <hask>Cont</hask> object, and a ''function that produces another <hask>Cont</hask> object given a value from the first'', and chains them together into one <hask>Cont</hask> object. That object, when invoked, is going to:

** take a single continuation object <hask>C</hask>,

** take a single continuation object <hask>C</hask>,

** produce an intermediate value,

** produce an intermediate value,

Line 50:

Line 50:

Why? The code <hask>($ a)</hask> is a ''slice'' of the operator <hask>$</hask>, which represents application. In other words, <hask>($ a)</hask> can be equivalently written <hask>\f -> f a</hask>, or "take a function as input and apply it to a."

Why? The code <hask>($ a)</hask> is a ''slice'' of the operator <hask>$</hask>, which represents application. In other words, <hask>($ a)</hask> can be equivalently written <hask>\f -> f a</hask>, or "take a function as input and apply it to a."

+

+

Thus, <hask>return</hask> in the <hask>Cont</hask> monad passes the result of its computation directly to the continuation it's given.

==Bind==

==Bind==

Line 66:

Line 68:

</haskell>

</haskell>

−

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 <hask>Cont</hask> objects are being created "just in time" to be used, based on the computation so far.

+

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

−

=Applying the Monad=

+

=Exploring the Monad=

−

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

+

Here's a simple example that should help illustrate the monad in action:

<haskell>

<haskell>

Line 121:

Line 123:

<hask>h</hask> is a function that takes a value and produces a <hask>Cont</hask> object depending on the value it's given.

<hask>h</hask> is a function that takes a value and produces a <hask>Cont</hask> object depending on the value it's given.

−

''Lemma:'' <hask>runCont Cont $</hask> effectively cancels out, i.e. <hask>runCont (Cont $ \c -> ...)</hask> is simply the function <hask>\c -> ...</hask>. This is because <hask>runCont</hask> is a field selector of <hask>Cont</hask> objects, and <hask>Cont</hask> objects only have that one field.

+

''Lemma:'' The sequence of terms <hask>runCont Cont $</hask> effectively cancel out, i.e. <hask>runCont (Cont $ \c -> ...)</hask> is simply the function <hask>\c -> ...</hask>. This is because <hask>runCont</hask> is a field selector of <hask>Cont</hask> objects, and <hask>Cont</hask> objects only have that one field.

Therefore, <hask>(return 5) >>= h</hask> expands and simplifies to:

Therefore, <hask>(return 5) >>= h</hask> expands and simplifies to:

<haskell>

<haskell>

−

let s c = c 5

+

doC = let s c = c 5

−

t c = \a -> runCont (h a) c

+

t c = \a -> runCont (h a) c

−

in Cont $ \c -> s (t c)

+

in Cont $ \c -> s (t c)

</haskell>

</haskell>

Line 135:

Line 137:

runCont doC finalC

runCont doC finalC

=> runCont (Cont $ \c -> s (t c)) finalC -- unfold doC

=> runCont (Cont $ \c -> s (t c)) finalC -- unfold doC

−

=> s (t finalC) -- simplify with lemma and apply to finalC

+

=> s (t finalC) -- simplify with lemma and apply to finalC

−

=> (t finalC) 5 -- unfold s

+

=> (t finalC) 5 -- unfold s

−

=> (\a -> runCont (h a) finalC) 5 -- unfold t

+

=> (\a -> runCont (h a) finalC) 5 -- unfold t

−

=> runCont (h 5) finalC -- apply \a... to 5

+

=> runCont (h 5) finalC -- apply \a... to 5

−

=> runCont (f 5) finalC -- unfold h

+

=> runCont (f 5) finalC -- unfold h

=> runCont (Cont $ \c -> c (5*3)) finalC -- unfold f

=> runCont (Cont $ \c -> c (5*3)) finalC -- unfold f

−

=> (\c -> c (5*3)) finalC -- simplify with lemma

+

=> (\c -> c (5*3)) finalC -- simplify with lemma

−

=> finalC (5*3) -- apply \c... to finalC

+

=> finalC (5*3) -- apply \c... to finalC

−

=> "Done: 15" -- apply *; apply finalC to final value!

+

=> "Done: 15" -- apply *; apply finalC to final value!

+

+

If you changed doC to <hask>return 4 >>= h</hask>, the derivation would be almost identical to the above, except that 4 would pass through to h, which would unfold to g instead. "Done: 2" should be the result.

−

=Understanding MonadCont and callCC=

+

=MonadCont and callCC=

−

One final extension to this which is frequently used is the <hask>MonadCont</hask> class, which provides a <hask>callCC</hask> operation. <hask>callCC</hask> creates a <hask>Cont</hask> 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 <hask>callCC</hask> 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:

+

One final extension to this monad, which can be extremely useful in practice, is the <hask>MonadCont</hask> class, which provides a <hask>callCC</hask> operation. <hask>callCC</hask> creates a <hask>Cont</hask> object that invokes a function to construct a <hask>Cont</hask> object, and then runs it with the continuation it's given. However, it provides that function an ''alternate'' continuation that can be invoked to "break out" of the computation and simply pass a value to the continuation that was active when <hask>callCC</hask> 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:

<haskell>

<haskell>

Line 185:

Line 189:

</haskell>

</haskell>

−

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

+

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

[[Category:Monad]]

[[Category:Monad]]

[[Category:Tutorials]]

[[Category:Tutorials]]

Revision as of 00:29, 26 July 2010

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

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

1 Introducing Continuations and the Cont type

Continuations are functions that represent "the remaining computation to do." Their representation here is

a -> r

, which is simply a function that takes some value produced by the current computation, of some type

a

, and returns the final result of type

r

from it.
The type

Cont r a

(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:

takes a continuation as an argument

does whatever it needs to do

produces a value of type

r

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

Cont

object. So, generally, we won't be dealing with

Cont

objects directly, but with functions that can ultimately produce one.

2 Sequencing Continuation-Style Computations

2.1 Basic Sequencing

Cont

objects can be chained together, so that the continuation you pass in threads through the guts of all the

Cont

objects in the chain before it's finally invoked. The way they chain is the way

Cont

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

, the derivation would be almost identical to the above, except that 4 would pass through to h, which would unfold to g instead. "Done: 2" should be the result.

5 MonadCont and callCC

One final extension to this monad, which can be extremely useful in practice, is the

MonadCont

class, which provides a

callCC

operation.

callCC

creates a

Cont

object that invokes a function to construct a

Cont

object, and then runs it with the continuation it's given. However, it provides that function an alternate continuation that can be invoked to "break out" of the computation and simply pass a value to the continuation that was active when

callCC

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: