Interpreters Lab: Predict, Trace, and Extend Eval/Apply

Practice the core SICP idea of interpreters as a universal machine: parse/represent programs as data, evaluate with environments via the Eval/Apply cycle, and extend a language by adding derived expressions like `unless` (and `let`).

0. Predict: `unless` is Derived from `if` (Exit Ticket)

**Predict what will happen BEFORE running.**

This tiny evaluator supports numbers, `+`, `if`, and a derived form `unless`.

```python
# Expression to evaluate:
expr = ['+', 1, ['unless', False, 10, ['boom']]]
```

1) What value should `eval_expr(expr)` return?
2) Will it raise an error by evaluating `['boom']`?

Write your prediction as a comment, then run to check.

def eval_expr(exp):
    """Evaluate a tiny AST represented with Python lists."""
    # Atoms
    if isinstance(exp, (int, float, bool)):
        return exp

    # Lists
    if isinstance(exp, list):
        op = exp[0]

        # A special form that would error if evaluated
        if op == 'boom':
            raise RuntimeError('boom was evaluated!')

        # Derived expression: (unless c a b) == (if c b a)
        if op == 'unless':
            _, c, a, b = exp
            return eval_expr(['if', c, b, a])

        # Special form: only evaluate one branch
        if op == 'if':
            _, c, t, f = exp
            return eval_expr(t) if eval_expr(c) else eval_expr(f)

        # Primitive call: '+'
        if op == '+':
            return sum(eval_expr(e) for e in exp[1:])

    raise TypeError(f'unknown expression: {exp!r}')

expr = ['+', 1, ['unless', False, 10, ['boom']]]

# Prediction (write before running):
# I predict eval_expr(expr) returns _____ and boom (is / is not) evaluated.

# Uncomment to check:
# print(eval_expr(expr))

`unless` rewrites into an `if` with swapped branches: (unless c a b) => (if c b a).

`if` is a special form because it must not evaluate both branches.

In this expression, `False` means the `unless` should pick its 'a' branch (10).

def eval_expr(exp):
    if isinstance(exp, (int, float, bool)):
        return exp
    if isinstance(exp, list):
        op = exp[0]
        if op == 'boom':
            raise RuntimeError('boom was evaluated!')
        if op == 'unless':
            _, c, a, b = exp
            return eval_expr(['if', c, b, a])
        if op == 'if':
            _, c, t, f = exp
            return eval_expr(t) if eval_expr(c) else eval_expr(f)
        if op == '+':
            return sum(eval_expr(e) for e in exp[1:])
    raise TypeError(f'unknown expression: {exp!r}')

expr = ['+', 1, ['unless', False, 10, ['boom']]]
assert eval_expr(expr) == 11

1. Trace: Eval/Apply Creates a New Frame for a Call

Trace the **Eval/Apply cycle** for this tiny program (already parsed into ASTs).

Program:
1. `['define', 'square', ['lambda', ['x'], ['*', 'x', 'x']]]`
2. `['square', 5]`

Tasks:
- Predict the final value of evaluating expression 2.
- Then **trace** where the binding `x = 5` lives (which frame?), and why `square` can still find `*`.

Fill in the comments in `run_program()` with your trace before running.

class Frame:
    def __init__(self, parent=None):
        self.parent = parent
        self.bindings = {}

    def define(self, name, value):
        self.bindings[name] = value

    def lookup(self, name):
        if name in self.bindings:
            return self.bindings[name]
        if self.parent is None:
            raise NameError(name)
        return self.parent.lookup(name)

class Procedure:
    def __init__(self, params, body, env):
        self.params, self.body, self.env = params, body, env  # env = defining env (closure)

def eval_expr(exp, env):
    # Atoms
    if isinstance(exp, (int, float, bool)):
        return exp
    if isinstance(exp, str):
        return env.lookup(exp)

    # Lists
    op = exp[0]

    if op == 'define':
        _, name, expr = exp
        env.define(name, eval_expr(expr, env))
        return None

    if op == 'lambda':
        _, params, body = exp
        return Procedure(params, body, env)

    if op == 'if':
        _, c, t, f = exp
        return eval_expr(t, env) if eval_expr(c, env) else eval_expr(f, env)

    # application
    proc = eval_expr(op, env)
    args = [eval_expr(arg, env) for arg in exp[1:]]
    return apply(proc, args)

def apply(proc, args):
    # primitive
    if callable(proc):
        return proc(*args)

    # compound
    call_env = Frame(proc.env)
    for name, val in zip(proc.params, args):
        call_env.define(name, val)
    return eval_expr(proc.body, call_env)

