タネ明かし: Whitespaceコンパイラを作った話の裏側

2020-04-01

κeenです。今朝、エイプリルフールのネタ記事を書いたのでそのタネ明かしをします。タネとはいっても、ほぼ手書きなんですけどね。

WhitespaceはEdwin BradyとChris Morrisにより2003年4月1日に発表された言語です。この言語自体エイプリルフールのジョークなんですね。公式ページはあるのですが、繋がらないのでWebArchiveとかからアクセスして下さい。

特徴としては空白文字、タブ文字、改行文字だけで構成されているのでパッと見では何も書いてないようになる点があります。いわゆるesoteric languageです。

今回の私のエイプリルフールのジョークは、Whitespaceを知らない人には「正直者にしか見えないコードですか？」、Whitespaceを知ってる人には「Whitespace！？んなもん書ける書けるわけないだろ！あ、そうか今日はエイプリルフールか」、私を知ってる人には「Whitespaceのコンパイラは普通はありえないけどコイツならやりかねない」と思われそうな絶妙なラインを狙ったつもりです。最終的にはちゃんと動く処理系を出してるのでジョークかどうかやや怪しいですが楽しんでいただけたなら幸いです。因みにソースコードは4000コマンド近くあります。

空白だと意思伝達に難があるので、以降この記事内では空白文字、タブ文字、改行文字をそれぞれ s 、 t 、 n と表記します。

Whitespaceの詳細

Whitespaceは命令型のスタックマシンです。ヒープも扱えます。値は任意長の整数のみです。

それぞれのコマンドの前には命令修飾パラメータ（Instruction Modification Parameter、IMP）がつきます。 IMPは5つあり、コマンドの種類を大別しています。

IMP	分類
`s`	スタック操作
`ts`	算術
`tt`	ヒープアクセス
`n`	制御構造
`tn`	I/O

それぞれのIMP毎にコマンドがあります。また、コマンドによってはパラメータを取ります。パラメータには数値とラベルがあります。

数値は符号（s が+で t が-）に続いて2進数（s が0で t が1）を書き、 n で終端します。2の補数表現ではないので注意して下さい。

ラベルは s と t の文字列で、 n で終端します。

以下に、コマンドを列挙します。名前がないと不便なので名前もつけておきます。これは私独自のものなので注意して下さい。

スタック操作

コマンド	別名	パラメータ	操作
`s`	push	数値	スタックに数値をプッシュする
`ns`	dup		スタックトップを複製する
`ts`	copy	数値	スタックのトップからn番目の値をスタックトップにコピーしてプッシュする
`nt`	swap		スタックのトップ2値を入れ替える
`nn`	discard		スタックのトップの値を捨てる
`tn`	slide	数値	スタックのトップの値を残してn個の値を捨てる

このうち、 copy と discard は Whitespace 0.3で追加されたコマンドだそうです。

これら2つのコマンドはキモチとしては、ローカル変数用のコマンドです。関数は引数に与えられた値からスタックがスタートします。

| v1  |
| v2  |
| v3  |
+-----+

これらの値をcopyで参照しながら関数を実行します。

| v3  |<-+
| v   |  |
| v1  |  | copy 3
| v2  |  |
| v3  |+-+
+-----+

で、最後にローカル変数の上に返り値を作ります。

| ret |
| v1  |
| v2  |
| v3  |
+-----+

この状態でdiscardを呼ぶと、キレイに返り値を呼び出し元に返せる訳です。

discard 3

| ret |
+-----+

算術

2値消費して1値を生成するコマンドです。

コマンド	別名	操作
`ss`	add	足し算 (top[1] + top[0])
`st`	sub	引き算 (top[1] - top[0])
`sn`	mul	掛け算 (top[1] * top[0])
`ts`	div	割り算 (top[1] / top[0])
`tt`	mod	乗余算 (top[1] % top[0])

ヒープアクセス

コマンド	別名	パラメータ	操作
`s`	store		ヒープに値を保存する (heap[stack[1]] <- stack[0] )
`t`	retrieve		ヒープから値をとってくる (stack.push(heap[stack[0]]))

制御構造

コマンド	別名	パラメータ	操作
`ss`	label	ラベル	プログラムにラベルをつける
`st`	call	ラベル	コールスタックに今のプログラムの場所を記録し、ラベルに飛ぶ
`sn`	jump	ラベル	ラベルに飛ぶ
`ts`	jz	ラベル	スタックトップが0ならラベルに飛ぶ
`tt`	jneg	ラベル	スタックトップが負ならラベルに飛ぶ
`tn`	ret		callに呼応し、記録されたプログラムの場所に戻る
`nn`	end		プログラムを終了する

