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