Что такое продолжения Scala и зачем их использовать?

Question

Я только что закончил Программирование в Scala, и я изучал изменения между Scala 2.7 и 2.8. Наиболее важным является плагин продолжения, но я не понимаю, для чего он полезен или как он работает. Я видел, что это хорошо для асинхронного ввода-вывода, но я не смог выяснить, почему. Вот некоторые из наиболее популярных ресурсов по этому вопросу:

• Разграниченные продолжения и Scala
• Перейти в Скала
• Вкус 2,8: продолжение
• Объясненные продолжения объяснены (в Scala)

И этот вопрос о переполнении стека:

• Каковы самые большие различия между Scala 2.8 и Scala 2.7?

К сожалению, ни одна из этих ссылок не пытается определить, для чего предназначены продолжения или что должны делать функции сдвига / сброса, и я не нашел никаких ссылок, которые бы это делали. Я не смог догадаться, как работает какой-либо из примеров в связанных статьях (или что они делают), поэтому одним из способов помочь мне было бы построчно просмотреть один из этих примеров. Даже этот простой из третьей статьи:

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

Почему результат 8? Это, вероятно, поможет мне начать.

Answer 1

Мой блог объясняет, что reset а также shift сделайте, так что вы можете прочитать это снова.

Еще один хороший источник, о котором я также упоминаю в своем блоге, - это статья в Википедии о стиле прохождения продолжения. Это, безусловно, наиболее ясно по предмету, хотя он не использует синтаксис Scala, и продолжение явно передается.

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

Но я думаю, что лучшим примером концепции продолжения с разделителями является Scala Swarm. В ней библиотека останавливает выполнение вашего кода в одной точке, а оставшиеся вычисления становятся продолжением. Затем библиотека делает что-то - в этом случае, передает вычисление другому хосту и возвращает результат (значение переменной, к которой был получен доступ) вычислению, которое было остановлено.

Теперь вы не понимаете даже простой пример на странице Scala, так что читайте мой блог. В нем я имею дело только с объяснением этих основ, почему результат 8,

Answer 2

Я обнаружил, что существующие объяснения менее эффективны в объяснении концепции, чем я хотел бы надеяться. Надеюсь, это ясно (и правильно). Я еще не использовал продолжения.

Когда функция продолжения cf называется:

1. Выполнение пропускает остальную часть shift блок и начинается снова в конце
   • параметр передан cf это то, что shift блок "оценивает", поскольку выполнение продолжается. это может быть разным для каждого звонка cf
2. Казнь продолжается до конца reset блокировать (или до вызова reset если нет блока)
   • результат reset блок (или параметр для reset() если нет блока) это то, что cf возвращается
3. Выполнение продолжается после cf до конца shift блок
4. Выполнение пропускается до конца reset блок (или вызов для сброса?)

Так что в этом примере следуйте буквам от А до Я

reset {
  // A
  shift { cf: (Int=>Int) =>
    // B
    val eleven = cf(10)
    // E
    println(eleven)
    val oneHundredOne = cf(100)
    // H
    println(oneHundredOne)
    oneHundredOne
  }
  // C execution continues here with the 10 as the context
  // F execution continues here with 100
  + 1
  // D 10.+(1) has been executed - 11 is returned from cf which gets assigned to eleven
  // G 100.+(1) has been executed and 101 is returned and assigned to oneHundredOne
}
// I

Это печатает:

11
101

Answer 3

Учитывая канонический пример из исследовательской работы для продолжения Scala с разделителями, он был немного изменен, поэтому вход функции shift дано имя f и, таким образом, больше не является анонимным.

def f(k: Int => Int): Int = k(k(k(7)))
reset(
  shift(f) + 1   // replace from here down with `f(k)` and move to `k`
) * 2

Плагин Scala преобразует этот пример так, что вычисление (в пределах входного аргумента reset) начиная с каждого shift к вызову reset заменяется на функцию (например, f) вход в shift,

Замененное вычисление смещается (т.е. перемещается) в функцию k, Функция f вводит функцию k, где k содержит замененные вычисления, k входные x: Intи вычисление в k заменяет shift(f) с x,

f(k) * 2
def k(x: Int): Int = x + 1

Который имеет тот же эффект, что и:

k(k(k(7))) * 2
def k(x: Int): Int = x + 1

Обратите внимание на тип Int входного параметра x (т.е. подпись типа k) был задан сигнатурой типа входного параметра f,

Еще один заимствованный пример с концептуально эквивалентной абстракцией, т.е. read является функцией входа в shift:

