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

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

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

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

continuation.connpass.com

やったこと

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

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

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

全体

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

概要

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

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

はじめに

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

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

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

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

// 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 を呼び出した時点では終わっているため、継続には含まれません)。 処理は以下のように進みます。

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

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

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

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

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

継続を使うとシンプルになる他の例として、高階関数ラムダ式を用いて制御構文を模倣、拡張するテクニックが広く知られていますが、 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();
        });
    });
}

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

継続渡し形式

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))));
}

SchemeStandard MLのcall/cc

継続を扱う命令で最も有名なのは SchemeStandard 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("このコードは実行されない。");
    });
}

多相の型システム

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

変更可能なセル

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

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

  1. OchaCamlでは二項演算子は右の項から実行する点に注意してください。
  2. if cond then a else b は、C#での条件演算子 cond ? a : b に相当します。また、=== に、^+(文字列の連結)に相当します。
  3. fst は2要素タプル (a, b) の1要素目を返します。また、let x = y in zvar x = y; z に相当しますが、C#とは異なり式であり、z の評価結果が let 式全体の評価結果となります。
  4. 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:この例ではラムダ式は不要だが、説明のために使っている。

多値について本気で考えてみた

先日のエントリの反応として、多値の批判をしているように受け取られた方がいました。 実際には、多値の批判をしているのではなく、Go言語の「多値とそう見えるけど違うものがある」という仕様を批判したものでした。

また、タプルにこだわっているという受け取り方をした方もいました。 このエントリでは、「タプルにこだわっているのではない、多値にこだわっているのだ」ということを説明しようと思います。 このエントリで出てくるコードは言及がない限り妄想上のもので、実際の言語のコードではありません。

長いから3行で。

  • スタックマシンと多値は仲良し。継続と多値も仲良し。
  • 多値は多値、タプルはタプル、みんなちがってみんないい。
  • 多値とは、カンマで区切られた単なる複数の値だよ。妄想だけどね。

これで満足して仕事に戻っていただいて構いません。以下オマケ。

多値とタプルの違い

まず、多値とタプルの意味的な違いについてをはっきりさせておきましょう。 ただし、多値はタプルと違って扱える言語が少ない*1うえ、各言語での違いもそれなりに大きいため、ここで紹介する違いは参考程度に考えてください。

他の値の一部になれるかどうか

タプルは何の制約もない、単なる値です。 そのため、他の値の一部になれます*2。 当然、タプルの要素にタプルを入れるという風に、入れ子構造も取れます。

それに対して、多値は他の値の一部にはなれません。 例えば、クラスのフィールドに多値を含むこともできませんし、多値の要素として多値を含むこともできません。 これを、制約の付いた型と見なすこともできますが、単に多値はファーストクラスのオブジェクトではないと考えてもよいでしょう。

多値は制限されたタプルなのか

ここまででは、多値は制限されたタプルであり、多値には何のメリットもないとしか思えないかもしれません。 しかし、多値には効率という大きなメリットがあるのです。 その話に入る前に、多値と相性のよいものについて見ていきましょう。 スタックマシンと、継続です。

スタックマシンと多値

まずはスタックマシンです。 スタックマシンというのは、スタックを用いて計算を行う計算機のことを言いますが、ここでは詳細には踏み込みません。 Java仮想マシンや、.NETのCLRや、RubyVM(旧称YARV)などもスタックマシンをベースにしています。少なくとも30億のデバイスでスタックマシンは動いていることになりますね。すごい。

スタックマシンでの関数呼び出し

スタックマシンでは、引数をスタックに積んでから関数に処理を移すだけで関数呼び出しができます。 例えば、Javaで次のようなメソッドを書いたとしましょう。

public static int add(int a, int b) {
    return a + b;
}

このメソッドを add(10, 20) のように呼び出した場合、以下のようなバイトコードが出力されます。

bipush 10           // byte範囲に収まる数値10をpush
bipush 20           // byte範囲に収まる数値20をpush
invokestatic add    // addメソッドを呼び出す

これをスタックの状態を含めて図にすると、このような感じになります。

|    | bipush 10 |    | bipush 20 | 20 | invokestatic add |    |
|    |---------->| 10 |---------->| 10 |----------------->| 30 |
+----+           +----+           +----+                  +----+

まさに、スタックに引数を積んでから関数が呼び出されています。 そして、結果はスタックに積まれます。

関数から戻る場合はどうでしょうか。 上で作った addバイトコードを見てみましょう。

iload_0 // 0番目の引数を整数としてpush
iload_1 // 1番目の引数を整数としてpush
iadd    // スタックに積まれた2つの整数を加算、結果をpush
ireturn // スタックに積まれた数値を戻り値としてメソッドからreturn

add(10, 20) で呼び出された場合のスタックの移り変わりはこのようになります。

|    | iload_0 |    | iload_1 | 20 | iadd |    | ireturn
|    |-------->| 10 |-------->| 10 |----->| 30 |-------->
+----+         +----+         +----+      +----+

スタックマシン上での多値の表現

スタックマシンでは、多値はスタック上に積まれた(複数の)値でしかありません。 n個の値を積んで関数を呼び出すということは、n値を入力にする関数を呼び出すということですし、 m個の値を積んだ状態で関数からreturnするということは、m値を出力として関数を終えた、ということです*3

これはとてもきれいですよね。 例えばGo言語がスタックマシン上で実装されているとしたら、

func add(a int, b int) int {
    return a + b
}

func f(a int) (int, int) {
    return a, a * 2
}

add(f(3))

は、

push 3
call f      // 3が積まれた状態でfを呼び出す。実行が終わるとスタックに値が2つ積まれている。
call add    // 3と6がスタックに積まれた状態でaddを呼び出す。

と表現されていることでしょう。

継続と多値

継続について説明しだすと延々と横道にそれていってしまうので、 解説ページ へのリンクだけ置いておきます。 未完成部分が埋められることはもはやないと思われます。残念。

さて、継続と多値の関係ですが、継続とはつまるところ「関数からのreturnを、returnした後の処理を表す関数呼び出し」と考えてしまおう、ということです*4。 このとき、「継続に渡される引数が複数個ある」ということの意味を考えてみましょう。 「継続に渡される引数」は、「returnされた値」に対応しますので、これが複数個あるということは「複数の結果が関数から返ってきた」ことを意味します。 つまりは多値です。

すべてを継続で考えれば、returnはすべて関数の引数になります。 その世界においては、多値とは単に継続(もしくは関数)に渡す引数が複数あるというだけとなります。 これもとてもきれいですね。

ちょっと無理やりですが、Go言語であればこのようなイメージの世界です。

// スタックマシン上での多値の表現で使ったプログラムをreturnやGo言語の多値なしに表現してみた例
func add(a int, b int, k func(int)) {
    k(a + b) // returnの代わりに継続を呼び出す
}

func f(a int, k func(int, int)) {
    k(a, a * 2) // returnの代わりに継続を呼び出す(多値!)
}

func main() {
    f(3, func(a int, b int) { // fは多値を関数の引数として渡してくる
        add(a, b, func(x int) {
            fmt.Println(x)
        })
    })
}

returnもGo言語の多値も使っていませんが、やっていることはGo言語の多値を使ったコードと同じです。

ちなみに、継続を扱える言語であるSchemeでは、多値を作る関数をこう定義できます。

(define (values . xs)
  (call/cc (lambda (k) (apply k xs))))

call/ccvalues 呼び出し以降の処理を切り取って k とし、その継続に values の引数を入れるという、まさに「継続の引数が多値である」をそのまま表したコードになっています。 きれいだ・・・!

関数

さて、ここまでは多値と相性のよいものを見てきました。 ここからは、関数について少し考えてみます。

関数型プログラミング言語と関数

メジャーな関数型プログラミング言語では、関数は1入力1出力というモデルです。

多入力したい場合は「関数を返す関数」のように関数を値として扱えるようにしたことで解決しています(カリー化というやつ)。

// F#
// let add x y = x + yと同じ
let add = fun x -> fun y -> x + y

多出力したい場合はどうでしょうか。 これも、「関数を受け取る関数」により実現できます。 これはつまり、継続で見た方法です*5

// F#
let f = fun x -> fun k ->
  k x (x * 2) // (k x)で返ってきた関数に(x * 2)を適用

// シンタックスシュガーを使うと、
// f 3 (fun x y -> add x y)
// とか
// f 3 add
// とか書ける
f 3 (fun x -> fun y ->
  add x y // (add x)で返ってきた関数にyを適用
)

このように、関数型プログラミング言語では1入力1出力の関数だけですべてを表せる世界を作っているわけです*6。 これはこれできれいですね。

手続き型プログラミング言語と関数

Go言語を除いた多くの手続き型プログラミング言語では、関数は多入力1出力です。 なぜ入力は複数許すのに、出力は1つか許してないのでしょうか。 自分はC言語が1つの戻り値しか許さないようになっていたのをずっと引きずってきたのではないか、と考えています。

アセンブリレベルまで降りていけば、そもそもレジスタを使って複数の値を返すようなサブルーチンなんかは普通に書けるわけです。 x86であれば、divはeaxに商を、edxに余りを格納しますが、これも多値を返していると見なせます。

アセンブリレベルまで降りれば多値が使えるのに、今までのプログラミング言語ではそれを有効活用してこなかったことになります。 これは、手続き型プログラミング言語が計算機を効率よく使えるように進化してきたことを考えると、少し不幸な感じがします。 Go言語は、そういった世界をぶち壊すインパクトを持った言語だと思います*7

タプルと多値(と手続き型プログラミング言語)

多値はネストができません。他の値の要素となることもできません。 この制約によって多値は何を手に入れたのでしょうか。

それは、効率です。 多値と同じようなものとみられることもあるタプルですが、タプルはあくまで1つの値に複数の値をパックしたものです。 パックする処理(タプルの構築)も、アンパックする処理(タプルの分解)も、どれもタダというわけではありません。 言語処理系において、タプルの効率を上げようとする試みはいくつもありますが、タプルが値である以上、すべてのタプルを最適化できるわけではありません。

それに対し、多値は単なる複数の値であり、それ自体は値ではありません(スタックに積んであるだけ、レジスタに並んでいるだけ)。 そのため、パックやアンパックなどとは無縁の世界で生きていられます。

手続き型プログラミング言語でも関数がファーストクラスの値として使えるような言語が増えてきましたが、 手続き型プログラミング言語は本来、計算機を効率を程よく保ったまま抽象的に扱えるようにした言語であるべきではないでしょうか(ただし異論は認める)。 その場合、関数だのタプルだのをファーストクラスで扱えることにこだわらず、効率よく扱えるものを扱うにとどめるという割り切った言語があってもいいと思います。

