Using Scala's Delimited Continuations for implicit Monads

Question

Hello,

I'm playing with some kind of DSL defined by an monadic interface.

Since applying the monad using a bunch of flatMap applications is kind of cumbersome and I find for-comprehension syntactically not that beautiful, I'm trying to implicitely mix monadic and non monadic code using delimited continuations.

It's actually working fine, but I'm really not happy with the types, because I have to restrain my self to the type "Any" to make at compilable :(. Thus using "Any" and "casting" later when the result is needed may lead to runtime errors...

Here is some example Code for mixing the Option-Monad in Scala with regular code, so you can see what I am talking about:

object BO {

  import scala.util.continuations._

  def runOption[C](ctx: => Any @cpsParam[Option[Any],Option[Any]]): Option[C] = {
    val tmp : Option[Any] = reset {
      val x : Any = ctx
      Some(x)
    }
    tmp.asInstanceOf[Option[C]]
  }

  def get[A](value:Option[A]) = shift { k:(A=>Option[Any]) => 
    value.flatMap(k)
  }     

  class CPSOption[A](o:Option[A]) {
    def value = get[A](o)
  }

  implicit def opt2cpsopt[A](o:Option[A]) = new CPSOption(o)

  def test1 = runOption[Int] {
    val x = get(None)
    x
  }

  def test2 = runOption[Int] {
    val x = Some(1).value
    x
  }

  def test3 = runOption[Int] {
    val x = Some(1)
    val y = Some(2)
    x.value + y.value
  }            

  def test_fn(x:Option[Int], y:Option[Int], z:Option[Int]) = runOption[Int] {
    x.value * x.value + y.value * y.value + z.value * z.value
  }            

  def test4 = test_fn(Some(1), Some(2), Some(3))

  def test5 = test_fn(Some(1), None, Some(3))
}

compile the code with: $ scalac -P:continuations:enable BO.scala

and test in scala REPL:

scala> import BO._
scala> test4
res0: Option[Int] = Some(14)
scala> test5
res1: Option[Int] = None

The Option-Monad is run using the runOption function (see test functions). Functions being called inside runOption can use the get function or the value method to get the value from an Option. In case the value is None, the Monad will stop immediately and return None. So there is no more need for pattern matching on value of type Option.

The Problem is, that I have to use the type "Any" in runOption and for the type of the continuation in get.

Is it possible to express runOption and get with rank-n types in scala? So I can write:

def runOption[C](ctx: forall A . => A @cpsParam[Option[A], Option[C]]) : Option[C] = 
  ...

def get[A](value:Option[A]) = shift { k:(forall B . A=>Option[B]) => 
  value.flatMap(k)
}

Thanks!

Answer 1

Scala doesn't have higher-rank polymorphism, although you can simulate it with some contortions (see here and here). The good news is, that kind of firepower isn't necessary here. Try these:

def runOption[A](ctx: => A @cps[Option[A]]): Option[A] = reset(Some(ctx))

def get[A](value:Option[A]) = shift { k:(A=>Option[A]) => value flatMap k }

Second Attempt

Ok, let's try this again, in light of your example using more than one type in the runOption block:

object BO {

  import scala.util.continuations._

  def runOption[A](ctx: => A @cps[Option[A]]): Option[A] = reset(Some(ctx))

  def get[A, B](value:Option[A]):A @cps[Option[B]] = shift { k:(A=>Option[B]) => 
    value flatMap k
  }

  class CPSOption[A](o:Option[A]) {
    def value[B] = get[A, B](o)
  }

  implicit def opt2cpsopt[A](o:Option[A]) = new CPSOption[A](o)

  def test1 = runOption {
    val x = get[Int, Int](None)
    x
  }

  def test2 = runOption {
    Some(1).value[Int]
  }

  def test3 = runOption {
    val x = Some(1)
    val y = Some(2)
    x.value[Int] + y.value[Int]
  }

  def test_fn(x:Option[Int], y:Option[Int], z:Option[Int]) = 
    runOption (x.value[Int] * x.value[Int] + 
               y.value[Int] * y.value[Int] + 
               z.value[Int] * z.value[Int])

  def test4 = test_fn(Some(1), Some(2), Some(3))

  def test5 = test_fn(Some(1), None, Some(3))

  def test6 = runOption { val x = Some(1)
                          val y = Some(2)
                          x.value[Boolean] == y.value[Boolean] }
}

Unfortunately, as you can see, the results ain't pretty. Due to Scala's limited type inferencing ability, you need to provide an explicit type parameter for most uses of value, and in any given runOption block, it'll always be the same type parameter for every usage of value--see test_fn for where this gets pretty horrible. On the other hand, you no longer need to provide an explicit type parameter to the runOption block, but that's a pretty small win in comparison. So this is completely type-safe now, but it's not what I'd call user-friendly, and I'm guessing user-friendliness was the point of this library.

I remain convinced that rank-n types are not applicable here. As you can see, the problem here is now one of type reconstruction, and rank-n types make reconstruction more difficult, not less!