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

Я понимаю, что это противоречит обычному смыслу 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 см. коммит 7cec9befcf58820b925bb222bc25f2a48cbec4a6)

1 9
scala continuations delimited-continuations

1 ответ:

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

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

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

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

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

7