Из Википедии, свободной энциклопедии
Перейти к навигации Перейти к поиску

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

История [ править ]

Разграниченные продолжения были впервые введены Фелляйзеном в 1988 году [1] с оператором под названием , впервые представленным в техническом отчете в 1987 году [2] вместе с конструкцией подсказки . Оператор был разработан , чтобы быть обобщением операторов управления , которые были описаны в литературе , такой как от схемы , ISWIM «ы оператора J , John C. Рейнольдса » оператора, и другие. Впоследствии, многие конкурирующие разделителями операторы управления были изобретены языков программирования научно - исследовательского сообщества , таких , как и , [4] и , [5] , [6]call/ccescapepromptcontrol shiftreset cupto fcontrol, и другие.

Примеры [ править ]

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

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

( * 2  ( сброс  ( + 1  ( сдвиг  k  ( k  5 )))))

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

( * 2  ( + 1  5 ))

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

 ( сброс  ( * 2  ( сдвиг  k  ПАРОЛЬ )))

всякий раз , когда CODEвызывающие (k N), (* 2 N)вычисляются и возвращаются.

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

 ( пусть (( k  ( lambda ( x )  ( * 2  x ))))  КОД )

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

 ( сброс  ( * 2  ( сдвиг  k  ( k  ( k  4 )))))

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

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

 ( + 1  ( сброс  ( * 2  ( сдвиг  k  ( k  ( k  4 ))))))

Разграниченные продолжения были впервые независимо описаны Felleisen et al. [9] и Джонсон. [10] С тех пор они использовались во многих областях, особенно при определении новых управляющих операторов ; см. обзор Кейннека [11] .

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

 ( reset  ( begin  ( shift  k  ( cons 1  ( k  ( void ))))  ;; (1)  null ))

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

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

 ( reset  ( begin  ( shift  k  ( cons 1  ( k  ( void ))))  ( shift  k  ( cons 2  ( k  ( void ))))  null ))

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

 ( сброс  ( начало  ( сдвиг  k  ( cons 1  ( k  ( void ))))  ( список 2 )))

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

yieldИспользуя этот трюк, мы можем определить :

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

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

 ( reset  ( begin  ( yield  1 )  ( yield  2 )  ( yield  3 )  null ))  ;; (список 1 2 3)

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

 ( определить ( поток-yield  x )  ( сдвиг  k  ( поток-cons  x  ( k  ( void ))))) ( определить lazy-example  ( reset  ( begin  ( stream-yield  1 )  ( stream-yield  2 )  ( stream-yield  3 )  stream-null )))

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

 ( определить ( список-> поток  xs )  ( сбросить  ( начало  ( для каждого потока-yield  xs )  stream-null )))

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

 ( define ( for-each-> stream-maker  for-each )  ( lambda ( collection )  ( reset  ( begin  ( for-each ( lambda ( element )  ( shift  k  ( stream-cons  element  ( k  'ignored ))))  коллекция )  stream-null ))))

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

Ограниченные продолжения также полезны в лингвистике : подробности см. В разделе « Продолжения в лингвистике» .

Ссылки [ править ]

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

Внешние ссылки [ править ]

  • Учебник по составным продолжениям на SchemeWiki
  • Разграниченные продолжения в операционных системах, Олег Киселев и Чун-чжи Шан
  • Нативные разграниченные продолжения в (байт-код и машинный код) OCaml
  • Shift / сброса для самых маленьких (на русском языке )
  • Несколько хороших статей о продолжениях с разделителями и первоклассных макросах