How it works
The Interpreter
The interpreter is where the program actually runs. It walks the AST node by node, executing statements and evaluating expressions, managing variable scope through a chain of environments.
Input
Program
received from previous stage
Output
int
passed to next stage
Source
interpreter.py
271 lines
What is a tree-walking interpreter?
A tree-walking interpreter executes a program by recursively visiting each node in the AST and calling the appropriate handler. No intermediate representation (bytecode, machine code) is produced. The AST is the only thing the interpreter ever operates on.
NATIVE COMPILED (C, Rust, Go) ───────────────────────────────────────────────────────────────────── Source ──▶ Compiler ──▶ x86 machine code ──▶ CPU executes directly Speed: fastest Complexity: very high Build step: required BYTECODE VM (CPython, JVM, Lua) ───────────────────────────────────────────────────────────────────── Source ──▶ Compiler ──▶ bytecode ──▶ virtual machine interprets Speed: fast Complexity: high Build step: implicit on first run TREE-WALKING (kemlang-py, early Ruby 1.x, MRI before YARV) ───────────────────────────────────────────────────────────────────── Source ──▶ Lexer ──▶ Parser ──▶ AST ──▶ walk and execute directly Speed: slow Complexity: low Build step: none Best for: scripting, education, rapid prototyping
Execute vs. evaluate
The interpreter has two recursive entry points. execute() handles statements - it produces side effects (printing, assigning variables) and returns nothing. evaluate() handles expressions - it returns a KemValue.
def execute(self, stmt: Stmt):
"""Execute a statement - side effects only, no return value."""
if isinstance(stmt, Print): return self.execute_print(stmt)
if isinstance(stmt, Declaration): return self.execute_declaration(stmt)
if isinstance(stmt, Assignment): return self.execute_assignment(stmt)
if isinstance(stmt, If): return self.execute_if(stmt)
if isinstance(stmt, While): return self.execute_while(stmt)
if isinstance(stmt, Block): return self.execute_block(stmt)
if isinstance(stmt, Break): raise BreakError()
if isinstance(stmt, Continue): raise ContinueError()
def evaluate(self, expr: Expr) -> KemValue:
"""Evaluate an expression - returns a KemValue."""
if isinstance(expr, Literal): return expr.value
if isinstance(expr, Variable): return self.environment.get(expr.name)
if isinstance(expr, Binary): return self.evaluate_binary(expr)
if isinstance(expr, Unary): return self.evaluate_unary(expr)
if isinstance(expr, Input): return self.input_fn().rstrip("\n")Environments and variable scope
Variables are stored in an Environment - a dict (dict[str, KemValue]) with a reference to an optional parent. The interpreter always has a current environment; it starts as global and is temporarily replaced when entering a block.
class Environment:
def __init__(self, enclosing: Optional["Environment"] = None):
self.values: dict[str, KemValue] = {}
self.enclosing = enclosing # parent environment
def define(self, name: str, value: KemValue):
if name in self.values:
raise RuntimeError(f"Variable '{name}' already declared")
self.values[name] = value
def get(self, name: str) -> KemValue:
if name in self.values:
return self.values[name]
if self.enclosing:
return self.enclosing.get(name) # walk up the chain
raise RuntimeError(f"Undefined variable '{name}'")
def assign(self, name: str, value: KemValue):
if name in self.values:
self.values[name] = value
return
if self.enclosing:
self.enclosing.assign(name, value)
return
raise RuntimeError(f"Undefined variable '{name}'")def execute_block(self, stmt: Block):
previous = self.environment
try:
self.environment = Environment(self.environment) # push new scope
for statement in stmt.statements:
self.execute(statement)
finally:
self.environment = previous # always restore, even on exceptionControl flow via Python exceptions
tame jao (break) and aagal vado (continue) need to unwind the call stack instantly, potentially through several nested recursive calls. kemlang-py raises Python exceptions instead of threading a flag through every call frame.
def execute_while(self, stmt: While):
"""farvu { body } jya sudhi condition
Note: body executes FIRST, condition checked AFTER (do-while semantics)."""
try:
while True:
with contextlib.suppress(ContinueError):
self.execute(stmt.body) # run the block
condition = self.evaluate(stmt.condition)
if not self.is_truthy(condition):
break # normal loop exit
except BreakError:
pass # tame jao -> exit immediately
i = 1 (declared before loop)
Iter 1:
execute(Block)
execute(Print) evaluate Variable("i") -> 1 -> output "1"
execute(Assignment) evaluate Binary(i+1) -> 2 -> assign i=2
evaluate condition: i <= 3 -> 2 <= 3 -> True continue
Iter 2:
execute(Block)
execute(Print) -> output "2"
execute(Assignment) -> i=3
evaluate condition: 3 <= 3 -> True continue
Iter 3:
execute(Block)
execute(Print) -> output "3"
execute(Assignment) -> i=4
evaluate condition: 4 <= 3 -> False break
stdout: "1" "2" "3" (each on its own line)Input and output
Both I/O operations use configurable callbacks so tests can capture output without patching builtins.
def __init__(
self,
input_fn: Callable[[], str] = input, # overridable for tests
output_fn: Callable[[str], None] = print, # overridable for tests
):
...
def execute_print(self, stmt: Print):
value = self.evaluate(stmt.expression)
self.output_fn(self.stringify(value)) # calls print() by default
# Input is an expression node, evaluated when encountered:
if isinstance(expr, Input):
return self.input_fn().rstrip("\n") # calls input() by defaultError handling
def interpret(self, program: Program) -> int:
try:
for statement in program.statements:
self.execute(statement)
return 0 # success
except RuntimeError as e:
self.output_fn(f"Runtime Error: {e.message}")
return 1 # error -> exit code 1