CPS(継続渡しスタイル)のプログラミングに入門する

モチベーション

研究室の教授からCPSというものを教えてもらったものの、とても難しかったので、理解で
きた部分を書き残しておこうと思います。

CPSの意義

CPS(continuation-passing style, 継続渡しスタイル)は関数の第1引数に、「後に続く処理」を渡すプログラミングスタイルです。
普通のCやJavaでのプログラミングでは、「後に続く処理」はセミコロンと改行の後に続く式になりますが、CPSでは引数で渡された関数に続くことになります。この「後に続く処理」は継続と呼ばれます。

CPSのスタイルでプログラミングをすることで、処理系に手を加えることなく継続を扱うことが出来るようになるため、try-catchのような例外処理や、コルーチンをライブラリのレベルで実装できるそうです。

以下では、CPSのスタイルで書かれた関数を「CPSな関数」と呼ぶことにします。

CPS(継続渡しスタイル)の例

クロージャを持つ言語ならプログラムをCPSで書くことが出来ます。今回はPythonで書きます。CPSの関数の第1引数に継続を表すクロージャを渡します。この引数のクロージャは**陽に表された(explicit)**継続と呼ばれます。
陽に表された継続は、ここでは整数の引数を1つ取り、返り値が無い関数(int -> void)とします。

以下の例ではprintを継続として渡しています。

インクリメント

hoge.py

#直接スタイル
def inc(x):
    return x+1

print(inc(5))

#CPS
def inc_c(cont, x):
    cont(x+1)

inc_c(print, 5)

加算

hoge.py

#直接スタイル
def add(x, y):
    return x+y

print(add(2, 5))

#CPS
def add_c(cont, x, y):
    cont(x+y)

add_c(print, 2, 5)

関数の呼び出し方

CPSな関数を1つだけprintするのは単純ですが、複数の処理を続けて書くには、継続として渡す(int -> void)の関数を意識した書き方が必要です。以下ではk1, k2, k3が継続を表す関数になります。

hoge.py

def inc_c(cont, x):
    cont(x+1)

def add_c(cont, x, y):
    cont(x+y)

def execute():
    def k1(v1):
        def k2(v2):
            def k3(v):
                print(v)
            inc_c(k3, v2)
        add_c(k2, v1, 5)
    add_c(k1, 1, 3)
    
execute()

output

10

lambdaで継続を表して書いてみます

hoge.py

def inc_c(cont, x):
    cont(x+1)

def add_c(cont, x, y):
    cont(x+y)

def execute():
    add_c(
        lambda v1: add_c(
            lambda v2: inc_c(
                lambda v3: print(v3)
            , v2)
        , v1, 5), 
    1, 3)
    
execute()

C++で書いてみます

hoge.cpp

#include<iostream>

using namespace std;

void inc_c(void(*cont)(int), int x) {
    cont(x+1);
}

void add_c(void(*cont)(int), int x, int y) {
    cont(x+y);
}

void execute() {
    add_c(
        [](int v1) {add_c(
            [](int v2) {inc_c(
                [](int v3) {cout << v3 << endl; }
            , v2); }
        , v1, 5); }
    , 1, 3);
}
    
int main() {
    execute();
}

call/cc(call-with-current-continuation)

call/ccという考え方がCPSを活用する鍵になります。
call/ccは「現在の継続とともに関数を呼び出す」という考え方です。現在の継続(current-continuation)が指す現在は、call/ccを行った時の事で、継続は呼び出し元の継続の事です。つまり、call/ccは「「call/ccの呼び出し元の、call/ccを呼び出した時の継続」とともに関数を呼び出す」という機能になります。
call/ccはCPSに限られた考え方ではありませんが、CPSなしでcall/ccをサポートしている言語はSchemeなど、一部の関数型言語に限られているようです。
CPSで書かれたプログラムであれば、どのような言語でもcall/ccを簡単に実装することが出来ます。call/ccのCPSのスタイルでのPythonでの実装は以下になります。

hoge.py

def callcc(cont, f):
    f(cont, lambda _c, v: cont(v))

callcc関数は、第2引数に呼び出す関数fをとり、その関数fの第2引数に現在の継続を表すlambdaを渡して呼び出すという動作をします。
callccに渡って来る関数fもCPSな関数なので、当然、fの第1引数には継続contが入ります。そのため、「これだけで現在の継続が渡せているじゃないか？」という気分になりますが、CPSでの第1引数の継続はCPSのコンテクストとしての裏方に徹するべきなので、第2引数で明示的にcontを渡します。
この際、CPSの「第1引数に継続をとる」というルールに沿うために、「第1引数に継続を取り、それを無視するlambda」にラップされて渡されています。
このlambdaをcallccの呼び出し先の関数から呼ぶと、callccの呼び出し元に帰ることが出来ます。

