Просмотр кода страницы Продолжение (информатика)

{{Парадигмы программирования}}

'''Продолжение''' ({{lang-en|continuation}}) представляет состояние [[Компьютерная программа|программы]] в определённый момент, которое может быть сохранено и использовано для перехода в это состояние. Продолжения содержат всю информацию, чтобы продолжить выполнения программы с определённой точки. Состояние глобальных переменных обычно не сохраняется, однако для функциональных языков это несущественно (выборочное сохранение/восстановление значений глобальных объектов в Scheme достигается отдельным механизмом dynamic-wind). Продолжения похожи на <code>[[goto]]</code> Бейсика или <code>[[setjmp]]/[[longjmp]]</code> Си, так как также позволяют перейти в любое место программы. Но продолжения, в отличие от <code>goto</code>, позволяют перейти только в участок программы с определённым состоянием, которое должно быть сохранено заранее, в то время, как <code>goto</code> позволяет перейти в участок программы с неинициализированными [[переменная (программирование)|переменными]].

[[Scheme (язык программирования)|Scheme]] была первым промышленным языком, в котором реализованы полноценные продолжения. Bruce Duba ввёл продолжения в [[Standard ML]].

== Понятие ==

Формально, <code>callcc</code> — это [[функция высшего порядка]], позволяющая абстрагировать динамический контекст имеющейся функции в виде другой функции, которая и называется «''продолжением''».

Более наглядно, продолжение — это «''вся оставшаяся часть программы от данной точки''», или «''функция, которая '''никогда''' не возвращает управление в точку своего вызова''»{{sfn|Fake threads|1999}}. В процессе изучения [[Функциональное программирование|функционального программирования]] многие испытывают трудности с пониманием сущности продолжений. Традиционное объяснение этого понятия сводится к «''расширению (усложнению) понятия [[Сопрограмма|сопрограммы]]''», но в педагогическом смысле такое объяснение считается бесполезным{{sfn|Fake threads|1999}}. Причина трудности понимания заключается том, что продолжения фактически представляют собой альтернативное '''''обоснование''''' понятия «поведения» («вызова» в самом широком понимании), т.е. иную семантическую модель, и в этом смысле начальный переход от «обычного» функционального программирования к программированию с интенсивным использованием продолжений можно сравнить с начальным переходом от [[Императивное программирование|императивного]] программирования к [[Функциональное программирование|функциональному]].

Продолжения представляют собой математическое обоснование всего [[Порядок выполнения|порядка выполнения]] программы, от <code>goto</code> и [[Цикл (программирование)|циклов]] до [[рекурсия|рекурсии]], [[Обработка исключений|исключений]], {{iw|Генератор (программирование)|генераторов|en|Generator (computer programming)}}, [[Сопрограмма|сопрограмм]] и [[Поиск с возвратом|механизма возврата]]{{sfn|Fake threads|1999}}. Как следствие, они позволяют ''реализовать'' все эти элементы в языке посредством единой конструкции.

== Программирование в стиле передачи продолжений ==

{{main|:en:Continuation-passing style|l1=Программирование в стиле передачи продолжений {{ref-en}}}}

[[Программирование в стиле передачи продолжений]] ({{lang-en|Continuation-passing style, '''CPS'''}}) — это стиль программирования, при котором [[Порядок выполнения|передача управления]] осуществляется через механизм продолжений. Стиль CPS впервые представили {{iw|Сассман, Джеральд|Джеральд Джей Сассман|en|Gerald Jay Sussman}} и {{iw|Стил, Гай Л. мл.|Гай Стил мл.|en|Guy L. Steele, Jr.}}, одновременно с языком [[Scheme (язык программирования)|Scheme]].

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

{|
!<center>Direct style</center>!!<center>Continuation passing style</center>
|-valign="top"
|<source lang=scheme>
(define (pyth x y)
 (sqrt (+ (* x x) (* y y))))</source>
||
<source lang=scheme>
(define (pyth& x y k)
 (*& x x (lambda (x2)
          (*& y y (lambda (y2)
                   (+& x2 y2 (lambda (x2py2)
                              (sqrt& x2py2 k))))))))
</source>
|-valign="top"
|
<source lang=scheme>
(define (factorial n)
 (if (= n 0)
     1     ; NOT tail-recursive
     (* n (factorial (- n 1)))))
</source>
||
<source lang=scheme>

(define (factorial& n k)
 (=& n 0 (lambda (b)
          (if b                    ; продолжение растёт
              (k 1)                ; в рекурсивном вызове
              (-& n 1 (lambda (nm1)
                       (factorial& nm1 (lambda (f)
                                        (*& n f k)))))))))
</source>
|-valign="top"
|
<source lang=scheme>
(define (factorial n)
 (f-aux n 1))
(define (f-aux n a)
 (if (= n 0)
     a        ; tail-recursive
     (f-aux (- n 1) (* n a))))
</source>
||
<source lang=scheme>
(define (factorial& n k) (f-aux& n 1 k))
(define (f-aux& n a k)
 (=& n 0 (lambda (b)
          (if b                    ; продолжение сохраняется
              (k a)                ; в рекурсивном вызове
              (-& n 1 (lambda (nm1) 
                       (*& n a (lambda (nta)
                                (f-aux& nm1 nta k)))))))))
</source>
|}

