自作言語 Ruccola のコンパイラがセルフホストできました!
https://github.com/sonota88/ruccola/tree/main/selfhost
※ Qiita に書いた記事のクロス投稿です
※ 最初は Pric という名前だったのですが、 Ruccola に変更しました。以下、修正できていない箇所は読み替えてください。
これまで vm2gol(virtual machine to game of life)というプロジェクト名で以下のようなことをやってきました。
今回のセルフホスト編は何もないところから全部書いたわけではなく、すでに v2 がある状態から出発しています。
※ 独自VM向けなので「仮想機械語」と呼ぶべきかもしれませんが、この記事では単に「機械語」とします。
※ 図ではコンパイラが直接機械語を出力しているように見えますが、実際はアセンブルの過程があります。説明の簡略化のために省略しています。
T図式でも描いてみました。図の「Pric M」は Pric VM 向けの機械語。
2021-01-12 〜 2021-02-21
第2世代コンパイラのサイズ(行数)はこのくらい(2021-05-25 現在):
$ wc -l lexer.pric parser.pric codegen.pric \
> lib/json.pric lib/std.pric lib/types.pric lib/words.pric
250 lexer.pric
973 parser.pric
1325 codegen.pric
170 lib/json.pric
536 lib/std.pric
466 lib/types.pric
305 lib/words.pric
4025 合計
# 補助ツール的なもの
$ wc -l check.rb preproc.rb
110 check.rb
19 preproc.rb
129 合計
以下、v2/v3 と 第1世代/第2世代 という表現が出てくるので先に説明しておきます。
※ 今回作った v3 ではライフゲーム(game of life)専用ではなくなるのと、やっぱり呼びやすい名前がほしくなって Pric という名前を付けました。 vm2gol = Pric (プロジェクト名・言語名)という雑な捉え方でだいたい大丈夫です。 vm2gol がコードネームで Pric が正式名みたいな雰囲気。
第1世代なのでここは Ruby のコードの修正です。どのような機能を追加したかについては後述。
できたもの: 第1世代-v3 なコンパイラ
別の言い方でいえば:
ここからは Pric 言語でもりもり書いていきます。
第2世代コンパイラはこの時点では v2 の機能しかサポートしておらず、ライフゲームはコンパイルできますがセルフホストはまだできません。
v2 コンパイラの移植作業はこれまで何度もやってきていてだいぶ慣れています。Pric 版に一番近い C 言語版もすでにありますし、実装で悩んだら C言語版を見ながら移植していけばOK。また、これまでの移植の過程で整備されてきたテスト用データもそのまま使えます。
できたもの: 第2世代-v2 なコンパイラ
やることはだいたいステップ (1) と同じ。
できたもの: 第2世代-v3 なコンパイラ … これができれば完成
ステップ (2) の移植作業はこれまでやってきた移植作業と同じようにやればいい。
ステップ (3) は Ruby で (1) をやったことを繰り返して Pric で同じように書けばいい。
というわけで、全体の中ではステップ (1) が今回の目玉でした。今回自分にとって一番収穫の大きかったのがステップ (1)。
(1) ができた時点で (3) で何をやればいいか大体の目星が付き、後はやっていけば終わるなという感じで割と気楽に進めていきました。とはいえ、退屈な作業ということはなく、自作の言語でこれくらいの分量のプログラムを書くのは初めての経験でしたから、 (2) も (3) も十分新鮮でおもしろかったです。
はっきり決めていたわけではありませんが、基本的には C言語版に近い感じになるのかなとイメージしていました。
そうすると、 C言語版では使っていて Pric v2 にない機能をリストアップしていけば、それが v3 で追加すべき機能の候補ということになります。
#include
#define
ざっとこんなところかなあとぼんやり考えて、後は作りながら決めていきました。
以下、思い出しながらそれぞれについて書いてみました。
※ 以下は説明のために整理していて、実際に考えたり作った順番とは多少違いがあります。
※ ちなみに、私はC言語はずっと前にちょっとやった程度でだいぶ忘れています。素人が書いていると思って読んでいただきたく……勘違い・浅い理解・不正確な記述などあると思います。
1文字ずつ読み書き。これは必要。
VM に命令を追加: read
, write
入り口と出口で文字と数(アスキーコード)との変換を行い、コンパイル処理本体で扱っているのはすべて単なる数(整数)となるイメージです。
"def main()\n ..."
↓ read
100 101 102 32 109 97 105 110 40 41 10 ...
↓コンパイル
32 32 99 97 108 108 32 109 97 105 110 ...
↓ write
" call main\n exit\n ..." (アセンブリコード)
こうやって見てみると、コンパイラがやっていることは「ある数の並びを別の数の並びに変換する」処理だと見ることができます。おもしろいですね。結局それしかやっていないというか。
それはさておき、出力ができるようになると print デバッグができるようになります。また、出力を検証する形でテストできるようになり、これだけでもだいぶ進歩を感じるものです。「おっ、この機能ができたらアレとアレができるようになるじゃん!」という、ブートストラップの楽しさ。
hello world はこんな感じ。こんなのでも動くと嬉しい。
def putchar(c)
write(c, 1);
end
def main()
putchar( 72); # H
putchar(101); # e
putchar(108); # l
putchar(108); # l
putchar(111); # o
putchar( 44); # ,
putchar( 32); # (SPACE)
putchar( 87); # W
putchar(111); # o
putchar(114); # r
putchar(108); # l
putchar(100); # d
putchar( 33); # !
putchar( 10); # (LF)
end
演算子としては小なり <
だけ追加しました。これだけ追加すれば、 v2 からある ==
、!=
と組み合わせてあれこれできます。
VM にレジスタを追加: sf
(sign flag)
VM に命令を追加: jump_g
... x86 の jg
命令を参考に
#include lib/std.pric
のような行を探し、指定されているファイルを読み込んでその場に埋め込むスクリプトを Ruby で書きました。
が、これは単に cat コマンドで繋げるだけもよかったですね。そうしておけばさらに簡略化できた。
※ 機能として挙げましたが、この部分はコンパイラの本体に含めず、補助ツールの類である(セルフホストの対象外)ということにしました。
C の &
と *
lea
命令を追加
lea
命令を参考にデリファレンスの括弧の中の部分は単なる式ということにしています。
*( some_addr_ + 2 )
^^^^^^^^^^^^^^
この部分は単なる式
途中紆余曲折があって *(some_addr_, 2)
のような書き方を試したりしましたが、括弧の中にはただの式を書くことにして単純化し、C っぽい見た目に落ち着きました。
デリファレンス演算の視点(?)では「とにかく何か値(式の評価結果=アドレス)が渡されるので、そのアドレスが指している場所を操作対象とする」のように考えればよい、ということに。
(余談)乗算の *
と被るのでデリファレンス演算子には別の記号を使うのはどうかと考えて ^
にしてみたり、前置じゃなくて後置にするのはどうだろう? と考えて ( ... )^
にしてみたり……という試みが途中ありました。
下手な考え休むに似たりかと思いきや、Pascal ではそのように書くのだと後から知りました。図らずも似たところに辿りついていたようでちょっとおもしろかったです。
他には addr(some_var)
, deref(addr_expr)
のように普通の関数っぽい構文にしてしまう、という案もありました。パースは少し楽になりそうですが、視認性が悪そう(普通の関数と見分けにくそう)な気がしてボツに。
メモリのスタック領域として使っていた部分のうち、アドレスの小さい方の端をヒープとしました。
malloc もまじめに作らないといけないのかなと思ってあれこれ調べていたんですが、単に確保した分だけカーソルを動かすだけなら簡単で私でもすぐ作れそうね、じゃあそれで、ということになりました。
※ bump allocator とか stack allocator と呼ばれている方式だそうです。 参考: Allocator Designs | Writing an OS in Rust
というわけで allocate 関数の中身はこれだけ。
def allocate(g_, size)
# 変更前のカーソル位置
var head_addr = *(g_ + GO_ALLOC_CURSOR());
# 変更後のカーソル位置
var next_addr = *(g_ + GO_ALLOC_CURSOR()) + size;
# カーソル位置を更新
*(g_ + GO_ALLOC_CURSOR()) = next_addr;
# スタックと衝突していないかチェック
check_heap_stack_overlap(g_);
# 確保した領域の始点アドレスを返す
return head_addr;
end
(g_
はグローバル変数構造体のアドレス。後述。)
free はありません(C言語版でも free してなかった)。ここは富豪的に。
富豪的にやってどのくらいメモリが必要だったかというと、最終的には番地の数で 2,600,000 となりました。1 byte/番地で換算すると約 2.6 MB。
あと、ヒープとスタックの衝突を Pric コードのレイヤーで検出する作りにしていて、そのためにレジスタ sp
の値を取得する組み込み関数を追加しました。ここはちょっとやっつけ。
配列は作る前からイメージがあって特に詰まらずに作れました。
「低レイヤを知りたい人のためのCコンパイラ作成入門」にならって、普通のローカル変数と同じようにスタックに置きます。
構造体の配列を使いたい場合は構造体のデータそのものは持たせず、ポインタというかアドレスを持たせる形で使います。もしデータそのものを持たせるとしたら各要素のオフセットの計算は自前でやらないとダメ(言語によるサポートはない)。
配列変数名[添字]
で配列の要素にアクセスする構文を一度用意して、ステップ (1) では実装までしましたが、ステップ (3) でやることが増えるので取りやめにして実装も削除しました。
デリファレンス演算子があれば
a = *(xs_ + 1);
*(xs_ + 1) = 2;
のように配列の要素を読み書きできます。つまりポインタ演算のシンタックスシュガーなわけですね。
機能はなるべく少なくしたいという方針に沿って、今回は []
演算子は取りやめにして実装も削除しました。
ただし、「これは配列を扱っているんだぞ」という意図を表すために実際は下記のような関数を介して操作するようにしています。
def aset(array_, i, val)
*(array_ + i) = val;
end
def aget(array_, i)
return *(array_, i);
end
Pric 言語で書けるものに関してはこのようにユーティリティ関数を作っていきました。
それで、結局配列のために手を加える必要があったのは
これだけといえばこれだけですね。
「配列という機能を追加した」というよりは「変数の幅の考慮とポインタ演算を組み合わせることによって配列の操作に相当する操作ができるようになった」という感覚です。
配列があればOK。プログラマ(私)が「これは文字列なのだ」と思い込むことにより文字列として扱うことができます。
たとえば C だったらこのように書くところを、
char str[] = "hello";
Pric では次のように書きます。
var [6]str;
aset(&str, 0, 104); # h
aset(&str, 1, 101); # e
aset(&str, 2, 108); # l
aset(&str, 3, 108); # l
aset(&str, 4, 111); # o
aset(&str, 5, 0); # (NUL)
さすがに毎回手で書くのは面倒なので適当なスクリプトで生成してターミナルからエディタに貼り付けていました。
また、コード上での行数が多くて邪魔なのと、複数箇所で同じ文字列を使うケースがあることから、実際は次のように文字列に値を詰める処理を関数にして使っています。
var [6]s_hello; set_s_hello(&s_hello);
ちなみに、文字列関連の何かを調べていたときに Pascal の文字列(先頭に文字列長を持つ)について知りました。Pascal 方式の方がバグが発生しにくそうな感じがしてちょっとなびきかけましたが、ひとまず C に寄せました(Pascal よりは C の方がなじみがあるため)。
心の目で見ると構造体のようなものに見える何か。これもすでにある機能でまかなえてしまいます。
構造体のデータはヒープに置いていていますが、これはそういう制約がある訳ではなくとりあえずのルールです。たぶんスタックにも置けるはず。
some_struct.some_member
や some_struct->some_member
のような構文は用意せず、操作用のインターフェイスとなる関数を作ってその中でごにょごにょしています。
例を挙げると以下は List 構造体の size メンバの値を返す getter 関数です。アドレスがあればそれで操作できるぞい、というノリ。
def List_size(self_)
var size = *(self_ + LIST__SIZE());
return size;
end
# 呼び出し側
# C でいえば list_->size に相当
var list_size = List_size(list_);
結局、メモリ上の位置とデータがあって操作がある、ということでしょうか(それはそう)。
関数はどこ(他のどの関数)からでも呼び出せますから、固定値を返す関数があればグローバルな定数と等価なものとして扱えます。マクロのような仕組みを追加しなくても、すでにある関数を使えばOK。じゃあそれで。
※ ということにしましたが、コンパイラの機能に含めないことにしてプリプロセッサでやってしまってもよかったかも。
たとえば 1つ前の「構造体」の節のコード例に出てくる LIST__SIZE()
がこれです。
たとえば ELF だと .data セクションや .bss セクションに置く、という話があります。
しかし、その方向で進めるとなるとアセンブリ・機械語のファイルのフォーマットやメモリレイアウトも考えないといけなくなります。話が大きくなってハードルが上がってしまう(完成までの道のりが長くなってしまう)ように思われました。
そこで、グローバル変数に関してもすでにある機能でなんとかできないかと。
要するに
という要件を満たせれば、その何かをグローバル変数相当のものとして使えます。
そこで思いついたのが、エントリポイントである main 関数で構造体を1つ用意して、そのアドレスを関数の引数でバケツリレーしていく方法です。よし、じゃあそれで。
<
だけ追加したこうして見てみると、今回は
ことの比重が大きく、これらを利用することでできることの幅がかなり広がった、と振り返ることができそうです。
また、グローバルな定数や配列・構造体操作用の関数に加えて -
, <=
, &&
, ||
などの演算子も関数でなんとかしていて、関数があることでなんとかなっている部分も多いですね。関数えらい。抽象化の力。
まずは文字列リテラル(に相当する部分)を静的なデータとして使いまわせるようにするところから手を付けたいですね。
おそらくここが速度的に一番のボトルネックになっているので、ここをなんとかするだけでかなり速くなって、後が楽になるんじゃないかと。
パッと思いつくもの、やりたいなーと思いつつ自重していたのはこのあたり:
[]
(
)
で囲めば済むので結局今回もお流れとなった-
, /
, %
, >
, !
, &&
, etc.&&
, ||
の短絡評価あんまり詳しく考えてないですが、C に近づいていくのかなあ。
v1, v2 では初心者向け教材っぽくしたくて(想定読者=どうやってコンパイラを作ればいいのか分からなかった頃の自分)「なるべくベタな仕様・見た目にしたい」「高度な機能や独自色をなるべく入れない」という気持ちがあったのですが、v3 ではその縛りは外してしまってもいいかなと思っています。
というわけで本体は以上で終わりです。以下、苦労話や枝葉な部分のメモです。
lexer, parser, codegen を全部コンパイルすると現状では 15分くらいかかります(第2世代コンパイラが育つに連れて伸びていき、最終的にこのくらい)。
ふつうに辛いのですが、終盤ではゴールが近いと分かっていたので下手にジタバタせず逃げ切りました。特に対策せず、実行して待ってる間に部屋の掃除、実行して部屋の掃除、を繰り返していました。部屋がちょっときれいになりました。
※ 「TODO」の節で書いたようにこれから速くしていく予定です
プログラムが大きくなってくるとアセンブリや機械語やメモリのダンプを見てもさっぱり分からん……ので git reset --hard
して歩幅を小さくしてやり直して、それで8割くらいはなんとかなった気がします。残りの2割はがんばってなんとか。gdb とか便利なものがないのでここはちょっと辛いですね。
ただ、長くても数時間くらいでなんとかなるレベルで、バグの原因が判明するまで何日もかかるということはありませんでした。
なるべく複雑なことをしないように作っていたのが良かったかもしれません。
print デバッグなどでがんばる……。
ある関数で配列の範囲外アクセスが原因と思われるエラーが発生し、おそらく呼び出し元で範囲指定をミスしており、そして呼び出し元がたくさんあり、まず呼び出し元の特定が必要……のようなパターン。
セルフホスト達成後に試したところ、VM などにちょいと細工をするだけでスタックトレースを見られるようにできました。若干チート感がありますが、これはさっさとやっておけばよかったかも。
これは結構鬱陶しくて、よく間違えるのと、個数が違うのが原因だと分かりにくく不毛だったため、さすがに対策しました。
構文木の段階で関数の定義と呼び出しを突き合わせてチェックする数十行程度のスクリプトを、これは補助ツールだから……と言い訳しつつ Ruby で書き、パース処理とコード生成処理の間に挟みました。
すごく原始的な静的解析でしょうか。
v2 から v3 への変更のうち、セルフホストにはそんなに関係ない部分、その他。
v2 では文頭に set
, call
, call_set
を明示的に書く方式にしていましたが、これを不要にしました。ある程度量を書くとなると、やはり鬱陶しいので。これは割と小さめの修正でOK。
-set a = 123;
+a = 123;
-call foo_func();
+foo_func();
-call_set a = foo_func();
+a = foo_func();
関数の引数として任意の式を書けるようにし、また、関数呼び出しを式として扱うようにしました。これにより、たとえば次のように関数呼び出しを関数の引数として書けるようになります。
foo_func(bar_func());
だいぶ普通の言語っぽくなりました。
v2 には else がなく
case
when ...
# ...
when (0 == 0) # else の代わり
# ...
end
のように書いていたところを、次のように else で書けるようにしました。
case
when ...
# ...
else
# ...
end
case文があれば if文はなくていいかなと思っていたのですが
ということで書けるようにしました。
レキサで処理しています。if
が来たら case
when
の2つのトークンに変換するだけ。
if ( ... ) ... end
↓ 変換
case when ( ... ) ... end
これだけで else
節のある if文も書けるようになります。
if ( ... )
# ...
else
# ...
end
↓ 変換
case when ( ... )
# ...
else
# ...
end
すでにここまで貼ったコード片で見てきた通りで、 Ruby っぽい見た目に変えてみました。見た目は Ruby っぽいけど中身は C っぽい、ちょっと不思議な書き味です。
これはなんとなくできそうだったので、試してみて、なんとなくこうなったというものです。
v2 とのギャップを小さくするために JavaScript っぽい構文に戻そうかなとも考えていましたが、元に戻すのが億劫になるところまで進めてしまって、めんどくさくなって結局そのままという。
アドレス演算子、デリファレンス演算子があるため Ruby と文法コンパチにはなっていないと思います。
コードの見た目だけでは通常の変数なのかアドレスが入ってる変数なのか、使用箇所を見ても宣言を見ても分かりません。
var a; # 普通の整数が入る
var b; # アドレスが入る
そこで、見た目で瞬時に判別できるように、アドレスが入っている変数には末尾に _
を付けています。
def foo(
arg1, # 普通の変数
arg2_ # アドレスが入っている
)
# ...
end
foo(
a, # 普通の整数を渡している
b_ # アドレスを渡している
);
というわけでおまけコーナーは以上です。また何か思い出したら追記するかもしれません。
Crieitは誰でも投稿できるサービスです。 是非記事の投稿をお願いします。どんな軽い内容でも投稿できます。
また、「こんな記事が読みたいけど見つからない!」という方は是非記事投稿リクエストボードへ!
こじんまりと作業ログやメモ、進捗を書き残しておきたい方はボード機能をご利用ください。
ボードとは?
コメント