斯卡拉延續插件是否支持嵌套移位？

Question

我正在閱讀以下Shift/Reset教程：http://www.is.ocha.ac.jp/~asai/cw2011tutorial/main-e.pdf。

到目前爲止，在將示例翻譯爲Scala（直到第2.11節）的過程中，我獲得了相當不錯的結果。但現在我似乎碰壁了。從淺井/ Kiselyov紙上的代碼定義了以下遞歸函數（這是OchaCaml - 我認爲）：

(* a_normal : term_t => term_t *) 
let rec a_normal term = match term with 
    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 with new variable *) 
      App (a_normal t1, a_normal t2))) ;; 

的功能應該A-正常化lambda表達式。這是我的斯卡拉翻譯：

// 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 i = 0 
    () => { i += 1; "t" + i } 
    } 

    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 
    } 
    } 

} 

我收到以下編譯錯誤：

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) => 
              ^
one error found 

我覺得這個插件是告訴我，它不能處理嵌套shift ...是否有辦法讓代碼編譯（我忽略了一個基本錯誤或者一些解決方法）？我試圖將模式匹配轉換爲if/else if/else並引入更多局部變量，但我得到了相同的錯誤。或者，使用Haskell和Cont monad（+ here的移位/重置），還是會出現與嵌套移位相同類型的限制？我也添加了Haskell標籤，因爲我不介意轉換到Haskell來完成本教程的其餘部分。

編輯︰感謝詹姆斯誰找出延續插件無法處理和如何調整它現在的作品。利用他的回答和版本如下格式代碼：

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)})" 
} 

我得到的文件提到了（雖然我不掌握還延續實際上是如何對其進行管理），輸出：

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 

Answer 1

問題是這一行：

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

我不能肯定，但我認爲類型inferencer是越來越由事實混淆起來，a_normal返回Term@cps[Term]，但我們在shift之內，所以延續並沒有以同樣的方式進行註釋。

如果你拉排隊出shift塊它將編譯：

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 
    } 
} 

關於嵌套shift S IN一般情況下，你絕對可以做到這一點，如果每個嵌套延續具有兼容類型：

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) 
    } 
} 

這個程序打印到stdout：

x: 1 
y: 2 
z: 3