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

Question

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

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

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

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

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

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

Answer 4

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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