ruruby: RustでつくっているRuby #Ruby

この記事は言語実装 Advent Calendar 2020２日目の記事です。前回はκeenさんの「自作コンパイラをブラウザ上で動かす」、次回はmitsuchiさんの「LLVM の Kaleidoscope を育てながら作る」です。

はじめに

みなさま、ご無沙汰しております。monochromeです。rurubyという名前でRuby処理系のRustによる実装を行っていて、昨年のAdvent CalendarでRustでつくる（つくれるかもしれない）Rubyという記事を書きました。今回はこの１年間の進捗と、今後の予定などを書いてみます。

レポジトリはこちら。実行にはRustツールチェーン(nightly channel)のインストールが必要です。
https://github.com/sisshiki1969/ruruby

毎度の宣伝ですが、「プログラミング言語処理系が好きな人の集まり」というSlackチャンネルがあって、言語処理系の話題が好きなプロ・アマ・学生・大学教員・水道屋・正常者・異常者などがごった煮になって議論や雑談をしています。質問、実装や発表の報告、学術的な話題、ポエム、何でもありです。この記事を読むまでもなく言語処理系が好きな方、この記事を読んで言語処理系に興味を持った方、この記事を読んでも言語処理系に興味が持てない方は是非ご参加ください。

要約

RustでRubyインタプリタを作っている。構文・機能の大半は実装できていて、中規模のプログラムも動くようになってきた。辛いこともあるけど楽しい。
野望としてはもっと多くのプログラムやライブラリを動かしたい、あともっと速く動くようにしたい。

Optcarrotが動いた話

昨年の段階で小さなベンチマークは動くようになったので、次の目標としてOptcarrotというプログラムを動かすことを目指すことにしました。OptcarrotはRubyコアチーム・コミッタのmameさんが作られている、Rubyで書かれたNES（ファミコン）のエミュレータです¹。今年のクリスマスにリリースされるRuby3をRuby2の３倍速く動作させる目標（Ruby3x3）の検証に使われています。また、公式（CRuby）以外の各種実装の速度比較もできます。

Optcarrotは自作Ruby処理系のターゲットとして都合がよい、いくつかの性質を備えています。

ある程度大きな、「普通の」プログラムである
Rubyの（一般によく使用される）各種文法・記法をまんべんなく使って書かれています。テストプログラムを自分で書くと未実装の構文・機能を避けて書きがちなので、「普通のプログラムが普通に動く」ことを目指す上では重要です。
外部ライブラリへの依存がない
実際にゲームで遊ぶにはグラフィックス・入出力ライブラリ（と連携するためのFFIライブラリ）が必要ですが、ベンチマーク専用のモードでは他のライブラリへの依存はありません。自作処理系では機能が乏しいのとライブラリも未整備で、特にC言語で書かれたライブラリは動きませんから、これもありがたいことです。Optcarrotは自作Ruby処理系製作者のために作られたものといって過言ではありません。
ベンチマークを取れる
ツールが付属していて、各処理系・バージョンをDocker内で自動的にビルド・実行して速度を計測し、グラフにできます。

で、色々頑張った結果、自作処理系でOptcarrotを動かすことができました。実行速度はまだまだですが、GitHubの既存処理系のベンチマークリストの片隅にrurubyも入れてもらいました。ありがとうございます。データは５月ごろのものなので、今は倍ぐらい速くなっています。

以下、その過程で実装に時間がかかった部分を紹介します。

ガーベジコレクタ（GC）

スクリプト言語はヒープ上に大量のオブジェクトを生成するため、定期的に不要になったオブジェクトを掃除する必要があります。掃除をするコンポーネントがガーベジコレクタ（GC）です。たいていのプログラムはGCなしでも動きますが、ベンチマークを取るのにフェアではないのでスクラッチから作りました。初心者なのでマーク＆スイープのシンプルなもの（precise, non-moving mark and sweep GC）です。256KBを１ページとし、オブジェクトとマーク用のビットマップをその中に入れています。

現在のところGCが扱うのはRubyオブジェクトの構造体のみです。その他にクロージャを生成する際に関数フレームをヒープにアロケートするので、将来的にはそれもGCの対象とする予定です²。

動作としては、

