Поддерживает ли плагин продолжения Scala вложенный сдвиг?

Я просматриваю следующий учебник Shift/Reset: http://www.is.ocha.ac.jp/~asai/cw2011tutorial/main-e.pdf.

На данный момент я получил довольно хорошие результаты при переводе примеров OchaCaml на Scala (вплоть до раздела 2.11). Но теперь я, кажется, ударился о стену. Код из статьи Асаи/Киселева определяет следующую рекурсивную функцию (кажется, это 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-нормализует лямбда-выражение. Это мой перевод Scala:

// 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 (+ сдвиг/сброс из здесь) или будут ли такие же ограничения с вложенным сдвигом? Я также добавляю тег 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

scala haskell continuations
person huynhjl    schedule 09.04.2013    source источник

Ответы (1)


arrow_upward
2
arrow_downward

Проблема в строке:

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

Я не уверен, но я думаю, что механизм вывода типов сбит с толку тем фактом, что 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 в целом, вы определенно можете сделать это, если каждое вложенное продолжение имеет совместимый тип:

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

Эта программа выводит на стандартный вывод:

x: 1
y: 2
z: 3
person earldouglas    schedule 21.06.2013
comment
Интересно, мне придется вернуться к своему коду и проверить, компилируется ли простое извлечение приложения. - person huynhjl; 22.06.2013
comment
Спасибо, теперь работает! Теперь мне нужно обдумать, что на самом деле делает этот умопомрачительный код. - person huynhjl; 22.06.2013