call と ret があるので思ったよりマトモなプログラミングができます。

I/O

コマンド	別名	操作
`ss`	outchar	スタックトップを文字として出力する
`st`	outnumber	スタックトップを数値として出力する
`ts`	readchar	文字を読んで、ヒープの指定されたアドレスに置く
`tt`	readnumber	数値を読んで、ヒープの指定されたアドレスに置く

その他

エッジケースの仕様が与えられてないので実装から紐解きます。

リファレンスにできそうな実装は、WebArchiveから辿れるオリジナル（Haskell実装）と、Whitespace作者によるIdris実装があります。これらを読んでみます。

未初期化のヒープを読んだときは0が返るときと返らないときがあるぞい
- Idris実装は0を返してる。Haskell実装今までにstoreしたヒープアドレスの最大値以下なら0、最大値を越えると例外っぽい
スタックの底をついたときは未定義っぽい
- Idris実装は0を返して、Haskell実装は例外
存在しないラベルにジャンプしようとするのは未定義っぽい
- Haskellは実行時エラー、つまり存在しないラベルにジャンプするコマンドにさしかかったところでエラー
- Idrisは検査エラー、つまり実際には実行されないコマンドでも実行に入る前にエラーになる
outcharとreadcharの細かな仕様が不明
- それぞれHaskellとIdrisが数値<->文字変換でできるもののみ扱える。
- 実質ASCIIのみ？
readnumとreadcharのEOFの扱いが不明
- 多分エラー。でもEOFは扱えてほしいな…。

因みにHaskell実装は手元にGHC処理系がなくて、Idris実装は最新版のIdrisコンパイラでコンパイルできないのでどちらもコンパイラ作成には使ってないです。

あ、あとs 、 t 、 n 以外の文字はコメント扱いで無視されます。

ところで、熱心なHaskellプログラマなら上記のコマンドセットに見覚えがあるかもしれません。これはG-Machineに由来するものだそうです。

Incidentally, for those who are interested in this sort of thing, Whitespace is essentially the G-machine with a weird syntax. You could probably use it as a target for a functional language. I keep thinking I should try that...
— Edwin Brady (@edwinbrady) May 14, 2019

アセンブラ

流石に s 、 t 、 n だけでプログラミングするのは発狂ものなのでアセンブラを作ります。直接Whitespaceを書いてないのでセルフホストのレギュレーションからは外れそうですが、アセンブラの1コマンドがWhitespaceの1コマンドに対応するという意味では実質Whitespaceでプログラミングしてます。

今回のWhitespaceのコンパイラのアセンブリソースの冒頭部分はこんな見た目です。

Flow call 0x00 # main
Flow end

# fn 0x00
# main {
Flow label 0x00
  # init start/top of ops
  Stack push 0x02
  Stack push 0x08
  Heap store
  Stack push 0x03
  Stack push 0x08
  Heap store

  Flow call 0x10 # parseInstAll

  # init start/top of labels
  Stack push 0x04
  Stack push 0x03
  Heap retrieve
  Heap store
  Stack push 0x05
  Stack push 0x03
  Heap retrieve
  Heap store

  Flow call 0xd0 # collectLabelsAndRewrite

  # Flow call 0xb0 # dumpOps
  # Flow end
  # init start/top of mcode
  Stack push 0x06
  Stack push 0x05
  Heap retrieve
  Heap store
  Stack push 0x07
  Stack push 0x05
  Heap retrieve
  Heap store

  # initialize labels
  Flow call 0xf0 # asmCode


  # reset top of mcode and run asmCode again
  Stack push 0x07
  Stack push 0x06
  Heap retrieve
  Heap store
  Flow call 0xf0 # asmCode

  Flow call 0x130 # dumpELF
  Flow return
# }

スタックマシンというつらさはありますが、call 、 ret やコメント、インデントを工夫することでそれなりにまともな見た目でプログラミングできるようになります。

開発

方針

結構プリミティブなコマンドが多く、そのままアセンブラにできそうなのでだいたいパース→機械語生成のシンプルな流れでやります。ただしラベルの扱いが難物です。プログラムを一度全て走査しないとジャンプ先のラベルがどこにあるか分かりませんし、一旦マシン語を生成しないとバイナリ内のラベルの位置が分かりません。それらを勘案して、以下の流れでコンパイルします

パース

ヒープに仮想命令を並べる

ラベル走査（リネーム）

ラベルの出現順に名前を振る。メモリ内でジャンプとラベルの対応がとれる

マシン語仮生成

ラベルの位置を決めるためにマシン語を生成する。ジャンプ先アドレスは仮

