ピクシブ 株式会社様の学生支援企画でRubyKaigi2025に参加しました。
この記事では、自分が特に気になったセッションについて復習を兼ねつつ紹介します。
私の理解が間違っていたらごめんなさい。訂正・補足などあればコメントやTwitter (@kat0h)で教えてくださると幸いです。
inside.pixiv.blog
自己紹介
day-n
大学でコミッタの斎藤さんと集まり、昨年のRubyKaigiのセッションを観る会をしました。
私は言語処理系が好きなので、RubyKaigiではその周辺を勉強したいなと考えていました。
Ruby 本体のセッションの中でも、特にパーサーの話は事前知識がないとついていけないなと感じたので、私のリクエス トでパーサーの発表を（解説してもらいながら）見ました。
下記は見たセッションの一覧です。
rubykaigi.org
rubykaigi.org
rubykaigi.org
特に金子さんの発表のインパク トがすごかったです。３０分の発表だったのですが、あまりにも話すのが早いかつ濃厚で、途中でとめつつああでもないこうでもないと見ていたら２時間が経ってしまいました。まじかよ
LR(1)/LALR(1)/IELR(1)/PSLR(1)などの関係をある程度整理してから会場に行けたのはよかったです。
day0
水曜日の夜に自宅のある調布から羽田を経由して飛行機で松山に行きました。ANA の飛行機に乗るのは幼稚園以来。孤独のグルメ が放送されていました。
松山には２１時ごろに到着。お昼ならRubyKaigiの運営さんがチャーターしたバスがあったらしいが、当然夜にあるわけもなく空港の外に停まっていたリムジンバスに乗車。
実のところ、この時点で泊まるホテルの場所を知らなかったので必死に調べながらバスに乗っていました。結局途中の停留所で降りればホテルに行けることがわかったので、新聞社の前で降りて1kmほど歩いてホテルに到着。
０日目の夜はコンビニ飯かなぁと考えていたのですが、SmartHRさんのdrinkupを終えた斎藤さんとちーすけさんにお誘いいただき一緒にご飯をいただきました。
毎度お二方にはめちゃめちゃお世話になっています。
tech.smarthr.jp
大街道のアーケードにRubyKaigiの横断幕を見つけたりもしました。
そんなこんなでday0は日付が変わる頃に就寝。
day1
朝７時頃に起床。朝食付きの部屋を取ってくださってたので、朝ごはんを食べに行きました。
家から大学まで５分の生活に慣れきってしまっていたので、けっこうきついです。
夜まで集中してセッションを聴き通すためにがんばってご飯を食べました。
会場の愛媛県 文化会館まではホテルから徒歩で20分くらいでした。実は路面電車 にのればもう少し時間を短縮できたらしいのですが、地理が頭に入っておらず乗れませんでした。
Ruby Taught Me About Encoding Under the Hood (ima1zumiさん) speakerdeck.com
文字コード と人生の話でした。
👨👩👧👧←この絵文字をirb に食わせたところ、irb がクラッシュしたという出来事をきっかけにコミッタにまで就任したそうです。尊敬しかない。
私自身も、高校の頃はVim にパッチを送るなどちょいちょいOSS にかかわってはいたのですが、継続することがなかなかできていませんでした。
「のめり込むようになってしまいました」という発言心に残っています。本当に楽しそうに発表されていてとてもよかったです。
Make Parsers Compatible Using Automata Learning (makenowjustさん)
個人的にたのしみにしていたセッションその１
speakerdeck.com
現在のCRubyのデフォルトのパーサーであるPrismと、Lramaで生成されるparse.yによるパーサーの挙動の違いを形式的に検証しようという発表です。
２つの異なるパーサーPlとPpが同じ挙動をするかは、パーサーは記号列を入力に取るオートマトン と考えると、L(Pl)=L(Pp)であることを示せばよいことになります。（発表ではL(Pl⊕Po)=∅かどうかを検証していました）
（DFA 同士が等価かどうかはそれぞれを最小化することで判定できると思うのですが、プッシュダウンオートマトン だとまた違うのかも、もしくはXORを取れば反例の入力文字列を（比較的）容易に生成できるという事情もあるのかもしれない）
2025/05/06追記オートマトン の等価判定についての補足をいただきました。
そもそも発表で扱っていたのはVisibly Pushdown Automataだったので、そもそも違うものでした。
なぜVPAにしたのか（うっかり聞き逃してしまったんだと思います）気になります。発表動画が公開されたら改めてみてみます。
追記終わり
2025/05/15
Pixivのアフターイベントで追加の情報をお聞きしました。
VPAを使ったのは、L*アルゴリズム が適用できる中では一番強いオートマトン だったから
オートマトン 同士の比較なら普通に比較しても良いけど（別にandだろうが=だろうがxorだろうがやれることは同じ）、xorなら反例を生成しやすいというのはメリットではあるとのことでした。
追記終わり
Lramaの生成するパーサーに関しては、parse.yを見ればどのような状態集合と遷移規則を持つオートマトン ができるかがわかります。
しかし、Prismパーサーは手書きの再帰 下降パーサー(prattパーサー)であり、レキサー を内包します。
（下に示した４つ目の記事によるとRuby の文法は文脈依存文法らしいのですが、この文脈の解析をレキサー に投げることでparse.yの文法はLALR(1)に収まっています）
ここからパーサーのオートマトン を生成することはかなりの困難を抱えると予想できるはずです。
そこで、この発表では入力と受理するかどうかしかわからないブラックボックス のオートマトン であるLramaとPrismに対してオートマトン 学習（L*アルゴリズム ）という手法を利用することで互換性を検証したそうです。
私は昨年度大学で形式言語 理論の講義を受けました。現代のプログラミングがこの理論の上に成り立っているというのは言わずもがな、、というのはわかるのですが、ここまで応用的に利用できるというのは非常に驚きました。
L*アルゴリズム によるオートマトン 学習でパーサーのオートマトン を推測するには、O(kn2 ) (kは|Σ|、nは状態数)のコストがかかるそうで、Ruby 全体の文法を対象に検証するのは現実的でないそうです。
実際、発表でもオートマトン 学習に利用するアルファベットはΣ={"a", :, (, )}に限定していました。こうでもしないと計算量が大きすぎるようで、prism全部のオートマトン を生成するといったことは難しそうです。(アルゴリズム が対応できる言語クラスにRuby が属さないので、一部だけを対象にする必要があるという事情もあるはず)
この発表を聞いて仕様書の気持ちになれるプロだけが発見できるものだった互換バグが、ついに誰でも見つけられるようになったのか！！とワクワクしました。
後にお聞きしたのですが、入力にするアルファベットの選定はかなり大変だったそうで、どんな文法ならバグりそうかな〜などの見立てを立てて入力を考えるのはやはりプロしかできないようです。無念....
まったくついていけなかったのですが、自分がいま大学でしている勉強は役に立つんだという実感が得られてとても良かったです。
L*について説明してみる | makenowjust-labs/blog Operator-precedence parser - Wikipedia Prism：エラートレラントな、まったく新しいRubyパーサ | gihyo.jp Rubyパーサーを一新するprism（旧YARP）プロジェクトの全容と将来（翻訳）｜TechRacho by BPS株式会社
(Continuation is to be continued)
個人的に聞きたかったのですが、被っていて聞けなかったセッションです。Scheme の（超小さいサブセットの）インタプリタ にcall/ccを実装してから、call/ccという非常に強力な言語機能に心を奪われていました。
発表スライドが公開されていることをydah_さんに教えていただいたので、後で読みたいと思っています。動画の公開が楽しみです。
speakerdeck.com
昼ごはん
お昼ごはんはPixivさんとSMSさんの学生支援企画で来た学生であつまって鯛めしをご馳走になりました。
午前聞いたセッションの感想を話し合ったり、いまやっていることの話を聞いたり楽しい時間を過ごすことができました。SMSさんの学生支援で来た方とは初対面だったので、ゆっくりお話をする機会をいただけて大変ありがたかったです。
愛媛には、炊き込みご飯風の松山鯛めしと刺し身と卵黄を一緒にいただく宇和島 鯛めしがあるそうです。今回伺ったお店では、両方の鯛めしを食べ比べることができました。
Ruby 's Line Breaks speakerdeck.com
個人的にたのしみにしていたセッションその２
Ruby の複雑怪奇な改行の仕様を明らかにしようという発表です。
Ruby のプログラミムにはおおまかに下記のような改行に関する規則があります。
スライドでは、このルールの（よく知られている）例外をいくつか解説していました。
Ruby の文法はPrismもしくは、parse.yでパースされているはずなので、この例外を探すのはパーサーの実装から形式的に探索できそうです。
今回の発表では、Ruby のparse.yを解析することでこのような例外を見つけ出す方法を提案していました。
そもそも、なぜRuby のparse.yというのはここまで恐れられる存在なのでしょうか。
前提として、多くの古典的なプログラミング言語 はその構文解析 器にyacc /lexやbison/flex から生成されたパーサーを使っています。これらが受理する構文は多少の差があれども、大抵はLR(1)（=CFG）やLALR(1)の文法に収まっているのが普通です。
しかし、多くのプログラミング言語 の構文規則はCFG（文脈自由文法）の中に収まっていないことがあります。パーサーはCFGを受理できる能力しか持っていないわけなので、CFGからはみ出た規則はどうやって処理されるかというとレキサー で吸収されているようです。（lex_stateの話ですね）
つまり、yylex関数はRuby がCFGに収まるようにがんばる関数であるということで、複雑なのも頷けます。
改行に関しても、レキサー は文脈に応じて返す結果を出し分けています。
文法的に改行可能なところ（終わっている式の後など）なところに来た改行文字列は'\n'の終端記号として返し、逆にまだ式の途中にいることがわかる(1+ \n 2)のような状態では改行を読み飛ばします。
レキサー とパーサーの結合は疎にできているので、それぞれが個別に解析中の状態を保持します。
このような非常に複雑な状態を整理して理解可能にするために、発表ではパーサーとレキサー のオートマトン を合成するということをしていました。
こうして、レキサー は改行を読み飛ばす状態に入っているのにパーサーは還元のために改行文字が入ることを想定している(lookaheadsetに\nがいる)状態や、逆にシフトのために改行文字を受け付けるのにレキサー が\nを読み飛ばす状態などを発見できたそうです。
makenowjustさんの発表でも感じたのですが、カオスに立ち向かうために理論を活用して、成果を上げていることにとても感動しました。自分がまだまだまったくコンピュータを知らないことを痛感しましたが、大学で勉強したことを上手に現実に持ち込むとこんなにも楽しいことができるのかとわかりました。
30分の発表だったのですが、面白すぎて体感では15分くらいで終わってしまったような気がします。
本屋さん
ホワイエ二階の一角で本屋さんが開催されていました。mame さんの「型システムのしくみ」を購入しました。ちょうどmame さんが近くにいて、直筆サイン（！）を頂いてしまいました！超嬉しい！！
早速実行....
SyntaxError!!
プログラムの写し間違いでした。
下2行はコメントなんだろうな...とみせかけて!で文字列を閉じているという、ミスリーディングなコードでした。
サインまでQuine...恐ろしい...
TRICK 2025: Episode Igithub.com
私がRuby を使い始めたきっかけはmame さんの書いたQuineでした。2022年のTRICK は高校の帰り道に電車で見ていました。今年のRubyKaigiでは会場で見ることができて感無量です。
できたらTrick に作品を応募したかったのですが、今の私の技術力・アイデア ではできませんでした。
どの作品も、クリエイティブかつ高い技術で実装されていて尊敬です。
omoikaneさんのだるまのコードは、本当に仕組みがわからなくて怖かったです。解説markdown にアスキーアート 生成用のHTMLジェネレータが記載されていたのですが、あれを見る限り職人の手作業でコードが記述されているような気がします。何を食ったらあんな芸術的なコードが書けるのでしょう....
ところで、、Episode 1というのは何なんでしょう...
day2
Dissecting and Reconstructing Ruby Syntactic Structures
個人的にたのしみにしていたセッションその３
speakerdeck.com
Ruby の文法の全体像を把握しつつ、parse.yをより良くしようという発表でした。
いいなと思ったのが、Perl /PHP /Ruby の構文（特に式まわり）の特徴をつかむために、lramaへの入力から構文図式を生成するツールを作ったという話でした。LTで詳しく話されていました。全体像をなんとなくつかむのにはとても便利そうです。
前にawk のパーサーを書いたときに感じたのですが、やはり式の構文を把握するというのはかなり大変な作業だと思います。Ruby も例にもれず、引数にかけるargとprimaryが分かれているなど他の部分と衝突しないために構文規則が分かれています。
理解が難しい文法の例として、カンマで区切られたリストのような規則をBNF で表現しようとすると、下のようになります。
rule1 := rule2
| rule2 ',' rule1
rule2 := 'e'
自然言語 で表現すれば「カンマ区切りのe」と表現できるのに、BNF がプリミティブな記法を持たないためにこのような記述をしなければなりません。
ただでさえ難しい文法の読解をより難しくしてしまいそうです。
上の例は本当に簡単な文法ですが、それなりに長く複雑な文法のBNF を読む際、再帰 的な記述から構造の本質をサッと読み取るのは大変です。
もちろん、CFGを処理する機械が扱えるのは再帰 的な構造なので、「n個の連続」のような記法は糖衣構文の一種になりますが、このような記述が書けるというのはすごく便利だと思いました。
また、同じ形・意味を持っているが違う構文規則の場所で記述されている規則をジェネリクス のようにまとめて扱えるようにするというアイデア は面白いなと感じました。
parse.yが整理されてRuby の文法の本質的な難しさに集中できるようになる日が楽しみです。
ZJIT: Building a Next Generation Ruby JIT
Ruby の新しいJIT の紹介のセッションです。
ShopifyがYJITを作った結局としてパフォーマンスが頭打ちになってしまったので、先２０年のメンテナンスを見込んで新しく設計をやり直したという話でした。
これまでのYJITはYARV のバイトコード インタプリタ をベースにJIT を組んでいたのに対して、ZJITは教科書的な設計のmethod-basedなJIT だそうです。Prismのようなものを見ていると、Shopifyの方がこのような昔ながらの設計をすることに驚きがありました。
Ruby が YJIT でなんで速くなるのか？ Lazy Basic Block Versioning をサクッと理解してみた - estie inside blog
The Implementations of Advanced LR Parser Algorithm
個人的にたのしみにしていたセッションその４
speakerdeck.com
Lramaに新しく実装したIELRという状態表生成アルゴリズム の紹介です。
Lramaの最終的な目標として、parse.yを読みやすくすることがありました。そのために注目しているのがPSLR(1)という方法で、これを使うとスキャナー（レキサー ）を使わずにパースができるそうです。（厳密な定義をまだ理解できていないです,,,）Ruby にこれを導入する嬉しさとして、パーサーとレキサー が構文解析 の状態を共有することで設計が簡潔になるとされています。
cf:
speakerdeck.com
https://open.clemson.edu/cgi/viewcontent.cgi?article=1519&context=all_dissertations
PSLR(1)はIELR(1)の発展形として実装されているので、まずはIELR(1)を実装する必要があるということでLramaにIELR(1)を実装したそうです。
IELR(1)を考える前にLR(1)から考えてみることにします。
簡単な文法
例として、上のような文法からLR(1)（スライドではCanonical LRと表現されていました）の正準オートマトン （≒パーサーの状態）を求めてみると、状態数は22個になってしまいました。
規則が数個しかない文法ですら、こんなにも多くなってしまうのですからより複雑な文法だともっとひどいことになるのは容易に予想できます。
speakerdeck.com JSON パーサーを書いた結果状態数がえらいことになっている
そこで考え出されたのが、LR(1)項の核が共通していて先読み記号のみ異なる規則を一つにまとめてしまうLALR(1)です。
LALR(1)はLR(1)よりも弱いですが、follow集合をつかうSLR(1)と同じ状態数でSLR(1)よりも広い（十分に実用的な）文法をパースできるということで広く使われています。
LALR(1)は十分に広い範囲をパースできるのですが、状態数の削減の過程でMysterious Conflictという現象が発生してしまうことがあります。これは、本来一つにまとめるべきでない状態をまとめてしまうことで発生するそうで、このようなパターンを回避するというのがIELR(1)の基本的なアイデア になるそうです。
つまり、扱える文法の大きさ的には
www.gnu.org
いいことづくめな気もしますが、IELR(1)では状態の計算にかかるコストがかなり重くなってしまうほか、プログラムもそれなりに複雑になってしまうそうで、スライドの後半では実装の過程でのトラブルが紹介されました。
day3
本屋さん②
うちのScheme インタプリタ にGC を実装したいので、ガーベジコレクション の本を買いました。大学に行けばあるのですが、手元に置いておきたかった。
また、inductorさんにeBPFをめっちゃ推されたのでeBPFの本も購入しました。
学生身分にとっては技術書を新本で買うのはかなりハードルが高いのですが、RubyKaigiに行ってとてもモチベーションが高くなっていたこともあり買ってしまいました。
Analyzing Ruby Code in IRB
drive.google.com
IRB がいかにして動作しているかという発表です。
IRB は入力途中（=Ruby に属していない言語）をいい感じに扱う必要があるということで、Prismのエラートレラント機能をうまく利用しているらしい。
私たちが使うときに、Ruby の書き味を失わないようにいい感じに調整してくれるIRB の偉大さと、むずかしさを目の当たりにしました。
day4
day4は大学の知人たちとレンタカーを借り、しまなみ海道 にドライブに行きました。
飛行機が19時ごろの離陸ということもあり、少し時間に余裕がない状態でしたが、伯方の島まで上陸できて大満足です。
day5〜
RubyKaigiの影響で最近やっていることを紹介します。
パーサージェネレーターをつくってみている
RubyKaigiから帰ってきてからパーサージェネレーターを自分の手で作りたい気持ちになったので、教科書を読みつつ手を動かしてプログラムを書いてみました。
はじめはLR(0)項の閉包を求めるところから始め、徐々に関数を増やしたり、データ構造を見直したりしました。
まだ全くパーサーとして動きませんが、LR(1)項にたいしてClosureとgotoと正準集合の計算をできるようになったので、もうちょっとでそれっぽくなるんじゃないかなと思っています。
自分はこれまでRuby をQuineを書く用途にしか使ってこなかったのですが、Ruby の強力な文法と組み込み関数のおかげでとても楽しくプログラミングができています。
おもちゃみたいなものでも、一回実装に落として具体的なものを書けばLramaのような大きいシステムにも立ち向かえる知識がつくんじゃないかなとおもっています。
2025/05/20追記
LALR(1)パーサージェネレーター（ぽいもの）が完成しました
↑ドラゴンブックを買ってしまった（家計に大打撃）
追記終わり
議論するための言語をもちたい
Rubyist と会話をする中で、自分の言語能力の欠如を痛感しました。
自分の概念理解が浅いために、何度も同じ説明をしてもらってしまったり、せっかく教えて頂いたことをいまいち理解できないままにしてしまったことも多々ありました。
せっかく聞いたことを十分に自分のものにできないのはとても悔しいです。
言語は思考のための道具であるということをしっかりと心に刻み、これから勉強を続けていきたいとおもいました。
ネットワークで遊びたい
RubyKaigi NOC の活動を見て、ネットワークの構築にも興味を持ちました。
いまだにどうやってRubyKaigiのWifi 網が実現されているか（特にNAT64周り）わかっていません。
自分もネットワークに詳しくなりたいなと思い、まずはということで自宅に少しだけネットワーク機器をそろえて遊び始めることにしました。
とりあえず、自宅から作業するときに大学のネットワークをうまく活用できるようにいろいろいじってみようかと思っています。
↑自宅に固定の
IPv4 アドレスを振ってもらったので、サークルの部員と
IPsec でピアを張りました。
VPN 用））
Ruby のパーサーに翻弄されているRuby のパーサーをもっと知りたいと思って、いろいろ試した記録です。
→持っていそう?
変数があるかどうかでレキサー の結果が変わっている様子
→厳密にはCFGに収まっていなそう?
（ここで自分がRuby のパーサーがlexical feedbackをしているといっていますが、これは自分の勘違いだと思います。）
2025/05/06追記
lexical feedbackの定義によりますが、
Ruby でもしてるそうです
追記終わり
RubyKaigiから帰ってきたあとの授業で、構文解析 の話題が出てきました。ちょうどRubyKaigiで聞いてきたことも触れられていてちょっとうれしかったです。
来年のRubyKaigiどうする
次のRubyKaigiは函館で開催されるそうです。
来年もぜひ参加したいと思っています。次はもっと技術をつけて、成果を引っ提げて行きたいです。
さいごに
今回の参加費用を援助してくださったピクシブ 株式会社様、私達がRubyKaigiを楽しめるように全力で支援してくださったPixivの皆さん、本当にありがとうございました！！
また、貴重な時間を割いて私と話してくださったスピーカー・コミッターの皆さん、Rubyist の皆さんありがとうございました！勉強したいことが増えてとても楽しいです。
Rubykaigiを運営してくださったスタッフの皆さん、スポンサー各社の方々、松山の方々、ありがとうございました！
またどこかでお会いしたら、どうぞよろしくお願いします。
参考文献
湯浅太一著, 情報系教科書シリーズ第９巻 コンパイラ , 昭晃堂
