2010-05-11 100 views
4

是否有任何方法可以在CPS中使用尾遞歸函數而不拋出StackOverflow?CPS/Continuations StackOverflowError(尾 - )遞歸函數

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

任何方式規避這個錯誤?蹦牀?通過拋出異常來堆棧展開? 謝謝!

+0

至少while循環雖然被CPS編譯器插件重寫,但不會終止堆棧... – hotzen 2010-05-13 17:58:30

回答

1

您正在調用continuation中的另一個函數。 Scala不支持跨方法的尾遞歸,因爲JVM不支持。

+1

將'@ tailrec'註釋放在'recurse'上,編譯器會告訴您它什麼時候可以'不要填寫你的尾遞歸請求。 – 2011-01-31 14:09:47

1

您可以使用-Xss2M運行Java,但是該錯誤可能僅在一千次以後纔會發生。只要你的方法不是尾遞歸,你將無法解決這個問題。