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

Продолжение(англ.continuation) — абстрактное представление состоянияпрограммыв определённый момент, которое может быть сохранено и использовано для перехода в это состояние. Продолжения содержат всю информацию, чтобы продолжить выполнения программы с определённой точки; состояние глобальных переменных обычно не сохраняется, однако для функциональных языков это несущественно (например, выборочное сохранение и восстановление значений глобальных объектов вSchemeдостигается отдельным механизмом dynamic-wind). Продолжения похожи наgotoБейсикаили макросыsetjmpиlongjmpвСи, так как так же позволяют перейти в любое место программы. Но продолжения, в отличие отgoto, позволяют перейти в участок программы только с определённым состоянием, которое должно быть сохранено заранее, в то время, какgotoпозволяет перейти в участок программы с неинициализированнымипеременными.
Первый язык, реализовавший концепцию продолжений —Scheme, позднее встроенная поддержка продолжений появилась в ряде других языков.
Формально,callcc— этофункция высшего порядка, позволяющая абстрагировать динамический контекст имеющейся функции в виде другой функции, которая и называется «продолжением».
Более наглядно, продолжение — это «вся оставшаяся часть программы от данной точки», или «функция, которая никогда не возвращает управление в точку своего вызова». В курсах функционального программирования объяснение понятия продолжения часто сводится к «расширению (усложнению) понятиясопрограммы», но в дидактическом смысле такое объяснение считается бесполезным. Причина трудности объяснения концепции заключается в том, что продолжения фактически являются альтернативным обоснованием понятия «поведения» («вызова» в самом широком понимании), то есть несут иную семантическую модель, и в этом смысле начальный переход от «обычного» функционального программирования к программированию с интенсивным использованием продолжений можно сравнить с начальным переходом отимперативногопрограммирования кфункциональному.
Продолжения обеспечивают математическое обоснование всегопорядка выполненияпрограммы, отgotoицикловдорекурсии,исключений,генераторов,сопрограммимеханизма возврата. Как следствие, они позволяютреализоватьвсе эти элементы в языке посредством единой конструкции.
Программирование в стиле передачи продолжений (англ.continuation-passing style, CPS) — этостиль программирования, при которомпередача управленияосуществляется через механизм продолжений. Стиль CPS впервые представилиДжеральд Джей СассманиГай Стил-младший, одновременно с языкомScheme.
Программу в «классическом стиле» зачастую можно переписать в стиле передачи продолжений. Например, для задачи вычисления гипотенузы прямоугольного треугольника с «классическим» кодом наHaskell:
можно добавить один аргумент типаF, гдеFозначает функцию из возвращаемого значения исходной функции в произвольный типx, а возвращающим значением сделать этот произвольный типx:
В функцииpyth'вычисляется квадрат отa, и в качестве продолжения передаётся функция (лямбда-выражение), принимающая единственным аргументомaв квадрате. Далее таким же образом вычисляются все последующие промежуточные значения. Для того, чтобы произвести вычисления, в качестве продолжения необходимо передать функцию от одного аргумента, например, функциюid, которая возвращает любое переданное ей значение. Таким образом, выражениеpyth' 3 4 idэквивалентно5.0.
Стандартная haskell-библиотека в модулеControl.Monad.Contсодержит типCont, позволяющий использовать CPS функции в монаде. Функцияpyth'будет выглядеть следующим образом:
Также данный модуль содержит функциюcallCC, имеющую типMonadCont m => ((a -> m b) -> m a) -> m a. Из типа видно, что она принимает единственным аргументом функцию, которая, в свою очередь, также имеет единственным аргументом функцию, прерывающую дальнейшие вычисления. Например, мы можем прервать дальнейшие вычисления, если хотя бы один из аргументов отрицательный:
Примеры CPS в Scheme:
В «чистом» 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.
Многие языки программирования предоставляют эту возможность под различными именами, например:
В любом языке, поддерживающемзамыкания, можно писать программы в стиле передачи продолжений и вручную реализоватьcall/cc. В частности, это принятая практика вHaskell, где легко строятся «монады, передающие продолжения» (для примера, монадаContи трансформер монадContTбиблиотекиmtl).