ページの先頭からオブジェクトを割り当てていく
ページの残りが少なくなったところでGC起動
ルートから全てのオブジェクトをたどり、ビットマップにマークをつける。
マークのないオブジェクトを廃棄してフリーリスト(linked list)につないでいく
オブジェクトの生成要求があればフリーリストを外して払い出す
空になったページは一旦廃棄して後で再利用
ページが一杯になったら新しいページを割り当てる

という感じです。

大量にオブジェクトを使い捨てるapp_aobench.rbで計測したベンチマーク（CRuby v3.0.0-devとの比較）を載せておきます。

左がメモリ消費、当たり前ですがGC導入で激減しています。右は実行時間、素朴な実装なのでパフォーマンス的にはまだまだです。将来的には世代別GCなどを導入したいですが、一体いつになることやら。

rurubyのGCについての発表資料

コルーチン（Fiber）

ファミコンではメインのCPUと画面描画用のGPU（PPUと呼んでいる）が同時に動きながらデータのやり取りを行います。Optcarrotでもこれをエミュレートするため、コルーチンを実現するRubyの言語機能であるFiberクラスを使っています。

コルーチンについてはこれまたmameさんがn月刊ラムダノート Vol.1, No.1(2019)に詳しく書かれています。RubyのFiberは（古典的な）コルーチンに忠実な実装と言って良いと思います。
『「コルーチン」とは何だったのか？』著者のブログエントリ

JavaScriptのジェネレータやC#のasync/awaitみたいなコルーチン「っぽい」ものは状態機械に変換することができますが、RubyのFiberは任意のメソッドを呼び出していった先からいきなりyieldして呼び出し元に帰る（そして後で元の場所へ復帰する）ことができるので、rurubyのようにメソッド呼び出しのたびにホスト言語（Rust）の関数を再帰的に呼び出していく動作モデルだと同じことをやるのは不可能です³。

実装にかなりてこずった挙句、結局OSのスレッドを使ってRustのsync channelの仕組みにより複数のVMを同期させつつ並行に動かしています。上の図はrurubyにおけるFiberの生成から実行、廃棄に至るライフサイクルを示しています。青の矢印は子→親へのデータ転送（Fiber.yieldメソッド）、赤は親→子（fiber.resumeメソッド）を示しています。

親FiberがFiber.newで子Fiber（fiberオブジェクト）を生成
親がfiber.resumeを実行すると親は一旦停止して子の実行が開始
Fiber.yieldが呼ばれると子は一時停止して親からのfiber.resumeを待機
再び親がfiber.resumeを呼ぶと動作は子に移る
子が実行を終えるとDeadとなり、次のGCのタイミングで回収される

本家RubyのFiberはユーザースレッドを用いて実装されており、rurubyに比べ軽量で高速に動作します。特に新しいFiberの生成は文字通り桁違いに速いです。Rustでポータブルな形で同じことをやるのはなかなか難しそうですが、自分の実装力が上がったらいつかチャレンジしてみたいと思っています。
Fiberを実装した人の講演動画「Fiber in the 10th year」 RubyKaigi2017

正直Fiberのような機能はなくても大半のプログラムは動きますし、実はOptcarrotもFiberの実装を持たない処理系のためにコードを自己書き換えしてFiberを使わないコードに変換する機能を持っています。rurubyはこのために複数スレッドでVMを動かす仕組みを入れました（アロケータ・GCは共有）⁴。結構面倒くさいので、もし自作言語だったら、もしくはターゲットがOptcarrotでなかったらこういうのは間違いなく実装しなかったと思います。モチベーションの維持には自己満足が大事。
rurubyのFiberの実装についての発表資料

カロリーメイトquineが動いた話

動きカクカク問題、@Linda_pp さんの助言により完璧に動作するようになりました！（嬉しかったのでしつこく投稿） pic.twitter.com/tvPV1K4a3i
— monochrome (@s_isshiki1969) August 18, 2020

少し前の話になりますが、今年の夏に大塚製薬のカロリーメイト・リキッドのプロモーションサイトが話題になりました。
CalorieMate to Programmer CUI MODE

（ネタバレになりますが）その中にQuineプログラムが隠れています（コードはこちらのブログ参照）。これはRubyで書かれており、自分自身のコードと同一の文字列⁵を出力した後、アニメーションが始まります。これは面白いと思い、rurubyで動くか試してみました。…が最初は全く動かず、ここでまたつまづきました。