callccの使用例

callccを呼び出す側と呼び出される側を見てみます。callccを呼び出す側については、CPSな関数であれば特に制約はありません。

呼び出す側

hoge.py

def execute(cont, x):
    def k1(v):
        def k2(v):
            print_c(cont, v)
        callcc(k2, func)
    print_c(k1, x)

callccにより関数funcを呼び出ししています。

呼び出される側

呼び出される側は第1引数にCPSのコンテクストとしての継続をとり、第2引数にcall/ccにより生成された現在の継続を取る関数である必要があります。

hoge.py

def func(cont, cc):
    def k1(v):
        cc(cont, 88)
    print_c(k1, "func")

print_cをした後、callccにより作成された現在の継続であるccを呼び出して、元の関数に戻っています。このようにcallcc先から元の関数に戻ることを大域脱出(Non-Local Exits)と言うようです。

プログラム全体

hoge.py

def callcc(cont, f):
    f(cont, lambda _c, v: cont(v))

def print_c(cont, x):
    print(x)
    cont('void')

def func(cont, cc):
    def k1(v):
        cc(cont, 88)
    print_c(k1, "func")

def execute(cont, x):
    def k1(v):
        def k2(v):
            print_c(cont, v)
        callcc(k2, func)
    print_c(k1, x)

execute(lambda v: v, 55)

出力

output

55
func
88

C#のTaskっぽい書き方

C#が好きなのでC#のTaskっぽい書き方で継続を呼び出してみます。

hoge.py

def callcc(cont, f):
    f(cont, lambda _c, v: cont(v))


def print_c(cont, x):
    print(x)
    cont('void')


def func(cont, cc):
    def k1(v):
        cc(cont, 88)

    print_c(k1, "func")


class Task:
    func = None
    arg = None

    def __init__(self, _func, _arg):
        print("init:")
        self.func = _func
        self.arg = _arg

    def continueWith(self, _cont):
        self.func(_cont, self.arg)


def execute2(cont, x):
    Task(print_c, x).continueWith(
        lambda v1: Task(callcc, func).continueWith(
            lambda v2: Task(print_c, v2).continueWith(cont)))

execute2(lambda v: v, 55)

個人的には結構好きな書き方になりました。

CPSによるコルーチン

最後に、Python/CPSでのcall/ccを使ったコルーチンを紹介します。

hoge.py

def callcc(cont, f):
    f(cont, lambda _c, v: cont(v))

def print_c(cont, x):
    print(x)
    cont('void')

def f_c(cont, k):
    def k1(v):
        def k2(v):
            f_c(cont, v)
        callcc(k2, k)
    print_c(k1, "f")

def g_c(cont, k):
    def k1(v):
        def k2(v):
            g_c(cont, v)
        callcc(k2, k)
    print_c(k1, "g")

f_c(lambda v: v, g_c)

1. 一番最初の処理で、f_cを呼び出しています。その際、g_cを現在の継続として渡しています。
2. f_c内で現在の継続kをcallccで呼び出しています。kはg_cです。
3. g_cが呼ばれます。その際、現在の継続としてlambda c, v: k2(v)が渡ります。このk2はf_c内のk2です。
4. g_c内で現在の継続kをcallccで呼び出しています。kはlambda c, v: k2(v)です。このk2はf_c内のk2です。
5. lambda c, v: k2(v)が呼ばれます。このk2はf_c内のk2です。その際、現在の継続としてlambda c, v: k2(v)が渡ります。このk2はg_c内のk2です。
6. k2が呼ばれます。このk2はf_c内のk2です。k2からf_cが呼ばれます。
7. f_c内で現在の継続kをcallccで呼び出しています。kはlambda c, v: k2(v)です。このk2はg_c内のk2です。
8. lambda c, v: k2(v)が呼ばれます。このk2はg_c内のk2です。その際、現在の継続としてlambda c, v: k2(v)が渡ります。このk2はf_c内のk2です。
9. k2が呼ばれます。このk2はg_c内のk2です。k2からg_cが呼ばれます。
10. g_c内で現在の継続kをcallccで呼び出しています。kはlambda c, v: k2(v)です。このk2はf_c内のk2です。
    ・
    ・
    ・

このようにcall/ccと大域脱出を繰り返すことでコルーチンを形成します。

感想

自分で手を動かして書いてみると、少しCPSの書き方に慣れた気がします。

参照

Continuations Made Simple and Illustrated
Denys Duchier