Run the Tree with Environments and Closures

Goal

You build an interpreter that walks the AST and executes it directly. You keep 64-bit integers, division toward 0, and the distinction between bool and int, find names with the environment chain and closures, and report run-time errors at that operator's position. This interpreter becomes the reference for the later modules (the VM and native code).

Why it matters

If the implementation that defines the meaning is wrong, every later implementation is fitted to a wrong reference. Python's meanings — integers that grow without end, // that rounds down, True == 1 — sneak into an interpreter written in Python. This lab plugs those leaks one by one.

The rules

값          int(64비트, 넘치면 감긴다) · bool · 함수 값 Function(선언, 선언될 때의 환경)
            show: int 는 10진수, bool 은 true/false, 함수는 <fn 이름>
            type_name 은 type() 으로 가른다 — 파이썬에서 True 는 int 이기도 하다
나눗셈      div: 0 쪽으로 자른다(-7/2 = -3) · mod: a - div(a,b)*b(부호는 나눠지는 수)
            INT_MIN / -1 = INT_MIN, INT_MIN % -1 = 0 (감긴다) · power(a, b): b ≥ 0, 2^64 로 감긴다
환경        Env(parent). define(이 환경에), get·find(사슬을 올라가며), assign(이름이 사는 환경의 칸)
            블록마다, 호출마다 새 Env. 호출 환경의 부모 = 함수 값이 붙잡은 환경(선언될 때)
            매개변수와 몸체의 맨 바깥 선언은 한 환경 · return 없이 끝나면 0
단락 평가   && 는 왼쪽이 false 면, || 는 왼쪽이 true 면 오른쪽을 계산하지 않는다(결과는 왼쪽).
            아니면 결과는 오른쪽 값(오른쪽의 타입은 쓰는 쪽이 검사한다). 왼쪽은 bool 이어야 한다
호출        callee → 인자(왼쪽부터) 계산 → 부를 수 있나 → 인자 수 → 깊이(동시에 200개까지)
오류 글자   RuntimeErr(노드, 메시지), str() 은 "줄:칸: runtime error: 메시지"(노드의 위치)
  division by zero · modulo by zero · negative exponent · stack overflow
  operator '+' expects int, got bool · operator '==' compares int with bool
  condition must be bool, got int(if·while 키워드) · cannot call int · function 'f' takes 2 arguments, got 1

Steps

1. Fill in RuntimeErr, Function, ReturnSignal, and wrap, div, mod, power, type_name, and show in /root/mini/interp.py.
2. Fill in define, find (KeyError if absent), get, and assign of Env.
3. Fill in need, evaluate (literals, names, assignment, unary, logical, binary), and binary of Interpreter. Hand calls over to call (step 6).
4. Fill in execute (let, print, expression statements, blocks) and run_block. Hand if and while over to control (step 5) and fn and return to function_stmt (step 6).
5. Fill in condition and control.
6. Fill in function_stmt and call — the environment at the time of declaration, the argument count, the depth, and return.
7. Fill in the module's run_program(program) (→ (출력 줄 목록, 오류 글자 또는 None), the list of output lines and the error text or None; even if an error occurs, the output up to that point is kept) and run_source(src) (for a parse or semantic analysis error, ([], 첫 오류), the first error).
8. The grader compares 150 random programs (mixing overflow, run-time errors, and closures) against the reference.

Notes

• You can run it with python3 /root/mini/mini.py run /opt/fixtures/mini/programs/closures.mini.
• A single Mini call uses several Python frames, so in run_program, raise sys.setrecursionlimit generously and then restore it.
• Common mistakes: using Python integers, //, and % as they are, treating bool as int with isinstance(v, int), assignment creating a new name in the current environment, taking the calling environment as the parent, and not restoring the depth when exiting through return.
• The session starts at 60 minutes and you can extend it with the +time button, and when it ends /root/mini disappears.

64-bit integers and C's division

Wrapping: (x - INT_MIN) % 2 ** 64 + INT_MIN. Division: do // on the absolute values and then make it negative if the two numbers have different signs. Remainder: a - div(a, b) * b. Exponentiation: if you wrap pow(a, b, 2 ** 64), even large exponents finish quickly. type_name checks type(v) is bool first.

The chain of environments

find climbs from itself along parent and returns the environment whose values contains the name, and raises KeyError if there is none to the end. get and assign read and write the slot of the environment that find returned — if assign writes to self.values, the closure sees a different slot.

Evaluate expressions

Dispatch on the node name (type(n).name). For Logical, after checking that the left side is a bool, if it is false for && or true for ||, return that value directly without evaluating the right side. For ==, if the type_name of the two values differs, it is a run-time error, and for arithmetic, first check that both sides are int.

Statements and blocks

Let does define in the current environment, Print appends the show text to output, and Block creates a new Env(env) and does run_block inside it. When the block ends, you can simply discard the new environment, so inner names do not leak out.

if and while

condition evaluates the condition and, if it is not a bool, is a run-time error at the keyword position. while re-evaluates the condition every time. If else is an If node, execute sends it to control again to follow the chain.

Functions, closures, and return

Fn does define of Function(node, current environment). A call first evaluates the callee and arguments and checks them, then does define of the parameters in Env(callee.closure) and run_block of the body. Catch ReturnSignal to return the value, and restore the depth in finally.

From parsing to execution

run_program creates an Interpreter, does run_block in the global Env, catches RuntimeErr, and returns (the output so far, the error text). run_source does not execute if parse_program or check has a first error.

Compare with random programs

There is no new code. The random programs mix multiplications beyond 64 bits, negative division, negative exponents, shadowing, and counter closures. If it fails, compare the expression on the first differing line that the message shows with the step 1 rules.