Поскольку вы, кажется, больше интересуетесь концепцией «продолжения», а не конкретным кодом, давайте на минутку забудем об этом коде (особенно потому, что он довольно старый, и мне не очень нравятся эти примеры, потому что ИМХО вы не может понять их правильно, если вы уже не знаете, что такое продолжение).
Примечание : это очень длинный ответ с некоторыми попытками описать, что такое продолжение и почему оно полезно. В похожем на Scala псевдокоде есть несколько примеров, ни один из которых на самом деле не может быть скомпилирован и запущен (в самом конце есть только один компилируемый пример, и он ссылается на другой пример из середины ответа). Ожидайте потратить значительное количество времени, просто читая этот ответ.
Введение в продолжение
Вероятно, первое, что вы должны сделать, чтобы понять продолжение, - это забыть о том, как работают современные компиляторы для большинства императивных языков, и как работает большинство современных процессоров, и в особенности идея стека вызовов. На самом деле это детали реализации (хотя они довольно популярны и полезны на практике).
Предположим, у вас есть процессор, который может выполнять некоторую последовательность инструкций. Теперь вы хотите иметь языки высокого уровня, которые поддерживают идею методов, которые могут вызывать друг друга. Очевидная проблема, с которой вы сталкиваетесь, заключается в том, что процессору нужна некоторая последовательность команд «только вперед», но вы хотите каким-то образом «вернуть» результаты из подпрограммы вызывающей стороне. Концептуально это означает, что у вас должен быть какой-то способ сохранить где-то перед вызовом все состояние метода вызывающего, которое требуется для его продолжения после вычисления результата подпрограммы, передать его подпрограмме и затем попросите подпрограмму в конце продолжить выполнение из этого сохраненного состояния. Это сохраненное состояние является в точности продолжением. В большинстве современных сред эти продолжения хранятся в стеке вызовов, и часто существуют некоторые инструкции по сборке, специально предназначенные для облегчения их обработки (например, call и return). Но опять же, это просто детали реализации. Потенциально они могут храниться произвольным образом, и он все равно будет работать.
Итак, давайте теперь повторим эту идею: продолжение - это состояние программы в какой-то момент, которого достаточно для продолжения ее выполнения с этой точки, обычно без дополнительного ввода или небольшого известного ввода (например, возвращаемого значения вызываемый метод). Выполнение продолжения отличается от вызова метода тем, что обычно продолжение никогда явно не возвращает управление выполнением вызывающей стороне, оно может только передать его другому продолжению. Потенциально вы можете создать такое состояние самостоятельно, но на практике для того, чтобы эта функция была полезной, вам нужна некоторая поддержка со стороны компилятора, чтобы автоматически создавать продолжения или эмулировать его каким-либо другим способом (поэтому для кода Scala, который вы видите, требуется плагин компилятора) .
Асинхронные вызовы
Теперь возникает очевидный вопрос: почему продолжения вообще полезны? На самом деле есть еще несколько сценариев, кроме простого случая «возврата». Одним из таких сценариев является асинхронное программирование. На самом деле, если вы делаете какой-то асинхронный вызов и предоставляете обратный вызов для обработки результата, это можно рассматривать как передачу продолжения. К сожалению, большинство современных языков не поддерживают автоматические продолжения, поэтому вам нужно самостоятельно захватить все соответствующие состояния. Другая проблема возникает, если у вас есть какая-то логика, которая нуждается в последовательности многих асинхронных вызовов. И если некоторые из вызовов являются условными, вы легко попадете в ад обратных вызовов. Продолжения помогают вам избежать этого, позволяя создать метод с эффективно инвертированным потоком управления. При обычном вызове именно вызывающий абонент знает вызываемого и ожидает получить результат обратно синхронным способом. С помощью продолжений вы можете написать метод с несколькими «точками входа» (или «возвратом к точкам») для разных этапов логики обработки, которые вы можете просто передать другому методу, и этот метод все еще может вернуться именно к этой позиции.
Рассмотрим следующий пример (в псевдокоде, который похож на Scala, но на самом деле во многих деталях далек от реального Scala):
def someBusinessLogic() = {
val userInput = getIntFromUser()
val firstServiceRes = requestService1(userInput)
val secondServiceRes = if (firstServiceRes % 2 == 0) requestService2v1(userInput) else requestService2v2(userInput)
showToUser(combineUserInputAndResults(userInput,secondServiceRes))
}
Если все эти вызовы синхронно блокируют вызовы, этот код прост. Но предположим, что все эти get и request вызовы являются асинхронными. Как переписать код? В тот момент, когда вы помещаете логику в обратные вызовы, вы теряете ясность последовательного кода. И здесь вам могут помочь продолжения:
def someBusinessLogicCont() = {
// the method entry point
val userInput
getIntFromUserAsync(cont1, captureContinuationExpecting(entry1, userInput))
// entry/return point after user input
entry1:
val firstServiceRes
requestService1Async(userInput, captureContinuationExpecting(entry2, firstServiceRes))
// entry/return point after the first request to the service
entry2:
val secondServiceRes
if (firstServiceRes % 2 == 0) {
requestService2v1Async(userInput, captureContinuationExpecting(entry3, secondServiceRes))
// entry/return point after the second request to the service v1
entry3:
} else {
requestService2v2Async(userInput, captureContinuationExpecting(entry4, secondServiceRes))
// entry/return point after the second request to the service v2
entry4:
}
showToUser(combineUserInputAndResults(userInput, secondServiceRes))
}
Трудно уловить идею в псевдокоде. Я имею в виду, что все эти методы Async никогда не возвращаются. Единственный способ продолжить выполнение someBusinessLogicCont - это вызвать продолжение, переданное в метод «async». Вызов captureContinuationExpecting(label, variable) должен создать продолжение текущего метода на label с входным (возвращаемым) значением, связанным с variable. С такой перезаписью у вас все еще есть последовательная бизнес-логика даже со всеми этими асинхронными вызовами. Так что теперь для getIntFromUserAsync второй аргумент выглядит просто как еще один асинхронный (то есть никогда не возвращающийся) метод, который просто требует один целочисленный аргумент. Давайте назовем этот тип Continuation[T]
trait Continuation[T] {
def continue(value: T):Nothing
}
Логически Continuation[T] выглядит как функция T => Unit, а точнее T => Nothing, где Nothing, поскольку тип возвращаемого значения означает, что вызов фактически никогда не возвращается (заметьте, в реальной реализации Scala такие вызовы действительно возвращаются, поэтому нет Nothing есть, но я думаю, что концептуально легко думать о невозвратных продолжениях).
Внутренняя и внешняя итерация
Другим примером является проблема итерации. Итерация может быть внутренней или внешней. API внутренней итерации выглядит так:
trait CollectionI[T] {
def forEachInternal(handler: T => Unit): Unit
}
Внешняя итерация выглядит так:
trait Iterator[T] {
def nextValue(): Option[T]
}
trait CollectionE[T] {
def forEachExternal(): Iterator[T]
}
Примечание : часто Iterator имеет два метода, таких как hasNext и nextValue, возвращающие T, но это только усложнит историю. Здесь я использую объединенный nextValue, возвращающий Option[T], где значение None означает конец итерации, а Some(value) означает следующее значение.
Предполагая, что Collection реализован с помощью чего-то более сложного, чем массив или простой список, например, какое-то дерево, здесь существует конфликт между разработчиком API и пользователем API, если вы используете типичный императив язык. И конфликт возникает из-за простого вопроса: кто контролирует стек (то есть простое в использовании состояние программы)? Внутренняя итерация проще для разработчика, поскольку он управляет стеком и может легко хранить любое состояние, необходимое для перехода к следующему элементу, но для пользователя API все становится сложнее, если она хочет выполнить некоторую агрегацию хранимых данных, потому что теперь она должен сохранить состояние между вызовами на handler где-то. Также вам понадобятся некоторые дополнительные приемы, чтобы пользователь мог остановить итерацию в произвольном месте до конца данных (учтите, что вы пытаетесь реализовать find через forEach). И наоборот, внешняя итерация проста для пользователя: она может хранить все состояния, необходимые для обработки данных любым способом, в локальных переменных, но разработчик API теперь должен сохранять свое состояние между вызовами nextValue где-то еще. Таким образом, в основном проблема возникает потому, что существует только одно место, в котором можно легко сохранить состояние «вашей» части программы (стека вызовов) и двух конфликтующих пользователей для этого места. Было бы хорошо, если бы вы могли просто иметь два разных независимых места для состояния: одно для разработчика и другое для пользователя. И продолжения обеспечивают именно это. Идея состоит в том, что мы можем передать контроль выполнения между двумя методами назад и вперед, используя два продолжения (по одному для каждой части программы). Давайте изменим подписи на:
// internal iteration
// continuation of the iterator
type ContIterI[T] = Continuation[(ContCallerI[T], ContCallerLastI)]
// continuation of the caller
type ContCallerI[T] = Continuation[(T, ContIterI[T])]
// last continuation of the caller
type ContCallerLastI = Continuation[Unit]
// external iteration
// continuation of the iterator
type ContIterE[T] = Continuation[ContCallerE[T]]
// continuation of the caller
type ContCallerE[T] = Continuation[(Option[T], ContIterE[T])]
trait Iterator[T] {
def nextValue(cont : ContCallerE[T]): Nothing
}
trait CollectionE[T] {
def forEachExternal(): Iterator[T]
}
trait CollectionI[T] {
def forEachInternal(cont : ContCallerI[T]): Nothing
}
Здесь ContCallerI[T] type, например, означает, что это продолжение (т. Е. Состояние программы), в котором ожидаются два входных параметра: один типа T (следующий элемент) и другой типа ContIterI[T] (продолжение для переключения назад). Теперь вы можете видеть, что новые forEachInternal и новые forEachExternal + Iterator имеют почти одинаковые подписи. Единственная разница в том, как сообщается об окончании итерации: в одном случае это делается путем возврата None, а в другом - путем передачи и вызова другого продолжения (ContCallerLastI).
Вот наивная псевдокодовая реализация суммы элементов в массиве Int, использующая эти сигнатуры (вместо упрощенного примера используется массив, а не что-то более сложное):
class ArrayCollection[T](val data:T[]) : CollectionI[T] {
def forEachInternal(cont0 : ContCallerI[T], lastCont: ContCallerLastI): Nothing = {
var contCaller = cont0
for(i <- 0 to data.length) {
val contIter = captureContinuationExpecting(label, contCaller)
contCaller.continue(data(i), contIter)
label:
}
}
}
def sum(arr: ArrayCollection[Int]): Int = {
var sum = 0
val elem:Int
val iterCont:ContIterI[Int]
val contAdd0 = captureContinuationExpecting(labelAdd, elem, iterCont)
val contLast = captureContinuation(labelReturn)
arr.forEachInternal(contAdd0, contLast)
labelAdd:
sum += elem
val contAdd = captureContinuationExpecting(labelAdd, elem, iterCont)
iterCont.continue(contAdd)
// note that the code never execute this line, the only way to jump out of labelAdd is to call contLast
labelReturn:
return sum
}
Обратите внимание, как обе реализации методов forEachInternal и sum выглядят довольно последовательными.
Многозадачность
Совместная многозадачность , также известная как сопрограммы , на самом деле очень похожа на пример итераций. Совместная многозадачность - это идея, что программа может добровольно отказаться («уступить») своему управлению выполнением либо глобальному планировщику, либо другой известной сопрограмме. На самом деле последний (переписанный) пример sum можно рассматривать как две сопрограммы, работающие вместе: одна выполняет итерацию, а другая выполняет суммирование. Но в более общем случае ваш код может привести к выполнению какого-либо планировщика, который затем выберет другую подпрограмму для запуска в следующем. И то, что делает планировщик, управляет группой продолжений, решая, что продолжать дальше.
Вытесняющая многозадачность можно рассматривать как похожую вещь, но планировщик запускается при некотором аппаратном прерывании, а затем планировщику требуется способ создать продолжение программы, выполняемой непосредственно перед прерыванием извне этой программы, а не изнутри.
Примеры Scala
То, что вы видите, это действительно старая статья, которая ссылается на Scala 2.8 (в то время как текущие версии - 2.11, 2.12 и скоро 2.13). Как правильно заметил @igorpcholkin, вам нужно использовать плагин компилятора продолжений Scala и библиотеку . На странице плагина sbt для компилятора есть пример, как включить именно этот плагин (для ответа Scala 2.12 и @ igorpcholkin есть волшебные строки для Scala 2.11):
val continuationsVersion = "1.0.3"
autoCompilerPlugins := true
addCompilerPlugin("org.scala-lang.plugins" % "scala-continuations-plugin_2.12.2" % continuationsVersion)
libraryDependencies += "org.scala-lang.plugins" %% "scala-continuations-library" % continuationsVersion
scalacOptions += "-P:continuations:enable"
Проблема в том, что плагин практически заброшен и не широко используется на практике. Кроме того, синтаксис изменился со времен Scala в 2,8 раза, поэтому эти примеры сложно запустить, даже если вы исправите очевидные синтаксические ошибки, такие как отсутствие ( здесь и там. Причина этого состояния указана на GitHub как:
Вас также может заинтересовать https://github.com/scala/async,, который охватывает наиболее распространенный вариант использования плагина для продолжения.
То, что делает этот плагин, эмулирует продолжения с использованием переписывания кода (я полагаю, что действительно трудно реализовать истинные продолжения в модели исполнения JVM). И при таких переписываниях естественным представлением продолжения является некоторая функция (обычно называемая k и k1 в этих примерах).
Так что теперь, если вам удалось прочитать стену текста выше, вы, вероятно, можете правильно интерпретировать пример сэндвича. AFAIU этот пример является примером использования продолжения в качестве средства для эмуляции «возврата». Если мы уточним это более подробно, это может выглядеть так:
Вы (ваш мозг) находитесь внутри какой-то функции, которая в некоторые моменты решает, что она хочет бутерброд. К счастью, у вас есть подпрограмма, которая знает, как сделать бутерброд. Вы сохраняете свое текущее состояние мозга как продолжение в кармане и вызываете подпрограмму, говоря ей, что когда работа завершена, она должна продолжить продолжение из кармана. Затем вы делаете бутерброд в соответствии с этой подпрограммой, портящей ваше предыдущее состояние мозга. В конце подпрограммы он запускает продолжение из кармана, и вы возвращаетесь в состояние непосредственно перед вызовом подпрограммы, забывая все свое состояние во время этой подпрограммы (то есть, как вы сделали бутерброд), но вы может видеть изменения во внешнем мире, то есть то, что бутерброд сделан сейчас.
Чтобы предоставить хотя бы один компилируемый пример с текущей версией scala-continuations, вот упрощенная версия моего асинхронного примера:
case class RemoteService(private val readData: Array[Int]) {
private var readPos = -1
def asyncRead(callback: Int => Unit): Unit = {
readPos += 1
callback(readData(readPos))
}
}
def readAsyncUsage(rs1: RemoteService, rs2: RemoteService): Unit = {
import scala.util.continuations._
reset {
val read1 = shift(rs1.asyncRead)
val read2 = if (read1 % 2 == 0) shift(rs1.asyncRead) else shift(rs2.asyncRead)
println(s"read1 = $read1, read2 = $read2")
}
}
def readExample(): Unit = {
// this prints 1-42
readAsyncUsage(RemoteService(Array(1, 2)), RemoteService(Array(42)))
// this prints 2-1
readAsyncUsage(RemoteService(Array(2, 1)), RemoteService(Array(42)))
}
Здесь удаленные вызовы эмулируются (смоделированы) с фиксированными данными, представленными в массивах. Обратите внимание, что readAsyncUsage выглядит как полностью последовательный код, несмотря на нетривиальную логику того, какую удаленную службу вызывать во втором чтении, в зависимости от результата первого чтения.