?

Предыдущий пост поделиться пожаловаться Следующий пост
Continuations
lex_kravetski
Данная статья не содержит никаких масштабных метафор, тонких ассоциаций или суровой сатиры. Поэтому интересна она будет только программистам. Да и то не всем.

Целью данной статьи является объяснение некоторого момента, который вызывает массу вопросов, а не обучение годному стилю написания программ и не рекомендация всё тут описанное в обязательном порядке использовать.


«Продолжения». Вопросы, что это такое, и зачем оно может понадобится Scala, имеются в изобилии практически в любом месте, где Scala обсуждается в постоянном режиме. А вот ответы на эти вопросы, напротив, почти не имеются.

Но если ответ всё-таки есть, то с вероятностью 99% им будет вот этот пример.

reset {
    shift { k: (Int => Int) =>  // The continuation k will be the '_ + 1' below.
        k(7)
    } + 1
}
// Result: 8


Данный пример поражает своей неинформативностью. Лично я по нему в принципе не смог бы ничего понять, даже если с самого начала бы знал, о чём тут идёт речь. И то, что я в этом вопросе не одинок, подтверждается наличием множества цитат этого примера с приписыванием к нему фраз в стиле «что, блин, тут вообще происходит?».

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

То есть k — это какой-то callback, но и то не факт. И самое главное, зачем всё это нужно, решительно неясно. Однако именно этот пример приводят с завидным постоянством. А что-нибудь более показательное не приводят практически никогда.

По этой причине мнения в интернетах по этому вопросу делятся на следующие три части: некая малая группа читателей, видимо, знает, что такое «продолжения», но никому не говорит, другая, гораздо более многочисленная считает, будто им стало децл понятно, однако практического смысла в этом всё равно нет, поэтому не всё ли равно, и, наконец, третья, самая обширная просто говорит себе «я в упор не понимаю этой хренотни, поэтому подумаю об этом чуть позже — никогда».

Однако те, чей разум постоянно требует ответов, испытывают от «я это пойму через никогда» гнетущую тревогу, а потому не перестают задавать вопросы.

Так вот, некоторые из них, я надеюсь, наткнутся на эту статью и чаемый ответ таки получат.

Формальный ответ на вопрос «что такое continuations?» звучит как «это такой способ запомнить состояние программы, а потом к нему снова вернуться». И он, на мой взгляд, столь же информативен, сколь вышеприведённый код, поскольку только те, кто уже и так понимает, в чём суть, смогут понять и что именно этот ответ означает. Ведь утверждение столь размыто, что под него неплохо подойдёт чуть ли не половина языковых конструкций. Ну а что? Замыкание, например, — тоже «способ запомнить состояние программы». И экземпляр анонимного класса. И экземпляр класса с именем. В общем, всё прямо как чуть выше: ну возвращает этот shift что-то там, нам-то что с того?

Поэтому вместо неясной мистики и долбанного формализма я предлагаю вам взглянуть на гораздо более понятный пример.

import scala.util.continuations._

var op1Callback: Int ⇒ Unit = null
var op2Callback: Int ⇒ Unit = null

println("reset begin")

reset {
    println("reset first line")

    val res1 = shift((k: Int ⇒ Unit) ⇒ op1Callback = k) // Блок 1
    println("op1 result = " + res1)

    val res2 = shift((k: Int ⇒ Unit) ⇒ op2Callback = k) // Блок 2
    println("op2 result = " + res2)
} // Точка выхода

println("reset end")

op1Callback(10)
op2Callback(20)


После его запуска, как на первый взгляд кажется, мы могли бы ожидать следующего содержимого консоли:

reset begin
reset first line
op1 result = 10
op2 result = 20
reset end


Но если мы запустим этот код, то результат будет иным.

reset begin
reset first line
reset end
op1 result = 10
op2 result = 20


И вот почему это так.

Внутри блока reset дважды вызывается shift, который в качестве аргумента требует некую функцию. Смысл этого требования — shift хочет передать в клиентский код некий callback. Мы с благодарностью принимаем оба коллбэка и запоминаем их в двух ссылках opCallback.

