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.