文法は正しいのに意味が違う — 意味解析
一言でいうと
パーサーが組み立てた木は、文法が合っているだけです。意味解析は、その木をもう一度たどりながら、名前ごとにどの宣言を指しているか(名前解決)と、わかる範囲で型が合っているかを実行前に確認し、見つけた間違いを位置順にすべて集めて知らせます。
なぜ必要なのか
print cnt;は、文法上は問題ありません。ところが、宣言した名前がcountだったなら、インタプリターはその行に到達した瞬間にやっと止まります。その行が月に1回だけ回る精算の分岐の中にあれば、1か月後にです。実行しなくてもわかる間違いは、実行前に知らせるべきです。その境界がどこにあるのかを決めるのが、意味解析です。
- 名前: 使われた名前がどの宣言を指すのか。なければエラー、同じスコープで2回宣言してもエラー、
let x = x + 1;のように宣言の途中で自分自身を読んでもエラーです。 - 構造: 関数の外の
return、引数の数が違う呼び出しです。 - 型:
1 + true、条件が整数のif (n)です。
名前解決の結果は、エラーだけではありません。「このxは3行目のそのxです」という表が、あとの段階の材料になります。インタプリターはこの表のおかげで、シャドーイングされた名前を取り違えず、コンパイラーはこの表で、ローカル変数のスロット番号を決めます。
どう動くのか
スコープはスタックです。いちばん下がグローバルで、ブロックや関数に入るたびに空の辞書を1つ積み、出るときに捨てます。名前を探すときは内側から見ます。そのため、内側の同じ名前が外側のものを隠します(シャドーイング)。ブロックを出るときに辞書を捨てないと、内側の名前が外に漏れ出します。スコープの漏れです。
let x = 1; 스택 [ {x:1:5} ]
{ 스택 [ {x:1:5}, {} ]
let x = true; 스택 [ {x:1:5}, {x:3:7} ] ← 여기서 x 는 3:7 (bool)
print !x;
} 스택 [ {x:1:5} ] ← 안쪽 사전을 버린다
print x + 1; x 는 다시 1:5 (int)
宣言は2回に分けて入れます。letは、名前をまず「まだ定義されていない」として入れ、初期値を検査してから「定義済み」に変えます。その間に同じスコープで自分の名前を読むと、「自分の初期値からの読み取り」エラーです。逆に、関数は名前を先に完全に入れてから本体を検査します。そうすれば、本体の中で自分自身を呼べます(再帰)。仮引数と本体のいちばん外側の宣言は、1つのスコープを使います。fn f(a) { let a = 1; }は重複です。
型はわかる範囲だけ見ます。ミニは、仮引数に型を書きません。そのため、fn f(p) { return p + 1; }のpは型がわかりません。わからないところまでエラーにすると、正常なプログラムが拒否され(誤検知)、わからないところを何でもよいものとして扱うと、あとで嘘をつくことになります。そのため、規則は1つです。両側の型がわかるときだけ検査し、わからなければ通します。通した箇所は、実行時にインタプリターがもう一度検査します。この方式を漸進的型検査と呼びます。
| 式 | 要求 | 結果 |
|---|---|---|
+ - * / % ^、前に付く- |
両側がint | int |
< <= > >= |
両側がint | bool |
== != |
両側が同じ型 | bool |
! && || |
bool | bool |
if・whileの条件 |
bool | — |
| 呼び出し | 名前で直接呼ぶ関数なら、引数の数が合う必要がある | 不明 |
エラーは、見つけた順ではなく位置順に並べます。木をたどる順序は実装ごとに違うことがありますが(演算子のノードを先に見るか、オペランドを先に見るか)、ユーザーが読む順序は、ファイルの上から下です。
現場での姿
- 静的検査をどこまで行うかが、言語の性格を決めます。Pythonは、名前のエラーでさえ実行しないとわからず(そのため、mypyやpyrightのようなツールが別にあります)、Javaは、型と名前をコンパイルですべて見ます。Rustはさらに進んで、値がいつまで生きているかと、だれが変更できるかまで、コンパイル時に見ます。その話は、Rust — コンパイラが止めるものコースが、エラーメッセージを読みながら扱います。このモジュールのスコープスタックは、それらの検査器がすべて土台にしているものです。
- シャドーイングの警告。多くのリンターが「外側の変数を隠している」を警告にしています。エラーではありませんが、スコープの漏れとシャドーイングを取り違えて生じるバグが多いからです。
- 誤検知のコスト。静的検査器が正常なコードを何度もエラーにすると、人は検査器を切ってしまいます。「わからなければ通す」という規則は緩く見えますが、検査器をずっと有効にしておくための規則です。
次のラボですること
checker.pyに、スコープスタック、名前解決(ブロック・シャドーイング・自分の初期値の読み取り)、関数・return・呼び出しの検査、わかる範囲だけを見る型検査、条件の型と結果の整理(analyze)を順に作ります。採点ツールは、エラー一覧と名前解決の表を基準と丸ごと突き合わせ、ランダムに作った正しいプログラムで誤検知がないか、1か所ずつ壊したプログラムで同じエラーを同じ位置に出すかを確認します。