Продолжение с разделителями - Delimited continuation

В языки программирования, а продолжение с разделителями, составное продолжение или же частичное продолжение, является "кусочком" продолжение Рамка это было овеществленный в функция. В отличие от обычных продолжений, разграниченные продолжения возвращаться значение, и, таким образом, может быть повторно использовано и составлен. Управляющие ограничители, основа ограниченных продолжений, были введены Маттиас Фелляйзен в 1988 г.[1] хотя ранние намеки на составные и разграниченные продолжения можно найти в Кэролайн Талкотт в Стэнфордской диссертации 1984 г., в статье Феллейзена и Фридмана о PARL 1987 г.,[2] и диссертация Феллейзена 1987 года.[3]

История

Разграниченные продолжения были впервые введены Фелляйзеном в 1988 году.[1] с оператором, называемым , впервые представленный в техническом отчете в 1987 году,[2] вместе с быстрой конструкцией . Оператор был разработан как обобщение операторов управления, которые были описаны в литературе, например вызов / cc из Схема, Я ПЛАВАЮ с Оператор J, Джон С. Рейнольдс ' побег оператор и другие. Впоследствии многие конкурирующие операторы управления с разделителями были изобретены сообществом исследователей языков программирования, таким как Подсказка и контроль,[4] сдвиг и перезагрузить,[5] чашка,[6] fcontrol, и другие.

Примеры

В исследовательской литературе предлагались различные операторы для ограниченных продолжений.[7]

Одно предложение[5] предлагает два оператора управления: сдвиг и перезагрузить. В перезагрузить оператор устанавливает предел для продолжения, в то время как сдвиг оператор захватывает или перерабатывает текущее продолжение до самого внутреннего включающего перезагрузить. Например, рассмотрим следующий фрагмент в Схема:

(* 2 (перезагрузить (+ 1 (сдвиг k (k 5)))))

В перезагрузить ограничивает продолжение, которое сдвиг захватывает (названо k в этом примере). Когда этот фрагмент выполняется, использование сдвиг свяжет k к продолжению (+ 1 []) куда [] представляет собой часть вычисления, которая должна быть заполнена значением. Это продолжение напрямую соответствует коду, который окружает сдвиг вверх к перезагрузить. Поскольку тело сдвига (т. Е. (к 5)) немедленно вызывает продолжение, этот код эквивалентен следующему:

(* 2 (+ 1 5))

В общем, эти операторы могут кодировать более интересное поведение, например, возвращая захваченное продолжение. k как значение или вызывая k многократно. В сдвиг оператор передает захваченное продолжение k к коду в своем теле, который может либо вызывать его, либо создавать в результате, либо полностью игнорировать. Какой бы результат сдвиг производит для самых сокровенных перезагрузить, отбрасывая продолжение между перезагрузить и сдвиг. Однако, если продолжение вызывается, оно эффективно переустанавливает продолжение после возврата к перезагрузить. Когда все вычисления внутри перезагрузить завершается, результат возвращается продолжением с разделителями.[8] Например, в этом Схема код:

 (перезагрузить (* 2 (сдвиг k КОД)))

в любое время КОД призывает (к Н), (* 2 Н) оценивается и возвращается.

Это эквивалентно следующему:

  (позволять ((k (лямбда (Икс) (* 2 Икс)))) КОД)

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

 (перезагрузить (* 2 (сдвиг k (k (k 4)))))

призывает (к 4) сначала (который возвращает 8), а затем (к 8) (что возвращает 16). На данный момент сдвиг выражение прекратилось, а остальная часть перезагрузить выражение отбрасывается. Следовательно, итоговый результат - 16.

Все, что происходит за пределами перезагрузить выражение скрыто, т.е. на него не влияет передача управления. Например, это возвращает 17:

 (+ 1 (перезагрузить (* 2 (сдвиг k (k (k 4))))))

Разграниченные продолжения были впервые описаны независимо Фелляйзеном. и другие.[9] и Джонсон.[10] С тех пор они использовались во многих областях, особенно при определении новых операторы управления; см. Queinnec[11] для опроса.

Давайте посмотрим на более сложный пример. Позволять ноль быть пустым списком:

 (перезагрузить   (начинать     (сдвиг k (минусы 1 (k (пустота)))) ;; (1)     ноль))