複素数クラスとリテラル
缶の中に液体が注がれてしぶきが飛び散るアニメーションがありますが、これは実行時に流体力学的シミュレーションにより計算されています。そのために複素数クラス及びリテラルが使われています。これはただ実装するだけ。
謎の記法
全体的にeval$s=%q{Z=?\s;eval"$><<S=Z*4"+(%w{+"n=#{-~n%3};eval$s=%q{#$s}#YE";（以下略）のような謎コードになっていて、今見返してもなぜこれが自分の処理系で動くのか理解できません。かすかに覚えている範囲では、まず文字列をevalして⁶得られた文字列をevalし、得られた文字列をさらにevalするという構造になっていたかと思います。
・#{式}（文字列中に式を埋め込むテンプレートリテラル、変数一つのみの場合は#$sのようにも書ける）
・%q{}, %w{}のような文字列リテラル（％記法）
・$>（標準出力オブジェクト、<<演算子で右辺のオブジェクトを出力できる）
・?\s（文字リテラル、\sで空白文字を表す）
のような多彩な記法⁷があるので、これらすべてを正しくパースするのが大変でした。
単一代入、多重代入時の評価順
s[k]=Z*(k=(k*2-21)** 2/99)+q*79+Z+q*2*(6-k)のようなコードが最初は正しく動かずかなりハマりました。これ、配列のインデックスkを右辺式の中で再代入していて、先に右辺を評価してから左辺の配列を評価するとダメなんですね。確かにそちらの方が自然⁸かもしれないですが、分かるまではかなり悩みました⁹。
で、恐ろしいことに単一代入だと左辺を評価→右辺を評価→代入ですが、多重代入（例:a,b,c = 1,2）の場合は右辺を順に評価→左辺を順に評価→順に代入という順番になる奇妙な仕様です。
多重代入の謎仕様を何とかしてほしいという市民の訴え
不思議な代入式
Rubyでは a+b=3が有効な式¹⁰です（a+(b=3)と解釈される）。こういうのを正しくパースするのも（手書きパーサなので）かなり手間取りました。

実行速度について

インタプリタの高速化に関してはここではあまり書きませんが、機会があればまた。各種ベンチマークとOptcarrotのデータを載せておきます。フィボナッチ数列の計算が一番遅いことからわかるようにメソッド呼び出しのオーバーヘッドがまだかなり大きいので頑張りたい。なんとか２倍（遅い）以内に収めたいですねえ。

各種ベンチマーク

benchmark	CRuby(v3.0.0dev)	ruruby	rate
loop_times.rb	0.82 ± 0.03 s	1.15 ± 0.03 s	x 1.41
loop_for.rb	0.85 ± 0.01 s	1.50 ± 0.01 s	x 1.76
loop_whileloop.rb	0.40 ± 0.01 s	0.63 ± 0.01 s	x 1.60
so_concatenate.rb	2.59 ± 0.01 s	3.13 ± 0.04 s	x 1.21
string_scan_str.rb	0.15 ± 0.00 s	0.29 ± 0.01 s	x 2.00
string_scan_re.rb	0.19 ± 0.00 s	0.30 ± 0.01 s	x 1.57
so_mandelbrot.rb	1.90 ± 0.02 s	2.76 ± 0.03 s	x 1.46
app_mandelbrot.rb	1.31 ± 0.02 s	1.24 ± 0.02 s	x 0.94
app_fibo.rb	0.53 ± 0.00 s	1.56 ± 0.01 s	x 2.95
app_aobench.rb	9.72 ± 0.40 s	20.34 ± 0.40 s	x 2.09
so_nbody.rb	1.10 ± 0.02 s	2.35 ± 0.04 s	x 2.13

rateが大きいほどrurubyが遅いことを示します。
Rubyレポジトリ内のベンチマーク　コードはこちら

Optcarrotベンチマーク

benchmark	ruby	ruruby	rate
optcarrot	40.68 ± 0.40 fps	14.19 ± 0.05 fps	x 2.87
optcarrot --opt	127.21 ± 1.66 fps	57.36 ± 1.89 fps	x 2.22

--optオプションをつけるとコードを自己書き換えして高速化されます。

既存言語の処理系実装について

最後に既存言語の実装について少し書きます。

自作言語にせよ、既存言語にせよ、インタプリタにせよコンパイラにせよ、自分の実装がある程度動くようになって（例：自作Cコンパイラで自分自身をコンパイルできた！）ひとしきり興奮した後、大抵は次に何をするかという問題に直面します¹¹。これはこの界隈でセルフホスト後燃え尽き症候群と呼ばれる深刻な病態です¹²。特に自作言語の場合はユーザーも少なく、一人で地道に文法を拡張して、扱える型やクラスを増やしてライブラリを整備して…というのはモチベーションを維持しづらく、なかなか続かないと思います。

一方、すでに広く使われている言語の場合はきちんと動作することが保証されているライブラリやプログラムがたくさんあります。それらを一つ一つ動かしていくというのはそれなりに楽しい作業です。もちろん巨大なフレームワークなどは依存する全てのライブラリが動かないとダメなので、依存の少ない小さめのものから始めていくことになります。私にとってはOptcarrotが最初の具体的な目標となり、そしてその選択は結果的には成功だったと思っています。

既存言語の処理系実装の良いところ

面倒くさい部分・あまり興味のない機能も実装しないといけないので、実装力がつく
動く（はずの）プログラムがライブラリを含めて豊富にあり、自分の処理系が正しく動いているかを検証できる
ライブラリが動いたらそれを使っているもっと大きなプログラムを動かして…というわらしべ長者戦略です。いずれrurubyでもRuby on Railsが動く予定です¹³。

既存言語の処理系実装のつらいところ

謎の文法や謎の仕様の実装がつらい
つらい。

今後の野望

今はruby/specという（rubyレポジトリの中にあるので、たぶん）Ruby公式のスペックスイートを動かせるようにしようと頑張っています。基本的には基本クラスのメソッドがまだ全然足りないのと、冒頭で「構文・機能の大半は実装できていて」とか書いてますが、実は例外処理がまだ動きません。これは今年中に何とかしたいです。
あと、高速化も頑張りたい。
寒さも厳しくなってきましたので、みなさま健康に気をつけて良い進捗を。
それではまた来年。

作者のプレゼン動画とブログエントリ ↩
クロージャを作らない通常のメソッド呼び出しでは関数フレームはスタック上に確保する。その他の、例えばArrayクラスのオブジェクトが使う配列の構造体などはRustがよしなに管理してくれる。 ↩
これは嘘で、レジスタ保存領域と戻り先のアドレスとスタック領域を１セット用意してその都度切り替えれば可能。古くはC言語のsetjmp/longjmp、最近だとUNIXのucontextというのがある。普通のポータブルなやり方では困難、という意味。 ↩
ついでに言うとrurubyでは１プロセスの中でアロケータ＋複数スレッドの組をさらに複数走らせることができるようになっている。何のためかというとRustのテスト（cargo test）はマルチスレッドで走るため。 ↩
自分自身と同じものを出力するのが本来のquineだが、これは色などが微妙に異なる３パターンあって、出力するたびに異なるバージョンが出力されるという凝りよう。人間とは役に立たないことにこそ熱中する生き物である。 ↩
%w{}リテラルで囲まれた部分は、中の空白がすべて除去されて結合され、一つの文字列になる。このおかげでロゴの部分の空白は潰された状態でevalされる。 ↩
Perlなど、いろんな言語由来らしい ↩
評価の順序としては自然だが、こういうコード自体は全く自然ではない ↩
そんなのprintfデバッグでもすればすぐ分かるんじゃないのか、と言われるかもしれないが、そもそもこのプログラムが何をやっているのかさっぱり分からないので大変なのである ↩
普通は'+'の方が'='より優先順位が高いので(a+b)=3にパースされてエラーになるはず。でないとa=b+3が(a=b)+3になってしまう。これも試行錯誤した挙句、アドホックに解決した。 ↩
コード書くのにモチベーションは不要という奇行種は除く ↩
そのまま開発を続けてgitやらpythonやらがコンパイルできるところまで突き抜けていく方もいるようですので、あくまで一般論です ↩
無理です。 ↩