バイトコードVM(バイトコードコンパイラとスタックマシン)

lang 編のツリーウォーク評価器の次の段を Go でモデル化する。木を毎回たどり直すのは遅いので、多くの本番言語は木を一度平らな命令列(バイトコード)に落とし、仮想マシンで回す。VM の仕事は命令を 1 つ取り出して実行するだけの単純なループだ。式は push/pop に、if は条件ジャンプに、変数はスロット番号に還元される。字句・構文解析は lang を再利用する。

この章で作るもの

lang 編のインタプリタは、実行のたびに AST を再帰的にたどり直した(ツリーウォーク)。単純で正しいが、同じ木を何度も歩き回るのは遅い。そこで多くの言語はもう一段挟む。木を一度平らな命令列(バイトコード)にコンパイルし、それを仮想マシン(VM)が回す。

  ソース                AST(木)               バイトコード(平らな命令列)
  "1 + 2"   ──lang──▶    (+ 1 2)   ──compile──▶  0000 OpConstant 0   ┐
                          /   \                    0003 OpConstant 1   ├ VM が上から
                         1     2                   0006 OpAdd          │ 一直線に実行
                                                   0007 OpPop          ┘ (スタックで計算)
     └──────── 字句解析 + 構文解析(lang を再利用)────────┘

ツリーウォーク(lang)とバイトコード(本章)の違い。前者は木をそのまま再帰でたどる。後者は木を一度平らな命令列にコンパイルし、VM が上から一直線に実行する。字句・構文解析(ソース→木)は共通で、『木をどう実行するか』だけが違う

順に見ていく。

1. バイトコード = 平らな命令列 + 定数プール: 木を、オペコード(1 バイト)とオペランドが詰まった 1 本のバイト列に落とす。値は命令に埋めず定数プールに置いて番号で指す
2. スタックマシン: レジスタを持たず、オペランドは全てスタックで受け渡す。OpAdd は「上位2つを pop して足し、結果を push」。式の評価が push/pop の列になる
3. 制御フロー = 条件ジャンプ: if は OpJumpNotTruthy / OpJump に変換される。飛び先は後から書き換える(back-patching)

① 命令セット: 木を数バイトに落とす

まず命令(オペコード)を定義する。各命令は 1 バイトのオペコードと、必要なら決まった幅のオペランドを持つ。OpConstant は 2 バイトのオペランド(定数プールの番号)を取り、OpAdd はオペランド無し。Make が 1 命令をバイト列に符号化する:

// Opcode は 1 バイトの命令種別。VM はこれを見て何をするかを決める。
type Opcode byte

const (
	OpConstant      Opcode = iota // 定数プールの [operand] 番目をスタックに積む
	OpPop                         // スタック先頭を1つ捨てる(式文の後始末)
	OpTrue                        // true を積む
	OpFalse                       // false を積む
	OpNull                        // null を積む(else 無き if の値)
	OpAdd                         // 上位2つを pop して加算し、結果を積む
	OpSub                         // 減算
	OpMul                         // 乗算
	OpDiv                         // 除算
	OpMinus                       // 前置 -(符号反転)
	OpBang                        // 前置 !(真偽反転)
	OpEqual                       // ==
	OpNotEqual                    // !=
	OpGreater                     // >(< は compiler がオペランドを入れ替えて表現)
	OpJump                        // 無条件に [operand] へ飛ぶ
	OpJumpNotTruthy               // pop した値が偽なら [operand] へ飛ぶ
	OpSetGlobal                   // pop した値をグローバル [operand] に束縛(let)
	OpGetGlobal                   // グローバル [operand] を積む(識別子参照)
)

// Definition は1つのオペコードの、人間向けの名前とオペランドの幅(バイト数)。
// OperandWidths が空なら、そのオペコードはオペランドを取らない。
type Definition struct {
	Name          string
	OperandWidths []int
}