マシン語本生成

決まったラベルの位置に基いて正しいマシン語を生成する

ELF出力

マシン語列にELFのヘッダをつけて出力する

連想配列とかがなくて苦しいのでラベル走査の段はちょっと苦労しました。

その他、細かな点で仕様が変わってたりします。

値は64bit整数とする
- 任意長整数からの変更
ラベルは2進数の整数としてパースする
- あとで考えたら st と sst が同じ値になってしまうのでNGだった
スタックが底をついたら未定義動作とする
- 確保してないメモリ領域にいくので多分SEGV
未初期化のヒープにアクセスしたら未定義動作とする
- mmap で確保してるので0が返るのかな？
readchar 、 outchar は任意のオクテットを扱えるものとする
- バイナリを扱うのに必須
- 逆にUnicodeのコードポイントとかは扱えなくなった
readchar 、 readnum はEOFにあたったらヒープに値を保存しないものとする
- ファイルの末尾まで読みたいのでエラーだと困る

主にcharの扱いの問題で既存の処理系が使えないのでネットに転がっていた処理系にパッチを当てて使っていました。どこで拾ったか覚えてないのと、確かライセンスが明記されていなかったのでこれは公開できないやつですね。ブートストラップに必要な処理系が世の中に存在しないという残念なことになってしまいました。

実装

ELFヘッダ

一番最初に作ったのはELFヘッダの出力でした。

Wikipediaやリンカ・ローダ実践開発テクニックを見ながらフィールドを埋めていきましたが、まあまあつらかったです。 Program Headerで機械語だけをメモリにロードして実行しようとしたらどうしても動かなくて、慣例に従ってELFファイル全体をロードしたら動いたりと、「よく分からないけどこうしたら動く」状態になりました。カーゴカルトですね。

ELFをいじいじしてもなんとかEXEを作れるのが精一杯だったのでlibcだとかのリンクが必要なものは使えそうにありませんでした。コンパイラは頑張ってマシン語を並べていく方針でいきます。

パース

ELFが作れるようになったら次はパースです。これはまあ、手慣れてるので特筆することはないです。界隈の人ならWhitespaceの文法を一瞥すればそれを受理するオートマトンが勝手に生成されると思うのでそのまま実装するだけです。

パースのコードを書いたら、一旦パースしたコマンドをそのまま push とか readchar とかの文字列で出力するようにしました。これでパーサ（と自作アセンブラ）のデバッグをします。

メモリ設計

データ構造とかそういうのがないのでメモリの何番地を何に使うかは事前に計画しないと破綻します。コンパイラのコードのコメントから抜粋すると、以下のようなレイアウトにしました。

# Heap layout
#      0/1            1/1
# +----------+--------------------+-
# | readchar | parse number/label |
# +----------+--------------------+-
#          2/1          3/1            4/1             5/1               6/1            7/1
# -+--------------+------------+-----------------+---------------+----------------+--------------+-
#  | start of ops | top of ops | start of labels | top of labels | start of mcode | top of mcode |
# -+--------------+------------+-----------------+---------------+----------------+--------------+-
#        8/l       8+l/m     8+l+m/n
# -+------------+--------+--------------+
#  | parsed ops | labels | machine code |
# -+------------+--------+--------------+
# where ops forms | op | arg |
# ops:
#  0x00 push
#  0x01 dup
#  0x02 copy
#  0x03 swap
#  0x04 discard
#  0x05 slide
#  0x10 add
#  0x11 sub
#  0x12 mul
#  0x13 div
#  0x14 mod
#  0x20 store
#  0x21 retrieve
#  0x30 label
#  0x31 call
#  0x32 jump
#  0x33 jz
#  0x34 jneg
#  0x35 return
#  0x36 end
#  0x40 outchar
#  0x41 outnumber
#  0x42 readchar
#  0x43 readnumber

0, 1番地は作業用。それ以降に可変長データへのポインタ、可変長データの実体が並びます。可変長データはパースしたコード、プログラム中に含まれるラベル一覧、機械語の3つがあります。

今回の作業はデータレイアウトを正しく設計するのが一番の鬼門でした。それが決まったあとはわりとすんなり進みました。まあ、データレイアウトを決めるときに実装のことも考えないといけないからというのもあります。

ラベル設計

プログラム中で扱うラベルはグローバルな名前空間しかないので工夫しないとバッティングして破綻します。

関数のラベルには 0x10 、 0x20 … と16の倍数を割り当て、関数内で下1桁を1づつインクリメントして使ってました。いくつか、関数内での分岐が多くて16個以上のラベルを使ったものがありましたが、それは次以降の関数のラベルをずらすことで解決しました。

