В функциональном программировании стиль передачи продолжения ( CPS ) — это стиль программирования, в котором управление передается явно в форме продолжения . Это контрастирует с прямым стилем, который является обычным стилем программирования. Джеральд Джей Сассман и Гай Л. Стил-младший придумали эту фразу в AI Memo 349 (1975), в котором излагается первая версия языка программирования Scheme . [1] [2] Джон К. Рейнольдс дает подробный отчет о многочисленных открытиях продолжений. [3]
Функция, написанная в стиле продолжения-передачи, принимает дополнительный аргумент: явное «продолжение»; т. е. функцию одного аргумента. Когда функция CPS вычислила свое результирующее значение, она «возвращает» его, вызывая функцию продолжения с этим значением в качестве аргумента. Это означает, что при вызове функции CPS вызывающая функция должна предоставить процедуру, которая будет вызвана со значением «возвращаемого» подпрограммы. Выражение кода в этой форме делает явным ряд вещей, которые неявны в прямом стиле. К ним относятся: возвраты процедур, которые становятся очевидными как вызовы продолжения; промежуточные значения, которые являются заданными именами; порядок оценки аргументов, который делается явным; и хвостовые вызовы , которые просто вызывают процедуру с тем же продолжением, неизмененным, которое было передано вызывающей стороне.
Программы могут быть автоматически преобразованы из прямого стиля в CPS. Функциональные и логические компиляторы часто используют CPS в качестве промежуточного представления , тогда как компилятор для императивного или процедурного языка программирования использовал бы статическую форму одиночного присваивания (SSA). [4] SSA формально эквивалентна подмножеству CPS (исключая нелокальный поток управления, который не происходит, когда CPS используется в качестве промежуточного представления). [5] Функциональные компиляторы также могут использовать A-нормальную форму (ANF) (но только для языков, требующих нетерпеливого вычисления), а не с « thunks » (описанными в примерах ниже) в CPS. CPS чаще используется компиляторами, чем программистами в качестве локального или глобального стиля.
В CPS каждая процедура принимает дополнительный аргумент, представляющий, что должно быть сделано с результатом, который вычисляет функция. Это, наряду с ограничительным стилем, запрещающим множество обычно доступных конструкций, используется для раскрытия семантики программ, что упрощает их анализ. Этот стиль также позволяет легко выражать необычные структуры управления, такие как catch/throw или другие нелокальные передачи управления.
Ключ к CPS заключается в том, чтобы помнить, что (a) каждая функция принимает дополнительный аргумент, известный как ее продолжение, и (b) каждый аргумент в вызове функции должен быть либо переменной, либо лямбда-выражением (не более сложным выражением). Это имеет эффект выворачивания выражений "наизнанку", поскольку самые внутренние части выражения должны быть вычислены первыми, таким образом CPS делает явным порядок вычисления, а также поток управления. Некоторые примеры кода в прямом стиле и соответствующие CPS приведены ниже. Эти примеры написаны на языке программирования Scheme ; по соглашению функция продолжения представлена как параметр с именем " k":
Обратите внимание, что в версиях CPS используемые примитивы, такие как +&и , *&сами по себе являются CPS, а не прямым стилем, поэтому для того, чтобы приведенные выше примеры работали в системе Scheme, нам нужно будет написать эти версии CPS примитивов, например, с *&определением следующим образом:
( определить ( *& x y k ) ( k ( * x y ))) Чтобы сделать это в общем случае, мы могли бы написать процедуру преобразования:
( define ( cps-prim f ) ( lambda args ( let (( r ( reverse args ))) (( car r ) ( apply f ( reverse ( cdr r ))))))) ( define *& ( cps-prim * )) ( define +& ( cps-prim + )) Чтобы вызвать процедуру, написанную на CPS, из процедуры, написанной в прямом стиле, необходимо предоставить продолжение, которое получит результат, вычисленный процедурой CPS. В приведенном выше примере (предполагая, что примитивы CPS были предоставлены), мы могли бы вызвать (factorial& 10 (lambda (x) (display x) (newline))).
Существует некоторое разнообразие между компиляторами в способе предоставления примитивных функций в CPS. Выше мы использовали простейшее соглашение, однако иногда предоставляются булевы примитивы, которые принимают два thunk для вызова в двух возможных случаях, поэтому (=& n 0 (lambda (b) (if b ...)))вызов внутри f-aux&определения выше будет записан как (=& n 0 (lambda () (k a)) (lambda () (-& n 1 ...))). Аналогично, иногда ifсам примитив не включен в CPS, и вместо этого предоставляется функция if&, которая принимает три аргумента: булево условие и два thunk, соответствующие двум ветвям условного оператора.
Переводы, показанные выше, показывают, что CPS является глобальным преобразованием. Факториал прямого стиля принимает, как и можно было ожидать, один аргумент; факториал CPS& принимает два: аргумент и продолжение. Любая функция, вызывающая функцию CPS, должна либо предоставить новое продолжение, либо передать свое собственное; любые вызовы из функции CPS в функцию, не являющуюся функцией CPS, будут использовать неявные продолжения. Таким образом, чтобы гарантировать полное отсутствие стека функций, вся программа должна быть в CPS.
В этом разделе мы напишем функцию pyth, которая вычисляет гипотенузу с помощью теоремы Пифагора . Традиционная реализация функции pythвыглядит так:
pow2 :: Плавающий -> Плавающий pow2 x = x ** 2 добавить :: Плавающий -> Плавающий -> Плавающий добавить x y = x + y pyth :: Float -> Float -> Float pyth x y = sqrt ( add ( pow2 x ) ( pow2 y )) Чтобы преобразовать традиционную функцию в CPS, нам нужно изменить ее сигнатуру. Функция получит еще один аргумент типа функции, и ее возвращаемый тип зависит от этой функции:
pow2' :: Плавающий -> ( Плавающий -> а ) -> а pow2' x продолжение = продолжение ( x ** 2 ) add' :: Float -> Float -> ( Float -> a ) -> a add' x y cont = cont ( x + y ) -- Типы a -> (b -> c) и a -> b -> c эквивалентны, поэтому функцию CPS -- можно рассматривать как функцию высшего порядка sqrt' :: Float -> (( Float -> a ) -> a ) sqrt' x = \ cont -> cont ( sqrt x ) pyth' :: Float -> Float -> ( Float -> a ) -> a pyth' x y cont = pow2' x ( \ x2 -> pow2' y ( \ y2 -> add' x2 y2 ( \ anb -> sqrt' anb cont ))) Сначала мы вычисляем квадрат a в pyth'функции и передаем лямбда-функцию как продолжение, которое примет квадрат a в качестве первого аргумента. И так далее, пока не достигнем результата наших вычислений. Чтобы получить результат этой функции, мы можем передать idфункцию как последний аргумент, который возвращает переданное ей значение без изменений: pyth' 3 4 id == 5.0.
Библиотека mtl, которая поставляется с GHC , имеет модуль Control.Monad.Cont. Этот модуль предоставляет тип Cont, который реализует Monad и некоторые другие полезные функции. Следующий фрагмент показывает функцию pyth', использующую Cont:
pow2_m :: Float -> Cont a Float pow2_m a = return ( a ** 2 ) pyth_m :: Float -> Float -> Cont a Float pyth_m a b = do a2 <- pow2_m a b2 <- pow2_m b anb <- cont ( add' a2 b2 ) r <- cont ( sqrt' anb ) return r Синтаксис не только стал чище, но этот тип позволяет нам использовать функцию callCCс типом MonadCont m => ((a -> m b) -> m a) -> m a. Эта функция имеет один аргумент типа функции; этот аргумент функции также принимает функцию, что отменяет все вычисления, идущие после ее вызова. Например, давайте прервем выполнение функции, pythесли хотя бы один из ее аргументов отрицателен, вернув ноль:
pyth_m :: Float -> Float -> Cont a Float pyth_m a b = callCC $ \ exitF -> do -- знак $ помогает избежать скобок: a $ b + c == a (b + c) when ( b < 0 || a < 0 ) ( exitF 0.0 ) -- when :: Applicative f => Bool -> f () -> f () a2 <- pow2_m a b2 <- pow2_m b anb <- cont ( add' a2 b2 ) r <- cont ( sqrt' anb ) return r Программирование с продолжениями также может быть полезным, когда вызывающий не хочет ждать, пока вызываемый завершит работу. Например, в программировании пользовательского интерфейса (UI) процедура может настроить поля диалогового окна и передать их вместе с функцией продолжения в UI-фреймворк. Этот вызов немедленно возвращается, позволяя коду приложения продолжать работу, пока пользователь взаимодействует с диалоговым окном. Как только пользователь нажимает кнопку «ОК», фреймворк вызывает функцию продолжения с обновленными полями. Хотя этот стиль кодирования использует продолжения, он не является полным CPS. [ необходимо разъяснение ]
function verifyName ( ) { fields.name = name ; framework.Show_dialog_box ( fields , firmNameContinuation ) ; } функция подтвердитьИмяПродолжение ( поля ) { имя = поля.имя ; } Похожую идею можно использовать, когда функция должна выполняться в другом потоке или на другом процессоре. Фреймворк может выполнить вызванную функцию в рабочем потоке, а затем вызвать функцию продолжения в исходном потоке с результатами рабочего потока. Это в Java 8 с использованием фреймворка Swing UI:
void buttonHandler () { // Это выполняется в потоке пользовательского интерфейса Swing. // Здесь мы можем получить доступ к виджетам пользовательского интерфейса для получения параметров запроса. int parameter = getField (); new Thread (() -> { // Этот код выполняется в отдельном потоке. // Мы можем выполнять такие действия, как доступ к базе данных или // блокирующему ресурсу, например, сети, для получения данных. int result = lookup ( parameter ); javax.swing.SwingUtilities.invokeLater (() - > { // Этот код выполняется в потоке пользовательского интерфейса и может использовать // извлеченные данные для заполнения виджетов пользовательского интерфейса. setField ( result ) ; } ); }). start () ; } Каждый вызов в CPS является хвостовым вызовом , и продолжение передается явно. Использование CPS без оптимизации хвостового вызова (TCO) приведет к потенциальному росту не только сконструированного продолжения во время рекурсии, но и стека вызовов . Обычно это нежелательно, но использовалось интересными способами — см. компилятор Chicken Scheme . Поскольку CPS и TCO устраняют концепцию неявного возврата функции, их совместное использование может устранить необходимость в стеке времени выполнения. Несколько компиляторов и интерпретаторов для языков функционального программирования используют эту возможность новыми способами. [6]
Стиль передачи продолжения может использоваться для реализации продолжений и операторов управления потоком в функциональном языке, который не имеет продолжений первого класса , но имеет функции первого класса и оптимизацию хвостового вызова . Без оптимизации хвостового вызова можно использовать такие методы, как trampolining , т. е. использование цикла, который итеративно вызывает функции, возвращающие thunk ; без функций первого класса можно даже преобразовать хвостовые вызовы в простые goto в таком цикле.
Написание кода в CPS, хотя и не невозможно, часто подвержено ошибкам. Существуют различные переводы, обычно определяемые как одно- или двухпроходные преобразования чистого лямбда-исчисления , которые преобразуют выражения прямого стиля в выражения CPS. Однако написание в трамплинированном стиле чрезвычайно сложно; при использовании он обычно становится целью какого-то преобразования, например компиляции .
Функции, использующие более одного продолжения, могут быть определены для охвата различных парадигм потока управления, например (в Схеме ):
( define ( /& x y ok err ) ( =& y 0.0 ( lambda ( b ) ( if b ( err ( list "делить на ноль!" x y )) ( ok ( / x y )))))) Следует отметить, что преобразование CPS концептуально является вложением Йонеды . [7] Оно также похоже на вложение лямбда-исчисления в π-исчисление . [8] [9]
За пределами компьютерной науки CPS представляет более общий интерес как альтернатива традиционному методу составления простых выражений в сложные выражения. Например, в лингвистической семантике Крис Баркер и его коллеги предположили, что указание обозначений предложений с использованием CPS может объяснить некоторые явления в естественном языке . [10]
В математике изоморфизм Карри–Ховарда между компьютерными программами и математическими доказательствами связывает перевод в стиле продолжения-передачи с вариацией вложений двойного отрицания классической логики в интуиционистскую (конструктивную) логику . В отличие от обычного перевода двойного отрицания , который отображает атомарные предложения p в (( p → ⊥) → ⊥), стиль продолжения-передачи заменяет ⊥ типом конечного выражения. Соответственно, результат получается путем передачи функции тождества в качестве продолжения выражению CPS, как в приведенном выше примере.
Классическая логика сама по себе относится к непосредственному управлению продолжением программ, как в операторе управления вызовом с текущим продолжением в Scheme , наблюдение Тима Гриффина (использующего тесно связанный оператор управления C). [11]
То есть, в этом стиле программирования с передачей продолжения функция всегда "возвращает" свой результат, "отправляя" его другой функции . Это ключевая идея.
Мы считаем, что это было первое появление термина "
continuous-passing style
" в литературе. Он оказался важной концепцией в анализе исходного кода и преобразовании для компиляторов и других инструментов метапрограммирования. Он также вдохновил ряд других "стилей" выражения программ.