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

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

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

Ограниченные и неограниченные продолжения

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

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

Многие языки программирования предоставляют эту возможность под различными именами, например:

• Scheme: call/cc (краткая запись для call-with-current-continuation)
• SML: SMLofNJ.Cont.callcc
• Си: setcontext et al. (UNIX System V и GNU libc)
• Ruby: callcc
• Smalltalk: Continuation currentDo:, в большинстве современных реализаций продолжения могут быть реализованы на чистом Smalltalk, не требуя специальной поддержки в виртуальной машине.
• Rhino : Continuation
• Haskell : callCC (в модуле Control.Monad.Cont)
• Factor : callcc0 и callcc1
• Python : yield
• Scala : Существует плагин для поддержки ограниченных продолжений.
• PHP: Есть поддержка.

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

См. также

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

Ссылки

• Продолжение всемирной паутины — о использования продолжений для построения веб-приложений.
• Библиотечка ПФП — в статье "Паттерны использования call with current continuation" (перевод) описана концепция продолжений и дан ряд разнообразных примеров их использования.
• Continuations and Continuation Passing Style — большая коллекция статей о разных видах продолжений и их использовании.