Продолжение (информатика)
Продолжение (англ. continuation) — абстрактное представление состояния программы в определённый момент, которое может быть сохранено и использовано для перехода в это состояние. Продолжения содержат всю информацию, чтобы продолжить выполнения программы с определённой точки; состояние глобальных переменных обычно не сохраняется, однако для функциональных языков это несущественно (например, выборочное сохранение и восстановление значений глобальных объектов в Scheme достигается отдельным механизмом dynamic-wind). Продолжения похожи на goto
Бейсика или макросы setjmp
и longjmp
в Си, так как так же позволяют перейти в любое место программы. Но продолжения, в отличие от goto
, позволяют перейти в участок программы только с определённым состоянием, которое должно быть сохранено заранее, в то время, как goto
позволяет перейти в участок программы с неинициализированными переменными.
Первый язык, реализовавший концепцию продолжений — Scheme, позднее встроенная поддержка продолжений появилась в ряде других языков.
Определения
Формально, callcc
— это функция высшего порядка, позволяющая абстрагировать динамический контекст имеющейся функции в виде другой функции, которая и называется «продолжением».
Более наглядно, продолжение — это «вся оставшаяся часть программы от данной точки», или «функция, которая никогда не возвращает управление в точку своего вызова»[1]. В курсах функционального программирования объяснение понятия продолжения часто сводится к «расширению (усложнению) понятия сопрограммы», но в дидактическом смысле такое объяснение считается бесполезным[1]. Причина трудности объяснения концепции заключается в том, что продолжения фактически являются альтернативным обоснованием понятия «поведения» («вызова» в самом широком понимании), то есть несут иную семантическую модель, и в этом смысле начальный переход от «обычного» функционального программирования к программированию с интенсивным использованием продолжений можно сравнить с начальным переходом от императивного программирования к функциональному.
Продолжения обеспечивают математическое обоснование всего порядка выполнения программы, от goto
и циклов до рекурсии, исключений, генераторов, сопрограмм и механизма возврата[1]. Как следствие, они позволяют реализовать все эти элементы в языке посредством единой конструкции.
Программирование в стиле передачи продолжений
Программирование в стиле передачи продолжений (англ. continuation-passing style, CPS) — это стиль программирования, при котором передача управления осуществляется через механизм продолжений. Стиль CPS впервые представили Джеральд Джей Сассман[англ.] и Гай Стил-младший[англ.], одновременно с языком Scheme.
Программу в «классическом стиле» зачастую можно переписать в стиле передачи продолжений. Например, для задачи вычисления гипотенузы прямоугольного треугольника с «классическим» кодом на Haskell:
pow2 :: Float -> Float
pow2 a = a ** 2
add :: Float -> Float -> Float
add a b = a + b
pyth :: Float -> Float -> Float
pyth a b = sqrt (add (pow2 a) (pow2 b))
можно добавить один аргумент типа F
, где F
означает функцию из возвращаемого значения исходной функции в произвольный тип x
, а возвращающим значением сделать этот произвольный тип x
:
pow2' :: Float -> (Float -> a) -> a
pow2' a cont = cont (a ** 2)
add' :: Float -> Float -> (Float -> a) -> a
add' a b cont = cont (a + b)
-- типы a -> (b -> c) и a -> b -> c эквивалентны, поэтому CPS-функцию можно
-- рассмотреть как функцию высшего порядка от одного аргумента
sqrt' :: Float -> ((Float -> a) -> a)
sqrt' a = \cont -> cont (sqrt a)
pyth' :: Float -> Float -> (Float -> a) -> a
pyth' a b cont = pow2' a (\a2 -> pow2' b (\b2 -> add' a2 b2 (\anb -> sqrt' anb cont)))
В функции pyth'
вычисляется квадрат от a
, и в качестве продолжения передаётся функция (лямбда-выражение), принимающая единственным аргументом a
в квадрате. Далее таким же образом вычисляются все последующие промежуточные значения. Для того, чтобы произвести вычисления, в качестве продолжения необходимо передать функцию от одного аргумента, например, функцию id
, которая возвращает любое переданное ей значение. Таким образом, выражение pyth' 3 4 id
эквивалентно 5.0
.
Стандартная haskell-библиотека в модуле Control.Monad.Cont содержит тип Cont
, позволяющий использовать CPS функции в монаде. Функция pyth'
будет выглядеть следующим образом:
pow2_m :: Float -> Cont a Float
pow2_m a = return (a ** 2)
-- функция cont поднимает обычные CPS функции в монаду
pyth_m :: Float -> Float -> Cont a Float
pyth_m a b = do
a2 <- pow2_m a
b2 <- pow2_m b
anb <- cont (add' a2 b2)
r <- cont (sqrt' anb)
return r
Также данный модуль содержит функцию callCC
, имеющую тип MonadCont m => ((a -> m b) -> m a) -> m a
. Из типа видно, что она принимает единственным аргументом функцию, которая, в свою очередь, также имеет единственным аргументом функцию, прерывающую дальнейшие вычисления. Например, мы можем прервать дальнейшие вычисления, если хотя бы один из аргументов отрицательный:
pyth_m :: Float -> Float -> Cont a Float
pyth_m a b = callCC $ \exitF -> do
when (b < 0 || a < 0) (exitF 0.0) -- when :: Applicative f => Bool -> f () -> f ()
a2 <- pow2_m a
b2 <- pow2_m b
anb <- cont (add' a2 b2)
r <- cont (sqrt' anb)
return r
Примеры CPS в Scheme:
(define (pyth x y)
(sqrt (+ (* x x) (* y y))))
| (define (pyth& x y k)
(*& x x (lambda (x2)
(*& y y (lambda (y2)
(+& x2 y2 (lambda (x2py2)
(sqrt& x2py2 k))))))))
|
(define (factorial n)
(if (= n 0)
1 ; NOT tail-recursive
(* n (factorial (- n 1)))))
| (define (factorial& n k)
(=& n 0 (lambda (b)
(if b ; продолжение растёт
(k 1) ; в рекурсивном вызове
(-& n 1 (lambda (nm1)
(factorial& nm1 (lambda (f)
(*& n f k)))))))))
|
(define (factorial n)
(f-aux n 1))
(define (f-aux n a)
(if (= n 0)
a ; tail-recursive
(f-aux (- n 1) (* n a))))
| (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)))))))))
|
В «чистом» CPS фактически не существует самих продолжений — всякий вызов оказывается хвостовым. Если язык не гарантирует оптимизации хвостовых вызовов (англ. Tail call optimization, TCO), то при каждом вложенном вызове callcc
растёт и само продолжение, и стек вызовов. Обычно это нежелательно, но временами используется интересным способом (например, в компиляторе Chicken Scheme[англ.]). Совместное использование стратегий оптимизации TCO и CPS позволяет полностью устранить динамический стек из исполнимой программы. Ряд компиляторов функциональных языков работает именно таким образом, к примеру, компилятор SML/NJ для языка Standard ML.
Ограниченные и неограниченные продолжения
Существует несколько разновидностей продолжений. Наиболее распространённая из них — неограниченные продолжения (undelimited continuations), реализуемые с помощью функции call/cc
или её аналогов. Такие продолжения действительно представляют собой состояние всей программы (или одной её нити) в определённый момент. Вызов такого продолжения не похож на вызов функции, поскольку он соответствует «прыжку» в сохраненное состояние программы и не возвращает никакого значения; такое продолжение обычно нельзя вызвать несколько раз. Ограниченные продолжения (delimited continuations) абстрагируют зависимость результата некоторого блока программы от результата некоторого подвыражения этого блока. В определённом смысле они соответствуют некоторому сегменту стека вызовов, а не всему стеку. Такие продолжения могут использоваться как функции, вызываться несколько раз и так далее. Они абстрагируются с помощью механизма shift/reset
: reset
оборачивает внешний блок, shift
действует как call/cc
, но получает в качестве аргумента не глобальное продолжение, а ограниченное — зависимость значения блока reset от значения на месте блока shift. Существуют и другие разновидности, к примеру prompt/control
.
Поддержка языками программирования
Многие языки программирования предоставляют эту возможность под различными именами, например:
- Scheme:
call/cc
(краткая запись дляcall-with-current-continuation
); - Standard ML:
SMLofNJ.Cont.callcc
, также реализовано в Concurrent ML; - Си:
setcontext
и аналоги (UNIX System V и GNU libc); - Ruby:
callcc
; - Smalltalk:
Continuation currentDo:
, в большинстве современных реализаций продолжения могут быть реализованы на чистом Smalltalk, не требуя специальной поддержки в виртуальной машине; - JavaScript:
await
иyield
; - JavaScript Rhino:
Continuation
; - Haskell:
callCC
(в модулеControl.Monad.Cont
); - Factor:
callcc0
иcallcc1
; - Python:
yield
; - Python PyPy:
_continuation.continulet
; - Kotlin:
suspend
, на основе которого реализованыasync
,await
,yield
и некоторые другие сопрограммные конструкции. - Scala: существует плагин для поддержки ограниченных продолжений;
- PHP:
yield
; - C#:
yield return
иawait
.
В любом языке, поддерживающем замыкания, можно писать программы в стиле передачи продолжений и вручную реализовать call/cc
. В частности, это принятая практика в Haskell, где легко строятся «монады, передающие продолжения» (для примера, монада Cont
и трансформер монад ContT
библиотеки mtl
).
Примечания
- ↑ 1 2 3 Fake threads, 1999.
Ссылки
- Продолжение всемирной паутины — о использования продолжений для построения веб-приложений.
- Библиотечка ПФП — в статье «Паттерны использования call with current continuation» (перевод) описана концепция продолжений и дан ряд разнообразных примеров их использования.
- Continuations and Continuation Passing Style — большая коллекция статей о разных видах продолжений и их использовании.
- Tim Peters. Fake threads (was [Python-Dev] ActiveState & fork & Perl). — 1999.