스코프와 이름 해석, 알 수 있는 곳만 보는 타입 검사

목표

파서가 만든 트리를 걸으며 이름마다 선언을 잇고(이름 해석), 실행 전에 알 수 있는 잘못 — 없는 이름, 중복 선언, 자기 초기값 읽기, 함수 밖 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 을 채웁니다 — 재귀가 되도록 이름을 먼저, 매개변수와 몸체는 한 스코프, 함수 밖 return, 인자 수.
ARITH·ORDER·want·typed_expr 를 채웁니다 — 모르는 타입은 넘어갑니다.
condition 과 모듈의 analyze(program)(→ (오류 글자 목록, 이름 해석 표)), check, resolve 를 채웁니다.
채점기가 고정 프로그램과 까다로운 스코프(클로저가 본 이름, 가지마다 스코프, 반복문 안 섀도잉)의 이름 해석 표를 통째로 대조합니다.
채점기가 오류 프로그램(/opt/fixtures/mini/errors/check-*.mini 와 몇 편 더)의 오류 목록을 대조합니다.
채점기가 무작위 올바른 프로그램 120편(거짓 경보가 없어야)과 한 군데씩 망가뜨린 120편을 대조합니다.

참고

python3 /root/mini/mini.py check 파일.mini 가 여러분의 검사기로 오류를 찍습니다.
렉서·파서·노드는 실습을 시작할 때 깔려 있습니다(앞 모듈에서 만든 여러분의 것을 붙여 넣어도 됩니다).
흔한 실수: 블록을 나올 때 스코프를 버리지 않는 것(누수), 초기값을 먼저 검사해 let x = x; 가 바깥 x 를 가리키게 하는 것, 모르는 타입을 오류로 잡는 것(거짓 경보), 오류를 찾은 순서대로 돌려주는 것.
세션은 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 + true 는 오류가 하나, true + false 는 둘입니다. 결과 타입은 검사 결과와 상관없이 연산자가 정합니다.

조건과 오류 정리

condition 은 조건의 타입이 알려져 있는데 bool 이 아니면 키워드 위치로 오류를 내고, 가지(블록)를 stmt 로 검사합니다 — 블록이 스코프를 쌓아 줍니다. analyze 는 오류 목록을 (줄, 칸) 으로 정렬한 뒤 글자로 바꿉니다.

섀도잉과 스코프 누수

새 코드는 없습니다. 이름 해석 표가 어긋나면 어느 쓴 곳이 엉뚱한 선언에 이어졌는지 메시지가 알려 줍니다. 블록이 끝난 뒤의 이름이 안쪽 선언에 이어졌다면 pop 을 빠뜨린 것이고, if 가지의 선언이 서로 부딪힌다면 가지를 블록으로 검사하지 않은 것입니다.

오류 프로그램을 한 글자까지

새 코드는 없습니다. 메시지 글자·위치·순서가 모두 같아야 합니다. 인자 수 오류는 이름으로 직접 부를 때만(값으로 받은 함수는 모름), 대입 오류는 = 의 위치, 조건 오류는 키워드의 위치입니다.

거짓 경보와 놓친 오류를 함께 잰다

새 코드는 없습니다. 올바른 무작위 프로그램에서 오류를 낸다면 모르는 타입(매개변수·호출 결과)을 검사하고 있는 것이고, 망가뜨린 프로그램에서 오류가 모자라면 이름을 못 찾았을 때 멈추거나 같은 식의 두 번째 오류를 버리고 있는 것입니다.