연속 패스 스타일

Continuation-passing style

기능 프로그래밍에서 연속 패스 스타일(CPS)은 연속의 형태로 제어권이 명시적으로 전달되는 프로그래밍 스타일이다. 이는 일반적인 프로그래밍 방식인 직접 스타일과 대비된다. 제럴드 제이 서스먼과 가이 엘 스틸 주니어는 스키 프로그래밍 언어의 첫 버전을 정하는 AI 메모 349(1975년)에서 이 구절을 만들었다.[1][2] 존 C. 레이놀즈는 계속의 수많은 발견에 대해 상세한 설명을 한다.[3]

연속 패스 스타일로 작성된 함수는 추가적인 논거를 취한다. 즉, 명시적인 "계속" 즉, 하나의 논거의 함수. CPS 함수는 결과 값을 계산했을 때 이 값을 인수로 하여 계속 함수를 "반환"한다. 즉, CPS 함수를 호출할 때 호출 함수가 서브루틴의 "반환" 값으로 호출할 절차를 제공해야 한다. 이 형태로 코드를 표현하면 직접적인 문체로 내포되어 있는 많은 것들이 명백해진다. 여기에는 계속에 대한 호출로 명백해지는 절차 복귀, 모든 이름이 주어지는 중간 값, 명시적으로 이루어지는 논쟁 평가 순서, 그리고 단순히 동일한 지속적이고 수정되지 않은 절차를 호출자에게 전달되는 테일 콜 등이 포함된다.

프로그램은 직접 스타일에서 CPS로 자동 변환할 수 있다. 기능 및 논리 컴파일러는 명령적 또는 절차적 프로그래밍 언어를 위한 컴파일러가 정적 단일 할당 양식(SSA)을 사용하는 중간 표현으로 CPS를 사용하는 경우가 많다.[4] SSA는 공식적으로 CPS의 하위 집합과 동등하다(CPS를 중간 표시로 사용할 때 발생하지 않는 비 로컬 제어 흐름 제외).[5] 또한 기능 컴파일러는 CPS에서 '쿵'(아래 예에서 설명함)이 아닌 A-정규형(ANF)을 사용할 수 있다. CPS는 프로그래머가 로컬 또는 글로벌 스타일로 사용하는 것보다 컴파일러에 의해 더 자주 사용된다.

예

CPS에서 각 절차는 함수가 계산하는 결과를 사용하여 수행해야 하는 작업을 나타내는 추가 인수를 사용한다. 이것은, 일반적으로 이용할 수 있는 다양한 구문을 금지하는 제한적인 스타일과 함께, 프로그램의 의미론을 노출시키는 데 사용되어, 분석하기 쉽게 한다. 이 스타일은 또한 캐치/던지기 또는 기타 국지적이지 않은 제어 전달과 같은 비정상적인 제어 구조를 쉽게 표현할 수 있게 한다.

CPS의 핵심은 (a) 모든 함수가 연속이라고 알려진 추가 인수를 사용하고, (b) 함수 호출의 모든 인수는 변수 또는 람다 식(더 복잡한 식이 아님)이어야 한다는 것을 기억하는 것이다. 이는 표현식의 가장 안쪽 부분을 먼저 평가해야 하기 때문에 표현식을 "내부"로 돌리는 효과가 있으므로, CPS는 조정기 흐름은 물론 평가 순서를 명시한다. 직접 스타일의 코드와 해당 CPS의 몇 가지 예는 아래와 같다. 이러한 예는 Scheme 프로그래밍 언어로 작성된다. 관례에 따라 연속 함수는 "라는 이름의 매개변수로 표현된다.k":

직접 스타일
연속 패스 스타일
(정의를 내리다 (비단뱀 x y)  (sqrt (+ (* x x) (* y y)))) 
(정의를 내리다 (피앤 x y k)  (*& x x (람다 (x 2)           (*& y y (람다 (y2)                    (+& x 2 y2 (람다 (x2py2)                               (sqrt& x2py2 k)))))))) 
(정의를 내리다 (요인의 n)  (만일 (= n 0)      1     ; 꼬리 자르기 금지      (* n (요인의 (- n 1))))) 
(정의를 내리다 (요인& n k)  (=& n 0 (람다 (b)           (만일 b                    ; 계속 증가               (k 1)                ; 재귀 호출 중               (-& n 1 (람다 (nm1)                        (요인& nm1 (람다 (f)                                         (*& n f k))))))))) 
(정의를 내리다 (요인의 n)  (가짜의 n 1)) (정의를 내리다 (가짜의 n a)  (만일 (= n 0)      a        ; 꼬리 자르기      (가짜의 (- n 1) (* n a)))) 
(정의를 내리다 (요인& n k) (f-aux& n 1 k)) (정의를 내리다 (f-aux& n a k)  (=& n 0 (람다 (b)           (만일 b                    ; 수정되지 않은 연속               (k a)                ; 재귀 호출 중               (-& n 1 (람다 (nm1)                         (*& n a (람다 (엔타)                                 (f-aux& nm1 엔타 k)))))))))