Если бы shift был простой функцией, то при выполнении строки кода, помеченной как «Блок 1», сразу после выполнения тела shift мы бы получили результат вызова shift. Этот результат записался бы в res1, потом управление перешло бы на следующую строку, где этот результат вывелся бы на экран.

Потом выполнился бы следующий shift, результат записался бы в res2 и вывелся бы на экран, после чего блок reset кончился, вызвались бы println(«reset end») и два коллбэка, в результате мы увидели бы в консоли первый из вышеприведённых вариантов её содержимого.

Однако вместо этого компилятор собирает код так, что после выполнения тела shift мы выходим из блока reset. То есть следующей строкой выполнения является та, которая следует за «Точкой выхода». res1 к этому моменту ещё не получает значения, вывод в консоль не делается и так далее.

Всё выглядит так, будто сработало нечто, подобное break, выведшего нас за пределы блока reset сразу же после выполнения тела первого встретившегося внутри него shift.

Однако отличие от break тут в том, что дальнейший код блока не был просто пропущен, как это происходит в случае с break. Вместо этого блок как бы на время «заснул», а разбудить его сможет вызов того самого коллбэка, который передал нам первый из shift-ов.

То, что мы передадим в качестве аргумента в коллбэк, станет результатом shift, и в нашем случае попадёт в res1, и с этого места тело блока reset возобновит работу. Вплоть до следующего shift.

Следующий shift вновь приостановит выполнение блока reset — пока в переданный теперь уже вторым shift-ом коллбэк не будет передано значение.

В нашем примере мы вызываем оба коллбэка за блоком reset, два раза восстанавливая выполнение этого блока с соответствующего shift-а, на котором оно притормозилось.

Итак ещё раз вкратце логика работы.

Блок reset выполняется до первого shift. Оный требует передать в него аргументом функцию, в которую он, в свою очередь, передаст аргументом свой коллбэк.

После выполнения shift содержимое блока reset «засыпает», а выполнение продолжается с первой строки за блоком.

Как только в коллбэк будет передано значение, выполнение блока reset продолжится ровно с того места, где он «заснул» — с получения результата shift, равного переданному в коллбэк, и так далее.

И так будет вплоть до следующего shift или до конца блока reset (в последнем случае управление перейдёт на то место, откуда вызывался последний коллбэк).

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

То есть вся эта конструкция — это как бы способ описать цепочку выполняющихся друг за другом функций, каждая из которых простирается от shift до следующего shift или до конца блока reset.

«Функция» от начала reset до первого shift запускается автоматически. Первый shift передаёт нам коллбэк, при помощи которого мы запускаем следующую «функцию» — от этого shift-а до следующего, и так далее.

Что это нам даёт?

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

Концепция действительно сложновата для понимания, да и программа с её использованием, наверно через раз будет выносить мозг тем, кто пытается понять, что тут вообще происходит.

Однако в некоторых случаях данный подход может быть неплохой альтернативой другим высокоуровневым абстракциям многопоточности — future/promise, fork/join, actors и т.п.

Дело в том, что абстракция «продолжений» имеет перед ними одно преимущество: в частности, она позволяет оформить последовательность многопоточных вызовов в «линейный» код. Нам не надо вписывать следующие вызовы в блоки обработки результатов предыдущих — мы пишем всё так, будто бы значения возвращаются к нам сразу, будто бы всё это просто функции. А неявное преобразование всего этого в цепочку событий и реакций на них обеспечивает компилятор.

Так, мы могли бы предположить, что программа в нашем примере делает что-то полезное, — например, в первом shift считывает и обрабатывает какой-то длинный файл, а во втором shift записывает результаты оной обработки в другой длинный файл.

В этом случае, естественно, мы вызывали бы наши коллбэки не после блока reset, а из других потоков — тех, где осуществляется считывание файлов, их обработка и запись, но общая организация кода осталась бы примерно той же: то, что написано в reset, запустило бы процесс параллельной обработки, вернув управление сразу же после запуска всего процесса.

