Продолжение

Чтобы узнать о других значениях, см. Продолжение (значения) .

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

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

История

Самое раннее описание продолжений было сделано Адрианом ван Вейнгаарденом в сентябре 1964 года. Вейнгаарден выступил на рабочей конференции ИФИП по языкам формального описания языка, проходившей в Баден-бай-Вене, Австрия. В рамках формулировки препроцессора Algol 60 он призвал преобразовать правильные процедуры в стиль передачи продолжения , хотя он не использовал это имя, и его намерением было упростить программу и тем самым сделать ее результат более понятным.

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

Стив Рассел изобрел продолжение в своей второй реализации Lisp для IBM 704 , хотя и не назвал его.

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

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

Первоклассные продолжения — это способность языка полностью контролировать порядок выполнения инструкций. Их можно использовать для перехода к функции, вызвавшей вызов текущей функции, или к функции, которая ранее завершилась. Под первоклассным продолжением можно понимать сохранение состояния выполнения программы. Настоящие первоклассные продолжения не сохраняют данные программы (в отличие от образа процесса ), а только контекст выполнения. Это иллюстрируется описанием «сэндвича продолжения»:

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

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

Scheme была первой полноценной производственной системой, обеспечивающей первый «улов». а затем позвоните /cc . Брюс Дуба представил call/cc в SML .

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

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

Использование

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

Более сложные конструкции, для которых «продолжение дает элегантное описание». также существуют. Например, в C к другой, при условии , longjmp можно использовать для перехода от середины одной функции что вторая функция находится глубже в стеке (если она ожидает возврата от первой функции, возможно, среди других). Другие более сложные примеры включают сопрограммы в Simula 67 , Lua и Perl ; тасклеты в Stackless Python ; генераторы в Icon и Python ; продолжения в Scala (начиная с версии 2.8); волокна в Ruby (начиная с версии 1.9.1); механизм возврата в Прологе ; монады в функциональном программировании ; и нити .

Примеры