var definitions = map[Opcode]*Definition{
	OpConstant:      {"OpConstant", []int{2}}, // 2 バイトの定数インデックス
	OpPop:           {"OpPop", nil},
	OpTrue:          {"OpTrue", nil},
	OpFalse:         {"OpFalse", nil},
	OpNull:          {"OpNull", nil},
	OpAdd:           {"OpAdd", nil},
	OpSub:           {"OpSub", nil},
	OpMul:           {"OpMul", nil},
	OpDiv:           {"OpDiv", nil},
	OpMinus:         {"OpMinus", nil},
	OpBang:          {"OpBang", nil},
	OpEqual:         {"OpEqual", nil},
	OpNotEqual:      {"OpNotEqual", nil},
	OpGreater:       {"OpGreater", nil},
	OpJump:          {"OpJump", []int{2}}, // 2 バイトの飛び先(命令列内の位置)
	OpJumpNotTruthy: {"OpJumpNotTruthy", []int{2}},
	OpSetGlobal:     {"OpSetGlobal", []int{2}}, // 2 バイトのグローバル番号
	OpGetGlobal:     {"OpGetGlobal", []int{2}},
}

// Lookup はオペコードの定義を引く。未知なら error。
func Lookup(op byte) (*Definition, error) {
	def, ok := definitions[Opcode(op)]
	if !ok {
		return nil, fmt.Errorf("opcode %d undefined", op)
	}
	return def, nil
}

// Instructions はバイトコード(平らな命令列)。オペコードとオペランドが
// 隙間なく詰まった 1 本のバイト列だ。
type Instructions []byte

// Make は 1 命令を符号化する: オペコード 1 バイト + 各オペランドをその幅で
// ビッグエンディアン格納。これが「木の 1 ノード → 数バイトの命令」への変換。
func Make(op Opcode, operands ...int) Instructions {
	def, ok := definitions[op]
	if !ok {
		return Instructions{}
	}
	length := 1
	for _, w := range def.OperandWidths {
		length += w
	}
	ins := make(Instructions, length)
	ins[0] = byte(op)
	offset := 1
	for i, o := range operands {
		w := def.OperandWidths[i]
		switch w {
		case 2:
			binary.BigEndian.PutUint16(ins[offset:], uint16(o))
		}
		offset += w
	}
	return ins
}

// ReadUint16 は命令列の先頭 2 バイトを 16bit オペランドとして読む。
// VM が飛び先や定数インデックスを取り出すのに使う。
func ReadUint16(ins Instructions) uint16 {
	return binary.BigEndian.Uint16(ins)
}

// String は命令列を人間可読に逆アセンブルする。各行は "0000 OpConstant 0"
// の形で、先頭の 4 桁はその命令の命令列内オフセット(= 飛び先の単位)。
func (ins Instructions) String() string {
	var out bytes.Buffer
	i := 0
	for i < len(ins) {
		def, err := Lookup(ins[i])
		if err != nil {
			fmt.Fprintf(&out, "ERROR: %s\n", err)
			i++
			continue
		}
		operands, read := readOperands(def, ins[i+1:])
		fmt.Fprintf(&out, "%04d %s\n", i, fmtInstruction(def, operands))
		i += 1 + read
	}
	return out.String()
}

// readOperands は 1 命令ぶんのオペランドを、定義の幅に従って読み出す。
func readOperands(def *Definition, ins Instructions) ([]int, int) {
	operands := make([]int, len(def.OperandWidths))
	offset := 0
	for i, w := range def.OperandWidths {
		switch w {
		case 2:
			operands[i] = int(ReadUint16(ins[offset:]))
		}
		offset += w
	}
	return operands, offset
}

func fmtInstruction(def *Definition, operands []int) string {
	if len(operands) != len(def.OperandWidths) {
		return fmt.Sprintf("ERROR: operand len %d != defined %d", len(operands), len(def.OperandWidths))
	}
	switch len(operands) {
	case 0:
		return def.Name
	case 1:
		return fmt.Sprintf("%s %d", def.Name, operands[0])
	}
	return fmt.Sprintf("ERROR: unhandled operandCount for %s", def.Name)
}

String()(逆アセンブラ)が出す 0000 OpConstant 0 の先頭 4 桁は、命令列内のオフセットだ。これがジャンプの飛び先の単位になる。命令は幅がまちまち(1 バイトや 3 バイト)なので、飛び先は「何番目の命令か」ではなく「先頭から何バイト目か」で指す。

② コンパイラ: AST を一度歩いて命令に落とす

