Interpreters

From objects (last time) to a program that runs programs (today)

• Last time: classes $\to$ objects, __init__, self
• Today: interpreter $=$ program that evaluates program data
• Driving question: how can eval + environments model "running code"?

An interpreter is a "universal machine"

• Input: program text $\to$ data structure
• Process: repeated reduction of expressions $\to$ values
• Output: behavior (and sometimes a value)

Parsing: text $\to$ tokens $\to$ $\mathrm{AST}$

• Text: "(+ 1 (* 2 3))"
• Tokenizing trick: add spaces around parentheses, then split on whitespace; extra $spaces/newlines$ are ignored
• Example pre-split: " ( + 1 ( * 2 3 ) ) " $\to$ split
• Tokens: ['(', '+', '1', '(', '*', '2', '3', ')', ')']
• AST forms: atoms parse into int/float (e.g., via int(token) / float(token)) or symbol strings; lists parse into Python lists
• $\mathrm{AST}$: ['+', 1, ['*', 2, 3]]

A tiny calculator evaluator (before variables!)

• Rule $1$: number $\to$ itself
• Rule $2$: list ['+', ...] $\to$ evaluate pieces, then combine
• Prediction: ['*', ['+', 1, 2], ['+', 3, 4]] $\to$ $21$

eval is a dispatcher: expression type decides the rule

$$ \text{eval} : (\text{exp}, E) \to \text{value} $$

• Example environment chain: $E_0 = {x\mapsto 3}\;\rightarrow\;E_1={+\mapsto \text{prim}+}\;\rightarrow\;\text{None}$
• Name $x$: lookup in environment $E$ (check current frame, then parent, until found)
• Combination: evaluate operator, evaluate operands, then apply

apply: where environments get extended

• Primitive procedure $p$: call underlying Python function
• Compound procedure $f$: new frame binds params $\to$ args
• Evaluate body in child environment $E'$

The $\mathrm{Eval}/\mathrm{Apply}$ cycle: mutual recursion as the engine

• eval on a call expression $\to$ needs apply
• apply on a compound procedure $\to$ needs eval (for the body)
• Cycle ends at primitives $+$ literals

Special forms: syntax with custom evaluation rules

• if: evaluate the condition, then evaluate only the selected branch

A mini interpreter can run a tiny "program"

• Program as data: ['define', 'square', ['lambda', ['x'], ['*', 'x', 'x']]]
• Then: ['square', 5]
• Predict: what will ['square', 5] evaluate to, and which frame will contain x?
• Result: value $25$ (via repeated $\mathrm{Eval}/\mathrm{Apply}$)

Extending the language: add unless as a derived expression

$$ (\texttt{unless}\ c\ a\ b)\;\Rightarrow\;(\texttt{if}\ c\ b\ a) $$

• Implementation move: add one new tag case in eval
• Payoff: language design becomes a small change

Exit ticket: predict, then justify using $\mathrm{Eval}/\mathrm{Apply}$

• Practice: predict value of ['+', 1, ['unless', False, 10, 20]]
• Reflection: why must if be a special form, not an ordinary function?