正規表現のPrettier、パーサに取り組むために読んだ本、RubyKaigi 2023で面白かった発表。深掘りRubyKaigi 2023 with spikeolaf & makenowjust 文字起こしレポート vol.3

2023年6月15日に『深掘りRubyKaigi 2023 with spikeolaf & makenowjust』を開催しました。イベントの内容をほぼ全文文字起こし形式でお届けします。この記事は第3部です。 hey.connpass.com

登場人物

ゲスト

makenowjust/藤浪大弥さん
spikeolaf/金子雄一郎さん

STORES

fujimura/藤村大介
shyouhei/卜部昌平
hogelog/小室直

LramaとRaccの関係性

fujimura：ここからは質疑応答コーナーに入りますので、みなさん質問があればどしどしZoomもしくはTwitterにお寄せいただけるとありがたいです。

shyouhei：藤並さんも金子さんに質問があれば。

makenowjust：今Rubyの標準の周辺にあるパーサジェネレータとしてLramaとは別にRaccもあるじゃないですか。Lramaに今後いろんな機能が増えていったときに、同じ機能をRaccの方にもほしいとなって、RaccがLramaをバックエンドとして使うみたいな感じになっていくことはあるのか？ある意味Lramaに生成できるRubyを入れたり、そういうことは現状は考えてはないでしょうか？

spikeolaf：Raccとの関係という意味でひとつ考えているのは、Lramaのパーサ、つまりparse.yを読む部分に関しては今手書きの再帰下降なんですけれどRaccで置き換えたいと思っています。

makenowjust：なるほど。2つのジェネレータの実装が存在すると、メンテナンスしていくのがどこかでつらくなっていきそうだなという気がしていて、うまく統合できたらいいのかなって。

spikeolaf：なるほど。

makenowjust：未来の話だとは思うんですけど。

spikeolaf：わかりました。

shyouhei：Raccで書いたBisonのパーサの文法定義ってなかったっけ？20年くらい前に読んだ気がするよ。どこにも載ってないかな。あ、256本とかか。

spikeolaf：なるほど。

shyouhei：ちょっとうろ覚えだから自信はないけどどこかで見たような気もしなくもない。

spikeolaf：太古のRubyの歴史に詳しい人がいろいろ（コメントを）書いていて、なるほどなって思って読んでいます。

shyouhei：なんか読んだような気がするな。

spikeolaf：今、新しくスクラッチで自分で書くっていうのは楽しみだと思うので。

shyouhei：わかります。

spikeolaf：そうすると何が面白いかっていうと、Rubyのparse.yからparse.cに変換するところはLramaがやっているんだけど、そのLramaのパーサの部分はRaccがコンパイルで作ってる循環構造というか。ブートストラップ問題などは起きないんですけど、入れ子の構造になるので非常に面白いなと思います。

makenowjust：面白いですね。

fujimura：これかな。 docs.ruby-lang.org

shyouhei：これはRubyの文法ですよね。RubyじゃなくてBisonの文法をパースするってやつ。

spikeolaf：そういうの書くのはね、青木さんな気がするんだよな。

Rubyで他に手を出したいところ

fujimura：ちょっと毛色が違う質問なんですけど、今回パーサと正規表現っていうところだったんですけど、それ以外に実はここも手を出したいんだよねってところありますか？

makenowjust：なんだろう。僕自身はOSSにコントリビュートするのが好きで、昔はCrystalっていうプログラミング言語にコントリビュートしていたので、その時も広くやっていて、Crystalの中で一番コントリビュートしたのはフォーマッターの部分なんですけど、標準ライブラリのいろんなアルゴリズムも実装していました。なので、イシューを見てみてやれることがあったらやりたいなっていうぐらいで、積極的にやりたい領域があるわけじゃないんですけど。自分にできることがあったらやっていこう。バグ見つけたら報告して修正しようかなみたいなのはあったりします。

fujimura：ありがとうございます。金子さんはどうでしょうか？

