val it: α → α = fun

行きがかり上、こちらもブログで紹介するのが筋かもしれないのでメモっておこう。

Yacc is Deadというタイトルの論文については先日紹介したとおりなのだけど、実はあの後、Russ CoxがYacc is Not Deadという記事を書いていた。この指摘が面白くて当を得ているので面白いと思った次第。この記事自体は会社で教えてもらって、読んだ結果を社内で軽く発表(?)したりしたのだが、そのときの記憶をたどりながら書いている。

Russ CoxはPlan9の開発に携わっていたエンジニアで、今はGoogleに在籍し、オートマトンの理論に基づいた正規表現エンジンライブラリであるre2やGo言語の開発に携わっている。今回はその彼のre2や形式言語処理の経験が生きた指摘になっている。

とはいえ、Russ Coxの指摘はまっとうかつ普通なものだ。私も自分の感想に書いたのだが「これ本当に効率的に動作するのか?」という疑問があり、けっきょくパース対象の文字列長nに対してO(kⁿ)かかる可能性のある文法を構築できることが指摘されている。それじゃ意味ないじゃん、ということである。Russ Cox自身、Yaccが生き残るかどうかということを問題にしているのではなく、Yacc is Dead論文が提示したものが、著者の主張するような利点を持たないのでは、という指摘である。

Yacc is DeadについてのLambda the Ultimateのエントリにもこの指摘がコメントとして貼られていて、Russ Cox is confusedと言われたり、そこに本人が登場してdisappointed, maybe, but not confusedと反論していたりするのも面白い。

でもなぜRuss Coxはdisappointed(失望させられている)のだろう。計算量がどれぐらい問題とされるのだろう。これについては、私の紹介ではすっぱりと割愛した、Yacc is Dead論文の序章を読まなければならない。序章で著者のMatthew Mightは、世の中のプログラムのどれだけ多くが、正規表現を使ってアドホックにデータをパースしているか、という問題を提示する。Mightはこうしたパースを「カーゴカルト・パーシング」と罵倒し、どうやったらこれを追放できるかを考えている。なぜ正規表現を使うかといえば、正規表現はわかりやすいからだ(MightいわくWYSIWYGである)。いっぽう、文脈自由文法のパースは、ベースとなるアルゴリズムの挙動を理解していないと、謎のconflictのエラーに悩まされることになり、面倒くさい。いわく、WYSIWYGIYULR(k) — what you see is what you get if you understand LR(k) — であって、これが問題だということになる。

それで、カーゴカルト・パーシングに引導を渡すには、次の三つの条件を満たすものが必要だとMightは言う。

1. 任意の文脈自由文法を扱えること
2. 平均的には効率的に動作すること
3. 少ない労力でライブラリとして実装できること

ここまではとても納得が行く人も多いんじゃないだろうか。わたしもなるほどと思った。Russ Coxの指摘が問題にしているのは2番であり、本当に平均的には効率的に動作すると言えるのか?ということである。そして、効率的に動作させることが難しいならば、カーゴカルト・パーシングは終わらないだろう。Russ Coxやコメントでは、任意の文脈自由文法を扱えて、とりうる構文木のうち1つだけを返しO(n³)なアルゴリズムがいくつか挙げられている。ようはこちらのほうがマシなのではないかというわけだ……。

ところで今気づいたけど、Lambda the Ultimateのエントリで「Russ Cox is confused」っていうコメントを書いてるThomas Lordって、もしかしてあのGNU archのTom Lord？

—

Yacc is Not Deadの最後の段落はちょっと面白いので訳しておこう。

Yaccは古いツールだし、さすがに時代を感じるが、Plan9のマニュアルでlex(1)について書かれているように「この恐竜を殺す隕石はいまだに軌道上にある」。Yaccそのものは使われないとあなたが思おうが(それも真実から程遠いが)、代替となるべき機能をもつ新しいツールでさえその精神を受け継いでいる。GNU BisonはLALR(1)ではなくGLRパーサとして動作させることができるが、BisonはYaccと同じく詳細さを欠いたいらいらさせられるエラーメッセージを表示させている(私はbison.outputファイルをパースして何が本当に間違っていたのかを教えてくれるawkスクリプトを使っている)。ANTLRはもっと多機能だがあまり広まっていない。これらのツールやほかのものはみな、構文に曖昧性がないと言われれば線形時間のパーサを与えるし、そうでなければ立方時間のパーサを与えてくれることを保証している。コンピュータ科学の理論はそれより良い方法を知らない。だがいずれにせよ、そのどちらも指数時間パーサよりは良い。
だからそう、Yaccは死んでいない。たとえYacc自体がそんな雰囲気を匂わせていても、多くの人がそうであってほしいと願っていても。

Yacc is an old tool, and it’s showing its age, but as the Plan 9 manual says of lex(1), “The asteroid to kill this dinosaur is still in orbit.” Even if you think yacc itself is unused (which is far from the truth), the newer tools that provide compelling alternatives still embody its spirit. GNU Bison can optionally generate a GLR parser instead of an LALR(1) parsers, though Bison still retains yacc’s infuriating lack of detail in error messages. (I use an awk script to parse the bison.output file and tell me what really went wrong.) ANTLR is a more full featured though less widespread take on the approach. These tools and many others all have the guarantee that if they tell you the grammar is unambiguous, they’ll give you a linear-time parser, and if not, they’ll give you at worst a cubic-time parser. Computer science theory doesn’t know a better way. But any of these is better than an exponential time parser.
So no, yacc is not dead, even if it sometimes smells that way, and even if many people wish it were.

ただ、私とRuss Coxには少し見解の違うところがあり、Russ Coxは上記の条件のうち3をあまり重視していないように思う。Yaccなどの問題のうちの一つは、独自の構文のファイルを書いてそれをプログラムのソースコードに変換しないといけないという面倒くささにあり、条件3はもっとお手軽に使えるようにするというものだ。逆に私は、1の条件はそこまで強くはないのでは、と思っていて、PEGはカーゴカルト・パーシングを終わらせる有力候補なんじゃないかと思う。PEGでも表現力としては充分だし、使いやすいと思うんだよね。