ただ、ユーザー定義できる型とジェネリクスがあるとそれだけでタプルが作れてしまうので、多値がないがしろにされがち、というのはあるかもしれません。

多値とは

さて、多値とは何者でしょうか。

  • 「単なるスタックに積まれた値だよ」
  • 「単なる継続の引数だよ」
  • 「Go言語の多値が多値だよ」

色々と意見はあるでしょうが、ここからは「カンマで区切られた単なる複数の値だよ」という妄想の世界の話です。 ちなみに、上の3つだと一番下が一番近いです(が、別物です)。

多値かくあるべし!

架空の言語(WillGoとでもしておきましょう)を考えます。 この言語では、多値はカンマで区切られた単なる複数の値です。 どういうことか見てみましょう。 まずは、多値を返す関数です。

// 型と値の間にはコロンを置く(趣味)
// 多値を出力する関数は、出力する型をそれぞれカンマで区切って表現する
func f(a: int): int, int {
    return a, a * 2 // 多値を返している。
}

x, y := f(3) // x, yというのは多値を表している。

多値はカンマで区切られたものとして表現されていますね。

多値を受け取る関数も見てみましょう。

// a: int, b: int というのは、多値を受け取る関数であることを表している。
// 関数の出力で多値を表す場合と同じ表現であることが分かる。
func add(a: int, b: int): int {
    return a + b
}

result := add(1, 2) // 1, 2というのは多値を表している。

当然、多値を返す関数の結果をそのまま多値を渡す関数に渡せます。

result := add(f(3)) // 多値を渡す関数に多値を返す関数の結果をそのまま渡している。

ここまではいい感じですね。

多値かくあるべし・・・?

さて、多値は「カンマで区切られた単なる複数の値」でした。 ここから、妄想らしくなっていきます。

// 4引数版addを定義。
func add4(a: int, b: int, c: int, d: int): int {
    return a + b + c + d
}

result := add4(1, 2, 3, 4) // 1, 2, 3, 4は多値。

この add4 に対して、こんな呼び出しはどうでしょうか。

res1 := add4(1, 2, f(3))
res2 := add4(1, f(2), 3)
res3 := add4(f(1), f(2))

くどいようですが、多値は「カンマで区切られた単なる複数の値」でした。 であるならば、「そこに展開した結果がvalidであればvalidとする」としてもいいと思いませんか。 きれいだ・・・!

きれいな多値の分かりにくさ

さて、この架空の言語ですが、関数呼び出しを見ても引数の個数が分からないという問題があります。

res3 := add4(f(1), f(2)) // 2引数関数に見える

今どきのIDEなら、コード上に書かれていない文字列を表示するくらいやってのけるので、IDE前提であれば使えるかもしれません。

// 上のコードは、IDEで開くとこう見える(実際に書いてない部分はグレーアウト)。
res3 := add4(a, b=f(x=1), c,d=f(x=2))

もしくは、関数名さえ気を付ければそれほど問題にはならないかもしれません。

ちなみに、実在するGoという言語はこの問題に足を片方入れています。

// Go言語
res := f(g()) // さて、fは何引数関数でしょう?

そこまでやったのであれば、きれいな多値が欲しくなりませんか?

可変長引数と多値、もしくは可変長戻り値と多値

ここまでくると、行くところまで行ってみたい気がしますね。 引数を何個でも指定できる関数というものがあります。

func sum(xs: ...int): int {
    res := 0
    for _, x range xs {
        res += x
    }
    return res
}

result := sum(1, 2, 3)

では、戻り値を何個でも指定できる関数というのはどうでしょうか。

func f(b: bool): ...int {
    if b {
        return 1, 2
    } else {
        return 4, 5, 6
    }
}

これは、通常の手段では受け取れない関数となります。 この結果を使うためには、可変長引数の関数が必要です。

result := sum(f(true))

または、コンパイル時定数が渡された場合のみ受け取れるようにするのも面白そうです*8

a, b, c := sum(f(false)) // OK
d, e, f := sum(f(true)) // コンパイルエラー

スライスに変換する組み込み関数があれば(効率以外は)問題ありません。

xs := valuesToSlice(f(true))
ys := valuesToSlice(f(false))

これで、多値を「カンマで区切られた単なる複数の値」としてみなしても成り立ちそうだということがなんとなくわかっていただけたかと思います(便利だとは言っていない)。

このように、多値は多値で面白い世界が広がっているのです。 Go言語の多値は始まりでしかありません。 みなさんも自分だけの多値の世界を考えて、どんどん多値のすばらしさを世界に発信していきましょう!

参考ページ

*1:メジャーな言語だとScheme/Common LispとGoくらいではないでしょうか。何をメジャーに入れるかという問題はありますが。※Luaも多値を持っているようです。Twitterで教えてもらいました。※GHC拡張にもUnboxed Tuplesという構文拡張があるようです。これもTwitterで教えてもらいました。

*2:クラスのフィールドとして持たせられる。

*3:ただし、上で例に挙げたJava仮想マシン(や、他の仮想マシン)では、m個の値を積んだ状態で関数からreturnすることを許していません。

*4:http://www.kmonos.net/wlog/95.html#_1109090307 という記事を思い出したので置いておきます。この記事では、returnを関数と見なすとどうなるだろう、という思考実験をしています。

*5:多入力と多出力で戻り値の位置に関数がくるか、引数の位置に関数がくるかが入れ替わるのも面白いですね。双対性というやつでしょうか。

*6:念のため: 実際にこんなコードは書きません。

*7:しかし、前のエントリでも書いたように、Go言語は多値っぽいけど多値じゃないものを入れてしまったのでそこはすごく残念。

*8:ただし、コンパイル時間は無視するものとする。

Go言語のイケてない部分

最近色々あって仕事でGo言語を使っています。 色々割り切っている言語なので、こんなこと言ってもしゃーないんですが、言語設計はミスってるんじゃなかなぁ、と思わざるを得ない点が多々あります。 使い始めて1か月くらいなので間違ったことを書いているかもしれませんので、何かあれば指摘していただけるとありがたいです。

本文ではネガばかり羅列していますが、ランタイムとツール周りは気に入っています。 Goのランタイムを使う、もっと洗練されたAlt Go的なものがあるといいのに(もしくはジェネリクスのったGo2を早くリリースしてほしい)、と思う日々です。

追記: なんか意図とは違った受け取られ方をしている方もいるので追記します。 この記事はあくまで、「Go言語を学ぶにあたって躓いた点」を列挙し、まとめ、理由を考えてみる(教えてもらう)ために書いたものです。 Go言語自体はDisってますが、Go言語ユーザーをDisる目的では書いていません。

また、以下のような意見も見られました。

  • Python とか Ruby とかのライトな言語ユーザらしい「典型的で、ありがちな批判」。タプルにこだわりすぎ
  • 慣れれば困らない
  • 他の言語を使えばよい
  • Issueにすればよい

まずひとつめについてですが、自分はPythonRubyのようないわゆるLL使いではありません。 典型的でありがちな批判かどうかは自分では判断できませんが、観測範囲でこのような批判がまとまっているものを見た覚えはないです。 そのため、この記事を書くためにいろいろと調べましたし。 それと、多値にこだわっているのではなく、言語仕様が初学者が躓きやすい(し、理由を調べにくい)ようになっているのでは?という指摘こそが言いたいことです。

ふたつめの慣れれば問題ないという指摘も、慣れるまでの障壁の話を書いているのでこの記事に対しては意味を持ちません。 人にもよりますが、ルールの推測しずらい(シンプルでない)ものを覚えるのは苦手なので、自分と同じような人間が躓かないように気にしていただければと思います。

みっつめですが、避けられない理由が「いろいろ」あるのです。察してください。

よっつめのIssueにすればよい、という意見ですが、このエントリはあくまで「ここが分かりにくい」というところを(理由があればそれも込みで)まとめたものであって、 言語仕様を自分の思い通りに変えたいという話ではありません。 Issueにすればどうなるというのでしょうか。 互換性を壊すということで却下されてそれで終わりだという確信があります。 それよりは、エントリにまとめて周知した方が生産的だと思いますし、IssueでやりあうほどのGo愛を自分は持ち合わせておりません。

多値まわり

Go言語には多値という機能*1が言語に組み込まれています。 しかし、これが中途半端なうえ、多値っぽい構文で多値ではないものがいくつかあるため、初心者を混乱させる原因になっています。

まず、多値はこのように使います。

// 多値を返す関数minmax
func minmax(x int, y int) (int, int) {
    if x < y {
        return x, y     // 条件演算子がないのも割り切りだとわかっていてもつらい。
    }
    return y, x
}

// 多値の受け取り
min, max := minmax(20, 10)
fmt.Println("min:", min, ", max:", max) // => min: 10, max: 20

これを念頭に読んでください。

追記: 多値に関して、別記事としてまとめました。

bleis-tift.hatenablog.com

こちらを読んでいただければ、多値はダメだからタプルを入れるべきだった、という話をしていないことが分かっていただけるかと思います。

多値をひと塊で扱える例外: 多値を多値として返す

Go言語では多値は基本的にひと塊のオブジェクトとして扱えません(ので、他の言語のにあるようなタプルとは違います)。

tuple := minmax(20, 10) // コンパイルエラー

しかし、例外がいくつかあります。 ひとつめが、他の関数の戻り値をそのまま自分の関数の戻り値として返す場合です。

func minmax2(x int, y int) (int, int) {
    return minmax(x, y) // そのまま返す
}

この場合、結果が同数*2かつすべて同じ型である必要があります。

多値をひと塊で扱える例外: 同じ形の多値を取る関数にそのまま渡す

ふたつめが、同じ形の多値をとる関数にそのまま渡す場合です。

fmt.Println(minmax(20, 10)) // => 10 20

fmt.Printlninterface{} という何でも渡せる型を可変長引数として複数受け取れる関数なので、 minmax 関数の結果をそのまま渡せています。 しかし、可変長だからと言ってこのようなことはできません。

fmt.Println("min, max:", minmax(20, 10))    // コンパイルエラー

できてもよさそうなものですが、なぜかできません。 出来ないようにしている理由はわかりません。

多値っぽい構文なのに多値ではない機能: for range構文

主にコレクションを走査するときに使う for range構文というものがあります。 例えば、Go言語にはジェネリクスがないのでいわゆるmap処理を行いたい場合、

ys := make([]int, len(xs))
for i, x := range xs {
    ys[i] = x * 2
}

のように書きます。

i, x の部分は多値のように見えますが、これは多値ではなく構文です。 多値では値を受け取らないということはできませんが、この構文は x の側(この記事では2nd valueと呼びます)を無視できます。

