スコープと名前解決、分かるところだけの型検査

目標

パーサーが作った木をたどりながら、名前ごとに宣言をつなぎ(名前解決)、実行前にわかる間違い、すなわち存在しない名前、重複宣言、自分の初期値の読み取り、関数の外のreturn、引数の数、わかる範囲の型を、位置順にすべて集めます。

なぜ重要なのか

実行しないと表に出ないエラーは、その行が回るまで隠れています。逆に、検査器が正常なプログラムを拒否すると、人は検査器を切ります。そのため、意味解析の核心はどこまでを確実に知っているかを決めることで、このラボの採点は「見逃したエラー」と「誤検知」を同じ重さで見ます。

ルール

스코프     맨 아래가 전역. 블록마다, 함수마다 하나씩 쌓는다. 찾기는 안쪽부터.
           함수의 매개변수와 몸체의 맨 바깥 선언은 한 스코프다.
let        이름을 '정의 전' 으로 먼저 넣고 → 초기값 검사 → '정의됨'. 선언의 타입 = 초기값의 타입.
fn         이름을 (fn, 인자 수) 로 먼저 넣고 → 새 스코프에 매개변수(타입 모름) → 몸체.
타입       int · bool · fn · 모름(None). 양쪽을 다 알 때만 검사한다.
           + - * / % ^ 앞 - : int → int      < <= > >= : int → bool
           == != : 두 쪽이 같은 타입 → bool   ! && || : bool → bool
           대입: 이름의 타입과 값의 타입을 다 알면 같아야. 대입식의 타입 = 값의 타입. 호출의 결과 = 모름.
이름 해석  "쓴 곳 줄:칸" → "선언 줄:칸" (선언 위치는 let·fn 은 이름 토큰, 매개변수는 그 이름 토큰)
오류 글자  (줄, 칸, 메시지)를 모아 두었다가 (줄, 칸) 순으로 "줄:칸: 메시지"
  undefined variable 'x'                         쓴 곳
  'x' is already declared in this scope          두 번째 선언의 이름
  cannot read 'x' in its own initializer         쓴 곳
  return outside function                        return 키워드
  function 'f' takes 2 arguments, got 3          여는 괄호(이름으로 직접 부를 때만)
  cannot call int                                여는 괄호(부르는 쪽 타입이 int·bool 일 때)
  operator '+' expects int, got bool             연산자 (피연산자마다 따로)
  operator '==' compares int with bool           연산자
  cannot assign bool to 'x' (int)                =
  condition must be bool, got int                if·while 키워드

ステップ

/root/mini/checker.pyのDecl(name, line, col, type_=None, arity=None, defined=True)とScopes(push・pop・declare(すでにあればFalse)・lookup・innermost)を埋めます。
Checkerのerror・declare・use・statements・stmt・exprを埋めます。let・ブロック・print・式文、名前・代入を扱います。呼び出しはcall、演算子はtyped_expr、if・whileはcondition、fn・returnはfunction_stmtに渡します。
function_stmtとcallを埋めます。再帰できるように名前を先に入れ、仮引数と本体は1つのスコープ、関数の外のreturn、引数の数を扱います。
ARITH・ORDER・want・typed_exprを埋めます。わからない型は通します。
conditionと、モジュールのanalyze(program)、check、resolveを埋めます。戻り値は(오류 글자 목록, 이름 해석 표)です(プレースホルダーはエラー文字列の一覧と名前解決の表です)。
採点ツールが、固定プログラムと厄介なスコープ(クロージャが見た名前、枝ごとのスコープ、ループ内のシャドーイング)の名前解決の表を、丸ごと突き合わせます。
採点ツールが、エラープログラム(/opt/fixtures/mini/errors/check-*.miniとさらに数個)のエラー一覧を突き合わせます。
採点ツールが、ランダムな正しいプログラム120個(誤検知がないこと)と、1か所ずつ壊した120個を突き合わせます。

参考

python3 /root/mini/mini.py check 파일.miniが、自分の検査器でエラーを出力します(プレースホルダーはファイル名です)。
レキサー・パーサー・ノードは、ラボを開始するときに置かれています(前のモジュールで作った自分のものを貼り付けてもかまいません)。
よくある間違いは、ブロックを出るときにスコープを捨てない(漏れ)、初期値を先に検査してlet x = x;が外側のxを指してしまう、わからない型をエラーにする(誤検知)、エラーを見つけた順に返す、の4つです。
セッションは60分で始まり、＋時間で延ばせます。終わると/root/miniが消えます。

スコープスタック

stackは辞書のリストで、いちばん下がグローバルです。declareは一番上の辞書にだけ入れ、すでにあれば何も変えずにFalseです。lookupはreversed(stack)で内側から探します。innermostは一番上の辞書だけを見ます。

名前を宣言につなぐ

letはDecl(defined=False)を先にdeclareし、初期値の型を求めてからdefined=Trueに変えます。useは、innermostが「定義前」なら自分の初期値の読み取りエラー、lookupがNoneなら存在しない名前、見つかればresolvedに「使った位置 → 宣言」を書きます。ブロックはpush・popで包みます。

関数、return、呼び出し

fnはDecl(名前, 'fn', 引数の数)を今のスコープに先に入れ、pushしてから仮引数を入れ、本体の文をそのスコープでそのまま検査します(本体のブロックをもう一度pushしません)。関数の深さを数えておけば、returnが関数の外かどうかがわかります。

わかる範囲だけを見る型

want(ノード, 演算子, 受け取った型, 期待する型)は、受け取った型がNoneなら何も言いません。オペランドを1つずつ別に検査するので、1 + trueはエラーが1つ、true + falseは2つです。結果の型は、検査の結果と関係なく演算子が決めます。

条件とエラーの整理

conditionは、条件の型がわかっていてboolでなければ、キーワードの位置でエラーを出し、枝(ブロック)をstmtで検査します。ブロックがスコープを積んでくれます。analyzeは、エラー一覧を(行, 桁)で並べ替えてから文字列に変えます。

シャドーイングとスコープの漏れ

新しいコードはありません。名前解決の表がずれたら、どの使った位置が見当違いの宣言につながったかを、メッセージが教えてくれます。ブロックが終わったあとの名前が内側の宣言につながっていたなら、popを忘れています。ifの枝の宣言が互いにぶつかるなら、枝をブロックとして検査していません。

エラープログラムを1文字まで合わせる

新しいコードはありません。メッセージの文字列・位置・順序がすべて同じである必要があります。引数の数のエラーは名前で直接呼ぶときだけ(値として受け取った関数は不明)、代入のエラーは=の位置、条件のエラーはキーワードの位置です。

誤検知と見逃しを同時に測る

新しいコードはありません。正しいランダムなプログラムでエラーが出るなら、わからない型(仮引数・呼び出しの結果)を検査しています。壊したプログラムでエラーが足りないなら、名前が見つからなかったときに止まっているか、同じ式の2つ目のエラーを捨てています。