ラベルのコンパイル

既に少し説明しましたがラベルの扱いが手に余りました。まず、ラベルは任意長の s と t の文字列として与えられます。それを64bitの符号なし整数にとしてパースします。これだと実は情報に欠損があるのは既述のとおりですが、一旦忘れましょう。

次にラベルを出現順のインデックスでリネームします。これはlabelやjumpなど全てのラベルを扱うコマンドから拾います。例えば以下のプログラムであれば

Flow call 0x00
Flow end
Flow label 0x00
Stack push 0x02
Stack push 0x08
Heap store
Stack push 0x03
Stack push 0x08
Heap store
Flow call 0x10

ラベルを出現順に並べるとこうなります。

0x00
0x00
0x10

これはこうリネームされます。

0x00 -> 0
0x10 -> 1

そしてラベル一覧のところにも記録します。

  0      1
+------+------+--
| 0x00 | 0x10 |
+------+------+--

こうすることで、「ラベル一覧内のインデックス」 = 「リネームされたラベル」にできます。

あとはラベルをみつけたら、

ラベル一覧にラベルがある → そのインデックスにリネーム
ラベル一覧にラベルがない → ラベル一覧にラベルを追加し、そのインデックスにリネーム

という処理を繰り返せばラベルの下処理は完了です。

一度下処理が終わればラベル一覧内のデータは不要になるのでマシン語内のポジションの確定に再利用します。 labelコマンドのマシン語生成時に、現在のマシン語のtop（要はマシン語内でのポジション）をラベル一覧の自分のラベルのセルに記録します。そしてジャンプ系コマンドのマシン語生成時にここからラベルのマシン語位置を読み取って、現在のマシン語topと引き算して相対アドレスを算出します。ジャンプ系コマンドの方がラベルより後にくることもあるのでこの走査を二回やれば確実にアドレスを計算できることになります。これが仮生成、本生成と呼んでいるものです。

機械語の生成

ほとんどのコマンドはアセンブラ数命令で表現可能なのであまり困りませんでした。ただし、先にランタイムを設計しておく必要があります。

ランタイム

今回はLinuxで動けばいいやの気持ちだったので雑に実装します。必要そうなのはWhitespaceで使うスタックとヒープ、スタックのトップを指すポインタとヒープのベースを指すポインタ、コールスタックです。コンパイラのコメントから抜粋するとそれぞれこういう設計です。

## runtime architecture
# runtime heap map
#
# +------------+-------------+-   -+---------------+
# | ws heap -> | ws stack -> | ... | <- call stack |
# +------------+-------------+-   -+---------------+
# registers
#     rbp ... base of ws heap
#     rbx ... top of ws stack
#     rsp ... ordinal rsp.
#   and some registers are used to hold temporal values
# values
#   all values are 64-bit

コールスタックとrspは普通のやつそのまま、Whitespaceのヒープとスタックはmmapでそれぞれ確保します。スタックとヒープを指すポインタに rbx と rbp を選んだのはシステムコールを呼んでも保存される汎用レジスタで、命令にエンコードしたときに短いものだからです。スタックのポインタに rbp を使えよって突っ込まれるかもしれませんがコールスタックとは逆向きにスタックが伸びる設計にしてしまったので気にせずにヒープ用に使っています。

mmapやread、write、exitのシステムコール番号はこちらのまとめから拾いました。どのレジスタにどの値を入れればいいのかも載ってたので分かりやすかったです。mmapに渡すフラグやプロテクションフラグなどはLinuxのヘッダファイルから読みとりました。

コマンドと機械語の対応

あんまり難しいことはやってないです。例えばpushコマンドならこうです。

# mov QWORD PTR [rbx], arg
# 48 c7 03 xx xx xx xx
Stack push 0x48
Stack push 0xc7
Stack push 0x03
Stack copy 3
Heap retrieve
Flow call 0x110 # decodeLE
Stack push 7
Flow call 0x120 # storeMCode
# add rbx, 0x08
# 48 83 c3 08
Stack push 0x48
Stack push 0x83
Stack push 0xc3
Stack push 0x08
Stack push 4
Flow call 0x120 # storeMCode

これがreturnコマンドとかになるともっと簡単ですね。

# ret
# c3
Stack push 0xc3
Stack push 1
Flow call 0x120 # storeMCode

マシン語はhttps://godbolt.orgにアセンブラを打って取得しました。

ここで苦労したのが readnum と writenum です。他は数命令で済むのにこれらは数十命令あります。頑張って実装しました。数十命令ですがこれでもサボっていて、符号の扱いは未実装です。