Можно заметить, что в чистом CPS фактически не существует самих продолжений — всякий вызов оказывается [[Хвостовая рекурсия|хвостовым]]. Если язык не гарантирует '''[[Оптимизация хвостовой рекурсии|оптимизацию хвостовых вызовов]]''' ({{lang-en|Tail call optimization, TCO}}), то при каждом вложенном вызове <code>callcc</code> растёт и само продолжение, и [[стек вызовов]]. Обычно это нежелательно, но временами используется интересным способом (см. {{iw|Chicken (реализация языка Scheme)|компилятор Chicken Scheme|en|Chicken (Scheme implementation)}}). Совместное использование стратегий оптимизации TCO и CPS позволяет полностью устранить динамический стек из исполнимой программы. Ряд компиляторов [[Функциональное программирование|функциональных языков]] работает именно таким образом, к примеру компилятор SML/NJ для языка [[Standard ML]].

== Ограниченные и неограниченные продолжения ==
Существует несколько разновидностей продолжений. Наиболее распространенная из них - '''неограниченные (undelimited continuations)''' продолжения, реализуемые с помощью функции '''[[callcc|call/cc]]''' или её аналогов. Такие продолжения действительно представляют собой состояние всей программы (или одной её нити) в определенный момент. Вызов такого продолжения не похож на вызов функции, поскольку он соответствует "прыжку" в сохраненное состояние программы и не возвращает никакого значения; такое продолжение обычно нельзя вызвать несколько раз. '''Ограниченные (delimited continuations)''' же продолжения абстрагируют зависимость результата некоторого блока программы от результата некоторого подвыражения этого блока. В определенном смысле они соответствуют '''сегменту''' стека вызовов, а не всему стеку. Такие продолжения могут использоваться как функции, вызываться несколько раз и т.п. Они абстрагируются с помощью механизма '''shift/reset''': '''reset''' оборачивает внешний блок, '''shift''' действует как [[callcc|call/cc]], но получает в качестве аргумента не '''глобальное''' продолжение, а ограниченное - зависимость значения блока reset от значения на месте блока shift. Существуют и другие разновидности, к примеру '''prompt/control'''.

== Поддержка языками программирования ==
Многие языки программирования предоставляют эту возможность под различными именами, например:
* [[Scheme]]: <code>call/cc</code> (краткая запись для <code>call-with-current-continuation</code>)
* [[Standard ML]]: <code>SMLofNJ.Cont.callcc</code>
* [[Си (язык программирования)|Си]]: <code>[[setcontext]]</code> et al. ([[UNIX System V]] и [[GNU]] libc)
* [[Ruby]]: <code>callcc</code>
* [[Smalltalk]]: <code>Continuation currentDo:</code>, в большинстве современных реализаций продолжения могут быть реализованы на чистом Smalltalk, не требуя специальной поддержки в [[виртуальная машина|виртуальной машине]].
* [[Rhino]] : <code>Continuation</code>
* [[Haskell]] : <code>callCC</code> (в модуле <code>Control.Monad.Cont</code>)
* [[Factor (язык программирования)|Factor]] : <code>callcc0</code> и <code>callcc1</code>
* [[Python]] : <code>yield</code>
* [[Scala (язык программирования)|Scala]] : Существует плагин для поддержки ограниченных продолжений.
* [[PHP]]: Есть поддержка.
* [[C Sharp|C#]]: конструкции <code>yield return</code> и <code>await</code>.
В любом языке, поддерживающем [[Замыкание (программирование)|замыкания]], можно писать программы [[Программирование в стиле передачи продолжений|в стиле передачи продолжений]] ({{lang-en|Continuation-passing style, CPS}}) и вручную реализовать <code>[[callcc|call/cc]]</code>. В частности это принятая практика в [[Haskell]], где легко строятся «монады, передающие продолжения» (для примера, монада <code>Cont</code> и трансформер монад  <code>ContT</code> библиотеки <code>mtl</code>).

== См. также ==
* [[Замыкание (программирование)|Замыкание]]
* [[Сопрограмма]]

== Примечания ==
{{примечания}}

== Ссылки ==
* [http://www.smalltalk.ru/articles/web-continuations.html Продолжение всемирной паутины] — о использования продолжений для построения веб-приложений.
* [http://fprog.ru/lib/ Библиотечка ПФП] — в статье "Паттерны использования call with current continuation" (перевод) описана концепция продолжений и дан ряд разнообразных примеров их использования.
* [http://library.readscheme.org/page6.html Continuations and Continuation Passing Style] — большая коллекция статей о разных видах продолжений и их использовании.
* {{статья
|автор=Tim Peters
|заглавие=Fake threads (was <nowiki>[Python-Dev]</nowiki> ActiveState & fork & Perl)
|ссылка=https://mail.python.org/pipermail/python-dev/1999-July/000467.html
|год=1999
|ref=Fake threads
}}

[[Категория:Концепции языков программирования]]
[[Категория:Управление потоком]]