9

これは SO の質問の通常の意味に反していることは認識していますが、次のコードは機能しないはずですが、機能します。以下は、while ループで継続を使用する小さな Scala プログラムです。継続渡しスタイルに関する私の理解によれば、このコードは、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 変換の主な利点の 1 つは、スタックを使用するのではなく、継続で制御の流れを捉えることです。callback = f各「反復」を設定すると、関数の以前の継続/状態への唯一の参照が上書きされ、ガベージコレクションが可能になります。

ここでのスタックは、数フレームの深さにしか達しません (すべてのネストされたクロージャーのため、おそらく 10 前後です)。を実行するたびにshift、現在の状態がクロージャー (ヒープ内) にキャプチャされ、スタックが展開されて式に戻りますfor。

ダイアグラムを使用するとより明確になると思いますが、デバッガーを使用してコードをステップ実行することも同様に役立つでしょう。ここでの重要な点は、トランポリンを本質的に構築したので、スタックを爆破することは決してないということです。

于 2013-12-21T19:06:16.117 に答える