spikeolaf：僕は手を出してみた結果思った以上にパーサとパーサジェネレータの世界が広かったので、しばらくはこの辺りを散策するだろうなって思っています。っていうのはパーサジェネレータ側でエラートレーランス機能を入れるときに、より内部なCの実装になってるんですけれど、アルゴリズム的にはもっといいものもありますし、あとは内部的なデータ構造としてもっとコンパクトに持てるんじゃないか。持てるっていう論文があるんですけれど。あとパーサジェネレータの吐くパーサの実装っていうのは今はナイーブなテーブルを使ったプシュダウンオートマトンなんですけど、これもよりコンパクトにする実装があり得ると思っていて、でここ一つだけで割といろんなやらなくちゃいけないことやいろんなテーマがあるので、そういう意味ではしばらくここにいると思います。

fujimura：なるほどな。

正規表現のPrettier

shyouhei：さっきフォーマッターの話があったけど、Rubyっていうプログラムのフォーマッターは今すごい難しい。parseが難しいから難しいという話でアプリケーションとしてはひとつあり得ると思うんだが、正規表現もできるっちゃできますよね。等価な形を変えることでもうちょっときれいにするみたいな、そういうのって考えられたりしないですか?

fujimura：正規表現のPrettierみたいなやつですね。

makenowjust：これはもう完全に研究のトピックとしてやりたいことなんですけど、正規表現をReDoSが起こらないような、なるべく等価な形に変換するってことをやりたいなって考えてます。結局ReDoSが起こらないような正規表現の方が基本的にはシンプルっていうか、重複する部分をうまくひとつにまとめた形になるので、シンプルになるはずだし、そういう意味ではprettier的な概念になるのかなと思いつつ、まだあまり手を出せていないのでわからないなと思ってます。

shyouhei：できれば楽しそうですよね。

makenowjust：はい。

spikeolaf：それとは今すでに解かれている問題は当然ないし、一方でとても無理な話でもないぐらいの間に落ちそうな感じではあるんですか?

makenowjust：一応先行研究自体はあるにはあって、ただそれがいろんな正規表現に対してできるわけではなかったりとか、自分が論文を見てみた感じまだ改良できそうだなっていうのは思ったり。

shyouhei：オートマトン自体の等価性判定というのは実際意外に難しいので、そういう方向にいっちゃうと多分つらいんですけどっていう感じですね。

fujimura：もうちょっと柔らかい方法があるって感じなんですかね？オートマトンの等価性じゃないような。

shyouhei：とある入力に対して最適なものが出るのを保証しますっていうのは多分無理なんですけど、そうじゃなくても分かるところだけでもやると効果あるよねって話だと思うんで。

fujimura：確かにな。

makenowjust：そんな感じですね。一応先行研究で最適なのを出すのはNP完全みたいなのとか、ちゃんと出してる系がやってましたね。結構面白くて、正規表現の中に任意の正規表現が入る穴みたいなものを作って、そこに入るものをSAT ソルバーで計算する、うまくいくまで穴を広げていくみたいな方法で先行研究はやってましたね。自分もそういう方向でうまくやってきました。

spikeolaf：ReDoSみたいなものを何と言うかちょっとわからないんですけど、SAT ソルバーが作った結果の評価はどういう軸で行われてるんですか？より良いというのは計算が軽く済むような評価値を与えなくちゃいけないじゃないですか。どういう評価値になるんですか？

makenowjust：SAT ソルバーで条件式を書くんですけど、待ち時間が爆発しないということを保障するような条件式にします。

spikeolaf：当たって見つかればそれは良いという感じなんですね。

makenowjust：当たるまで良い感じに、いい感じの穴を探していくっていう。

spikeolaf：穴を探す部分がわりとしらみつぶしというか力のないやしと。

makenowjust：だったりとか、待ちが線形かどうかという条件がいまいちなんじゃないかなと僕は先行研究を見て思っていて。

spikeolaf：それは言える範囲でいいんですけど、どういう風に？もうちょっと緩めた方がいい？強めた方がいい？

makenowjust：もうちょっと強められるんじゃないかな。強いと緩めるの方向性の表現が難しいんですけど、もう少し詳細な条件にできるんじゃないかな。ただそうするとなかなか当てはまるのが出なくて、結局時間がかかってしまうとかになるかもしれない。ただ現状だと正規表現を直しすぎちゃうんじゃないかなって自分は思っていて。

実験で使う言語はScala

spikeolaf：そういう正規表現系の研究をされたりするときに実際に手元で実験のためにプログラムを書くと思うんですけど、そういう時はどういう言語を使うことが多いんですか？

