第1回継続勉強会を開催しました

最近自分の中で継続熱が高まっているので、継続の話をできる場所が欲しくなりました。とはいっても、そもそも継続の知識を持っている人が少ないので、そこを広めるところから始めることにしました。社内でも継続を理解したいという人がおり、その人たちも勉強会を開きたいという話をしていたため、継続勉強会を開くことにしました。

とりあえずの目標としては、浅井先生のshift/resetプログラミング入門(PDF)を理解するところまでとしました。第0回は社内で試しにどこまで行けそうかを見てみて、6回で1章と2章が終えられそうだったので、隔週開催でまずは6回やってみることにしました。

ここでは第1回でやった内容を紹介します。

continuation.connpass.com

やったこと

会の趣旨の説明と、テキストを2.5まで進めました。思ったよりも進みが早く、用意していたメモが尽きかけました。このあたりの話を理解するのに結構時間がかかったので、衝撃的でした。

shift/resetプログラミング入門メモ

以降はshift/resetプログラミングを読み進めるために補足説明等が必要な部分を補うためのメモです。第1回継続勉強会では、これをもとにすすめました。ので、単体で読んでも色々と繋がっていないです。副読書としてどうぞ。

全体

読み進めるうちに「継続ってなんだっけ？」となったら、継続を「後続処理」と読み替えるといいかもしれません。

概要

継続の概念はどのプログラミング言語においても現れる普通の概念である

とありますが、「どんな言語でも、どこでも"考えられる"概念」であり、どんな言語でも現れるかというとそうではないように感じまし。実際、継続をファーストクラスとして扱える言語は限られているため、後述の継続渡しスタイルを用いない限りはプログラム中で明には扱えません。分岐や例外やgotoは、あくまで「継続という考え方でとらえることもできる」というものであり、それらを使うことがすなわち継続という概念を使っていることにはならないと思っておいた方が気が楽になると思います。

はじめに

普通のブロック構造では書きにくい制御構造

複雑な計算を書こうと思うと、しばしば普通のブロック構造では書きにくい制御構造を扱わなくてはならなくなる。

とありますが、具体的な例がありません。

書きにくいかどうかは別にして、例えば多重ループからの break や continue による脱出は、「ラベル構文」と「脱出構文」を組み合わせて実現することが多いです。

// C#
outer: // ラベル構文
while (true) {
    while (true) {
        if (cond) break outer; // 脱出構文
        ...
    }
    ...
}

継続であれば、「継続」という仕組み1つで成立するため、よりシンプルになります。

// C#に継続を入れたつもりの言語
callcc(k => {
    while (true) {
        while (true) {
            if (cond) k();
            ...
        }
        ...
    }
    k();
});

callcc は、呼び出された時点「以降の処理」を関数に変換(これを継続と呼ぶ)し、callcc に渡された関数に継続を渡して実行します。言葉だと分かりにくいのでコードで説明します。

var res = 1 + callcc(k => k(2)) + 3;

このコードで k に渡されるのは、 callcc を呼び出した時点以降の処理が関数に変換されたものなので、「callcc の結果に3を加える」となります(1を足す処理は callcc を呼び出した時点では終わっているため、継続には含まれません)。処理は以下のように進みます。

callcc 呼び出し以前の処理が実行される
callcc 呼び出し以降の処理が関数化される
callcc に渡した関数が呼び出され、引数としてstep2で関数化されたものが渡される
callcc 内に渡した関数の中で引数(継続)に値を渡すと、 callcc 呼び出し自体の値としてそれが使われて以降の処理が実行される
- つまり、継続を起動すると callcc を呼び出した場所に「脱出」する

上記のコードでは継続 k に 2 を渡しているので、callcc 呼び出し自体は 2 となります(step4)。結果、上記コードは var res = 1 + 2 + 3; と同じ意味のコードになります。

これを踏まえて再度多重ループからの脱出のコードを見てみましょう。

callcc(k => {
    while (true) {
        while (true) {
            if (cond) k();
            ...
        }
        ...
    }
    k();
});

このコードでは、何らかの条件 cond が true に評価された場合に継続を起動しています。継続を起動すると callcc 呼び出しから脱出するため、2重の while を break するのと同じ意味になります。

継続を使うとシンプルになる他の例として、高階関数とラムダ式を用いて制御構文を模倣、拡張するテクニックが広く知られていますが、 C#をはじめとした多くの手続き型言語では、この方法によって作られた関数は制御構文とは一部異なる振る舞いになります。例えば、 foreach によるループを模倣する場合、C#では

public static void ForEach<T>(this IEnumerable<T> xs, Action<T> a) { ... }

のような関数を定義することで、

foreach (var s in xs) {
    Console.WriteLine(s);
}

の代わりに

xs.ForEach(s => {
    Console.WriteLine(s);
});

のように書けます*1。しかし、このラムダ式の中で return を使った場合の挙動は、組み込みの foreach を使った場合と ForEach を使った場合では異なるものとなります。

public void F1(IEnumerable<string> xs) {
    foreach (var s in xs) {
        if (s == "exit") return; // F1からreturn
        Console.WriteLine(s);
    }
}

