Scala – Delimited Continuations

(The examples can be found on my GitHub)

Like many others out there, the first time I saw a continuation it threw me for a loop. So, I took to Google to find an explanation of what the code was doing. This led me in circles. Hopelessly hopping from message board to message board trying to find an explanation that made sense to me. I could not find one. This is an abbreviation of my attempt at learning continuations by “hacking away” along with my contrived examples along the way. I take the form of a scientist running experiments for this exercise.

Here are the resources I found most useful in my journey:

0. Setup

Scala does not by default support continuations. You will need to enable the continuations compiler plugin by passing -P:continuations:enable.

Once the plugin is ready to go each of your scala source files which wants to utilize continuations should import the scala.util.continuations._ elements.

1. Example 1: Control Flow Basics

Let’s compose an application that performs a few println calls:

1.1 The skeleton

object Test extends App{
  def doContinuation{
    reset{
      shift{continuation: (Unit => Unit) =>
      }
    }
  }
  doContinuation
}

Here we have an application which calls reset with a shift that takes as an argument a function with no arguments and no output. The shift is empty. Running this will produce no result. 

1.2 Say Hello

Let’s add the seminal hello world print call.

  def doContinuation{
    reset{
      shift{continuation: (Unit => Unit) =>
      }
      println("Hello World!")
    }
  }

Here our reset prints hello world after it performs the shift. Well… not exactly. This function also produces no result. Let’s add another print.

  def doContinuation{
    reset{
      println("Before shift")
      shift{continuation: (Unit => Unit) =>
      }
      println("Hello World!")
    }
  }

Now we have prints before and after the shift. We would expect to see before shift then hello world printed. Running this gives us before shift but still no hello world. Let’s add a third print.

  def doContinuation{
    reset{
      println("Before shift")
      shift{continuation: (Unit => Unit) =>
        println("shift")
      }
      println("Hello World!")
    }
  }

Adding a print within the shift prints before shift, followed by shift then program termination. So far we have three pieces of information:

  1. Tasks given before the shift are always performed
  2. Tasks given within the shift are always performed
  3. Tasks given after the shift may not be performed

Point 3 says “may not” rather than “won’t” because we have yet to have done enough testing to make such a strong claim.

Taking a look at the application, we see we have one object sitting around that we have yet to play with: the argument into shift. Let’s use this function.

  def doContinuation{
    reset{
      println("Before shift")
      shift{continuation: (Unit => Unit) =>
        println("start shift")
        continuation()
        println("end shift")
      }
      println("Hello World!")
    }
  }

Running this we finally get out hello world to print! But, it prints where the function continuation is placed in the control flow not where someone who comes from Java (such as myself) would expect it to be called.

1.3 Trying to understand what just happened.

Let’s change the hello world print to something more appropriate and examine the output:

  def doContinuation{
    reset{
      println("Before shift")
      shift{continuation: (Unit => Unit) =>
        println("start shift")
        continuation()
        println("end shift")
      }
      println("after shift")
    }
  }

Which produces:

Before shift
start shift
after shift
end shift

So, it seems the code after the shift is performed within the shift by the call to the argument of shift. In other words: the function that is argument to shift captures the code within the reset block after the shift. To test this let’s get a bit fancier within our shift.

  def doContinuation{
    reset{
      println("Before shift")
      shift{continuation: (Unit => Unit) =>
        println("start shift")
        continuation()
        println("between1")
        continuation()
        println("between2")
        continuation()
        println("end shift")
      }
      println("after shift")
    }
  }

Which produces:

Before shift
start shift
after shift
between1
after shift
between2
after shift
end shift

Here in each case where continuation is called, the code after shift is called. This implies the code after shift is used as the argument into shift which shift uses to determine the control flow of the reset operation.

2. Example 2: Argument and Return Value Basics

Let’s compose an application which counts natural numbers.

2.1 The skeleton

object Test extends App{
  def doContinuation{
    println("entering reset")
    reset{
      println("before shift")
      shift{cont: (Unit => Unit) =>
        println("start shift")
        cont()
        println("end shift")
      }
      println("after shift")
    }
    println("exited reset")
  }
  doContinuation
}

2.2 The Argument

Say we want our continuation to perform actions on Int objects.Then our continuation would need to take an Int as an argument.

  def doContinuation{
    println("entering reset")
    reset{
      println("before shift")
      shift{cont: (Int => Unit) =>
        println("start shift")
        cont(0)
        println("end shift")
      }
      println("after shift")
    }
    println("exited reset")
  }

We’ve changed shift’s input function to take an Int and produce a Unit but, what does this mean in our reset context? What represents the input? The shift itself represents the input. Let’s add more to our application.

  def doContinuation{
    println("entering reset")
    reset{
      println("before shift")
      val argument =
        shift{cont: (Int => Unit) =>
          println("start shift")
          cont(0)
          println("end shift")
        }
      println("after shift " + argument)
    }
    println("exited reset")
  }