Compiler は lang の AST を再帰的に歩き、対応する命令を命令列の末尾に足していく。1 + 2 なら「左をコンパイル → 右をコンパイル → OpAdd」。整数リテラルは定数プールに登録して OpConstant で番号を指す。山場は if の扱いだ。制御フローが条件ジャンプに化け、飛び先はコンパイル中まだ分からないので仮の値で出しておき、行き先が確定してから書き換える(back-patching):

// Bytecode はコンパイルの成果物: 平らな命令列と、そこから参照される定数プール。
// 整数リテラルなどの値は命令に埋め込まず、定数プールに置いて番号で指す。
type Bytecode struct {
	Instructions Instructions
	Constants    []lang.Object
}

// emitted は直近に出力した命令(オペコードと、その命令列内の位置)。
// if の後始末で「末尾の OpPop を消す」「飛び先を後から埋める」のに使う。
type emitted struct {
	Opcode   Opcode
	Position int
}

// Compiler は lang の AST を一度だけ歩いて、バイトコードに落とす。
// シンボルテーブルで「変数名 → グローバル番号」を管理する。
type Compiler struct {
	instructions Instructions
	constants    []lang.Object
	symbols      map[string]int // 変数名 → グローバル番号
	last         emitted        // 直近に出した命令
	prev         emitted        // その 1 つ前(OpPop 除去で末尾を戻すため)
}

// New は空のコンパイラを作る。
func New() *Compiler {
	return &Compiler{symbols: map[string]int{}}
}

// Compile は AST ノードを再帰的にコンパイルする。木を一度歩き、対応する命令を
// 命令列の末尾に足していく。これが「木 → 平らな命令列」への変換の全体だ。
func (c *Compiler) Compile(node lang.Node) error {
	switch node := node.(type) {
	case *lang.Program:
		for _, s := range node.Statements {
			if err := c.Compile(s); err != nil {
				return err
			}
		}

	case *lang.ExpressionStatement:
		// 式だけの文。値を評価したら、その結果は捨てる(次の文のためにスタックを空に保つ)。
		if err := c.Compile(node.Expression); err != nil {
			return err
		}
		c.emit(OpPop)

	case *lang.BlockStatement:
		for _, s := range node.Statements {
			if err := c.Compile(s); err != nil {
				return err
			}
		}

	case *lang.InfixExpression:
		// a < b は「b > a」に読み替えて OpGreater だけで賄う——オペコードを1つ減らす
		// コンパイラの定番テク。左右を逆順にコンパイルするだけでよい。
		if node.Operator == "<" {
			if err := c.Compile(node.Right); err != nil {
				return err
			}
			if err := c.Compile(node.Left); err != nil {
				return err
			}
			c.emit(OpGreater)
			return nil
		}
		if err := c.Compile(node.Left); err != nil {
			return err
		}
		if err := c.Compile(node.Right); err != nil {
			return err
		}
		switch node.Operator {
		case "+":
			c.emit(OpAdd)
		case "-":
			c.emit(OpSub)
		case "*":
			c.emit(OpMul)
		case "/":
			c.emit(OpDiv)
		case "==":
			c.emit(OpEqual)
		case "!=":
			c.emit(OpNotEqual)
		case ">":
			c.emit(OpGreater)
		default:
			return fmt.Errorf("未知の演算子: %s", node.Operator)
		}

	case *lang.PrefixExpression:
		if err := c.Compile(node.Right); err != nil {
			return err
		}
		switch node.Operator {
		case "-":
			c.emit(OpMinus)
		case "!":
			c.emit(OpBang)
		default:
			return fmt.Errorf("未知の前置演算子: %s", node.Operator)
		}

	case *lang.IntegerLiteral:
		// 値は命令に埋めず、定数プールに登録して「その番号」を OpConstant で指す。
		c.emit(OpConstant, c.addConstant(&lang.Integer{Value: node.Value}))

	case *lang.Boolean:
		if node.Value {
			c.emit(OpTrue)
		} else {
			c.emit(OpFalse)
		}

	case *lang.IfExpression:
		if err := c.compileIf(node); err != nil {
			return err
		}

	case *lang.LetStatement:
		if err := c.Compile(node.Value); err != nil {
			return err
		}
		idx := c.define(node.Name.Value)
		c.emit(OpSetGlobal, idx)

	case *lang.Identifier:
		idx, ok := c.symbols[node.Value]
		if !ok {
			return fmt.Errorf("未定義の変数: %s", node.Value)
		}
		c.emit(OpGetGlobal, idx)

	case *lang.FunctionLiteral, *lang.CallExpression, *lang.ReturnStatement:
		// 関数/呼び出し/return は、フレームとコール規約が要る。本章の範囲外。
		return fmt.Errorf("この章のコンパイラは関数を扱わない(式・let・if まで)")

	default:
		return fmt.Errorf("コンパイル未対応のノード: %T", node)
	}
	return nil
}