def read(callback: Byte => Unit): Unit = myCallback = callback
reset {
  val byte = "byte"

  val byte1 = shift(read)   // replace from here with `read(callback)` and move to `callback`
  println(byte + "1 = " + byte1)
  val byte2 = shift(read)   // replace from here with `read(callback)` and move to `callback`
  println(byte + "2 = " + byte2)
}

Я считаю, что это будет переведено в логический эквивалент:

val byte = "byte"

read(callback)
def callback(x: Byte): Unit {
  val byte1 = x
  println(byte + "1 = " + byte1)
  read(callback2)
  def callback2(x: Byte): Unit {
    val byte2 = x
    println(byte + "2 = " + byte1)
  }
}

Я надеюсь, что это объясняет общую последовательную абстракцию, которая была несколько омрачена предварительным представлением этих двух примеров. Например, канонический первый пример был представлен в исследовательской работе как анонимная функция, а не по имени fтаким образом, некоторые читатели не сразу поняли, что это абстрактно аналогично read во втором заимствованном примере.

Разграниченные таким образом продолжения создают иллюзию инверсии контроля со стороны "ты называешь меня извне reset"чтобы" я звоню тебе внутри reset".

Обратите внимание на тип возврата f есть, но k не требуется, должен совпадать с типом возврата resetт.е. f имеет свободу объявлять любой тип возвращаемого значения для k пока f возвращает тот же тип, что и reset, То же самое для read а также capture (смотрите также ENV ниже).

---

Продолжения с разделителями не косвенно инвертируют контроль состояния, например read а также callback не являются чистыми функциями. Таким образом, вызывающая сторона не может создавать ссылочно-прозрачные выражения и, следовательно, не имеет декларативного (или прозрачного) контроля над предполагаемой императивной семантикой.

Мы можем явно получить чистые функции с продолжениями с разделителями.

def aread(env: ENV): Tuple2[Byte,ENV] {
  def read(callback: Tuple2[Byte,ENV] => ENV): ENV = env.myCallback(callback)
  shift(read)
}
def pure(val env: ENV): ENV {
  reset {
    val (byte1, env) = aread(env)
    val env = env.println("byte1 = " + byte1)
    val (byte2, env) = aread(env)
    val env = env.println("byte2 = " + byte2)
  }
}

Я считаю, что это будет переведено в логический эквивалент:

def read(callback: Tuple2[Byte,ENV] => ENV, env: ENV): ENV =
  env.myCallback(callback)
def pure(val env: ENV): ENV {
  read(callback,env)
  def callback(x: Tuple2[Byte,ENV]): ENV {
    val (byte1, env) = x
    val env = env.println("byte1 = " + byte1)
    read(callback2,env)
    def callback2(x: Tuple2[Byte,ENV]): ENV {
      val (byte2, env) = x
      val env = env.println("byte2 = " + byte2)
    }
  }
}

Это становится шумно из-за явного окружения.

Тангенциально отметим, что у Scala нет глобального вывода типов из Haskell, и поэтому, насколько мне известно, не может поддерживать неявное поднятие монады государства. unit (как одна из возможных стратегий сокрытия явной среды), поскольку глобальный вывод типа Хескли (Хиндли-Милнера) зависит от того, не поддерживает ли множественное виртуальное наследование алмазов.

Answer 4

Продолжение фиксирует состояние вычислений, которое будет вызвано позже.

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

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

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

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

Отказ от ответственности: у меня нет глубокого понимания продолжений в Scala, я просто сделал вывод, что смотрю на примеры и знаю продолжения из Схемы.

Answer 5

С моей точки зрения, лучшее объяснение было дано здесь: http://jim-mcbeath.blogspot.ru/2010/08/delimited-continuations.html

Один из примеров:

Чтобы увидеть поток управления немного яснее, вы можете выполнить этот фрагмент кода:

reset {
    println("A")
    shift { k1: (Unit=>Unit) =>
        println("B")
        k1()
        println("C")
    }
    println("D")
    shift { k2: (Unit=>Unit) =>
        println("E")
        k2()
        println("F")
    }
    println("G")
}

Вот вывод, который производит приведенный выше код:

A
B
D
E
G
F
C

Answer 6

Продолжение Scala через содержательные примеры

Определим from0to10 который выражает идею итерации от 0 до 10:

def from0to10() = shift { (cont: Int => Unit) =>
   for ( i <- 0 to 10 ) {
     cont(i)
   }
}

Сейчас же,

reset {
  val x = from0to10()
  print(s"$x ")
}
println()

печатает:

0 1 2 3 4 5 6 7 8 9 10 

На самом деле нам не нужно x:

reset {
  print(s"${from0to10()} ")
}
println()