makenowjust：僕はそういう実験やオートマトンをいろいろ書くときはScalaを使っていることが多いです。論文に書いてあることって数学的な表記が多いので関数型言語がうれしいけど、アルゴリズムはアルゴリズムとして結構動的な構造として書かれているので。

shyouhei：よくある論文のコードだよね。

makenowjust：そういうのを落とし込むときには手続き型に書けた方がうれしいので、Scalaはバランスがいいなと個人的に思って使っています。

spikeolaf：Scalaのバランスの良さをそういう側面で語られたのを僕は初めて聞いた。

makenowjust：Scalaを作っているのは研究者のグループだと思うので、意外とそういうところを意識しているんじゃないかなと個人的には思っているけど、どうかな。

shyouhei：去年も思いましたけど、この深掘りイベントはRubyじゃない話を豊富にやりますね。

Rubyでプリティプリンタをやると大変なの？

fujimura：今それ聞いてと思ったんですけど、一つの出力にあるフォーマッターがある言語ってありがたいなって思いながらPrettierとかGoを使っているんですけど、Rubyでそれをやるのって、過去この話はいろんなところでされてきたかと思うんですけど、改めてここにいる皆さんがもしかしたら知見あるかもなと思って聞くんですけど、Rubyでそれをやる。いわゆるプリティプリンタみたいなのをやろうとすると大変だったりするんですかね？

makenowjust：Rubyのフォーマッターでrufoってあると思うんですけどご存知でしょうか？あれってCrystalのコンパイラを作っている人が作っているんですけど、なのでCrystalの内部にあるフォーマッターと基本の構造は同じみたいな感じになっています。作ろうと思えば作れるんですけど、ASTと実際のソースコードの中に離れている部分があって、なのでrufoだとどうかわからないんですけど、Crystalのフォーマッターだと1回パースした後にパースしたASTと同時にレキサーを並列に動かしてフォーマットしていく方法を取っています。

spikeolaf：CST、Concrete Syntax Treeではなくてもう一回レキサーを同時に動かす。どちらかというとIRBの中に近いような感じの挙動なのかな？

makenowjust：はい。

spikeolaf：そういうことなんだ。

makenowjust：みたいなやり方をしていて、多分rufoもそれに近いやり方をしているはずです。

spikeolaf：ちょうどフォーマッターの話になったので脱線させちゃうんですけど、トークン情報とASTをどういうふうに持っておくとみなさんが都合がいいかって僕まだ分かってなくて。おっしゃるとおり、フォーマッターだと多分具体的な元の入力の情報って、セミコロンとか含めて1個も落としてほしくないじゃないですか。

shyouhei：あるいはコメントとかね。

spikeolaf：そういったのをどういうインタフェースで統合的に扱わない、どういうのが優れている他言語のこのライブラリ、他言語のこういう仕様はよかったみたいなのがあったら教えてほしいなっていうふうに思っているのでちょっと宣伝させてもらいました。

shyouhei：わからないね、難しいですね。僕も昔Rubyのコードの中に挟まっているコメントの中に矢印で 1+1 # => 2とか書くじゃないですか。ああいうのって本当にあってるのかを検証したくなってRubyのコードの中に挟まっているコメントを抜き出して検証して戻すみたいなプログラム書いたんですけど。

fujimura：Pythonでありますよね？

shyouhei：そうそうPythonでもある感じですね。(編集注：doctestでした)。RubyにはRipperっていうRuby自身のパーサがRubyで使えるやつがあるんで、これを使えば楽勝やろうと思って作ってみたら超大変だったっていう話があって。やっぱりASTだけではこぼれてくる情報があるんですよね、その辺をどういうふうに持ち回ればいいのかなっていうのはやっぱり僕も正解がなくてちょっと悩んだところでしたね、すごい難しい感じですね。

makenoejust：そういうあたりってJavaScript周辺がエコシステム発達してるんじゃないかなという期待があるけれど、わからないな。正直詳しくはないですね。

shyouhei：JavaScriptだとsource map持っとけって話ですよね。

fujimura：ああsource mapがあるのか。はい、難しいなってことがわかりましたね。

パーサに取り組むために読んだ本は？

fujimura：金子さんに他にどんなことをやってみたいですかという質問からこうなったんですね。

