cannot cps-transform malformed expression

[cristipp]

Experimenting on implementing http://www.randomhacks.net/2005/10/11/amb-operator via delimited continuations in Scala. Getting:

Error:(172, 17) cannot cps-transform malformed (possibly in shift/reset placement) expression
          reset {

The code attempt:

"playground" should "eval amb via delimited continuations" in {
    import scala.util.continuations._

    case class Cont[T, U](fn: T => U, arg: T)

    class Evaluator[T, U](init: Cont[T, U]) {
      var queue = Queue.empty[Cont[Any, U]]
      var results = Vector.empty[U]

      lazy val eval: Vector[U] = {
        queue.enqueue(init)
        loop()
        results
      }

      def amb[V](vs: Vector[V]): V @cpsParam[U, Unit] = {
        shift {
          k: (V => U) =>
            vs.foreach {
              v =>
                queue.enqueue(Cont[V, U](k, v))
            }
        }
      }

      @tailrec
      private def loop(): Unit = {
        if (queue.nonEmpty) {
          val (cont, newQueue) = queue.dequeue
          queue = newQueue
          reset {
            val result = cont.fn(cont.arg)
            results = results :+ result
          }
          loop()
        }
      }
    }
  }

Not sure what to do next...

[howtonotwin]

A bit late, but this a non-issue (or perhaps just a case of bad error message).

This should just be something like

def ambImpl[A, B](xs: List[A])(rest: A => Option[B]): Option[B] = xs match {
  case Nil => None
  case x :: xs1 => rest(x).orElse(ambImpl(xs1)(rest))
}
final class Amb[B] private[containingscope]() {
  def apply[A](xs: List[A]): A @cps[Option[B]] = shift(ambImpl(xs))
}
def amb[B]: Amb[B] = new Amb()

The shift/reset-style continuations here are different from the call/cc-style continuations at the link. The Ruby version used an explicit vector of backtrack points, because calling the continuation means "abort", and the stack was used for normal flow-control. The Scala version is pretty much the opposite. The stack contains the backtracking information in a sequence of calls to amb, and communication between amb and the caller is done via the continuations. You were using reset entirely wrong. The reset goes around the shifts (the shifts can be bare, or inside other functions), and it limits how much of a continuation they can capture. You didn't put a shift inside the reset, breaking it.

The whole class Amb dance is because type inference is absolutely atrocious with this plugin. You'll have to do things like Ret to actually use amb:

val nums = (1 to 5).toList
println(reset {
  type Ret = (Int, Int)
  Some((amb[Ret](nums), amb[Ret](nums)))
    .filter { case (a, b) => val x = a + b; x * x == 8 * x }
})
// more like the Ruby version
println(reset {
  type Ret = (Int, Int)
  val l = amb[Ret](nums)
  val r = amb[Ret](nums)
  val x = l + r 
  Some(amb[Ret](if(x * x == 8 * x) List((l, r)) else Nil))
})

[TiarkRompf]

You might want to try passing a type parameter to the resets. Sometimes having an expected type eliminates the need to give explicit parameters elsewhere.