выводит тот же результат.

А также

reset {
  print(s"(${from0to10()},${from0to10()}) ")
}
println()

печатает все пары:

(0,0) (0,1) (0,2) (0,3) (0,4) (0,5) (0,6) (0,7) (0,8) (0,9) (0,10) (1,0) (1,1) (1,2) (1,3) (1,4) (1,5) (1,6) (1,7) (1,8) (1,9) (1,10) (2,0) (2,1) (2,2) (2,3) (2,4) (2,5) (2,6) (2,7) (2,8) (2,9) (2,10) (3,0) (3,1) (3,2) (3,3) (3,4) (3,5) (3,6) (3,7) (3,8) (3,9) (3,10) (4,0) (4,1) (4,2) (4,3) (4,4) (4,5) (4,6) (4,7) (4,8) (4,9) (4,10) (5,0) (5,1) (5,2) (5,3) (5,4) (5,5) (5,6) (5,7) (5,8) (5,9) (5,10) (6,0) (6,1) (6,2) (6,3) (6,4) (6,5) (6,6) (6,7) (6,8) (6,9) (6,10) (7,0) (7,1) (7,2) (7,3) (7,4) (7,5) (7,6) (7,7) (7,8) (7,9) (7,10) (8,0) (8,1) (8,2) (8,3) (8,4) (8,5) (8,6) (8,7) (8,8) (8,9) (8,10) (9,0) (9,1) (9,2) (9,3) (9,4) (9,5) (9,6) (9,7) (9,8) (9,9) (9,10) (10,0) (10,1) (10,2) (10,3) (10,4) (10,5) (10,6) (10,7) (10,8) (10,9) (10,10) 

Как же это работает?

Есть названный код,from0to10, и телефонный код. В данном случае это блок, следующий заreset. Один из параметров, переданных в вызываемый код, - это адрес возврата, который показывает, какая часть вызывающего кода еще не была выполнена (**). Эта часть вызывающего кода является продолжением. Вызываемый код может делать с этим параметром все, что решит: передавать ему управление, игнорировать или вызывать его несколько раз. Вотfrom0to10 вызывает это продолжение для каждого целого числа в диапазоне 0..10.

def from0to10() = shift { (cont: Int => Unit) =>
   for ( i <- 0 to 10 ) {
     cont(i) // call the continuation
   }
}

Но где кончается продолжение? Это важно, потому что последнийreturn из продолжения возвращает управление вызываемому коду, from0to10. В Scala он заканчивается там, гдеreset блок заканчивается (*).

Теперь мы видим, что продолжение объявлено как cont: Int => Unit. Зачем? Мы призываемfrom0to10 в качестве val x = from0to10(), а также Int это тип значения, которое переходит в x. Unit означает, что блок после resetне должен возвращать никакого значения (иначе будет ошибка типа). В общем, существует 4 типа сигнатуры: ввод функции, ввод продолжения, результат продолжения, результат функции. Все четыре должны соответствовать контексту вызова.

Выше мы напечатали пары значений. Распечатаем таблицу умножения. Но как мы выводим\n после каждой строки?

Функция back позволяет нам указать, что нужно сделать, когда управление вернется, от продолжения до кода, который его вызвал.

def back(action: => Unit) = shift { (cont: Unit => Unit) =>
  cont()
  action
}

backсначала вызывает его продолжение, а затем выполняет действие.

reset {
  val i = from0to10()
  back { println() }
  val j = from0to10
  print(f"${i*j}%4d ") // printf-like formatted i*j
}

Он печатает:

   0    0    0    0    0    0    0    0    0    0    0 
   0    1    2    3    4    5    6    7    8    9   10 
   0    2    4    6    8   10   12   14   16   18   20 
   0    3    6    9   12   15   18   21   24   27   30 
   0    4    8   12   16   20   24   28   32   36   40 
   0    5   10   15   20   25   30   35   40   45   50 
   0    6   12   18   24   30   36   42   48   54   60 
   0    7   14   21   28   35   42   49   56   63   70 
   0    8   16   24   32   40   48   56   64   72   80 
   0    9   18   27   36   45   54   63   72   81   90 
   0   10   20   30   40   50   60   70   80   90  100 

Что ж, теперь пришло время для головоломок. Есть два вызоваfrom0to10. Какое продолжение для первогоfrom0to10? Это следует за призывомfrom0to10в двоичном коде, но в исходном коде он также включает оператор присваиванияval i =. Это заканчивается там, гдеreset блок заканчивается, но конец reset блок не возвращает управление первому from0to10. Конецreset блок возвращает управление 2-му from0to10, что, в свою очередь, возвращает управление back, и это back который возвращает управление первому вызову from0to10. Когда первый (да! 1-й!)from0to10 выходы, весь reset блок закрыт.