spikeolaf：僕は引き続きパーサとパーサジェネレータ。パーサとパーサジェネレータって並べて言ってますけど両方をやっている人ってそんなにいないのかなって最近ちょっと思ってて、ANTLRの人たちが言語のパーサ側を書いてるかっていうとあんまり。僕の知っている範囲ではないので、両方やっていると面白いし大変です。

fujimura：パーサとその周辺をやるにあたってどんな本を読みましたか？

spikeolaf：これは賛否両論わかれると思うんですけど、ドラゴンブック（編集注：『コンパイラ―原理・技法・ツール』）は日本語でアクセスできる情報源としては、翻訳が古かったり難しい読みにくい部分もあるんですけれど、特に前半半分を読んでました。それとは別に大堀先生かなんかが書かれている結局LRパーサと何なのかっていうコラムみたいな記事が一個あってそれは結構最近読んでようやくLRパーサの気持ちがわかったなって。LRパーサのステートとしてのっているものは何か、あれは有限オートマトンなんだよっていうその一言の説明がすごく身に染みて最近落ちましたね。あとは結構Bisonのレファレンスマニュアルとかそういうのいろいろ書いてあるので、それは読んだりしてます。

fujimura：ありがとうございます。

shyouhei：Bisonの実装は読まなかったんですか？

spikeolaf：一通りは読みました。

shyouhei：しんどかったとか簡単だったとか。読んでみた結果自分がこれに手を入れるのはないなって思った？

spikeolaf：Bisonは僕のものじゃないんですけど、管理しているのは別だし、あれに機能をどんどん入れてもらうのは難しいし、あとBisonってみなさんの環境で違うバージョンなのがきつくて。Bisonを読んでてきつかったのはテンプレートファイルがm4で書かれてるんですよね。m4を僕は読めなかったんできつかったですね。

shyouhei：昔ながらのプログラムだからね。

spikeolaf：config.ac以外でm4って見るんだなって思って。

shyouhei：C++とかが生まれるよりも前から使われているので。

spikeolaf：前より引き継がれている謎の。

shyouhei：大変ですね。

RubyKaigi 2023で面白かった発表

fujimura：ちょっと全然違う質問をすると、RubyKaigiで自分の発表以外でこれは面白かったなという感想を聞いてみたいです。

makenowjust：自分が面白いと思ったのはTruffleRubyの最適化の話。何てタイトルだったっけ、Stringの話じゃなくて型でJIT コンパイルの分岐をしてみたいな話。そういうコンパイルの仕方自体はCrystalにコントリビュートした時に見たことがあるなって思ったんですけど、歴史的にこれまでそういった研究がいろいろされていたんだなみたいな話も踏まえられていてすごい学びのある話だったなと思っています。あとそういう最適化がRubyでちゃんと動くんだなっていう、そのあたりをしっかりやっているのがすごいなって思った記憶があります。何てタイトルだったんだろう。(編集注：『Splitting: the Crucial Optimization for Ruby Block』でした)

spikeolaf：僕ちょっといろいろ発表とかLTとかBisonを倒すとかいろいろあって、あんまり発表は全部ちゃんと見れてなかったんですけれど。現地で見た中ではまつもとさんのキーノートが今年は面白かったなって思っていて。うまく説明できないんですけれど、上から目線みたいになりますが、Rubyはこの後発展するっていう話をまつもとさんが自信を持って言ってたなって。そういうオーラがわりと伝わってきたのが僕はすごく楽しかったですね。

fujimura：あれはそうですよね。結果というか実績も重ねられるとすごいですね。

spikeolaf：結局Ruby3.3x3というか3の先ってまだ道を模索している、キーワードがまだ揃ってないって思ってるんですけれど、そういうところに対してもまつもとさんは前のめりだなって例年よりも今年は強く感じましたね。

Rubyに対する要望

fujimura：みんなが同意するわけではないが、Rubyはこうなってほしいというのがあればお二人に聞いてみたいです。これは入らないだろうけど自分はこうなっててほしいみたいな。例えば2日目の夜とかにモリスさん*1とかと話してたら、モジュールシステムはなんとかならんのかみたいな話をしていて。そうよねみたいなところもあったなと思って、みんなそれぞれに思うところが実はあるのではないかと思って聞いてみました。

spikeolaf：卜部さんは何かありますか？

