« Controlling effects with flatMap/>>=
Pan-pan medico »

Continuation monad in Scala

Here is how a continuation data type might look in Scala:

sealed trait Continuation[R, +A] {
  def apply(f: A => R): R
 
  import Continuation.continuation
 
  def map[B](k: A => B) = 
    continuation[R, B](z => apply(z compose k))
 
  def flatMap[B](k: A => Continuation[R, B]) = 
    continuation[R, B](z => apply(k(_)(z)))
}

Note that there are map and flatMap functions that satisfy the functor and monad laws. Continuation[R, _] is a monad.

Now let’s add some construction functions:

 
object Continuation {
  def continuation[R, A](g: (A => R) => R) = new Continuation[R, A] {
    def apply(f: A => R) = g(f)
  }
 
  def unit[R] = new {
    def apply[A](a: A) = continuation[R, A](f => f(a))
  }
 
  def callcc[R, A, B](f: (A => Continuation[R, B]) => Continuation[R, A]) =
    continuation[R, A](k => f(a => continuation(x => k(a)))(k))
}

The continuation function is a straight-forward construction. The unit function constructs a continuation is such a way as to satisfy the monad laws against the flatMap method. The callcc function (call with current continuation) is to allow “escaping” from the current continuation.

Here is some example client code that squares a number using a continuation (see squarec):

object Square {
  import Continuation._
 
  def square(n: Int) = n * n
 
  // Continuation for square
  def squarec[R](n: Int) = unit[R](square(n))
 
  // Continuation for effect (Unit) on square.
  // This is simply to help the type inferencer by applying a type argument.
  def squareE(n: Int) = squarec[Unit](n)
 
  def main(args: Array[String]) {
    val k = squareE(args(0).toInt)
    k(println)
  }
}

A slightly more complicated example for modelling exceptions. Let’s divide where the denominator must be 0 or an “exception” is thrown:

object Divide {
  import Continuation._
 
  // Division
  def div[R](c: String => Continuation[R, Int])
            (n: Int, // numerator
             d: Int) // denominator
                    : Continuation[R, Int] =
    callcc[R, Int, String](ok => 
      callcc[R, String, String](err =>
        if(d == 0) err("Denominator 0")
        else ok(n / d)
      ) flatMap c)
 
  def main(args: Array[String]) {
    def divError[R] = div[R](error(_)) _
    println(divError(7, 3)(x => x))
    println(divError(7, 0)(x => x)) // throws error
  }
}

This entry was posted on Sunday, December 28th, 2008 at 1:25 pm and is filed under Programming. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

6 Responses to “Continuation monad in Scala”

  1. Vadim Says:
    December 29th, 2008 at 8:52 am

    Hey, great examples. If only I could understand them as easily as you seem to be writing. I’m fairly new to Scala (it’s been a week) and this example you provided (squares), which is supposed to be trivial by your measures, confuses me even after an hour of beating my head against the interpreter.

    Why doesn’t square(n) in def squarec[R](n: Int) = unit[R](square(n)) get evaluated immediately after squarec[Unit](n) is called? Instead, it gets evaluated 2 times upon the last call to the resulting Continuation .apply (k(println)), before executing the function supplied to the .apply (println).

    I’m sure it’s something very simple, but it’s driving me nuts.

  2. Tony Morris Says:
    December 29th, 2008 at 11:26 am

    Hi Vadim,
    It doesn’t get evaluated because the continuation acts as a function to the value. It is when that function’s arguments are applied that all the evaluation occurs.

    Consider this simple Java snippet:

    int method() {
  return a + b;
}

    This is slightly different to:

    int method = a + b;

    This is because of the evaluation semantics. The use of the def keyword in Scala effectively makes the code like the former (while val would make it like the latter).

    I hope this helps.

  3. Vadim Says:
    December 29th, 2008 at 8:46 pm

    Thanks, I finally got it )

  4. Martin Says:
    January 4th, 2009 at 2:18 am

    Hi Tony,

    Not sure whether this is known: There is something very similar to what you describe in Scala’s standard library: It’s called Responder, and it is in the scala package.

    Cheers

    — Martin

  5. Tony Morris Says:
    January 4th, 2009 at 7:34 am

    Thanks Martin, I wasn’t aware of Responder. It looks like Responder applies the first type parameter of my example as Unit. That is, Continuation[Unit, A] ~= Responder[A].

  6. Peter Says:
    January 27th, 2009 at 7:26 am

    Is it possible to express something like the following Scheme snippet with this continuation formulation?


    (+ 1 (call/cc
       (lambda (k)
       (+ 2 (k 4)))))

Leave a Reply