9

我意识到这与 SO 问题的通常意义背道而驰，但是即使我认为它不应该工作，以下代码仍然有效。下面是一个小的 Scala 程序，它使用带有 while 循环的延续。根据我对延续传递风格的理解，这段代码应该会通过为 while 循环的每次迭代向堆栈添加一个帧来产生堆栈溢出错误。但是，它工作得很好。

import util.continuations.{shift, reset}


class InfiniteCounter extends Iterator[Int] {
    var count = 0
    var callback: Unit=>Unit = null
    reset {
        while (true) {
            shift {f: (Unit=>Unit) =>
                callback = f
            }
            count += 1
        }

    }

    def hasNext: Boolean = true

    def next(): Int = {
        callback()
        count
    }
}

object Experiment3 {

    def main(args: Array[String]) {
        val counter = new InfiniteCounter()
        println(counter.next())
        println("Hello")
        println(counter.next())
        for (i <- 0 until 100000000) {
            counter.next()
        }
        println(counter.next())
    }

}

输出是：

1
Hello
2
100000003

我的问题是：为什么没有堆栈溢出？Scala 编译器是在做尾调用优化（我认为它不能用延续做）还是有其他事情发生？

（此实验与运行它所需的 sbt 配置一起在 github 上：https ://github.com/jcrudy/scala-continuation-experiments 。请参阅提交 7cec9befcf58820b925bb222bc25f2a48cbec4a6）

4

1 回答 1

7

您在这里没有堆栈溢出的原因是因为您使用的方式shift就像callback()蹦床一样。

每次执行线程到达shift构造时，它设置callback等于当前的延续（闭包），然后立即返回Unit到调用上下文。当你调用next()和调用callback()时，你会执行延续闭包，它只是执行count += 1，然后跳回到循环的开头并shift再次执行。

CPS 转换的主要好处之一是它在延续中捕获控制流，而不是使用堆栈。当您设置callback = f每个“迭代”时，您将覆盖您对函数先前继续/状态的唯一引用，这允许它被垃圾收集。

这里的堆栈只达到几帧的深度（由于所有嵌套的闭包，它可能在 10 左右）。每次执行时，shift它都会在闭包中（在堆中）捕获当前状态，然后堆栈展开回您的for表达式。

我觉得图表会让这更清楚——但使用调试器单步执行代码可能同样有用。我认为这里的关键点是，因为你基本上已经建立了一个蹦床，所以你永远不会破坏堆栈。

于 2013-12-21T19:06:16.117 回答