// compileIf は if 式をコンパイルする。制御フローが**条件ジャンプ**に化ける、
// バイトコードの肝。飛び先はコンパイル時にはまだ分からないので、仮の値で出して
// おき、行き先が確定したら後から書き換える(back-patching)。
func (c *Compiler) compileIf(node *lang.IfExpression) error {
	if err := c.Compile(node.Condition); err != nil {
		return err
	}
	// 条件が偽なら「then を飛び越す」。飛び先は未確定なので仮に 9999。
	jumpNotTruthy := c.emit(OpJumpNotTruthy, 9999)

	if err := c.Compile(node.Consequence); err != nil {
		return err
	}
	// ブロックの式文が付けた OpPop を消す——if 式は値を残したいから。
	c.removeLastPopIfAny()

	// then を実行し終えたら else を飛び越す。ここも仮の飛び先。
	jumpOverElse := c.emit(OpJump, 9999)

	// ここが「条件が偽のときの行き先」。確定したので JumpNotTruthy を書き換える。
	c.changeOperand(jumpNotTruthy, len(c.instructions))

	if node.Alternative == nil {
		c.emit(OpNull) // else が無ければ、偽のとき null を値にする
	} else {
		if err := c.Compile(node.Alternative); err != nil {
			return err
		}
		c.removeLastPopIfAny()
	}
	// if 全体の直後。then 実行後の Jump をここへ向ける。
	c.changeOperand(jumpOverElse, len(c.instructions))
	return nil
}

// Bytecode はコンパイル結果を返す。
func (c *Compiler) Bytecode() *Bytecode {
	return &Bytecode{Instructions: c.instructions, Constants: c.constants}
}

// --- 低レベルの出力補助 ---

// emit は 1 命令を符号化して命令列の末尾に足し、その位置を返す。
func (c *Compiler) emit(op Opcode, operands ...int) int {
	ins := Make(op, operands...)
	pos := len(c.instructions)
	c.instructions = append(c.instructions, ins...)
	c.prev = c.last
	c.last = emitted{Opcode: op, Position: pos}
	return pos
}

// addConstant は定数プールに値を登録し、その番号を返す。
func (c *Compiler) addConstant(obj lang.Object) int {
	c.constants = append(c.constants, obj)
	return len(c.constants) - 1
}

// define は変数名に次のグローバル番号を割り当てる(let の左辺)。
func (c *Compiler) define(name string) int {
	if idx, ok := c.symbols[name]; ok {
		return idx // 再代入は同じ番号に上書き
	}
	idx := len(c.symbols)
	c.symbols[name] = idx
	return idx
}

// removeLastPopIfAny は直近が OpPop なら命令列末尾から取り除く。
func (c *Compiler) removeLastPopIfAny() {
	if c.last.Opcode != OpPop {
		return
	}
	c.instructions = c.instructions[:c.last.Position]
	c.last = c.prev
}

// changeOperand は既に出した命令のオペランドを差し替える(back-patching)。
// 同じオペコードで作り直して、その場に上書きする。
func (c *Compiler) changeOperand(opPos int, operand int) {
	op := Opcode(c.instructions[opPos])
	newIns := Make(op, operand)
	copy(c.instructions[opPos:], newIns)
}

a < b を「b > a」に読み替えて OpGreater だけで賄っているのも見どころ。左右を逆順にコンパイルするだけで OpLess を作らずに済む、コンパイラの定番テクだ。

③ VM: スタックマシンで実行する

心臓部。VM は命令を先頭から1つずつ取り出して実行する(fetch-decode-execute)。レジスタは無く、値は全てスタックに積んでやり取りする。OpAdd は「上位2つを pop して足し、結果を push」、OpJump は命令ポインタ ip を飛び先へ動かすだけ。木を歩く代わりに、平らなバイト列を一直線に舐めていく:

const (
	stackSize   = 2048  // スタックの深さ上限
	globalsSize = 65536 // グローバル変数の本数上限(OpSetGlobal の 2 バイトぶん)
)

// 真偽値と null は毎回作らず、共有インスタンスを積む(値の同一性も単純になる)。
var (
	True  = &lang.BooleanObj{Value: true}
	False = &lang.BooleanObj{Value: false}
	Null  = &lang.Null{}
)

// VM はスタックマシン。レジスタを持たず、オペランドはすべてスタックに積んで
// やり取りする。命令を 1 つずつ取り出して解釈する(fetch-decode-execute)。
type VM struct {
	constants    []lang.Object
	instructions Instructions
	stack        []lang.Object
	sp           int // 次に積む位置。先頭要素は stack[sp-1]
	globals      []lang.Object
}

// NewVM はコンパイル結果から VM を作る。
func NewVM(bc *Bytecode) *VM {
	return &VM{
		constants:    bc.Constants,
		instructions: bc.Instructions,
		stack:        make([]lang.Object, stackSize),
		sp:           0,
		globals:      make([]lang.Object, globalsSize),
	}
}

// Run は命令列を先頭から回す。ip(命令ポインタ)を進めながら、オペコードごとに
// スタックを操作する——これがバイトコード実行の全体。木を歩く代わりに、平らな
// バイト列を一直線に舐めていく(ジャンプ命令だけが ip を飛ばす)。
func (vm *VM) Run() error {
	for ip := 0; ip < len(vm.instructions); ip++ {
		op := Opcode(vm.instructions[ip])

		switch op {
		case OpConstant:
			idx := ReadUint16(vm.instructions[ip+1:])
			ip += 2
			if err := vm.push(vm.constants[idx]); err != nil {
				return err
			}

		case OpPop:
			vm.pop()

		case OpTrue:
			if err := vm.push(True); err != nil {
				return err
			}
		case OpFalse:
			if err := vm.push(False); err != nil {
				return err
			}
		case OpNull:
			if err := vm.push(Null); err != nil {
				return err
			}

		case OpAdd, OpSub, OpMul, OpDiv:
			if err := vm.binaryOp(op); err != nil {
				return err
			}

		case OpEqual, OpNotEqual, OpGreater:
			if err := vm.comparison(op); err != nil {
				return err
			}

		case OpMinus:
			operand := vm.pop()
			i, ok := operand.(*lang.Integer)
			if !ok {
				return fmt.Errorf("- は整数にしか使えない: %s", operand.Type())
			}
			if err := vm.push(&lang.Integer{Value: -i.Value}); err != nil {
				return err
			}

		case OpBang:
			operand := vm.pop()
			if err := vm.push(boolObj(!isTruthy(operand))); err != nil {
				return err
			}

		case OpJump:
			// 無条件ジャンプ。飛び先はオペランド。ip は直後に ++ されるので -1 する。
			pos := int(ReadUint16(vm.instructions[ip+1:]))
			ip = pos - 1

		case OpJumpNotTruthy:
			pos := int(ReadUint16(vm.instructions[ip+1:]))
			ip += 2
			cond := vm.pop()
			if !isTruthy(cond) {
				ip = pos - 1 // 偽なら飛ぶ。真ならそのまま then へ進む
			}

		case OpSetGlobal:
			idx := ReadUint16(vm.instructions[ip+1:])
			ip += 2
			vm.globals[idx] = vm.pop()

		case OpGetGlobal:
			idx := ReadUint16(vm.instructions[ip+1:])
			ip += 2
			if err := vm.push(vm.globals[idx]); err != nil {
				return err
			}

		default:
			return fmt.Errorf("未知のオペコード: %d", op)
		}
	}
	return nil
}

// binaryOp は算術2項演算。右→左の順に pop し(スタックなので後入れが右)、
// 結果を積む。整数以外はエラー。
func (vm *VM) binaryOp(op Opcode) error {
	right := vm.pop()
	left := vm.pop()
	l, lok := left.(*lang.Integer)
	r, rok := right.(*lang.Integer)
	if !lok || !rok {
		return fmt.Errorf("算術は整数どうしだけ: %s %s", left.Type(), right.Type())
	}
	var res int64
	switch op {
	case OpAdd:
		res = l.Value + r.Value
	case OpSub:
		res = l.Value - r.Value
	case OpMul:
		res = l.Value * r.Value
	case OpDiv:
		if r.Value == 0 {
			return fmt.Errorf("ゼロ除算")
		}
		res = l.Value / r.Value
	}
	return vm.push(&lang.Integer{Value: res})
}

