scala - 在while循环中使用Scala延续

Question

我意识到这与通常的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。请参见commit 7cec9befcf58820b925bb222bc25f2a48cbec4a6)

Answer 1

之所以没有在此处导致堆栈溢出，是因为您使用shift和callback()的方式就像trampoline一样。

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

CPS转换的主要好处之一是，它捕获了连续中的控制流，而不是使用堆栈。在每个“迭代”上设置callback = f时，您将覆盖对函数的先前延续/状态的唯一引用，从而可以对其进行垃圾回收。

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

我觉得用图可以使这一点变得更清楚，但是使用调试器逐步执行代码可能同样有用。我认为这里的关键是，因为您基本上已经 build 了蹦床，所以永远不会炸毁堆栈。