Run the Tree with Environments and Closures

목표

AST 를 걸으며 바로 실행하는 인터프리터를 만듭니다. 64비트 정수·0 쪽 나눗셈·bool 과 int 의 구분을 지키고, 환경 사슬과 클로저로 이름을 찾으며, 실행 오류는 그 연산자의 위치로 알립니다. 이 인터프리터가 뒤 모듈(VM·네이티브 코드)의 기준이 됩니다.

왜 중요한가

뜻을 정의하는 구현이 틀리면 뒤의 모든 구현이 틀린 기준에 맞춰집니다. 파이썬으로 짜는 인터프리터에는 파이썬의 뜻 — 끝없이 커지는 정수, 아래로 내리는 //, 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

단계

1. /root/mini/interp.py 의 RuntimeErr·Function·ReturnSignal 과 wrap·div·mod·power·type_name·show 를 채웁니다.
2. Env 의 define·find(없으면 KeyError)·get·assign 을 채웁니다.
3. Interpreter 의 need·evaluate(리터럴·이름·대입·단항·논리·두 항)·binary 를 채웁니다. 호출은 call 로 넘깁니다(6단계).
4. execute(let·print·식 문장·블록)와 run_block 을 채웁니다. if·while 은 control(5단계), fn·return 은 function_stmt(6단계)로 넘깁니다.
5. condition 과 control 을 채웁니다.
6. function_stmt 와 call 을 채웁니다 — 선언될 때의 환경, 인자 수, 깊이, return.
7. 모듈의 run_program(program)(→ (출력 줄 목록, 오류 글자 또는 None), 오류가 나도 그때까지의 출력은 남긴다)과 run_source(src)(파싱·의미 분석 오류면 ([], 첫 오류))를 채웁니다.
8. 채점기가 무작위 프로그램 150편(넘침·실행 오류·클로저 섞임)을 기준과 대조합니다.

참고

• python3 /root/mini/mini.py run /opt/fixtures/mini/programs/closures.mini 로 돌려 볼 수 있습니다.
• 미니 호출 하나가 파이썬 프레임 여럿을 쓰므로 run_program 에서 sys.setrecursionlimit 을 넉넉히 올렸다가 되돌립니다.
• 흔한 실수: 파이썬 정수·//·% 를 그대로 쓰는 것, isinstance(v, int) 로 bool 을 int 로 보는 것, 대입이 지금 환경에 새 이름을 만드는 것, 부를 때의 환경을 부모로 삼는 것, return 으로 빠져나갈 때 깊이를 되돌리지 않는 것.
• 세션은 60분에 시작해 ＋시간으로 늘릴 수 있고, 끝나면 /root/mini 가 사라집니다.

64비트 정수와 C 의 나눗셈

감기: (x - INT_MIN) % 2 ** 64 + INT_MIN. 나눗셈: abs 끼리 // 한 뒤 두 수의 부호가 다르면 음수로. 나머지: 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단계 규칙과 견줘 보세요.