Стиль продолжения прохождения

В функциональном программировании стиль передачи продолжения ( CPS ) — это стиль программирования, в котором управление передается явно в форме продолжения . Это контрастирует с прямым стилем, который является обычным стилем программирования. Джеральд Джей Сассман и Гай Л. Стил-младший придумали эту фразу в AI Memo 349 (1975), в которой изложена первая версия языка программирования Scheme . Джон К. Рейнольдс подробно описывает многочисленные открытия продолжений.

Функция, написанная в стиле передачи продолжения, принимает дополнительный аргумент: явное «продолжение»; т.е. функция одного аргумента. Когда функция CPS вычислила свое значение результата, она «возвращает» его, вызывая функцию продолжения с этим значением в качестве аргумента. Это означает, что при вызове функции CPS вызывающая функция должна предоставить вызываемой процедуре «возвращаемое» значение подпрограммы. Выражение кода в такой форме делает явными многие вещи, которые неявно подразумеваются в прямом стиле. К ним относятся: возвраты процедур, которые проявляются как вызовы продолжения; промежуточные значения, которым всем даны имена; порядок вычисления аргументов, который сделан явным; и хвостовые вызовы , которые просто вызывают процедуру с тем же неизмененным продолжением, которое было передано вызывающей стороне.

Программы могут быть автоматически преобразованы из прямого стиля в CPS. Функциональные и логические компиляторы часто используют CPS в качестве промежуточного представления , тогда как компилятор для императивного или процедурного языка программирования будет использовать статическую форму одиночного присваивания (SSA). SSA формально эквивалентен подмножеству CPS (исключая нелокальный поток управления, который не возникает, когда CPS используется в качестве промежуточного представления). Функциональные компиляторы также могут использовать A-нормальную форму (ANF) (но только для языков, требующих быстрого вычисления), а не с помощью « thunk » (описанных в примерах ниже) в CPS. CPS чаще используется компиляторами , чем программистами, как локальный или глобальный стиль.

Примеры

В CPS каждая процедура принимает дополнительный аргумент, представляющий, что следует делать с результатом, который вычисляет функция. Это, наряду с ограничительным стилем, запрещающим различные обычно доступные конструкции, используется для раскрытия семантики программ, что упрощает их анализ. Этот стиль также позволяет легко выражать необычные структуры управления, такие как захват/бросок или другие нелокальные передачи управления.

Ключом к CPS является запоминание того, что (а) каждая функция принимает дополнительный аргумент, известный как ее продолжение, и (б) каждый аргумент в вызове функции должен быть либо переменной, либо лямбда-выражением (а не более сложным выражением). Это приводит к переворачиванию выражений «наизнанку», поскольку сначала должны быть вычислены самые внутренние части выражения, таким образом, CPS четко определяет порядок вычисления, а также поток управления. Ниже приведены некоторые примеры кода в прямом стиле и соответствующие CPS. Эти примеры написаны на языке программирования Scheme ; по соглашению функция продолжения представлена ​​как параметр с именем " k":

Прямой стиль	Продолжение стиля прохождения
(define (pyth x y) (sqrt (+ (* x x) (* y y))))	(define (pyth& x y k) (*& x x (lambda (x2) (*& y y (lambda (y2) (+& x2 y2 (lambda (x2py2) (sqrt& x2py2 k))))))))
(define (factorial n) (if (= n 0) 1 ; NOT tail-recursive (* n (factorial (- n 1)))))	(define (factorial& n k) (=& n 0 (lambda (b) (if b ; growing continuation (k 1) ; in the recursive call (-& n 1 (lambda (nm1) (factorial& nm1 (lambda (f) (*& n f k)))))))))
(define (factorial n) (f-aux n 1)) (define (f-aux n a) (if (= n 0) a ; tail-recursive (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 ; unmodified continuation (k a) ; in the recursive call (-& n 1 (lambda (nm1) (*& n a (lambda (nta) (f-aux& nm1 nta k)))))))))

Обратите внимание, что в версиях CPS используются примитивы, например +& и *& сами по себе являются CPS, а не прямым стилем, поэтому, чтобы приведенные выше примеры работали в системе Scheme, нам нужно будет написать эти версии примитивов CPS, например *& определяется:

(define (*& 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. Выше мы использовали простейшее соглашение, однако иногда предоставляются логические примитивы, для вызова которых в двух возможных случаях требуется два преобразователя , поэтому (=& 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.

CPS в Haskell

В этом разделе мы напишем функцию 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)

-- Types a -> (b -> c) and a -> b -> c are equivalent, so CPS function
-- may be viewed as a higher order function
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)))

Сначала вычислим квадрат а в 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 -- $ sign helps to avoid parentheses: 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) процедура может настроить поля диалогового окна и передать их вместе с функцией продолжения в структуру пользовательского интерфейса. Этот вызов сразу же возвращается, позволяя коду приложения продолжать работу, пока пользователь взаимодействует с диалоговым окном. Как только пользователь нажимает кнопку «ОК», платформа вызывает функцию продолжения с обновленными полями. Хотя этот стиль кодирования использует продолжения, он не является полным CPS.

