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

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

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

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

Понятие

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

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

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

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

Программирование в стиле передачи продолжений (англ. Continuation-passing style, CPS) — это стиль программирования, при котором передача управления осуществляется через механизм продолжений. Стиль 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, не требуя специальной поддержки в виртуальной машине.
• 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).

См. также

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

Ссылки

• [www.smalltalk.ru/articles/web-continuations.html Продолжение всемирной паутины] — о использования продолжений для построения веб-приложений.
• [fprog.ru/lib/ Библиотечка ПФП] — в статье "Паттерны использования call with current continuation" (перевод) описана концепция продолжений и дан ряд разнообразных примеров их использования.
• [library.readscheme.org/page6.html Continuations and Continuation Passing Style] — большая коллекция статей о разных видах продолжений и их использовании.
• Tim Peters [mail.python.org/pipermail/python-dev/1999-July/000467.html Fake threads (was [Python-Dev] ActiveState & fork & Perl)]. — 1999.

Отрывок, характеризующий Продолжение (информатика)

– Ты что нибудь не то говоришь. Да я никогда не приказывала уезжать… – сказала княжна Марья. – Позови Дронушку.
Пришедший Дрон подтвердил слова Дуняши: мужики пришли по приказанию княжны.
– Да я никогда не звала их, – сказала княжна. – Ты, верно, не так передал им. Я только сказала, чтобы ты им отдал хлеб.
Дрон, не отвечая, вздохнул.
– Если прикажете, они уйдут, – сказал он.
– Нет, нет, я пойду к ним, – сказала княжна Марья
Несмотря на отговариванье Дуняши и няни, княжна Марья вышла на крыльцо. Дрон, Дуняша, няня и Михаил Иваныч шли за нею. «Они, вероятно, думают, что я предлагаю им хлеб с тем, чтобы они остались на своих местах, и сама уеду, бросив их на произвол французов, – думала княжна Марья. – Я им буду обещать месячину в подмосковной, квартиры; я уверена, что Andre еще больше бы сделав на моем месте», – думала она, подходя в сумерках к толпе, стоявшей на выгоне у амбара.
Толпа, скучиваясь, зашевелилась, и быстро снялись шляпы. Княжна Марья, опустив глаза и путаясь ногами в платье, близко подошла к ним. Столько разнообразных старых и молодых глаз было устремлено на нее и столько было разных лиц, что княжна Марья не видала ни одного лица и, чувствуя необходимость говорить вдруг со всеми, не знала, как быть. Но опять сознание того, что она – представительница отца и брата, придало ей силы, и она смело начала свою речь.
– Я очень рада, что вы пришли, – начала княжна Марья, не поднимая глаз и чувствуя, как быстро и сильно билось ее сердце. – Мне Дронушка сказал, что вас разорила война. Это наше общее горе, и я ничего не пожалею, чтобы помочь вам. Я сама еду, потому что уже опасно здесь и неприятель близко… потому что… Я вам отдаю все, мои друзья, и прошу вас взять все, весь хлеб наш, чтобы у вас не было нужды. А ежели вам сказали, что я отдаю вам хлеб с тем, чтобы вы остались здесь, то это неправда. Я, напротив, прошу вас уезжать со всем вашим имуществом в нашу подмосковную, и там я беру на себя и обещаю вам, что вы не будете нуждаться. Вам дадут и домы и хлеба. – Княжна остановилась. В толпе только слышались вздохи.
– Я не от себя делаю это, – продолжала княжна, – я это делаю именем покойного отца, который был вам хорошим барином, и за брата, и его сына.
Она опять остановилась. Никто не прерывал ее молчания.
– Горе наше общее, и будем делить всё пополам. Все, что мое, то ваше, – сказала она, оглядывая лица, стоявшие перед нею.
Все глаза смотрели на нее с одинаковым выражением, значения которого она не могла понять. Было ли это любопытство, преданность, благодарность, или испуг и недоверие, но выражение на всех лицах было одинаковое.
– Много довольны вашей милостью, только нам брать господский хлеб не приходится, – сказал голос сзади.
– Да отчего же? – сказала княжна.
Никто не ответил, и княжна Марья, оглядываясь по толпе, замечала, что теперь все глаза, с которыми она встречалась, тотчас же опускались.
– Отчего же вы не хотите? – спросила она опять.
Никто не отвечал.
Княжне Марье становилось тяжело от этого молчанья; она старалась уловить чей нибудь взгляд.
– Отчего вы не говорите? – обратилась княжна к старому старику, который, облокотившись на палку, стоял перед ней. – Скажи, ежели ты думаешь, что еще что нибудь нужно. Я все сделаю, – сказала она, уловив его взгляд. Но он, как бы рассердившись за это, опустил совсем голову и проговорил:
– Чего соглашаться то, не нужно нам хлеба.
– Что ж, нам все бросить то? Не согласны. Не согласны… Нет нашего согласия. Мы тебя жалеем, а нашего согласия нет. Поезжай сама, одна… – раздалось в толпе с разных сторон. И опять на всех лицах этой толпы показалось одно и то же выражение, и теперь это было уже наверное не выражение любопытства и благодарности, а выражение озлобленной решительности.
– Да вы не поняли, верно, – с грустной улыбкой сказала княжна Марья. – Отчего вы не хотите ехать? Я обещаю поселить вас, кормить. А здесь неприятель разорит вас…
Но голос ее заглушали голоса толпы.
– Нет нашего согласия, пускай разоряет! Не берем твоего хлеба, нет согласия нашего!
Княжна Марья старалась уловить опять чей нибудь взгляд из толпы, но ни один взгляд не был устремлен на нее; глаза, очевидно, избегали ее. Ей стало странно и неловко.
– Вишь, научила ловко, за ней в крепость иди! Дома разори да в кабалу и ступай. Как же! Я хлеб, мол, отдам! – слышались голоса в толпе.
Княжна Марья, опустив голову, вышла из круга и пошла в дом. Повторив Дрону приказание о том, чтобы завтра были лошади для отъезда, она ушла в свою комнату и осталась одна с своими мыслями.


