В функциональном программировании , продолжение обходя стиль ( CPS ) является стилем программирования , в котором управление передается в явном виде продолжения . Это контрастирует с прямым стилем , который является обычным стилем программирования. Джеральд Джей Сассман и Гай Л. Стил-младший придумали эту фразу в AI Memo 349 (1975), в которой изложена первая версия языка программирования Scheme . [1] [2] Джон К. Рейнольдс дает подробный отчет о многочисленных открытиях продолжений. [3]
Функция, написанная в стиле передачи продолжения, принимает дополнительный аргумент: явное «продолжение», то есть функцию одного аргумента. Когда функция CPS вычисляет значение своего результата, она «возвращает» его, вызывая функцию продолжения с этим значением в качестве аргумента. Это означает, что при вызове функции CPS вызывающая функция должна предоставить процедуру, которая будет вызываться с «возвращаемым» значением подпрограммы. Выражение кода в этой форме делает ряд явных явлений, которые неявны в прямом стиле. К ним относятся: возврат процедуры, который проявляется как вызов продолжения; промежуточные значения, которым всем присвоены имена; порядок вычисления аргументов, который сделан явным; и хвостовые вызовы , которые просто вызывают процедуру с тем же продолжением, без изменений, которое было передано вызывающей стороне.
Программы могут быть автоматически преобразованы из прямого стиля в CPS. Функциональные и логические компиляторы часто используют CPS в качестве промежуточного представления, тогда как компилятор для императивного или процедурного языка программирования будет использовать статическую форму одиночного присваивания (SSA). [4] SSA формально эквивалентен подмножеству CPS (исключая нелокальный поток управления, который не происходит, когда CPS используется в качестве промежуточного представления). [5] Функциональные компиляторы также могут использовать A-нормальную форму (ANF) (но только для языков, требующих активной оценки), а не с « преобразователями » (описанными в примерах ниже) в CPS. CPS чаще используется компиляторами, чем программистами как локальный или глобальный стиль.
Примеры
В CPS каждая процедура принимает дополнительный аргумент, представляющий, что следует делать с результатом, вычисляемым функцией. Это, наряду с ограничительным стилем, запрещающим множество обычно доступных конструкций, используется для раскрытия семантики программ, что упрощает их анализ. Этот стиль также позволяет легко выражать необычные структуры управления, такие как захват / бросок или другие нелокальные передачи управления.
Ключ к CPS - помнить, что (а) каждая функция принимает дополнительный аргумент, известный как ее продолжение, и (б) каждый аргумент в вызове функции должен быть либо переменной, либо лямбда-выражением (не более сложным выражением). Это приводит к переворачиванию выражений «наизнанку», потому что в первую очередь должны быть оценены самые внутренние части выражения, таким образом, CPS делает явным порядок оценки, а также поток управления. Ниже приведены некоторые примеры кода в прямом стиле и соответствующие CPS. Эти примеры написаны на языке программирования Scheme ; по соглашению функция продолжения представлена как параметр с именем " k
":
( определить ( pyth x y ) ( sqrt ( + ( * x x ) ( * y y )))) | ( определить ( pyth & x y k ) ( * & x x ( lambda ( x2 ) ( * & y y ( lambda ( y2 ) ( + & x2 y2 ( lambda ( x2py2 ) ( sqrt & x2py2 k )))))))) |
( определить ( факториал n ) ( если ( = n 0 ) 1 ; НЕ хвостовая рекурсия ( * n ( факториал ( - n 1 ))))) | ( define ( factorial & n k ) ( = & n 0 ( lambda ( b ) ( if b ; растущее продолжение ( k 1 ) ; в рекурсивном вызове ( - & n 1 ( lambda ( nm1 ) ( factorial & nm1 ( lambda ( f ) ( * & н ф к ))))))))) |
( define ( факториал n ) ( f-aux n 1 )) ( define ( f-aux n a ) ( if ( = n 0 ) a ; хвост-рекурсивный ( 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 ) ; в рекурсивном вызов ( - & п 1 ( лямбда ( NM1 ) ( * & п ( лямбда ( NTA ) ( F-AUX & NM1 NTA к ))))))))) |
Обратите внимание, что в версиях 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 * )) ( определить + & ( 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-ed, должна либо предоставить новое продолжение, либо передать свое собственное; любые вызовы из функции CPS-ed в функцию, не являющуюся CPS, будут использовать неявные продолжения. Таким образом, чтобы гарантировать полное отсутствие стека функций, вся программа должна быть в CPS.
CPS в Haskell
В этом разделе мы напишем функцию, pyth
которая вычисляет гипотенузу, используя теорему Пифагора . Традиционная реализация pyth
функции выглядит так:
pow2 :: Float -> Float pow2 a = a ** 2add :: Float -> Float -> Float добавить a b = a + bpyth :: Float -> Float -> Float pyth a b = sqrt ( добавить ( pow2 a ) ( pow2 b ))
Чтобы преобразовать традиционную функцию в CPS, нам нужно изменить ее сигнатуру. Функция получит еще один аргумент типа функции, и его тип возврата зависит от этой функции:
pow2' :: Float -> ( Float -> ) -> pow2' прод = продолжение ( ** 2 ) add ' :: Float -> Float -> ( Float -> a ) -> a add' a b cont = cont ( a + b )- Типы a -> (b -> c) и a -> b -> c эквивалентны, поэтому функция CPS - может рассматриваться как функция более высокого порядка sqrt ' :: Float -> (( Float -> a ) -> а ) sqrt ' a = \ cont -> cont ( sqrt a )pyth ' :: Float -> Float -> ( Float -> ) -> pyth' б прод = pow2' ( \ a2 -> pow2' б ( \ b2 -> добавить» a2 b2 ( \ АНБ -> SQRT» АНБ продолжение )))
Сначала мы вычислим квадрат в функции и передать функцию лямбды как продолжение , которое будет принимать квадрат в качестве первого аргумента. И так до тех пор, пока не дойдем до результата наших расчетов. Для того, чтобы получить результат этой функции мы можем передать функцию в качестве последнего аргумента , который возвращает значение , которое было передано ему неизменным: .pyth'
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 -> прод Float pyth_m а б = сделать a2 <- pow2_m b2 <- pow2_m б АНБ <- продолжение ( добавить ' a2 b2 ) г <- продолжение ( SQRT' АНБ ) возвращение г
Не только стал чище синтаксис, но и этот тип позволяет нам использовать функцию 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 || < 0 ) ( exitF 0.0 ) - когда :: Аппликативный е => Bool -> F () -> F () а2 <- pow2_m б2 <- pow2_m б АНБ <- продолжение ( добавить» а2 б2 ) г <- продолжение ( SQRT» АНБ ) возвращение г
Продолжения как объекты
Программирование с продолжениями также может быть полезно, когда вызывающий абонент не хочет ждать, пока вызываемый абонент завершит работу. Например, при программировании пользовательского интерфейса (UI) подпрограмма может настраивать поля диалогового окна и передавать их вместе с функцией продолжения в структуру UI. Этот вызов сразу же возвращается, позволяя коду приложения продолжать работу, пока пользователь взаимодействует с диалоговым окном. Как только пользователь нажимает кнопку «ОК», платформа вызывает функцию продолжения с обновленными полями. Хотя этот стиль кодирования использует продолжения, это не полная CPS. [ требуется разъяснение ]
function confirmName () { fields . name = name ; рамки . Show_dialog_box ( поля , confirmNameContinuation ); }функция confirmNameContinuation ( fields ) { name = fields . имя ; }
Похожая идея может использоваться, когда функция должна выполняться в другом потоке или на другом процессоре. Платформа может выполнить вызываемую функцию в рабочем потоке, а затем вызвать функцию продолжения в исходном потоке с результатами рабочего. Это в Java с использованием инфраструктуры Swing UI:
void buttonHandler () { // Это выполняется в потоке пользовательского интерфейса Swing. // Здесь мы можем получить доступ к виджетам пользовательского интерфейса, чтобы получить параметры запроса. последний параметр типа int = getField (); new Thread ( new Runnable () { public void run () { // Этот код выполняется в отдельном потоке. // Мы можем делать такие вещи, как доступ к базе данных или // блокирующий ресурс, например сеть, для получения данных. final int result = поиск ( параметр ); javax . качели . SwingUtilities . invokeLater ( new Runnable () { public void run () { // Этот код выполняется в потоке пользовательского интерфейса и может использовать // полученные данные для заполнения виджетов пользовательского интерфейса. setField ( result ); } }); } }). start (); }
Используя лямбда-нотацию Java 8, приведенный выше код сокращается до ( final
ключевое слово может быть пропущено):
void buttonHandler () { параметр int = getField (); новый поток (() -> { int result = lookup ( параметр ); javax . swing . SwingUtilities . invokeLater (() -> setField ( результат )); }). start (); }
Хвостовые крики
Каждый вызов в CPS - это хвостовой вызов , и продолжение передается явно. Использование CPS без оптимизации хвостовых вызовов (TCO) приведет к потенциальному росту не только сконструированного продолжения во время рекурсии, но и стека вызовов . Обычно это нежелательно, но использовалось интересным образом - см. Компилятор Chicken Scheme . Поскольку CPS и TCO исключают концепцию неявного возврата функции, их совместное использование может устранить необходимость в стеке времени выполнения. Некоторые компиляторы и интерпретаторы для языков функционального программирования используют эту возможность по-новому. [6]
Использование и реализация
Стиль передачи продолжения может использоваться для реализации продолжений и операторов потока управления на функциональном языке, который не имеет первоклассных продолжений, но имеет первоклассные функции и оптимизацию хвостового вызова . Без оптимизации хвостового вызова, такие методы, как батут , то есть с помощью цикла , что итеративно вызывает стук -returning функция, может быть использована; без первоклассных функций в таком цикле можно даже преобразовать хвостовые вызовы в просто gotos.
Написание кода на CPS, хотя и возможно, часто подвержено ошибкам. Существуют различные переводы, обычно определяемые как одно- или двухпроходные преобразования чистого лямбда-исчисления , которые преобразуют выражения прямого стиля в выражения CPS. Однако писать на батуте чрезвычайно сложно; при использовании он обычно является целью некоторого преобразования, например компиляции .
Функции, использующие более одного продолжения, могут быть определены для захвата различных парадигм потока управления, например (на схеме ):
( определить ( / & x y ok err ) ( = & y 0.0 ( lambda ( b ) ( if b ( err ( list "div by zero!" x y )) ( ok ( / x y ))))))
Следует отметить, что преобразование CPS концептуально является вложением Йонеды . [7] Это также похоже на вложение лямбда-исчисления в π-исчисление . [8] [9]
Использование в других областях
Помимо информатики , CPS представляет более общий интерес как альтернатива традиционному методу объединения простых выражений в сложные. Например, в рамках лингвистической семантики , Крис Баркер и его коллеги предположили , что определение денота- предложений с использованием КП могут объяснить определенные явления в естественном языке . [10]
В математике , тот Карри-Говард изоморфизм между компьютерными программами и математическими доказательствами относится продолжение обходя перевод стиля к изменению двойного отрицания вложений в классических логиках в интуиционистскую (конструктивную) логику . В отличие от обычного перевода двойного отрицания , который отображает атомарные предложения p в (( p → ⊥) → ⊥), стиль передачи продолжения заменяет ⊥ типом окончательного выражения. Соответственно, результат получается путем передачи функции идентификации в качестве продолжения выражения в стиле CPS, как в приведенном выше примере.
Сама классическая логика относится к непосредственному управлению продолжением программ, как в операторе управления вызовом с текущим продолжением в Scheme , наблюдение Тима Гриффина (с использованием тесно связанного с ним управляющего оператора C). [11]
Смотрите также
- Рекурсия хвоста через прыжки на батуте
Заметки
- ^ Сассман, Джеральд Джей ; Стил, Гай Л. младший (декабрь 1975 г.).
То есть, в этом продолжение обходя стиля программирования , функция всегда «возвращает» его результат с помощью «отправки» это на другую функцию . Это ключевая идея.
. Памятка AI . 349 : 19. - ^ Сассман, Джеральд Джей ; Стил, Гай Л., младший (декабрь 1998 г.). «Схема: интерпретатор для расширенного лямбда-исчисления» (перепечатка) . Вычисление высшего порядка и символическое вычисление . 11 (4): 405–439. DOI : 10,1023 / A: 1010035624696 .
Мы полагаем, что это первое появление в литературе термина « стиль продолжения передачи ». Оказалось, что это важная концепция в анализе и преобразовании исходного кода для компиляторов и других инструментов метапрограммирования. Он также вдохновил на создание множества других «стилей» программного выражения.
- ^ Рейнольдс, Джон С. (1993). «Открытия продолжений». Лисп и символьные вычисления . 6 (3–4): 233–248. CiteSeerX 10.1.1.135.4705 . DOI : 10.1007 / bf01019459 .
- ^ * Аппель, Эндрю В. (апрель 1998 г.). «SSA - это функциональное программирование». Уведомления ACM SIGPLAN . 33 (4): 17–20. CiteSeerX 10.1.1.34.3282 . DOI : 10.1145 / 278283.278285 .
- ^ * Келси, Ричард А. (март 1995 г.). «Соответствие между стилем прохождения продолжения и статической формой одиночного назначения». Уведомления ACM SIGPLAN . 30 (3): 13–22. CiteSeerX 10.1.1.489.930 . DOI : 10.1145 / 202530.202532 .
- ^ Аппель, Эндрю В. (1992). Компиляция с продолжениями. Издательство Кембриджского университета. ISBN 0-521-41695-7 .
- ^ Майк Стэй, «Продолжение проходящего преобразования и вложения Йонеды»
- ↑ Майк Стей, «Исчисление числа Пи II»
- ^ Будоль, Жерар (1997). «Π-исчисление в прямом стиле». CiteSeerX 10.1.1.52.6034 . Цитировать журнал требует
|journal=
( помощь ) - ^ Баркер, Крис (2002-09-01). «Продолжение и природа количественной оценки» (PDF) . Семантика естественного языка . 10 (3): 211–242. DOI : 10,1023 / A: 1022183511876 . ISSN 1572-865X .
- ^ Гриффин, Тимоти (январь 1990 г.). Понятие управления по типу формул . Материалы конференции по основам языков программирования . 17 . С. 47–58. DOI : 10.1145 / 96709.96714 . ISBN 978-0897913430.
Рекомендации
- Continuation Passing C (CPC) - язык программирования для написания параллельных систем , разработанный и разработанный Юлиушем Хробочком и Габриэлем Кернейсом. репозиторий github
- Создание компилятора для ML на основе CPS описано в: Аппель, Эндрю В. (1992). Компиляция с продолжениями . Издательство Кембриджского университета. ISBN 978-0-521-41695-5. CS1 maint: обескураженный параметр ( ссылка )
- Дэнви, Оливье ; Филински, Анджей (1992). «Представление контроля, исследование трансформации CPS». Математические структуры в информатике . 2 (4): 361–391. CiteSeerX 10.1.1.46.84 . DOI : 10.1017 / S0960129500001535 .
- Chicken Scheme компилятор , Схема для C компилятор , который использует продолжение обходя стиль для перевода процедуры Scheme в функцию C при использовании C-стек как питомник для поколений сборщика мусора
- Келси, Ричард А. (март 1995 г.). «Соответствие между стилем прохождения продолжения и статической формой одиночного назначения». Уведомления ACM SIGPLAN . 30 (3): 13–22. CiteSeerX 10.1.1.3.6773 . DOI : 10.1145 / 202530.202532 .
- Аппель, Эндрю В. (апрель 1998 г.). «SSA - это функциональное программирование» . Уведомления ACM SIGPLAN . 33 (4): 17–20. CiteSeerX 10.1.1.34.3282 . DOI : 10.1145 / 278283.278285 . CS1 maint: обескураженный параметр ( ссылка )
- Дэнви, Оливье; Милликин, Кевин; Нильсен, Лассе Р. (2007). «Об однопроходных преобразованиях КПС» . БРИКС, Департамент компьютерных наук, Орхусский университет. п. 24. ISSN 0909-0878 . РС-07-6 . Проверено 26 октября 2007 года . CS1 maint: обескураженный параметр ( ссылка )
- Дибвиг, Р. Кент (2003). Язык программирования схем . Прентис Холл. п. 64. CS1 maint: обескураженный параметр ( ссылка )Прямая ссылка: «Раздел 3.4. Стиль прохождения продолжения» .