継続渡しスタイル
継続渡しスタイル (CPS: Continuation-passing style) とは、プログラムの制御を継続を用いて陽に表すプログラミングスタイルのことである。この用語は、ジェラルド・ジェイ・サスマン とガイ・スティール・ジュニアにより、Scheme言語に関する初期の論文において導入された。
継続渡しスタイルで書かれた関数は、通常の直接スタイル (direct style) のように値を「返す」かわりに、「継続」を引数として陽に受け取り、その継続に計算結果を渡す。継続とは、関数の計算結果を受け取るための(一般には元の関数とは別の)1引数の関数のことである。継続渡しスタイルの関数を呼び出すときは、呼び出し側の関数が、呼び出される関数の「戻り値」を受け取るための継続を与える必要がある。この形でコードを書くと、直接スタイルにおいて暗黙に仮定されていた様々な動作が、陽に表される。例えば、手続きからの復帰が継続の呼び出しとして表される、計算の途中の値がすべて陽に名前を与えられる、引数の評価順序が陽に表される、末尾呼び出しは呼び出される手続きに呼び出し側と同じ継続を渡すことにあたる、等である。
直接スタイルのプログラムはCPSに自動変換することが可能である。関数型言語や論理型言語のコンパイラはCPSを中間表現として用いることがある。命令型言語ないし手続き型言語のコンパイラはしばしば静的単一代入(SSA)形式を用いるが、SSAとCPSはある意味で等価であることが知られている。また、やはり関数型言語のコンパイラの中間表現として用いられることがあるA正規形(A-normal form)も、CPSとの対応関係が(当初から)知られている。