min := minmax(20, 10)   // コンパイルエラー
ys := make([]int, len(xs))
for i := range xs { // OK. xsの要素ではなく、インデックスが取れる
    ys[i] = i
}

要素の方ではなくインデックスの方が取れるのが使いにくい感じがしますが、これはmapとの統一をしたかったためと思われます。 mapでは1st valueがキー、2nd valueが値となるので、mapでもスライスでも1st value側を取れるようにした、ということでしょう。 mapは値を走査するよりもキーを走査する方が多いでしょうから。

多値ではないものはまだあります。

多値っぽい構文なのに多値ではない機能: mapへのアクセス

Go言語では、mapへのアクセスにはスライスや文字列などと同様、 [] を使います。 その結果として、値のほかにキーが存在したかどうかを表す bool 値が受け取れます。

m := map[string]int { "a": 10, "b": 20 }
n, ok := m["c"] // 2nd valueとしてbool値が受け取れる
if !ok {
    n = 0
}
fmt.Println("n:", n)    // => n: 0

これも n, ok の部分は多値に見えますが、多値ではありません。 まず、 ok の部分が省略できますし、多値ではできる「他の関数にそのまま渡す」ができません。

func f(n int, ok bool) {
}

f(m["c"])   // コンパイルエラー

これは ok が省略できることと両立できないからでしょう。 上のようなコードが許された場合、下のようなコードでどういう挙動にすればいいのかという微妙な問題が出てきます。

// 1st valueだけを表示すべきなのか、2nd valueも表示すべきなのか
fmt.Println(m["c"])

多値っぽく見せるなら、省略なぞ許さずに多値にしてしまったほうがよかったと思います。 あり得ない話だとは思いますが、もしGoが演算子オーバーロードを許すようになったとしても、 [] の結果を多値にしては組み込みのmapと同じになりません。 ではどうするのか。省略可能を示す ? みたいな機能を増やすんでしょうかね。

多値っぽい構文なのに多値ではない機能: 型アサーション

アサーション(キャストのようなもの)も、mapへのアクセス同様に2nd valueとして成否を表す bool 値を返します。

func f(x interface{}) int {
    n, ok := x.(int)    // 多値ではない
    if !ok {
        n = -1
    }
    return n
}

mapと同じことが言えますね。

多値っぽい構文なのに多値ではない機能: チャネルからの受信

同上なので略。

多値が使えると便利そうなのに使えないし、別の意味になる: switch構文

Go言語でのswitch構文には多値が使えません。

// コンパイルエラー
switch minmax(20, 10) {
case 10, 20:
}

ですが、 case 10, 20 の部分は多値ではない意味として使われています。

switch 20 {
case 10, 20:
    fmt.Println("10 or 20")
default:
    fmt.Println("other")
}

Go言語では、 case はフォールスルーしませんので、複数の選択肢で同じ処理をさせたい場合は上のようにカンマを使います。 switch で多値が使えたら、 ok とそうでない場合とか、 errnil かそうでないかなどで分岐処理が書けたのに、残念な文法の選択をしたと思います。

多値が使えると便利そうなのに使えない: チャネル

Go言語における同期処理の入力、出力と言えば、関数の引数とその結果*3です。 関数の引数は多値を許しますし、関数の結果も多値を許します。対称性が取れていますね。

Go言語における非同期処理の入力、出力と言えば、チャネルへの送信と受信ではないでしょうか。 しかし、チャネルへの送信にも受信にも、多値は使えません。対称性は取れていますね。でも、同期処理と非同期処理で統一性はないように思います。

なぜチャネルで多値が使えないかの理由は思い浮かびません。 実装が難しいとかなんでしょうか。CSPよりもアクター派なんで詳しくはわかりません。

コレクション

ジェネリクスがないので、基本的には言語組み込みのものしか使いません。 また、ジェネリクスがないので、いわゆるmap関数だとかは用意できないので基本的にはfor文を書くことになります。 他の言語では1行で書けることが、Go言語では3行~6行程度必要になることは多いです。 コンパイル速度のためとはいえ、今どきの言語としてはイケていない部分でしょう。

mapには2nd valueがあるのに配列, スライス, 文字列には2nd valueがない

多値の項でも言及した通り、mapへのインデックスアクセスは2nd valueを持ちます。 しかし、同じく言語組み込みのコレクションである配列やスライス、文字列には2nd valueがありません。

そのため、範囲外のインデックスアクセスが発生するとこれらはpanicを起こします。 効率のためかもしれませんが、そうであるならmapに対しても2nd valueを(多値と同じような構文で)用意するべきではなかったと思います。 それよりは、mapに対して組み込み関数で多値を返すようなものを用意してほしかったです(それか、配列やスライスなどにも2nd valueを用意する)。

:=

:=var + = の略記法、だけではないんです。

シャドーイングと再代入

= は再代入*4:=シャドーイング、という説明を見たような気がします。 が、これだけでは := の性質をすべて語っていません。

まず、Go言語では同一スコープでのシャドーイングはできません*5

x := 10
x := 20 // コンパイルエラー

ですが、みなさんこんなコード書いてませんか?

x, err := f()
if err != nil {
    return nil, err
}
y, err := g(x)
// ...

これ、同一スコープに err という同じ名前の変数があるので、シャドーイングできているようにも見えます。 しかし、実はこれは再代入なのです。

func f() (int, error) {
    return 0, nil
}

func g(x int) (string, string) {
    return "", ""
}

としたうえでコンパイルすると、 stringerror を実装していない、というコンパイルエラーになります。

また、 := では新たな識別子を導入しないとコンパイルエラーになるため、

x, err := f()
x, err := g()

のようなことはできません。 これだと2行目では新たな識別子が導入されておらず、「short variable declaration(短い変数宣言)」にならないからです。

でも、短い変数宣言という名前なのに多値に対しては再代入が起こり得るというのはどうなんでしょうか。 そうするくらいなら、同一スコープでのシャドーイングを許してしまった方がよかったと思います。

このせいで error しか返さないような関数が混ざると残念なことになります。

x, err := f()
err := g()  // コンパイルエラー
err = g()   // こうするか、
err2 := g() // こうする。上かな。

もし同一スコープでのシャドーイングを許していたらこう書けました。

x, err := f()
err := g()

err:= で受ける。統一されていると思いませんか。

追記:

error のみを返す関数は、if文のSimpleStmtで受け取る書き方を常時行えば問題ないとのこと。 処理がif文の中に紛れ込むのを完全には賛成できませんが、これは好みの問題でしょう。 同一スコープでのシャドーイングが欲しかったという意見は変わりませんが、今後はこの書き方で回避したいと思います。

別の意味に同じ記号

Go言語において、 := は実は2つの意味を持ちます。

  • short variable declaration
  • for range構文でのRangeClause

これらは、意味としてはとても似通っているのですが、別物です。

前者は3値や4値も当然受け取れますが、後者はインデックスと値の2値のみです*6。 前者は右項の値すべてを受ける必要がありますが、後者は2nd valueが必要ない場合は省略できます。

個人的には、for range構文に := は不要だったのではないかな、と思っています。

// コンパイルエラーだけどこれでよかったのでは?
for i, x range xs {
}

こうなっていない理由として考えられるのは、実はfor range構文では := のほかに = も使えるからというのがあるのでしょう。 = の方を使うと、ループの最後の値がループの外から参照できる、という利点があります。

func f(xs []string) {
    var i int
    var x string
    for i, x = range xs {   // ちなみに、ここにはvarはそもそも置けない(ので、:=はvar+=の略記法だけではない)
        fmt.Println(i, x)
    }
    fmt.Println("last index:", i, "last value:", x)
}

しかし、これは少々技巧的で、条件演算子すら省くGo言語の思想とは相容れないように思えます。 なので、for range構文ではシンプルに := の機能だけに絞って := 自体は省略してしまった方がいろいろと分かりやすくなったのでは、と思います。

ちなみに、紛らわしいことに、C風のfor構文で使える := はshort variable declarationです。

// short variable declaration
for i := 0; i < n; i++ {
}

defer

スコープではなく、関数に属する

そのままです。罠ですよね。 一応、無名関数をその場で呼び出すことで回避できますが、スコープに属するようにしてくれればよかったのに、と思います。 そうなっていない理由は効率なのでしょうか。わかりません。

追記:

Twitterで納得度の高い理由を教えてもらいました。 なるほど、これは確かにブロックスコープだと困りますね。 ループの中で defer して死というのはまだ分かりやすいですし、この点に関してGo言語の選択は正解かもしれません。

パッケージ

階層構造を取れない

これもそのままです。 複数の粒度でのグルーピングは不要ということでしょうか。 地味に困ります。

struct / interface

構文上の違いがないのに区別が必要

型の表現方法(struct/interface)によってポインタを渡すべきかどうか変える必要が出てくる(効率を考えた場合の話)のに、それが構文上区別できないのはつらいです。 C#のように命名規約で回避するくらはしてくれてもよかったように思います。 それか、C言語のように struct を明示するだとかでもこの際よかったかな、と思います。

echo

JSONメソッド

Go言語ではなく、echoというフレームワークに対する愚痴です。 echo(この名前もググラビリティ低い)ではレスポンスを組み立てるために Context オブジェクトのメソッドを呼び出します。 そして、アクセスされた際に呼び出されるハンドラーは error を返します。 だいたいこんな感じになるわけです。

e.GET("/path", func (c Context) error {
    return c.JSON(http.StatusOK, f())
})

これ見てどう思いますか。 c.JSON を呼び出すことでレスポンスオブジェクトが作られ、それが error インターフェイスを実装している、そう感じませんか。 どうやらechoの作者はそうではなかったようで、このメソッドで レスポンスに対してJSONの書き込みが走 るように作られています。 そして、書き込みに失敗したら error を返すのです。

func f(c Context) ([]SomeResult, error) {
    // なんやかんや処理
    if reason != nil {
        return c.JSON(http.StatusInternalServerError, reason)
    }
    return result
}

とかやって、

e.GET("/path", func (c Context) error {
    res, err := f(c)
    if err != nil {
        return err
    }
    return c.JSON(http.StatusOK, res)
})

とやったらどうなりますか。 そうです。 reasonnil ではなかった場合、reason がレスポンスに書き込まれますが、レスポンスへの書き込み自体が失敗しなければ c.JSONnil が返ってくるので、 ハンドラーの中の if には入らず、再度 c.JSON が呼び出され、ステータスOKでエラーレスポンス(reasonの内容)が返されます。 さらに、エラーレスポンスの後ろに [] というゴミが付いて しまいます。 なぜなら c.JSON はレスポンスに書き込むだけだから。 ハンドラーの最後の returnres を書き込んでいますから。 多くの場合エラーがあれば res は空ですから。 当然、レスポンスには [] が付いてきますよね。

