[HOME]  [INDEXJavascriptプログラミング

12 継続渡し形式(CPS)

12.1 継続

継続とはコンピュータがプログラムを実行しているときの次に何をするのかを表す概念です。詳しくは何でも継続のページを参照し欲しいのですが、継続はプログラムを実行する上で欠かせない存在となっています。ソースコードのある行を実行したら次の行を実行します。関数(サブルーチン)を終了したら、呼び出し元に戻ります。これらは全て継続です。あたりまえと言えばあたりまえのことです。しかし、このあたり前のことを明確に意識しようとすると途端に目の前に霞がかかったようになります。
上記で紹介したWEBページは次のような言葉で始まります。
プログラミングの世界の概念には、禅の公案のようなものがある。それを説明する文章はほんの一文なのに、最初に目にする時、その文は全く意味をなさない、暗号のように感じられる。だがひとたびその概念を理解すると、その概念の説明は確かにその一文で説明されているのがわかるのだ。
そんな、「分かれば分かる」という禅問答の中でも「継続」は最も謎めいたものの一つと言えるだろう。文献を紐解くと、継続とは「これから行われるであろう計算をパッケージ化したもの」とある。そして、lambdaだらけの説明が後に続くのが普通だ。実は、分かってしまえばlambdaを使うのが最も正確かつ簡潔な説明なのだが、分かるまではあまり役に立たない。
何でも継続 http://practical-scheme.net/docs/cont-j.htmlより
継続Schemeという言語では基本的なデータのひとつとして扱うことができます。Schemeを学ぶ上で最も難しい概念のひとつだと言われています。そのほかにもCommon Lispでは基本データとはなっていないものの継続を扱うマクロも作られており比較的知られた概念となっています。
ここでは継続そのものの詳細な解説はしません。継続の概念を応用した継続渡し形式(Continuation Passing Style)についての説明を行ないたいと思います。

12.2 継続渡し形式(CPS)

継続渡し形式継続ほど難しい考え方ではありません。GUI、WEB、通信などでは普通に使われています。GUIフレームワークなどでは、継続渡し形式をサポートするための手段を提供しています。継続渡し形式Continuation Passing Styleの頭文字を取ってCPSと呼ばれます。継続渡し形式そのものはプログラムの中では継続をクロージャとして定義しコールバック関数として渡します。
コールバックにはふたつのパターンがあります。
ひとつはコールバックを指定した箇所に戻ってからの処理を期待するもの、こちらのコールバックは比較的理解しやすいものが多いような気がします。ソート関数に与える比較関数や繰り返し処理などのブロックになるものがあります。動作も同期的に実行されます。
もうひとつはコールバックを指定した箇所に戻ってからの処理を期待しないもの、こちらの場合クロージャには継続する処理が含まれています。具体的な例としては、GUIのイベントへの応答やAjaxで使われる非同期通信の後処理があります。こちらの方はひとつめのコールバックに比べると理解が難しいものになります。
このように考えると継続渡し形式そのものは何も特別なものではないことがわかります。ただし、継続継続渡し形式の概念を知らないと試行錯誤による実装となり非常に頭を悩ませるものになります。

12.3 継続渡し形式変換(CPS変換)

通常の処理を継続渡し形式に変換します。このような変換を継続渡し形式変換(CPS変換)と呼びます。

12.3.1 簡単な継続渡し形式

まずは、次のような簡単な例を継続渡し形式に変換します。
1|function power(n) {
2|    return n * n;
3|}
4|
5|WScript.Echo("power(4) => " + power(4));
これはべき乗を求めて表示するプログラムです。べき乗を求める処理を継続渡しにします。この例ではべき乗を求める処理があり、その続きの処理は結果を表示するということになります。継続渡し形式に変換すると次のようになります。
1|function power_cps(n, cont) {
2|    cont(n * n);
3|}
4|
5|power_cps(4, function (result) {
6|    WScript.Echo("power_cps(4) => " + result);
7|});
power_cpsが継続渡し形式に変換したべき乗を求める関数になります。引数のcontが継続です。power_cpsはべき乗を求め継続を起動します。
継続はべき乗の計算結果を受け取りそれを表示します。実行した結果は次のようになります。
power_cps(4) => 16

12.3.2 再帰呼び出しの継続渡し形式

次は再帰呼び出しを継続渡し形式に変換する例になります。
1|function fact(n) {
2|    if (n == 0) return 1;
3|    return n * fact(n - 1);
4|}
5|
6|WScript.Echo("fact(7) => " + fact(7));
階乗を求める再帰関数の例です。これを継続渡し形式に変換します。
 1|function fact_cps(n, cont) {
 2|    if (n == 0) {
 3|        cont(1);
 4|    } else {
 5|        fact_cps(n - 1, function (result) {
 6|            cont(n * result);
 7|        });
 8|    }
 9|}
10|
11|fact_cps(7, function (result) {
12|    WScript.Echo("fact_cps(7) => " + result);
13|});

12.3.3 複雑な再帰呼び出しの継続渡し形式

次のフィボナッチ数を求める関数を継続渡し形式に変換してみます。これは、内部で2回再帰呼び出し処理を行なうため、階乗の例に比べると複雑になっています。
function fib(n) {
    if (n == 1 || n == 2) {
        return 1;
    }
    return fib(n - 1) + fib(n - 2);
}

WScript.Echo("fib(7) => " + fib(7));
継続渡し形式への変換は関数側から考えると混乱してきます。使う側から考えます。まず、最後の結果表示から考えます。
fib_cps(7, function (result) {
    WScript.Echo("fib_cps(7) => " + result);
});
これは、引数として 7 を指定して、継続として渡したクロージャで結果を受け取りそれを表示する処理を表します。
これでfib_cpsの基本的な形式が見えてきます。
function fib_cps(n, cont) {
    ・・・
}
引数が 12 の場合、結果は 1 になるので、これを結果として継続に返すことにします。
function fib_cps(n, cont) {
    if (n == 1 || n == 2) {
        cont(1);
    } else {
        ・・・
    }
}
さて、次は少し複雑になります。引数が 12 以外の場合を考えます。最初のfib関数の定義を見ると内部で fib(n - 1)fib(n - 2) の結果を得る必要があります。まず、fib(n - 1) の結果を得るようにしてみましょう。
function fib_cps(n, cont) {
    if (n == 1 || n == 2) {
        cont(1);
    } else {
        fib_cps(n - 1, function (result1) {
            ・・・
        });
    }
}
結果として result1 を受け取ります。その後どうするのでしょうか?再び最初のfibの例を見ると、fib(n - 2) の結果との和を求めています。つまり、続きの処理としては fib_cps(n - 2, ...) を実行することになります。そこで、 fib_cps(n - 1, ...) に渡す継続の中で fib_cps(n - 2, ...) を実行するようにします。
function fib_cps(n, cont) {
    if (n == 1 || n == 2) {
        cont(1);
    } else {
        fib_cps(n - 1, function (result1) {
            fib_cps(n - 2, function (result2) {
            ・・・
            });
        });
    }
}
最後は、fib_cps(n - 1, ...)fib_cps(n - 2, ...) の結果の合計を呼び出し元の継続に渡します。
function fib_cps(n, cont) {
    if (n == 1 || n == 2) {
        cont(1);
    } else {
        fib_cps(n - 1, function (result1) {
            fib_cps(n - 2, function (result2) {
                cont(result1 + result2);
            });
        });
    }
}
全体は次のようになります。
 1|function fib_cps(n, cont) {
 2|    if (n == 1 || n == 2) {
 3|        cont(1);
 4|    } else {
 5|        fib_cps(n - 1, function (result1) {
 6|            fib_cps(n - 2, function (result2) {
 7|                cont(result1 + result2);
 8|            });
 9|        });
10|    }
11|}
12|
13|fib_cps(7, function (result) {
14|    WScript.Echo("fib_cps(7) => " + result);
15|});
これで継続渡し形式となりました。

12.4 継続渡し形式によるループ

繰り返し処理のためのループは再帰呼び出しとして書くことができます。この再帰呼び出しの継続渡し形式を利用することで繰り返しのループを継続渡し形式に変換することができるようになります。
階乗を求める例を繰り返し処理として書きます。これを再帰呼び出しに変換し、さらに継続渡し形式へと変換します。最初はforループによる階乗を求める関数です。
 1|function fact_loop(n) {
 2|    var acc = 1;
 3|    for (var i = 1; i <= n; i++) {
 4|        acc *= i;
 5|    }
 6|    return acc;
 7|}
 8|
 9|WScript.Echo("fact_loop(6) => " + fact_loop(6));
これを再帰呼び出しを使った形式に変換します。再帰呼び出しですが、前に出てきたfact()と異なりfact_loop()でのwhileループを使った場合と同等の処理になっています。
 1|function fact_loop_rec(n) {
 2|    function fact_loop_rec_sub(i, acc) {
 3|        if (i <= n) {
 4|            acc *= i;
 5|            return fact_loop_rec_sub(i + 1, acc);
 6|        }
 7|        return acc;
 8|    }
 9|    
10|    return fact_loop_rec_sub(1, 1);
11|}
12|
13|WScript.Echo("fact_loop_rec(6) => " + fact_loop_rec(6));
これを継続渡し形式に変換します。
 1|function fact_loop_cps(n, cont) {
 2|    function fact_loop_cps_sub(i, acc, cont) {
 3|        if (i <= n) {
 4|            acc *= i;
 5|            fact_loop_cps_sub(i + 1, acc, function (result) {
 6|                cont(result);
 7|            });
 8|        } else {
 9|            cont(acc);
10|        }
11|    }
12|    
13|    fact_loop_cps_sub(1, 1, function (result) {
14|        cont(result);
15|    });
16|}
17|
18|fact_loop_cps(6, function (result) {
19|    WScript.Echo("fact_loop_cps(6) => " + result);
20|});

12.5 処理のぶつ切り

さて、ここからが本題です。
これまで例として扱ってきた処理をブラウザ上で実行することを考えましょう。計算の進行状況を表示するために途中経過を表示するようにします。最初は、fact_loop()をブラウザ上で実行するようにします。
<html>
<head>
  <title>fact</title>
<script language="Javascript">

function writeLine(text) {
    var value = document.mainForm.resultArea.value + text + "\n";
    document.mainForm.resultArea.value = value;
}

function fact_loop(n) {
    var acc = 1;
    for (var i = 1; i <= n; i++) {
        acc *= i;
        writeLine("fact_loop(" + n + ") i=" + i + " acc=" + acc);
    }
    return acc;
}

function startButtonClick() {
    writeLine("fact_loop(10) => " + fact_loop(10));
}

</script>
</head>
<body>
<form name="mainForm">
  <input type="button" name="startButton"
    value="START" onclick="startButtonClick()" /><br />
  <textarea name="resultArea" cols="40" rows="15"></textarea>
</form>
</body>
</html>
例が単純なためSTARTボタンをクリックするとすぐに結果が表示されます。しかし、このプログラムは作者の意図どおり実行されているとは言えない点があります。それは、もっと時間のかかる処理の場合に明らかになりますが、結果が出てから途中経過も含めて一度に表示されています。
それでは、継続渡し形式を使ってみます。fact_loop_cps()をそのまま使うとfact_loop()と同じ結果になります。実はfact_loop_cps()では内部のfact_loop_cps_sub()関数を呼び出した後、制御が戻ってくることを期待しなくてもよくなっています。そこでsetTimeout関数を使ってfact_loop_cps_sub()関数の実行を行なうようにします。fact_loop_cps_sub()の呼び出しを引数なしのクロージャの内部で行なうようにして、このクロージャをsetTimeout関数に渡します。
<html>
<head>
  <title>fact</title>
<script language="Javascript">

function writeLine(text) {
    var value = document.mainForm.resultArea.value + text + "\n";
    document.mainForm.resultArea.value = value;
}

function fact_loop_cps(n, cont) {
    function fact_loop_cps_sub(i, acc, cont) {
        if (i <= n) {
            acc *= i;
            writeLine("fact_loop_cps(" + n + ") i=" + i + " acc=" + acc);
            setTimeout(function () {
                fact_loop_cps_sub(i + 1, acc, function (result) {
                    cont(result);
                });
            }, 0);
        } else {
            cont(acc);
        }
    }
    
    setTimeout(function () {
        fact_loop_cps_sub(1, 1, function (result) {
            cont(result);
        });
    }, 0);
}

function startButtonClick() {
    fact_loop_cps(10, function (result) {
        writeLine("fact_loop_cps(10) => " + result);
    });
}

</script>
</head>
<body>
<form name="mainForm">
  <input type="button" name="startButton"
    value="START" onclick="startButtonClick()" /><br />
  <textarea name="resultArea" cols="40" rows="15"></textarea>
</form>
</body>
</html>
サンプルではタイムアウト時間に0を指定していますが、ここに大きな数を指定するとゆっくり実行され途中結果が順番に表示されていく様子を見ることができます。
ここでもう一点注目して欲しいのはfact_loop_cps()の内部ではsetTimeoutの呼び出しが終了した時点で制御が呼び出し元に戻っているという点です。つまり、このようにすることでスタックオーバーフローを回避できます。ただし、記憶領域については各関数やクロージャが呼び出された時点の環境が保持されるためすべての処理が終了されるまで解放されないことになります。無限ループにならないように注意する必要があります。

12.6 非同期通信

Ajaxの普及で有名になったXmlHttpRequestによる非同期通信ですが、実際の使用例を見るとコールバックだらけで使いづらい印象を持ちます。そこでこの非同期通信を行なう処理を継続渡しの視点で整理します。
// XML Http オブジェクト生成関数

var makeXMLHttpRequest = null;
if (window.XMLHttpRequest) {
    makeXMLHttpRequest = function () {
        return new XMLHttpRequest();
    };
} else if (window.ActiveXObject) {
    makeXMLHttpRequest = function () {
        return new ActiveXObject("Microsoft.XMLHTTP");
    };
}

// 非サポートブラウザ表示

if (makeXMLHttpRequest == null) {
    alert("ご利用のブラウザでは、当サイトをご利用いただけません。");
}

// 非同期通信処理

var timeoutSeconds = 10;

function httpRequest(method, url, headers, data, cont) {
    var httpObj = null;
    try {
        httpObj = makeXMLHttpRequest();
    } catch (e) {
        cont(1, "オブジェクトが生成できません。");
    }
    if (httpObj) {
        var timeoutCount = timeoutSeconds;
        var timerId = setInterval(function () {
            if (--timeoutCount == 0) {
                clearInterval(timerId);
                cont(2, "通信でタイムアウトが発生しました。");
            }
        }, 1000);
        
        httpObj.open(method, url, true);
        httpObj.onreadystatechange = function () {
            if (httpObj.readyState == 4) {
                clearInterval(timerId);
                if (httpObj.status >= 200 && httpObj.status < 400) {
                    cont(httpObj.status, httpObj.responseText);
                } else {
                    cont(httpObj.status, httpObj.statusText);
                }
            }
        };
        if (headers) {
            for (var x in headers) {
                httpObj.setRequestHeader(x, headers[x]);
            }
        }
        httpObj.send(data);
    }
}

// GETリクエスト

function httpGet(url, cont) {
    httpRequest("GET", url, null, "", cont);
}

// POSTリクエスト

function httpPost(url, headers, data, cont) {
    httpRequest("POST", url, headers, data, cont);
}

// エラー表示

function isHttpError(name, status, text) {
    if (status < 200) {
        alert(text);
    } else if (status >= 400) {
        alert(name + " : " + status + " : " + text);
        return true;
    }
    return false;
}
この関数群を使うと、ボタンをクリックしてリクエストを行い、その結果をDOMに設定するという処理を次のように書くことができるようになります。
function requestButtonClick(event) {
    httpGet("http://foo.co.jp/foo.html", function (status, text) {
        if (!isHttpError("request", status, text)) {
            document.getElementById("foo").innerHTML = text;
        }
    });
}
非同期通信処理も書きやすくなると思います。
次の例はJavascriptのファイルを動的にロードする関数です。
// Javscriptファイルのロード

function loadScript(url, cont) {
    httpGet(url, function (status, text) {
        if (!isHttpError("loadScript", status, text)) {
            if (cont) {
                cont(eval(text));
            } else {
                eval(text);
            }
        }
    });
}
この関数にも継続を渡すことができます。継続を渡していないときは受信したファイルを evel(text); で評価するだけですが、継続を渡されているときは evel(text); の結果を引数にして継続を実行します。

12.6.1 未来の選択

継続渡しを使うことで、未来の選択をゆだねることもできます。上の非同期通信の例では、通信に成功した場合と成功した場合を同じ継続で受け取るようにしていますが、これを異なる継続で受け取るようにすることもできます。
// 非同期通信処理

var timeoutSeconds = 10;

function httpRequest(method, url, headers, data, contOk, contError) {
    var httpObj = null;
    try {
        httpObj = makeXMLHttpRequest();
    } catch (e) {
        contError(1, "オブジェクトが生成できません。");
    }
    if (httpObj) {
        var timeoutCount = timeoutSeconds;
        var timerId = setInterval(function () {
            if (--timeoutCount == 0) {
                clearInterval(timerId);
                contError(2, "通信でタイムアウトが発生しました。");
            }
        }, 1000);
        
        httpObj.open(method, url, true);
        httpObj.onreadystatechange = function () {
            if (httpObj.readyState == 4) {
                clearInterval(timerId);
                if (httpObj.status >= 200 && httpObj.status < 400) {
                    contOk(httpObj.responseText);
                } else {
                    contError(httpObj.status, httpObj.statusText);
                }
            }
        };
        if (headers) {
            for (var x in headers) {
                httpObj.setRequestHeader(x, headers[x]);
            }
        }
        httpObj.send(data);
    }
}
contOkには通信に成功したときの継続を渡します。contOkは通信結果を受け取る引数をひとつだけ受け取るようにします。
contErrorには通信に失敗したときの継続を渡します。contErrorはエラーコードとメッセージを受け取るふたつの引数を受け取るようにします。
使い方は次のようになります。
funciton alertHttpError(status, message) {
    if (status < 200) {
        alert(text);
    } else if (status >= 400) {
        alert(name + " : " + status + " : " + message);
    }
}

function requestButtonClick(event) {
    httpRequest("GET", "http://foo.co.jp/foo.html", "",
        function (text) {
            document.getElementById("foo").innerHTML = text;
        },
        alertHttpError
    );
}

12.7 まとめ

クライアント側で継続渡しを利用するとブラウザ上で長いスクリプトを実行する場合に、ブラウザが出すスクリプトの処理が長過ぎると言うメッセージを回避することができます。また、ブラウザが固まったようになる現象も回避できます。
サーバ側では、前処理画面表示(ブラウザ)後処理という一連の流れを整理しやすくなります。ただし、サーバ側の処理系で継続渡しを扱うことができる必要があります。Gauche(SCHEMEの一種)で作られたkahuaというWEBアプリケーションサーバでは継続渡しを基本とすることで処理を作りやすくしています。
継続渡し形式を使うとアプリケーションとしての処理の流れとシステムとしての制御の流れを分離することができます。これは使い方によっては強力な手段になるでしょう。
ただし、正直なところ継続渡し形式に変換された処理は読みやすいとは思いません。使いどころに注意してください。