Продолжение - Continuation

эта статья нужны дополнительные цитаты для проверка. Пожалуйста помоги улучшить эту статью от добавление цитат в надежные источники. Материал, не полученный от источника, может быть оспорен и удален. Найдите источники: «Продолжение»  – Новости  · газеты  · книги  · ученый  · JSTOR (Июль 2010 г.) (Узнайте, как и когда удалить этот шаблон сообщения)

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

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

История

Самое раннее описание продолжений было сделано Адриан ван Вейнгаарден в сентябре 1964 г. Вейнгаарден выступал на Рабочей конференции IFIP по языкам формального описания языков, проходившей в Баден-бай-Вена, Австрия. В составе рецептуры Алгол 60 препроцессор, он призвал преобразовать правильные процедуры в стиль передачи,^[1] хотя он не использовал это имя, и его намерением было упростить программу и тем самым сделать ее результат более понятным.

Кристофер Стрейчи, Кристофер П. Уодсворт и Джон С. Рейнольдс принес срок продолжение в своей работе в области денотационная семантика который широко использует продолжения, чтобы позволить анализировать последовательные программы с точки зрения функциональное программирование семантика.^[1]

Стив Рассел^[2] придумал продолжение в своем втором Лисп реализация для IBM 704, хотя он и не назвал его.^[3]

Рейнольдс (1993) дает полную историю открытия продолжений.

Первоклассные продолжения

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

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

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

Схема была первая полноценная производственная система (1969-1970), обеспечивающая первый «улов»^[1] а потом вызов / cc. Брюс Дуба представил call / cc в SML.

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

Функциональные программисты, пишущие свои программы на стиль передачи получить выразительную способность манипулировать потоком управления произвольными способами. Цена состоит в том, что они должны поддерживать инварианты управления и продолжения вручную, что может быть очень сложной задачей (но см. «Стиль передачи продолжения» ниже).

Использует

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

Более сложные конструкции, для которых "продолжения дают элегантное описание"^[1] тоже существуют. Например, в C, longjmp можно использовать для прыжка с середины одного функция к другому, при условии, что вторая функция лежит глубже в стеке (если она ожидает возврата первой функции, возможно, среди прочего). Другие более сложные примеры включают сопрограммы в Симула 67, Lua, и Perl; тасклеты в Безстековый Python; генераторы в Икона и Python; продолжение в Scala (начиная с версии 2.8); волокна в Рубин (начиная с 1.9.1); то возврат механизм в Пролог; монады в функциональное программирование; и потоки.

Примеры