・・・。 ドキュメントを読まなかった自分も悪いんですが、こういう関数に JSON なんて宣言的に見える名前を付けてほしくなかった。 WriteJson とか、操作的に見える名前ならこんな間違いはしなかった。

vim

テキストオブジェクトとの相性の悪さ

GoLandを使っているのですが、当然(?)Vim Pluginを使っています。 ですが、Goの構文は括弧を省略しているため、「if文の条件部分に対して操作」・・・あっ・・・できない! となることが多いです。 Vimmerに優しくない*7

まとめ

細かいところではまだまだあるのですが、好みの部分も多い*8のでこのくらいにしておきます。 後半力尽きて適当アンド愚痴ですが、こんな感じで今のところGo言語イケてない。ダサい。という認識です。 この言語のどこがシンプルなんじゃ!むずかしいやろ!どちらかというとイージー方向の機能満載やろ!!!という気分です。 「いいやそこは見方が悪いんだ、こういう見方をするとイケてるんだぜ!」という意見があれば是非聞きたいです。 よろしくお願いします。

*1:他の言語でのタプルのようなもの。ただし、タプルのようにひと塊として扱えるものではなく、単に関数から戻るときに複数の値がスタックに残っているような状態と思った方がいいです。

*2:多値は2値だけでなく、3値でも4値でも返せます。

*3:ちなみに、戻り値型と呼ばないのは多値は(Goでは)型ではないからです。

*4:varでの=は除く

*5:例えばF#は同一スコープでのシャドーイングができているように見えるのですが、実はletがスコープを作っているので同一スコープでのシャドーイングを実際にしているわけではありません。見た目的には同一スコープのシャドーイングに見えるので置いておきましょう。

*6:チャネルは2nd valueを取りませんが、ここでは省きます。

*7:そもそもIntellij/GoLandのvim pluginって文字列リテラルの中でテキストオブジェクト使えないという致命的な欠点があってつらいんですが、それはまた別の話。

*8:型指定の書き方とか。

FParsecでJSONパーサーを書いてみる話

F# Advent Calendar 2017の4日目の記事です。 NGK2017B昼の部でパーサーコンビネーターについてLTしてきたので、その内容について書きます。 ただし、内容は大幅に加筆修正しています。

導入

世の中にはパースすべきものであふれています。 例えば、下記のようなものがあります。

構造を持ったものはそこら中にあります。 これらを処理するためにどうすればいいでしょうか。

一つの方法として、正規表現を使うというものがあります。 しかし、(本来の)正規表現ではネストする文法などは扱えません。 拡張機能として、ネストする文法が扱えるようになっているような処理系もあります。 しかし、そもそもそんな複雑な正規表現には近寄りたくないですよね。

では、文字列操作関数を駆使してどうにかする方法はどうでしょうか。 ごくシンプルなものならそれでもいいですが、すぐに限界が訪れます。 なんの指針もなしに書いてしまうと、機能拡張も保守も困難なひどいコードが出来上がります。

こういうものは、パーサーを使って処理するのがいいでしょう。

パーサーとは?

パーサーとは、一次元的な構造、例えば文字列などから構文木を作るものと言えます。 例えば、ログの中身から LogEntry のリスト構造にしたり、設定ファイルの中身から Config オブジェクトにしたり、ソースコードをASTに変換したりするものです。

では、パーサーはどのようにして作ればいいのでしょうか。 それには、おおざっぱに3つの方法があります。

  1. 手書き
  2. パーサージェネレーター
  3. パーサーコンビネータ

手書きによる方法

手書きによる方法では通常、LL法と呼ばれる手法により、再帰関数としてパーサーを書きます。 どのくらいの複雑さを持った文法を相手にしているのかが自明ではなくなるので、この方法に最初から手を出すのはおすすめしません。

パーサージェネレーターによる方法

文法規則のためのDSLを、パーサージェネレーターというツールを使い、その文法規則を解析するためのコードを生成する方法です。 文法規則を修正した際に、コードの再生成が必要になるため、手書きや後述のパーサーコンビネーターほど手軽ではありません。

パーサーコンビネーターによる方法

基本的なパーサーとパーサーを組み合わせるための関数から構成される、パーサーを作るためのライブラリです。 単なるライブラリなので、コードの生成などの追加のビルドプロセスを必要としません。 しかし、手書きやパーサージェネレーターに比べると処理速度の面で劣ることがあるため、頻繁に実行する必要がある場面では計測をするといいでしょう。

3つの方法をざっくりと紹介しましたが、まずは手軽なパーサーコンビネーターから始めてみるのがおすすめです*1

パーサーコンビネーターの特徴

パーサーコンビネーターは次のような特徴を持ちます。

  • パーサーが部品として再利用可能
  • 各パーサー(部品)単位でテスト可能
  • 表現力が高い
    • パーサーを実行時に組み立てたりもできる

なにから始めればいいか

パーサーコンビネーターを使うと決めたとして、最初に取り組む題材にはどのようなものを選べばいいでしょうか。 ここでは、下記の3つの題材について考えてみます。

どの題材についても言えることですが、「すでにあるライブラリを使えばいい」という考えではいつまでたっても自分でパーサーが書けるようになりません。 パーサーが自分で書けるようになると、プログラマーとして対応できる範囲が広がり、文字列解析に対する判断力も上がります。 たとえすでにライブラリがあったとしても、練習としてそれらを自前で実装しなおすことには大きな意味があるのです。

数式

伝統的なものとして、簡単な数式があります。 四則演算からはじめて、かっこの追加や変数の追加など、発展も考えやすい題材です。 しかし、出来上がるものが地味なので、ありがたみや達成感が薄いのがつらいところです。

YAML

YAMLは設定ファイルなどで見かける形式です。 yaml.orgに仕様があります。 YAMLがパース出来るようになると、設定ファイルをオブジェクトに変換するコードが書けるようになるので、数式よりも達成感は大きいでしょう。 しかし、YAML1.0でもかなり巨大な仕様なので、最初の題材としてはあまりおすすめできません。

JSON

JSONは、設定ファイルのほかにもWebAPIのリクエストボディやレスポンスボディなど、様々な場所で使われています。 json.orgに仕様があります。 YAMLよりもはるかにコンパクトな仕様であり、さらに文法もパースしやすいように考えられたものになっています*2。 そのため、最初の題材としてはJSONがおすすめです。

もし、JSONで拍子抜けしてしまうようであれば、HOCONの機能をつけ足してみるとか、TOMLなど別の形式のパーサーを書いてみるといいでしょう。

パーサーを書く大まかな流れ

パーサーを書く流れとして、次の3つの手順を繰り返すのがいいでしょう。

  1. 解析したデータを格納するためのデータ構造を用意する
  2. パーサーを組み合わせて、パース結果を用意したデータ構造に変換する
  3. 作ったパーサーをテストし、通ったら1や2に戻る

JSONでの例

まずは、 [1,2,3] というJSONをパースできるところを目指します。 このJSONを表すのに必要最小限のデータ構造を考えます。

type Json =
  | JNumber of float    // F#のfloatは64bit
  | JArray of Json list // F#では配列よりもlistの方が扱いやすい

[1,2,3] という文字列を、 JArray [JNumber 1.0; JNumber 2.0; JNumber 3.0] に変換できたらとりあえずの目標達成ということになります。

いきなり JNumberJArray の2つに対応するのは難しいので、 JNumber を解析するパーサーだけを作ってみます。 このエントリでは、FParsecというF#用のパーサーコンビネーターライブラリを使います。

FParsecには pfloat という、浮動小数点数形式の文字列("1.5" とか)をパースするパーサーが用意されています*3。 このパーサーを使って浮動小数点数形式の文字列を解析すると、 float 型の結果が得られます。

let parseBy p str =
  // run関数はFParsecが用意している、パーサーを実行するための関数
  match run p str with
  | Success (res, _, _) -> res
  | Failure (msg, _, _) -> failwithf "parse error: %s" msg

"1.5" |> parseBy pfloat // => 1.5

欲しいのは、 float ではなく JNumber なので、結果を変換する必要があります。 そのための方法はいくつかありますが、最も手軽な方法として |>> 演算子を使ってみます。

let jnumber = pfloat |>> (fun x -> JNumber x)

|>> は左項のパーサーの結果を右項の関数によって変換する演算子です*4|>> 演算子の戻り値の型もパーサーになるため、ここで作った jnumber も先程用意した parseBy 関数に渡せます。

"1.5" |> parseBy jnumber // => JNumber 1.5

これでJSONの数値がパース出来るようになったので、次にJSONの配列に進みます。

let jarray =
  sepBy jnumber (pchar ',')
  |> between (pchar '[') (pchar ']')
  |>> (fun xs -> JArray xs)

新しいパーサーが3つ出てきました。 一番使われている pchar 関数は、指定された文字をパースするパーサーを返します。 sepBy 関数は、第一引数で指定されたパーサーが、第二引数で指定されたパーサーで区切られて連続するような文字列をパースするパーサーを返します。

"1,2,3"
|> parseBy (sepBy jnumber (pchar ',')) // => [JNumber 1.0; JNumber 2.0; JNumber 3.0]

between 関数は、第一引数で指定されたパーサーと第二引数で指定されたパーサーの間に第三引数で指定されたパーサーが来るような文字列をパースするパーサーを返します。 コードでは第三引数はパイプライン演算子で渡しています。

jarray 全体を試してみましょう。

"[1,2,3]"
|> parseBy jarray // => JArray [JNumber 1.0; JNumber 2.0; JNumber 3.0]

目標だった、 [1,2,3] のパースができるようになりました。 このようにして小さいパーサーを組み立てて確認しながら目標に向かっていきやすいのが、パーサーコンビネーターの素晴らしい点です。

はまりがちポイント

パーサーコンビネーターでパーサーを書く際に、入門者がはまりそうなポイントを見ていきましょう。

空白の無視

パーサーの前段には、レキサー(字句解析器)を置くことがあります。 レキサーは「文字列→トークン列」への変換を行い、パーサーは文字列を直接扱うのではなく、トークン列を扱うようにするのです。 レキサーで空白やコメントを読み飛ばすようにしておけば、それらを意識せずにパーサーが書けます。

しかし、パーサーコンビネーターによってはトークン列が扱えないものがあります。 今回使っているFParsecもそのうちの一つなので、本来いレキサーがやるような仕事もパーサーでやらなければなりません。

例えば、先程の jarray パーサーですが、空白を挟むとうまく動きません。

"[ 1, 2, 3 ]"
|> parseBy jarray // => エラー

