В функциональном программировании стиль передачи продолжения ( CPS ) — это стиль программирования, в котором управление передается явно в форме продолжения . Это контрастирует с прямым стилем, который является обычным стилем программирования. Джеральд Джей Сассман и Гай Л. Стил-младший придумали эту фразу в AI Memo 349 (1975), в которой изложена первая версия языка программирования Scheme . [1] [2] Джон К. Рейнольдс дает подробный отчет о многочисленных открытиях продолжений. [3]
Функция, написанная в стиле передачи продолжения, принимает дополнительный аргумент: явное «продолжение»; т.е. функция одного аргумента. Когда функция CPS вычислила свое значение результата, она «возвращает» его, вызывая функцию продолжения с этим значением в качестве аргумента. Это означает, что при вызове функции CPS вызывающая функция должна предоставить вызываемой процедуре «возвращаемое» значение подпрограммы. Выражение кода в такой форме делает явными многие вещи, которые неявно подразумеваются в прямом стиле. К ним относятся: возвраты процедур, которые проявляются как вызовы продолжения; промежуточные значения, которым присвоены имена; порядок вычисления аргументов, который сделан явным; и хвостовые вызовы , которые просто вызывают процедуру с тем же неизмененным продолжением, которое было передано вызывающей стороне.
Программы могут быть автоматически преобразованы из прямого стиля в CPS. Функциональные и логические компиляторы часто используют CPS в качестве промежуточного представления , тогда как компилятор для императивного или процедурного языка программирования будет использовать статическую форму одиночного присваивания (SSA). [4] SSA формально эквивалентен подмножеству CPS (исключая нелокальный поток управления, который не возникает, когда CPS используется в качестве промежуточного представления). [5] Функциональные компиляторы также могут использовать A-нормальную форму (ANF) (но только для языков, требующих быстрой оценки), а не с помощью « thunk » (описанных в примерах ниже) в CPS. CPS чаще используется компиляторами , чем программистами, как локальный или глобальный стиль.
В CPS каждая процедура принимает дополнительный аргумент, представляющий, что следует делать с результатом, который вычисляет функция. Это, наряду с ограничительным стилем, запрещающим различные обычно доступные конструкции, используется для раскрытия семантики программ, что упрощает их анализ. Этот стиль также позволяет легко выражать необычные структуры управления, такие как захват/бросок или другие нелокальные передачи управления.
Ключом к CPS является запоминание того, что (а) каждая функция принимает дополнительный аргумент, известный как ее продолжение, и (б) каждый аргумент в вызове функции должен быть либо переменной, либо лямбда-выражением (а не более сложным выражением). Это приводит к переворачиванию выражений «наизнанку», поскольку сначала должны быть вычислены самые внутренние части выражения, таким образом, CPS четко определяет порядок вычисления, а также поток управления. Некоторые примеры кода в прямом стиле и соответствующие CPS приведены ниже. Эти примеры написаны на языке программирования Scheme ; по соглашению функция продолжения представлена как параметр с именем " k":
Обратите внимание, что в версиях CPS используемые примитивы, как +&и *&сами CPS, а не прямой стиль, поэтому, чтобы приведенные выше примеры работали в системе Scheme, нам нужно будет написать эти версии примитивов CPS, например, *&определенные следующим образом:
( определить ( *& x y k ) ( k ( * x y ))) В общем, чтобы сделать это, мы могли бы написать процедуру преобразования:
( define ( cps-prim f ) ( лямбда- аргументы ( let (( r ( обратные аргументы ))) (( car r ) ( Apply f ( verse ( cdr r ))))))) ( define *& ( cps-prim * )) ( определить +& ( cps-prim + )) Чтобы вызвать процедуру, написанную на CPS, из процедуры, написанной в прямом стиле, необходимо предоставить продолжение, которое будет получать результат, вычисленный процедурой CPS. В приведенном выше примере (при условии, что примитивы CPS предоставлены) мы могли бы вызвать (factorial& 10 (lambda (x) (display x) (newline))).
Между компиляторами существуют некоторые различия в способах предоставления примитивных функций в CPS. Выше мы использовали простейшее соглашение, однако иногда предоставляются логические примитивы, которые требуют двух переходников для вызова в двух возможных случаях, поэтому вызов (=& n 0 (lambda (b) (if b ...)))внутри f-aux&определения выше будет записан вместо этого как (=& n 0 (lambda () (k a)) (lambda () (-& n 1 ...))). Точно так же иногда ifсам примитив не включается в CPS, а вместо него предоставляется функция if&, принимающая три аргумента: логическое условие и два преобразователя, соответствующие двум ветвям условного выражения.
Приведенные выше переводы показывают, что CPS представляет собой глобальную трансформацию. Как и следовало ожидать, факториал прямого типа принимает один аргумент; факториал& CPS принимает два аргумента: аргумент и продолжение. Любая функция, вызывающая функцию CPS, должна либо предоставить новое продолжение, либо передать свое собственное; любые вызовы функции, поддерживающей CPS, к функции, не поддерживающей CPS, будут использовать неявные продолжения. Таким образом, чтобы обеспечить полное отсутствие стека функций, вся программа должна находиться в CPS.
В этом разделе мы напишем функцию pyth, вычисляющую гипотенузу по теореме Пифагора . Традиционная реализация функции pythвыглядит так:
pow2 :: Float -> Float pow2 x = x ** 2 add :: Float -> Float -> Float add x y = x + y pyth :: Float -> Float -> Float pyth x y = sqrt ( add ( pow2 x ) ( pow2 y )) Чтобы преобразовать традиционную функцию в CPS, нам нужно изменить ее сигнатуру. Функция получит еще один аргумент типа функции, и ее тип возвращаемого значения зависит от этой функции:
pow2' :: Float -> ( Float -> a ) -> a pow2' x cont = cont ( 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 и продолжение ) )) Сначала мы вычисляем квадрат функции in 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), когда ( b < 0 || a < 0 ) ( exitF 0.0 ) -- When :: Аппликативный f => Bool -> f () -> f () a2 <- pow2_m a b2 <- pow2_m b anb <- cont ( add' a2 b2 ) r <- cont ( sqrt' anb ) return r Программирование с использованием продолжений также может быть полезно, когда вызывающая сторона не хочет ждать завершения выполнения вызываемой программы. Например, в программировании пользовательского интерфейса (UI) процедура может настроить поля диалогового окна и передать их вместе с функцией продолжения в структуру пользовательского интерфейса. Этот вызов сразу же возвращается, позволяя коду приложения продолжать работу, пока пользователь взаимодействует с диалоговым окном. Как только пользователь нажимает кнопку «ОК», платформа вызывает функцию продолжения с обновленными полями. Хотя этот стиль кодирования использует продолжения, он не является полным CPS. [ нужны разъяснения ]
функция подтвержденияИмя () { поля . имя = имя ; рамки . Show_dialog_box ( поля , подтверждениеИмениПродолжение ); } функция подтвержденияИмяПродолжение ( поля ) { имя = поля . имя ; } Аналогичную идею можно использовать, когда функция должна выполняться в другом потоке или на другом процессоре. Платформа может выполнить вызванную функцию в рабочем потоке, а затем вызвать функцию продолжения в исходном потоке с результатами рабочего потока. Это в Java 8 с использованием инфраструктуры Swing UI:
void buttonHandler () { // Это выполняется в потоке пользовательского интерфейса Swing. // Здесь мы можем получить доступ к виджетам пользовательского интерфейса, чтобы получить параметры запроса. параметр int = getField (); new Thread (() -> { // Этот код выполняется в отдельном потоке. // Мы можем делать такие вещи, как доступ к базе данных или // блокирующему ресурсу, например сети, для получения данных. int result = поиск ( параметр ); Явакс . качать . SwingUtilities . ignoreLater (() -> { // Этот код выполняется в потоке пользовательского интерфейса и может использовать // полученные данные для заполнения виджетов пользовательского интерфейса. setField ( result ); }); }). начинать (); } Каждый вызов в CPS является хвостовым вызовом , и продолжение передается явно. Использование CPS без оптимизации хвостового вызова (TCO) приведет к потенциальному росту во время рекурсии не только созданного продолжения, но и стека вызовов . Обычно это нежелательно, но его можно использовать интересным образом — см. компилятор Chicken Scheme . Поскольку CPS и TCO устраняют концепцию неявного возврата функции, их совместное использование может устранить необходимость в стеке времени выполнения. Некоторые компиляторы и интерпретаторы функциональных языков программирования используют эту возможность по-новому. [6]
Стиль передачи продолжения можно использовать для реализации продолжений и операторов потока управления на функциональном языке, который не имеет первоклассных продолжений , но имеет первоклассные функции и оптимизацию хвостовых вызовов . Без оптимизации хвостового вызова можно использовать такие методы, как трамплин , то есть использование цикла, который итеративно вызывает функции, возвращающие thunk ; без первоклассных функций в таком цикле можно даже преобразовать хвостовые вызовы в просто переходы.
Написание кода в CPS хотя и не невозможно, но часто подвержено ошибкам. Существуют различные переводы, обычно определяемые как одно- или двухпроходные преобразования чистого лямбда-исчисления , которые преобразуют выражения прямого стиля в выражения CPS. Однако писать батутным стилем чрезвычайно сложно; при использовании он обычно является целью какого-либо преобразования, например компиляции .
Функции, использующие более одного продолжения, могут быть определены для захвата различных парадигм потока управления, например (в Scheme ):
( define ( /& x y ok err ) ( =& y 0.0 ( лямбда ( b ) ( if b ( err ( список «деление на ноль!» x y )) ( ok ( / x y )))))) Следует отметить, что преобразование CPS концептуально является вложением Йонеды . [7] Это также похоже на встраивание лямбда-исчисления в π-исчисление . [8] [9]
За пределами информатики CPS представляет более общий интерес как альтернатива традиционному методу составления простых выражений в сложные. Например, в рамках лингвистической семантики Крис Баркер и его коллеги предположили, что определение значений предложений с использованием CPS может объяснить определенные явления в естественном языке . [10]
В математике изоморфизм Карри -Ховарда между компьютерными программами и математическими доказательствами связывает перевод в стиле передачи продолжения с вариацией вложений двойного отрицания классической логики в интуиционистскую (конструктивную) логику . В отличие от обычного перевода с двойным отрицанием , который отображает атомарные предложения p в (( p → ⊥) → ⊥), стиль передачи продолжения заменяет ⊥ типом конечного выражения. Соответственно, результат получается путем передачи тождественной функции как продолжения выражения CPS, как в приведенном выше примере.
Классическая логика сама по себе связана с непосредственным управлением продолжением программ, как в операторе управления вызовом с текущим продолжением Scheme , наблюдении Тима Гриффина (с использованием тесно связанного оператора управления C). [11]
То есть в этом стиле программирования с передачей продолжения функция всегда «возвращает» свой результат, «отправляя» его другой функции . Это ключевая идея.
Мы полагаем, что это первое упоминание термина «
стиль продолжения-передачи
» в литературе.
Это оказалось важной концепцией анализа и преобразования исходного кода для компиляторов и других инструментов метапрограммирования.
Он также вдохновил множество других «стилей» программного выражения.