CPS / Fortsetzungen Stackoverflow on (Schwanz-) rekursive Funktionen
-
25-09-2019 - |
Frage
ist es eine Möglichkeit, eine Schwanz-rekursive Funktion innerhalb CPS hat keinen Stackoverflow zu werfen?
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)
}
}
}
Ergebnisse in folgenden Stackoverflow:
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...
Jede Möglichkeit, diesen Fehler zu umgehen? Trampolin springen? Stack-Abwicklung von Ausnahmen zu werfen? Dank!
Lösung
Sie fordern eine andere Funktion in der Fortsetzung. Scala nicht unterstützt Cross-Methode Endrekursion, weil die JVM nicht.
Andere Tipps
Sie können Java mit -Xss2M
laufen jedoch, dass Fehler erst später tausend Iterationen auftreten könnten. Solange Ihre Methode nicht Schwanz rekursiv ist, werden Sie nicht in der Lage sein, dieses Problem zu umgehen.
Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow