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

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

• Разграниченные продолжения и Scala
• Goto в 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? Это, вероятно, поможет мне начать работу.

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

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

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

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

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

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

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

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

Итак, в этом примере следуйте буквам от A до Z

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

Учитывая канонический пример из исследовательской статьи для ограниченных продолжений 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».

Обратите внимание, что тип возвращаемого значения fis, но 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(как одну из возможных стратегий для скрытия явного окружения), потому что вывод глобального типа Haskell (Hindley-Milner) зависит от того, что не поддерживается алмазное множественное виртуальное наследование .

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

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

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

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

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

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

С моей точки зрения, лучшее объяснение было дано здесь: 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

Другая (более свежая - май 2016 г.) статья о продолжениях Scala:
« Путешествие во времени в Scala: CPS в Scala (продолжение scala) » Шиванша Шриваставы ( shiv4nsh) .
Это также относится к Jim McBeath «s статье упоминается в Дмитрий Беспалов » s ответ .

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

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

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

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

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

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

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

Продолжение 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. Зачем? Мы вызываем from0to10as 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блок выходит.

Такой метод возврата управления называется backtracking , это очень старая техника, известная по крайней мере со времен 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