Введение
Стиль программирования, в котором управление передается явно. В функциональном программировании стиль передачи продолжения (CPS) — это стиль программирования, в котором управление передается явно в виде продолжения. Это противопоставляется прямому стилю, который является обычным стилем программирования. Джеральд Джей Суссман и Гай Л. Стил-младший ввели этот термин в AI Memo 349 (1975), где изложена первая версия языка программирования Scheme. Джон К. Рейнольдс дает подробный обзор многочисленных открытий, связанных с продолжениями. Функция, написанная в стиле передачи продолжения, принимает дополнительный аргумент: явное «продолжение», то есть функцию одного аргумента. Когда функция CPS вычисляет результирующее значение, она «возвращает» его, вызывая функцию продолжения с этим значением в качестве аргумента. Это означает, что при вызове функции CPS вызывающая функция должна предоставить процедуру, которая будет вызвана со «возвращаемым» значением подпрограммы. Представление кода в этой форме делает явными многие вещи, которые подразумеваются в прямом стиле. К ним относятся: возвраты из процедур, которые становятся очевидными как вызовы продолжения; промежуточные значения, которым присваиваются имена; порядок вычисления аргументов, который становится явным; и хвостовые вызовы, которые просто вызывают процедуру с тем же продолжением, без изменений, которое было передано вызывающей стороне. Программы могут быть автоматически преобразованы из прямого стиля в CPS. Функциональные и логические компиляторы часто используют CPS в качестве промежуточного представления, в то время как компилятор для императивного или процедурного языка программирования использует статическую форму однозначного присваивания (SSA). SSA формально эквивалентна подмножеству CPS (за исключением нелокального потока управления, который не возникает при использовании CPS в качестве промежуточного представления). Функциональные компиляторы также могут использовать нормальную форму (ANF) (но только для языков, требующих строгой оценки), вместо «тхунков» (описанных в примерах ниже) в CPS. CPS чаще используется компиляторами, чем программистами, в качестве локального или глобального стиля.
In functional programming, continuation passing style (CPS) is a style of programming in which control is passed explicitly in the form of a continuation. This is contrasted with direct style, which is the usual style of programming. Gerald Jay Sussman and Guy L. Steele, Jr. coined the phrase in AI Memo 349 (1975), which sets out the first version of the Scheme programming language. John C. Reynolds gives a detailed account of the numerous discoveries of continuations. A function written in continuation passing style takes an extra argument: an explicit "continuation"; i. e., a function of one argument. When the CPS function has computed its result value, it "returns" it by calling the continuation function with this value as the argument. That means that when invoking a CPS function, the calling function is required to supply a procedure to be invoked with the subroutine's "return" value. Expressing code in this form makes a number of things explicit which are implicit in direct style. These include: procedure returns, which become apparent as calls to a continuation; intermediate values, which are all given names; order of argument evaluation, which is made explicit; and tail calls, which simply call a procedure with the same continuation, unmodified, that was passed to the caller. Programs can be automatically transformed from direct style to CPS. Functional and logic compilers often use CPS as an intermediate representation where a compiler for an imperative or procedural programming language would use static single assignment form (SSA). SSA is formally equivalent to a subset of CPS (excluding non local control flow, which does not occur when CPS is used as intermediate representation). Functional compilers can also use A normal form (ANF) (but only for languages requiring eager evaluation), rather than with 'thunks' (described in the examples below) in CPS. CPS is used more frequently by compilers than by programmers as a local or global style.
Задние звонки
Каждый вызов в CPS является хвостовым вызовом, и продолжение передаётся явно. Использование CPS без оптимизации хвостовых вызовов (TCO) приведёт не только к потенциальному росту создаваемого продолжения при рекурсии, но и к увеличению стека вызовов. Это обычно нежелательно, но было применено интересными способами — например, в компиляторе Chicken Scheme. Поскольку CPS и TCO устраняют понятие неявного возврата из функции, их совместное использование может исключить необходимость во временном стеке. Ряд компиляторов и интерпретаторов для функциональных языков программирования используют эту возможность новыми способами.
Использование в других областях
Вне компьютерных наук CPS представляет более общий интерес как альтернатива обычному методу составления простых выражений в сложные выражения. Например, в рамках лингвистической семантики Крис Баркер и его коллеги предположили, что определение значений предложений с использованием CPS может объяснить некоторые явления в естественном языке. В математике изоморфизм Карри — Ховарда между компьютерными программами и математическими доказательствами связывает преобразование в стиле передачи продолжения с вариацией двойного отрицания, встраивающего классическую логику в интуиционистскую (конструктивную) логику. В отличие от стандартного преобразования двойного отрицания, которое отображает атомарные высказывания p в ((p → ⊥) → ⊥), стиль передачи продолжения заменяет ⊥ типом конечного выражения. Соответственно, результат получается путем передачи функции идентичности в качестве продолжения выражению CPS, как в вышеприведенном примере. Сама классическая логика связана с непосредственной манипуляцией продолжением программ, как в операторе `call/cc` в Scheme, что является наблюдением Тима Гриффина (использующего тесно связанный оператор управления C).