What type parameters should I use to make List.map work with delimited continuations?

Question

I'm basically following the example given at the Scala API page for delimited continuations. The code below works fine:

import scala.util.continuations._
import scala.collection.mutable.HashMap

val sessions = new HashMap[Int, Int=>Unit]
def ask(prompt: String): Int @cps[Unit] = shift {
  ret: (Int => Unit) => {
    val id = sessions.size
    printf("%s\nrespond with: submit(0x%x, ...)\n", prompt, id)
    sessions += id -> ret
  }
}

def submit(id: Int, addend: Int): Unit = {
  sessions.get(id) match {
    case Some(continueWith) => continueWith(addend)
  }
}

def go = reset {
  println("Welcome!")
  val first = ask("Please give me a number")
  val second = ask("Please enter another number")
  printf("The sum of your numbers is: %d\n", first + second)
}

However, when I modify go to the following:

def go = reset {
  println("Welcome!")
  List("First?","Second?").map[Int @cps[Unit]](ask)
}

I get this error:

error: wrong number of type parameters for method map: [B, That](f: String => B)
(implicit bf: scala.collection.generic.CanBuildFrom[List[String],B,That])That
             List("First?","Second?").map[Int @cps[Unit]](ask)
                                         ^

Adding Any as a second type parameter doesn't help. Any idea what types I should be supplying?

Answer 1

Here's the closest thing I could work out. It uses shiftR to reify the continuation rather than reset it, uses a foldRight to construct the suspended continuation chain, uses a shift/reset block to get the continuation after the suspension, and an "animate" method to kick off the suspended continuation.

import scala.collection.mutable.HashMap
import scala.util.continuations._

val sessions = new HashMap[Int, (Unit=>Unit, Int)]
val map = new HashMap[Int, Int]

def ask(pair:(String, Int)) = pair match { 
  case (prompt, index) => shiftR { (ret: Unit => Unit) => {
    val id = sessions.size
    printf("%s\nrespond with: submit(0x%x, ...)\n", prompt, id)
    sessions += id -> (ret, index)
    ()
  }}
}

def submit(id: Int, addend: Int): Unit = {
  sessions.get(id) match {
    case Some((continue, index)) => { map.put(index, addend); continue() }
  }
}

def sum(m:HashMap[Int,Int]) : Int = {
  m.fold[(Int, Int)]((0, 0))((a, b) => (0, {a._2+b._2}))._2
}

type Suspended = ControlContext[Unit,Unit,Unit]

class AnimateList(l:List[Suspended]) {
  def suspend(k: => Unit) = (c: Unit) => k
  def animate(k:Unit => Unit): Unit = {
    l.foldRight(k)(
      (elem: Suspended, acc: Unit => Unit) => suspend(elem.fun(acc, ex => ())))()
  }
}

implicit def listToAnimateList(l:List[Suspended]) = new AnimateList(l)

reset { 
  val conts = List("First?","Second?","Third?").zipWithIndex.map(ask)
  shift { conts.animate }
  println(sum(map))
}

Answer 2

The reason is that this is simply not possible without creating a CPS-transformed map method on List: the CPS annotations make the compiler turn your methods “inside out” in order to pass the continuation back to where it is needed and the standard List.map does not obey the transformed contract. If you want to have your mind wrapped in Klein bottles for a while you may look at the class files produced from your source, in particular the method signatures.

This is the primary reason why the CPS plugin will never be a complete generic solution to this problem, which is not due to a deficiency but caused by an inherent mismatch between “straight” code and continuation passing style.

Answer 3

You need to give correct parameter for the CanBuildFrom implicit to be found:

List("First?","Second?").map[Int @cps[Unit], List[Int @cps[Unit]](ask)

But do you really need to be explicit about type? maybe just do .map(ask) will work.