Стиль прохождения продолжения - Википедия - Continuation-passing style
В функциональное программирование, стиль передачи (CPS) - это стиль программирования, в котором контроль передается явно в виде продолжение. Это контрастирует с прямой стиль, что является обычным стилем программирования. Джеральд Джей Сассман и Гай Л. Стил-младший. придумал фразу в Памятка AI 349 (1975), в котором изложена первая версия Схема язык программирования.[1][2]Джон С. Рейнольдс дает подробный отчет о многочисленных открытиях продолжений.[3]
Функция, написанная в стиле передачи продолжения, принимает дополнительный аргумент: явное «продолжение», то есть функцию одного аргумента. Когда функция CPS вычисляет значение своего результата, она «возвращает» его, вызывая функцию продолжения с этим значением в качестве аргумента. Это означает, что при вызове функции CPS вызывающая функция должна предоставить процедуру, которая будет вызываться с «возвращаемым» значением подпрограммы. Выражение кода в этой форме делает ряд явных явлений, которые неявны в прямом стиле. К ним относятся: возврат процедуры, который проявляется как вызов продолжения; промежуточные значения, которым всем присвоены имена; порядок вычисления аргументов, который сделан явным; и хвостовые звонки, которые просто вызывают процедуру с тем же продолжением, без изменений, которое было передано вызывающей стороне.
Программы могут быть автоматически преобразованы из прямого стиля в CPS. Функциональные и логика компиляторы часто используют CPS как промежуточное представление где компилятор для императив или же процедурный язык программирования использовал бы статическая форма единого назначения (SSA).[4] SSA формально эквивалентен подмножеству CPS (за исключением нелокального потока управления, который не возникает, когда CPS используется в качестве промежуточного представления).[5] Функциональные компиляторы также могут использовать А-нормальная форма (ANF) (но только для языков, требующих активной оценки), а не с 'thunks '(описанный в примерах ниже) в CPS. CPS чаще используется компиляторы чем программисты в локальном или глобальном стиле.
Примеры
Эта секция написано как руководство или путеводитель.Апрель 2018 г.) (Узнайте, как и когда удалить этот шаблон сообщения) ( |
В CPS каждая процедура принимает дополнительный аргумент, представляющий, что следует делать с результатом, вычисляемым функцией. Это, наряду с ограничительным стилем, запрещающим множество обычно доступных конструкций, используется для раскрытия семантики программ, что упрощает их анализ. Этот стиль также позволяет легко выражать необычные структуры управления, такие как захват / бросок или другие нелокальные передачи управления.
Ключ к CPS - помнить, что (а) каждый функция принимает дополнительный аргумент, его продолжение, и (б) каждый аргумент в вызове функции должен быть либо переменной, либо лямбда-выражение (не более сложное выражение). Это приводит к переворачиванию выражений «наизнанку», потому что в первую очередь должны быть оценены самые внутренние части выражения, поэтому CPS явно указывает порядок оценки, а также поток управления. Ниже приведены некоторые примеры кода в прямом стиле и соответствующие CPS. Эти примеры написаны в Язык программирования схем; по соглашению функция продолжения представлена как параметр с именем "k
":
(определять (пит Икс у) (sqrt (+ (* Икс Икс) (* у у)))) | (определять (pyth & Икс у k) (*& Икс Икс (лямбда (x2) (*& у у (лямбда (y2) (+& x2 y2 (лямбда (x2py2) (sqrt & x2py2 k)))))))) |
(определять (факториал п) (если (= п 0) 1 ; НЕ хвостовая рекурсия (* п (факториал (- п 1))))) | (определять (факториал& п k) (=& п 0 (лямбда (б) (если б ; продолжение роста (k 1) ; в рекурсивном вызове (-& п 1 (лямбда (нм1) (факториал& нм1 (лямбда (ж) (*& п ж k))))))))) |
(определять (факториал п) (f-aux п 1))(определять (f-aux п а) (если (= п 0) а ; хвостовой рекурсивный (f-aux (- п 1) (* п а)))) | (определять (факториал& п k) (f-aux & п 1 k))(определять (f-aux & п а k) (=& п 0 (лямбда (б) (если б ; неизмененное продолжение (k а) ; в рекурсивном вызове (-& п 1 (лямбда (нм1) (*& п а (лямбда (нта) (f-aux & нм1 нта k))))))))) |
Обратите внимание, что в версиях CPS использовались примитивы, например +&
и *&
сами являются CPS, а не прямым стилем, поэтому для того, чтобы приведенные выше примеры работали в системе Scheme, нам нужно было бы написать эти версии примитивов CPS, например *&
определяется:
(определять (*& Икс у k) (k (* Икс у)))
Чтобы сделать это в целом, мы могли бы написать процедуру преобразования:
(определять (cps-prim ж) (лямбда аргументы (позволять ((р (обеспечить регресс аргументы))) ((машина р) (подать заявление ж (обеспечить регресс (CDR р)))))))(определять *& (cps-prim *))(определять +& (cps-prim +))
Чтобы вызвать процедуру, написанную на CPS, из процедуры, написанной в прямом стиле, необходимо предоставить продолжение, которое получит результат, вычисленный процедурой CPS. В приведенном выше примере (при условии, что были предоставлены примитивы в стиле CPS) мы могли бы вызвать (факториал и 10 (лямбда (x) (отображение x) (новая строка)))
.
Между компиляторами существует некоторое различие в способах предоставления примитивных функций в CPS. Выше мы использовали простейшее соглашение, однако иногда предоставляются логические примитивы, которые занимают два thunks вызывается в двух возможных случаях, поэтому (= & n 0 (лямбда (b) (если b ...)))
позвонить внутрь f-aux &
определение выше будет записано вместо этого как (= & n 0 (лямбда () (k a)) (лямбда () (- & n 1 ...)))
. Точно так же иногда если
сам примитив не включен в CPS, а вместо него функция если&
предоставляется, которое принимает три аргумента: логическое условие и два переходника, соответствующие двум ветвям условного оператора.
Приведенные выше переводы показывают, что CPS - это глобальное преобразование. Прямой стиль факториал принимает, как и следовало ожидать, единственный аргумент; CPS факториал& требуется два: аргумент и продолжение. Любая функция, вызывающая функцию CPS-ed, должна либо предоставить новое продолжение, либо передать свое собственное; любые вызовы из функции CPS-ed в функцию, не являющуюся CPS, будут использовать неявные продолжения. Таким образом, чтобы гарантировать полное отсутствие стека функций, вся программа должна быть в CPS.
CPS в Haskell
В этом разделе мы напишем функцию пит
который вычисляет гипотенузу с помощью теорема Пифагора. Традиционная реализация пит
функция выглядит так:
pow2 :: Плавать -> Плаватьpow2 а = а ** 2Добавить :: Плавать -> Плавать -> ПлаватьДобавить а б = а + бпит :: Плавать -> Плавать -> Плаватьпит а б = sqrt (Добавить (pow2 а) (pow2 б))
Чтобы преобразовать традиционную функцию в CPS, нам нужно изменить ее подпись. Функция получит другой аргумент типа функции, и его тип возврата зависит от этой функции:
pow2 ' :: Плавать -> (Плавать -> а) -> аpow2 ' а продолжение = продолжение (а ** 2)Добавить' :: Плавать -> Плавать -> (Плавать -> а) -> аДобавить' а б продолжение = продолжение (а + б)- Типы a -> (b -> c) и a -> b -> c эквивалентны, поэтому функция CPS- можно рассматривать как функцию высшего порядкаsqrt ' :: Плавать -> ((Плавать -> а) -> а)sqrt ' а = \продолжение -> продолжение (sqrt а)pyth ' :: Плавать -> Плавать -> (Плавать -> а) -> аpyth ' а б продолжение = pow2 ' а (\а2 -> pow2 ' б (\Би 2 -> Добавить' а2 Би 2 (\анб -> sqrt ' анб продолжение)))
Сначала мы вычисляем квадрат а в pyth '
функцию и передайте лямбда-функцию в качестве продолжения, которое примет квадрат а в качестве первого аргумента. И так до тех пор, пока не дойдем до результата наших расчетов. Чтобы получить результат этой функции, мы можем передать я бы
функция в качестве последнего аргумента, который возвращает значение, которое было передано ей без изменений: pyth '3 4 id == 5.0
.
Библиотека mtl, поставляемая с GHC, имеет модуль Control.Monad.Cont. Этот модуль предоставляет тип Cont, который реализует Monad и некоторые другие полезные функции. Следующий фрагмент показывает pyth '
функция с использованием Cont:
pow2_m :: Плавать -> Cont а Плаватьpow2_m а = возвращаться (а ** 2)pyth_m :: Плавать -> Плавать -> Cont а Плаватьpyth_m а б = делать а2 <- pow2_m а Би 2 <- pow2_m б анб <- продолжение (Добавить' а2 Би 2) р <- продолжение (sqrt ' анб) возвращаться р
Не только синтаксис стал чище, но и этот тип позволяет нам использовать функцию callCC
с типом MonadCont m => ((a -> m b) -> m a) -> m a
. Эта функция имеет один аргумент типа функции; этот аргумент функции также принимает функцию, что отменяет все вычисления, выполняемые после ее вызова. Например, прервем выполнение пит
функция, если хотя бы один из ее аргументов отрицательный, возвращает ноль:
pyth_m :: Плавать -> Плавать -> Cont а Плаватьpyth_m а б = callCC $ \exitF -> делать - Знак $ помогает избежать скобок: a $ b + c == a (b + c) когда (б < 0 || а < 0) (exitF 0.0) - when :: Applicative f => Bool -> f () -> f () а2 <- pow2_m а Би 2 <- pow2_m б анб <- продолжение (Добавить' а2 Би 2) р <- продолжение (sqrt ' анб) возвращаться р
Продолжения как объекты
Программирование с продолжениями также может быть полезно, когда вызывающий не хочет ждать, пока вызываемый завершит работу. Например, при программировании пользовательского интерфейса (UI) подпрограмма может настраивать поля диалогового окна и передавать их вместе с функцией продолжения в структуру UI. Этот вызов сразу же возвращается, позволяя коду приложения продолжать работу, пока пользователь взаимодействует с диалоговым окном. Как только пользователь нажимает кнопку «ОК», инфраструктура вызывает функцию продолжения с обновленными полями. Хотя этот стиль кодирования использует продолжения, он не является полноценным CPS.[требуется разъяснение ]
функция confirmName() { поля.имя = имя; рамки.Show_dialog_box(поля, confirmNameContinuation);}функция confirmNameContinuation(поля) { имя = поля.имя;}
Похожая идея может использоваться, когда функция должна выполняться в другом потоке или на другом процессоре. Платформа может выполнить вызванную функцию в рабочем потоке, а затем вызвать функцию продолжения в исходном потоке с результатами рабочего. Это в Ява с использованием Качать Структура пользовательского интерфейса:
пустота buttonHandler() { // Это выполняется в потоке пользовательского интерфейса Swing. // Здесь мы можем получить доступ к виджетам пользовательского интерфейса, чтобы получить параметры запроса. окончательный int параметр = getField(); новый Нить(новый Работоспособен() { общественный пустота пробег() { // Этот код выполняется в отдельном потоке. // Мы можем делать такие вещи, как доступ к базе данных или // блокируем ресурс, например сеть, для получения данных. окончательный int результат = искать(параметр); javax.качать.SwingUtilities.invokeLater(новый Работоспособен() { общественный пустота пробег() { // Этот код выполняется в потоке пользовательского интерфейса и может использовать // полученные данные для заполнения виджетов пользовательского интерфейса. setField(результат); } }); } }).Начните();}
При использовании лямбда-нотации Java 8 приведенный выше код сокращается до (окончательный
ключевое слово может быть пропущено):
пустота buttonHandler() { int параметр = getField(); новый Нить(() -> { int результат = искать(параметр); javax.качать.SwingUtilities.invokeLater(() -> setField(результат)); }).Начните();}
Хвостовые крики
Каждый звонок в CPS - это хвостовой зов, и продолжение передается явно. Использование CPS без оптимизация хвостового вызова (TCO) приведет к потенциальному росту не только построенного продолжения во время рекурсии, но и стек вызовов. Обычно это нежелательно, но использовалось интересным образом - см. Схема с курицей компилятор. Поскольку CPS и TCO исключают концепцию неявного возврата функции, их совместное использование может устранить необходимость в стеке времени выполнения. Несколько компиляторов и интерпретаторов для функциональные языки программирования использовать эту способность по-новому.[6]
Использование и реализация
Стиль передачи продолжения может использоваться для реализации операторов продолжения и потока управления на функциональном языке, который не имеет первоклассных функций. продолжения но есть первоклассные функции и оптимизация хвостового вызова. Без оптимизации хвостового вызова такие методы, как прыжки на батуте, т.е. используя цикл, который итеративно вызывает thunk -возвратные функции, можно использовать; без первоклассных функций в таком цикле можно даже преобразовать хвостовые вызовы в просто переходы.
Написание кода на CPS, хотя и возможно, часто подвержено ошибкам. Существуют различные переводы, обычно определяемые как одно- или двухпроходные преобразования чистого лямбда-исчисление, которые преобразуют прямые выражения стиля в выражения CPS. Однако писать на батуте чрезвычайно сложно; при использовании он обычно является целью некоторого преобразования, например сборник.
Функции, использующие более одного продолжения, могут быть определены для захвата различных парадигм потока управления, например (в Схема ):
(определять (/& Икс у Ok ошибаться) (=& у 0.0 (лямбда (б) (если б (ошибаться (список "делить на ноль!" Икс у)) (Ok (/ Икс у))))))
Следует отметить, что преобразование CPS концептуально Йонеда вложение.[7] Это также похоже на вложение лямбда-исчисление в π-исчисление.[8][9]
Использование в других областях
Вне Информатика, CPS представляет более общий интерес как альтернатива традиционному методу объединения простых выражений в сложные. Например, в лингвистическом семантика, Крис Баркер и его сотрудники предположили, что указание обозначений предложений с помощью CPS может объяснить определенные явления в естественный язык.[10]
В математика, то Изоморфизм Карри – Ховарда между компьютерными программами и математическими доказательствами связывает перевод в стиле передачи продолжения с вариантом двойного отрицания вложения из классическая логика в интуиционистская (конструктивная) логика. В отличие от обычного перевод двойного отрицания, который отображает атомарные предложения п к ((п → ⊥) → ⊥), стиль передачи продолжения заменяет ⊥ типом последнего выражения. Соответственно результат получается путем передачи функция идентичности как продолжение выражения в стиле CPS, как в приведенном выше примере.
Сама классическая логика относится к непосредственному управлению продолжением программ, как в схеме Scheme. вызов с текущим продолжением оператор управления, наблюдение Тима Гриффина (с использованием тесно связанного оператора управления C).[11]
Смотрите также
Примечания
- ^ Сассман, Джеральд Джей; Стил, Гай Л., мл. (Декабрь 1975 г.). . Памятка AI. 349: 19.
То есть в этом продолжающийся стиль программирования, функция всегда «возвращает» свой результат, «отправляя» его другой функции. Это ключевая идея.
- ^ Сассман, Джеральд Джей; Стил, Гай Л., мл. (Декабрь 1998 г.). «Схема: интерпретатор для расширенного лямбда-исчисления» (перепечатка). Вычисление высшего порядка и символическое вычисление. 11 (4): 405–439. Дои:10.1023 / А: 1010035624696.
Мы полагаем, что это было первое упоминание термина "стиль передачи"в литературе. Это оказалось важным понятием в анализе и преобразовании исходного кода для компиляторов и других инструментов метапрограммирования. Оно также послужило источником вдохновения для ряда других" стилей "выражения программ.
- ^ Рейнольдс, Джон С. (1993). «Открытия продолжений». Лисп и символьные вычисления. 6 (3–4): 233–248. CiteSeerX 10.1.1.135.4705. Дои:10.1007 / bf01019459.
- ^ * Аппель, Эндрю В. (апрель 1998 г.). «SSA - это функциональное программирование». Уведомления ACM SIGPLAN. 33 (4): 17–20. CiteSeerX 10.1.1.34.3282. Дои:10.1145/278283.278285.
- ^ * Келси, Ричард А. (март 1995 г.). «Соответствие между стилем прохождения продолжения и статической формой однократного назначения». Уведомления ACM SIGPLAN. 30 (3): 13–22. CiteSeerX 10.1.1.489.930. Дои:10.1145/202530.202532.
- ^ Аппель, Эндрю В. (1992). Компиляция с продолжениями. Издательство Кембриджского университета. ISBN 0-521-41695-7.
- ^ Майк Стэй, «Проходящее преобразование продолжения и вложение Йонеды»
- ^ Майк Стей, "Исчисление числа Пи II"
- ^ Будоль, Жерар (1997). «П-исчисление в прямом стиле». CiteSeerX 10.1.1.52.6034. Цитировать журнал требует
| журнал =
(помощь) - ^ Баркер, Крис (2002-09-01). «Продолжение и природа количественной оценки» (PDF). Семантика естественного языка. 10 (3): 211–242. Дои:10.1023 / А: 1022183511876. ISSN 1572-865X.
- ^ Гриффин, Тимоти (январь 1990 г.). Понятие управления по типу формул. Материалы конференции по основам языков программирования. 17. С. 47–58. Дои:10.1145/96709.96714. ISBN 978-0897913430.
Рекомендации
- Продолжение прохождения C (CPC) - язык программирования для написания параллельных систем, разработан и разработан Юлиушем Хробочком и Габриэлем Кернейсом. репозиторий github
- Построение CPS-компилятора для ML описывается в: Аппель, Эндрю В. (1992). Компиляция с продолжениями. Издательство Кембриджского университета. ISBN 978-0-521-41695-5.
- Дэнви, Оливье; Филински Анджей (1992). «Представление контроля, исследование трансформации CPS». Математические структуры в компьютерных науках. 2 (4): 361–391. CiteSeerX 10.1.1.46.84. Дои:10.1017 / S0960129500001535.
- Компилятор Chicken Scheme, а Схема к C компилятор, который использует стиль передачи продолжения для перевода процедур Scheme в функции C, используя C-стек в качестве питомника для сборщик мусора поколений
- Келси, Ричард А. (март 1995 г.). «Соответствие между стилем прохождения продолжения и статической формой одиночного присвоения». Уведомления ACM SIGPLAN. 30 (3): 13–22. CiteSeerX 10.1.1.3.6773. Дои:10.1145/202530.202532.
- Аппель, Эндрю В. (Апрель 1998 г.). «SSA - это функциональное программирование». Уведомления ACM SIGPLAN. 33 (4): 17–20. CiteSeerX 10.1.1.34.3282. Дои:10.1145/278283.278285.
- Данви, Оливье; Милликин, Кевин; Нильсен, Лассе Р. (2007). «Об однопроходных преобразованиях CPS». БРИКС, Департамент компьютерных наук, Орхусский университет. п. 24. ISSN 0909-0878. РС-07-6. Получено 26 октября 2007.
- Дибвиг, Р. Кент (2003). Язык программирования схем. Прентис Холл. п. 64. Прямая ссылка: «Раздел 3.4. Стиль прохождения продолжения».