// comparison は比較演算。整数どうしなら大小/等値、真偽値どうしなら等値のみ。
func (vm *VM) comparison(op Opcode) error {
	right := vm.pop()
	left := vm.pop()
	l, lok := left.(*lang.Integer)
	r, rok := right.(*lang.Integer)
	if lok && rok {
		switch op {
		case OpEqual:
			return vm.push(boolObj(l.Value == r.Value))
		case OpNotEqual:
			return vm.push(boolObj(l.Value != r.Value))
		case OpGreater:
			return vm.push(boolObj(l.Value > r.Value))
		}
	}
	// 整数でない(= 真偽値)の比較は等値のみ。共有インスタンスなのでポインタ一致で足りる。
	switch op {
	case OpEqual:
		return vm.push(boolObj(left == right))
	case OpNotEqual:
		return vm.push(boolObj(left != right))
	default:
		return fmt.Errorf("その比較は真偽値には使えない: %s %s", left.Type(), right.Type())
	}
}

func (vm *VM) push(o lang.Object) error {
	if vm.sp >= stackSize {
		return fmt.Errorf("スタックあふれ")
	}
	vm.stack[vm.sp] = o
	vm.sp++
	return nil
}

func (vm *VM) pop() lang.Object {
	if vm.sp == 0 {
		return Null // 値を残さない式(例: 本体が let だけの if)でも壊れないように
	}
	o := vm.stack[vm.sp-1]
	vm.sp--
	return o
}

// StackTop は現在のスタック先頭を返す(空なら nil)。
func (vm *VM) StackTop() lang.Object {
	if vm.sp == 0 {
		return nil
	}
	return vm.stack[vm.sp-1]
}

// LastPopped は直前に pop された値(sp が指す位置に残っている)を返す。
// プログラム末尾の OpPop で捨てられた「最後の式の値」= 実行結果を取り出すのに使う。
func (vm *VM) LastPopped() lang.Object { return vm.stack[vm.sp] }

// boolObj は Go の bool を共有 True/False に写す。
func boolObj(b bool) *lang.BooleanObj {
	if b {
		return True
	}
	return False
}

// isTruthy は VM 上の真偽判定。false と null が偽、それ以外は真。
func isTruthy(o lang.Object) bool {
	switch o := o.(type) {
	case *lang.BooleanObj:
		return o.Value
	case *lang.Null:
		return false
	default:
		return true
	}
}

// Run はソース文字列を字句解析→構文解析(lang を再利用)→コンパイル→VM 実行し、
// 結果オブジェクトを返す。lang.Run と同じ入口を、評価器の代わりにコンパイラ+VM で。
func Run(input string) (lang.Object, error) {
	p := lang.NewParser(lang.NewLexer(input))
	program := p.ParseProgram()
	if errs := p.Errors(); len(errs) > 0 {
		return nil, fmt.Errorf("構文エラー: %s", errs[0])
	}
	comp := New()
	if err := comp.Compile(program); err != nil {
		return nil, err
	}
	machine := NewVM(comp.Bytecode())
	if err := machine.Run(); err != nil {
		return nil, err
	}
	return machine.LastPopped(), nil
}

OpJump / OpJumpNotTruthy で ip を pos - 1 にしているのは、ループの ip++ で相殺されて次に pos から実行されるようにするため。木の分岐が、平らな命令列上のジャンプになった。式の評価が push/pop の列に、制御フローがジャンプに、変数がインデックス付きの Set/Get に還元される。

動かす

下のデモは、この「ソース → バイトコード → スタックマシン実行」をそのままブラウザで動かしている。プログラムを選ぶと、コンパイル結果の逆アセンブルが出る。「1手すすめる」で VM が1命令ずつ実行し、スタックが伸び縮みする様子と、if で命令ポインタがジャンプで飛ぶ様子を追える。式が push/pop に、分岐がジャンプに化けているのが見えるはずだ。

デモbytecode(コンパイラ + スタックマシン)ip → 0000

算術if 分岐let 束縛

source1 + 2 * 3

bytecode(逆アセンブル)

0000OpConstant0