CPS 버전에서 사용된 원시 요소(예: +& 그리고 *& 직접 스타일이 아니라 CPS이기 때문에 위의 예제를 Scheme 시스템에서 작동시키려면 예를 들어 CPS 버전의 원시 요소를 작성해야 한다. *& 정의: 

(정의를 내리다 (*& x y k)  (k (* x y)))

일반적으로 이를 위해 다음과 같은 변환 루틴을 작성할 수 있다. 

(정의를 내리다 (cps-prime f)  (람다 아그   (하게 하다 ((r (역행의 아그)))    ((자동차 r) (신청하다 f              (역행의 (cdr r))))))) (정의를 내리다 *& (cps-prime *)) (정의를 내리다 +& (cps-prime +))

직접 작성한 절차에서 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-ed 함수를 비 CPS 함수로 호출하는 모든 함수는 암시적 연속성을 사용한다. 따라서 기능 스택의 전체 부재를 보장하기 위해 전체 프로그램이 CPS에 있어야 한다.

하스켈의 CPS

이 섹션에는 함수를 쓰겠다. pyth 피타고라스의 정리를 이용하여 하이포텐스를 계산한다. 기존 구현 방식: pyth 기능은 다음과 같다: 

pow2 :: 플로트 -> 플로트 pow2 a = a ** 2  덧셈을 :: 플로트 -> 플로트 -> 플로트 덧셈을 a b = a + b  비단뱀 :: 플로트 -> 플로트 -> 플로트 비단뱀 a b = sqrt (덧셈을 (pow2 a) (pow2 b))

기존 기능을 CPS로 전환하려면 서명을 변경해야 한다. 함수는 함수 유형의 또 다른 인수를 얻게 되며, 반환 유형은 해당 함수에 따라 달라진다. 

pow2' :: 플로트 -> (플로트 -> a) -> a pow2' a 결부시키다 = 결부시키다 (a ** 2)  덧붙이다' :: 플로트 -> 플로트 -> (플로트 -> a) -> a 덧붙이다' a b 결부시키다 = 결부시키다 (a + b)  -- 타입 a -> (b -> c)와 a -> b -> c는 등가이므로 CPS기능 -- 고차 함수로 간주될 수 있음 sqrt' :: 플로트 -> ((플로트 -> a) -> a) sqrt' a = \결부시키다 -> 결부시키다 (sqrt a)  비단뱀의 :: 플로트 -> 플로트 -> (플로트 -> a) -> a 비단뱀의 a b 결부시키다 = pow2' a (\a2 -> pow2' b (\b2 -> 덧붙이다' a2 b2 (\anb -> sqrt' anb 결부시키다)))

먼저 a의 제곱을 계산한다. pyth' 람다 함수를 연속적으로 기능하고 통과시켜 a의 제곱을 첫 번째 인수로 받아들인다. 그리고 우리가 계산의 결과에 도달할 때까지도 그렇다. 이 기능의 결과를 얻기 위해서 우리는 통과할 수 있다. id 전달된 값을 변경하지 않고 반환하는 최종 인수의 함수: pyth' 3 4 id == 5.0.

GHC와 함께 선적되는 mtl 라이브러리에는 모듈이 있다. Control.Monad.Cont이 모듈은 Monad와 다른 유용한 기능을 구현하는 Contt 타입을 제공한다. 다음 조각은 다음 조각들을 보여준다. pyth' 콘트를 사용하여 함수: 

pow2_m :: 플로트 -> 콘트 a 플로트 pow2_m a = 돌아오다 (a ** 2)  python_m :: 플로트 -> 플로트 -> 콘트 a 플로트 python_m a b = 하다   a2 <- pow2_m a   b2 <- pow2_m b   anb <- 결부시키다 (덧붙이다' a2 b2)   r <- 결부시키다 (sqrt' anb)   돌아오다 r

구문이 깨끗해졌을 뿐만 아니라, 이 타입은 우리가 함수를 사용할 수 있게 해준다. callCC 활자로 MonadCont m => ((a -> m b) -> m a) -> m a. 이 함수는 함수 유형의 한 가지 인수를 가지고 있다; 그 함수 인수는 함수를 또한 받아들인다. 이것은 호출 후에 진행되는 모든 계산을 무시한다. 예를 들어 사형집행을 파기하자. pyth 변수 인수 중 하나 이상이 마이너스 반환인 경우 함수: 

