話のネタのまとめ

[sxarp]

このリポジトリの概要

なにをやっているか

GolangでCのコンパイラを書いてる
低レイヤを知りたい人のためのCコンパイラ作成入門に触発された

なぜやっているのか

低レイヤーの勉強&Golangを手に馴染ませたい

ここに書かれてる内容

• コンパイラを書くにあたって考えていること
  • 壊れにくいコードについて
    • 型による制約
    • データ駆動とDSL
    • Fail Fast
• その他の開発ネタ
  • Golangに特有な話
  • 開発環境

コンパイラを書くにあたって考えていること

壊れにくいコードについて

コードを書いて開発してるとき、ほとんどの時間はバグとの戦いに費やされている(気がする)。
体感的には、5%コードが書いてる時間で、残りの95%がデバッグ。
しかし、最善手を打つと、デバッグにかかる時間を抑えられる=>5%でコードを書く、15%でバグりにくい設計を考える、15%でテストを書く、残りの15%がデバッグ=>トータルで50%の所要時間に！

つまるところ、テストや設計でバグを事前に捻り潰すのが大事。

バグの予防としてこのレポジトリ内で行ったていることをいくつか揚げる:

• 型による制約
• データ駆動とDSL
• Fail Fast

型による制約

• プリミティブな型、例えばstringなどを使わない。
• 不正な入力は型でコンパイル時にリジェクトする

アセンブリコードを吐く部分を例に上げて説明する。

アセンブリコードを書く部分を、素朴にやると、↓のような書き方となる。

asmCode := "        mov rax, 42"
asmCode += "        ret"

でも、この書き方は脆弱でぶっ壊れやすい。例えば↓のようになるとただちにバグってしまう:

asmCode := "        mob rax, 42"

なので↓のように書けるようにした:

acode.Ins(asm.I().Mov().Rax().Val(42))

ここで、各メソッドのシグネチャーはそれぞれ以下のようになっている:

asm.I => func() Ini
Ini#Mov => func() Oped
Oped#Rax => func() Dested
Dested#Val=> func() Fin
code#Ins => func(Fin)

code.Insは、完成されたインストラクション(Fin型)しか引数として受け付けないので、不完全なインストラクション、例えばasm.I().Mov().Rax()をcode.Insを突っ込んでも、コンパイラに弾かれる。

データ駆動とDSL

データ駆動

データ駆動とは、ロジックを出来るだけ薄くして出来るだけデータを使ってコードを書くことを指す。
データ駆動が良い理由は、機能の追加や変更をするとき、データの修正だけで済むので安全だからである。
一方で機能追加の際にロジックを弄る場合は、ロジックはある種何でもありなので、コードを壊す危険がある。
データ駆動は表現出来ることが抑えられているので事故が起きにくい。

• このリポジトリでの例: トークンナイザーの生成
  文字列を字句解析するとき、素朴にやると以下のようなコードになる:

for {
	if len(s) == 0 {
	break
	}
	if s[0] == "+" {
		tokens = append(tokens, PlusToken)
		s = s[1:]
		continue
	}
	if s[0] == "-" {
		tokens = append(tokens, MinusToken)
		s = s[1:]
		continue
	}

}

新しいトークンのタイプを追加する場合、if文を追加していくことになるが、それ以外なんでも追加しようと思えば出来るので危険。例えば微妙に間違った形のif文とか、あるいはおもむろに無限に終わらないfor文を回し始めることだって可能。

一方でデータ駆動だと↓のような書き方となる。

var TPlus TokenType = TokenType{literal: "+"}
var TMinus TokenType = TokenType{literal: "-"}
var TLPar TokenType = TokenType{literal: "("}
var TRPar TokenType = TokenType{literal: ")"}
var TMul TokenType = TokenType{literal: "*"}
var TDiv TokenType = TokenType{literal: "/"}

var TokenTypes = []*TokenType{&TPlus, &TMinus, &TInt, &TLPar, &TRPar, &TMul, &TDiv}

func Tokenize(s string) []Token {
	return tokenize(TokenTypes, s)

}

https://github.com/sxarp/c_compiler_go/blob/master/src/tok/tokenizer.go#L96

var TPlus TokenType = TokenType{literal: "+"}を追加していく定形作業なので事故が起きる余地が少ない。
また、TokenTypesから、トークンナイザーを生成する関数tokenizeは、単体テスト可能な点に注意。
if文を追加する場合と違い、トークンタイプを追加するたびにテストを追加しなくても良い(追加しても良い)。
ロジックにデータを流し込むことで、処理を構成出来れば、ロジックを薄く出来て単体テストもしやすくなり、結果として壊れにくいコードとなる。

DSL

データ駆動と考え方は同じで、表現力を絞ることにより事故が起きにくくなるようにする。
コード上に、必要な自由度のみが残り、余計なものが入らないので事故が起きにくくなる。
ただし、対象となるドメインの本質的な難しさは無くならない(本質的な難しさに集中できるとも言える。)

このリポジトリの例として、パーサーコンビネーターを使ったパーサーを生成するDSLを紹介する:

パーサーを以下のような感じで定義できる(実際は少し違うが/ノードをASTに追加するかどうかもオプションで取る)

mul := OrId()
add := OrId()
term := OrId()

termPlusMul := AndId().And(&term).And(Plus).And(&mul)
termMinusMul := AndId().And(&term).And(Minus).And(&mul)
add = add.Or(&termPlusMul).Or(&termMinusMul).Or(&term)
// add = term + mul | term - mul | term

termMulMul := AndId().And(&term).And(Mul).And(&mul)
termDivMul := AndId().And(&term).And(Div).And(&mul)
mul = mul.Or(&termMulMul).Or(&termDivMul).Or(&add)
// mul = term * mul | term / mul | add

parTerm := AndId().And(LPar).And(&mul).And(RPar)
term = term.Or(&parTerm).Or(num)
// term = ( term ) | num

return AndId().And(&mul).And(EOF)
// mul EOF

DSLはAndとOrの実装に相当する。
パースのテスト。

再帰を表現するために、AndとOrにはパーサーのポインターを渡すようにしている。

このDSLは正しく書かないと、すぐ無限ループに入ったり、トークン列を最後までパースできなくなったりするので、DSL化したことで、問題が簡単になったわけではない(正しい生成規則を見つけるは難しい)。

Fail Fast

ちょっとでもおかしなことが起きてたら、直ちに例外(panic)を投げるようにしている。
これは本番のコードでも同様にやるべきだと考えていて、できるだけ早い段階で分かりやすい例外を吐いてクラッシュさせる方が、テスト時やデプロイ後の早い段階で検知/修正できるので、良いと思っている。

その他の開発ネタ

• Golangに特有な話
• 開発環境

Golangに特有な話

直和型がない件

パーサーを書く際には型的には以下のような感じにするのが自然:

func([]token) (Fail | AST, []token) 

しかし、Goだと、Fail | ASTのような型は素朴には定義できない。
ワークアラウンドとして、AST型で定数としてFailを定義してお茶をにごした。

var TFail ASTType = ASTType{}
var Fail = AST{atype: &TFail}

https://github.com/sxarp/c_compiler_go/blob/master/src/psr/parser.go#L21-L22

これでそんなに困っていはいない。

開発環境

dockerの中に全てを封じ込めている。
git pullし、make startし、make testでテストが回るようになっている。
GOPATHがない環境でも安心。