function confirmName() {
    fields.name = name;
    framework.Show_dialog_box(fields, confirmNameContinuation);
}

function confirmNameContinuation(fields) {
    name = fields.name;
}

Аналогичную идею можно использовать, когда функция должна выполняться в другом потоке или на другом процессоре. Платформа может выполнить вызванную функцию в рабочем потоке, а затем вызвать функцию продолжения в исходном потоке с результатами рабочего потока. Это в Java 8 с использованием инфраструктуры Swing UI:

void buttonHandler() {
    // This is executing in the Swing UI thread.
    // We can access UI widgets here to get query parameters.
    int parameter = getField();

    new Thread(() -> {
        // This code runs in a separate thread.
        // We can do things like access a database or a 
        // blocking resource like the network to get data.
        int result = lookup(parameter);

        javax.swing.SwingUtilities.invokeLater(() -> {
            // This code runs in the UI thread and can use
            // the fetched data to fill in UI widgets.
            setField(result);
        });
    }).start();
}

Хвостовые вызовы

Каждый вызов в CPS является хвостовым вызовом , и продолжение передается явно. Использование CPS без оптимизации хвостового вызова (TCO) приведет к потенциальному росту во время рекурсии не только созданного продолжения, но и стека вызовов . Обычно это нежелательно, но его можно использовать интересным образом — см. компилятор Chicken Scheme . Поскольку CPS и TCO устраняют концепцию неявного возврата функции, их совместное использование может устранить необходимость в стеке времени выполнения. Некоторые компиляторы и интерпретаторы функциональных языков программирования используют эту возможность по-новому.

Использование и реализация

Стиль передачи продолжения можно использовать для реализации продолжений и операторов потока управления на функциональном языке, который не имеет первоклассных продолжений , но имеет первоклассные функции и оптимизацию хвостовых вызовов . Без оптимизации хвостового вызова такие методы, как трамплин , то есть использование цикла, который итеративно вызывает функции, возвращающие thunk можно использовать ; без первоклассных функций в таком цикле можно даже преобразовать хвостовые вызовы в просто переходы.

Написание кода в CPS хотя и не невозможно, но часто подвержено ошибкам. Существуют различные переводы, обычно определяемые как одно- или двухпроходные преобразования чистого лямбда-исчисления , которые преобразуют выражения прямого стиля в выражения CPS. Однако писать батутным стилем чрезвычайно сложно; при использовании он обычно является целью какого-либо преобразования, например компиляции .

Функции, использующие более одного продолжения, могут быть определены для захвата различных парадигм потока управления, например (в Scheme ):

(define (/& x y ok err)
 (=& y 0.0 (lambda (b)
            (if b
                (err (list "div by zero!" x y))
                (ok (/ x y))))))

Следует отметить, что преобразование CPS концептуально является вложением Йонеды . Это также похоже на встраивание лямбда-исчисления в π-исчисление .

Использование в других областях

За пределами информатики CPS представляет более общий интерес как альтернатива традиционному методу составления простых выражений в сложные. Например, в рамках лингвистической семантики и его коллеги предположили , Крис Баркер что определение значений предложений с использованием CPS может объяснить определенные явления в естественном языке .

В математике изоморфизм Карри-Ховарда между компьютерными программами и математическими доказательствами связывает перевод в стиле передачи продолжения с вариацией вложений двойного отрицания классической логики в интуиционистскую (конструктивную) логику . В отличие от обычного перевода с двойным отрицанием , который отображает атомарные предложения p в (( p → ⊥) → ⊥), стиль передачи продолжения заменяет ⊥ типом конечного выражения. Соответственно, результат получается путем передачи идентификационной функции как продолжения выражения CPS, как в приведенном выше примере.

Классическая логика сама по себе относится к непосредственному управлению продолжением программ, как в операторе управления вызовом с текущим продолжением Scheme , наблюдении Тима Гриффина (с использованием тесно связанного оператора управления C).

См. также

• Хвостовая рекурсия через прыжки на батуте

Ссылки

• Continuation Passing C (CPC) — язык программирования для написания параллельных систем , спроектированный и разработанный Юлиушем Хробочеком и Габриэлем Кернейсом. репозиторий GitHub
• Создание компилятора для машинного обучения на основе CPS описано в: Аппель, Эндрю В. (1992). Компиляция с продолжениями . Издательство Кембриджского университета. ISBN  978-0-521-41695-5 .
• Дэнви, Оливье ; Филинский, Анджей (1992). «Представление контроля, исследование трансформации CPS». Математические структуры в информатике . 2 (4): 361–391. CiteSeerX   10.1.1.46.84 . дои : 10.1017/S0960129500001535 . S2CID   8790522 .
• Компилятор Chicken Scheme , компилятор 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 . S2CID   207227209 .
• Дэнви, Оливье; Милликин, Кевин; Нильсен, Лассе Р. (2007). «Об однопроходных преобразованиях СУЗ» . Серия отчетов БРИКС : 24. ISSN   0909-0878 . РС-07-6 . Проверено 26 октября 2007 г.
• Дибвиг, Р. Кент (2003). Язык программирования Scheme . Прентис Холл. п. 64. Прямая ссылка: «Раздел 3.4. Стиль продолжения передачи» .