Такой метод возврата управления называется backtrack ing, это очень старый метод, известный по крайней мере со времен Prolog и AI-ориентированных производных Lisp.

Имена reset а также shiftнеправильные названия. Эти имена лучше оставить для побитовых операций.reset определяет границы продолжения, и shift берет продолжение из стека вызовов.

Примечания)

(*) В Scala продолжение заканчивается там, гдеresetблок заканчивается. Другой возможный подход - позволить ей заканчиваться там, где заканчивается функция.

(**) Одним из параметров вызываемого кода является адрес возврата, показывающий, какая часть вызывающего кода еще не была выполнена. Что ж, в Scala для этого используется последовательность адресов возврата. Как много? Все адреса возврата, помещенные в стек вызовов с момента входа вreset блок.

---

UPD Part 2Отбрасывание продолжений: фильтрация

def onEven(x:Int) = shift { (cont: Unit => Unit) =>
  if ((x&1)==0) {
    cont() // call continuation only for even numbers
  }
}
reset {
  back { println() }
  val x = from0to10()
  onEven(x)
  print(s"$x ")
}

Это печатает:

0 2 4 6 8 10 

Выделим две важные операции: отбрасывание продолжения (fail()) и передать ему управление (succ()):

// fail: just discard the continuation, force control to return back
def fail() = shift { (cont: Unit => Unit) => }
// succ: does nothing (well, passes control to the continuation), but has a funny signature
def succ():Unit @cpsParam[Unit,Unit] = { }
// def succ() = shift { (cont: Unit => Unit) => cont() }

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

reset {
  back { println() }
  val x = from0to10()
  if ((x&1)==0) {
    succ()
  } else {
    fail()
  }
  print(s"$x ")
}

как и ожидалось, он печатает

0 2 4 6 8 10

Внутри функции succ() не обязательно:

def onTrue(b:Boolean) = {
  if(!b) {
    fail()
  }
}
reset {
  back { println() }
  val x = from0to10()
  onTrue ((x&1)==0)
  print(s"$x ")
}

снова он печатает

0 2 4 6 8 10

Теперь определим onOdd() через onEven():

// negation: the hard way
class ControlTransferException extends Exception {}
def onOdd(x:Int) = shift { (cont: Unit => Unit) =>
  try {
    reset {
      onEven(x)
      throw new ControlTransferException() // return is not allowed here
    }
    cont()
  } catch {
    case e: ControlTransferException =>
    case t: Throwable => throw t
  }
}
reset {
  back { println() }
  val x = from0to10()
  onOdd(x)
  print(s"$x ")
}

Выше, если xчетное, генерируется исключение и продолжение не вызывается; еслиxявляется нечетным, исключение не генерируется и вызывается продолжение. Приведенный выше код печатает:

1 3 5 7 9 

Answer 7

Еще одна (более поздняя - май 2016 г.) статья о продолжении Scala:
" Путешествие во времени в Скале: CPS в Скале (продолжение Скалы)" Шиванш Сривастава (shiv4nsh )
Это также относится к статье Джима МакБита, упомянутой в ответе Dmitry Bespalov.

Но перед этим он описывает продолжение так:

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

Чтобы объяснить это далее, у нас может быть один из самых классических примеров,

Скажем, вы на кухне перед холодильником и думаете о сэндвиче. Вы берете продолжение прямо здесь и суете его в карман.
Затем вы достаете немного индейки и хлеба из холодильника и делаете себе бутерброд, который сейчас стоит на прилавке.
Вы вызываете продолжение в своем кармане, и вы снова стоите перед холодильником, думая о бутерброде. Но, к счастью, на прилавке есть бутерброд, и все материалы, использованные для его приготовления, исчезли. Так ты ешь это.:-)

В этом описании sandwich является частью данных программы (например, объект в куче), и вместо вызова "make sandwich"Рутина, а затем возвращаясь, человек назвал"make sandwich with current continuation”Подпрограмма, которая создает бутерброд и затем продолжается там, где остановилось выполнение.

При этом, как было объявлено в апреле 2014 года для Scala 2.11.0-RC1

Мы ищем сопровождающих, чтобы взять на себя следующие модули: scala-swing, scala-продолжений.
2.12 не будет включать их, если новый сопровождающий не найден.
Скорее всего, мы продолжим поддерживать другие модули (scala-xml, scala-parser-combinators), но помощь по-прежнему высоко ценится.