An intuition for delimited continuations

Many times when trying to explain delimited continuations in Scala, a code example is shown and then explained. Usually this creates confusion since the client code feels unnatural but more importantly, doesn't give an intuition of when to decide to use delimited continuations in our own code.

 

The intuition I have is that when I have a function that accepts functions, and the resulting client code means several levels of nesting such functions, then DC can help.

 

Let's see a familiar example:

scala> List(1,2,3).flatMap{i =>
     |   List(10,20,30).flatMap{j =>
     |     List(100,200,300).map {k =>
     |       k + j + i
     |     }
     |   }
     | }
res0: List[Int] = List(111, 211, 311, 121, 221, 321, 131, 231, 331, 112, 212, 312, 122, 222, 322, 132, 232, 332, 113, 213, 313, 123, 223, 323, 133, 233, 333)

 

This code is hard to read, so Scala has a better construct:

scala> for (i <- List(1,2,3);
     |      j <- List(10,20,30);
     |      k <- List(100,200,300))
     |   yield k + j + i
res1: List[Int] = List(111, 211, 311, 121, 221, 321, 131, 231, 331, 112, 212, 312, 122, 222, 322, 132, 232, 332, 113, 213, 313, 123, 223, 323, 133, 233, 333)

 

Note that the nesting is gone.

 

But what if we didn't have the `for` construct?

 

`flatMap` and `map` are both methods that accepts functions, so they are candidates for DC.

 

The intuition is this: If you have a method of the form:

def something(f: A => B): C

 

Which is used like:

something {a => 
  expr1
  expr2
  ...
  exprn
}

 

Then you can create a DC function/method of the form:

def cpsSomething = shift {f: (A => B) => something(f)}

 

Which will be used like:
 

reset {
  val a = cpsSomething
  expr1
  expr2
  ...
  exprn
}

 

It looks like not much gain, but when several nestings are involved, then code like:

something {
  expr1
  something {
     expr2
     something {
       expr3
     }
  }
}

 

Becomes

reset {
  val a1 = cpsSomething
  expr1
  val a2 = cpsSomething
  expr2
  val a3 = cpsSomething
  expr3
}


Of course in both cases, the methods can accept other arguments except for the `f` function.

 

In our case, `flatMap` accepts a function from Int  to List[Int]. In DC, the `shift` function is also passed a function whose argument is a function. So the general rule is that the function our "normal" flatMap accepts is the argument of the shift function. This is a bit confusing, so lets see the code (for simplicity, I'm focusing on just the types for the example above, not going into generics or builders):

scala> def generator(lst: List[Int]) = shift {f: (Int => List[Int]) => lst.flatMap(f)}
generator: (lst: List[Int])Int @scala.util.continuations.cpsParam[List[Int],List[Int]]

 

So now our DC code will work in any code block that accepts an Int and results in List[Int]:

scala> reset {
     |   val i = generator(List(1,2,3))
     |   List(i * 2)
     | }
res2: List[Int] = List(2, 4, 6)

 

Which is just equivalent to:

scala> List(1,2,3).flatMap{i => List(i * 2)}
res3: List[Int] = List(2, 4, 6)

 

In order to sprinkle some syntax sugar, we'll replace the need to wrap the result with a List with a `yld` method:

scala> def yld(r: Int) = List(r)
yld: (r: Int)List[Int]

 

And now we have it all:

scala> reset {
     |   val i = generator(List(1,2,3))
     |   val j = generator(List(10,20,30))
     |   val k = generator(List(100,200,300))
     |   yld(k + j + i)
     | }
res4: List[Int] = List(111, 211, 311, 121, 221, 321, 131, 231, 331, 112, 212, 312, 122, 222, 322, 132, 232, 332, 113, 213, 313, 123, 223, 323, 133, 233, 333)

 

Or even shorter (and not possible in for comprehension)

scala> reset {
     |   yld(generator(List(100,200,300)) + generator(List(10,20,30)) + generator(List(1,2,3)))
     | }
res5: List[Int] = List(111, 112, 113, 121, 122, 123, 131, 132, 133, 211, 212, 213, 221, 222, 223, 231, 232, 233, 311, 312, 313, 321, 322, 323, 331, 332, 333)

 

And we can even further shorten it:

scala> def yld(body: => Int @cpsParam[List[Int], List[Int]]) = reset {List(body)}
yld: (body: => Int @scala.util.continuations.cpsParam[List[Int],List[Int]])List[Int]

scala>   yld(generator(List(100,200,300)) + generator(List(10,20,30)) + generator(List(1,2,3)))
res5: List[Int] = List(111, 112, 113, 121, 122, 123, 131, 132, 133, 211, 212, 213, 221, 222, 223, 231, 232, 233, 311, 312, 313, 321, 322, 323, 331, 332, 333)

 

(the annotation of cpsParam tells the compiler to treat the code passed to yild as a CPS construct when creating the body thunk)

Thank you for your interest!

We will contact you as soon as possible.

Send us a message

Oops, something went wrong
Please try again or contact us by email at info@tikalk.com