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

В функциональном программировании стиль передачи продолжения ( 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 ( лямбда ( x2 ) ( *& y y ( лямбда ( y2 ) ( +& x2 y2 ( лямбда ( x2py2 ) ( sqrt& x2py2 k )))))))
( define ( факториал n ) ( if ( = n 0 ) 1 ; НЕ хвостовая рекурсия ( * n ( факториал ( - n 1 )))))	( define ( factorial& n k ) ( =& n 0 ( лямбда ( b ) ( if b ; продолжение роста ( k 1 ) ; в рекурсивном вызове ( -& n 1 ( лямбда ( nm1 ) ( факториал& nm1 ( лямбда ( f )) ( *& н ж к )))))))))
( определить ( факториал n ) ( f-aux n 1 )) ( определить ( f-aux n a ) ( if ( = n 0 ) a ; хвостовая рекурсия ( f-aux ( - n 1 ) ( * n a )) ))	( define ( факториал& n k ) ( f-aux& n 1 k )) ( define ( f-aux& n a k ) ( =& n 0 ( лямбда ( b ) ( if b ; немодифицированное продолжение ( k a ) ; в рекурсивном вызов ( -& n 1 ( лямбда ( nm1 ) ( *& n a ( лямбда ( nta ) ( f-aux& nm1 nta k )))))))))

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

(  определить   (  *&   x   y   k  ) 
  (  k   (  *   x   y  ))) 

В общем, чтобы сделать это, мы могли бы написать процедуру преобразования:

(  define   (  cps-prim   f  ) 
  (  лямбда-   аргументы 
   (  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, должна либо предоставить новое продолжение, либо передать свое собственное; любые вызовы функции, поддерживающей 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   х  )   (  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'   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   -- $ знак помогает избежать круглых скобок: a $ b + c == a (b + c), 
   когда   (  b   <   0   ||   a   <   0  )   (  exitF   0.0  )   -- когда :: Аппликативный 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   =   поиск  (  параметр  ); 

         javax  .  SwingUtilities  .  //  ;  ignoreLater  (()   ->   { 
             // Этот код выполняется в потоке пользовательского интерфейса и может использовать 
             полученные данные для заполнения виджетов пользовательского интерфейса. 
             setField  (  result  ); 
         } 
     )   начинать  (); 
  } 

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

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

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

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

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

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

(  define   (  /&   x   y   ok   err  ) 
  (  =&   y   0.0   (  лямбда   (  b  ) 
             (  if   b 
                 (  err   (  список   «деление на ноль!»   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. Стиль продолжения передачи» .