【コンパイラ自作】スタックマシンを実装したらCPUの気持ちがわかった Part4

シリーズ目次

Part	タイトル	内容
Part1	字句解析器を書いたら正規表現の気持ちがわかった	Lexer（字句解析器）
Part2	ASTって何？木構造で式を理解する	Parser（構文解析器）
Part3	変数のスコープを実装したら、Rustの気持ちがわかった	意味解析
Part4	スタックマシンを実装したらCPUの気持ちがわかった	コード生成 + VM
Part5	目指せFizzBuzz！自作言語で実際に動かす	最終回

はじめに

どうも、あくあです。

Part1からPart3で、こんな感じのパイプラインを作ってきました：

ソースコード → [Lexer] → トークン列 → [Parser] → AST → [Analyzer] → 検証済みAST

「で、いつ実行できるの？」

そうなんですよ。ここまで作っても、まだプログラムは動かないんですよね。

というわけで今回は、ASTからバイトコードを生成して、それを**仮想マシン（VM）**で実行するところまでやります！

なぜバイトコードが必要なの？

ASTを直接実行する方法（インタプリタ）もありますが、今回はバイトコードを経由します。

AST → [CodeGen] → バイトコード → [VM] → 実行結果

バイトコードを使うメリット：

1. 実行が速い - 木構造を辿るより、配列を順番に実行する方が速い
2. 最適化しやすい - 命令列に対して最適化を適用できる
3. クロスプラットフォーム - VMがあればどこでも動く（Java、Python、Luaなど）
4. CPUの気持ちがわかる ← これ重要

スタックマシンとは

VMの設計には大きく2種類あります：

方式	特徴	代表例
スタックマシン	スタックでデータをやり取り	JVM、Python VM、WebAssembly
レジスタマシン	レジスタでデータをやり取り	Lua VM、実際のCPU

今回はスタックマシンを実装します。理由は単純で、実装が楽だから！

スタックマシンの動き

例えば 3 + 5 を計算する場合：

命令列:
  Push(3)     // 3をプッシュ
  Push(5)     // 5をプッシュ
  Add         // 2つをポップして足して結果をプッシュ

スタックの変化:
  []        → Push(3)
  [3]       → Push(5)
  [3, 5]    → Add
  [8]       ← 結果！

「え、めちゃくちゃシンプルじゃない？」

そうなんです。スタックマシンは構造がシンプルなので、初めてVMを作る人にぴったりです。

命令セットの設計

実装する命令を決めましょう：

pub enum Instruction {
    // 定数とスタック操作
    Push(i64),          // 定数をプッシュ
    Pop,                // スタックトップを捨てる
    
    // ローカル変数
    LoadLocal(usize),   // ローカル変数を読み込み
    StoreLocal(usize),  // ローカル変数に保存
    
    // 算術演算
    Add,                // 加算
    Sub,                // 減算
    Mul,                // 乗算
    Div,                // 除算
    Mod,                // 剰余
    Neg,                // 符号反転
    
    // 比較演算
    Eq,                 // ==
    Ne,                 // !=
    Lt,                 // <
    Le,                 // <=
    Gt,                 // >
    Ge,                 // >=
    
    // 論理演算
    Not,                // !
    And,                // &&
    Or,                 // ||
    
    // 制御フロー
    Jump(usize),        // 無条件ジャンプ
    JumpIfFalse(usize), // 条件が偽ならジャンプ
    
    // 関数
    Call(String),       // 関数呼び出し
    Return,             // 関数から戻る
}

18種類の命令です。実際のCPUよりはだいぶ少ないですね！

CodeGenerator の実装

ASTからバイトコードを生成するCodeGeneratorを実装します。

pub struct CompiledFunction {
    pub name: String,
    pub param_count: usize,
    pub local_count: usize,
    pub instructions: Vec<Instruction>,
}

pub struct CodeGenerator {
    functions: HashMap<String, CompiledFunction>,
    current_function: Option<String>,
    local_indices: HashMap<String, usize>,
    next_local_index: usize,
}

式のコード生成

式の生成は再帰的に行います：

fn generate_expr(&mut self, expr: &Expr, instructions: &mut Vec<Instruction>) {
    match expr {
        // 数値リテラル → Push命令
        Expr::Number(n) => {
            instructions.push(Instruction::Push(*n));
        }
        
        // 変数 → LoadLocal命令
        Expr::Identifier(name) => {
            let index = self.local_indices[name];
            instructions.push(Instruction::LoadLocal(index));
        }
        
        // 二項演算 → 左辺、右辺を評価してから演算
        Expr::BinaryOp { left, op, right } => {
            // 左辺を評価（結果がスタックに積まれる）
            self.generate_expr(left, instructions);
            // 右辺を評価（結果がスタックに積まれる）
            self.generate_expr(right, instructions);
            // 演算命令
            match op {
                BinOp::Add => instructions.push(Instruction::Add),
                BinOp::Sub => instructions.push(Instruction::Sub),
                BinOp::Mul => instructions.push(Instruction::Mul),
                BinOp::Div => instructions.push(Instruction::Div),
                BinOp::Mod => instructions.push(Instruction::Mod),
                // ... 比較演算子も同様
            }
        }
        
        // 関数呼び出し
        Expr::Call { name, args } => {
            // 引数を逆順でプッシュ（スタックの都合）
            for arg in args.iter().rev() {
                self.generate_expr(arg, instructions);
            }
            instructions.push(Instruction::Call(name.clone()));
        }
        
        // ... その他の式
    }
}