В Схема язык программирования включает оператор управления вызов с текущим продолжением (сокращенно: call / cc), с помощью которого программа Scheme может управлять потоком управления:

 (определять продолжение #f) (определять (тест)   (позволять ((я 0))     ; call / cc вызывает свой первый аргумент функции, передавая     ; переменная продолжения, представляющая эту точку в     ; программа в качестве аргумента этой функции.     ;     ; В этом случае аргумент функции указывает, что     ; continue к переменной the-continue.     ;     (вызов / cc (лямбда (k) (набор! продолжение k)))     ;     ; В следующий раз, когда будет вызвано продолжение, мы начнем здесь.     (набор! я (+ я 1))     я))

Определяет функцию тест это устанавливает продолжение к будущему состоянию исполнения самого себя:

 > (тест) 1 > (продолжение) 2 > (продолжение) 3 > ; сохраняет текущее продолжение (которое будет печатать 4 следующих) > (определять еще одно продолжение продолжение) > (тест) ; сбрасывает продолжение 1 > (продолжение) 2 > (еще одно продолжение) ; использует ранее сохраненное продолжение 4

Для более мягкого введения в этот механизм см. вызов с текущим продолжением.

Сопрограммы

В этом примере показано возможное использование продолжений для реализации сопрограммы как отдельные потоки.^[5]

 ;;; Наивная очередь для планирования потоков. ;;; Он содержит список продолжений, «ожидающих запуска».   (определять *очередь* '())   (определять (пустая очередь?)     (ноль? *очередь*))   (определять (ставить в очередь Икс)     (набор! *очередь* (добавить *очередь* (список Икс))))   (определять (исключать из очереди)     (позволять ((Икс (машина *очередь*)))       (набор! *очередь* (CDR *очередь*))       Икс))   ;;; Это запускает новый поток (процесс).   (определять (вилка proc)     (вызов / cc      (лямбда (k)        (ставить в очередь k)        (proc))))   ;;; Это передает процессор другому потоку, если он есть.   (определять (Уступать)     (вызов / cc      (лямбда (k)        (ставить в очередь k)        ((исключать из очереди)))))   ;;; Это завершает текущий поток или всю программу   ;;; если не осталось других нитей.   (определять (нить-выход)     (если (пустая очередь?)         (выход)         ((исключать из очереди))))

Определенные выше функции позволяют определять и выполнять потоки через совместная многозадачность, т.е. потоки, которые передают управление следующему в очереди:

   ;;; Тело некоторого типичного потока схемы, который выполняет что-то:   (определять (делать вещи и печатать ул)     (лямбда ()       (позволять петля ((п 0))         (формат #t "~ А ~ А  п" ул п)         (Уступать)         (петля (+ п 1)))))   ;;; Создайте два потока и запустите их.   (вилка (делать вещи и печатать "Это ААА"))   (вилка (делать вещи и печатать "Привет от BBB"))   (нить-выход)

Предыдущий код выдаст такой результат:

 Это AAA 0 Привет от BBB 0 Это AAA 1 Привет от BBB 1 Это AAA 2 Привет от BBB 2 ...

Выполнение

Программа должна выделять место в памяти для переменных, используемых ее функциями. Большинство языков программирования используют стек вызовов для хранения необходимых переменных, поскольку он позволяет быстро и просто выделять и автоматически освобождать память. Другие языки программирования используют куча для этого, что обеспечивает гибкость при более высоких затратах на выделение и освобождение памяти. Обе эти реализации имеют преимущества и недостатки в контексте продолжений.^[6]

Поддержка языков программирования

Многие языки программирования демонстрируют первоклассные продолжения под разными именами; конкретно:

• Common Lisp: cl-cont. Также можно использовать собственные макросы
• C # / VB.NET: асинхронный и Ждите: "зарегистрируйте остальную часть метода в качестве продолжения, а затем немедленно вернитесь к вызывающей стороне; задача вызовет продолжение, когда оно завершится." Асинхронное программирование для C #
• Фактор: callcc0 и callcc1
• Haskell: Продолжение монада в Control.Monad.Cont
• Haxe: продолжение
• Икона, Юникон  : создать, приостановить, @ оператор: совместные выражения
• Ява: Lightwolf javaflow (требует манипуляции с байт-кодом во время выполнения или компиляции)
• Котлин  : Продолжение
• JavaScript Rhino  : Продолжение
• Попугай: Продолжение ЧВК; использует стиль передачи для всего потока управления
• Perl: Коро и Непрерывность
• Пико: вызов (exp ()) и continue (aContinuation, anyValue)
• Python: PyPy с _continuation.continulet
• Ракетка: вызов с текущим продолжением (обычно сокращается до вызов / cc)
• Рубин: callcc
• Scala: scala.util.continuations обеспечивает сдвиг/перезагрузить
• Схема: вызов с текущим продолжением (обычно сокращается до вызов / cc)
• Болтовня: Продолжение текущего; в большинстве современных сред Smalltalk продолжение можно реализовать без дополнительной поддержки виртуальных машин.
• Стандартный ML Нью-Джерси: SMLofNJ.Cont.callcc
• Unlambda: c, операция управления потоком для вызова с текущим продолжением

На любом языке, поддерживающем закрытие и правильные хвостовые сигналы, можно писать программы на стиль передачи и вручную реализовать call / cc. (В стиле продолжения передачи call / cc становится простой функцией, которую можно написать с помощью лямбда.) Это особенно распространенная стратегия в Haskell, где легко построить "продолжение-переход монада "(например, Cont монада и ContT преобразователь монад в mtl библиотека). Поддержка правильные хвостовые сигналы требуется, потому что в стиле передачи продолжения никакая функция никогда не возвращает; все звонки - это хвостовые звонки.

В веб-разработке

Одна из областей, в которой наблюдается практическое использование продолжений, - это Веб-программирование.^[7][8] Использование продолжений защищает программиста от без гражданства характер HTTP протокол. В традиционной модели веб-программирования отсутствие состояния отражается в структуре программы, что приводит к созданию кода, построенного на основе модели, которая очень плохо подходит для выражения вычислительных проблем. Таким образом, продолжения позволяют коду, который имеет полезные свойства, связанные с инверсия контроля, избегая при этом его проблем. Обратное преобразование инверсии управления или продолжения по сравнению с программированием, ориентированным на страницы - это статья, которая дает хорошее введение в продолжения, применяемые в веб-программировании.

Некоторые из наиболее популярных, поддерживающих продолжение Веб-серверы являются Ракетка Веб сервер, то Необычная веб-платформа и Веб-фреймворк Weblocks для Common Lisp, то Приморский каркас для Болтовня, Осиген / Элиом для OCaml, Непрерывность для Perl, Wee для Рубин, Рамки сказок для Фантом и Фреймворк Nagare для Python, Wt для C ++, MFlow для Haskell. В Apache Cocoon Фреймворк веб-приложений также предоставляет продолжения (см. Руководство по кокону ).

Виды

Поддержка продолжений широко варьируется. Язык программирования поддерживает повторно вызываемый продолжения, если продолжение можно вызывать повторно (даже после того, как оно уже вернулось). Повторно вызываемые продолжения были введены Питер Дж. Ландин используя его J (для Jump) оператор, который может передавать поток управления обратно в середину вызова процедуры. Повторно вызываемые продолжения также называются "возвращающимися" в Ракетка язык. Однако такое использование термина «повторно входящий» можно легко спутать с его использованием при обсуждении многопоточность.

Более ограниченный вид - это продолжение побега это может быть использовано для перехода от текущего контекста к окружающему. Многие языки, которые явно не поддерживают продолжения, поддерживают Обработка исключений, что эквивалентно escape-продолжению и может использоваться для тех же целей. C setjmp / longjmp также эквивалентны: их можно использовать только для раскрутки стека. Эскейп-продолжения можно также использовать для реализации устранение хвостового вызова.

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

Недостатки

Продолжения являются функциональным выражением ИДТИ К заявление, и применяются те же предостережения.^[9] Хотя они являются разумным вариантом в некоторых особых случаях, таких как веб-программирование, использование продолжений может привести к появлению кода, за которым трудно следовать. Фактически, эзотерический язык программирования Unlambda включает в себя вызов с текущим продолжением как одна из его черт исключительно из-за его сопротивления пониманию.^{[нужна цитата ]} Внешние ссылки ниже иллюстрируют концепцию более подробно.

Лингвистика

В разделе «Продолжение и природа количественной оценки», Крис Баркер ввел «гипотезу продолжения», что

некоторые лингвистические выражения (в частности, QNP [количественные словосочетания с существительными]) имеют обозначения, которые управляют своими собственными продолжениями.^[10]

Баркер утверждал, что эту гипотезу можно использовать для объяснения таких явлений, как двойственность значения NP (например, тот факт, что QNP «все» ведет себя совсем не так, как неколичественная именная фраза «Боб» в отношении значения предложения типа «Алиса видит [Боба / всех]»), смещение прицела (например, что «капля дождя упала на каждую машину» обычно интерпретируется как ${ Displaystyle forall c существует г, { mbox {упал}} (г, с)}$ а не как ${ Displaystyle существует r forall c, { mbox {упал}} (r, c)}$), и двусмысленность (что предложение типа «кто-то видел всех» может быть двусмысленным между ${ displaystyle существует x forall y, { mbox {saw}} (x, y)}$ и ${ displaystyle forall y существует x, { mbox {saw}} (x, y)}$). Он также заметил, что эта идея в некотором смысле является естественным продолжением Подход Ричарда Монтегю в «Правильном подходе к количественной оценке в обычном английском» (PTQ), где написано, что «оглядываясь назад, можно ясно различить ограниченную форму передачи продолжения в основе трактовки PTQ Монтегю (1973) NP как обобщенных квантификаторов». .

Степень, в которой продолжения могут быть использованы для объяснения других общих явлений на естественном языке, является темой текущих исследований.^[11]

Смотрите также

• Call-with-current-continue
• Закрытие
• РОДОМ ИЗ
• Продолжение прохождения стиля
• Поток управления
• Coroutine
• Продолжение с разделителями
• Денотационная семантика
• ИДТИ К
• Стек спагетти
• Quajects, тип объекта, который позволяет настраивать выбираемые продолжения (называемые «выноски») для методов для каждого объекта на основе Внедрение зависимости.

использованная литература

дальнейшее чтение

• Питер Ландин. Обобщение скачков и меток Отчет. Исследования системного программирования UNIVAC. Август 1965. Перепечатано в «Высшем порядке и символических вычислениях», 11 (2): 125-143, 1998, с предисловием Хайо Тилеке.
• Дрю Макдермотт и Джерри Сассман. Справочное руководство Conniver MIT AI Memo 259. Май 1972 г.
• Дэниел Боброу: Модель структур управления для языков программирования с искусственным интеллектом IJCAI 1973.
• Карл Хьюитт, Питер Бишоп и Ричард Штайгер. Универсальный модульный актерский формализм для искусственного интеллекта IJCAI 1973.
• Кристофер Стрейчи и Кристофер П. Уодсворт. Продолжения: математическая семантика для обработки полных прыжков Техническая монография ПРГ-11. Вычислительная лаборатория Оксфордского университета. Январь 1974 г. Перепечатано в «Высшем порядке и символические вычисления», 13 (1/2): 135–152, 2000, с предисловием Кристофера П. Уодсворта.
• Джон С. Рейнольдс. Определительные интерпретаторы языков программирования высшего порядка Труды 25-й Национальной конференции ACM, стр. 717–740, 1972 г. Перепечатано в «Высшем порядке и символические вычисления» 11 (4): 363-397, 1998, с предисловием.
• Джон С. Рейнольдс. О связи между прямой и продолжающейся семантикой Труды Второго коллоквиума по автоматам, языкам и программированию. LNCS Vol. 14. С. 141–156, 1974.
• Рейнольдс, Джон С. (1993). «Открытия продолжений» (PDF). Лисп и символьные вычисления. 6 (3/4): 233–248.CS1 maint: ref = harv (ссылка на сайт)
• Джеральд Сассман и Гай Стил. СХЕМА: Интерпретатор для расширенного лямбда-исчисления Памятка AI 349, Лаборатория искусственного интеллекта Массачусетского технологического института, Кембридж, Массачусетс, декабрь 1975 г. Перепечатано в журнале High-Order and Symbolic Computing 11 (4): 405-439, 1998, с предисловием.
• Роберт Хиб, Р. Кент Дибвиг, Карл Брюггеман. Представление контроля при наличии первоклассных продолжений Материалы конференции ACM SIGPLAN '90 по разработке и реализации языков программирования, стр. 66–77.
• Уилл Клингер, Энн Хартхаймер, Эрик Ост. Стратегии реализации для продолжения Труды конференции ACM 1988 г. по LISP и функциональному программированию, стр. 124–131, 1988 г. Версия журнала: Высшие порядки и символьные вычисления, 12 (1): 7-45, 1999.
• Кристиан Кейннек. Обратное преобразование инверсии управления или продолжения по сравнению с программированием, ориентированным на страницы Уведомления SIGPLAN 38 (2), стр. 57–64, 2003 г.

внешние ссылки

• ACM СИГПЛАН Мастер-класс по продолжению 2011 на ICFP.
• Продолжение для Скряги Сэм Руби
• Изучите схему за Fixnum Days Дораи Ситарам содержит красивую главу о продолжениях.
• Продолжение и безстековый Python Кристиан Тисмер
• Он-лайн материалы Четвертого семинара ACM SIGPLAN по продолжениям
• Он-лайн материалы Второго семинара ACM SIGPLAN по продолжениям
• Продолжение, функции и прыжки
• http://okmij.org/ftp/continuations/ Олег Киселев
• https://wiki.haskell.org/Continuations
• Rhino с продолжениями
• Продолжения на чистой Java от RIFE каркас веб-приложений
• Продолжение отладки на чистой Java от RIFE каркас веб-приложений
• Сравнение генераторов, сопрограмм и продолжений, источник приведенного выше примера