継続について知りたい

はじめに

ずっと理解したいと思って放置していることをこの機会に1つ進めてみよう、ということで、「継続」について今回は書いてみました。schemeの解説を辿るだけだとまた分からないままになりそうなので、普段使ってるphpでの実装を交えつつ。

継続とは

ある時点での処理を続けるための情報(残りの処理)のこと。通常これを表立って取り扱うことはしませんが、意図的にこれを値として明示的に渡す形のプログラミングを継続渡しスタイル（continuation passing style）と呼びます。

これを少しでも理解しよう、というのがこの記事の主旨になります。

まずは具体例

素朴に引数の値をそのまま返す関数を定義します。
※動作環境としてLaravelのtinker上で実施しています。

function id($x)
{
    return $x;
}

これを呼び出して処理結果を出力する関数を定義、実行してみます。dumpはLaravelのヘルパ関数になります。

function runId()
{
    dump(id('hoge'));
}

>>> runId()
^ "hoge"

特になんてことないですが、とりあえずこれを継続渡しスタイルにしてみましょう。処理の途中結果を受けて続きの処理を行うのが継続ですから、こうなります。

function cpsId($x, callable $cont)
{
    $cont($x);
}

2番目の引数で関数を受けてます。これが継続です。これはこの関数の処理結果を受けて何かをする関数です。

ではこれを呼び出す関数はどうなるでしょうか。

function runCpsId()
{
    cpsId('hoge', fn ($result) => dump($result));
}

>>> runCpsId()
^ "hoge"

当然ですが、これはどちらも同じように動きます。何が違うか？ id 関数に存在した return が cpsId 関数には無いですね。つまり関数の呼び出し元へ戻って「継続する」、ということと等価なことが渡されている関数によって明示的に行われている、ということになってます。

もう少し複雑な例として再帰を見てみます。指定の数から0までの数字を足し合わせる関数を再帰で書いてみます。通常は、

function recursion(int $x)
{
    if ($x === 0) {
        return $x;
    }

    return recursion($x - 1) + $x;
}

こんな感じになると思いますが、継続渡しスタイルでは、

function cpsRecursion(int $x, callable $cont)
{
    if ($x === 0) {
        $cont($x);
    } else {
        cpsRecursion($x - 1, fn ($result) => $cont($result + $x));
    }
}

こんな感じになります。実行してみます。

function runRecursion()
{
    dump(recursion(10));
}

>>> runRecursion()
^ 55

function runCpsRecursion()
{
    cpsRecursion(10, fn ($result) => dump($result));
}

>>> runCpsRecursion()
^ 55

return なしで、数珠つなぎで継続が渡されてそこで足し算が行われることに注意してください。

例外

継続渡しスタイルでは例外をどう扱うのでしょうか。通常は例外を発行してtry-catch構文で

function recursionWithException(int $x)
{
    if ($x < 0) {
        throw new Exception('マイナスは不可です');
    }
    if ($x === 0) {
        return $x;
    }

    return recursionWithException($x - 1) + $x;
}

function runRecursionWithException($x)
{
    try {
        dump(recursionWithException($x));
    } catch (Exception $e) {
        dump($e->getMessage());
    }
}

>>> runRecursionWithException(-1)
^ "マイナスは不可です"

これは try-catch によって正常系の処理とは別種のフローが存在することを意味しています。つまり例外というのは正常系とは別の 継続 です。ですからこれは継続渡しスタイルでこのように書くことができます。

function cpsRecursionWithException(int $x, callable $cont, callable $throw)
{
    if ($x < 0) {
        $throw('マイナスは不可です');
    } elseif ($x === 0) {
        $cont($x);
    } else {
        cpsRecursionWithException($x - 1, fn ($result) => $cont($result + $x), $throw);
    }
}

function runCpsRecursionWithException($x)
{
    cpsRecursionWithException($x, fn ($result) => dump($result), fn ($error) => dump($error));
}

>>> runCpsRecursionWithException(-1)
^ "マイナスは不可です"
>>> runCpsRecursionWithException(10)
^ 55

単純に例外時の継続関数を渡します。注目すべきは、try-catch 構文がここでは不要になっている、ということです。処理の 継続 を変数として明示的に扱うことで、例外の構文糖衣を脱糖することができます。

なぜ使うのか

こういった書き方は通常はしないですが、どういう利点があるのでしょうか。ポイントとしては、上記でも分かったように、この継続渡しなスタイルで書くことでreturnを避けることができる、という点になります。

returnする、ということは呼び出し元はそれを待たなければなりません。しかし、それができないケースは多々あります。例えば、これは皆さんもよく使ってるかと思いますが、Ajaxプログラミングでfetchする際、そのレスポンスを待って他の動作を止めることはできません。この場合はcallback関数をfetch処理に渡して、レスポンスを取得した後に呼び出す仕組みが必要になります。