ポイント： 二項演算では「左辺 → 右辺 → 演算」の順で命令を生成します。

if文のコード生成

制御フローは少しトリッキーです：

// if (condition) { then_body } else { else_body }
fn generate_if(&mut self, condition: &Expr, then_body: &[Stmt], 
               else_body: &Option<Vec<Stmt>>, instructions: &mut Vec<Instruction>) {
    // 条件式を評価
    self.generate_expr(condition, instructions);
    
    // JumpIfFalse → else部へ（アドレスは後で埋める）
    let jump_to_else = instructions.len();
    instructions.push(Instruction::JumpIfFalse(0)); // 仮の値
    
    // then部を生成
    for stmt in then_body {
        self.generate_stmt(stmt, instructions);
    }
    
    // Jump → if文の終わりへ（アドレスは後で埋める）
    let jump_to_end = instructions.len();
    instructions.push(Instruction::Jump(0)); // 仮の値
    
    // else部の開始アドレスを埋める
    let else_start = instructions.len();
    instructions[jump_to_else] = Instruction::JumpIfFalse(else_start);
    
    // else部を生成
    if let Some(else_stmts) = else_body {
        for stmt in else_stmts {
            self.generate_stmt(stmt, instructions);
        }
    }
    
    // if文終了アドレスを埋める
    let end_addr = instructions.len();
    instructions[jump_to_end] = Instruction::Jump(end_addr);
}

バックパッチングと呼ばれるテクニックです。ジャンプ先のアドレスがわからないので、まず仮の値を入れておいて、後で正しい値に書き換えます。

生成されるバイトコード

実際にどんなバイトコードが生成されるか見てみましょう：

fn add(a, b) {
    return a + b;
}

fn main() {
    return add(10, 20);
}

これが以下のバイトコードになります：

Function: main (params: 0, locals: 0)
     0: Push(20)         // 第2引数
     1: Push(10)         // 第1引数
     2: Call("add")      // add関数を呼び出し
     3: Return           // 結果を返す

Function: add (params: 2, locals: 2)
     0: LoadLocal(0)     // a を取得
     1: LoadLocal(1)     // b を取得
     2: Add              // 足し算
     3: Return           // 結果を返す

「おお、思ったよりシンプル！」

VM の実装

いよいよVMの実装です！

pub struct CallFrame {
    pub function_name: String,
    pub return_addr: usize,  // 戻り先のアドレス
    pub locals_base: usize,  // ローカル変数の開始位置
}

pub struct VM {
    stack: Vec<i64>,              // 値スタック
    call_stack: Vec<CallFrame>,   // コールスタック
    functions: HashMap<String, CompiledFunction>,
}

実行ループ

VMのメインループは意外とシンプルです：

pub fn run(&mut self, entry: &str) -> Result<i64, String> {
    let func = self.functions.get(entry).unwrap().clone();
    let mut pc = 0;  // プログラムカウンタ
    let mut current_func = func;
    
    // ローカル変数用の領域を確保
    let locals_base = self.stack.len();
    for _ in 0..current_func.local_count {
        self.stack.push(0);
    }
    
    loop {
        if pc >= current_func.instructions.len() {
            break;
        }
        
        let instruction = &current_func.instructions[pc];
        pc += 1;
        
        match instruction {
            // 定数をプッシュ
            Instruction::Push(n) => {
                self.stack.push(*n);
            }
            
            // 算術演算
            Instruction::Add => {
                let b = self.stack.pop().unwrap();
                let a = self.stack.pop().unwrap();
                self.stack.push(a + b);
            }
            
            // ローカル変数を読み込み
            Instruction::LoadLocal(index) => {
                let value = self.stack[locals_base + index];
                self.stack.push(value);
            }
            
            // ローカル変数に保存
            Instruction::StoreLocal(index) => {
                let value = self.stack.pop().unwrap();
                self.stack[locals_base + index] = value;
            }
            
            // 条件ジャンプ
            Instruction::JumpIfFalse(addr) => {
                let cond = self.stack.pop().unwrap();
                if cond == 0 {
                    pc = *addr;
                }
            }
            
            // 関数呼び出し
            Instruction::Call(name) => {
                // ... 後述
            }
            
            // リターン
            Instruction::Return => {
                // ... 後述
            }
            
            // ... その他の命令
        }
    }
    
    Ok(self.stack.pop().unwrap_or(0))
}

関数呼び出しの実装

ここが一番難しい！ 再帰関数を正しく動かすには、コールスタックの管理が重要です。