Контекст, захваченный сдвиг является (begin [*] null), куда [*] это дыра, где kбудет введен параметр. Первый звонок k внутри сдвиг оценивает этот контекст с помощью (пустота) = # заменяя отверстие, поэтому значение (k (недействительно)) является (начало # null) = ноль. Тело сдвиг, а именно (минусы 1 ноль) = (1), становится общей стоимостью перезагрузить выражение в качестве окончательного результата.

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

 (перезагрузить   (начинать     (сдвиг k (минусы 1 (k (пустота))))     (сдвиг k (минусы 2 (k (пустота))))     ноль))

Если мы закомментируем первый сдвиг, мы уже знаем результат, это (2); так что мы можем также переписать выражение следующим образом:

 (перезагрузить   (начинать     (сдвиг k (минусы 1 (k (пустота))))     (список 2)))

Это довольно знакомо, и его можно переписать как (минусы 1 (список 2)), то есть, (список 1 2).

Мы можем определить урожай используя этот трюк:

(определить (yield x) (shift k (cons x (k (void)))))

и использовать его при построении списков:

 (перезагрузить (начинать          (урожай 1)          (урожай 2)          (урожай 3)          ноль))    ;; (список 1 2 3)

Если мы заменим минусы с минусы потока, мы можем создавать ленивые потоки:

  (определять (ручей-урожай Икс) (сдвиг k (минусы потока Икс (k (пустота)))))  (определять ленивый пример    (перезагрузить (начинать            (ручей-урожай 1)            (ручей-урожай 2)            (ручей-урожай 3)            stream-null)))

Мы можем обобщить это и преобразовать списки в поток одним махом:

 (определять (список-> поток хз)   (перезагрузить (начинать            (для каждого ручей-урожай хз)            stream-null)))

В более сложном примере ниже продолжение можно безопасно обернуть в тело лямбды и использовать как таковое:

 (определять (для каждого-> стрим-мейкер для каждого)    (лямбда (коллекция)      (перезагрузить (начинать               (для каждого (лямбда (элемент)                           (сдвиг k                             (минусы потока элемент (k игнорируется))))                         коллекция)               stream-null))))

Часть между перезагрузить и сдвиг включает функции управления, такие как лямбда и для каждого; это невозможно перефразировать, используя лямбды[Почему? ].

Продолжения с разделителями также полезны в лингвистика: видеть Продолжение в лингвистике для подробностей.

Рекомендации

  1. ^ а б Маттиас Фелляйзен (1988). «Теория и практика первоклассных подсказок». Принципы языков программирования: 180–190. Дои:10.1145/73560.73576. ISBN  0-89791-252-7.
  2. ^ а б Felleisen; Фридман; Дуба; Меррилл (1987). Помимо продолжений (Технический отчет). Университет Индианы. 87-216.
  3. ^ Маттиас Фелляйзен (1987). Вычисления преобразования лямбда-v-CS: синтаксическая теория управления и состояния в императивных языках программирования высшего порядка (PDF) (Тезис).
  4. ^ Ситарам, Дораи; Фелляйзен, Маттиас (1990). «Контрольные ограничители и их иерархии» (PDF). Лисп и символьные вычисления.
  5. ^ а б Оливье Данви; Анджей Филински (1990). «Абстрагирование управления». LISP и функциональное программирование: 151–160. Дои:10.1145/91556.91622. ISBN  0-89791-368-X.
  6. ^ Гюнтер; Реми; Рике (1995). «Обобщение исключений и контроля в языках, подобных ML». Функциональные языки программирования и компьютерная архитектура.
  7. ^ См., Например, операторов, предлагаемых ракетка / контроль Ракетка библиотека [1]; следующие примеры можно запустить в Racket, используя (требуется ракетка / контроль)
  8. ^ Гасбихлер, Мартин; Спербер, Майкл (2002). «Последняя смена для вызова / cc: прямая реализация сдвига и сброса». CiteSeerX  10.1.1.11.3425. Цитировать журнал требует | журнал = (помощь)
  9. ^ Фелляйзен, Матиас; Friedman, Daniel P .; Дуба, Брюс; Маррилл, Джон (февраль 1987). "За гранью продолжений" (PDF). Технический отчет 216. Департамент компьютерных наук, Университет Индианы. Цитировать журнал требует | журнал = (помощь)
  10. ^ Джонсон, Грегори Ф. (июнь 1987 г.). «GL: денотационный стенд с продолжениями и частичными продолжениями». Proc. Симпозиум SIGPLAN '87 по устным и устным переводам. С. 218–225.
  11. ^ Кейннек, Кристиан (апрель 1994 г.). «Библиотека операторов управления высокого уровня». École Polytechnique и INRIA -Rocquencourt. CiteSeerX  10.1.1.29.4790. Цитировать журнал требует | журнал = (помощь)

внешняя ссылка