Сама по себе конструкция с reset-shift многопоточной не является. Тело передаваемой в shift функции выполняется в том же потоке, поэтому если в ней напрямую вызвать «обработку длинного файла», то за пределы reset мы выйдем не «мгновенно», а только после завершения обработки. То есть параллельность выполнения мы должны обеспечивать иными способами, не полагаясь на «продолжения».

Иными словами, так неправильно:

def doOp(k: Int ⇒ Unit) = {
    Thread.sleep(10000) // Делаем что-то долгое
    k(10) // Возвращаем «результат вычислений»
}

reset {
    val res = shift(doOp)
    println(res)
    shift(doSomeOtherOp)
}

println("!!!") // Сюда мы попадём минимум через десять секунд


Так правильно:

def doOp(k: Int ⇒ Unit) = {
    new Thread(new Runnable {
        override def run() = {
            Thread.sleep(10000) // Делаем что-то долгое
            k(10) // Возвращаем «результат вычислений»
        }
    }).start()
}

reset {
    val res = shift(doOp)
    println(res)
    shift(doSomeOtherOp)
}

println("!!!") // Сюда мы попадём почти мгновенно


Кроме того, вызов коллбэка с целью продолжить выполнение блока reset, приостанавливает тот поток, откуда производился вызов, передавая выполнение в блок reset — это как раз и обеспечивает «линейность» выполнения.

def doOp(k: Int ⇒ Unit) = {
    new Thread(new Runnable {
        override def run() = {
            Thread.sleep(10000) // Делаем что-то долгое
            k(10) // Возвращаем «результат вычислений»
            println("!!!") // Сюда мы попадём минимум через 20 секунд после вызова k
        }
    }).start()
}

reset {
    val res = shift(doOp)
    println(res)
    Thread.sleep(20000) // Делаем что-то долгое и всё это происходит во время вызова k(10) из doOp
    shift(doSomeOtherOp)
}


Удобно это или нет — от ситуации зависит. Однако иметь в виду это надо.

В общем, такая вот концепция. Пригодится ли она вам, я не знаю, однако, надеюсь, любопытство было удовлетворено.



doc-файл
Публикация в блоге автора



  • 1
(Удалённый комментарий)
Насколько мне удалось понять ещё раньше - аналог setjump/longjump.
Типа функция выполняется-выполняется, а потом решает "да ну нафик, надоело".
А потом делает куда-то переход или вызов.
А там, где-то в глубине вызовов, в произвольном месте - можно возобновить исполение процедуры.

есть у меня впечатления что пока это не поиспользуешь самостоятельно ничо так и не дойдет.


бо читал я про них в разрезе Лиспа (причем с инструкцией как их на лиспе самому написать), в разрезе Схемы, что по сути то же самое, вот теперь в разрезе скалы почитал.

Толку ровно одинаково...

Это весьма эзотерическая концепция.

Создалось впечатление о неком асинхронном goto.

Re: Ответ на вашу запись "Continuations"

Не goto — break.

Вот если итератор с yield return наизнанку вывернуть - начто подобное получится.

С yield return - это называется ГЕНЕРАТОРЫ. По сути и они, и продолжения - различные формы сопрограмм.

Любопытный механизм, крайне.

Заодно хотел тонко, сурово и метафорично пошутить, но первый комментатор заведомо меня переплюнул.

Иногда мне кажется что некоторые конструкции надо изучить только для того чтобы знать за что бить тех кто это написал в боевом коде.

Можно я это напечатаю и в рамочке над столом повешу?

Это очень похоже на использование директив async и await в C# 5. Очень неплохо там придумано, кстати.

Вобщем разъяснение получилось не сильно понятнее заумного примера. Зачем это нужно мы так и не поняли. В 2011 комментаторы и то лучше справлялись., а так например. Учиться объяснять программирование нужно вот так http://blog.bruchez.name/2011/09/continuations-in-scala.html (Другого эрика вам уже советовали). Этот человек рассказывает тоже самое что мы пытались сказать в 2011: у вас есть сервер, он работает в цикле
loop {
  input = get_next_message()
  process(input)
}

