こんにちわ、んだです。
今回も『Writing A Compiler In Go』でございまして、前回はcompilerまで触れましたので、いよいよVirtual Machineについてです。
What Is a Virtual Machine?
まずは、Virtual Machineについて軽く触れておきます。
本書での説明を読んでみましょう。
A virtual machine has a run loop that goes through the fetch-decode-execute cycle, just like a computer. It has a program counter; it fetches instructions; it decodes and executes them. It also has a stack, just like a real computer. Sometimes it has a call stack and sometimes even registers. All built in software. p.19
CPUは、 fetch-decode-execute cycleを回すことでプログラムを実行します。
VMの挙動も同じです。
違うのはCPUはハードウェアですが、VMはソフトウェアである点です。ソフトウェアであることで、異なるハードウェアやOS間で移植性を持つことが可能になります。
素晴らしいアイディアですね。
TestCode
いつも通り、まずはテストコードから眺めていきましょう。
// vm/vm_test.go
func TestIntegerArithmetic(t *testing.T) {
tests := []vmTestCase{
{"1", 1},
{"2", 2},
{"1 + 2", 3},
}
runVmTests(t, tests)
}
func runVmTests(t *testing.T, tests []vmTestCase) {
t.Helper()
for _, tt := range tests {
program := parse(tt.input)
comp := compiler.New()
err := comp.Compile(program)
if err != nil {
t.Fatalf("compiler error: %s", err)
}
vm := New(comp.Bytecode())
err = vm.Run()
if err != nil {
t.Fatalf("vm error: %s", err)
}
stackElem := vm.StackTop()
testExpectedObject(t, tt.expected, stackElem)
}
}
パーサーを呼び出し、ASTを生成。 ASTをコンパイラに渡して、bytecodeを生成。
VMがbytecodeを処理した結果、StackTopが期待されたオブジェクトであることをテストしていますね。
Virtual Machine
では、具体的にVMの実装を確認していきましょう。
VM struct
まずは、VM structです。
type VM struct {
constants []object.Object
instructions code.Instructions
stack []object.Object
sp int
}
constantsは、定数を格納します。
今回のターゲットの式は、1 + 2ですが、constantsには、1と2が格納されます。
spはスタックポインタです。現在のスタックのトップの番号を指しています。CPUの構造については、名著『コンピュータシステムの理論と実装』の前半戦で学んだので、そこまで苦労はありませんでした。
Run
次に、本体であるRunをみていきましょう
// vm/vm.go
func (vm *VM) Run() error {
for ip := 0; ip < len(vm.instructions); ip++ {
op := code.Opcode(vm.instructions[ip])
switch op {
case code.OpConstant:
constIndex := code.ReadUnit16(vm.instructions[ip+1:])
ip += 2
err := vm.push(vm.constants[constIndex])
if err != nil {
return err
}
case code.OpAdd:
right := vm.pop()
left := vm.pop()
leftValue := left.(*object.Integer).Value
rightValue := right.(*object.Integer).Value
result := leftValue + rightValue
vm.push(&object.Integer{Value: result})
}
}
return nil
}
やっていることは、シンプルです。
OpConstant
vm.instructionsからOpcodeを取り出し、OpConstantである場合は
①定数のインデックスを取得する
constIndex := code.ReadUnit16(vm.instructions[ip+1:])
[ip+1:]としているのは、定数がオペコードの直後、つまりip+1位置のバイトからだからですね。
② 定数プールから値を取得してpush
今度は、constantsから実際の定数を取得してpush
err := vm.push(vm.constants[constIndex])
OpAdd
① 式の左右の値をpopする
right := vm.pop() left := vm.pop()
② 足してpush
あとは、足し算してpushです
result := leftValue + rightValue
vm.push(&object.Integer{Value: result})
PushとPop
続いて、PushとPopについてみていきましょう。 スタックマシンは、PushとPopを行うことで計算をしていきます。
PushとPopの詳細に入る前には、まずはVMの初期状態について確認しましょう
VM New
stackは、StackSize分だけobject.Objectのスライスですね。 そして、sp=スタックポインタの初期値は0です。
func New(bytecode *compiler.Bytecode) *VM {
return &VM{
instructions: bytecode.Instructions,
constants: bytecode.Constants,
stack: make([]object.Object, StackSize),
sp: 0,
}
}
push
では、pushについてみていきましょう。
func (vm *VM) push(o object.Object) error {
if vm.sp >= StackSize {
return fmt.Errorf("stack overflow")
}
vm.stack[vm.sp] = o
vm.sp++
return nil
}
引数として与えられたObjectを、現在のspの位置のstackに積んでいますね。 詰んだ後は、spを進めています。
pop
popは、こんな感じです。
func (vm *VM) pop() object.Object {
o := vm.stack[vm.sp-1]
vm.sp--
return o
}
取り出す時には、pushでspを進めている分、現在のSPの一個前の値になりますよね。
取り出して、spを１つ減らして終了です。
まとめ
VMを実装できたので、1 + 2 を無事に実行できるようになりました。 長い旅でした。
全体としてみると複雑で難しそうなのですが、一つ一つの処理自体はシンプルで機能美的な美しさがあって、とても面白かったです。
さて、２章が完了したので３章も楽しんで進めたいと思います。
僕から以上。あったかくして寝ろよ
