継続渡しスタイル
継続渡しスタイル (CPS: Continuation-passing style) とは、プログラムの制御を継続を用いて陽に表すプログラミングスタイルのことである。この用語は、ジェラルド・ジェイ・サスマン とガイ・スティール・ジュニアにより、Scheme言語に関する初期の論文において導入された[1][2]。
継続渡しスタイルで書かれた関数は、通常の直接スタイル (direct style) のように値を「返す」かわりに、「継続」を引数として陽に受け取り、その継続に計算結果を渡す。継続とは、関数の計算結果を受け取るための（一般には元の関数とは別の）1引数の関数のことである。継続渡しスタイルの関数を呼び出すときは、呼び出し側の関数が、呼び出される関数の「戻り値」を受け取るための継続を与える必要がある。この形でコードを書くと、直接スタイルにおいて暗黙に仮定されていた様々な動作が、陽に表される。例えば、手続きからの復帰が継続の呼び出しとして表される、計算の途中の値がすべて陽に名前を与えられる、引数の評価順序が陽に表される、末尾呼び出しは呼び出される手続きに呼び出し側と同じ継続を渡すことにあたる、等である。
直接スタイルのプログラムはCPSに自動変換することが可能である。関数型言語や論理型言語のコンパイラはCPSを中間表現として用いることがある。命令型言語ないし手続き型言語のコンパイラはしばしば静的単一代入(SSA)形式を用いるが、SSAとCPSはある意味で等価であることが知られている[3]。また、やはり関数型言語のコンパイラの中間表現として用いられることがあるA正規形(A-normal form)も、CPSとの対応関係が（当初から）知られている[4]。
例 編集
以下に直接スタイルと、それに対応する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 ; 末尾再帰でない
(* n (factorial (- n 1)))))
|
(define (factorial& n k)
(=& n 0 (lambda (b)
(if b ; 再帰呼び出しにおいて
(k 1) ; 継続が成長する
(-& 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
(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) ; 継続が変わらない
(-& 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を用いて文の表示を定義することにより、ある種の言語現象を説明できるとされている[1].
数理論理学のカリー＝ハワード同型対応において、CPS変換は、二重否定による古典論理の直観主義論理への埋め込みにあたる。また、古典論理そのものは、Schemeの call-with-current-continuation 制御演算子のように、継続を直に扱うことができるプログラミング言語に対応する[5]。
参考文献 編集
- ^ Gerald Jay Sussman and Guy L. Steele, 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."
- ^ Gerald Jay Sussman and Guy L. Steele, 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. "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."
- ^ * Richard A. Kelsey (March 1995). “A Correspondence between Continuation Passing Style and Static Single Assignment Form”. ACM SIGPLAN Notices 30 (3): 13--22. doi:10.1145/202530.202532.
- ^ Flanagan, Cormac; Amr, Sabry; Bruce F., Duba; Matthias, Felleisen. "The Essence of Compiling with Continuations". Proceedings ACM SIGPLAN 1993 Conf. on Programming Language Design and Implementation, PLDI'93. Albuquerque, NM, USA. Flanagan93. 2007年6月5日閲覧。
- ^ Timothy Griffin. (January 1990). “A formulae-as-type notion of control”. Proceedings of the Conference on the Principles of Programming Languages 17: 47–58.
- The construction of a CPS-based compiler for ML is described in: Appel, Andrew W. (1992). Compiling with Continuations. Cambridge University Press. ISBN 0-521-41695-7
- Olivier Danvy and Andrzej Filinski (1992). “Representing Control, A Study of the CPS Transformation”. Mathematical Structures in Computer Science 2 (4): 361--391. doi:10.1017/S0960129500001535.
- Chicken Scheme compiler, a Scheme to C compiler that uses continuation-passing style for translating Scheme procedures into C functions while using the C-stack as the nursery for the generational garbage collector
- Richard A. Kelsey (March 1995). “A Correspondence between Continuation Passing Style and Static Single Assignment Form”. ACM SIGPLAN Notices 30 (3): 13--22. doi:10.1145/202530.202532.
- Andrew W. Appel (April 1998). “SSA is Functional Programming”. ACM SIGPLAN Notices 33 (4): 17--20. doi:10.1145/278283.278285.
- Danvy, Olivier (2007年). “On One-Pass CPS Transformations”. pp. 24. 2007年10月26日閲覧。
- R. Kent Dybvig (2003). The Scheme Programming Language. Prentice Hall. p. 64 Direct link: "Section 3.4. Continuation Passing Style".
- Tail recursion through trampolining
 | この項目は、ソフトウェアに関連した書きかけの項目です。この項目を加筆・訂正などしてくださる協力者を求めています（PJ:コンピュータ/P:コンピュータ）。 |