環境とクロージャで木を実行する

目標

ASTをたどりながらそのまま実行するインタプリターを作ります。64ビット整数・0方向への除算・boolとintの区別を守り、環境の連鎖とクロージャで名前を探し、実行エラーはその演算子の位置で知らせます。このインタプリターが、あとのモジュール(VM・ネイティブコード)の基準になります。

なぜ重要なのか

意味を定義する実装が間違っていると、あとのすべての実装が、間違った基準に合わせられます。Pythonで書くインタプリターには、Pythonの意味、すなわち際限なく大きくなる整数、下へ切り下げる//、True == 1が、こっそり混ざり込みます。このラボは、その漏れを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)を埋めます。前者の戻り値は(출력 줄 목록, 오류 글자 또는 None)で(プレースホルダーは出力行の一覧、エラー文字列またはNoneです)、エラーが起きても、それまでの出力は残します。後者は、構文解析や意味解析でエラーなら([], 첫 오류)を返します(プレースホルダーは最初のエラーです)。
採点ツールが、ランダムなプログラム150個(オーバーフロー・実行エラー・クロージャが混ざっています)を基準と突き合わせます。

参考

python3 /root/mini/mini.py run /opt/fixtures/mini/programs/closures.miniで実行してみられます。
ミニの呼び出し1つがPythonのフレームを複数使うので、run_programでsys.setrecursionlimitを十分に引き上げ、あとで元に戻します。
よくある間違いは、Pythonの整数・//・%をそのまま使う、isinstance(v, int)でboolをintとして見る、代入が今の環境に新しい名前を作ってしまう、呼ぶときの環境を親にする、returnで抜けるときに深さを戻さない、の5つです。
セッションは60分で始まり、＋時間で延ばせます。終わると/root/miniが消えます。

64ビット整数とCの除算

折り返し: (x - INT_MIN) % 2 ** 64 + INT_MIN。除算: absどうしで//したあと、2つの数の符号が違えば負の数に。剰余: 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なら、その値をすぐ返して右を計算しません。==は、2つの値の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の規則と見比べてみてください。