Использование продолжений Scala с циклами while

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 выполняет оптимизацию хвостового вызова (что, как я думал, не может быть сделано с продолжениями), или происходит что-то еще?

(Этот эксперимент проводится на github вместе с конфигурацией sbt, необходимой для его запуска: https://github.com/jcrudy/scala-continuation-experiments. См. Commit 7cec9befcf58820b925bb222bc25f2a48cbec4a6)

Answer 1

Причина, по которой вы не получаете переполнение стека, потому что то, как вы используете shift а также callback() действует как батут.

Каждый раз, когда поток выполнения достигает shift построить, это устанавливает callback равно текущему продолжению (закрытию), а затем сразу возвращается Unit в контекст вызова. Когда вы звоните next() и вызвать callback(), вы выполняете продолжение закрытия, которое просто выполняет count += 1, затем возвращается к началу цикла и выполняет shift снова.

Одним из ключевых преимуществ преобразования CPS является то, что оно захватывает поток управления в продолжении, а не использует стек. Когда вы установите callback = f на каждой "итерации" вы перезаписываете свою единственную ссылку на предыдущее продолжение / состояние функции, и это позволяет собирать мусор.

Стек здесь достигает глубины всего в несколько кадров (вероятно, около 10 из-за всех вложенных замыканий). Каждый раз, когда вы выполняете shift он захватывает текущее состояние в закрытии (в куче), а затем стек разворачивается обратно к вашему for выражение.

Я чувствую, что диаграмма сделает это более понятным, но пошаговое выполнение кода с помощью вашего отладчика, вероятно, будет столь же полезным. Я думаю, что ключевым моментом здесь является то, что, по сути, вы построили батут, вы никогда не взорвете стек.