Pythonで作る自作インタプリタ入門シリーズ
Part1【字句解析】 | Part2【構文解析】 | Part3【AST構築】 | Part4【評価器】 | Part5【スコープ】
はじめに
いよいよ本番！ASTを実際に評価して動かす。
目標：このコードが動くインタプリタを作る
fn factorial(n) {
if n <= 1 {
return 1;
}
return n * factorial(n - 1);
}
print(factorial(5)); # 120
再帰関数も動く！
インタプリタの構造
インタプリタは3つの部品でできている：
- Environment: 変数を管理
- Function: ユーザー定義関数を表現
- Interpreter: ASTを評価
Environment（環境）
変数のスコープを管理するクラス。親環境へのポインタを持つことで、スコープチェーンを実現。
class Environment:
"""変数のスコープを管理"""
def __init__(self, parent: Optional['Environment'] = None):
self.variables: Dict[str, Any] = {}
self.parent = parent
def define(self, name: str, value: Any):
"""変数を定義"""
self.variables[name] = value
def get(self, name: str) -> Any:
"""変数を取得"""
if name in self.variables:
return self.variables[name]
if self.parent:
return self.parent.get(name) # 親スコープを探す
raise NameError(f"Undefined variable: {name}")
def set(self, name: str, value: Any):
"""変数に代入"""
if name in self.variables:
self.variables[name] = value
return
if self.parent:
self.parent.set(name, value)
return
raise NameError(f"Undefined variable: {name}")
スコープチェーンのイメージ：
グローバル環境
├── x = 10
├── add = <Function>
│
└── 関数呼び出し時の環境
├── a = 1 (引数)
├── b = 2 (引数)
└── 親 → グローバル環境
Function（関数）
ユーザー定義関数を表現。クロージャも対応。
class Function:
"""ユーザー定義関数"""
def __init__(self, name: str, params: List[str], body: List[Stmt], closure: Environment):
self.name = name
self.params = params
self.body = body
self.closure = closure # 定義時の環境を保持（クロージャ）
closure が重要。関数が定義された時点の環境を保持することで、クロージャが実現できる。
return文の実装
return文は例外を使って実装するのが簡単。
class ReturnException(Exception):
"""return文の値を伝播するための例外"""
def __init__(self, value: Any):
self.value = value
return文に遭遇したら例外を投げて、関数呼び出し側でキャッチ。
Interpreterクラス
基本構造
class Interpreter:
"""インタプリタ"""
def __init__(self):
self.global_env = Environment()
self.output: List[str] = [] # print出力を記録
def run(self, program: Program):
"""プログラムを実行"""
for stmt in program.statements:
self.execute(stmt, self.global_env)
文の実行
def execute(self, stmt: Stmt, env: Environment):
"""文を実行"""
if isinstance(stmt, LetStmt):
value = self.evaluate(stmt.value, env)
env.define(stmt.name, value)
elif isinstance(stmt, AssignStmt):
value = self.evaluate(stmt.value, env)
env.set(stmt.name, value)
elif isinstance(stmt, IfStmt):
condition = self.evaluate(stmt.condition, env)
if self.is_truthy(condition):
self.execute_block(stmt.then_body, env)
elif stmt.else_body:
self.execute_block(stmt.else_body, env)
elif isinstance(stmt, WhileStmt):
while self.is_truthy(self.evaluate(stmt.condition, env)):
self.execute_block(stmt.body, env)
elif isinstance(stmt, ReturnStmt):
value = None
if stmt.value:
value = self.evaluate(stmt.value, env)
raise ReturnException(value) # 例外で脱出！
elif isinstance(stmt, PrintStmt):
value = self.evaluate(stmt.value, env)
print(value)
elif isinstance(stmt, FnDef):
func = Function(stmt.name, stmt.params, stmt.body, env)
env.define(stmt.name, func)
ポイント：
- return文は例外で実装
- 関数定義時に現在の環境を保存（クロージャ）
式の評価
def evaluate(self, expr: Expr, env: Environment) -> Any:
"""式を評価"""
if isinstance(expr, NumberLit):
return expr.value
if isinstance(expr, StringLit):
return expr.value
if isinstance(expr, BoolLit):
return expr.value
if isinstance(expr, Var):
return env.get(expr.name)
if isinstance(expr, BinOp):
return self.eval_binop(expr, env)
if isinstance(expr, UnaryOp):
return self.eval_unary(expr, env)
if isinstance(expr, Call):
return self.eval_call(expr, env)
二項演算
def eval_binop(self, expr: BinOp, env: Environment) -> Any:
"""二項演算を評価"""
# 短絡評価（&&と||）
if expr.op == "&&":
left = self.evaluate(expr.left, env)
if not self.is_truthy(left):
return False
return self.is_truthy(self.evaluate(expr.right, env))
if expr.op == "||":
left = self.evaluate(expr.left, env)
if self.is_truthy(left):
return True
return self.is_truthy(self.evaluate(expr.right, env))
# 通常の演算
left = self.evaluate(expr.left, env)
right = self.evaluate(expr.right, env)
ops = {
"+": lambda a, b: a + b,
"-": lambda a, b: a - b,
"*": lambda a, b: a * b,
"/": lambda a, b: a / b,
"%": lambda a, b: a % b,
"<": lambda a, b: a < b,
"<=": lambda a, b: a <= b,
">": lambda a, b: a > b,
">=": lambda a, b: a >= b,
"==": lambda a, b: a == b,
"!=": lambda a, b: a != b,
}
return ops[expr.op](left, right)
短絡評価を忘れずに！false && something() は something() を評価しちゃダメ。
関数呼び出し（再帰対応）
ここが一番大事！
def eval_call(self, expr: Call, env: Environment) -> Any:
"""関数呼び出しを評価"""
func = env.get(expr.name)
if not isinstance(func, Function):
raise RuntimeError(f"{expr.name} is not a function")
if len(expr.args) != len(func.params):
raise RuntimeError(
f"Function {expr.name} expects {len(func.params)} arguments, got {len(expr.args)}"
)
# 引数を評価
args = [self.evaluate(arg, env) for arg in expr.args]
# 新しい環境を作成（クロージャを親に）
func_env = Environment(func.closure)
for param, arg in zip(func.params, args):
func_env.define(param, arg)
# 関数本体を実行
try:
for stmt in func.body:
self.execute(stmt, func_env)
return None # 明示的なreturnがなければNone
except ReturnException as e:
return e.value
再帰が動く理由：
- 関数定義時に、その関数自身を環境に登録
- 関数呼び出し時に、**クロージャ（定義時の環境）**を親にした新環境を作る
- その環境には関数自身が含まれている
- だから関数内から自分自身を呼べる！
動かしてみる
テストコード：
source = '''
let x = 10;
let y = 20;
fn add(a, b) {
return a + b;
}
fn factorial(n) {
if n <= 1 {
return 1;
}
return n * factorial(n - 1);
}
print(add(x, y));
print(factorial(5));
let i = 1;
while i <= 5 {
print(i);
i = i + 1;
}
if x > 5 {
print("x is greater than 5");
} else {
print("x is not greater than 5");
}
'''
lexer = Lexer(source)
tokens = lexer.tokenize()
parser = Parser(tokens)
ast = parser.parse_program()
print("=== Running Program ===")
interpreter = Interpreter()
interpreter.run(ast)
実行結果
=== Running Program ===
30
120
1
2
3
4
5
x is greater than 5
完璧！
-
add(10, 20)= 30 ✓ -
factorial(5)= 120 ✓（再帰！） - while文 ✓
- if文 ✓
- 文字列出力 ✓
truthy/falsyの判定
Pythonらしく、値の「真偽」を判定する関数：
def is_truthy(self, value: Any) -> bool:
"""値が真かどうか"""
if value is None:
return False
if isinstance(value, bool):
return value
if isinstance(value, (int, float)):
return value != 0
if isinstance(value, str):
return len(value) > 0
return True
これで if 0 { ... } は実行されない、みたいな挙動ができる。
まとめ
今回実装したもの：
- Environment: スコープチェーンで変数管理
- Function: クロージャ対応の関数
- Interpreter: ASTを評価して実行
ポイント：
- return文は例外で実装すると楽
- クロージャ = 定義時の環境を保持
- 再帰はスコープチェーンで自然に動く
次回は最終回、変数スコープをもっと深掘りする！
次回予告
Part5: 変数スコープ実装で発狂しかけた【完結】
シャドーイング、クロージャ、スコープの闇に迫る！