def run_program():
    global_env = Frame()
    global_env.define('*', lambda a, b: a * b)

    program = [
        ['define', 'square', ['lambda', ['x'], ['*', 'x', 'x']]],
        ['square', 5],
    ]

    # TRACE (write before running):
    # 1) After the define, global_env has binding: square -> (Procedure with params ['x'], body ['*','x','x'], env=global_env)
    # 2) To eval ['square', 5], eval finds the procedure for 'square' and the value 5.
    # 3) apply makes a NEW frame whose parent is ________.
    # 4) That new frame binds x -> ________.
    # 5) When evaluating ['*','x','x'], lookup('*') succeeds because ________.

    for expr in program[:-1]:
        eval_expr(expr, global_env)
    return eval_expr(program[-1], global_env), global_env

result, env = run_program()
print('result =', result)
print('global has square?', 'square' in env.bindings)

In `apply` for a compound procedure, the call frame’s parent is the procedure’s defining environment (`proc.env`).

`x` is bound in the call frame (not in the global frame).

Looking up `*` starts in the call frame, then proceeds to its parent (global).

class Frame:
    def __init__(self, parent=None):
        self.parent = parent
        self.bindings = {}

    def define(self, name, value):
        self.bindings[name] = value

    def lookup(self, name):
        if name in self.bindings:
            return self.bindings[name]
        if self.parent is None:
            raise NameError(name)
        return self.parent.lookup(name)

class Procedure:
    def __init__(self, params, body, env):
        self.params, self.body, self.env = params, body, env

def eval_expr(exp, env):
    if isinstance(exp, (int, float, bool)):
        return exp
    if isinstance(exp, str):
        return env.lookup(exp)

    op = exp[0]
    if op == 'define':
        _, name, expr = exp
        env.define(name, eval_expr(expr, env))
        return None
    if op == 'lambda':
        _, params, body = exp
        return Procedure(params, body, env)
    if op == 'if':
        _, c, t, f = exp
        return eval_expr(t, env) if eval_expr(c, env) else eval_expr(f, env)

    proc = eval_expr(op, env)
    args = [eval_expr(arg, env) for arg in exp[1:]]
    return apply(proc, args)

def apply(proc, args):
    if callable(proc):
        return proc(*args)
    call_env = Frame(proc.env)
    for name, val in zip(proc.params, args):
        call_env.define(name, val)
    return eval_expr(proc.body, call_env)

def run_program():
    global_env = Frame()
    global_env.define('*', lambda a, b: a * b)
    program = [
        ['define', 'square', ['lambda', ['x'], ['*', 'x', 'x']]],
        ['square', 5],
    ]
    for expr in program[:-1]:
        eval_expr(expr, global_env)
    return eval_expr(program[-1], global_env), global_env

result, env = run_program()
assert result == 25
assert isinstance(env.lookup('square'), Procedure)

2. Extend: Add Derived Expressions `unless` + `let` (SICP Ex 4.6-inspired)

In this evaluator, `unless` and `let` are **not** primitive special forms. Instead, we will implement them as **derived expressions** (syntactic transformations).

Implement `desugar(exp)` so that:

- `['unless', c, a, b]` rewrites to `['if', c, b, a]`
- `['let', [[v1, e1], [v2, e2], ...], body]` rewrites to a combination:
  
  `[[ 'lambda', [v1, v2, ...], body], e1, e2, ...]`

Then the existing `eval_expr` will evaluate the rewritten form using its normal Eval/Apply rules.

After writing `desugar`, predict the value of `prog2` before running.

class Frame:
    def __init__(self, parent=None):
        self.parent = parent
        self.bindings = {}

    def define(self, name, value):
        self.bindings[name] = value

    def lookup(self, name):
        if name in self.bindings:
            return self.bindings[name]
        if self.parent is None:
            raise NameError(name)
        return self.parent.lookup(name)

class Procedure:
    def __init__(self, params, body, env):
        self.params, self.body, self.env = params, body, env

def desugar(exp):
    """Return an equivalent expression using only core forms.

    Core forms supported by eval_expr: numbers/bools, names, define, lambda, if, begin, and application.
    Derived forms to implement here: unless, let.
    """
    # YOUR CODE HERE
    # Hint: only desugar the OUTERMOST expression; you may assume the evaluator will keep desugaring as it evaluates.
    return exp

