「低レイヤを知りたい人のためのCコンパイラ作成入門」をやっている話

TL; DR

  • 「低レイヤを知りたい人のためのCコンパイラ作成入門」をやっている
  • 関数定義が動くようになった
  • 「低レイヤを知りたい人のためのCコンパイラ作成入門」はいいぞ

はじめに

1年ぐらい前にこれが公開されて、ずっとやりたいと思っていたがやれてなかったので今年の2月ぐらいから地道に進めていた。

www.sigbus.info

やっとこさ関数を定義して、関数を呼び出せるようになったのでここにいたるまでの振り返り

成果物はこれ

GitHub - sasurau4/9ccs

やって楽しいポイント

loxのときのように別の言語で実装しても良かったが、Cをほとんど書いたことがなかったので、紹介されている通りCで実装した。

assemblyとかレジスタはそもそもよく分かってなかったので、基礎の基礎から説明されてて楽しい。

tokenizeらへんはloxで一度通っているのですっと頭に入ってくる。再帰下降構文解析とBFNらへんは何度やっても人類の叡智という感じがする。

スタックマシンが実際にどうやって使われてるかもようやっと少し理解できた。

makeの使い方も触れるしよい。

途中に挟んであるコラムが面白いので、コンパイラを実際に作らないでも読み物として楽しむだけでも面白い。

Cの歴史も少し触るので、現在から見ると明らかに不自然に感じる文法が採用された時代背景や思想、普段使っているJSなんかが高級言語であることがなんとなく分かる。

ハマったポイント

どのへんにハマったかをつらつら書く

ここに取り上げていないものはREADMEに書いてある。

GitHub - sasurau4/9ccs

Cのコードで困ったら9cc本体を見れば雰囲気は分かるので、それでなんとかなる。

GitHub - rui314/9cc: A Small C Compiler

アセンブラで詰まったら付録1を見たり、Compiler Explorerと自分の出力したアセンブラを比較したりすると分かる。

Compiler Explorer

アセンブラは手で書き換えて、gdbで行実行しつつ、レジスタの中身を確認するとより分かりやすかった。

SIGSEGV

友人曰く、C言語名物らしい。

初めて出たとき、例のアレじゃんとテンションが上がった。

とはいえ、それも最初だけで、実装を進めていると頻繁に出て来る上に、デバッグが非常に困難なのでこれは嫌になるわけですわという気持ちになった。

デバッグが非常に困難というのは、こいつが出ると普段JSや他の言語なんかで使うprintなど一切の出力がされなくなる。

JSのthrow errorと同じように発生したソースのlineとなんで発生したかも出るだろうし、そこまでに実行されるprintfなんかの処理は出力されるだろうと油断していたのでこれには真顔になってしまった。

仕方ないので記憶の片隅からgdbというツールでデバッグ出来たはずと思い出し、それの使い方を覚えて、ある程度はなんとかなるようになった。

gdbは便利。もう手放せなくなってしまった。

このあたりを一通り踏んだので、Rustがsafeな書き方をしているとSegmentation faultが出ないというのがどれだけありがたいかを体感できるようになった。

インクリメントの前置と後置

トークナイザを実装しているときにインクリメントの後置と+=演算子が同じ意味だと勘違いしていて、トークナイザが上手いこと動かなくなった。

これは、JSでも同じ仕様

let x = 3;
const y = x++;

console.log(`x:${x}, y:${y}`);
// expected output: "x:4, y:3"

let a = 3;
const b = ++a;

console.log(`a:${a}, b:${b}`);
// expected output: "a:4, b:4"

let p = 3;
const q = p+=1

console.log(`p:${p}, q:${q}`)
// expected output: "p:4, q:4"

インクリメントの前置と+=が同じ意味になる。

フィボナッチ数列の実行速度の比較

関数定義ができるようになって、再帰フィボナッチ数列が動くようになった記念で、以前作ったlox compilerと実行時間を比較してみた。

以前のloxの記事はこれ

Rustでlox言語のinterpreterを作っている話 - sasurau4のブログ

まずはlox版のフィボナッチ数列の実装

fun fib(n) {
  if (n < 2) return n;
  return fib(n - 1) + fib(n - 2);
}

9ccsのフィボナッチ数列実装

fibonacci(x) {
    if (x < 2) return x;
    return fibonacci(x - 1) + fibonacci(x - 2);
}

実装されてる言語機能がほぼ一緒なので、実装もほぼ同じものになる。

こちらが実行にかかった時間

実行関数 9ccs lox compiler
fib(20) 0.002 sec 1 sec
fib(30) 0.04 sec 56 sec
fib(38) 0.6 sec 2721 sec
fib(40) 1.5 sec -- (長すぎて未測定)
fib(50) 191 sec -- (長すぎて未測定)

9ccsはtimeコマンドで計ったのに対して、loxは実装したclock関数で測定していて、双方とも1回ずつしか実行していないので、正確な比較ではないが、ざっくり比較でもこれぐらい差がある。

引数が38と中途半端なのはloxの39の実行終了に時間がかかりすぎて、途中で打ち切ってデータが取れた最後の値が38だったため。

9ccsの方が圧倒的に早いが、それでもこの実装だと引数60で30分程度はかかりそうな気配がする。計算量の爆発怖い。

テスト

フィボナッチ数列で比較するために久しぶりにlox compilerを動かしたがfor文が動かなくなっていて悲しかった。

Cコンパイラ作成入門ではきちんとテストケースを書いて、毎回テストケースが通るように実装しているので、こういうことがない。

テスト書くの大事。

最後に

セルフホストまでは行けるかわからないが、本に紹介されているテストケースをCで書き直すまではやりたい。

とりあえず、ポインタが扱えるようになるとぐっとCっぽくなる気がするので、次はそれをやる。

おしまい。