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

Запрос «Программирование в стиле передачи продолжений»^[d] перенаправляется сюда. На эту тему нужно создать отдельную статью.

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

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

Понятие

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

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

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

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

Основная статья: Программирование в стиле передачи продолжений  (англ.)

Программирование в стиле передачи продолжений (англ. 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))

Для того чтобы преобразовать классическую функцию в CPS-подобную надо добавить еще один аргумент типа 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.

Стандартная библиотека в модуле 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:

Direct style	Continuation passing style
(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 et al. (UNIX System V и GNU libc).
• Ruby: callcc.
• Smalltalk: Continuation currentDo:, в большинстве современных реализаций продолжения могут быть реализованы на чистом Smalltalk, не требуя специальной поддержки в виртуальной машине.
• JavaScript: await и yeild.
• JavaScript Rhino: Continuation.
• Haskell: callCC (в модуле Control.Monad.Cont).
• Factor: callcc0 и callcc1.
• Python: yield.
• Python PyPy: _continuation.continulet.
• Kotlin: suspend - На основе которого реализованы async, await, yeild и не ограничены этим списком.
• Scala: Существует плагин для поддержки ограниченных продолжений.
• PHP: yield.
• C#: yield return и await.

В любом языке, поддерживающем замыкания, можно писать программы в стиле передачи продолжений (англ. Continuation-passing style, CPS) и вручную реализовать call/cc. В частности это принятая практика в Haskell, где легко строятся «монады, передающие продолжения» (для примера, монада Cont и трансформер монад ContT библиотеки mtl).

См. также

• Замыкание
• Сопрограмма

Ссылки

• Продолжение всемирной паутины — о использования продолжений для построения веб-приложений.
• Библиотечка ПФП — в статье "Паттерны использования call with current continuation" (перевод) описана концепция продолжений и дан ряд разнообразных примеров их использования.
• Continuations and Continuation Passing Style — большая коллекция статей о разных видах продолжений и их использовании.
• Tim Peters. Fake threads (was [Python-Dev] ActiveState & fork & Perl). — 1999.