関数とコールスタックを実装する——グローバル名前解決で相互再帰を可能にする
関数を導入すると型検査を素通りさせられなくなる
この処理系にはまだ関数宣言が無いため、関数呼び出しExpr::Callの型検査はType::Unknownを返してその場をやり過ごす設計にしていました。呼び出し先の関数がそもそも存在しない以上、引数の型も戻り値の型も検査のしようがなかったからです。
関数を導入するということは、このUnknown型を退場させ、本物の関数シグネチャ検査に置き換えるということでもあります。
fn add(a: int, b: int): int {
return a + b;
}パラメータと戻り値に型注記が必要になりました。letの右辺から型を推論するのとは違い、関数の中身を見ずに呼び出し側だけで引数の型・個数・戻り値の型を検査できるようにするには、シグネチャを外から与えてもらう必要があるためです。戻り値の型注記を省略すると、値を返さない関数（void関数）になります。
fn greet(name: string) {
return;
}相互再帰はコンパイル時の定数埋め込みでは解決できない
関数を実装するにあたって最初に突き当たる設計判断は、「関数Aの中から関数Bを呼び出すとき、Bの実体をどうやってAのコンパイル済みバイトコードに埋め込むか」です。
素朴に考えると、コンパイルした関数の値をそのまま呼び出し側の定数プールに埋め込めばよさそうに見えます。しかし、次のように2つの関数が互いを呼び合う場合を考えると、この方式は破綻します。
fn is_even(n: int): bool {
if (n == 0) { return true; }
return is_odd(n - 1);
}
fn is_odd(n: int): bool {
if (n == 0) { return false; }
return is_even(n - 1);
}is_evenを先にコンパイルしようとすると、その中のis_odd(n - 1)という呼び出しを埋め込むためにis_oddのバイトコードが必要になります。しかしis_oddはまだコンパイルされていません。かといってis_oddを先にコンパイルしても、今度はその中のis_even呼び出しで同じ問題が起きます。定義順にどちらを先にコンパイルしても、もう一方が必ず未完成という堂々巡りです。
この処理系で採った解決策は、関数の実体をコンパイル時の定数として埋め込むのをやめ、実行時に名前で引く方式に変えることでした。関数を定義するというのは、名前と値のペアをグローバルなテーブルに登録することだと考え直します。
fn add(a: int, b: int): int { ... }は、コンパイルすると次のようなバイトコードになります。
OP_CONSTANT <fn addの値>
OP_DEFINE_GLOBAL "add"そして呼び出し側のadd(1, 2)は、コンパイル時にaddのバイトコードがどこにあるかを一切知らないまま、次のようにコンパイルされます。
OP_GET_GLOBAL "add"
OP_CONSTANT 1
OP_CONSTANT 2
OP_CALL 2OP_GET_GLOBALは「実行時に、globalsというHashMap<String, Value>から"add"という名前の値を引いてくる」という命令です。コンパイラは呼び出し先の関数がすでに存在するかどうかを一切気にする必要がなくなり、コンパイル順の制約から解放されます。実行時に必要なのは「呼び出しが実際に実行される時点までに、その名前のOP_DEFINE_GLOBALが一度でも実行されていること」だけです。関数定義をソースの先頭付近にまとめて書いておけば、この条件は自然に満たされます。
OpCode::GetGlobal => {
let Value::Str(name) = self.read_constant() else {
unreachable!("compiler always emits a string constant for OP_GET_GLOBAL");
};
let value = self
.globals
.get(&name)
.cloned()
.expect("type checker guarantees a function is defined before it's called");
self.push(value);
}型検査の段階でも同じ考え方を採っています。すべての関数の型シグネチャを、本体の中身を検査するより先に一括で集めておくことで、相互再帰する関数同士が互いを型検査の時点でも解決できるようにしています。
fn collect_function_signatures(&mut self, program: &[Stmt]) -> Result<(), TypeError> {
for stmt in program {
let StmtKind::Function { name, params, return_type, .. } = &stmt.kind else {
continue;
};
// ...シグネチャを resolve して self.functions に登録するだけで、
// 本体はまだ一切検査しない
}
Ok(())
}関数値はRcで持つ——ヒープオブジェクトはまだ無いが困らない
関数はコンパイルされた独自のChunkを持つ必要があります。このChunkを値として持ち運ぶために、Value列挙型に新しいバリアントを追加しました。
pub struct FunctionObj {
pub name: String,
pub arity: u8,
pub chunk: Chunk,
}
pub enum Value {
// ...
Function(Rc<FunctionObj>),
Void,
}この処理系にはまだヒープオブジェクトを管理するガベージコレクタが無く、それは今後の実装課題です。しかし関数値に関しては、GCを先取りして作り込む必要はありませんでした。関数はコンパイル時に一度作られたら二度と書き換わらない不変の値で、しかも「関数Aが関数Bを参照し、Bが再びAを参照する」という参照だけを見ればループになり得ますが、これは単なる名前の呼び合い（OP_GET_GLOBALによるグローバルテーブル経由の間接参照）であって、Rc同士が直接循環参照を作っているわけではありません。参照カウント方式のRc<FunctionObj>で持ち運ぶだけで、メモリリークの心配なく安全に共有できます。
コールフレーム——呼び出しごとにチャンクとスタック位置を切り替える
関数を呼び出すということは、実行するバイトコードの入れ替え（呼び出し先自身のChunkに切り替える）と、ローカル変数のスタック上の位置の入れ替え（呼び出しごとに新しいスタック領域を使う）の両方が起きるということです。この2つをまとめて管理するのがコールフレームです。
struct CallFrame {
function: Rc<FunctionObj>,
ip: usize,
stack_base: usize,
}
pub struct Vm {
chunk: Chunk,
ip: usize,
stack: Vec<Value>,
frames: Vec<CallFrame>,
globals: HashMap<String, Value>,
}OP_CALLが実行されると、スタックの上には呼び出し対象の関数値と、その下に積まれた各引数が並んでいます。ここから新しいフレームを作ります。
fn exec_call(&mut self) {
let arg_count = self.read_u8() as usize;
let callee = self.peek(arg_count).clone();
let Value::Function(function) = callee else {
unreachable!("type checker guarantees the callee is a function");
};
debug_assert_eq!(function.arity as usize, arg_count, "type checker guarantees a matching argument count");
self.frames.push(CallFrame { function, ip: 0, stack_base: self.stack.len() - arg_count - 1 });
}stack_baseは関数値そのものが積まれている位置を指します。関数のローカル変数スロット0番はこの関数値自身の位置（ユーザーからは名前を持たない、決して参照されないスロット）で、スロット1番以降が実際のパラメータになります。この「スロット0番を予約する」というのは、パラメータの受け渡しをローカル変数の仕組みにそのまま乗せるための小さな工夫で、関数を実装する前から存在していたGetLocal/SetLocalの仕組みをほぼ手を加えずに再利用できています。
呼び出し中にどのスロットを読み書きするかは、実行中の一番内側のフレームがあるかどうかで変わります。
fn locals_base(&self) -> usize {
self.frames.last().map_or(0, |frame| frame.stack_base)
}OpCode::GetLocal => {
let slot = self.read_u8() as usize;
let base = self.locals_base();
self.push(self.stack[base + slot].clone());
}コンパイラ側では、関数ごとに独立したCompilerインスタンスを新しく作ることで、スロット番号を毎回0から振り直しています。ローカル変数の解決ロジック自体は一切変更していません。
fn compile_function(&mut self, name: &str, params: &[(String, TypeName)], body: &Block, line: usize) -> Result<(), CompileError> {
let mut function_compiler = Compiler::new_function();
function_compiler.declare_local(String::new()); // スロット0: 関数値自身のための予約枠
for (param_name, _) in params {
function_compiler.declare_local(param_name.clone());
}
for stmt in body {
function_compiler.compile_stmt(stmt)?;
}
function_compiler.chunk.write_op(OpCode::Void, line);
function_compiler.chunk.write_op(OpCode::Return, line);
// ...できあがったChunkをFunctionObjに詰めて、呼び出し元のチャンクへ
// OP_CONSTANT + OP_DEFINE_GLOBAL として書き出す
}「コンパイル時にはスロット0起点、実行時にはstack_base起点」という2つの座標系を、locals_base()という1点だけで変換しているのがポイントです。
returnは値を残す、OP_RETURNはスタックを巻き戻す
関数から抜けるときの処理は、「戻り値をスタックの一番上に用意しておき、呼び出しのために積んだ分（関数値・引数・ローカル変数のすべて）をまとめて捨てて、戻り値だけを積み直す」という手順です。
OpCode::Return => {
let Some(frame) = self.frames.pop() else {
return Ok(());
};
let result = self.pop();
self.stack.truncate(frame.stack_base);
self.push(result);
}値を返さないreturn;は、戻り値の代わりにこの処理系だけの内部値Value::Voidを積みます。ユーザーが書く式にVoidが現れることは無く、あくまで「この関数は値を返さなかった」という事実をコールフレームの巻き戻し処理に伝えるためだけの単位値です。
match value {
Some(expr) => self.compile_expr(expr, line, column)?,
None => self.chunk.write_op(OpCode::Void, line),
}
self.chunk.write_op(OpCode::Return, line);関数の本体がreturn文で終わらずに最後まで実行された場合に備えて、すべての関数の末尾には無条件でOP_VOID・OP_RETURNを追加しています。値を返す関数がこの暗黙のreturnに到達してしまうのはバグですが、それは次に説明する型検査で事前に弾いています。
戻り値のある関数が全パスでreturnしているかを構造的に検査する
戻り値の型を宣言した関数の本体を最後まで実行しても一度もreturnしなかった場合、呼び出し元は本来int型を期待している場所にValue::Voidを受け取ってしまいます。これは実行時の型エラーであり、型検査で事前に防ぐべきものです。
厳密に「すべての実行パスを通ってもreturnに到達するか」を判定するには制御フロー解析が必要ですが、この処理系では次のような保守的な構造チェックにとどめました。
fn block_always_returns(block: &Block) -> bool {
block.iter().any(stmt_always_returns)
}
fn stmt_always_returns(stmt: &Stmt) -> bool {
match &stmt.kind {
StmtKind::Return(_) => true,
StmtKind::Block(block) => block_always_returns(block),
StmtKind::If { then_branch, else_branch: Some(else_branch), .. } => {
block_always_returns(then_branch) && stmt_always_returns(else_branch)
}
_ => false,
}
}returnそのものはもちろん、ifにelseがあり両方の枝が必ずreturnしているならそのif文自体も「必ずreturnする」とみなします。一方whileやforは、たとえwhile (true) { ... }のように無限ループになる場合でも「必ずreturnする」とはみなしません。ループの中身がreturnするかどうかより先に、ループ自体が本当に無限に回り続けるかを判定する方がずっと難しい問題だからです。これはbreak・continueのループ外チェックと同じく、「完璧な解析より、実装コストに見合う保守的な近似を選ぶ」という、この処理系で繰り返し採っている方針です。
トップレベルはあえて「関数」として統一しなかった
ここまでの説明で気づいた方もいるかもしれませんが、この処理系のスクリプト全体（トップレベル）は、コールフレームの仕組みに一切乗っていません。バイトコードVMの教科書的な実装では、スクリプト全体を「引数0個の暗黙の関数」とみなし、実行開始時から最初のコールフレームとして扱うのが標準的です。しかしこの処理系はそうしませんでした。
pub struct Vm {
chunk: Chunk,
ip: usize,
stack: Vec<Value>,
frames: Vec<CallFrame>, // トップレベルのぶんのフレームはここには積まれない
globals: HashMap<String, Value>,
}トップレベル用のchunk/ipをVm自身のフィールドとして残し、framesは実際の関数呼び出しが起きたときだけ使う、という2本立てにしています。OP_RETURNの実装でself.frames.pop()がNoneだった場合に単にrunを終了してスタックには一切触れないのは、この設計のためです。
理由は、この処理系にはまだprintに相当する組み込み関数が無く、動作確認やテストを「実行後にVMのスタックをそのまま覗く」という方法に頼っていることにあります。トップレベルをコールフレームとして統一すると、プログラムの終了時に暗黙のOP_RETURNが実行され、トップレベルのletで作ったローカル変数がすべて巻き戻されて消えてしまいます。これは教科書的には正しい統一の仕方ですが、この時点でそれを選ぶと、既存のテスト資産と暫定的な動作確認手段の両方を失うことになります。
組み込み関数を導入し、printで本当の意味での出力ができるようになった段階で、この特別扱いを見直すかどうかをあらためて判断する予定です。
動作確認
再帰と相互再帰の両方を含むプログラムを実行してみます。
fn fib(n: int): int {
if (n < 2) {
return n;
}
return fib(n - 1) + fib(n - 2);
}
fn is_even(n: int): bool {
if (n == 0) { return true; }
return is_odd(n - 1);
}
fn is_odd(n: int): bool {
if (n == 0) { return false; }
return is_even(n - 1);
}
let a = fib(10);
let b = is_even(7);
let c = is_odd(7);$ cargo run -- examples/fib.na
stack after execution: [Int(55), Bool(false), Bool(true)]fib(10)が正しく55を返し、ソース上でis_evenより後に定義されているis_oddを先に呼び出しても（is_evenの本体はis_oddをまだコンパイルされていない段階で参照しています）正しくfalse/trueを返しています。関数まわりのテストは、型検査・コンパイラ・VMを合わせて19件追加し、既存の66件と合わせて85件が通ることを確認しています。
備考
関数はまだ「値」として扱えない
fn宣言はトップレベルにしか書けず、関数を変数に代入したり、引数として渡したりすることはできません。Expr::Callのcalleeは直接の関数名（識別子）だけを受け付けるよう型検査で制限しています。関数を第一級の値にするにはクロージャの仕組み（自由変数のキャプチャ、コンパイル時の解決）が必要で、これは今後の実装課題です。
コールスタックの深さ制限は依然として無い
以前スタックマシンVMを実装した時点で、self.stack: Vec<Value>が際限なく伸びる実装になっており深い再帰への対策が無いことに触れていましたが、関数（したがって再帰）を導入した今もこれは変わっていません。ただし正確には、深すぎる再帰によって壊れるのはRustのネイティブなコールスタックではありません。Vm::run自体は再帰しない1つのループなので、危険なのはself.framesとself.stackという2つのVecが際限なく伸びていくことによるメモリ枯渇です。ネイティブなスタックオーバーフローのような即座のクラッシュにはならない代わりに、検出も難しい失敗の仕方をします。
引数の個数・型の不一致はランタイムでは検証していない
OP_CALLはdebug_assert_eq!で引数の個数を検証していますが、これはリリースビルドでは無効になります。型検査を通過したプログラムである以上、呼び出し時の引数の個数・型が関数のシグネチャと一致していることは保証されているという前提に立ち、実行時の本番コストとしては検証しない設計です。