空白のスキップを下手に書くと、繰り返しや再帰と組み合わさった際に簡単に無限ループに陥ってしまいます。 そこで、空白スキップの戦略を決めておくといいでしょう。 例えば、各パーサーの「後ろの空白」を読み飛ばすようにし、最後に全体のパーサーの「前の空白」を読み飛ばすようにすれば、空白のスキップが実現できます。

let ws = spaces
let jnumber = pfloat .>> ws |>> JNumber
let jarray =
  sepBy jnumber (pchar ',' >>. ws)
  |> between (pchar '[' >>. ws) (pchar ']' >>. ws)
  |>> JArray

let parseBy p str =
  match run (ws >>. p) str with
  | Success (res, _, _) -> res
  | Failure (msg, _, _) -> failwithf "parse error: %s" msg

"[ 1, 2, 3 ]"
|> parseBy jarray // => JArray [JNumber 1.0; JNumber 2.0; JNumber 3.0]

spaces は、0文字以上の空白文字をパースするパーサーです。 これまで見てきた pfloatpchar と違い、パースした文字列を結果として返さない(unit を返す)点に注意してください。 spaces をそのまま使ってもいいのですが、長いので ws という別名(whitespaceの略)を与えています。 また、もしコメント機能を追加したいような場合でも、 ws の定義を変更すれば対応できます。

このパーサーのバリエーションとして、 spaces1 というものもあり、こちらは1文字以上の空白文字をパースします。 このように、サフィックスとして1が付くようなパーサーがほかにもあります。 例えば、 jarray の実装に使っている sepBy のバリエーションである sepBy1 などです。 こちらも、 sepBy は0回以上の繰り返しを表すのに対し、 sepBy1 は1回以上の繰り返しを表します。

.>>>>. は、パーサーを連続して適用する演算子です。 ピリオドが付いている方を結果として使い、付いていない方はパースはしますが結果を捨てることを意味しています。 また、どちらの結果も保持する .>>. という演算子もあり、この場合結果はタプルになります。

let hi =
  pchar 'h' .>>. pchar 'i'
  |>> (fun (h, i) -> string h + string i) // 結果はタプルとして渡される
  
let hi2 =
  pchar 'h' .>> pchar 'i' // pchar 'i' の結果は捨てる
  |>> (fun h -> string h) // 捨てたので結果に含まれない

let hi3 =
  pchar 'h' >>. pchar 'i' // pchar 'h' の結果は捨てる
  |>> (fun i -> string i) // 捨てたので結果に含まれない
  
"hi" |> parseBy hi  // => "hi"
"hi" |> parseBy hi2 // => "h"
"hi" |> parseBy hi3 // => "i"

// 捨てるとは言っても、パースしないわけではないので、
// 後続のパーサーが失敗すると全体として失敗する
"ho" |> parseBy hi2 // => エラー

jarray の新しい定義をもう一度見てみます。

let jarray =
  sepBy jnumber (pchar ',' >>. ws)
  |> between (pchar '[' >>. ws) (pchar ']' >>. ws)
  |>> JArray

sepBybetween.>> ではなく >>. を使っていますが、解析結果には含まれないため、どちらを使っても構いません。 しかし、 .>> よりも >>. の方が効率がいい場合があるため、どちらでもいい場合は >>. を使うようにするといいでしょう。

ちなみに、 p |> between popen pclose (popenとpcloseに挟まれたpをパースするパーサー)は popen >>. p .>> pclose (popenを解析して結果を捨て、pを解析し、pcloseを解析して結果を捨てるパーサー)と同じ意味になります。

let between popen pclose p = popen >>. p .>> pclose

実際には、 >>..>> がインライン展開されたような定義になっているため、速度を気にする場面では between を使うといいでしょう*5

完全一致

これまで作ってきたパーサーですが、実はパース対象の文字列の後ろに余分なものがあってもパースが成功してしまいます(前方一致)。

"[1, 2, 3]]]]"
|> parseBy jarray // => JArray [JNumber 1.0; JNumber 2.0; JNumber 3.0]

これでは困ることが多いので、 eof というパーサーを最後に合成するのが普通です。

let parseBy p str =
  // わかりやすさのため、between ws eof p ではなく >>. と .>> を使ったが、
  // 一番上のレベルのパーサーなので速度上の問題にもならないはず
  match run (ws >>. p .>> eof) str with
  | Success (res, _, _) -> res
  | Failure (msg, _, _) -> failwithf "parse error: %s" msg

これで、完全一致しない場合はエラーになるようになりました。

文字列のエスケープ

JSONの文字列にはエスケープがあります。 エスケープを考えなくていい場合、文字列のパーサーは次のようにすればいいでしょう。

type Json =
  | JNumber of float
  | JString of string
  | JArray of Json list

let jstring =
  manyChars (noneOf ['"'])
  |> between (pchar '"') (pchar '"')
  .>> ws
  |>> JString

noneOf 関数は、第一引数で指定された seq<char> に含まれる char 以外の文字にマッチするパーサーを返します。

// string は seq<char> でもあるので、 ['x'; 'y'; 'z'] の代わりに "xyz" と書いてもOK
"a" |> parseBy (noneOf "xyz") // => 'a'
"y" |> parseBy (noneOf "xyz") // => エラー

manyChars 関数は、 char を返すパーサーを受け取り、その0回以上の繰り返しをパースして、文字列に連結するパーサーを返します*6

"abc" |> parseBy (manyChars (noneOf "xyz")) // => "abc"
"axc" |> parseBy (manyChars (noneOf "xyz")) // => エラー

エスケープ非対応版の文字列パーサーを再掲します。

let jstring =
  manyChars (noneOf ['"'])           // 「"」以外の文字の繰り返しが
  |> between (pchar '"') (pchar '"') // 「"」に挟まれているのが文字列
  .>> ws
  |>> JString

これをエスケープに対応させるには、エスケープシーケンスとそうでないものを分割して考えます。

