Rustで作るプログラミング言語 (original) (raw)

だいたいやりたいところまでやったので感想を。めっちゃ良い本なので、自作プログラミング言語興味ある人にお勧めです。

どんな本

Rustを使ってスタックマシーン、パーサー、ASTインタープリター、バイトコードコンパイラ、実行環境を作っていきます。型チェックのシステムやコルーチン等のトピックもあり、実際に動く所までやります。

Rustの説明は少なめで結構いろんなテクは使われているので、別途Rustの本は必要です。途中からはパーサー（＋トーカナイザー）として、ライブラリのnomを使います。yaccのように別途設定ファイルがなく、ソースコードにrustの文法で直接ルールを書いていくスタイルです。

ソースコードは段階毎にgithubに公開されていて、写経するならそこを見ながらやれば大丈夫です。

github.com

対象読者

本の対象読者はこう書かれています。

いずれかの言語で中級以上のプログラミング経験をもつこと
コマンドプロンプトやシェルを使って最低限の操作ができる人
スタック、ヒープ、ツリー等の基本的なデータ構造を理解している人
Rustに興味があり、なにか作ってみる題材がないか探している人
理論よりも実践を通してプログラミング言語を学ぶタイプの人

実際に内容をみても、結構中級者向けでした。

加えてプログラミング言語を作ってみようって人の一冊目にはお勧めしません。別の本で軽く勉強するか、できたら実装してからこの本に挑戦した方が良いです。パーサーの細かい動きの説明は足りない気がします。

特に拘りがが無ければ、低レイヤを知りたい人のためのCコンパイラ作成入門がお勧めです。

www.sigbus.info

Rustの観点から見ると本の説明とgithubのソースコードとの同期が時々取れてなく、自力で突破する必要があります。図は少なめ。前半にAST、後半にスタックの図が少しあるくらいで、その辺の基本的なデータ構造はわかっている前提です。とはいえ、そんなトリッキーな実装は無くどちらかというとわかりやすさを優先した素直な実装に感じました。

スタックベースの仮想マシーン

最初にスタックベースの仮想マシーンを作ります。ここから難易度が高かったです。この章はわからなかったら飛ばしても良いと感じました。

/x 10 def /y 20 def { x y < } { x } { y } if

このコードは変数の宣言とifによる処理の分岐をしています。知っていれば典型的なスタックベースのソースコードなのですが、初めてだと何をやっているのかわからないと思います。

また不要な空白をスキップする機能が入ってないので、空白がちょうど1個出ないと駄目。2個続けるとそこが空文字列になって処理が終わってしまい、これに気がつくまで結構時間かかりました。

繰り返しですが、この章は上手く動かなかったら飛ばして次のパーサーに行っても良いです。次の章からが本番です。

パーサー

三章から本番で、独自言語のパーサーとインタープリターを作っていきます。ここでnomというパーサコンビネータのライブラリを導入します。

github.com

パーサーの実装部分のソースコードです。細かい説明はないので、これみてあーこういう事してるんだろうなって想像する力は必要です。なので一回別の本で何かパーサーを実装してからの方が理解は進むと思います。

fn parens(i: Span) -> IResult<Span, Expression> {
space_delimited(delimited(tag("("), expr, tag(")")))(i)

}

fn expr(i: Span) -> IResult<Span, Expression> {
alt((if_expr, cond_expr, num_expr))(i)
}

fn identifier (input: Span ) -> IResult<Span, Span> {
recognize(pair(
alt((alpha1, tag(""))),
many0(alt((alphanumeric1, tag("")))),
))(input)
}

このライブラリが面白いのは、トーカナイザーとパーサーが別れてないんですね。実際パーサー書いてみるとトーカナイズと分ける必要ないんじゃ・・って思いますが、実際に別れていない形の実装は初めて見ました。普通の教科書だとトーカナイザーを教える為に、1章取って正規表現の説明があったりするのでとても新鮮に感じました。

スクリプト言語ランタイム

ここではインタープリターに機能を追加していきます。設計上のトレードオフについても言及があり面白いです。変数に宣言が必要なのか不要なのか、変数への代入は文なのか式なのか。あまり小難しい話に踏み込まず、実際のプログラミング言語がどうなっているかを紹介し、自作言語の仕様を決めていきます。

その中でもifを式にするか文にするかの部分が面白い。僕は無意識にif文って読んでしまうくらいifは文派です。C言語がそうなのでその影響を受けていると思います。この本では、ifは式として実装します。そうなると値を返す必要があり、if式にelseが無い場合の処理で、何を返すのか？という課題が出てきます。

実装している部分です。

If(cond, t_case, f_case) => {
if coerce_i64(&eval(cond, frame)?) != 0 {
eval_stmts(t_case, frame)?
} else if let Some(f_case) = f_case {
eval_stmts(f_case, frame)?
} else {
Value::I64(0) }

elseに相当する処理があるかないかわからないのでOption型とし、中身があればその処理結果を、中身が無ければI64(0)を返します。今までの言語処理系を作ろう系の本で、この処理を書いたことが無いです。面白いですね。

最後、暗黙の型変換をRustらしく書いておしまいです。

静的型付けと型チェック

ここは実行前に演算の型同士をチェックする仕組みを入れます。そんなに難しくないです。

ここでもifは式なので、elseが無く条件が成立しなかったときは、条件が成立したときの型と同じ型の何かを返す処理が入ってます。面白い。

ここでパース時にエラーがあったときにパース対象のエラーの場所を出す仕組みを入れます。この修正が結構大変で、今までもインタープリターに読ませるソースが間違っていて動かない事がしょっちゅうあった事もあり、もっと早く導入してほしかったと思いました。

バイトコードへのコンパイル

ここまではソースを読んでそのASTを直接実行していましたが、ここから一度バイトコードへ変換しファイルに保存した後、そのファイルを読み込んでスタックマシーンで動作する仕組みを作っていきます。

今まで通り最小限のコードから徐々に機能を足していきますが、追加する機能は説明済みですよねで飛ばされるので、githubのコードを眺めながら実装していきます。写経はかなり辛い部類に入ります。

レジスタの無いスタックマシーンのループはbreakやconituneまでいれると難易度が高かったです。低レイヤを知りたい人のためのCコンパイラ作成入門（https://www.sigbus.info/compilerbook）の実装と比べてみるのも面白いです。両方ともコンパイラの実装が進んで行くと、最終的なデータ構造が関数単位になるのは、おおって思いました。

ここが出来たところで、マンデルブロー動いて満足。

この後の型チェックは一度実装しているし、コルーチンからデバッガの流れも自力実装出来そうだったのでここまでにしました。面白かったです。

最後に

コードが素晴らしいだけで無く、本文で説明されているプログラミング言語に対する洞察がとても面白かったです。

一点お願いがあるとすれば、簡単で良いので最適化の情報が欲しかったです。ASTを作ってから、定数をたたみ込んだりループを展開したりしながらASTを変更するのをRustでどう書けば良いのかが難しく、一個でも二個でも例があればうれしかったです。

Rustのソースは素晴らしく、本の内容も面白く、プログラミング言語を作りたい人の二冊目としてお勧めします。