This produces:

entering reset
before shift
start shift
after shift 0
end shift
exited reset

Within the shift, the value passed into the continuation(Int) function is delivered to the reset as the shift itself. This allows us to set a value to shift then use that value in our continuation.

2.3 The Return Value

Say we want our continuation to increment Int objects. Then we would need to take an Int as argument and return one as a result.

  def doContinuation{
    println("entering reset")
    reset{
      println("before shift")
      val argument =
        shift{cont: (Int => Int) =>
          println("start shift")
          cont(0)
          println("end shift")
        }
      println("after shift " + argument)
      argument + 1
    }
    println("exited reset")
  }

This produces the same result as the last code snippet but it opens up a few possibilities. Now, we can call the continuation inside our shift and transform our single input even further.

  def doContinuation{
    println("entering reset")
    reset{
      println("before shift")
      val argument =
        shift{cont: (Int => Int) =>
          println("start shift")
          cont(cont(cont(0)))
          println("end shift")
        }
      println("after shift " + argument)
      argument + 1
    }
    println("exited reset")
  }

This produces:

entering reset
before shift
start shift
after shift 0
after shift 1
after shift 2
end shift
exited reset

To count from an Int until any other you compose the continuation their difference, then start with the original figure. This will of course be incredibly annoying and eventually result in a stack overflow. The following procudes 10 to 12 without the fluff:

object Test extends App{
  def doContinuation(start: Int, end: Int){
    val count = end - start
    println("entering reset")
    reset{
      println("before shift")
      val argument =
        shift{cont: (Int => Int) =>
          println("start shift")
          var current = cont(start)
          1 to count foreach{num=>
            current = cont(current)
          }
          println("end shift")
        }
      println("after shift " + argument)
      argument + 1
    }
    println("exited reset")
  }
  
  doContinuation(10, 12)
}

3. Example 3: Increasing Complexity

3.1 The skeleton

Lets say we wanted a List[Int] from 1 to some Int.

object Test extends App{
  def doContinuation(count: Int): List[Int]={
    val buffer: Buffer[Int] = Buffer()
    reset{
      val curr =
        shift{cont: (Int => Any) =>
          1 to count foreach{num =>
            cont(num)
          }
        }
      buffer += curr
    }
    buffer toList
  }
  
  println(doContinuation(10))
}

This results in:

List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10)

Not surprising given what we’ve learned from the above.

3.2 Continuation Composition

Let’s take this one step further and make a list of lists of this kind using continuations.

  def doContinuation(count: Int): List[List[Int]]={
    val buffer: Buffer[List[Int]] = Buffer()
    reset{
      val curr =
        shift{cont: (Int => Any) =>
          1 to count foreach{num =>
            cont(num)
          }
        }
      buffer += List(curr)
    }
    buffer toList
  }

This gives us:

List(List(1), List(2), List(3), List(4), List(5), List(6), List(7), List(8), List(9), List(10))

Not too exciting yet but we’ll get there. Recall when I said the function that is argument to shift captures the code within the reset block after the shift. This statement is all inclusive. Let’s take a look.

  def doContinuation(count: Int): List[List[Int]]={
    val buffer: Buffer[Buffer[Int]] = Buffer()
    reset{
      val first =
        shift{cont: (Int => Any) =>
          0 to count foreach{num =>
            cont(num)
          }
        }
      val innerBuffer: Buffer[Int] = Buffer()
      buffer += innerBuffer
      val second=
        shift{cont: (Int => Any) =>
          1 to count foreach{num =>
            cont(first + num)
          }
        }
      innerBuffer += second
    }
    buffer.
      toList.
      map{element => element toList}
  }

This results in (formatted for readability):

List(
  List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10),
  List(2, 3, 4, 5, 6, 7, 8, 9, 10, 11),
  List(3, 4, 5, 6, 7, 8, 9, 10, 11, 12),
  List(4, 5, 6, 7, 8, 9, 10, 11, 12, 13),
  List(5, 6, 7, 8, 9, 10, 11, 12, 13, 14),
  List(6, 7, 8, 9, 10, 11, 12, 13, 14, 15),
  List(7, 8, 9, 10, 11, 12, 13, 14, 15, 16),
  List(8, 9, 10, 11, 12, 13, 14, 15, 16, 17),
  List(9, 10, 11, 12, 13, 14, 15, 16, 17, 18),
  List(10, 11, 12, 13, 14, 15, 16, 17, 18, 19),
  List(11, 12, 13, 14, 15, 16, 17, 18, 19, 20)
)

The first shift’s continue contains within it, the second shift. So, the continuation for the first shift creates a new buffer which it appends to the function scope buffer then calls the second shift. The continuation for the second shift appends its value to the buffer created by the continuation for the first shift.