public void F2(IEnumerable<string> xs) {
    xs.ForEach(s => {
        if (s == "exit") return; // (F2ではなく)ラムダ式からreturn
                                 // foreach内でのcontinueと同じ意味
        Console.WriteLine(s);
    });
}

これも、 return ではなく継続を言語機能として提供することでシンプルに解決できます。

// C#ではない何か
public void F3(IEnumerable<string> xs) {
    callcc(k => {
        xs.ForEach(s => {
            if (s == "exit") k(); // F3から脱出(F1の例と同じ挙動)
            Consolw.WriteLine(s);
        });
        k();
    });
}

さらに、 continue も継続で実現できます。

// C#ではない何か
public void F4(IEnumerable<string> xs) {
    xs.ForEach(s => {
        callcc(k => {
            if (s == "exit") k(); // 今回のループからの脱出
            Console.WriteLine(s);
            k();
        });
    });
}

この例では break と return が同じ意味になるので説明しませんが、それらが異なる意味になる場合でも継続で実現可能です。

継続渡し形式

Continuation Passing Styleの和訳で、継続渡しスタイルとも言われます。CPSと略されます。継続渡し形式でないものを、直接形式(Direct Style)と呼びます。

Direct Styleの例

double F(double x, double y) {
    double a = Math.Pow(x, 2);
    double b = Math.Pow(y, 2);
    return Math.Sqrt(a + b);
}

CPSの例

戻り値を使わず、すべてコールバックを使い、コールバックの引数として結果を渡すようにします。

void F(double x, double y, Action<double> k) {
    PowCps(x, 2, a =>
        PowCps(y, 2, b =>
            SqrtCps(a + b, result => k(result))));
}

SchemeやStandard MLのcall/cc

継続を扱う命令で最も有名なのは Scheme や Standard ML の call/cc である。

とありますが、Standard MLの仕様にはcall/ccは含まれていないはずで、あくまで処理系(SML/NJやMLton)が実装している機能です。

call/ccの使いにくさ

call/cc に渡す関数の引数(今までの例での k)が継続ですが、 call/cc では受け取った継続はプログラム終了までの処理を含んでいるため、この継続を起動すると呼び出し元には戻ってきません。これは、継続の範囲が「以降のプログラム全体」となっているためです。

例えば、以下のプログラムでは、k() 以降に書いた処理は実行されません。

// C#ではない何か
public void F() {
    callcc(k => {
        k();
        Console.WriteLine("このコードは実行されない。");
    });
}

多相の型システム

JavaやC#でいう、ジェネリクスを持っているということです。

変更可能なセル

再代入可能な変数と思えば大丈夫です。

shift/resetプログラミング

3 + [・] - 1

元のプログラムはこうでした。

3 + 5 * 2 - 1

このプログラムで次に実行すべき部分は 5 * 2 の部分です(加減算よりも乗算の方が優先度が高い)。この「次に実行すべき部分」をhole(穴という意味)にしたプログラムはこうなります。

3 + [・] - 1

これを callcc を使ってよりプログラムらしく表現するとこうなります。

3 + callcc(k => k(5 * 2)) - 1

継続は、「holeの値を受け取ったら、その後の計算を行う」という意味で関数と似たような概念である。

とあるように、継続 k はここでは関数として表現されています。継続処理を実行することをこのテキストでは「継続を起動する」と表現します。上の例では、10(5 * 2の結果)を渡して継続を起動しています。

このプログラムにおいて k は、以下のような定義になっていると考えられます。

Func<int, int> k = (int result) => 3 + result - 1;

callcc は、その時点の継続を取り出し、渡されたラムダ式の引数に関数として渡してくれます。取り出す以外にも、切り取るや取り除く、取るなどと表現することもあります。

raise Abort

C#でいう throw new Exception(); です。

練習問題1

OchaCamlでは二項演算子は右の項から実行する点に注意してください。
if cond then a else b は、C#での条件演算子 cond ? a : b に相当します。また、= は == に、^ は +(文字列の連結)に相当します。
fst は2要素タプル (a, b) の1要素目を返します。また、let x = y in z は var x = y; z に相当しますが、C#とは異なり式であり、z の評価結果が let 式全体の評価結果となります。
string_length は文字列の長さを返し、string_of_int は数値を文字列に変換します。

reset (fun () -> M)

C#風に書くと reset(() => M) です。 M の中に、後述する shift を含まない場合、M と書いた場合と同じです。

var s1 = reset(() => "hello"); // 下と同じ
var s2 = "hello";

Mを実行中の継続

callcc 的なもので継続を取り出したように、reset で区切られた継続を取り出せる関数が shift です。

「Mを実行中の継続」というよりは、「shift によって取り出される継続」といった方がより正確かもしれません。

try ... with Abort -> ...

C#での try { ... } catch (Exception e) { ... } ですが、式なので値を持つという点が異なります。無理やり表現するなら、次のような感じでしょうか。

Func<T>(() => {
    try {
        ...
    } catch (Exception e) {
        ...
    }
})();

*1:この例ではラムダ式は不要だが、説明のために使っている。