он не должен сильно задерживаться на каждом запросе чтобы у вас например GUI не подвис, если наш поток является гуишным обработчиком. Для длительной обработки он может запускать параллельные задачи. По их окончании ему тоже придёт сообщение и он возобновит преравнную задачу. Проблема однако в том что значения переменных на тот момент уже будут другие и исполняющий поток вынужден будет вспоминать "а на чём мы собственно остановились?". То есть ему нужно вычитывать состояние из сообжения. Это муторно сперва сохранять состоянеи в сообщение, потом при помощи case-ов его оттудова доставать. Это ещё машина состояний называется
loop {
  Дождаться нового цикла
  switch state
    case A: делаем то, новое сост => B
    case B: делаем сё, новое сост => C
    case C: делаем пятое, новое сост => D
    case D: делаем десятое, новое сост =>  A

Это например в VHDL-е так. Состояния сигналов обновляются каждый такт, но не раньше, а дожидаться прходится забывая в каком месте программы процесс находился до этого. Точнее номер строки запоминается в сигнале state и потом на нужную строку приходится прыгать таким вот неазтейливым способом. Выглядит опрятно, но программировать нифига не удобно
Удобнее обычными блокирующими вызовами, когда последовательность действий задаётся просто порядком стейтментов в программе. В функциональном программировании мы можем вместо

долго делай это
долгко делай это
а потом ещё долго делай это

написать

"асинхронно сделай это, а когда закончишь запусти ещё вот эту функцию, как продолжение"

Continuations похоже могут заменить композицию функций
f1(
  f2(
    f3())) 

в серийную форму "стейтментов"
f1
f2
f3

ценой того что вместо indent-ов надо писать

shift(f1)
shift(f2)
shift(f3)


(отсюда видимо и название!). Continuations похоже умеют брать весь код который между shift и конец блока reset и исполнять его позже, как одну функцию, аргументом который будет результат функции-аргумета shift.

Тут место для Монад и Функторов лифтинга

С сервера/машины состояний на мой взгляд надо излагать. А потом уже рассказывать про reset и shit. Ожидания на мой взгляд, даже в другом потоке ничего не иллюстрируют. Потому что если нужно сразу продолжать - создали поток и пусть он там себе исполняет всё последовательно, если нужно подождать результата - прямой вызов и ждём. При чём тут continuations? Поэтому и первый вопрос: что такое continuations и зачем это нужно.

> В 2011 комментаторы и то лучше справлялись

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

> http://blog.bruchez.name/2011/09/continuations-in-scala.html

А вот этот справился, да.

> Это муторно сперва сохранять состоянеи в сообщение, потом при помощи case-ов его оттудова доставать. Это ещё машина состояний называется

Таким способом уже давно не делают.

> Continuations похоже могут заменить композицию функций в серийную форму "стейтментов"

Это только часть концепции.

> При чём тут continuations?

При том, что можно это дело записать линейно, а не в виде отдельных реакций на события.

Edited at 2014-07-02 20:24 (UTC)

Этот кадр говорит что распрямлять функциональные продолжения в императивный стиль не нужно

May Your Data Ever Be Coherent?
нужно https://www.youtube.com/watch?v=gVXt1RG_yN0#t=649

Я вот как-то не доконца понял на примерах, почему "шибко умный компилятор"™ не может так параллелить?

Сперва нужно чётко обозначить в каком потоке будет исполнятся само продолжение (что произойдёт с тем потоком который выполнял первый shift). Из того что возврат результата происходит вызовом функции совсем не очевидно что он просто убъётся вместо того чтобы самому довести дело до конца. А потом уже про распараллеливоемость думать. Там может быть много ньюансов - создавать новый поток или погодеть или кинуть исполнение на какой-нибудь executor, какие параметры должны быть у нового потока (размер стека) если его создавать, а чаще всего может вообще потребываться не другой поток, а async io вместо потока правда в этом случае вопрос "а кто/как будет вызывать продолжение?" возникает с новой силой. Вобщем это место совершенно непроработано так что непонятно как пользователь прочитав её поймёт: пользовать ему continuations или обойтись без них.

В Яваскипт6 офигительную фичу добавили

https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Statements/function*

По-моему, я про них у кравецкого читал. Правда по ссылке гораздо короче и понятнее.

  • 1