Instruction::Call(name) => {
    // 呼び出す関数を取得
    let callee = self.functions.get(name).unwrap().clone();
    
    // 現在の状態を保存
    self.call_stack.push(CallFrame {
        function_name: current_func.name.clone(),
        return_addr: pc,
        locals_base,
    });
    
    // 新しいローカル変数領域の開始位置
    // 引数はすでにスタックに積まれているので、その前から
    let new_locals_base = self.stack.len() - callee.param_count;
    
    // 関数が必要とする追加のローカル変数領域を確保
    let additional_locals = callee.local_count - callee.param_count;
    for _ in 0..additional_locals {
        self.stack.push(0);
    }
    
    // 新しい関数に切り替え
    current_func = callee;
    pc = 0;
    locals_base = new_locals_base;
}

Instruction::Return => {
    // 戻り値を取得
    let return_value = self.stack.pop().unwrap_or(0);
    
    // ローカル変数領域をクリーンアップ
    self.stack.truncate(locals_base);
    
    if let Some(frame) = self.call_stack.pop() {
        // 呼び出し元に戻る
        current_func = self.functions.get(&frame.function_name).unwrap().clone();
        pc = frame.return_addr;
        locals_base = frame.locals_base;
    }
    
    // 戻り値をプッシュ
    self.stack.push(return_value);
}

ポイント：

1. 関数呼び出し時に現在の状態（戻り先アドレス、ローカル変数の位置）を保存
2. リターン時に保存した状態を復元
3. 引数は「スタックに積まれている値」として渡す

動作確認：再帰関数

再帰的な階乗計算が動くか確認しましょう：

fn factorial(n) {
    if n <= 1 {
        return 1;
    }
    return n * factorial(n - 1);
}

fn main() {
    return factorial(5);
}

$ cargo run

=== Recursive factorial(5) ===
Result: 120

キターーー！🎉

5! = 5 × 4 × 3 × 2 × 1 = 120 で正解です！

再帰呼び出しのスタックの様子：

factorial(5) が呼ばれる
  └─ factorial(4) が呼ばれる
       └─ factorial(3) が呼ばれる
            └─ factorial(2) が呼ばれる
                 └─ factorial(1) が呼ばれる → 1を返す
                 2 * 1 = 2 を返す
            3 * 2 = 6 を返す
       4 * 6 = 24 を返す
  5 * 24 = 120 を返す

コールスタックが正しく機能している証拠ですね。

実行の様子を追ってみる

1 + 2 * 3 の実行を詳しく見てみましょう：

生成されたバイトコード:
  Push(1)
  Push(2)
  Push(3)
  Mul
  Add

実行:
  PC=0: Push(1)     Stack: [1]
  PC=1: Push(2)     Stack: [1, 2]
  PC=2: Push(3)     Stack: [1, 2, 3]
  PC=3: Mul         Stack: [1, 6]       ← 2*3=6
  PC=4: Add         Stack: [7]          ← 1+6=7

結果: 7

演算子の優先順位は、ASTの構造で表現されていて、コード生成の順序で自然に反映されます。

テストを書こう

#[test]
fn test_recursive_factorial() {
    let code = r#"
        fn factorial(n) {
            if n <= 1 {
                return 1;
            }
            return n * factorial(n - 1);
        }
        fn main() {
            return factorial(5);
        }
    "#;
    
    let tokens = Lexer::new(code).tokenize().unwrap();
    let program = Parser::new(tokens).parse().unwrap();
    Analyzer::new().check_program(&program).unwrap();
    let compiled = CodeGenerator::new().generate(&program).unwrap();
    let result = VM::new(compiled).run("main").unwrap();
    
    assert_eq!(result, 120);
}

#[test]
fn test_while_loop() {
    let code = r#"
        fn main() {
            let sum = 0;
            let i = 1;
            while i <= 10 {
                sum = sum + i;
                i = i + 1;
            }
            return sum;
        }
    "#;
    
    // ... 省略 ...
    assert_eq!(result, 55);  // 1+2+...+10 = 55
}

CPUの気持ち

実装してみて感じたこと：

1. フェッチ→デコード→実行のサイクルが体感できる
2. スタックポインタ、プログラムカウンタの役割が理解できる
3. 関数呼び出しの仕組み（コールスタック）がわかる
4. なぜバッファオーバーフローが危険かわかる

VMを作るとCPUアーキテクチャの入門として最適！

まとめ

今回作ったもの：

モジュール	行数	役割
codegen.rs	約300行	ASTからバイトコード生成
vm.rs	約250行	バイトコード実行

コンパイラのバックエンドが完成しました！

これで、ソースコードから実行まで全部動くようになりました：

ソースコード
    ↓ [Lexer]
トークン列
    ↓ [Parser]
AST
    ↓ [Analyzer]
検証済みAST
    ↓ [CodeGen]
バイトコード  ← New!
    ↓ [VM]
実行結果     ← New!

次回Part5では、いよいよFizzBuzzを動かして、このシリーズを完結させます！

参考資料

• Crafting Interpreters - バイトコードVMの章が素晴らしい
• Writing An Interpreter In Go - インタプリタ実装の名著
• WebAssembly Specification - スタックマシンの実例
• JVM Specification - 本格的なスタックマシン

次回予告： 「目指せFizzBuzz！自作言語で実際に動かす Part5」