python_m :: 플로트 -> 플로트 -> 콘트 a 플로트 python_m a b = 콜CC $ \출구F -> 하다 -- $ 부호는 괄호를 피하는 데 도움이 된다: $ b + c == a (b + c)   할 때 (b < 0    a < 0) (출구F 0.0) -- when : : 적용 f => Bool -> f() -> f()   a2 <- pow2_m a   b2 <- pow2_m b   anb <- 결부시키다 (덧붙이다' a2 b2)   r <- 결부시키다 (sqrt' anb)   돌아오다 r

개체로서의 연속성

참고 항목: 콜백(컴퓨터 프로그래밍)

연속성을 가진 프로그래밍은 호출자가 캘리어가 완료될 때까지 기다리지 않으려는 경우에도 유용할 수 있다. 예를 들어 사용자 인터페이스(UI) 프로그래밍에서 루틴은 대화 상자 필드를 설정하고 이를 연속 기능과 함께 UI 프레임워크로 전달할 수 있다. 이 호출은 즉시 반환되므로 사용자가 대화 상자와 상호 작용하는 동안 응용 프로그램 코드를 계속할 수 있다. 일단 사용자가 "확인" 버튼을 누르면, 프레임워크는 업데이트된 필드의 계속 기능을 호출한다. 이 코딩 스타일은 연속성을 사용하지만, 완전한 CPS는 아니다.[clarification needed] 

기능을 하다 confirmName() {     들판.이름을 붙이다 = 이름을 붙이다;     틀.Show_dialog_box(들판, confirmName계속); }  기능을 하다 confirmName계속(들판) {     이름을 붙이다 = 들판.이름을 붙이다; }

기능이 다른 스레드 또는 다른 프로세서에서 실행되어야 하는 경우에도 유사한 아이디어를 사용할 수 있다. 프레임워크는 작업자 스레드에서 호출된 함수를 실행한 다음 작업자의 결과와 함께 원래의 스레드에서 계속함수를 호출할 수 있다. 이는 Java 8에서 Swing UI 프레임워크를 사용하는 경우: 

