Представление состояния управления компьютерной программой
Continuation
Континуации в программировании: абстрактное представление состояния программы. Реализация контроля, исключений, корутин. Сохранение и возобновление выполнения.
Сравнивайте с английским: нажмите на абзац — оригинал откроется в окне. Кнопка EN под абзацем показывает его прямо в тексте.
Содержание
Введение
Представление состояния управления компьютерной программой
Representation of the control state of a computer program
В информатике, продолжение — это абстрактное представление состояния управления компьютерной программой. Продолжение реализует (реифицирует) состояние управления программой, то есть является структурой данных, представляющей вычислительный процесс в определенный момент его выполнения; эта структура данных становится доступной языку программирования, а не остаётся скрытой в среде выполнения. Продолжения полезны для реализации других механизмов управления в языках программирования, таких как исключения, генераторы, корутины и так далее. "Текущее продолжение" или "продолжение шага вычисления" — это продолжение, которое, с точки зрения выполняющегося кода, было бы получено из текущей точки выполнения программы. Термин "продолжения" также может относиться к продолжениям первого класса, которые предоставляют языку программирования возможность сохранять состояние выполнения в любой точке и возвращаться к нему позже, возможно, многократно.
In computer science, a continuation is an abstract representation of the control state of a computer program. A continuation implements (reifies) the program control state, i. e. the continuation is a data structure that represents the computational process at a given point in the process's execution; the created data structure can be accessed by the programming language, instead of being hidden in the runtime environment. Continuations are useful for encoding other control mechanisms in programming languages such as exceptions, generators, coroutines, and so on. The "current continuation" or "continuation of the computation step" is the continuation that, from the perspective of running code, would be derived from the current point in a program's execution. The term continuations can also be used to refer to first class continuations, which are constructs that give a programming language the ability to save the execution state at any point and return to that point at a later point in the program, possibly multiple times.
История
Самое раннее описание продолжений было сделано Адриааном ван Вейнгаарденом в сентябре 1964 года. Ван Вейнгаарден выступил на рабочей конференции IFIP по языкам описания формальных языков, проходившей в Бадене близ Вены, Австрия. В рамках разработки препроцессора Algol 60 он предложил преобразовать собственные процедуры в стиль передачи продолжений, хотя и не использовал такое название, и его целью было упростить программу и сделать её результат более ясным. Кристофер Стречи, Кристофер П. Уодсворт и Джон К. Рейнольдс сделали термин "продолжение" широко известным в своих работах в области денотационной семантики, которая активно использует продолжения для анализа последовательных программ с точки зрения семантики функционального программирования. Он изобрел продолжение во второй реализации Lisp для IBM 704, хотя и не дал ему названия. [Автор] представляет полную историю открытия продолжений.
The earliest description of continuations was made by Adriaan van Wijngaarden in September 1964. Wijngaarden spoke at the IFIP Working Conference on Formal Language Description Languages held in Baden bei Wien, Austria. As part of a formulation for an Algol 60 preprocessor, he called for a transformation of proper procedures into continuation passing style, though he did not use this name, and his intention was to simplify a program and thus make its result more clear. Christopher Strachey, Christopher P. Wadsworth and John C. Reynolds brought the term continuation into prominence in their work in the field of denotational semantics that makes extensive use of continuations to allow sequential programs to be analysed in terms of functional programming semantics. invented the continuation in his second Lisp implementation for the IBM 704, though he did not name it. gives a complete history of the discovery of continuations.
Реализация
Программа должна выделять место в памяти для переменных, используемых её функциями. Большинство языков программирования используют стек вызовов для хранения необходимых переменных, поскольку он обеспечивает быстрое и простое выделение памяти и её автоматическое освобождение. Другие языки программирования используют кучу для этого, что обеспечивает большую гибкость, но требует больших затрат на выделение и освобождение памяти. Обе эти реализации имеют свои преимущества и недостатки в контексте продолжений.
A program must allocate space in memory for the variables its functions use. Most programming languages use a call stack for storing the variables needed because it allows for fast and simple allocating and automatic deallocation of memory. Other programming languages use a heap for this, which allows for flexibility at a higher cost for allocating and deallocating memory. Both of these implementations have benefits and drawbacks in the context of continuations.
В веб-разработке
Одной из областей практического применения продолжений является веб-программирование. Использование продолжений позволяет программисту абстрагироваться от безгосударственной природы протокола HTTP. В традиционной модели веб-программирования отсутствие состояния отражается в структуре программы, что приводит к коду, построенному вокруг модели, которая крайне неудобна для выражения вычислительных задач. Таким образом, продолжения позволяют создавать код, обладающий полезными свойствами, связанными с инверсией управления, избегая при этом присущих ей недостатков. Статья "Инверсия инверсии управления, или Продолжения против программирования, ориентированного на страницы" дает хорошее представление о применении продолжений в веб-программировании.
One area that has seen practical use of continuations is in Web programming. The use of continuations shields the programmer from the stateless nature of the HTTP protocol. In the traditional model of web programming, the lack of state is reflected in the program's structure, leading to code constructed around a model that lends itself very poorly to expressing computational problems. Thus continuations enable code that has the useful properties associated with inversion of control, while avoiding its problems. "Inverting back the inversion of control or, Continuations versus page centric programming" is a paper that provides a good introduction to continuations applied to web programming.
Виды
Поддержка продолжений сильно различается. Язык программирования поддерживает повторно вызываемые продолжения, если продолжение может быть вызвано многократно (даже после того, как оно уже вернуло значение). Повторно вызываемые продолжения были введены Питером Дж. Ландином с использованием его оператора J (от Jump), который позволял перенести поток управления обратно в середину вызова процедуры. Повторно вызываемые продолжения также называют "реэнтрантными" в языке Racket. Однако такое использование термина "реэнтрантный" может легко быть спутано с его использованием в обсуждениях многопоточности. Более ограниченным типом является продолжение-побег, которое можно использовать для выхода из текущего контекста во внешний. Многие языки, которые явно не поддерживают продолжения, поддерживают обработку исключений, что эквивалентно продолжениям-побегам и может использоваться для тех же целей. Функции setjmp/longjmp в C также эквивалентны: они могут использоваться только для размотки стека. Продолжения-побеги также могут использоваться для реализации устранения хвостовой рекурсии. Обобщением продолжений являются ограниченные продолжения. Операторы продолжений, такие как call/cc, захватывают все оставшееся вычисление в заданной точке программы и не предоставляют способа ограничения этого захвата. Операторы ограниченных продолжений решают эту проблему, предоставляя два отдельных механизма управления: запрос, который ограничивает операцию продолжения, и оператор реификации, такой как shift или control. Продолжения, захваченные с использованием ограниченных операторов, таким образом, представляют собой лишь часть контекста программы.
Support for continuations varies widely. A programming language supports re invocable continuations if a continuation may be invoked repeatedly (even after it has already returned). Re invocable continuations were introduced by Peter J. Landin using his J (for Jump) operator that could transfer the flow of control back into the middle of a procedure invocation. Re invocable continuations have also been called "re entrant" in the Racket language. However this use of the term "re entrant" can be easily confused with its use in discussions of multithreading. A more limited kind is the escape continuation that may be used to escape the current context to a surrounding one. Many languages which do not explicitly support continuations support exception handling, which is equivalent to escape continuations and can be used for the same purposes. C's setjmp/longjmp are also equivalent: they can only be used to unwind the stack. Escape continuations can also be used to implement tail call elimination. One generalization of continuations are delimited continuations. Continuation operators like call/cc capture the entire remaining computation at a given point in the program and provide no way of delimiting this capture. Delimited continuation operators address this by providing two separate control mechanisms: a prompt that delimits a continuation operation and a reification operator such as shift or control. Continuations captured using delimited operators thus only represent a slice of the program context.
Недостатки
Продолжения — это функциональное выражение оператора GOTO, и к ним применимы те же ограничения. Хотя в некоторых особых случаях, например, при веб-программировании, они могут быть разумным выбором, использование продолжений может привести к коду, который сложно понять. Фактически, эзотерический язык программирования Unlambda включает вызов по текущему продолжению в качестве одной из своих особенностей исключительно потому, что выражения с его использованием "обычно крайне сложно отследить". Внешние ссылки ниже иллюстрируют эту концепцию более подробно.
Continuations are the functional expression of the GOTO statement, and the same caveats apply. While they are a sensible option in some special cases such as web programming, use of continuations can result in code that is difficult to follow. In fact, the esoteric programming language Unlambda includes call with current continuation as one of its features solely because expressions involving it "tend to be hopelessly difficult to track down." The external links below illustrate the concept in more detail.