はじめに
Continuation-Passing Style (CPS)は、関数型プログラミングや非同期プログラミングにおいて重要な概念です。CPSを理解することで、複雑な計算や非同期処理の制御が容易になります。この記事では、CPSの基本概念から具体的な例、そしてCPSを活用するメリットまで説明します。
CPSとは何か
CPS（継続渡しスタイル）は、関数の戻り値を直接返すのではなく、「継続」と呼ばれる別の関数に渡すスタイルです。継続は、関数が計算を完了した後に何をすべきかを定義します。これにより、関数の実行が完了した後の処理を明示的に制御できます。
実装例
通常の再帰的実装
// 通常の関数呼び出しでは、計算の結果が直接戻り値として返されます。
function add(a, b) {
return a + b;
}
const result = add(2, 3);
console.log(result); // 5
CPSによる実装
// CPSでは、計算結果は継続に渡されます。
function addCPS(a, b, cont) {
cont(a + b);
}
addCPS(2, 3, result => console.log(result)); // 5
基本的なCPSの例
CPSの基本的な例として、加算と乗算の関数を見ていきます。
加算のCPS
function addCPS(a, b, cont) {
cont(a + b);
}
addCPS(2, 3, result => console.log(result)); // 5
乗算のCPS
function multiplyCPS(a, b, cont) {
cont(a * b);
}
multiplyCPS(2, 3, result => console.log(result)); // 6
これらの関数では、計算結果を継続（cont）に渡すことで処理を進めています。
フィボナッチ数列のCPSによる実装
CPSの概念を使ってフィボナッチ数列を計算する関数を実装してみます。
通常の再帰的実装
function fib(n) {
if (n === 0) return 0;
if (n === 1) return 1;
return fib(n - 1) + fib(n - 2);
}
console.log(fib(10)); // 55
CPSによる実装
type NS = (n: number) => number;
type CPS = (n: number) => (k: NS | CPS) => number;
// fibCPS に n を渡し、最終的に結果を受け取るために恒等関数 x => x を渡します。
const fib: NS = n =>
fibCPS(n)(x => x);
// n が 0 なら ret(0) を返し、1 なら ret(1) を返します。
// それ以外の場合、fibCPS(n - 1) の結果を a とし、さらに fibCPS(n - 2) の結果を b として、
// ret(a + b) を呼び出します。
const fibCPS: CPS = n => {
return n === 0
? ret(0)
: n === 1
? ret(1)
: fibCPS(n - 1)
(a => fibCPS(n - 2)
(b => ret(a + b))
);
}
// ret は、与えられた値 x を継続 k に渡します。これにより、計算が次のステップに進みます。
const ret: CPS = x => k =>
k(x);
// 使用例：
// fib(40) を呼び出すと、fibCPS(40)(x => x) が実行され、フィボナッチ数列の第40項が計算されます。
// fibCPS は再帰的に呼び出され、最終的な結果が ret 関数によって継続に渡されます。
console.log(fib(40)); // 102334155
この実装では、計算結果が次の継続に渡されることで、計算の流れが継続的に進行します。
CPSの利点
非同期処理の容易な実装
CPSは非同期処理の実装において特に有用です。非同期処理の結果を次の継続に渡すことで、コールバック地獄（callback hell）を避け、コードをより直感的に書くことができます。
コントロールフローの明示的な管理
CPSでは、関数の実行が完了した後の処理を継続関数として渡すため、コントロールフローを明示的に管理できます。これにより、複雑な処理やエラーハンドリングが容易になります。
再帰の最適化
CPSは再帰の最適化にも役立ちます。再帰的な関数呼び出しを継続として表現することで、スタックオーバーフローのリスクを軽減し、効率的な再帰処理が可能になります。
まとめ
CPS（継続渡しスタイル）は、関数の戻り値を直接返すのではなく、継続関数に渡すスタイルです。これにより、非同期処理や複雑なコントロールフローを容易に管理できます。非同期プログラミングや高階関数の使用が一般的な関数型プログラミングにおいて特に有用です。