Язык программирования Scheme включает оператор управления call-with-current-continuation (сокращенно: call/cc), с помощью которого программа Scheme может манипулировать потоком управления:

 (define the-continuation #f)

 (define (test)
   (let ((i 0))
     ; call/cc calls its first function argument, passing
     ; a continuation variable representing this point in
     ; the program as the argument to that function.
     ;
     ; In this case, the function argument assigns that
     ; continuation to the variable the-continuation.
     ;
     (call/cc (lambda (k) (set! the-continuation k)))
     ;
     ; The next time the-continuation is called, we start here.
     (set! i (+ i 1))
     i))

Используя вышеизложенное, следующий блок кода определяет функцию test который устанавливает the-continuation к будущему состоянию выполнения:

 > (test)
 1
 > (the-continuation)
 2
 > (the-continuation)
 3
 > ; stores the current continuation (which will print 4 next) away
 > (define another-continuation the-continuation)
 > (test) ; resets the-continuation
 1
 > (the-continuation)
 2
 > (another-continuation) ; uses the previously stored continuation
 4

Более подробное введение в этот механизм см. в разделе call-with-current-continuation .

Сопрограммы

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

 ;;; A naive queue for thread scheduling.
 ;;; It holds a list of continuations "waiting to run".

   (define *queue* '())

   (define (empty-queue?)
     (null? *queue*))

   (define (enqueue x)
     (set! *queue* (append *queue* (list x))))

   (define (dequeue)
     (let ((x (car *queue*)))
       (set! *queue* (cdr *queue*))
       x))

   ;;; This starts a new thread running (proc).

   (define (fork proc)
     (call/cc
      (lambda (k)
        (enqueue k)
        (proc))))

   ;;; This yields the processor to another thread, if there is one.

   (define (yield)
     (call/cc
      (lambda (k)
        (enqueue k)
        ((dequeue)))))

   ;;; This terminates the current thread, or the entire program
   ;;; if there are no other threads left.

   (define (thread-exit)
     (if (empty-queue?)
         (exit)
         ((dequeue))))

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

   ;;; The body of some typical Scheme thread that does stuff:

   (define (do-stuff-n-print str)
     (lambda ()
       (let loop ((n 0))
         (format #t "~A ~A\n" str n)
         (yield)
         (loop (+ n 1)))))

   ;;; Create two threads, and start them running.
   (fork (do-stuff-n-print "This is AAA"))
   (fork (do-stuff-n-print "Hello from BBB"))
   (thread-exit)

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

 This is AAA 0
 Hello from BBB 0
 This is AAA 1
 Hello from BBB 1
 This is AAA 2
 Hello from BBB 2
 ...

Выполнение

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

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

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

• Common Lisp : cl-cont . Также можно использовать пользовательские макросы
• С# / ВБ.NET : async и await: «зарегистрируйте остальную часть метода как продолжение, а затем немедленно вернитесь к вызывающему объекту; задача вызовет продолжение после завершения». Асинхронное программирование для C#
• Фактор : callcc0 и callcc1
• Haskell продолжения : монада в Control.Monad.Cont
• Haxe : haxe-продолжение
• Иконка , Юникон : create, suspend, @ оператор: ковыражения
• Java : Lightwolf Javaflow (требует манипуляций с байт-кодом во время выполнения или во время компиляции)
• Котлин : Continuation
• JavaScript Носорог : Continuation
• Попугай : Continuation ЧВК; использует стиль передачи продолжения для всего потока управления
• Perl : Coro и непрерывность
• Пико : call(exp()) и continue(aContinuation, anyValue)
• Python : PyPy ​ _continuation.continulets
• Ракетка : call-with-current-continuation (обычно сокращается до call/cc)
• Руби : callcc
• Скала : scala.util.continuations обеспечивает shift/ reset
• Схема : call-with-current-continuation (обычно сокращается до call/cc)
• Смолток : Continuation currentDo:; в большинстве современных сред Smalltalk продолжения могут быть реализованы без дополнительной поддержки VM.
• Стандартный ML штата Нью-Джерси : SMLofNJ.Cont.callcc
• Унлямбда : c, операция управления потоком для вызова с текущим продолжением

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

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

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

Виды

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

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

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

Недостатки

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

Лингвистика

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

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

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

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

См. также

• Звонок с текущим продолжением
• Закрытие
• COMEFROM
• Стиль продолжения прохождения
• Поток управления
• Сопрограмма
• Продолжение с разделителями
• Денотационная семантика
• ПЕРЕЙТИ К
• Стопка спагетти
• Quajects — тип объекта, который позволяет устанавливать выбираемые продолжения (так называемые «выноски») для методов для каждого объекта посредством внедрения зависимостей .

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

• Питер Ландин . Обобщенный отчет о переходах и метках. Исследование системного программирования UNIVAC. Август 1965 г. Перепечатано в журнале Higher Order and Символические вычисления, 11(2):125-143, 1998 г., с предисловием Хайо Тилеке.
• Дрю МакДермотт и Джерри Сассман . Справочное руководство Conniver, MIT AI Memo 259. Май 1972 г.
• Дэниел Боброу : Модель структур управления для языков программирования искусственного интеллекта IJCAI 1973.
• Карл Хьюитт , Питер Бишоп и Ричард Стайгер . Универсальный модульный формализм актеров для искусственного интеллекта IJCAI 1973.
• Кристофер Стрейчи и Кристофер П. Уодсворт . Продолжение: Математическая семантика обработки полных прыжков. Техническая монография ПРГ-11. Вычислительная лаборатория Оксфордского университета. Январь 1974 г. Перепечатано в журнале Higher Order and Символические вычисления, 13(1/2):135–152, 2000 г., с предисловием Кристофера П. Уодсворта.
• Джон К. Рейнольдс . Дефиниционные интерпретаторы для языков программирования высшего порядка. Материалы 25-й национальной конференции ACM, стр. 717–740, 1972. Перепечатано в журнале Higher-Order and Символические вычисления 11 (4): 363-397, 1998, с предисловием.
• Джон К. Рейнольдс. О соотношении прямой и продолженной семантики. Материалы второго коллоквиума по автоматам, языкам и программированию. LNCS Том. 14, стр. 141–156, 1974.
• Рейнольдс, Джон К. (1993). «Открытия продолжений» (PDF) . LISP и символьные вычисления . 6 (3/4): 233–248.
• Джеральд Сассман и Гай Стил . СХЕМА: Интерпретатор расширенного лямбда-исчисления AI, Memo 349, Лаборатория искусственного интеллекта Массачусетского технологического института, Кембридж, Массачусетс, декабрь 1975 г. Перепечатано в журнале Higher-Order and Символические вычисления 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 SIGPLAN Семинар по продолжению 2011 года на ICFP .
• Продолжение для скряг Сэма Руби
• В книге «Teach Yourself Scheme in Fixnum Days» Дораи Ситарама есть хорошая глава, посвященная продолжению.
• Продолжения и Stackless Python , Кристиан Тизмер
• Онлайн-материалы четвертого семинара ACM SIGPLAN по продолжениям. Архивировано 2 декабря 2010 г. в Wayback Machine.
• Онлайн-материалы второго семинара ACM SIGPLAN по продолжению
• Продолжение, функции и переходы. Архивировано 2 декабря 2010 г. на Wayback Machine.
• http://okmij.org/ftp/continuations/ by Oleg Kiselyov
• https://wiki.haskell.org/Continuations
• Носорог с продолжениями
• Продолжение на чистой Java из фреймворка веб-приложений RIFE
• Продолжения отладки на чистой Java. Архивировано 16 мая 2021 г. на Wayback Machine из среды веб-приложений RIFE.
• Сравнение генераторов, сопрограмм и продолжений, источник приведенного выше примера