shyouhei：バグが少なくなるプログラムが良いプログラムだと思っていて、特にRubyってあまり速さを求める方向性じゃないじゃないですか。現代のプログラミング言語って人類の不可能に挑むという方向性もありつつ、もうひとつはプログラムに誤りがないようにしながら、自分がやりたいことができていくっていう方向があると思っていて。多分Rubyはやりたいことができる寄りだと思うんですよ。例えば正規表現をふと書いた時にそれがReDoSになっちゃうっていうのがありがちだから、パラパラと見つかって社会的な問題になりかけたわけなんだけど、そういうのを未然に防いでいくっていうのはRubyの方向性としては正しいと思うんですよね。入らないけどっていう意味で言うと入らないだと難しいな、ユーザーがふと書いたものがふと正しく動くっていう方向に行ってほしい。速いよりも、と思ってますね。

fujimura：産業界の生産性アップみたいなところで言うと、速いのもそうだが、正しく動くこともだいぶインパクトがありますよね。

shyouhei：そうですね。難しくて。正しく書かないと正しく動かないんだぞみたいな方向もあると思うんで、それはやっぱり役割分担だと思うんですよ。

makenowjust：それだったらさっき話してた 1 + 1 => 2 みたいなそういう簡単にテストできる仕組みみたいなのをRubyの標準じゃないけど近いところに入ってて、気軽にできる仕組みがあると嬉しいんじゃないかなというのは。

shyouhei：ぜひぜひほしいですね。

fujimura：同じファイルに書きたいなと思うときもありますね。

shyouhei：そうですね。例えばRustやNode.jsだと、組込みのテストランナーがあって、1つのファイルの中にテストを書くと勝手に実行してくれるみたいになりつつありますよね。そんな感じのものがRubyにもあってもいいかもしれないですね。みなさん、どうですか？何か欲しいのとか。

makenowjust：正直に言うと、Rubyでそんなにプログラムを書いてないっていう。

一同：（笑）

shyouhei：CrystalにはあるけどRubyにはないぜみたいなもの、その逆とか。そんなないか、CrystalはだいたいRubyと同じ感じだから。

makenowjust：そうですね。昔Crystalがよかったのはブロックの省略機構みたいな感じで、&シンボルでto_proc呼び出すのがRubyだとあるんですけど、あれがCrystalだと&.メソッド名みたいな感じ。そこからメソッドチェーンが書けたり、引数が渡せたりみたいな書き方ができて当時は便利だなって思ったんですけど、今Rubyって匿名パラメータがあって便利になっていってるから別にそれでいいんじゃないかなという気もしていて。

shyouhei：あるいはScalaにあって便利なものとか?

makenowjust：Scalaにこれがあって便利なものは多分RubyにあってもRubyっぽくないだけな気がしていて。

shyouhei：なるほど。

makenowjust：でも個人的にあったらいいなと思うのは、Scalaってパターンマッチングのエクストラクターを自由に書けるんですけど、正規表現をパターンマッチングのパターンの部分に書くことができて、正規表現にマッチして、マッチした時にキャプチャーだったりとかネームドキャプチャーの内容を取り出せるみたいなパターンマッチの内容として。そういうのをRubyでも書けるような仕組みがあったらいいなというのは。

shyouhei：今まさに金子さんが嫌だって言ってたと思う。

spikeolaf：みなさんはそういう欲望を持ってていいなって思っただけです。

makenowjust：別にそれはパーサとかに影響する部分ではない。

spikeolaf：ローカル変数を束縛しちゃダメだからダメだと思いますよ。

makenowjust：いや、何て言うか別に今あるものの、今クラス名が来るところとかに正規表現のパターンが来て角格好みたいなのが来てその後に変数名が来てそれがキャプチャーの内容になるみたいな。

spikeolaf：今と同じ仕組みだと思ったんですけど、今と同じ複雑さだと思いました。

makenowjust：まあ、はい。ぐらいですかね。あったら面白いなって思うだけで、自分がすごく使いたいかというとそうでもない気がする。

fujimura：金子さんは作る側の苦労みたいなのが。

