第1回継続勉強会を開催しました
最近自分の中で継続熱が高まっているので、継続の話をできる場所が欲しくなりました。 とはいっても、そもそも継続の知識を持っている人が少ないので、そこを広めるところから始めることにしました。 社内でも継続を理解したいという人がおり、その人たちも勉強会を開きたいという話をしていたため、継続勉強会を開くことにしました。
とりあえずの目標としては、浅井先生のshift/resetプログラミング入門(PDF)を理解するところまでとしました。 第0回は社内で試しにどこまで行けそうかを見てみて、6回で1章と2章が終えられそうだったので、隔週開催でまずは6回やってみることにしました。
ここでは第1回でやった内容を紹介します。
やったこと
会の趣旨の説明と、テキストを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) { ... } })();
多値について本気で考えてみた
先日のエントリの反応として、多値の批判をしているように受け取られた方がいました。 実際には、多値の批判をしているのではなく、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/cc
で values
呼び出し以降の処理を切り取って 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言語の多値は始まりでしかありません。 みなさんも自分だけの多値の世界を考えて、どんどん多値のすばらしさを世界に発信していきましょう!
参考ページ
- Scheme:多値: Schemeでの多値についての解説ページ。
- なんでも継続: 継続についての解説ページ。未完。
- 思考実験: returnを関数と思ってみる話: JavaScript風言語でreturnを関数と思ったらどういう世界があるのか考察したページ。
- なぜ、多値関数は人気がないのだろう - 檜山正幸のキマイラ飼育記: 多値が流行っていない理由の考察ページ。
- 他にもあったけど忘れた・・・
*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言語は多値っぽいけど多値じゃないものを入れてしまったのでそこはすごく残念。
Go言語のイケてない部分
最近色々あって仕事でGo言語を使っています。 色々割り切っている言語なので、こんなこと言ってもしゃーないんですが、言語設計はミスってるんじゃなかなぁ、と思わざるを得ない点が多々あります。 使い始めて1か月くらいなので間違ったことを書いているかもしれませんので、何かあれば指摘していただけるとありがたいです。
本文ではネガばかり羅列していますが、ランタイムとツール周りは気に入っています。 Goのランタイムを使う、もっと洗練されたAlt Go的なものがあるといいのに(もしくはジェネリクスのったGo2を早くリリースしてほしい)、と思う日々です。
追記: なんか意図とは違った受け取られ方をしている方もいるので追記します。 この記事はあくまで、「Go言語を学ぶにあたって躓いた点」を列挙し、まとめ、理由を考えてみる(教えてもらう)ために書いたものです。 Go言語自体はDisってますが、Go言語ユーザーをDisる目的では書いていません。
また、以下のような意見も見られました。
まずひとつめについてですが、自分はPythonやRubyのようないわゆる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
これを念頭に読んでください。
追記: 多値に関して、別記事としてまとめました。
こちらを読んでいただければ、多値はダメだからタプルを入れるべきだった、という話をしていないことが分かっていただけるかと思います。
多値をひと塊で扱える例外: 多値を多値として返す
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.Println
が interface{}
という何でも渡せる型を可変長引数として複数受け取れる関数なので、 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
とそうでない場合とか、 err
が nil
かそうでないかなどで分岐処理が書けたのに、残念な文法の選択をしたと思います。
多値が使えると便利そうなのに使えない: チャネル
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 "", "" }
としたうえでコンパイルすると、 string
は error
を実装していない、というコンパイルエラーになります。
また、 :=
では新たな識別子を導入しないとコンパイルエラーになるため、
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
は :=
で受ける。統一されていると思いませんか。
追記:
ちなみにerrに何度も代入するところは「if err := g(); err != nil {}」と書くのでなにも問題ない。
— のぼのぼ☂️ (@nobonobo) 2018年11月8日
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
スコープではなく、関数に属する
そのままです。罠ですよね。 一応、無名関数をその場で呼び出すことで回避できますが、スコープに属するようにしてくれればよかったのに、と思います。 そうなっていない理由は効率なのでしょうか。わかりません。
追記:
if xxx {
— いわた (@wonderful_panda) 2018年11月8日
defer con.Close()
}
とか書けた方がうれしいことあるやろ?だから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) })
とやったらどうなりますか。
そうです。 reason
が nil
ではなかった場合、reason
がレスポンスに書き込まれますが、レスポンスへの書き込み自体が失敗しなければ c.JSON
は nil
が返ってくるので、
ハンドラーの中の if
には入らず、再度 c.JSON
が呼び出され、ステータスOKでエラーレスポンス(reasonの内容)が返されます。
さらに、エラーレスポンスの後ろに []
というゴミが付いて しまいます。
なぜなら c.JSON
はレスポンスに書き込むだけだから。
ハンドラーの最後の return
で res
を書き込んでいますから。
多くの場合エラーがあれば 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つの方法があります。
- 手書き
- パーサージェネレーター
- パーサーコンビネーター
手書きによる方法
手書きによる方法では通常、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に戻る
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]
に変換できたらとりあえずの目標達成ということになります。
いきなり JNumber
と JArray
の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文字以上の空白文字をパースするパーサーです。
これまで見てきた pfloat
や pchar
と違い、パースした文字列を結果として返さない(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
sepBy
や between
で .>>
ではなく >>.
を使っていますが、解析結果には含まれないため、どちらを使っても構いません。
しかし、 .>>
よりも >>.
の方が効率がいい場合があるため、どちらでもいい場合は >>.
を使うようにするといいでしょう。
ちなみに、 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
で実現しています。
digit
は 0
から 9
までの文字をパースするパーサーです。
"-2" |> parseBy (opt (pchar '-') .>>. digit) // => (Some '-', '2') "1" |> parseBy (opt (pchar '-') .>>. digit) // => (None, '1')
many1Chars2
関数は、1回以上の繰り返しをパースするパーサーを返します。
manyChars
や many1Chars
に似ていますが、引数を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
を使わずに今回の問題を解決する方法もあります。
例えば、 jinteger
と jfloat
を削除し、 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
の要素に JInteger
か JFloat
しか許しません。
型の定義としては、 JString
でも JArray
自体でもいいようになっていますので、この対応をしましょう。
現状の jarray
の定義を確認しておきましょう。
let jarray = sepBy jnumber (pchar ',' >>. ws) |> between (pchar '[' >>. ws) (pchar ']' >>. ws) |>> JArray
sepBy
に jnumber
を渡していますね。
ここに自分自身が渡せればネストに対応できそうですが、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
の結果の型を関数にして、 crnt
と next
を渡して NEAdd
や NESub
を返すようにしてみましょう。
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#版です。
今日のリポジトリはこちら。
実は、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));
これで、定義した FirstAll
や SecondAll
には 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.SequentialEqual
で IEnumerable<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#に型クラスを導入してみたぜ、って内容です。
型クラスとは
JavaやC#での 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#への型クラスの実装方法
実際に動作するコードは下記のリポジトリで公開されています。
先に示した 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でビルドできなくなった)ので、やるなら仮想環境で試してみることをお勧めします。
続・そろそろPower Assertについてひとこと言っておくか
3年前にこんな記事をあげました。
3行でまとめると、
- Power Assertはユニットテストのためにほしかったものではない
- 欲しいのは結果の差分
- 誰か作って!
というエントリでした。 そしたら id:pocketberserker が作ってくれました!
PowerAssertより強そうな名前でいい感じです。
Power Assertは時代遅れ、今はMuscle Assertだ!的な話かな?
— 裸のWPF/MVVMを書く男(マン) (@gab_km) 2016年6月1日
MuscleAssertの使い方
このライブラリは、PersimmonというF#用のテスティングフレームワークを拡張するライブラリとして作られています。 ただ、ざっくり概要をつかむだけであればどちらも知らなくても問題ありません。 このライブラリでできることはほぼ1つだけです。
open Persimmon open Persimmon.Syntax.UseTestNameByReflection open Persimmon.MuscleAssert let add x y = x + y let ``add 2 3が5を返す`` () = test { do! add 2 3 === 5 }
以上。簡単。 これを実行しても成功してしまって面白みがないので、わざと間違ってみましょう。
open Persimmon open Persimmon.Syntax.UseTestNameByReflection open Persimmon.MuscleAssert let add x y = x + x // ミス! let ``add 2 3が5を返す`` () = 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
関数の実装にミスがあり、text
の vOffset
に hOffset
の値を使ってしまったとしましょう。
このテストを実行すると、下記のようなエラーメッセージが表示されます。
Assertion Violated: JSONが読み込める 1. .text.vOffset left 250 right 100
text
の vOffset
の値が左は 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のようなネストした構造に対するテストに強そうだ、というのは先ほど紹介した例で分かると思います。 XMLやJSONやYAMLは当然として、そもそもクラス自体が何かを内部に持っているネスト構造をしているため、ネストした構造をそのまま比較してもわかりやすいメッセージが出力されるMuscleAssertは便利です。
対してPowerAssertはこの例には貧弱です。
let ``JSONが読み込める`` () = test { do! read json === expected }
このテストが失敗するとして、PowerAssertで表示されるのは
json
変数の中身read json
の結果expected
の中身read json === expected
がfalse
になったということ
ですかね。 どれもドバドバと大量の出力をするわりに、本当に欲しい「どこがどう違うのか?」という情報はそこから得るのは容易ではありません。 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を実装してみてはいかがでしょう?便利ですよ。