使用带循环的Scala延续

Question

我意识到这与通常的SO问题相反,但是即使我认为它不起作用,下面的代码也能正常工作.下面是一个小型Scala程序,它使用while循环的continuation.根据我对连续传递样式的理解,这段代码应该通过在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编译器是否正在进行尾调用优化(我认为它不能用continuation进行)或是否还有其他事情要进行？

(这个实验是在github上运行它所需的sbt配置:https://github.com/jcrudy/scala-continuation-experiments.见commit 7cec9befcf58820b925bb222bc25f2a48cbec4a6)

Answer 1

不要因为你使用的方式在这里得到一个堆栈溢出的原因shift和callback()被表现得像一个蹦床.

每次执行线程到达shift构造时,它都设置为callback等于当前的continuation(闭包),然后立即返回Unit到调用上下文.当你调用next()并调用时callback(),你执行刚刚执行的continuation闭包count += 1,然后跳回到循环的开头并shift再次执行.

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

这里的堆栈只能达到几帧的深度(由于所有嵌套的闭包,它可能大约为10帧).每次执行时,shift它都会捕获闭包中的当前状态(在堆中),然后堆栈将展开回到for表达式.

我觉得图表会让这个更清晰 - 但是使用调试器逐步执行代码可能同样有用.我认为这里的关键点是,因为你基本上建造了一个蹦床,所以你永远不会砸到堆叠.