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

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

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

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

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

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

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

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

1. Execution skips over the rest of the shift block and begins again at the end of it
   • the parameter passed to cf is what the shift block "evaluates" to as execution continues. this can be different for every call to cf
2. Execution continues until the end of the reset block (or until a call to reset if there is no block)
   • the result of the reset block (or the parameter to reset() if there is no block) is what cf returns
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».

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

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

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

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

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

В этом описании 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), но помощь по-прежнему приветствуется.