CPS変換について - fushigu’s blog

はじめに
CPSとは
- CPS変換とコールバック関数
- CPS変換と末尾再帰最適化
おわりに

はじめに

ISer Advent Calendar 2021 - Adventarの記事です．

まじめに書きたいなと思います。

CPSとは

CPSは、Continuation-Passing Styleの頭文字をとって名付けられています。これは継続と呼ばれるものを使ったプログラムの書き方の１つです。継続は、「今行う計算の続きの計算」を表していると考えられます。そして、CPS変換は、通常の書き方をCPSに変換することを指します。

とりあえず、JavaScriptでの例を見てみたいと思います。

次の処理を行うことを考えます。

引数kに1を足す。
上の結果を2倍する。
上の結果から1引く。
上の結果を表示する。

ここでは上の処理一つ一つを関数にして、書いてみたいと思います。

function add1(v) {
    return v + 1;
}
function times2(v) {
    return 2*v;
}
function minus1(v) {
    return v - 1;
}

let initial_value = 1;
console.log(minus1(times2(add1(initial_value))));

これをCPSに変換すると次のようになります。

function add1(k) {
    return function(r) {
        return k(r + 1);
    }
}

function times2(k) {
    return function(r) {
        return k(2*r);
    }
}

function minus1(k) {
    return function(r) {
        return k(r - 1);
    }
}

let inital_value = 1;
let something = add1(times2(minus1(function (r) { console.log(r); })));

上のadd1やdoubleといった関数に渡される引数kはすべて継続です。そして、最後の関数呼び出しが重要です。呼び出し部分だけを抜き出すと、

add1(times(minus1(function (r) { console.log(r); })))

となります。これをじっくりと観察しましょう！

内側から見ていくと、minus1に引数を受け取って表示する関数を渡しています。継続は「今行う計算の続きの計算」であることを思い出せば、これはminus1の後に値を表示するという継続を渡していることになります。

minus1(function (r) { console.log(r); })

つぎは、times2にminus1(hoge)を渡していますね。もう1度、継続は「今行う計算の続きの計算」であることを思い出せば、times2の後にminus1(hoge)を行うのでtimes2の継続はminus1になります。

times(minus1(function (r) { console.log(r); }))

さらに、add1にtimes2(minus1(function(r) { console.log(r); } ))を渡しています。これはadd1した後にtimes2(minus1(function(r) { console.log(r); } ))というこれから行う処理を渡しています。

add1(times(minus1(function (r) { console.log(r); })))

さて、最後にすべての返り値であるsomethingとは何でしょうか？これは、これから行う処理と考えられます。よって、このsomethingを継続としてほかの処理に渡していくことができます。いまは計算を実際に行って、結果を表示する処理まで行いたいです。そうするためには、この関数を評価すればいいことがわかります。そうすると上の1～4までの計算が実際に行われます！

something(1);

CPS変換とコールバック関数

さて、上のような継続はどこかで見たことはないですか？Promiseを扱ったことがある人ならわかると思います。

そうです！コールバック関数*1です。コールバック関数は、呼び出した関数の処理が終わったら呼び出す関数のことですが、言い換えれば「今行う計算の続きの計算」です。

CPS変換と末尾再帰最適化

今度は上で述べたcallbackを意識しながら、再帰関数で書いた階乗のCPS変換を見ていきましょう。

通常は、階乗の計算は次のようになります。

function fact (n) {
    if (n < 1) {
        return 1;
    }
    else {
        return n * fact (n-1);
    }
}

一方、継続を用いた書き方に直すと次のようになっています。

function fact_cps (n, callback) {
    if (n < 1) {
        return callback(1);
    }
    else {
        return fact_cps (n-1, function (r) { return callback(n*r); })
    }
}

実際に使うには、次のようにすればよいです。

fact_cps(4, function(v) { console.log(v); });

ここで末尾再帰最適化の話をしたいと思います。末尾再帰最適化とは、再帰関数において最後に1度だけ関数呼び出しが行われ、処理が終了するように関数を最適化を行うことです。こうすることで関数呼び出しのためにスタックを保持する必要がなくなり、スタックオーバーフローが起きにくくなります。

通常の再帰関数では、n * fact(n - 1)の部分で関数呼び出し後に掛け算が行われます。一方、上のCPS変換後の関数は、最後にfact_cpsの呼び出しが行われて、末尾呼び出しになっています。*2

主張は、CPS変換を理解すると末尾再帰最適化がしやすくなる！ということです。

しかし、上のfact_cpsに掛け算をする関数渡すだけです。関数を渡すことは無駄が多いです。これを何とかできないでしょうか？

実は次のことに注意すると、掛け算する関数を整数と同一視することができます。具体的には次のようになります。

$M: \text{整数を掛ける関数全体}$

$Z: \text{整数}$

$f :M \rightarrow Z\\ ~~~~~a\times \mapsto a$

ここで、 $M,Z$ はモノイドであり、 $f$ はモノイド同型になる。*3 合成が、整数の掛け算になるので関数の合成は掛け算であり、関数を1つの整数で表すことができます。

よって、次のようになります。

function fact_cps2 (n, v) {
    if (n < 1) {
        return v*1;
    }
    else {
        return fact_cps2 (n-1, v*n)
    }
}

次は、末尾再帰最適化が難しいフィボナッチ関数についてみていきたいと思います。

function fib(n) {
    if(n < 2) {
        return 1;
    }
    else {
        return fib(n-1)+fib(n-2);
    }
}

まず、最後にfib(n-1)+fib(n-2)としています。これは、最後は、足し算の処理で終わっており、末尾呼び出しになっていません。では、CPS変換を行いたいと思います。

function fib_cps(n, callback) {
    if (n < 3) {
        return callback(1);
    }
    else {
        return fib_cps(n - 1, function (a) {
            return fib_cps(n - 2, function (b) {
                return callback(a + b);
            })
        })
    }
}

よく見れば、すべての関数が末尾呼び出しになっています。つまり、CPS変換をすると、自然に末尾呼び出しが可能になる！ということです。

おわりに

あんまり理解していないことを記事にするのは、つらいです。*4

*1:正確には違う。イメージとしてぐらいしか正しくない。

*2:-は関数呼び出しではないのかという批判。

*3:あんまり自信がない

*4:誰にも理解されなさそうな記事を書いてしまったなあという気持ちになりました。