공허하게 하다 버튼핸들러() {     // 이것은 스윙 UI 스레드에서 실행 중이다.     // 여기서 UI 위젯에 액세스하여 쿼리 매개 변수를 가져올 수 있다.     인트로 매개 변수 = 겟필드();      새로운 나사산(() => {         // 이 코드는 별도의 스레드에서 실행된다.         // 데이터베이스나 데이터에 대한 액세스 같은 작업을 수행할 수 있음          // 데이터를 얻기 위해 네트워크와 같은 리소스를 차단한다.         인트로 결과 = 찾다(매개 변수);          자바스.스윙을 하다.스윙유틸리티.호출Later(() => {             // 이 코드는 UI 스레드에서 실행되며 사용할 수 있음             // UI 위젯을 채우기 위해 가져온 데이터.             setField(결과);         });     }).출발하다(); }

테일 콜

CPS의 모든 호출은 추적 호출이며, 계속은 명시적으로 통과된다. 테일 콜 최적화(TCO) 없이 CPS를 사용하면 재귀 중에 생성된 연속성이 잠재적으로 증가할 뿐만 아니라 콜 스택도 증가할 수 있다. 이 방법은 일반적으로 바람직하지 않지만 흥미로운 방법으로 사용되어 왔다. 닭 구성표 컴파일러를 참조하십시오. CPS와 TCO가 암묵적 함수 반환 개념을 제거함에 따라, CPS와 TCO를 결합하면 런타임 스택의 필요성이 없어질 수 있다. 기능 프로그래밍 언어에 대한 여러 컴파일러와 통역사는 이 능력을 참신한 방법으로 사용한다.[6]

사용 및 구현

연속 패스 스타일은 1등급 연속성을 특징으로 하지 않지만 1등급 기능 및 테일콜 최적화를 가지고 있는 기능 언어로 연속성을 구현하고 흐름 연산자를 제어하는 데 사용할 수 있다. 테일콜 최적화 없이 트램폴링(trampolining)과 같은 기법, 즉 반복적으로 텀블링(thunk-returning) 기능을 발동시키는 루프를 사용할 수 있으며, 일급 기능이 없는 경우 그러한 루프에서 테일콜을 그냥 gotos로 변환할 수도 있다.

CPS에서 코드를 쓰는 것은 불가능하지는 않지만 오류가 발생하기 쉬운 경우가 많다. 보통 순수한 람다 미적분학의 1패스 또는 2패스 변환으로 정의되는 다양한 번역이 있는데, 이 변환은 직접 스타일 표현식을 CPS 표현으로 변환한다. 그러나 trampollated 문체로 쓰는 것은 매우 어렵다. 그러나 사용할 때, 그것은 보통 컴파일과 같은 어떤 종류의 변환의 대상이 된다.

두 개 이상의 연속성을 사용하는 함수를 정의하여 다양한 제어 흐름 패러다임을 포착할 수 있다(예: (구성표). 

(정의를 내리다 (/& x y 네 알겠습니다 잘못을 저지르다)  (=& y 0.0 (람다 (b)             (만일 b                 (잘못을 저지르다 (리스트를 작성하다 "0으로 나누다!" x y))                 (네 알겠습니다 (/ x y))))))

CPS 변환은 개념적으로 요네다 임베딩이라는 점에 유의한다.[7] 또한 --미적분에 람다 미적분을 내장하는 것과도 비슷하다.[8][9]

다른 필드에서 사용

컴퓨터 과학 외적으로, CPS는 단순한 표현을 복잡한 표현으로 합성하는 기존의 방법의 대안으로 더 일반적인 관심을 가지고 있다. 예를 들어, 언어적 의미론 내에서, Chris Bakker와 그의 협력자들은 CPS를 사용한 문장의 변조를 명시하는 것이 자연 언어로 특정 현상을 설명할 수 있다고 제안했다.[10]

수학에서, 컴퓨터 프로그램과 수학적 증명 사이의 Curry-Howard 이소모르퍼시즘은 연속 패스 스타일 번역과 고전적 논리를 직관적(건설적) 논리로 내장한 이중 부정의 변형을 연관시킨다. 원자제안 p를 (p → ⊥) → ⊥에 매핑하는 일반 이중부정 번역과 달리 연속 패스 방식은 최종 표현형식으로 ⊥을 대체한다. 따라서 위의 예와 같이 CPS 스타일 식에 대한 연속성으로서 ID 함수를 전달함으로써 결과를 얻는다.

고전적 논리 자체는 Scheme의 콜-와 함께-전류-연속 제어 운영자에서처럼 (밀접하게 관련된 C 제어 운영자를 사용) 팀 그리핀에 의한 관측에서처럼 프로그램의 연속성을 직접 조작하는 것과 관련이 있다.[11]

참고 항목

메모들

  1. ^ Sussman, Gerald Jay; Steele, Guy L., Jr. (December 1975). "Scheme: An interpreter for extended lambda calculus" . AI Memo. 349: 19. That is, in this continuation-passing programming style, a function always "returns" its result by "sending" it to another function. This is the key idea.
  2. ^ Sussman, Gerald Jay; Steele, Guy L., Jr. (December 1998). "Scheme: A Interpreter for Extended Lambda Calculus" (reprint). Higher-Order and Symbolic Computation. 11 (4): 405–439. doi:10.1023/A:1010035624696. S2CID 18040106. We believe that this was the first occurrence of the term "continuation-passing style" in the literature. It has turned out to be an important concept in source code analysis and transformation for compilers and other metaprogramming tools. It has also inspired a set of other "styles" of program expression.
  3. ^ Reynolds, John C. (1993). "The Discoveries of Continuations". Lisp and Symbolic Computation. 6 (3–4): 233–248. CiteSeerX 10.1.1.135.4705. doi:10.1007/bf01019459. S2CID 192862.
  4. ^ * Appel, Andrew W. (April 1998). "SSA is Functional Programming". ACM SIGPLAN Notices. 33 (4): 17–20. CiteSeerX 10.1.1.34.3282. doi:10.1145/278283.278285. S2CID 207227209.
  5. ^ * Kelsey, Richard A. (March 1995). "A Correspondence between Continuation Passing Style and Static Single Assignment Form". ACM SIGPLAN Notices. 30 (3): 13–22. CiteSeerX 10.1.1.489.930. doi:10.1145/202530.202532.
  6. ^ 애플, 앤드류 W. (1992년). 계속을 사용한 컴파일. 케임브리지 대학 출판부. ISBN 0-521-41695-7
  7. ^ 마이크 스테이, "계속 지나가는 변신과 요네다 임베딩"
  8. ^ 마이크 스테이, "파이 미적분 II"
  9. ^ Boudol, Gérard (1997). "The π-Calculus in Direct Style". CiteSeerX 10.1.1.52.6034. {{cite journal}}: Cite 저널은 필요로 한다. journal= (도움말)
  10. ^ Barker, Chris (2002-09-01). "Continuations and the Nature of Quantification" (PDF). Natural Language Semantics. 10 (3): 211–242. doi:10.1023/A:1022183511876. ISSN 1572-865X. S2CID 118870676.
  11. ^ Griffin, Timothy (January 1990). "A formulae-as-type notion of control". Proceedings of the 17th ACM SIGPLAN-SIGACT symposium on Principles of programming languages - POPL '90. Proceedings of the Conference on the Principles of Programming Languages. Vol. 17. pp. 47–58. doi:10.1145/96709.96714. ISBN 978-0897913430. S2CID 3005134.

참조