用环境与闭包执行语法树

目标

做出一个遍历 AST 并直接执行的解释器。遵守 64 位整数、向 0 截断的除法、区分 bool 与 int 的规则，通过环境链和闭包查找名字，运行时错误则报告在该运算符的位置。这个解释器将成为后面模块（VM、原生代码）的基准。

为什么重要

如果定义含义的那个实现错了，后面所有实现都会按错误的基准来对齐。用 Python 写的解释器里，Python 的含义——无限增大的整数、向下取整的 //、True == 1——会悄悄混进来。本实验会把这些泄漏逐个堵上。

规则

값          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

步骤

补全 /root/mini/interp.py 的 RuntimeErr、Function、ReturnSignal，以及 wrap、div、mod、power、type_name 和 show。
补全 Env 的 define、find（没有则 KeyError）、get 和 assign。
补全 Interpreter 的 need、evaluate（字面量、名字、赋值、一元、逻辑、二元）和 binary。调用交给 call（第 6 步）。
补全 execute（let、print、表达式语句、块）和 run_block。if 和 while 交给 control（第 5 步），fn 和 return 交给 function_stmt（第 6 步）。
补全 condition 和 control。
补全 function_stmt 和 call——声明时的环境、实参个数、深度、return。
补全模块级的 run_program(program) 和 run_source(src)。run_program 返回 (출력 줄 목록, 오류 글자 또는 None)（占位符依次为输出行列表、错误文字），即使出错，也保留此前的输出；run_source 在解析或语义分析出错时返回 ([], 첫 오류)（占位符为第一个错误）。
评分器会把 150 个随机程序（混有溢出、运行时错误和闭包）与参考对照。

参考

可以用 python3 /root/mini/mini.py run /opt/fixtures/mini/programs/closures.mini 来运行。
一次 mini 调用会用掉好几个 Python 帧，所以要在 run_program 里把 sys.setrecursionlimit 调得足够大，之后再恢复。
常见错误：直接使用 Python 的整数、// 和 %，用 isinstance(v, int) 把 bool 当作 int，赋值在当前环境里新建名字，把调用时的环境当作父环境，靠 return 跳出时没有恢复深度。
会话从 60 分钟开始，可以用＋时间延长，结束后 /root/mini 会消失。

64 位整数与 C 的除法

回绕：(x - INT_MIN) % 2 ** 64 + INT_MIN。除法：先对绝对值做 //，如果两个数的符号不同就取负。余数：a - div(a, b) * b。幂：对 pow(a, b, 2 ** 64) 做回绕，即使指数很大也能很快结束。type_name 先看 type(v) is bool。

环境之链

find 从自己开始沿着 parent 向上走，返回名字在 values 中的那个环境，一直找不到就是 KeyError。get 和 assign 读写 find 返回的那个环境里的格子——如果 assign 写到 self.values，闭包就会看到另一个格子。

计算表达式

按节点名（type(n).name）区分。Logical 先看左边是不是 bool，在 && 中为 false、在 || 中为 true 时，直接返回那个值，不计算右边。== 在两个值的 type_name 不同时是运行时错误，算术则先看两边是不是 int。

语句与块

Let 在当前环境 define，Print 把 show 出来的文字追加到 output，Block 新建一个 Env(env)，并在其中 run_block。块结束后把新环境直接丢掉就行，所以内层的名字不会泄漏到外面。

if 与 while

condition 计算条件，如果不是 bool，就在关键字位置报运行时错误。while 每次都要重新计算条件。如果 else 是 If 节点，execute 就再送回 control，沿着链走下去。

函数、闭包与 return

Fn 把 Function(节点, 当前环境) 放入 define。调用时先计算 callee 和实参并做检查，再在 Env(callee.closure) 中 define 形参，并对函数体 run_block。捕获 ReturnSignal 并返回值，深度在 finally 中恢复。

从解析一直到执行

run_program 创建 Interpreter，在全局 Env 中 run_block，捕获 RuntimeErr，并返回（此前的 output，错误文字）。run_source 如果 parse_program 和 check 有第一个错误，就不执行。

用随机程序对照

没有新代码。随机程序里混有超出 64 位的乘法、负数除法、负指数、遮蔽和计数器闭包。如果没通过，把消息指出的第一个不同的行的表达式，与第 1 步的规则对一对。