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

Материал из Википедии — свободной энциклопедии
(перенаправлено с «Продолжение»)
Перейти к: навигация, поиск

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

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

Понятие[править | править исходный текст]

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

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

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

Программирование в стиле передачи продолжений[править | править исходный текст]

Программирование в стиле передачи продолжений (англ. Continuation-passing style, CPS) — это стиль программирования, при котором передача управления осуществляется через механизм продолжений. Стиль CPS впервые представили Джеральд Джей Сассман[en] и Гай Стил мл.[en], одновременно с языком Scheme.

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

Можно заметить, что в чистом CPS фактически не существует самих продолжений — всякий вызов оказывается хвостовым. Если язык не гарантирует оптимизацию хвостовых вызовов (англ. Tail call optimization, TCO), то CPS приводит к лавинообразному росту затрат памяти, т.к. при каждом вложенном вызове callcc растёт и само продолжение, и стек вызовов. Обычно это нежелательно, но временами используется интересным способом (см. компилятор Chicken Scheme[en]). Совместное использование стратегий оптимизации 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
  • Си: 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: Есть поддержка.
  • C#: конструкции yield return и await.

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

См. также[править | править исходный текст]

Примечания[править | править исходный текст]

Ссылки[править | править исходный текст]