まず、エスケープされていない、普通の文字とは何かを考えてみます。 これは簡単で、「エスケープの開始文字()と、文字列の終了文字(")以外の文字」です。

let nonEscapedChar = noneOf ['\\'; '"']

次に、エスケープされた文字を考えてみます(\uxxxx形式は省略します)。 エスケープされた文字は、開始文字()から始まり、エスケープシーケンスの種類を表す文字が続きます。

let escapedChar = pchar '\\' >>. anyOf @"\""/bfnrt"

anyOf 関数は noneOf の逆で、引数で指定された seq<char> のうちの1文字をパースするパーサーを返します。

"a" |> parseBy (anyOf "abc") // => 'a'
"c" |> parseBy (anyOf "abc") // => 'c'
"z" |> parseBy (anyOf "abc") // => エラー

これで、エスケープされた文字もパース出来るようになりました。

@"\\"  |> parseBy escapedChar // => '\\'
@"\""" |> parseBy escapedChar // => '"'
@"\n"  |> parseBy escapedChar // => 'n'

しかし、これだけだと \n は改行文字ではなく n という文字になってしまうため、結果を変換する必要があります。 変換しなければならないのは、 b, f, n, r, t の5つです。 \, ", / は変換せず、そのまま使います。

let convEsc = function
| 'b' -> '\b'
| 'f' -> '\f'
| 'n' -> '\n'
| 'r' -> '\r'
| 't' -> '\t'
| c -> c      // '\\', '"', '/' はそのまま使う

let escapedChar = pchar '\\' >>. anyOf @"\""/bfnrt" |>> convEsc

これで、エスケープされていない文字のパーサーとエスケープされた文字のパーサーが手に入りました。 文字列は、その中の1文字1文字がどちらかでパース出来るものの並びになります。 <|> という演算子は、この「どちらか」を表すパーサーを作る演算子です。

"a" |> parseBy (pchar 'a' <|> pchar 'b') // => 'a'
"b" |> parseBy (pchar 'a' <|> pchar 'b') // => 'b'

それさえわかれば、あとは簡単です。

let jstring =
  manyChars (nonEscapedChar <|> escapedChar) // どちらかの繰り返し
  |> between (pchar '"') (pchar '"')
  .>> ws
  |>> JString

"\"abc\""       |> parseBy jstring // => JString "abc"
"\"abc\\ndef\"" |> parseBy jstring // => JString "abc\ndef"

エスケープ非対応版を再掲しておきます。 manyChars に渡すパーサーだけ変えたことが分かります。

let jstring =
  manyChars (noneOf ['"'])
  |> between (pchar '"') (pchar '"')
  .>> ws
  |>> JString

選択されない選択肢

文字列パーサーの実装で紹介した <|> 演算子ですが、気を付けなければならないことがあります。

JSONには浮動小数点数しかありませんが、F#には整数があるので、整数と浮動小数点数を区別するようにしてみましょう。

type Json =
  //| JNumber of float
  | JInteger of int
  | JFloat of float
  | JString of string
  | JArray of Json list

let ws = spaces

// jnumberの定義を変更
let minusSign = opt (pchar '-') |>> Option.isSome
let digit1to9 = anyOf ['1'..'9']
let integer = (many1Chars2 digit1to9 digit <|> pstring "0") |>> int
let jinteger =
  minusSign .>>. integer
  |>> (fun (hasMinus, x) -> JInteger (if hasMinus then -x else x))
let jfloat =
  tuple3 minusSign integer (pchar '.' >>. integer)
  |>> (fun (hasMinus, i, flac) ->
         let f = float i + float ("0." + string flac)
         JFloat (if hasMinus then -f else f))
let jnumber = (jinteger <|> jfloat) .>> ws

pfloat よりもかなり複雑になりましたが、ほとんどjson.orgの定義を書き下しているだけです(指数表記は未対応です)。

opt 関数は、引数で指定されたパーサーが成功した場合 Some でくるみ、失敗した場合 None を返すパーサーを作ります。 引数で指定されたパーサーが失敗した場合でも、 opt 自体は成功するので、省略可能な構文要素を表すために使います。 JSONの数値の場合、負の符号は省略可能なので、 opt で実現しています。 digit0 から 9 までの文字をパースするパーサーです。

"-2" |> parseBy (opt (pchar '-') .>>. digit) // => (Some '-', '2')
"1"  |> parseBy (opt (pchar '-') .>>. digit) // => (None, '1')

many1Chars2 関数は、1回以上の繰り返しをパースするパーサーを返します。 manyCharsmany1Chars に似ていますが、引数を2つ取り、最初の1回は1つめの引数のパーサーを、以降は2つめの引数のパーサーを使います。 複数桁の数値は、先頭に 0 を許しません(1230はOKだけど、0123はNG)。 それを簡単に実現するために、 many1Chars2 を使っています。

"1230" |> parseBy (many1Chars2 (anyOf ['1'..'9']) digit) // => "1230"
"0123" |> parseBy (many1Chars2 (anyOf ['1'..'9']) digit) // => エラー

pstring 関数は、指定された文字列をパースするパーサーを返します。 many1Chars2 digit1to9 digit だけでは "0" がパース出来ないので、 <|> 演算子pstring "0" を合成することで対応しています。

tuple3 関数は、3つのパーサーを受け取ってそれらの結果を3要素タプルにするパーサーを返します。 .>>. 演算子を2回使ってもいいのですが、 .>>. 演算子を複数回使う場合、2要素タプルがネストしてしまいます。 これを避けるために、 tuple3 が使えます。tuple2 から tuple5 まで用意されています。

"1.2" |> parseBy (digit .>>. pchar '.' .>>. digit) // => (('1', '.'), '2')
"1.2" |> parseBy (tuple3 digit (pchar '.') digit)  // => ('1', '.', '2')

浮動小数点数は、「符号」「整数部」「小数部」の3つに分割できるため、 tuple3 を使っています。

jnumber まわりの定義を再掲します。

let minusSign = opt (pchar '-') |>> Option.isSome
let digit1to9 = anyOf ['1'..'9']
let integer = (many1Chars2 digit1to9 digit <|> pstring "0") |>> int
let jinteger =
  minusSign .>>. integer
  |>> (fun (hasMinus, x) -> JInteger (if hasMinus then -x else x))
let jfloat =
  tuple3 minusSign integer (pchar '.' >>. integer)
  |>> (fun (hasMinus, i, flac) ->
         let f = float i + float ("0." + string flac)
         JFloat (if hasMinus then -f else f))
let jnumber = (jinteger <|> jfloat) .>> ws

これで動きそうに見えますが、実はこれでは動きません。

"1"   |> parseBy jnumber // => JInteger 1
"2.0" |> parseBy jnumber // => エラー

エラーメッセージを見てみましょう。

parse error: Error in Ln: 1 Col: 2
2.0
 ^
Expecting: decimal digit or end of input

2.0. の位置で、数値か入力終了を期待していた、と出ています。 入力終了を期待していたということなので、 eof の合成をしない場合にどういう挙動になるのか確認してみましょう。

let parseByJNumber str =
  match run jnumber str with // eofを合成しない
  | Success (res, _, _) -> res
  | Failure (msg, _, _) -> failwithf "parse error: %s" msg

parseByJNumber "1"    // => JInteger 1
parseByJNumber "2.0"  // => JInteger 2

eof を合成している parseBy jnumber ではエラーになりましたが、eof を合成していない parseByJNumber では(JFloat 2.0 ではなく) JInteger 2 が返ってきました。 この結果が意味しているのは、 2.0 をパースする際、 2 までを読んで JInteger としてしまっており、 .0 が入力に残ったままになっているということです。

これは、 jfloat が成功する入力では必ず jinteger が成功してしまうことが原因です。 つまり、この jnumber の定義では jfloat が使われることはありません。

では、項を入れ替えてみてはどうでしょうか。

let jnumber = jfloat <|> jinteger

これであれば、 jfloat に失敗すれば jinteger が試されるため、問題ないように見えます。 しかし、今度は "1" のパースに失敗します。

parse error: Error in Ln: 1 Col: 2
1
 ^
Note: The error occurred at the end of the input stream.
Expecting: decimal digit or '.'

数値か . を期待していたけど、入力が終了してしまった、と言っています。 これは、 <|> 演算子が左項のパーサーが失敗しても、そのパーサーが消費した入力を戻さないことが原因です。 jnumber はまず jfloat を試しますが、 "1" が入力として与えられた際、整数部の入力までは成功します。 そして、小数点をパースしようとしますが . が見つからないため jfloat が失敗します。 この際に整数部を消費してしまったため、 jinteger が成功することはありません。 jinteger は数値を期待しているため、エラーがマージされ、「数値か . が期待されている」というメッセージになります。

この問題を最も手軽に解決するためには、失敗した際に入力を戻す*7パーサー attempt を合成します。

let jnumber = attempt jfloat <|> jinteger

attempt は入力を巻き戻すため、 attempt を使わずに済むなら使わない方が効率の良いパーサーになります。 <|> 演算子は、効率を重視してデフォルトの挙動が入力を巻き戻さないようになっているので、 attempt をやみくもに使うのはやめましょう。

attempt を使わずに今回の問題を解決する方法もあります。 例えば、 jintegerjfloat を削除し、 jnumber の定義を次のように変更します。

let jnumber =
  tuple3 minusSign integer (opt (pchar '.' >>. integer))
  |>> (function
       | (hasMinus, i, None) -> JInteger (if hasMinus then -i else i)
       | (hasMinus, i, Some flac) ->
           let f = float i + float ("0." + string flac)
           JFloat (if hasMinus then -f else f))

この定義は、小数点数以降を opt で省略可能にし、 |>> による変換部分で JInteger にするか JFloat にするかを決めています。 これにより、 attempt を使わずに整数と浮動小数点数を区別できるパーサーが手に入りました。

同じプレフィックス(今回の場合整数部)を持つ選択肢が3つ以上になった場合、 opt では解決できなくなります。 そのような場合でも、今回の手法を応用すれば解決可能です。

type Json =
  | JInteger of int
  | JFloat of float
  | JRational of int * int // 有理数を追加
  | JString of string
  | JArray of Json list

// ..略..

let jnum =
  // choice [p1; p2; ...; pn] は、 p1 <|> p2 <|> ... <|> pn と同じ意味で、高速
  choice
    [ pchar '.' >>. integer |>> (fun frac i -> JFloat (float i + float ("0." + string frac)))
      pchar '/' >>. integer |>> (fun d n -> JRational (n, d))
      preturn JInteger ] // preturnは、常に成功し、引数に指定した結果を返すパーサーを返す関数
let jnumber =
  tuple3 minusSign integer jnum
  |>> (fun (hasMinus, i, f) -> f (if hasMinus then -i else i))

再帰文法

さて、ここまでのパーサーでは、 JArray の要素に JIntegerJFloat しか許しません。 型の定義としては、 JString でも JArray 自体でもいいようになっていますので、この対応をしましょう。

現状の jarray の定義を確認しておきましょう。

let jarray =
  sepBy jnumber (pchar ',' >>. ws)
  |> between (pchar '[' >>. ws) (pchar ']' >>. ws)
  |>> JArray

sepByjnumber を渡していますね。 ここに自分自身が渡せればネストに対応できそうですが、F#ではそのようなことはできません。

let jarray =
  // jarrayの定義の中ではjarrayにアクセスできないのでコンパイルエラー
  sepBy (choice [jnumber; jstring; jarray]) (pchar ',' >>. ws)
  |> between (pchar '[' >>. ws) (pchar ']' >>. ws)
  |>> JArray

FParsecでは、このような再帰した文法を表現するために、 createParserForwardedToRef という関数を用意してくれています。 この関数は、パーサーとそのパーサーへの参照(ref 型)のタプルを返します。 そして、パーサーへの参照に定義を再代入により設定することで、再帰した文法が表現できます。

// jarray は、 jarrayRef を見るようになっている
let jarray, jarrayRef = createParserForwardedToRef ()
// jarrayRef は ref 型なので、再代入できる
jarrayRef :=
  // 再帰したい場合は、 !jarrayRef ではなく、 jarray を使う
  sepBy (choice [jnumber; jstring; jarray]) (pchar ',' >>. ws)
  |> between (pchar '[' >>. ws) (pchar ']' >>. ws)
  |>> JArray

これで、配列内に数値以外も格納できるようになりました。 JObject に対応することを考え、 json というパーサーを作っておきましょう。

let json, jsonRef = createParserForwardedToRef ()
let jarray =
  sepBy json (pchar ',' >>. ws)
  |> between (pchar '[' >>. ws) (pchar ']' >>. ws)
  |>> JArray
jsonRef :=
  choice [jnumber; jstring; jarray]

これで、 jobject などを作った場合に choice の中に入れるだけで配列の要素としてオブジェクトが使えるようになります。

"[[], 1, \"aaa\"]" |> parseBy json // => JArray [JArray []; JInteger 1; JString "aaa"]

再帰

JSONの文法はよく考えられているため、何も考えずに実装しても問題ないようにできています。 しかし、それでは勉強になりませんので、JSONを勝手に拡張して問題を起こしてみましょう。

このような入力をパース出来るようにしたいと思います。

[ 10 - 4 + 2, 20 ]

型の定義はこうでしょうか。

type NumExpr =
  | NEInteger of int           // 簡単のためにfloatは省略
  | NEAdd of NumExpr * NumExpr
  | NESub of NumExpr * NumExpr
type Json =
  | JNumExpr of NumExpr
  | JArray of Json list        // 簡単のためstringも省略

先程のJSON(拡張)をパースした結果は、このようになればいいでしょう。

JArray
  [ JNumExpr (NEAdd (NESub (NEInteger 10, NEInteger 4), NEInteger 2))
    JNumExpr (NEInteger 20) ]

これをパースするパーサーを何も考えずに実装すると、次のようになるでしょう。

let ws = spaces

let neinteger = pint32 .>> ws |>> NEInteger
let numExpr, numExprRef = createParserForwardedToRef ()
let neadd =
  (numExpr .>> pchar '+' .>> ws) .>>. neinteger |>> NEAdd
let nesub =
  (numExpr .>> pchar '-' .>> ws) .>>. neinteger |>> NESub
numExprRef := choice [attempt neadd; attempt nesub; neinteger]

let jnumExpr = numExpr |>> JNumExpr

let json, jsonRef = createParserForwardedToRef ()
let jarray =
  sepBy json (pchar ',' >>. ws)
  |> between (pchar '[' >>. ws) (pchar ']' >>. ws)
  |>> JArray
jsonRef :=
  choice [jnumExpr; jarray]

let parseBy p str =
  match run (ws >>. p .>> eof) str with
  | Success (res, _, _) -> res
  | Failure (msg, _, _) -> failwithf "parse error: %s" msg

しかし、このパーサーで "[ 10 - 4 + 2, 20 ]" をパースしようとすると StackOverflowException が発生します。 問題は、この辺りにあります。

let neadd =
  (numExpr .>> pchar '+' .>> ws) .>>. neinteger |>> NEAdd
let nesub =
  (numExpr .>> pchar '-' .>> ws) .>>. neinteger |>> NESub
numExprRef := choice [attempt neadd; attempt nesub; neinteger]

まず、 numExpr でパースしようとします。 choice の先頭に neadd があるので、 neadd でパースしようとします。 neadd の先頭に numExpr があるので、 numExpr でパースしようとします。 ・・・戻ってきてしまいましたね。 このように、入力をなにも消費せずに再帰してしまうと、パースが先に進まずにスタックオーバーフローしてしまうのです。

このように、文法の先頭(左側)で再帰している文法を再帰の文法といいます。

この問題を解決するために、ここでは再帰を繰り返しで表現する方法を使います。

// numExpr ::= neinteger (op neinteger)*
let numExpr =
  neinteger .>>. (many (op .>>. neinteger)) // opの定義は後で

many 関数は、引数のパーサーの0回以上の繰り返しをパースするパーサーを返します。 このままでは、 numExpr パーサーの結果の型は NumExpr * (opの結果の型 * NumExpr) list になってしまいます。 これを NumExpr にしないといけません。 複数の NumExpr を一つの NumExpr にする必要があるので、 List.fold を使えばいいでしょう。

let numExpr =
  neinteger .>>. many (op .>>. neinteger)
  |>> (fun (i, xs) ->
         List.fold (fun crnt (op, next) ->
                      // crnt, op, nextを使ってNEAdd, NESubを作る
                      ...) i xs)

op は例えばこのような定義が考えられます。

type Op = Add | Sub
let op =
  (pchar '+' .>> ws >>% Add) <|> (pchar '-' .>> ws >>% Sub)

>>% 演算子は、左項のパーサーが成功した場合に右項の値を返すパーサーを返します。

"a" |> parseBy (pchar 'a' >>% [1; 2; 3]) // => [1; 2; 3]

先程の op 定義の場合、 List.fold に渡す関数はこのようにすればいいでしょう。

let f crnt (op, next) =
  match op with
  | Add -> NEAdd (crnt, next)
  | Sub -> NESub (crnt, next)

これで、 "[ 10 - 4 + 2, 20 ]" がパース出来るようになりました。

"[ 10 - 4 + 2, 20 ]"
|> parseBy json
     // => JArray
     //      [JNumExpr (NEAdd (NESub (NEInteger 10,NEInteger 4),NEInteger 2));
     //       JNumExpr (NEInteger 20)]

さて、これでもいいのですが、 NEAdd に対応する Add, NESub に対応する Sub を定義する必要があるのが少し面倒です。 そこで、 op の結果の型を関数にして、 crntnext を渡して NEAddNESub を返すようにしてみましょう。

let op =
  choice
    [ pchar '+' .>> ws >>% (fun a b -> NEAdd (a, b))
      pchar '-' .>> ws >>% (fun a b -> NESub (a, b)) ]
let numExpr =
  neinteger .>>. many (op .>>. neinteger)
  |>> (fun (i, xs) ->
         List.fold (fun crnt (f, next) -> f crnt next) i xs)

だいぶすっきりしました。

実は、これを一発でやってくれる chainl1 という関数がFParsecに用意されています。

let op =
  choice
    [ pchar '+' .>> ws >>% (fun a b -> NEAdd (a, b))
      pchar '-' .>> ws >>% (fun a b -> NESub (a, b)) ]
let numExpr = chainl1 neinteger op

便利ですね。

まとめ

最後の方はJSONに関係のない拡張をベースに説明しましたが、ここまでで数値、文字列、配列が実装できました。 残っている機能は次の通りです。

  • null
  • true / false
  • JFloat の指数表記対応
  • \uXXXX 形式の文字対応
  • オブジェクト

オブジェクト以外は簡単に対応できるでしょう。 オブジェクトも、配列を参考にすればそれほど難しくないと思うので、ぜひ実装してみてください。

年末年始は、パーサーを書いて過ごしましょう!

*1:お使いの言語がジェネリクスや無名関数をサポートしていないような場合はこの限りではありません。

*2:JSONを使うだけの場合、オブジェクトのキーとして文字列しか使えないことなどが煩わしく感じた方も多いと思います。しかし、パーサーを作る側の視点に立つと、それなりの表現能力を少ない労力で手に入れられるようによく考えられた仕様であるということに気付けるようになります。コメントくらいは欲しいですが・・・

*3:p はパーサーを表すプレフィックスです。FParsecでは、標準関数などと名前がかぶるパーサーには p プレフィックスを付けて区別できるようになっています。

*4:F#では流れる方向を意識した演算子が標準でも用意されており、その文化にFParsecも合わせるような演算子の使い方をしています。

*5:>>. に入っている最適化が between には入っていません。 >>. の前段に2つのパーサがあるため、コードが複雑になる事を嫌ったのかもしれません。

*6:1回以上の繰り返しの場合は many1Chars 関数を使います。 sepBy1 や spaces1 と違い、 many のサフィックスとして1が付く点に注意してください。 many / many1 というパーサーもあり、これは list を返しますが、 manyChars / many1Chars はリストを連結して文字列を返します。

*7:厳密に言うと、引数のパーサーを実行する前に現在の状態(入力のどこまで読んだかという位置情報など)を保持しておき、引数のパーサーが失敗した場合にパーサーの状態を戻します。

C#に型クラスを入れる実装の話

この記事はC# Advent Calendar 2016の12日目のものです。 昨日(今日)書いた、F# Advent Calendar 2016 11目C#版です。

今日のリポジトリはこちら。

github.com

実は、F#版だけじゃなくてC#版の実装もあります。 ということで、そのざっくりした紹介です。

型クラス?コンセプト?

F#版では「型クラス(type class)」と呼んでいますが、C#版では「コンセプト(concept)」と呼んでいるようです。 で、コンセプトがあると何がうれしいかですが、例えばC#には現在3つの2要素タプルがあります。

  • System.Collections.KeyValuePair<TKey, TValue>
  • System.Tuple<T1, T2>
  • (T1, T2)

これらの型すべてに対応するためには、現在のC#ではオーバーロードを3つ書く必要があります。 例えば、「2要素タプルの IEnumerable から1番目の要素を取り出した IEnumerable にしたい」という場合を考えてみましょう。

public static IEnumerable<T1> FirstAll<T1, T2>(IEnumerable<KeyValuePair<T1, T2>> xs)
    => xs.Select(kvp => kvp.Key);
public static IEnumerable<T1> FirstAll<T1, T2>(IEnumerable<Tuple<T1, T2>> xs)
    => xs.Select(t => t.Item1);
public static IEnumerable<T1> FirstAll<T1, T2>(IEnumerable<(T1, T2)> xs)
    => xs.Select(t => t.Item1);

面倒ですね。 ここで、提案されているコンセプトを使った場合にどうなるか見てみましょう。

// 新しいキーワードconceptを使ってコンセプトを定義
public concept Tuple2<Tpl, [AssociatedType] T1, [AssociatedType] T2>
{
    T1 First(Tpl t);
    T2 Second(Tpl t);
    Tpl Make(T1 item1, T2 item2);
}

// 新しいキーワードinstanceを使ってコンセプトのインスタンスを定義
// ここではKeyValuePairをTuple2のインスタンスにしている
public instance KeyValuePairTuple2<T1, T2> : Tuple2<KeyValuePair<T1, T2>, T1, T2>
{
    T1 First(KeyValuePair<T1, T2> t) => t.Key;
    T2 Second(KeyValuePair<T1, T2> t) => t.Value;
    KeyValuePair<T1, T2> Make(T1 item1, T2 item2) => new KeyValuePair<T1, T2>(item1, item2);
}

// System.TupleをTuple2のインスタンスにする
public instance TupleTuple2<T1, T2> : Tuple2<Tuple<T1, T2>, T1, T2>
{
    T1 First(Tuple<T1, T2> t) => t.Item1;
    T2 Second(Tuple<T1, T2> t) => t.Item2;
    Tuple<T1, T2> Make(T1 item1, T2 item2) => Tuple.Create(item1, item2);
}

// System.ValueTupleをTuple2のインスタンスにする
public instance ValueTupleTuple2<T1, T2> : Tuple2<(T1, T2), T1, T2>
{
    T1 First((T1, T2) t) => t.Item1;
    T2 Second((T1, T2) t) => t.Item2;
    (T1, T2) Make(T1 item1, T2 item2) => (item1, item2);
}

こういう定義をしておけば、あとは一つだけ実装を書くだけです。

// 型パラメータにimplicitを付けて、その型パラメータがTuple2でなければならないことを制約で書く
public static IEnumerable<T1> FirstAll<T1, T2, implicit Tpl2>(IEnumerable<Tpl2> xs) where Tpl2 : Tuple2<T1, T2>
    => xs.Select(x => First(x)); // 本体部分では何の修飾もなしにメソッドを呼び出す

// 当然、SecondAllも同様に定義可能
public static IEnumerable<T2> SecondAll<T1, T2, implicit Tpl2>(IEnumerable<Tpl2> xs) where Tpl2 : Tuple2<T1, T2>
    => xs.Select(x => Second(x));

これで、定義した FirstAllSecondAll には IEnumerable<KeyValuePair<TKey, TValue>>IEnumerable<Tuple<T1, T2>>IEnumerable<(T1, T2)> も渡せます。 このように、既存の型に対して後付けで新たな抽象を追加できるのがコンセプトの便利なところの一つです。

ここからは未確認ですが、おそらく戻り値オーバーロードのようなこともできるようです。

public static IEnumerable<Tpl2> Singleton<T1, T2, implicit Tpl2>(T1 x, T2 y) where Tpl2 : Tuple2<T1, T2>
    => Enumerable.Repeat(Make(x, y), 1);

IEnumerable<KeyValuePair<string, int>> res1 = Singleton("aaa", 0);
IEnumerable<Tuple<int, int>> res2 = Singleton(10, 20);
IEnumerable<(string, string)> res3 = Singleton("hoge", "piyo");

他にも、例えば今は Enumerable.SequentialEqualIEnumerable<T> どうしの比較をしていますが、比較不可能なもの((Equals をオーバーライドしていないとかとか))でもコンパイルが通ってしまいますが、コンセプトが導入されれば Eq コンセプトの要素を持つ場合のみに有効な比較演算子みたいなものも定義出来てうれしい、とかがあったりします。

この実装方法の利点・欠点

この実装方法は、既存のランタイムに全く手を加える必要がないのが利点です。

欠点は、この実装方法でどこまでやるかという話になりますが、例えば == 演算子Eq コンセプトで置き換えるとなると、互換性を犠牲にする必要が出てきてしまう点です。 全部作り直してしまえるタイミングはとうの昔に過ぎ去っているので、別の演算子を導入するとか何らかのスイッチで切り替えられるようにしておくとかしないといけません(そんなの知るか、全部作り直しじゃー!ってのも面白いんですけどまずないでしょう)。

C#にコンセプトはいつ乗るの?

この実装が乗ることはまずないです。 ですが、こういう「今ここにない機能」が実際に動作するコードとともに公開されているというのは、いい時代になったものです。 コンセプト(≒型クラス)は、Haskellはもちろん似たような機能がSwiftやRust、Scalaといった今をときめく言語たちに乗っていますので、この実装そのままではなくても、いつかはC#にも乗ったりする日が来るかもしれませんね。

F#に型クラスを入れる実装の話

この記事はF# Advent Calendar 2016の11日目のものです。ちょっと遅れてしまいました。。。

ICFP 2016(と併催されたML workshop?)で気になる内容があったので、ちょっとまとめてみました。

Classes for the Masses - ICFP 2016

ざっくり、F#に型クラスを導入してみたぜ、って内容です。

型クラスとは

JavaC#での interface みたいなものですが、interface は侵入的なのに対して、型クラスは非侵入的という違いがあります。

侵入的というのは、型の定義にその interface を実装しますよ、ということを書く必要があることを意味します。

// C#
interface Eq<A>
{
    bool Equal(A a, A b);
}

// intefaceは型に侵入する
class SomeClass : Eq<SomeClass>
{
    public bool Equal(A a, A b) { ... }
}

それに対して型クラスは非侵入的であり、型の定義にその型クラスを実装することは書きません。

-- haskell
class Eq a where
  (==) :: a -> a -> Bool

-- 型クラスは型の定義に書かなくていい
data SomeType = ...

-- SomeTypeをEq型クラスのインスタンスにする(型定義と分かれている)
instance Eq SomeType where
  x == y = ...

これの何が嬉しいかというと、ひとつは、型の定義をその型に対して可能な操作と分離できることです*1

これによって、例えば標準ライブラリの型に対しても、後付けで型クラスのインスタンスにできるようになります。 抽象を後付けできるとでも表現すればいいでしょうか。

この型クラスをF#に導入してみた、というのが今回紹介する内容です。

F#への型クラスの実装方法

実際に動作するコードは下記のリポジトリで公開されています。

github.com

先に示した Eq 型クラスはこの実装を使うと、

// Eq型クラスの実装(interfaceとしてコンパイルされる)
[<Trait>]
type Eq<'a> =
  abstract equal: 'a -> 'a -> bool

// SomeTypeをEq型クラスのインスタンスにする(structとしてコンパイルされる)
// Haskellと違い、インスタンスの定義に名前(ここではEqSomeType)が必要
[<Witness>]
type EqSomeType =
  interface Eq<SomeType> with
    member equal x y = ...

と書きます。

この Eq 型クラスを使うには、

let (==) a b = Eq.equal a b

のように、型クラス名.メンバー 引数リスト ... のように書くようです。 型クラスは structコンパイルされるため、デフォルト値を介して型クラスのメンバーにアクセスできます。 この関数は、下記のようにコンパイルされます。

// C#モドキ
public static bool operator ==<A, EqA>(A a, A b) where EqA : struct, Main.Eq<A>
    => default(EqA).equal(a, b);

struct を使うことで、追加の引数を不要にしています。

また、Eq 型クラスを要素に持つリストを Eq 型クラスのインスタンスにする(それ以外のリストは Eq 型クラスにしない)こともできます。

[<Witness>]
type EqList<'a, 'EqA when 'EqA :> Eq<'a>> =
  interface Eq<'a list> with
    member equal a b =
      match a, b with
      | x::xs, y::ys -> Eq.equal a b && Eq.equal xs ys
      | [], [] -> true
      | _, _ -> false

互換性及び他の.NET言語との連携

ここまででみたように、この実装ではあくまで.NETの型でそのまま表現できる形になっています。 ランタイムに手を加える必要がないため、互換性を崩すことなく採用できるように実装されている、ということです。

また型クラスを使った関数は、型クラスに対応しない既存の.NET言語からは型パラメータを明示的に渡せば使えます(使いやすいとは言っていない)。

この方法の問題点

この方法はランタイムに手を加えないため、(例えば Monad のような)高階型クラスがサポートできません。 ううむ、残念・・・

あ、それと、このリポジトリをcloneしてbuild.cmdを管理者権限で実行するとF#の環境がぶっ壊れた(VSでビルドできなくなった)ので、やるなら仮想環境で試してみることをお勧めします。

*1:オブジェクト指向プログラミングのよくある説明の一つに「データと操作をひとまとまりにできる」というものがありますが、それとはある意味正反対の特徴ですね。まぁ、この「データと操作をひとまとまりにできる」という説明には言いたいことがあるんですが、それは別の機会にでも

続・そろそろPower Assertについてひとこと言っておくか

3年前にこんな記事をあげました。

bleis-tift.hatenablog.com

3行でまとめると、

  • Power Assertはユニットテストのためにほしかったものではない
  • 欲しいのは結果の差分
  • 誰か作って!

というエントリでした。 そしたら id:pocketberserker が作ってくれました!

github.com

PowerAssertより強そうな名前でいい感じです。

MuscleAssertの使い方

このライブラリは、PersimmonというF#用のテスティングフレームワークを拡張するライブラリとして作られています。 ただ、ざっくり概要をつかむだけであればどちらも知らなくても問題ありません。 このライブラリでできることはほぼ1つだけです。

open Persimmon
open Persimmon.Syntax.UseTestNameByReflection
open Persimmon.MuscleAssert

let add x y = x + y

let ``add 2 35を返す`` () = test {
  do! add 2 3 === 5
}

以上。簡単。 これを実行しても成功してしまって面白みがないので、わざと間違ってみましょう。

open Persimmon
open Persimmon.Syntax.UseTestNameByReflection
open Persimmon.MuscleAssert

let add x y = x + x // ミス!

let ``add 2 35を返す`` () = test {
  do! add 2 3 === 5
}

これをPersimmon.Consoleで実行すると、

 Assertion Violated: add 2 3が5を返す
 1. .
      left  4
      right 5

こんなエラーが出てきました。 普通ですね。

では、例えばこんなJSONがあったとしましょう。

{"widget": {
    "debug": "on",
    "window": {
        "title": "Sample Konfabulator Widget",
        "name": "main_window",
        "width": 500,
        "height": 500
    },
    "image": { 
        "src": "Images/Sun.png",
        "name": "sun1",
        "hOffset": 250,
        "vOffset": 250,
        "alignment": "center"
    },
    "text": {
        "data": "Click Here",
        "size": 36,
        "style": "bold",
        "name": "text1",
        "hOffset": 250,
        "vOffset": 100,
        "alignment": "center",
        "onMouseUp": "sun1.opacity = (sun1.opacity / 100) * 90;"
    }
}}

これを読み込む関数を定義したとして、その関数をテストしたいですよね。

let expected =

let ``JSONが読み込める`` () = test {
  do! read json === expected
}

read 関数の実装にミスがあり、textvOffsethOffset の値を使ってしまったとしましょう。 このテストを実行すると、下記のようなエラーメッセージが表示されます。

 Assertion Violated: JSONが読み込める
 1. .text.vOffset
      left  250
      right 100

textvOffset の値が左は 250 だったけど、右は 100 だった、ということが一目瞭然です。

MuscleAssert VS PowerAssert

MuscleAssertとPowerAssertの目的ははっきりと分かれています。 MuscleAssertが最初からテスティングフレームワークアサーションを書くために特化しているのに対して、PowerAssertは(テストではなく)表明に使うことを前提にデザインされています。

表明手段

表明手段としてのPowerAssertはとても便利です。 言語内蔵の assert は、条件式が false の場合に何やらメッセージを出しますが、「どこで表明が false と評価された」くらいの情報しか持っていません。 メッセージをカスタマイズすることはできますが、文字列で指定する必要があるため「どうなったか」を埋め込むのは大変です。

PowerAssertは、言語内蔵の assert をそのままに表示されるメッセージをリッチにしてくれます。 表明として埋め込んだ式の「部分式の値」がメッセージとして表示されるため、「どの式の評価値が想定と違うのか」を調べるための情報をコーディングのコストを払わずに得られるようになるのです。

対してMuscleAssertはそもそも、Persimmon.MuscleAssertはPersimmon用のライブラリとして作られているため、Persimmonに依存しており単体で使えるものではありません。 表明に使えたとしても、MuscleAssertは式全体の評価結果の差分を出すため、ほしい情報である「どの式の評価値が想定と違うのか」を調べるための情報はそこに乗っていないでしょう。

表明手段としては、PowerAssertの圧勝です。

ユニットテストアサーション

しかし、MuscleAssertがやりたかったのは表明ではありません。 ユニットテストアサーションとして使いたかったのです。

MuscleAssertが例えばJSONのようなネストした構造に対するテストに強そうだ、というのは先ほど紹介した例で分かると思います。 XMLJSONYAMLは当然として、そもそもクラス自体が何かを内部に持っているネスト構造をしているため、ネストした構造をそのまま比較してもわかりやすいメッセージが出力されるMuscleAssertは便利です。

対してPowerAssertはこの例には貧弱です。

let ``JSONが読み込める`` () = test {
  do! read json === expected
}

このテストが失敗するとして、PowerAssertで表示されるのは

  • json 変数の中身
  • read json の結果
  • expected の中身
  • read json === expectedfalse になったということ

ですかね。 どれもドバドバと大量の出力をするわりに、本当に欲しい「どこがどう違うのか?」という情報はそこから得るのは容易ではありません。 diffツールを使って外部でdiffとるとかしたことある人も多いんじゃないでしょうか?

そもそも、テストで actual 側に部分式が出てうれしいほど何かを書くことって多いのか?というのも疑問です。 このテストのように、多くのテストでは期待値との一点比較ができればいいのではないでしょうか?

ちなみに、MuscleAssertでは一度に複数の箇所の間違いを出してくれますので、小さいテストをまとめるのも容易です。

1. .image.hOffset
      left  500
      right 250
    .image.vOffset
      left  500
      right 250
    .text.vOffset
      left  250
      right 100
    .text.alignment
      left  centre
      right center

    @@ -1,6 +1,6 @@
     cent
    -re
    +er

MuscleAssertの弱点

MuscleAssertの弱点は、一点比較しかできないところです。 そのため、浮動小数点数を含むデータ構造を、浮動小数点数の一致範囲を指定して比較、ということは現状ではできません。 また、大小比較などもサポートしていません。

現状でこれらをテストしたい場合は、MuscleAssertを使わずにテストするしかありません。 今のところ、これで困ったことはありません(そういうテストが必要なドメインで仕事をしていない)。

まとめ

まとめも3行で。

  • MuscleAssert便利
  • テストのためのアサーションライブラリとしてはPowerAssertよりも便利
  • 弱点はある。でも自分が困っていないから放置

みなさんも自分が使っている言語でMuscleAssertを実装してみてはいかがでしょう?便利ですよ。