# RubyKaigi 2023 参加記
RubyKaigi 2023 に二日目から参加しました。

処理系周りのセッションを主に聞いていたのですが，パーサー関連の話が多かったのと，二日目の夜に居酒屋で金子さんにパーサーの話を熱く語ってもらえたのが印象的だったので，Rubyのパーサーに関して書くことにします。

## Rubyのパーサー周りの動向
CRubyはbison (注: RubyKaigi二日目くらいに金子さんのlramaに置き換わった) というパーサージェネレーターでparse.yから生成したパーサーを使っていることが知られています。

CRubyのパーサーにはいくつか課題があることが知られていて，金子さんが開発しているlramaと，Shopify主導の Yet Another Ruby Parser(YARP)が最近は盛んに開発されているようです。
lramaとYARPの最大の違いは，lramaはbisonのようにパーサージェネレータを用いたLRパーサーを用い，YARPは手書きのrecursive descentパーサーを用いるという点です。

## CRubyパーサーの課題とlramaとYARPのアプローチの違い
二日目からの参加だったので初日の金子さんの発表はその場では聞けていなかったので，以下YARPの発表ベースの話になります。

今に至ってわざわざ新しいパーサーを書く動機としては，
- Portability
- Error tolerance
- Maintainability

あたりが挙げられていました。

Portabilityに関しては，CRubyのパーサーの移植性の不十分さ故に，JRubyやTruffleRubyといったCRuby以外のRuby処理系やパーサーライブラリは独自のパーサー実装を持っているという状態だったみたいです。
そうした処理系は独自のparse.yフォークを持って生成規則部分を書き換えることで対応しているものが多かったらしく，うまいことCRuby依存を除きつつupstreamの変更に追従するのはたしかに難しそうです。
YARPのセッションでは，ASTのSerializationも言及されていました。AST情報をJSON等の構造化形式データにしてプログラム間でやり取りしたりファイルシステムに保存できるようになると，フォーマッタといったASTベースのtoolingの発達に大きなプラスの影響を与えそうです。

Error toleranceとは単純に言うと，不正なソースコードに対して柔軟な対応をすることを意味します。
例えばパーサーが不正なソースコードに遭遇したときに不正な箇所で構文解析を中止するのではなく，適切なエラーメッセージを出力しつつ後続のコード中にある不正な部分を見つけられるように構文解析を継続することが現代の多くのコンパイラでは行われています。
Error toleranceは，irbのようなREPLや，エディタと処理系を連携させるのに用いるLanguage Server Protocol(LSP)関連の開発をする際に特に必要性が出てきます。
REPLやエディタでユーザーが入力しているコードは多くの場合は不正なソースコードの状態で，ユーザーは補完を要求したりします。こうした際に適切に不正なコードを処理しないと，適切な補完を出せなかったり，エディタでエラーがある箇所に適切にハイライトを出すことができなかったりします。
エディタの例に関しては，最終日のSoutaro MatsumotoさんのRBSのパースに関する話でも出てきていました。

不正なコードに遭遇した際にどういう動作をするべきかという問題はError recoveryと呼ばれ，Dragon Book(_Compilers: Principles, Techniques, and Tools_)といった比較的古めの本でも言及されています。

YARPのような手書きパーサーは，手書きなので細かい部分の調整がしやすく，それ故にerror toleranceの達成がしやすいという見方があります。
Error recoveryと一言に言っても複数の手法を組み合わせるのが普通なのですが，手書きパーサーだとPanic-Mode Recoveryという手法がよく使われています。
これは構文エラーが発生したら区切りの良さそうなところ(synchronizing token)までトークンをスキップするという方法です。

パーサージェネレーターを使う際の代表的なerror recovery戦略としてはError Productionという手法があります。
これは，よく踏まれる構文エラーにはそのエラーパターンを生成する生成規則をパーサーに追加し，その生成規則が適用されたら適切なエラーメッセージを出すというものです。
これはいわばユーザーのエラーを予測するようなもので，いくつも不正パターンを考えていてはキリがなくなってしまうしエンジニアリング的な観点からもrobustとは言い難くなることもあるでしょう。

この問題に関連して，Dragon Bookでは他にも，不正なソースコードを発見した場所で最小限の文字の挿入・削除を施すことでvalidなコードにするPhrase-Level Recoveryという手法も言及されています。
金子さんがlramaで実装しているのは [_Repairing Syntax Errors in LR Parsers_](https://idus.us.es/bitstream/handle/11441/65631/Repairing%20syntax%20errors.pdf) という論文を参考にしたものだそうで，方向性としてはPhrase-Level Recoveryに近いものがありそうです。

Maintainabilityに関してはYARPの発表中ではあまり言及がなかったように思います。デザインドキュメントにも，YARPにより保守性が大幅に向上すると考えているわけではないと述べられています。
ただデザインドキュメント中では，parse.yにコントリビュートしている人数が少ないことが言及されていて，parse.yの解説やコントリビュート方法への説明といったドキュメントが不足していることが問題視されています。
YARP作成を機会にパーサー周りのドキュメントやコントリビュートガイドを充実させて貢献しやすい環境を作り上げたいそうです。
bisonを用いるとbisonのDSLを学ぶ必要があるので，個人的にはこれが一つ大きい障壁となっている気はします。bisonに詳しくない個人としては手書きパーサーの方がデバッグしやすいし読みやすいので，バグを見つけたらissueを立てるだけでなくパッチを投げてみようかなと思えます。

一方で，lramaはbisonのDSLに拡張を加えてより柔軟で書きやすい記述を可能にすることで保守性の向上を図るようで，これは斬新な取り組みで興味深いです。
lramaの新しいDSLがbison等のパーサージェネレーターのコミュニティでどのような反応をされるのかに注目したいです。

パーサーの実装によるパフォーマンスの変化に関しては定性的なことは言えませんが，同日の _**JRuby Looking Forward**_ (Charles Oliver Nutter) セッションによると，JRubyではYARPを利用し始めてから`ruby -e 1`の起動にかかる時間が[20%高速化した](https://speakerdeck.com/headius/jruby-looking-forward?slide=46)らしいです。
lramaとYARPでパフォーマンス・メモリ使用量がどのくらい差が出るのかも追っていきたいと思っています。

YARP開発のモチベーションに関しては[YARPのデザインドキュメント](https://docs.google.com/document/d/1x74L_paTxS_h8_OtQjDoLVgxZP6Y96WOJ1LdLNb4BKM/edit#heading=h.6eyajfy04xhw)に詳細に述べられています。

### 終わりに
金子さんと話して，パーサーの理論的な部分もちゃんと勉強しようと思いました。
ちょうど大学の講義で構文解析が扱われてるので悪くないタイミングだったかなと思います。

執筆時点でYARPのレポジトリも[Ruby配下に移行された](https://github.com/ruby/yarp)ので，今後本格的にtrunkに取り込まれていくのでしょうか。
lramaとYARPでRubyのパーサー全体が大きな変化を迎えているので，今後の議論や進展も追っていきたいです。

パーサー以外にも，Splitting最適化やYJIT等のバックエンド寄りの話も多くて楽しかったです。
なにより，対面でRubyの処理系開発者何人かと話せたのがよかったです。

ピクシブ株式会社様の学生支援プログラムで参加させていただきました。
ピクシブさん、ありがとうございました！