haskell - Does Scala continuation plugin support nested shift? -

i going through following shift/reset tutorial: http://www.is.ocha.ac.jp/~asai/cw2011tutorial/main-e.pdf.

i got pretty results far in translating ochacaml examples scala (all way section 2.11). seem have hit wall. code paper asai/kiselyov defines following recursive function (this ochacaml - think):

(* a_normal : term_t => term_t *) let rec a_normal term = match term     var (x) -> var (x)   | lam (x, t) -> lam (x, reset (fun () -> a_normal t))   | app (t1, t2) ->       shift (fun k ->         let t = gensym () in (* generate fresh variable *)         app (lam (t, (* let expression *)                   k (var (t))), (* continue new variable *)              app (a_normal t1, a_normal t2))) ;; 

the function supposed a-normalize lambda expression. scala translation:

// section 2.11 object shiftreset extends app {    sealed trait term   case class var(x: string) extends term   case class lam(x: string, t: term) extends term   case class app(t1: term, t2: term) extends term    val gensym = {     var = 0     () => { += 1; "t" + }   }    def a_normal(t: term): term@cps[term] = t match {     case var(x) => var(x)     case lam(x, t) => lam(x, reset(a_normal(t)))     case app(t1, t2) => shift{ (k:term=>term) =>       val t = gensym()       val u = lam(t, k(var(t)))       val v = app(a_normal(t1), a_normal(t2))       app(u, v): term     }   }  } 

i getting following compilation error:

 found   : shiftreset.term @scala.util.continuations.cpssynth               @scala.util.continuations.cpsparam[shiftreset.term,shiftreset.term]  required: shiftreset.term     case app(t1, t2) => shift{ (k:term=>term) =>                                               ^ 1 error found 

i think plugin telling me cannot deal nested shift... there way make code compile (either basic error i've overlooked or workaround)? have tried convert pattern match if/else if/else , introduce more local variables got same error.

alternately, have more luck using haskell , cont monad (+ shift/reset here) or there going same type of limitation nested shift? adding haskell tag well, since don't mind switching haskell go through rest of tutorial.

edit: james figured out line continuation plugin not deal , how tweak it, works. using version in answer , following formatting code:

def format(t: term): string = t match {   case var(x) => s"$x"   case lam(x, t) => s"\\$x.${format(t)}"   case app(lam(x, t1), t2) => s"let $x = ${format(t2)} in ${format(t1)}"   case app(var(x), var(y)) => s"$x$y"   case app(var(x), t2) => s"$x (${format(t2)})"   case app(t1, t2) => s"(${format(t1)}) (${format(t2)})" } 

i output paper mentions (though don't grasp yet how continuation manages it):

scombinator: \x.\y.\z.(xz) (yz) reset{a_normal(scombinator)}: \x.\y.\z.let t1 = xz in let t2 = yz in let t3 = t1t2 in t3 

the problem line:

val v = app(a_normal(t1), a_normal(t2)) 

i'm not certain, think type inferencer getting confused fact a_normal returns term@cps[term], we're inside shift continuation isn't annotated same way.

it compile if pull line out of shift block:

def a_normal(t: term): term@cps[term] = t match {   case var(x) => var(x)   case lam(x, t) => lam(x, reset(a_normal(t)))   case app(t1, t2) =>     val v = app(a_normal(t1), a_normal(t2))     shift{ (k:term=>term) =>       val t = gensym()       val u = lam(t, k(var(t)))       app(u, v): term     } } 

regarding nested shifts in general, can if each nested continuation has compatible type:

object nestedshifts extends app {    import scala.util.continuations._    def foo(x: int): int@cps[unit] = shift { k: (int => unit) =>        k(x)   }    reset {     val x = foo(1)     println("x: " + x)      val y = foo(2)     println("y: " + y)      val z = foo(foo(3))     println("z: " + z)   } } 

this program prints stdout:

x: 1 y: 2 z: 3