Использование продолжений 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. См. commit 7cec9befcf58820b925bb222bc25f2a48cbec4a6)


scala continuations delimited-continuations
person jcrudy    schedule 21.12.2013    source источник

Ответы (1)


arrow_upward
7
arrow_downward

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

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

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

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

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

person DaoWen    schedule 21.12.2013
comment
Я думаю, это отличное объяснение чего-то довольно запутанного. Я могу попытаться обрисовать это визуально и выложу здесь ссылку, если создам что-нибудь иллюстративное. Чтобы уточнить, это означает, что эта конструкция не только не взорвет стек, но и общие требования к памяти также скромны и не зависят от количества итераций? - person jcrudy; 21.12.2013
comment
@jcrudy - Да, требования к памяти не зависят от количества итераций в выражении for. В качестве простого теста я запустил ваш код следующим образом: JAVA_OPTS="-Xmx2M -verbose:gc" scala Experiment3 (это работает на моем ноутбуке). Это доказывает, что 100 миллионов итераций работают с объемом кучи всего 2 МБ. Добавление опции для подробной сборки мусора также позволяет увидеть, что фактическое использование памяти остается практически постоянным на протяжении всего выполнения. - person DaoWen; 22.12.2013
comment
В блоге Рича Догерти есть красивый иллюстрированный пост о батутах в Scala: blog.richdougherty.com/2009/04/ - person jcrudy; 16.01.2014