Rustでインタープリターを書いた話

嘘です。

Rustでインタープリターを書いている話

こんにちは。VOYAGE GROUPの子会社、fluctで学生アルバイトをしているアメミヤです。
日程調整のスプレッドシートにしれっと記入したら、何も怒られなかったので、本記事はVOYAGE GROUP Advent Calendar 2015の11日目となります。

RustはMozillaが開発している、マルチパラダイムの静的型付け言語で、パターンマッチや強力な型推論ジェネリクスやそれを柔軟にする型クラスに近いトレイトを持っています。
中でも特徴的なのは、変数の所有権やポインターの貸し出しといった概念で、これによりGCを用いずに静的にメモリ領域の寿命を計算することができます。

詳しくは公式サイト今年のRust Adevent Calenderへ。
最近は落ち着いてきたものの、依然として変更の激しい言語なので、参考にする時はなるべく新しい文書の方がベターです。

今回はLLVM IRへのコンパイラを書き始めたのですが、思っていた以上にLLVM分からないマンだったのでEvaluaterの方を実装してインタープリタになってしまいました。

github.com

ビルド・実行

cargo run -- [file]

Cargoについて詳しくは今年のRust Ad以下略
後述しますが、rustcコンパイラへのプラグインを使っているため、この機能の存在するRust Nightlyチャンネルでの実装になっています。
Stableチャンネルではビルドが失敗します。

文法

オレオレ。こんなのを予定(妄想)しています。

fizzbuzz: {
  is_fizz: i % 3 == 0
  is_buzz: i % 5 == 0
  fizz: if is_fizz "fizz" ""
  buzz: if is_buzz "buzz" ""

  fizz.concat{buzz}
}

range{min: 1 max: 100}.map{i: fizzbuzz}

いまはこんな程度しか動きません/(^o^)\

i: j / 2
j: 5
k: k + 1

i * (j + 3) - (j / i)

遅延評価戦略(言いたいだけ)を実装しており、後に出てくるjをiの定義で使うことができます。
また、無限に再帰してしまうkは必要がないため評価されません。

なぜ作っているのか?

現在、社内では読書会/勉強会という形でSICPTAPLアンダースタンディングコンピューテーションといった書籍を読み進めているのですが、そのどれもに、言語処理系を実装する章が存在しています。
そこで、実際に手を付ける前に自分で試行錯誤してみたくなってみた。というのが今回の動機になっています。

言語作ること自体初めてですし、お勉強もそっち方面ではないです。なので、コードは地獄です。破茶滅茶です。ゆるして。

使ったCrates

crateはRubyでいうgem、Pythonでいうeggです。

peg

github.com

PEG(Parsing Expression Grammar)のRust実装。
PEGって知らなかったんですが、RubyのTreetopもそうだったみたいです。
正規表現に感覚は近いですが、再帰的なマッチャの定義ができるのがミソ。

Rustを拡張したDSLこんな感じで書くことでパーサーとグラマーが同時に実装できます。便利。
代数的データ型であるEnumとの相性がよく、リテラルに対してのマッチを除いた殆んどがASTの定義に即した記述になりました。
ここら辺、型定義からパーサを生成する何か?を作れそうな夢が広がります。

Rustを拡張したDSLコンパイル時に評価するために、pegはコンパイラプラグインを提供しています。ここがNightlyでないと動かない理由。

docopt

github.com

docoptはPythonやGoでよく使われるコマンドラインツールを作るためのパッケージで、ドキュメントからフラグやサブコマンドのパーサを生成してくれるナイスなやつです。
こちらもドキュメントからパーサを定義する処理をコンパイル時に走らせるため、コンパイラプラグインとして提供されています。

やったこと

四則演算子、変数、多項式、変数定義のための環境、変数に結びつく値の遅延評価

やってないこと

ブロック、比較、条件分岐、マサカリを防ぐためExecuterという名前をEvaluaterに変える(フセゲナカッタ

やりたいこと

型の静的検査

いまのところ苦労した点

多項式のパース

ここから多項式のパーサ定義なのですが、苦労ポイントでした。
単に数字リテラルのみの多項式ならさくっと書けたものの、項にもまた変数やブロックの評価といった式を書けるようにするのにハマった時間が長かったです。

結局、式の優先順位を正しく整理できていなかったのが原因で、単に

3

といったコードも Add(Mul(Pri(Atom(Ltr(Num(3)))))) のように構文木を作らなければならないことに気付きました。

Rustの変数のとりあつかい

Rustでなにか書く時に毎回ハマってる気がする。きのせい?

環境、Envを各executeメソッドで持ち回す方法でもハマりました。
Envは変数の名前とそれに紐付く式のハッシュマップを持っていて、名前が見つかれば式を評価した値で置き換えるために持ち回します。

spectr/executer.rs at 9dcc2061ef23cf653cc8c40fac25abb9f02ac76c · rail44/spectr · GitHub

枝を複数持っている構文木のノードでは、それぞれに対してexecuteを呼びだす必要があるため、当初は fn execute(self, &Env)といったメソッドの定義でした。
この&EnvはBorrowed Pointerと呼ばれるもので、変数への参照を"貸しだし"、それを渡した関数やメソッドが終了次第開放されるというものです。(Lifetimeに関する説明は省きます)

ただ、今回作ろうとしている言語は、式は必要になったタイミングで遅延評価され、同じ環境で同じ式は1回しか評価されないという戦略を取ろうとしていたのがアダになりました。
遅延評価をしたタイミングでEnvの持つ別のハッシュマップへとその値を格納する必要が出てくるので、Envへの変更権限を持たない&Envの持ち回しでは実現できなかったのです。

そこで、execute関数へとEnvを所有権ごと値渡ししてしまうことにしました。executeはEnvを返すことで所有権を返還する、といった方法です。

let (hoge_value, env) = try!(hoge.execute(env));
fuga.execute(env).map(|fuga_value| (hoge_value, fuga_value))

ちょっと不恰好に見えますが、&mutを使うよりも見通しが効きますし、ここら辺のオーバーヘッドを気にするのはrustcの仕事で、僕の懸案ではないと割り切りました。

まとめ

Rustむずい(小学生並みの感想) 言語開発たのしい(小学生並みの感想)

明日、12日目は@takeru911の担当です。お楽しみに!