def eval_expr(exp, env):
    # Desugar one step if needed
    if isinstance(exp, list) and exp and exp[0] in ('unless', 'let'):
        exp = desugar(exp)

    # Atoms
    if isinstance(exp, (int, float, bool)):
        return exp
    if isinstance(exp, str):
        return env.lookup(exp)

    op = exp[0]

    if op == 'define':
        _, name, expr = exp
        env.define(name, eval_expr(expr, env))
        return None

    if op == 'lambda':
        _, params, body = exp
        return Procedure(params, body, env)

    if op == 'if':
        _, c, t, f = exp
        return eval_expr(t, env) if eval_expr(c, env) else eval_expr(f, env)

    if op == 'begin':
        val = None
        for e in exp[1:]:
            val = eval_expr(e, env)
        return val

    # application
    proc = eval_expr(op, env)
    args = [eval_expr(arg, env) for arg in exp[1:]]
    return apply(proc, args)

def apply(proc, args):
    if callable(proc):
        return proc(*args)
    call_env = Frame(proc.env)
    for name, val in zip(proc.params, args):
        call_env.define(name, val)
    return eval_expr(proc.body, call_env)

# --- Programs to test ---

def make_global_env():
    env = Frame()
    env.define('+', lambda a, b: a + b)
    env.define('*', lambda a, b: a * b)
    env.define('-', lambda a, b: a - b)
    return env

# Uses unless as derived from if
prog1 = ['+', 1, ['unless', False, 10, 20]]

# Uses let as derived into a lambda call
# (let ((x 2) (y 3)) (+ (* x x) y))  => 7
prog2 = ['let', [['x', 2], ['y', 3]], ['+', ['*', 'x', 'x'], 'y']]

# Prediction (write before running):
# I predict eval_expr(prog2, env) returns ______.

env = make_global_env()
# Uncomment after implementing desugar:
# print('prog1 =>', eval_expr(prog1, env))
# print('prog2 =>', eval_expr(prog2, env))

`unless`: just swap the last two operands into an `if`.

`let`: collect variable names and value expressions separately; rewrite into a lambda call.

Test t3 checks a common misconception: the RHS expressions of `let` bindings are evaluated in the *outer* environment (so `y` should see the global `x = 100`, not the new `x = 2`).

class Frame:
    def __init__(self, parent=None):
        self.parent = parent
        self.bindings = {}

    def define(self, name, value):
        self.bindings[name] = value

    def lookup(self, name):
        if name in self.bindings:
            return self.bindings[name]
        if self.parent is None:
            raise NameError(name)
        return self.parent.lookup(name)

class Procedure:
    def __init__(self, params, body, env):
        self.params, self.body, self.env = params, body, env

def desugar(exp):
    if not (isinstance(exp, list) and exp):
        return exp

    tag = exp[0]

    if tag == 'unless':
        _, c, a, b = exp
        return ['if', c, b, a]

    if tag == 'let':
        _, bindings, body = exp
        names = [name for (name, _rhs) in bindings]
        rhss = [_rhs for (_name, _rhs) in bindings]
        return [[ 'lambda', names, body], *rhss]

    return exp

def eval_expr(exp, env):
    if isinstance(exp, list) and exp and exp[0] in ('unless', 'let'):
        exp = desugar(exp)

    if isinstance(exp, (int, float, bool)):
        return exp
    if isinstance(exp, str):
        return env.lookup(exp)

    op = exp[0]

    if op == 'define':
        _, name, expr = exp
        env.define(name, eval_expr(expr, env))
        return None

    if op == 'lambda':
        _, params, body = exp
        return Procedure(params, body, env)

    if op == 'if':
        _, c, t, f = exp
        return eval_expr(t, env) if eval_expr(c, env) else eval_expr(f, env)

    if op == 'begin':
        val = None
        for e in exp[1:]:
            val = eval_expr(e, env)
        return val

    proc = eval_expr(op, env)
    args = [eval_expr(arg, env) for arg in exp[1:]]
    return apply(proc, args)

def apply(proc, args):
    if callable(proc):
        return proc(*args)
    call_env = Frame(proc.env)
    for name, val in zip(proc.params, args):
        call_env.define(name, val)
    return eval_expr(proc.body, call_env)

def make_global_env():
    env = Frame()
    env.define('+', lambda a, b: a + b)
    env.define('*', lambda a, b: a * b)
    env.define('-', lambda a, b: a - b)
    return env

env = make_global_env()
assert eval_expr(['+', 1, ['unless', False, 10, 20]], env) == 11
assert eval_expr(['let', [['x', 2], ['y', 3]], ['+', ['*', 'x', 'x'], 'y']], make_global_env()) == 7
env = make_global_env(); eval_expr(['define','x',100], env)
exp = ['let', [['x', 2], ['y', 'x']], ['+', 'x', 'y']]
assert eval_expr(exp, env) == 102