特段アセンブラのデバッグ環境は用意しなかったのでWhitespaceコンパイラを動かして挙動が変だったらバイナリをデバッグして…というようにしました。つらいですね。

苦労した点とか

まあまあ大変だったので色々掃き出します。

セマンティクスが不明

公式サイトに繋がらなくて、正しい情報を集められませんでした。特に苦労したのがslideコマンドです。私が手元で使った処理系も作者によるIdris実装もバグっていて、WebArchiveからオリジナルの実装を掘り出してようやく理解できました。

正しいELFの吐き方が分からなかった

「Linuxで動く最小のELF」とかがあれば使いたかったんですが（あんまり熱心に検索しなかったのもあって）見付からず、試行錯誤しながら生成していきました。

バイナリエディタで開いて1バイトずつ指差し確認してデバッグしていきました。既存のELFもいくつか眺めたのですがプログラムをロードするアドレスが様々で面白かったです。

生成されたバイナリのデバッグが大変

今回生成するのはEXEなのと、労力削減のためにセクションヘッダを生成しなかったのでシンボルなしでデバッグする必要がありました。シンプルにつらいですね。

ところでgdbで機械語をデバッグするTipsが少し得られました。

layout asm → 今実行しているアセンブラを表示する
starti → プログラムを実行し、アセンブラの一番最初の命令でbreakする
stepi → アセンブラ1命令実行する
info registers → レジスタの中身を表示する

最終的に info registers を毎回打つのはやってられないのでgdb dashboardを使いました。

末尾の数コマンドの実行でSEGV

現象としては分かりやすくて、ELFの指定したファイルサイズを越えた箇所にアクセスしています。しかし現象が分かっても原因は全然分かりませんでした。 ELFの生成コードの問題を疑ったのですが、ELF生成とは関係なくマシン語の長さをデバッグ出力してみたら正しそうなのでお手上げでした。結局、マシン語サイズを適当に水増ししてごまかしました。

しかし今になってよく考えたらメモリにロードするときにELFファイルのヘッダごとロードしてるのでそこで100byteくらい想定より長くなってるのかもしれませんとなると、末尾の数コマンド（outcharがあるのでマシン語にすると長め）+ 最後のexitの呼び出しで100byteくらいありそうなので納得ですね。あとで修正しよ。

第2世代コンパイラのデバッグが大変

whitespaceで書かれたコンパイラを第0世代、それを使って自身をコンパイルしたものを第1世代、第1世代を使ってwhitespaceで書かれたコンパイラをコンパイルしたのを第2世代と呼ぶことにします。完全なセルフホストコンパイラであれば第1世代と第2世代はバイナリレベルで完全一致します。

第1世代コンパイラはなんとなく動いてるけど、第2世代コンパイラを生成するとバイナリレベルで一致しないし変な挙動をするときのお話。直接書いたコードがバグっている訳ではないのでかなり厳しいものがあります。第2世代の挙動を見て、バグっていそうな第1世代のコンパイラの怪しいところに検討をつけて、そこの部分を生成する第0世代のコンパイラの該当箇所を血眼になってデバッグします。正直、自分が今何をデバッグしているのか分からなくなります。

gdbで第1世代をデバッグできたらよかったんですが先述の通りシンボルがないのと、コンパイラは大きくてバイナリ内でバグってる箇所が分かったとしてもソースコードとの対応が中々とれないので難航しました。

結局、バグが再現するコードをどんどん縮めていって小さなバイナリでデバッグしました。

因みにバグっていたのは負の値のリテラルのパースでした。コンパイラ内では1箇所しか負の値を使っていたので「おおむね動くけどたまに変なコードを食わせるとバグる」という挙動になりました。つらい。

結びに

Whitespaceでセルフホストコンパイラを作ろうというfoolなことを思い付いたのは先に引用したEdwin Bradyのツイートを見たときでした。最初はWhitespaceにコンパイルする関数型言語でも作ろうかと思ってたのですが、脳内で色々こねくり回している間にエイプリルフールにWhitespaceのセルフホストコンパイラを作るという発想に至りました。

計画は随分前からあったものの、実際に取り掛かったのは3月中だったので時間が足りず、有給を2日使ってようやく3月31日の22時というギリギリの時間に完成しました。有給まで使って何してるんでしょうね。我ながらfoolだなと思います。

今年はもう終わりましたが来年はみなさんもfoolなことやっていきましょう。

今回のコンパイラのアセンブラとアセンブリのコードはこちらに置いておきます。ライセンスはGPLv2とします。

https://gist.github.com/KeenS/6081b0c802a4e575ddbacb1930680870