Inferring result type in continuations

Question

Is it possible to remove some types from the following code:

import util.continuations._

object TrackingTest extends App {

  implicit def trackable(x: Int) = new {
    def tracked[R] = shift { cf: (Int => (R, Set[Int])) =>
      cf(x) match {
        case (r, ints) => (r, ints + x)
      }
    }
  }


  def track[R](body: => R @cpsParam[(R, Set[Int]), (R, Set[Int])]) = reset {
    (body, Set[Int]())
  }

  val result = track(7.tracked[Int] + 35.tracked[Int])
  assert(result == (42, Set(7, 35)))

  val differentTypes = track(9.tracked[String].toString)
  assert(differentTypes == ("9", Set(9)))
}

track function tracks calls of tracked on Int instances (e.g. 7.tracked).

Is it possible to infer type parameter on tracked implicit, so the following would compile:

track(7.tracked + 35.tracked)

Answer 1

Your question made me think of how continuations can track state. So I adapted that to your case and came up with this:

import util.continuations._

object TrackingTest extends App {

  type State = Set[Int]
  type ST = State => State

  implicit class Tracked(val i: Int) extends AnyVal { 
    def tracked = shift{ (k: Int=>ST) => (state:State) => k(i)(state + i) }
  }

  def track[A](thunk: => A@cps[ST]): (A, State) = {
    var result: A = null.asInstanceOf[A]
    val finalSate = (reset {
      result = thunk
      (state:State) => state
    }).apply(Set[Int]())
    (result, finalSate)
  }

  val result = track(7.tracked + 35.tracked)
  assert(result == (42, Set(7, 35)))

  val differentTypes = track(9.tracked.toString)
  assert(differentTypes == ("9", Set(9)))
}

This is using 2.10.1 but it works fine with 2.9.1 as well provided you replace the 2.10.x implicit value class with:

implicit def tracked(i: Int) = new {
  def tracked = shift{ (k: Int=>ST) => (state:State) => k(i)(state + i) }
}

The key change I made is to have tracked not use any type inference, fixing to Int@cps[ST]. The CPS plugin then maps the computation to the right type (like String@cps[ST]) as appropriate. The state is threaded by the continuation returning a State=>State function that takes the current state (the set of ints) and returns the next state. The return type of reset is a function from state to state (of type ST) that will take the initial state and will return the final state.

The final trick is to use a var to capture the result while still keeping the expected type for reset.

Answer 2

While the exact answer to this question can be given only by the authors of the compiler, we can guess it is not possible by giving a look to the continuation plugin source code.

If you look to the source of the continuations you can see this:

  val anfPhase = new SelectiveANFTransform() {
    val global = SelectiveCPSPlugin.this.global
    val runsAfter = List("pickler")
  }

  val cpsPhase = new SelectiveCPSTransform() {
    val global = SelectiveCPSPlugin.this.global
    val runsAfter = List("selectiveanf")
  }

The anfPhase phase is executed after the pickler phase, and the cpsPhase after selectiveAnf. If you look to SelectiveANFTransform.scala

abstract class SelectiveANFTransform extends PluginComponent with Transform with
  TypingTransformers with CPSUtils {
  // inherits abstract value `global' and class `Phase' from Transform

  import global._                  // the global environment
  import definitions._             // standard classes and methods
  import typer.atOwner             // methods to type trees

  /** the following two members override abstract members in Transform */
  val phaseName: String = "selectiveanf"

If we use scalac -Xshow-phases, we can see the phases during the compilation process:

parser
namer
packageobjects
typer
superaccessors
pickler
refchecks
selectiveanf
liftcode
selectivecps
uncurry
......

As you can see the typer phase is applied before the selectiveAnf and selectiveCps phases. It should be confirmed that type inference occurs in the typer phase, but if this is really the case and it would make sense, it should be now clear why you can't omit the Int type on 7.tracked and 35.tracked.

Now if you are not satisfied yet, you should know that the compiler works by performing a set of transformations on "trees", which you might look, using the following options:

• -Xprint: shows your scala code after a certain phase have been executed
• -Xprint: -Yshow-trees shows your scala code and the trees after the phase have been executed
• -YBrowse: opens a GUI to surf both.