Долго эту ночь княжна Марья сидела у открытого окна в своей комнате, прислушиваясь к звукам говора мужиков, доносившегося с деревни, но она не думала о них. Она чувствовала, что, сколько бы она ни думала о них, она не могла бы понять их. Она думала все об одном – о своем горе, которое теперь, после перерыва, произведенного заботами о настоящем, уже сделалось для нее прошедшим. Она теперь уже могла вспоминать, могла плакать и могла молиться. С заходом солнца ветер затих. Ночь была тихая и свежая. В двенадцатом часу голоса стали затихать, пропел петух, из за лип стала выходить полная луна, поднялся свежий, белый туман роса, и над деревней и над домом воцарилась тишина.
Одна за другой представлялись ей картины близкого прошедшего – болезни и последних минут отца. И с грустной радостью она теперь останавливалась на этих образах, отгоняя от себя с ужасом только одно последнее представление его смерти, которое – она чувствовала – она была не в силах созерцать даже в своем воображении в этот тихий и таинственный час ночи. И картины эти представлялись ей с такой ясностью и с такими подробностями, что они казались ей то действительностью, то прошедшим, то будущим.
То ей живо представлялась та минута, когда с ним сделался удар и его из сада в Лысых Горах волокли под руки и он бормотал что то бессильным языком, дергал седыми бровями и беспокойно и робко смотрел на нее.
«Он и тогда хотел сказать мне то, что он сказал мне в день своей смерти, – думала она. – Он всегда думал то, что он сказал мне». И вот ей со всеми подробностями вспомнилась та ночь в Лысых Горах накануне сделавшегося с ним удара, когда княжна Марья, предчувствуя беду, против его воли осталась с ним. Она не спала и ночью на цыпочках сошла вниз и, подойдя к двери в цветочную, в которой в эту ночь ночевал ее отец, прислушалась к его голосу. Он измученным, усталым голосом говорил что то с Тихоном. Ему, видно, хотелось поговорить. «И отчего он не позвал меня? Отчего он не позволил быть мне тут на месте Тихона? – думала тогда и теперь княжна Марья. – Уж он не выскажет никогда никому теперь всего того, что было в его душе. Уж никогда не вернется для него и для меня эта минута, когда бы он говорил все, что ему хотелось высказать, а я, а не Тихон, слушала бы и понимала его. Отчего я не вошла тогда в комнату? – думала она. – Может быть, он тогда же бы сказал мне то, что он сказал в день смерти. Он и тогда в разговоре с Тихоном два раза спросил про меня. Ему хотелось меня видеть, а я стояла тут, за дверью. Ему было грустно, тяжело говорить с Тихоном, который не понимал его. Помню, как он заговорил с ним про Лизу, как живую, – он забыл, что она умерла, и Тихон напомнил ему, что ее уже нет, и он закричал: „Дурак“. Ему тяжело было. Я слышала из за двери, как он, кряхтя, лег на кровать и громко прокричал: „Бог мой!Отчего я не взошла тогда? Что ж бы он сделал мне? Что бы я потеряла? А может быть, тогда же он утешился бы, он сказал бы мне это слово“. И княжна Марья вслух произнесла то ласковое слово, которое он сказал ей в день смерти. «Ду ше нь ка! – повторила княжна Марья это слово и зарыдала облегчающими душу слезами. Она видела теперь перед собою его лицо. И не то лицо, которое она знала с тех пор, как себя помнила, и которое она всегда видела издалека; а то лицо – робкое и слабое, которое она в последний день, пригибаясь к его рту, чтобы слышать то, что он говорил, в первый раз рассмотрела вблизи со всеми его морщинами и подробностями.