0003OpConstant1

0006OpConstant2

0009OpMul

0010OpAdd

0011OpPop

stack(先頭が上)

(空)

globals

—

constants

#0: 1#1: 2#2: 3

定数 1 をスタックに積む

1 / 7

設計の観点: なぜバイトコード VM か

• ツリーウォーク vs バイトコード: ツリーウォークは実装が最も素直だが、実行のたびに木を再帰でたどりポインタを追うのでキャッシュ効率も悪い。バイトコードは一度コンパイルすれば、平らな配列を舐めるだけで済み、命令ディスパッチが速く、局所性も良い。多くの言語(Python/Ruby/Lua/JVM)がこの段を持つ理由
• スタックマシン vs レジスタマシン: スタックマシン(JVM・CPython・WASM)は命令が小さく移植しやすいが、命令数が増えがち。レジスタマシン(Lua 5・Dalvik)は命令数が減り速いことが多いが、レジスタ割り当てが要る。設計上の古典的トレードオフ
• 命令ディスパッチの速さ: switch による解釈は分岐予測ミスが多い。実用 VM は computed goto(direct threading)や、さらに JIT(ホットな部分を機械語にコンパイル)で速くする。V8・JVM HotSpot・PyPy はこの延長
• コンパイル時に決まること: 変数はコンパイル時に番号(スロット)へ解決され、実行時は名前引きせずインデックスアクセスになる。if の飛び先も back-patching で確定済み。実行時の仕事を減らすのがコンパイルの効能
• WebAssembly との関係: WASM は「移植可能なスタックマシンのバイトコード」そのもの。本章の命令セットを型付き・サンドボックス付きにし、標準化したものと見なせる

メリット・デメリットと実例

実行方式	速さ	実装の素直さ	起動	実例
ツリーウォーク	遅い	最も素直	速い(コンパイル不要)	lang 編、素朴な言語、設定 DSL
バイトコード VM(本章)	中くらい	素直	中(コンパイルが要る)	CPython、Ruby(YARV)、Lua、初期 JS
バイトコード + JIT	速い	複雑	遅い(ウォームアップ)	JVM HotSpot、V8、PyPy、.NET
AOT ネイティブ	最速	複雑	最速(実行のみ)	Go、Rust、C/C++

裏どり:

• CPython: ソースを .pyc(バイトコード)にコンパイルし、ceval.c の巨大な評価ループ(スタックマシン)が回す。dis モジュールでバイトコードを覗ける。本章の逆アセンブルと同じもの
• JVM: .java → .class(バイトコード)。起動時はバイトコードを解釈し、ホットなメソッドを HotSpot が JIT で機械語にコンパイルする。「解釈 → JIT」の二段構え
• Lua: 軽量なレジスタマシンのバイトコード VM。組み込み向けに速く小さい。LuaJIT はさらに JIT を載せる
• WebAssembly: ブラウザ/サーバで動く、標準化された移植可能なスタックマシンのバイトコード。本章の命令セットに型とサンドボックスを足し標準化した姿と見なせる

簡略化したこと

• 関数・クロージャは範囲外: 呼び出しにはフレーム(戻り先・ローカル領域)とコール規約が要る。本章は式・let・if までに絞り、関数はコンパイルエラーで明示的に弾く。lang 編はツリーウォークでクロージャまで実装済み(=同じ言語の別実装)
• グローバル変数のみ: let は全てグローバル領域。ローカル変数(フレーム内スロット)は関数と一緒に省略
• 整数と真偽値のみ: 文字列・配列・ハッシュ・組み込み関数は無し
• 最適化・JIT なし: 定数畳み込み・ピープホール最適化・レジスタ割り当て・機械語 JIT はしない。素直な命令列を switch で解釈するだけ
• GC は別章: 生成したオブジェクトの回収はgc 編を参照。ここではメモリ管理に踏み込まない

参考資料

• Thorsten Ball, Writing A Compiler In Go — 本章の下敷き。lang 編(Writing An Interpreter In Go)の続編で、同じ言語をバイトコード VM で実行する
• Bob Nystrom, Crafting Interpreters — スタックマシンと命令ディスパッチの決定版(無料公開)
• CPython の dis モジュール — 実在するバイトコードを覗く。本章の逆アセンブルの実物
• 実装: foundations/bytecode