sedをターゲットアーキテクチャとしてコンパイラを自作する (自作言語 Soil)
nishishinjuku-ctf アドベントカレンダー2日目
イントロ
皆さんは sed を使っていますか？ 「テキストの置換に使うよ〜」とか、「初めて習得した言語です」とか、「メインで使ってるエディタだね！」とか色々な反応が聞こえてきます。でも、私にとっての sed はランタイム環境です。
sedlisp というプロジェクトに触発され、「sedはチューリング完全なのだから、コンパイラのターゲットになるはずだ」と考えました。 そこで本記事では、独自の高級言語 Soil を作成し、それを sed スクリプトにコンパイルして実行するまでの記録をまとめます。
リポジトリはこちら 👉 sed-compiler
この記事では、単なるネタに留まらず、実際にコンパイラとして機能させるまでの以下の工程を記録します。
- sedの基本機能を演算命令と見なす
- スタックフレームを文字列操作で実装する
- **中間表現(IR)**を設計してsedの記述を自動化する
- 独自言語Soilを被せて人間が書けるようにする
また、sedにデフォルトで用意されていない数値演算も合わせて実装していきます。言語の機能を強化していきつつ、途中で四則演算をソフトウェア的に実装するような感じで話を進めていきます。
最終的に、このようなプログラムがこのようなsedスクリプトにコンパイルできるようになります。
sedで「計算」をする
sedには演算機能がない
通常、プログラミング言語には「関数」「変数」「加減乗除」などがありますが、sedにあるのは「置換」「バッファ」「ジャンプ」というような低級な操作だけです。 ここでは、**sedというテキストエディタを「特殊な命令セットのCPU」**だと見立てて、無理やり計算の概念を構築していきます。
sedが具体的にどんな機能を持つのか、さらっと確認していきましょう。
最低限のsedの知識
- ジャンプラベル - sedにおける制御構文
if文や関数の実装、更にはループ処理などで重要になります。
: label <-+
... |
b label --+
- HoldスペースPatternスペース - sedにおけるメモリ
今回は、関数のスタック（ローカル変数を保存する領域）の実現のために使います。
+-------------------+
| pattern space | <= メインの作業スペース
+-------------------+
^
| x,h,H,g,Gなどのコマンドでスイッチしたりコピーしたり追加したり...
v
+-------------------+
| hold space | <= 作業内容を一旦保存する場所
+-------------------+
なかなかイメージが湧きづらい概念だと思うので、sed用のdebugger(desed)を使ってどうなっているのか確認してみましょう。
desedでHold/Patternスペースを確認
-
s/.../.../- sedにおけるデータ操作
sedで一番使われる機能です。
s/<置換したいパターン>/<置換後のパターン>/
といった感じのやつです。丸括弧でパターンを囲むと置換パターンをグループ化できますが、最大で9個しか使えません
# パターングループを最大限使ったプログラム
s/\(.*\):\(.*\):\(.*\):\(.*\):\(.*\):\(.*\):\(.*\):\(.*\):\(.*\):/\1\2\3\4\5\6\7\8\9/
2進数と文字列置換による加算の実装
言語も何も構築されていない段階でまず、加算器を実装してみました。init commitを見ればadd.sedが作られていることがわかるでしょう。
直感的に扱いやすいと感じたため数値のデータは二進数で管理しています。ピュアsedで実装したのは加算器だけで、他の演算はすべて自作言語を使って実装しています。
関数を実現する「スタックフレーム」
sedには関数がない
先程も言ったとおり、sedには関数なる概念がありません。加算はともかく、減算乗算除算の実装に関数が使えないのはとてもしんどいです。このセクションでは、一般的に関数を実現するために使われるようなスタックフレームの概念を参考にしてsedというランタイム上で関数を再現するためのアイデアを練っていきます。
Hold/Patternスペースを使ったメモリ管理
スタックフレームの設計図
※ 上の図では、対応する概念が同じ色で表現されています。
- 🟢: 緑で囲まれた部分に引数、ローカル変数が入る
- 🟠: オレンジの部分がスタックフレームの単位
- 🟣: 紫の矢印はスタックがcallされた際に伸びる向き
- 🔴: 赤の部分に、返るべき命令の位置情報が保存される
スタックフレームは関数が呼ばれたときにローカル変数や渡された引数などが保持される領域です。
関数の呼び出し(call)が発生するとスタックにスタックフレームがpushされ、returnされると最上部（最後にpushされたスタックフレーム）がpopされます。
スタックフレームには更にローカル変数、引数情報以外に含めるべき情報があります。
関数から値が返る際、次に実行すべき命令は呼び出した命令の直後である必要があります。そのためには、各スタックフレームごとにその呼び出し元の直後のアドレスが記録されている必要があります。
上の画像のデータ構造をもとに、PatternスペースとHoldスペースをうまい具合にメモリとして扱い、関数に渡された引数、ローカル変数を管理していきます。
中間表現(IR)の作成
sedを書くのは辛すぎる
関数を構築しようと思うたびに自分でsedを書くのはしんどいので、自動で行えるようにRustプログラムを書きます。
sedより一層高級なレイヤーの中間表現(Intermediate Representation:IR)を設けて、それをsedに変換する方針で解決します。
Wasm/Forth風のスタック指向IRの設計
今回、sedで作ったスタックフレームは特定の文字をデリミタとしてスタックフレーム同士を区切っているため(一般的なスタックフレームのようにサイズで区切っていないため)、スタックフレームの長さを自由に変更して問題ありません。(その代わりデータにデリミタ文字は含められない)
スタックフレームの伸び縮みが許容されるためIRはForthやWasm Text Format(WAT)のように、値をスタック指向に操作できるデザインにしました。(スタックフレーム内にスタックを作る)
スタック指向でデータを操作するってどういうことだ?と思った人は、以前私が書いた以下の記事を読んでみてください。
この段階でしっかりIRという概念を作ったことが後の実装のスムーズさにつながったと思います。
掛け算のIR上の実装
以下は掛け算をIRで実装したものです。掛け算は再帰的な操作を伴います。つまりsedで実装しようとするとめんどいです。でも今はIRを使えるので、sedの事情を気にすることなく簡単に実装できます
Wasm Text Format(WAT)で書くとするのなら、以下のようになるでしょうか。あくまで例のため動作確認はできていませんが、だいたい上のソースと似ているなーってことがわかれば大丈夫です。
上のIRはおよそ下のようなsedスクリプトに変換されます。
引き算の実装
上のセクションですでに加算と乗算は実装できました。後２つの基本的な演算は減算除算(引き算割り算)です。除算への準備も兼ねてまずは引き算について考えます。
二進数で負数を表現しようと考えたらまずどうするでしょうか？愚直な考え方としては最上位のビットで正負を表現というのが普通でしょう。でもこれだと0が±0の二通りで表現できてしまいます(4bit で考えたら0000b == 1000b)。
4bitに制限して考えるとどうでしょう。下のように数が割り当てられたらうまく行きそうですよね！？
こうすれば、0が二通りで表現されることがありません（0000b != 1000b）。
２の補数表現
上の図で0110bの負数を考えたいときは、真ん中の対照線で折ったときに重なる部分を見れば良さそうです。
計算で求めるにはどうすればいいでしょう。オーバーフローを一旦無視して、10000b - 0110bを考えたら良いでしょう！
ところで、bitを反転させた後と前を足すと常に(4bitなら)1111bになります。これは当たり前な結果です。
1001 --+ 1010 --+
! !
0110 <-+ 0101 <-+ (+
---------------------
1111 1111
(!はbit反転の意味)
さっきの10000b - 0110bを一般化したものf(x)を考えると、、、
x:4bit int
x + x! = 1111b // bitを反転させた後と前を足すと常に4bit
x! = 1111b - x
f(x) = 10000b - x
= 1b + (1111b - x)
= 1b + x!
こうしてめでたくマイナスの数を求めるためにマイナスを用いなくてもよくなりました。(加算(+)と反転(!)さえ実装すれば引き算が実装できる!)
やっと引き算が実装できました。
苦労話
ここでの考え方自体は間違っていないのですが、補数を求めるsedのプログラムに偶数を入れると誤って返り値に処理中に使うデリミタが混じるバグがありました。
このミスのせいで後々とんでもない時間を失うことになります。 テストはしっかり作ったほうが良いです。
自作言語「Soil」
IRを書くのは辛すぎる
残る演算、除算及び剰余の計算のため、試行錯誤しつつ、pythonなどの実装を参考にしてIRで実装しようと考えていました。
しかし、それでもまだスタックの操作を意識する必要があり、除算などの複雑なアルゴリズムを書くには低レベルすぎました。
そのため、IRよりもさらに高級な言語を作り解決します。sedを埋め込める必要があるので、それを意識しつつ実装していきます。
chumskyを使うパーサー
言語を作ると言ったときには、色々なやり方がありますが、今回私は既存のパーサーコンビネータを利用することにしました。
Rustで書いているのでRust製のものを選びます。色々な選択肢の中で私はchumskyを選択しました。
今年触って最も感動したソフトウェアといっても過言ではないです。chumskyはそれ自体がRustの型システムをふんだんに使い作られていて、ある程度使い方側わかればとても簡単に、そして安全にパーサーを構築することができます。今度別記事にまとめられたらいいと考えています。
Soilの文法
Rustライクな見た目の言語です、まだできたばかりで引数の個数すらチェックされない代物です。何かコンパイルでミスっている場合は、自分の力で何とかする必要があります。
関数定義
複値返却ができたりします。引数の宣言部分に括弧が無いのは特徴的かも。
fn func_name a:bit32, b:bit32 -> bit32, bit32 {
...
return a, b;
}
変数
これも、複値返却ができたりします。
let a = 100;
let b = 3;
let d = 0;
let m = 0;
d, m = divmod(a, b);
条件分岐
特に特徴的なことはない。
if expr {
...
} else {
...
}
埋め込みsed
Soil言語でカバーできない機能をsedで実現する際に使います。
書くためにはスタックフレーム上で引数がどのように扱われるか理解する必要があったり、ホールドスペースが使えないという制約があります。
fn shift_right1 a:bit32 -> bit32 {
// ${ ... }$ で生のsedコマンドを埋め込める
sed ${
"s/\\(~[01]*\\)[01]/\\1;/"
}$
}
while forなどはありませんが基本的な計算はとりあえずこれらで実現できます。
除算の実装 演算の書き直し
ある程度パーサーが出来上がってきたので、パーサー-IR間を接続してみました。
言語の機能はまだ不完全ですが、今までの演算を書き直したら、すべて期待どおりに動きました。
足し算
Soilの埋め込みsed文法を利用しています。
引き算
二の補数表現を使っています。
掛け算
先程あげたIRと比較してもだいぶシンプルになっていることがわかります。
割り算
Soilを作ったことによって圧倒的に簡単に書けます。
おまけ：最大公約数 (GCD) の計算
再帰的なプログラムを更にテストとして追加したいと考えました。
私が正の整数を扱う再帰的な題材として最初に思い浮かぶのはユークリッドの互除法です。
他にも正の整数&&再帰の題材を知っている方がいたら教えてくださるとありがたいです。
最適化への挑戦
gcdをSoilで実装して思ったのはこのコンパイラの出力するsedはとにかく遅いということでした。gcd(x, y) == 1となるようなケースは絶望的な遅さです。
sedのせいにしない場合、遅い理由は以下のようなものがあると考えられます。
- 四則演算すべてのもととなる加算機が遅い
- リターンアドレス解決のマッチセクションに構造的な問題がある
- コンパイル時に判明するローカル変数の初期化(を処理していない)
- IRの命令の最適化をしていない
etc..
ここからは、sed特有の制約の中でいかに処理速度を稼ぐかという、泥臭い最適化の話になります。
1.四則演算すべてのもととなる加算機が遅い
四則演算すべてにおいて使われている加算機の実装は最初に作って以来ほぼ変更していません。関数に切り分けているので一応使えるという状況ですが流石に遅すぎます。コンパイラの問題ではないという理由で後回しにしていますが、基本的な部分なので改善の余地があります。
2.リターンアドレス解決のマッチセクションに構造的な問題がある
関数が返る際にどこから呼ばれたのかをスタックフレーム内に書かれたリターンアドレスの情報をもとに巨大なマッチ文で処理していて、最悪ケースではすべてのパスを調べていました。
すなわち、funcAからの返り道なのに、funcA以外を呼び出している場所に返る可能性も含めて検索してしまっている状態です。これは普通のアーキテクチャをターゲットにしている場合には生じえない問題です。しかし、sedでは何かアドレスをもとにしてある命令までジャンプするという命令は存在しないために泥臭くマッチ文相当の処理で解決する必要があります。
この問題は根本的なマッチセクションの配置を見直して、関数ごとに分割することで、無駄なパスを通らないようにして解決しました。
リターンアドレス解決
3.コンパイル時に判明するローカル変数の初期化(を処理していない)
現状では生成物に以下のようなコードが見られます。
でもこれは、ただ初期化をしたいだけなので、
s/\(~[^\~]*~[^\~]*\)/\1~00000000000000000000000000000000~00000000000000000000000000000000/
とあるだけで十分です。うまい具合にコンパイル時に処理してあげたいです。
4.IRの命令の最適化をしていない
コンパイルの一連のプロセス、言語 -> 中間表現 -> sed、をよく観察してみると、中間表現によく現れる命令のパターンがあります。
例えば、以下のようなものです。
ありがちなパターン
local.set 1
local.get 1
call somefunc
何をしているかといえば、スタックをpopし、その値を変数にセット、更に変数の内容をもう一度スタックにプッシュして、関数呼び出しでそれを消費。
これは、変数に値を代入してからすぐにその変数を関数に引数として与える場合によく見られます。
先程の画像のIRは、以下のコードと対応しています。4とナンバリングされている変数は元々R_newという名前の変数です。
上の操作は、もしスタックのトップを消費せずに変数に値をセットする命令があれば、２つの命令を1つにできて省エネになります。そして、スタック指向の言語Wasm Text Format(WAT)にもそのような命令teeがあります。
このような命令の追加によってsedの命令を短縮したいです。
実装したい機能
cli機能
私以外の人も使えるようなインターフェイスを作りたいなと考えています。cliがエントリーポイントとなり、処理も追いやすくなると思います。
色々なデータ操作
今回は数値計算と関数の実現に特化した内容でしたが、sedの本来の威力は文字列操作です。文字列を簡単に操作できるようにSoil側のデザインも変えていく必要がありそうです。
型チェック
できたらいいなと考えています。
試してみたい人向けtips
実行してみる
リポジトリをクローン
git clone https://github.com/Tom-game-project/sed-compiler.git
cd sed-compiler
例えば、私がずっと使っていたデバッグ用プログラムbasic_operations.soilをコンパイルして動かす。
# いい感じの場所に移動
git checkout 7805e272b8653ab578bae035089ea9e08cfa1c90
cd sed-compiler
# コンパイルする
# 下のようにすると`sed-compiler/soil/basic_operations.soil`がコンパイルされて`sed-compiler/sed/basic_operations.sed`に出力される。
cargo test compiler_test02 -- --nocapture
# entry関数に引数を与え実行する
# - 標準入力で与える場合
echo ~00000111010110111100110100010101~00111010110111100110100010110001 | sed -f sed/basic_operations.sed
# - ファイルで与える場合
echo ~00000111010110111100110100010101~00111010110111100110100010110001 > in
sed -f sed/basic_operations.sed in
# 環境にもよると思いますが3,4秒かかって結果が出るはずです
# ~00000000000000000000000000000000~00000000000000000000000000001001~00000000000000000000000000001001;
もし、soilに少し変更を加えて再度コンパイルしたいなら、もう一度cargo test compiler_test02 -- --nocaptureをする。
エントリー関数に引数を渡す
entry関数がSoilのエントリーポイントとなります。c言語やRustのmain関数のようなものです。
例えば、以下のようにentry関数を書いたならば
pub fn entry a:bit32, b:bit32 -> bit32, bit32 {
let r1 = 0;
let r2 = 0;
r1, r2 = divmod(a, b);
return r1, r2;
}
このように、引数を渡します。
echo ~00000000000000000000000000101010~00000000000000000000000000001010 | sed -f sed/basic_operations.sed
引数を与えたい場合は、ファイルか標準入力かで与える必要があります。
引数の渡し方はエントリー関数の型によって違います。以下に示すよフォーマットのように渡す必要があります。
# `pub fn entry a:bit32, b:bit32 -> bit32, bit32, bit32` の場合
# すなわち、引数が２つの場合
f2 = lambda a,b : f"~{a:032b}~{b:032b}"
f2(42, 10)
# ~00000111010110111100110100010101~00111010110111100110100010110001
# `pub fn entry a:bit32, b:bit32, c:bit32 -> bit32, bit32, bit32`の場合
# すなわち、引数が３つの場合
f3 = lambda a,b,c : f"~{a:032b}~{b:032b}~{c:032b}"
f3(123456789,987654321, 42)
# ~00000111010110111100110100010101~00111010110111100110100010110001~00000000000000000000000000101010
desedで動きを見る
desedをinstallすると、どんな風に動作しているのかがわかります。
desedをinstallしたら
echo ~00000111010110111100110100010101~00111010110111100110100010110001 > in
desed sed/basic_operations.sed in
まとめ
役に立つとは到底思えないツールですが、生成物の見た目が割とエグいので気に入っています。
作った言語の名前は、Se(e)dを埋め込めるのでSoilです。
Discussion