また、Webアプリケーションは、ユーザーに入力を促すフォーム画面を出力した後、ユーザーの入力を待つことはできません（しません）。ですが、ユーザーがフォームを入力してデータをPOSTしてきたならば、そこで何らかの 継続 をサーバー側で行う必要があります。

こういうケースの場合、通常ではサーバー側に何かしらのセッション情報を保持しておき、ユーザーからのフォームデータとの組み合わせで処理を進める実装をします。もしここで継続渡しスタイルが使えるとするならば、継続を保存することにより簡単に続きの処理を再開できるでしょう。(実際にそういうフレームワークもあります)

call/cc

ところで、継続というのはこのようにクロージャの連鎖になります。なので、複数の継続渡しの関数を組み合わせようとするとこうなってしまいます。

function cpsAddOne($x, callable $cont)
{
    $cont($x + 1);
}

function cpsAddTwo($x, callable $cont)
{
    $cont($x + 2);
}

function cpsAddThree($x, callable $cont)
{
    $cont($x + 3);
}

function cpsAddOneTwoThree($x, callable $cont)
{
    cpsAddOne($x, function ($result) use ($cont) {
        cpsAddTwo($result, function ($result) use ($cont) {
            cpsAddThree($result, $cont);
        });
    });
}

これは呼び出しが増えれば増えるほどネストが深くなりちょっと不便です。継続渡しの関数も適宜普通に呼び出せると便利です。

そこで、schemeでは任意のタイミングでの継続を取り出して通常の変数と同じように扱える仕組みが用意されています。 call-with-current-continuation 、略して call/cc という関数がそれになります。

上記のような内容をschemeの call/cc 使って実装すると、こういうのが

(cps-add-one 1 (lambda (ret)
  (cps-add-two ret (lambda (ret)
    (cps-add-three ret (lambda (ret) ret))))))

こういう書き方も可能になります。

(define ret null)
(set! ret (call/cc (lambda (k) (cps-add-one 1 k))))
(set! ret (call/cc (lambda (k) (cps-add-two ret k))))
(set! ret (call/cc (lambda (k) (cps-add-three ret k))))
ret

> 7

これは無名関数の引数 k に継続、ここではトップレベルへ戻って set! されるところへ戻るための関数が渡され、それを呼び出すことで戻ることができるようになってます。この k を current-continuation と呼び、call/cc はそれを任意のタイミングで生成して渡してくれます。

ではphpではどうかというと、残念ながら call/cc のような仕組みはありません。ですので、それに近い実装をしてみようと思います。

function callcc(callable $f)
{
    $ret = null;
    $cc = function ($x) use (&$ret) {
        $ret = $ret ?: $x;
    };

    $f($cc);

    return $ret;
}

これは継続をパラメータとして受ける関数を受けて、関数適用時に渡される値をクロージャの外の変数に設定する継続関数を生成し、渡す関数になります。つまり関数$ccが適用されるとその引数がcallccの戻り値とになる、適用後の継続がスキップされる、ということを意味します。

これを使うと、

function cpsAddOneTwoThreeByCallCC($x, callable $cont)
{
    $result = callcc(fn ($k) => cpsAddOne($x, $k));
    $result = callcc(fn ($k) => cpsAddTwo($result, $k));
    cpsAddThree($result, $cont);
}

上記schemeの例のような書き方ができました。

このコード自体はクロージャ連鎖によるネストを避ける以外に特に何のありがたみも無さそうですが、一つ既視感がある形になってます。つまり、このコードは callcc を使うことで return と等価なことを行っている、return の実装になっている、ということです。

これは次の例を見るとよくわかります。cpsAddThreeがスキップされた計算結果が取得されています。

function cpsReturn($x)
{
    $result = callcc(function ($return) use ($x) {
        cpsAddOne($x, function ($result) use ($return) {
            cpsAddTwo($result, function ($result) use ($return) {
                $return($result);
                cpsAddThree($result, $return);
            });
        });
    });

    dump($result);
}

>>> cpsReturn(1)
^ 4

このphpの callcc ではできないのですが、schemeなどでの実装では任意のタイミングで呼び出し元へ戻る、つまり後続の処理をスキップして return をする、という実装が可能になります。これを応用してループを抜けたり（ break ）、例外処理（ throw ）の実装も可能になります。

まとめ

ここまでで継続なるものの導入部分を書いてみました。call/ccでreturnが実装できる、というあたりで、Haskellの継続モナド関連などがうっすらと思い浮かびましたが、関連が自分にはまだよく分かってないのでとりあえずここまで。

参考

なんでも継続
Scheme/継続の種類と利用例
Kahuaによる継続渡しスタイルWebプログラミング
kahua/Kahua