宣言時の環境を持ち歩く — クロージャ

一言でいうと

木をたどるインタプリターは、ASTのノードごとに「このノードに出会ったら何を計算するか」を書いた関数1つです。名前は環境(名前から値への辞書が、外側の環境を指していく連鎖)で探し、関数の値は宣言されたときの環境をいっしょに持ち歩きます。これがクロージャです。

なぜ必要なのか

モジュール6のバイトコードVMとモジュール8の機械語は速いのですが、意味を定義するには遠い存在です。「&&の左が偽なら右を計算しない」「ブロックが終わると内側の名前が消える」「関数は自分が宣言された場所の変数を見る」のような規則を、いちばんまっすぐ書ける場所が、木をたどるインタプリターです。そのため、このコースはインタプリターを基準にします。あとのVMとネイティブコードは、同じプログラムを動かしたときにインタプリターと同じ行を出力して、はじめて正しいことになります。

ただし、「まっすぐ書ける」ことが「簡単」という意味ではありません。インタプリターをPythonで書くと、Pythonの意味がこっそり混ざり込みます。

Pythonの整数は際限なく大きくなりますが、ミニの整数は64ビットで折り返します(9223372036854775807 + 1は負の数になります)。機械語がそうなるからです。
Pythonの-7 // 2は-4ですが、ミニの-7 / 2はCと同じく-3です。
PythonではTrue == 1で、isinstance(True, int)も真です。ミニでは1 == trueは実行エラーです。

意味を定義する側がこうしたものを見逃すと、あとのすべての実装が、間違った基準に合わせられてしまいます。

どう動くのか

環境は連鎖です。ブロックに入るたび、関数を呼ぶたびに新しい環境を作り、親を指すようにします。名前の検索は連鎖をたどって上がっていき、代入は、その名前が存在する環境の欄を書き換えます。今の環境に新しく作るのではありません。

fn counter(start) {           counter(10) 을 부르면
  let n = start;                [호출 환경 {start:10, n:10}] → [전역 {counter, …}]
  fn next() { n = n + 1;        next 를 선언하는 순간, 함수 값 = (next 의 선언, 지금 환경)
              return n; }
  return next;                 counter 가 끝나도 호출 환경은 next 가 붙잡고 있어 살아남는다
}
let a = counter(10);           a() → 새 환경 {} → 부모는 붙잡아 둔 호출 환경 → n 을 11 로
print a(); print a();          11, 12 — 같은 칸을 바꾸기 때문에 이어진다

関数の値を呼ぶときの環境ではなく、宣言されたときの環境を親にすることが核心です(静的スコープ)。呼ぶときの環境を親にすると(動的スコープ)、a()はcounterのnを見つけられず、グローバルに同じ名前があれば、見当違いにそれを書き換えます。クロージャが環境をコピーして持っていくのも間違いです。同じ環境をつかんでいる2つの関数(値を上げる関数と読む関数)が、別々の欄を見ることになるからです。

returnは複数の層を一度に抜けます。whileの中のifの中のreturnは、呼び出し元までまっすぐ戻る必要があります。Pythonでは、例外を1つ(ReturnSignal)投げて、呼び出し元で捕まえるのがいちばん簡単です。呼び出しが終わったら呼び出しの深さを必ず戻す必要がありますが、例外で抜ける経路で忘れやすくなります(finallyが必要な場所です)。

実行エラーは演算子の位置で知らせます。a / bでbが0なら、/の行:桁で「runtime error: division by zero」を出します。意味解析が知らずに通した型(引数として入ってきたtrue)も、ここで引っかかります。同時に生きている呼び出しが200個を超えたら、「stack overflow」で止まります。Python自身の再帰の上限に先に達すると、ユーザーにPythonのエラーを見せることになります。

現場での姿

CPythonのnonlocal宣言。Pythonのクロージャで外側の変数に代入するには、nonlocalを書く必要があります。書かないと、代入が今の環境に新しい名前を作るという規則だからです。このモジュールの「代入は名前が存在する欄を書き換える」とは正反対のデフォルトを選んだことになり、そのために生じるUnboundLocalErrorは、Pythonの初心者がいちばんよく出会うエラーの1つです。
ループ内のクロージャ。JavaScriptのvarで作ったループ変数を複数のクロージャがつかむと、すべて同じ欄(最後の値)を見ます。letがループごとに新しい環境を作るように変わった理由です。環境がいつ新しく作られるかが、そのまま言語の意味です。
基準実装。多くの言語が、仕様書とともに「遅いがまっすぐな」インタプリターを基準に置き、速いコンパイラーがそれと同じ結果を出すかを突き合わせます。このコースの採点ツールがすることも同じです。

次のラボですること

interp.pyに、値の規則(64ビットの折り返し、0方向への除算、boolとintの区別)、環境の連鎖、式の計算(短絡評価と実行中の型検査)、文とブロック、if・while、関数とクロージャ・return・呼び出しの深さ、そして構文解析から実行までをつなぐrun_sourceを作ります。採点ツールは、ランダムな数の組数百個、固定プログラム、ランダムなプログラム150個で出力した行と実行エラーを、基準と突き合わせます。