CPS/Continuations StackOverflowError для (хвостовых) рекурсивных функций

есть ли способ иметь функцию хвостовой рекурсии внутри CPS, не вызывающую StackOverflow?

import scala.util.continuations._
object CPSStackOverflow {
  def main(args: Array[String]) = {
    reset {
      def recurse(i: Int): Unit @suspendable = {
        println(i)
        shift { k: (Unit => Unit) =>
          k( () ) // just continue
        }
        recurse(i + 1)
      }
      recurse(1)
    }
  }
}

приводит к следующему StackOverflowError:

1298
1299
1300
Exception in thread "main" java.lang.StackOverflowError
    at java.nio.CharBuffer.wrap(CharBuffer.java:350)
    at sun.nio.cs.StreamEncoder.implWrite(StreamEncoder.java:246)
    at sun.nio.cs.StreamEncoder.write(StreamEncoder.java:106)
    at java.io.OutputStreamWriter.write(OutputStreamWriter.java:190)
    at java.io.BufferedWriter.flushBuffer(BufferedWriter.java:111)
    at java.io.PrintStream.write(PrintStream.java:476)
    at java.io.PrintStream.print(PrintStream.java:619)
    at java.io.PrintStream.println(PrintStream.java:773)
    at scala.Console$.println(Console.scala:198)
    at scala.Predef$.println(Predef.scala:182)
    at test.CPSStackOverflow$$anonfun$main$1.recurse$1(CPSStackOverflow.scala:9)
    at test.CPSStackOverflow$$anonfun$main$1$$anonfun$recurse$1$2.apply(CPSStackOverflow.scala:13)
    at test.CPSStackOverflow$$anonfun$main$1$$anonfun$recurse$1$2.apply(CPSStackOverflow.scala:10)
    at scala.util.continuations.ControlContext$$anonfun$flatMap$2$$anonfun$apply$2.apply(ControlContext.scala:71)
    at test.CPSStackOverflow$$anonfun$main$1$$anonfun$recurse$1$1.apply(CPSStackOverflow.scala:11)
    at test.CPSStackOverflow$$anonfun$main$1$$anonfun$recurse$1$1.apply(CPSStackOverflow.scala:10)
    at scala.util.continuations.package$$anonfun$shiftR$1.apply(package.scala:58)
    at scala.util.continuations.package$$anonfun$shiftR$1.apply(package.scala:58)
    at scala.util.continuations.ControlContext$$anonfun$flatMap$2.apply(ControlContext.scala:68)
    at scala.util.continuations.ControlContext$$anonfun$flatMap$2.apply(ControlContext.scala:67)
    at scala.util.continuations.ControlContext$$anonfun$flatMap$2$$anonfun$apply$2.apply(ControlContext.scala:73)
    at test.CPSStackOverflow$$anonfun$main$1$$anonfun$recurse$1$1.apply(CPSStackOverflow.scala:11)
    at test.CPSStackOverflow$$anonfun$main$1$$anonfun$recurse$1$1.apply(CPSStackOverflow.scala:10)
    at scala.util.continuations.package$$anonfun$shiftR$1.apply(package.scala:58)
    at scala.util.continuations.package$$anonfun$shiftR$1.apply(package.scala:58)
etc...

Есть ли способ обойти эту ошибку? батут? раскручивание стека путем создания исключений? Спасибо!


scala continuations scala-2.8
person hotzen    schedule 11.05.2010    source источник
comment
По крайней мере, цикл while, хоть и переписанный CPS-компилятором-плагином, работает, не убивая стек...   -  person hotzen    schedule 13.05.2010

Ответы (2)


arrow_upward
1
arrow_downward

Вы вызываете другую функцию внутри продолжения. Scala не поддерживает хвостовую рекурсию между методами, потому что JVM не поддерживает.

person Anonymous    schedule 31.01.2011
comment
поместите аннотацию @tailrec в recurse, и компилятор сообщит вам, когда он не сможет выполнить ваш запрос на хвостовую рекурсию. - person Ken Bloom; 31.01.2011

arrow_upward
1
arrow_downward

Вы можете запустить Java с -Xss2M, однако эта ошибка может возникнуть только через тысячу итераций. Пока ваш метод не является хвостовой рекурсией, вы не сможете обойти эту проблему.

person Joa Ebert    schedule 11.05.2010