spikeolaf：いや、そういうのはあんまり考えないようにしてますけれど、割と今出ている話で僕が面白いっていうか、なんとかうまく入れられないかなって言っているのの一つはLINQですね。C#にある機能かなあれは。実用としては、今トレジャーデータって会社にいるので、SQLをある程度テンプレート化して地の文で書くっていうのはそれなりにやるんですよ。その時に毎回リテラルとかのエスケープとかを頭で意識しながら、ここはユーザー入力値だからちゃんとエスケープしなくちゃいけないとか、ここがセレクトの後ろだからちゃんとカラム名としてエスケープしなくちゃいけないみたいなことを毎回レビューしたりとか大変なので、その辺を全部抽象化してくれるようなレイヤーが一番挟まると嬉しいなっていうのはすごくスピシフィックに僕はあります。

shyouhei：JSXみたいな感じですね。

spikeolaf：という言い方もあります。それは構文的にもチャレンジングな部分があるので、そういうのをどういうふうにつなぎ込んでいくかっていうのは興味があるのと、あと入ってほしいというのはここは維持してほしいなっていうのはさっきも言ったRubyって人間がぱっと見た時に迷わず読めるけど、よく考えると不思議なものが結構あるんですよ。っていうのが何なのかが僕はまだちょっとわかってない、言語化ができてないので、そういうのは今後も大事にしてほしいなって思ってます。

fujimura：そうなんですよね。他の言語から戻ってくるとあれ？みたいな。何だかよくわからないけど何とかなっているみたいな感覚は不思議ですよね。

Rubyの実装を読んでみよう

fujimura：hogelogさんはどうですか？

hogelog：ちょっと話をずらしちゃってるかもしれないですけど、藤浪さんと金子さんは言語処理系の中のフロントエンドに興味が強い人だなって思って。僕はつい言語処理系の中を見ているとバックエンドの方が面白く見えてきてしまって、速くなるとかが単純に楽しいみたいなところがあります。速さはそんなに重要じゃないのではという話もあったような気がしますが、速いとなんか楽しくて数字が出るから面白いんですよね。っていうところで、普通にJIT コンパイラの改善が積み重ねられていっているところとか、そこら辺を見ていくのは非常に楽しい。まだ自分は全然貢献できてないですが。

shyouhei：楽しいですよ。Rubyのプログラムを解釈した後、実行するまでの間にRubyのプログラムを実行できる形に変換するところがあるんですけど、手書きの何千行もあるひとつの関数で行われていて大変感動するので、みなさん実装を読んでみるといいと思います。あそこは結構楽しくて、parseは一瞬で終わるけどそこからコンパイルするのが何分もかかるみたいなプログラムとか書けるんですよね。

spikeolaf：へぇー、全体は短いってことですね。

shyouhei：短いんだけどコンパイルするとiseqが爆発しちゃってみたいなのとか書けるんですよね。まだまだやれることがたくさんあるな、楽しそうだなと思います。

Rubyのプログラムのソースコードを落としてきて解析するとすごい大きい関数がいくつかあって、一番大きいのはparse.yが自動生成するファイルですけど、2番目くらいが正規表現エンジンの正規表現ループで、その次がcompile.cのコンパイラですね。すごい大きいかつ手書きなので夢がある。いじってみると楽しいと思います。

spikeolaf：「defined?だっけ」って聞いてますけど、あってますか？

shyouhei：そうそうそう、defined?のところですね。

spikeolaf：defined?もエグいタイプの文法だなって思ってます。

fujimura：どこら辺が？

spikeolaf：あれも後ろにいろいろ書けるんですよね。思ったよりいろんなものが書ける。そんなものは普段書かないんだけどっていうのが書けちゃうので面白いなって思ってますけど。

fujimura：そろそろクロージングへお願いしますという指示があったので、クロージングに入ろうと思います。ちょっとだけ宣伝をさせてもらいますと STORES はRubyでいろんな事業をしている方の役に立つソフトウェアを作るっていう楽しい仕事をしてますのでよかったらぜひお声がけいただければ嬉しいです。

ということで深掘りRubyKaigiをちょうど1ヶ月後くらいにやれたのは個人的には嬉しかった。松本のことを思い出しながらウオーってなりながら1ヶ月勉強するのが楽しい時間だったんですけども、終わりの時間になりましたね。改めて藤浪さんと金子さん、今日はありがとうございました。

makenowjust/spikeolaf：ありがとうございました。

fujimura：以上で深掘りRubyKaigi 2023を終わります。お疲れさまでした。（完）