Войти
В информатике, a продолжение - это абстрактное представление состояния управления компьютерной программы . Продолжение реализует (повторяет ) состояние управления программой, то есть продолжение - это структура данных, которая представляет вычислительный процесс в заданной точке выполнения процесса; Созданная структура данных может быть доступна для языка программирования, вместо того, чтобы быть скрытой в среде выполнения . Продолжения полезны для кодирования других механизмов управления в языках программирования, таких как исключения, генераторы, сопрограммы и так далее.
«текущее продолжение » или «продолжение этапа вычислений» - это продолжение, которое, с точки зрения выполняемого кода, могло бы быть получено из текущей точки выполнения программы. Термин «продолжения» также может использоваться для обозначения первоклассных продолжений, которые представляют собой конструкции, которые дают языку программирования возможность сохранять состояние выполнения в любой момент и возвращаться к этой точке. позже в программе, возможно, несколько раз.
Самое раннее описание продолжений было сделано Адрианом ван Вейнгаарденом в сентябре 1964 года. Вейнгаарден выступал на Рабочей конференции IFIP по языкам описания формальных языков, проходившей в Баден-бай-Вена, Австрия. В рамках разработки препроцессора Algol 60 он призвал преобразовать соответствующие процедуры в стиль передачи продолжения, хотя он не использовал это имя, и его намерение состояло в том, чтобы упростить программу и тем самым сделать ее результат более понятным.
Кристофер Стрейчи и Джон К. Рейнольдс выдвинули термин «продолжение» на видное место в своей работе в области денотационной семантики, которая широко использует продолжения, чтобы позволить последовательное программы, подлежащие анализу с точки зрения семантики функционального программирования.
Стив Рассел изобрел продолжение в своей второй реализации Lisp для IBM 704, хотя он не назвал это.
Рейнольдс (1993) дает полную историю открытия продолжений.
Первоклассные продолжения - это способность языка полностью контролировать порядок выполнения инструкций. Их можно использовать для перехода к функции, которая вызвала вызов текущей функции, или к функции, которая ранее завершилась. Можно думать о первоклассном продолжении как о сохранении состояния выполнения программы. Важно отметить, что истинные первоклассные продолжения не сохраняют данные программы - в отличие от образа процесса - только контекст выполнения. Это иллюстрируется описанием «сэндвич продолжения»:
Допустим, вы находитесь на кухне перед холодильником и думаете о сэндвиче. Вы тут же берете продолжение и кладете в карман. Затем вы достаете индейку и хлеб из холодильника и делаете себе бутерброд, который теперь стоит на прилавке. Вы вызываете продолжение в кармане и снова стоите перед холодильником, думая о бутерброде. Но, к счастью, на прилавке есть бутерброд, и все материалы, из которых он сделан, исчезли. Итак, съешь это. :-)
В этом описании сэндвич - это часть данных программы (например, объект в куче), и вместо того, чтобы вызывать процедуру «сделать бутерброд» и затем вернуться, человек назвал «сделать бутерброд с текущее продолжение », которая создает сэндвич и затем продолжает с того места, где было остановлено выполнение.
Схема была первой полноценной производственной системой (1969-1970), обеспечивающей сначала «улов», а затем call / cc. Брюс Дуба представил call / cc в SML.
Продолжения также используются в моделях вычислений, включая денотационную семантику, модель актора, вычисление процессов и лямбда-исчисление. Эти модели полагаются на программистов или инженеров по семантике для написания математических функций в так называемом стиле передачи продолжения. Это означает, что каждая функция использует функцию, которая представляет остальную часть вычислений относительно этого вызова функции. Чтобы вернуть значение, функция вызывает эту «функцию продолжения» с возвращаемым значением; чтобы прервать вычисление, он возвращает значение.
Функциональные программисты, которые пишут свои программы в стиле передачи продолжения, получают выразительную способность манипулировать потоком управления произвольными способами. Цена состоит в том, что они должны поддерживать инварианты управления и продолжения вручную, что может быть очень сложной задачей (но см. «Стиль передачи продолжения» ниже).
Продолжение упрощает и разъясняет реализацию нескольких общих шаблонов проектирования , включая сопрограммы / зеленые потоки и обработка исключений, предоставляя базовый низкоуровневый примитив, который объединяет эти, казалось бы, несвязанные шаблоны. Продолжения могут предоставить элегантные решения некоторых сложных проблем высокого уровня, таких как программирование веб-сервера, поддерживающего несколько страниц, доступ к которым осуществляется с помощью кнопок вперед и назад и по ссылкам. Веб-среда Smalltalk Seaside очень эффективно использует продолжения, позволяя программировать веб-сервер в процедурном стиле, переключая продолжения при переключении страниц.
Также существуют более сложные конструкции, для которых «продолжения дают элегантное описание». Например, в C, longjmp можно использовать для перехода от середины одной функции к другой, при условии, что вторая функция лежит глубже в стеке (если она ожидает, пока первая функция вернуться, возможно, среди прочего). Другие более сложные примеры включают сопрограммы в Simula 67, Lua и Perl ; тасклеты в Stackless Python ; генераторы в Icon и Python ; продолжения в Scala (начиная с 2.8); волокна в Ruby (начиная с 1.9.1); механизм возврата в Prolog ; монады в функциональном программировании ; и потоки.
Язык программирования Scheme включает в себя управляющий оператор call-with-current-continue (сокращенно: call / cc) с помощью которого программа Scheme может манипулировать потоком управления:
(define the-continue #f) (define (test) (let ((i 0)); call / cc вызывает свой первый аргумент функции, передавая; продолжение переменная, представляющая эту точку в; программе в качестве аргумента этой функции.;; В этом случае аргумент функции присваивает это продолжение переменной the-continue.; (call / cc (lambda (k) (set! the- continue k)));; В следующий раз, когда вызывается продолжение, мы начнем здесь. (set! i (+ i 1)) i))
Определяет функцию test, которая устанавливает продолжениек будущему состоянию выполнения самого себя:
>(тест) 1>(продолжение) 2>(продолжение) 3>; сохраняет текущее продолжение (которое напечатает 4 следующих) прочь>(определить продолжение продолжения)>(тест); сбрасывает продолжение 1>(продолжение) 2>(продолжение другого); использует ранее сохраненное продолжение 4
Для более мягкого введения в этот механизм см. call-with-current-continue.
В этом примере показано возможное использование продолжений для реализации сопрограммы как отдельные потоки.
;;; Наивная очередь для планирования потоков. ;;; Он содержит список продолжений, «ожидающих запуска». (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)) ;;; Это запускает новый поток (процесс). (define (fork proc) (call / cc (lambda (k) (enqueue k) (proc)))) ;;; Это передает процессор другому потоку, если он есть. (define (yield) (call / cc (lambda (k) (enqueue k) ((dequeue))))) ;;; Это завершает текущий поток или всю программу ;;; если не осталось других нитей. (define (thread-exit) (if (empty-queue?) (exit) ((dequeue))))
Определенные выше функции позволяют определять и выполнять потоки с помощью совместной многозадачности, т. е. потоков которые передают управление следующему в очереди:
;;; Тело некоторого типичного потока схемы, который выполняет что-то: (define (do-stuff-n-print str) (lambda () (let loop ((n 0)) (format #t "~ A ~ A \ n" str n) (yield) (loop (+ n 1))))) ;;; Создайте два потока и запустите их. (fork (do-stuff-n-print "Это AAA")) (fork (do-stuff-n-print "Hello from BBB")) (thread-exit)
Предыдущий код даст следующий результат:
Это AAA 0 Привет от BBB 0 Это AAA 1 Привет от BBB 1 Это AAA 2 Привет от BBB 2...
Программа должна выделить пространство в памяти для переменных, которые используются его функциями. Большинство языков программирования используют стек вызовов для хранения необходимых переменных, поскольку он позволяет быстро и просто выделять и автоматически освобождать память. В других языках программирования для этого используется куча, что обеспечивает гибкость при более высоких затратах на выделение и освобождение памяти. Обе эти реализации имеют преимущества и недостатки в контексте продолжений.
Многие языки программирования демонстрируют первоклассные продолжения под разными именами; в частности:
asyncи await: "зарегистрируйте остальную часть метода в качестве продолжения, а затем немедленно вернитесь к вызывающей стороне. ; по завершении задача вызовет продолжение ". Асинхронное программирование для C # callcc0и callcc1Control.Monad.Cont create, suspend, @operator: coexpressionsПродолжениеПродолжениеПродолжениеPMC; использует стиль передачи продолжения для всего потока управленияcall (exp ())и continue (aContinuation, anyValue)_continuation.continulet call- with-current-continue (обычно сокращается до call / cc)callccscala.util.continuationsобеспечивает shift/resetcall-with-current-continuation (обычно сокращается до call / cc)CurrentDo:; в большинстве современных сред Smalltalk продолжения могут быть реализованы без дополнительной поддержки виртуальных машин.SMLofNJ.Cont.callccc, операция управления потоком для вызова с текущим продолжением. На любом языке, который поддерживает закрытие и соответствующие хвостовые вызовы, можно писать программы на стиль передачи продолжения и ma обычно реализуйте call / cc. (В стиле передачи продолжения call / cc становится простой функцией, которую можно записать с помощью лямбда.) Это особенно распространенная стратегия в Haskell, где легко построить «продолжение-передача монады » (например, монада Contи преобразователь монады ContTв библиотеке mtl). Поддержка правильных хвостовых вызовов необходима, потому что в стиле передачи продолжения никакая функция никогда не возвращает; все звонки - хвостовые.
Одной из областей практического использования продолжений является веб-программирование. Использование продолжений защищает программиста от природы без сохранения состояния протокола HTTP. В традиционной модели веб-программирования отсутствие состояния отражается в структуре программы, что приводит к созданию кода, построенного на основе модели, которая очень плохо подходит для выражения вычислительных проблем. Таким образом, продолжения включают код, который имеет полезные свойства, связанные с инверсией управления, избегая при этом его проблем. Обратное обращение, инверсия управления или «Продолжение против программирования» - это статья, которая дает хорошее введение в продолжения, применяемые в веб-программировании.
Некоторые из наиболее популярных веб-серверов с поддержкой продолжения - это Racket веб-сервер, UnCommon Web Framework и Weblocks Web framework для Common Lisp, Seaside framework для Smalltalk, Ocsigen / Eliom для OCaml, Continuity для Perl, Wee для Ruby, Tales Framework для Fantom и Nagare framework для Python, Wt для C ++, MFlow для Haskell. Apache Cocoon Инфраструктура веб-приложений также обеспечивает продолжения (см. руководство по Cocoon ).
Поддержка продолжений сильно различается. Язык программирования поддерживает повторно вызываемые продолжения, если продолжение можно вызывать повторно (даже после того, как оно уже было возвращено). Повторно вызываемые продолжения были введены Питером Дж. Ландином с помощью оператора J (для перехода), который мог передавать поток управления обратно в середину вызова процедуры. Повторно вызываемые продолжения также называются «реентерабельными» на языке Racket. Однако такое использование термина «повторно входящий» можно легко спутать с его использованием при обсуждении многопоточности.
Более ограниченным видом является escape-продолжение, которое может использоваться для выхода из текущего контекста в окружающий. Многие языки, которые явно не поддерживают продолжения, поддерживают обработку исключений, которая эквивалентна escape-продолжениям и может использоваться для тех же целей. C setjmp/longjmp также эквивалентны: они могут использоваться только для раскрутки стека. Экранирующие продолжения также могут использоваться для реализации исключения хвостовых вызовов.
Одним из обобщений продолжений являются ограниченные продолжения. Операторы продолжения, такие как call / cc, фиксируют все оставшиеся вычисления в заданной точке программы и не предоставляют возможности ограничить этот захват. Операторы продолжения с разделителями решают эту проблему, предоставляя два отдельных механизма управления: подсказку, ограничивающую операцию продолжения, и оператор повторения, такой как shiftили control. Таким образом, продолжения, захваченные с использованием операторов с разделителями, представляют только часть контекста программы.
Продолжения - это функциональное выражение оператора GOTO, и здесь применяются те же предостережения. Хотя они являются разумным вариантом в некоторых особых случаях, таких как веб-программирование, использование продолжений может привести к появлению кода, за которым трудно следовать. Фактически, эзотерический язык программирования Unlambda включает call-with-current-continue в качестве одной из своих функций исключительно из-за его сопротивления пониманию. Внешние ссылки ниже иллюстрируют концепцию более подробно.
В разделе «Продолжение и природа количественной оценки» Крис Баркер представил «гипотезу продолжения», что
некоторые лингвистические выражения (в частности, QNPs [количественные выражения существительных]) имеют обозначения, которые манипулируют их собственными продолжениями.
Баркер утверждал, что эту гипотезу можно использовать для объяснения таких явлений, как двойственность значения NP (например, тот факт, что QNP «все» ведет себя совершенно иначе, чем неколичественная фраза существительного «Боб», вносящая вклад в смысл предложения типа «Алиса видит [Боба / всех]»), смещение области действия (например, что «капля дождя упала на каждую машину» обычно интерпретируется как 
Степень, в которой продолжения могут использоваться для объяснения других общих явлений на естественном языке, является темой текущих исследований.
