URL: https://thunderseethe.dev/posts/nameres-base/

이름 해석을 마침내 끝내기

언어 만들기

이 글은 언어 만들기 시리즈의 일부다. Rust로 프로그래밍 언어를 구현하는 방법을 가르치는 시리즈다.

이 글은 이름 해석(name resolution)을 다룬다. 디슈가링은 타입 추론에 아직 바로 넣을 수 없는 Ast<String>을 남겼다. 이름 해석은 프로그램 안의 이름들이 무엇을 의미하는지 밝혀내어, 그것을 타입 체크(타입 추론)가 가능한 Ast<Var>로 바꿔 준다.

왜 우리는 이름을 붙일까? 어쩌면 바보 같은 질문일지도 모른다. 누가 내게 애완 돌에 이름을 붙이라고 말해 준 적은 없다. 그의 퇴적암 같은 겉모습을 한 번 보는 것만으로도 나는 그를 프랜시스(Francis)라고 부르기로 했다.

이름은 우리가 어떤 것과 동일시하고 식별하는 데 도움을 준다. 이는 컴퓨터에서도, 돌 친구에게도 똑같이 적용된다. 프로그래밍 언어에서 이름은 값을 식별하고 공유하게 해 준다. 1 + 2가 필요할 때마다 반복하는 대신, 그것을 three라고 이름 붙이고 그 이름으로 참조할 수 있다.

이름 붙이기는 동료 프로그래머들에게 프로그램을 더 읽기 쉽게 만들어 준다. 이름은 복잡함을 묶어 외부로 내보내고, 우리가 더 크고 더 나은 프로그램을 이해할 수 있게 해 준다. 또한 공유의 수단을 제공한다.

대부분의 언어에서 값에 이름을 붙인다는 것은 그 값에 메모리 상의 자리를 주는 것을 의미한다. three는 단지 매번 1 + 2라고 쓰는 일을 덜어 줄 뿐 아니라, 컴퓨터가 매번 1 + 2를 다시 계산하지 않게도 해 준다. 메모리의 위치에 이름을 붙이는 일은 사람이 추적하기엔 매우 유용하다. 하지만 컴퓨터에겐 덜 유용한 것으로 밝혀진다.

컴퓨터 친화적인 이름

컴퓨터는 어떤 값이 메모리의 어디에 사는지, 그리고 확장해서 두 값이 같은 위치에 살기 때문에 사실상 동일한 값인지에만 관심이 있다. 사람이 읽기 좋은 이름은 스코프(scope)와 섀도잉(shadowing) 때문에 이 목적에 그다지 좋지 않다. 이 두 기능은 사람이 이름을 관리하는 데는 도움이 되지만, 컴퓨터에게는 방해가 된다.

스코프는 프로그램의 특정 지점에서 이름을 그 값에 매핑한 지도(map)다. 다음 프로그램을 보자:

let one = 1;
let two = 2;
let three = add one two;
add three two

let two = 2; 지점에서의 스코프에는 one이 들어 있다. 하지만 add three two 지점에서의 스코프에는 one, two, three가 들어 있다.

스코프는 서로 위에 쌓인다. 함수를 도입하면 함수 본문은 새로운 스코프에 놓인다:

let y = 2;
let f = |x| add x y;
f 1

|x| add x y는 기존 스코프(그 안에는 y가 있음) 위에 쌓이는 새 스코프를 도입한다. f 정의를 마치면 |x| 스코프는 스택에서 빠져나가고 더 이상 x에 접근할 수 없다.

y가 |x| add x y 내부에서 접근 가능하다는 것을 볼 수 있다. 한 스코프 안에서 이름을 찾지 못하면, 스택을 위로 올라가 그 위의 스코프에서 찾는다. 이 동작이 두 번째 기능, 즉 섀도잉을 낳는다.

새로운 스코프를 도입하면 이전에 정의된 이름을 다시 정의할 수 있다. 앞의 예제가 다음과 같다고 상상해 보자:

let y = 2;
let f = |y| add y y;
f 1

함수의 스코프는 y라는 이름을 도입한다. 함수 본문 안에서는 더 이상 y = 2를 참조할 수 없다. 함수 매개변수 |y|가 그 이름을 섀도잉했기 때문이다.

디슈가링에서 배웠듯이, let 표현식은 내부적으로 함수다. 즉, 각 let 표현식은 기존 이름을 섀도잉할 수 있는 새 스코프를 도입한다. 다음과 같은 코드는 완전히 유효하다:

let x = 1;
let x = add x x;
let x = add x x;
x

즉시 소비되는 값들을 위해 x'나 x0 같은 이름을 억지로 만들지 않아도 된다는 점은 좋다. 독자 입장에서도 x = 1이 섀도잉된다는 것을 보면 도움이 된다. 그 표현식의 나머지 부분에서는 x = 1이 다시 참조되지 않는다는 걸 알 수 있으니, 머릿속에서 치워 버릴 수 있다.

다만 섀도잉은 논쟁적인 기능이기도 하다. 어떤 이름이 무엇을 참조하는지 파악하기가 더 어려워질 수 있고, 이름이 섀도잉되었다는 사실을 놓치기 쉽다. 섀도잉을 배제하는 많은 실사용 언어들이 있고, 그들도 성공적이다. 하지만 이는 다른 날의 설계 논의다. 우리 언어는 섀도잉을 지원할 것이고, 나는 그 편이 좋다.

이름 해석하기

이름으로 돌아가 보자. 스코핑은 어떤 이름이 무엇을 참조하는지 결정하는 일을 복잡하게 만든다. 이름을 보면, 그것이 어디에서 정의되었는지 찾기 위해 스코프 스택을 걸어 올라가며 검색해야 한다. 사람으로서는 괜찮다. 소스 코드를 읽으면 변수 정의 위치를 (바라건대) 찾을 수 있다.

하지만 컴퓨터 입장에서 이름을 볼 때마다 이런 여정을 떠나는 것은 효율적이지 않아 보인다. 이름 해석은 이 불일치를 해결하는 데 초점이 있다. 컴퓨터는 사실 값이 어떤 이름을 갖는지 신경 쓰지 않는다. 컴퓨터는 읽을 필요가 없기 때문이다.

이름 해석은 한 번의 패스로 스코핑과 섀도잉을 모두 계산한 뒤, 스코프나 섀도잉을 필요로 하지 않는 컴퓨터 친화적 형태를 만들어 낸다. 이미 타입 추론을 작성해 두었기 때문에, 사실 이 형태가 무엇인지 알고 있다. 각 이름은 고유한 변수로 치환될 것이고, 이 변수는 본질적으로 정수 카운터다:

struct Var(usize);

이름 해석 이후 섀도잉 예제는 다음과 같이 된다:

let v0 = 1;
let v1 = add v0 v0;
let v2 = add v1 v1;
v2

각 이름에 고유한 변수를 부여하고, 이 변수들은 x 같은 이름과 달리 메모리의 고유한 위치를 나타낸다. 더 이상 스코프 스택을 걱정할 필요가 없다. 프로그램의 모든 이름을 큰 HashMap<Var, T>에 넣어도 두 이름이 겹칠 걱정을 하지 않아도 된다. 실제로 이름 해석에서 바로 그렇게 할 것이다.

이름 해석 동안 수행하는 작업이 하나 더 있다. 모든 이름이 정의되어 있는지 확인하는 것이다. 다음과 같은 코드를 쓰는 것은 완전히 합법적일 수 있다(나는 변호사가 아니다. 지역 의회에 문의하라):

let f = |y| add x y;
g 1

하지만 컴파일러에게는 완전히 무의미하다. g는 정의가 없고, 함수일지도 확실치 않다. x도 let 바인딩이 한 번도 보이지 않는데 참조되고 있다. 이름을 해석하면서 이런 오류는 아주 명확하게 드러나며, 우리는 그것을 추적할 것이다. 오류가 진행을 멈추게 하진 않을 것이다. 우리는 회복력이 있다. 대신 정의되지 않은 이름은 Hole로 대체할 것이다.

패스 준비하기

코드를 보자. 거의 모든 패스에서 시작하는 곳과 똑같다: 상태를 공유할 구조체다.

struct NameResolution {
  supply: VarSupply,
  names: HashMap<Var, String>,
  errors: HashMap<NodeId, NameResolutionError>,
}

supply는 모든 변수를 공급한다:

#[derive(Default)]
struct VarSupply {
  next: usize,
}
impl VarSupply {
  fn supply(&mut self) -> Var {
    let id = self.next;
    self.next += 1;
    Var(id)
  }
}

카운터지만, 카운트를 Var로 감싸 준다. 아주 친절하다.

names는 고유 변수들을 그것이 원래 가리키던 이름으로 되돌려 매핑한다. 진단(diagnostics)에 사용한다. 사용자에게 var12 같은 것을 보여 주는 일은 가능하면 피하고 싶다.

errors는 이름 해석 중 발생하는 오류를 추적한다. 실제로 발생할 수 있는 오류는 하나뿐이다:

enum NameResolutionError {
  UndefinedVar(NodeId, String),
}

정의되지 않은 변수를 만나면 이 오류를 발생시킨다. AST 노드 하나당 최대 한 번만 이렇게 할 수 있으므로, 모두 맵에 보관한다. 다만 솔직히 말해, 이 일은 아마 Ast::Var 노드에서만 일어날 것 같다.

resolve 메서드

NameResolution에는 모든 해석 작업을 수행하는 resolve 메서드 하나가 있다.

impl NameResolution {
  fn resolve(
    &mut self, 
    ast: Ast<String>, 
    env: im::HashMap<String, Var>
  ) -> Ast<Var> {
    match ast {
      // Put some cases here...
    }
  }
}

resolve는 이름을 고유한 Var로 매핑하는 env를 받는다. env는 스코프를 추적한다. 이것이 영속(persistent) 맵이기 때문에 스코프 스택이 필요 없다. 맵에 값을 추가하면 새 맵이 만들어지고 기존 맵은 그대로 남는다. resolve를 재귀 호출할 때 갱신된 맵을 넘기면, 호출 스택을 스코프 스택처럼 재사용하는 셈이다.

env의 어떤 인스턴스도 항상 “현재 스코프에서 보이는 이름들”만 담는다. 만약 어떤 이름이 env에 있던 기존 엔트리를 덮어쓴다면, 그 이름은 현재 스코프에서 섀도잉된 것이며 덮어씌워진 엔트리는 어차피 접근할 수 없다. 그래서 섀도잉에 취약한 HashMap<String, Var>를 써도 괜찮다. 반면 names 멤버는 프로그램 전체의 이름을 저장하므로 HashMap<Var, String>을 사용한다. 맵에서 이름이 겹쳐 덮어써지는 일을 피하려면 키로 Var를 써야 한다.

그 다음 resolve는 ast를 매칭한다. 케이스별로 처리하되, 함수부터 시작하자:

Ast::Fun(id, name, body) => {
  let var = self.supply.supply();
  self.names.insert(var, name.clone());
  let body = self.resolve(*body, env.update(name, var));
  Ast::fun(id, var, body)
}

let 표현식을 적용된 함수로 디슈가링했기 때문에, 이름을 도입할 수 있는 케이스는 이것 하나뿐이다. 함수 매개변수에 대한 Var를 하나 만들고, 그 Var를 원래 이름으로 되돌려 매핑해 둔다. 그리고 env를 갱신하여 이름이 해당 Var를 가리키도록 만든 뒤, body 안에서 이름을 해석한다. 마지막으로 이름 해석이 완료된 함수를 재구성한다.

Var 케이스는 Fun이 도입한 변수를 즉시 활용한다:

Ast::Var(id, name) => match env.get(&name).copied() {
  Some(v) => Ast::Var(id, v),
  None => {
    self
      .errors
      .insert(id, NameResolutionError::UndefinedVar(id, name));
    let var = self.supply.supply();
    Ast::Hole(id, var)
  }
}

이름에 대한 Var를 찾으면 성공적으로 해석하고 넘어간다. Var를 찾지 못하면 오류다. 하지만 오류에서 멈추지는 않는다. 오류를 기록하고 해당 변수를 홀(hole)로 취급한다.

또, 놀랍게도 Hole 케이스에서도 홀을 만든다:

Ast::Hole(id, name) => {
  let var = self.supply.supply();
  self.names.insert(var, name.clone());
  Ast::Hole(id, var)
}

홀에도 이름을 붙이므로, 홀에도 Var를 할당하고 그 Var를 이름으로 되돌려 매핑한다. 이는 프로그램 실행에는 중요하지 않다. 홀을 실행 가능한 코드로 컴파일할 일은 없기 때문이다. 하지만 에러 리포팅과 진단에는 도움이 된다.

App에는 이름이 없지만, 자식 노드들 안의 이름은 해석해야 한다:

Ast::App(id, fun, arg) => {
  let fun = self.resolve(*fun, env.clone());
  let arg = self.resolve(*arg, env);
  Ast::app(id, fun, arg)
}

Int에는 이름도 없고 자식도 없으므로 할 일이 없다:

Ast::Int(id, i) => Ast::Int(id, i)

Int는 절대 바뀌지 마라. 너는 내 바위다.

resolve는 NameResolution의 유일한(그리고 메인) 메서드다. 끝이다. 그런데 왜 메서드 하나를 위해 상태 공유용 구조체를 굳이 만들었을까? 모든 호출 지점에 resolve(supply, names, errors, ast, env)를 쓰고 싶지 않았으니까, 고소해라. 좀 더 이념적으로 말하자면 일관성이 중요하다. 우리는 이 패턴을 확립해 왔고, 메서드가 하나뿐일 때도 그 패턴을 유지하는 게 도움이 된다.

모든 것은 최상위 name_resolution 함수에서 조립된다:

fn name_resolution(
  ast: Ast<String>
) -> NameResolutionOut {
  let mut nameres = NameResolution::default();
  let ast = nameres.resolve(ast, im::HashMap::default());
  NameResolutionOut {
    ast,
    errors: nameres.errors,
    names: nameres.names,
  }
}

names는 Var에서 사람 친화적인 이름으로의 매핑을 추적한다는 점을 기억하자. 이는 전체 컴파일러에서 필요하므로, 패스의 출력에 포함한다.

예시

이름 해석이 실제로 어떻게 동작하는지 보자. 많은 이름을 재사용하는 프로그램부터 시작하자:

let x = |x| x;
let y = |y| x y;
let x = 3;
y x

대수학 수업으로 나를 다시 내던지기에 충분한 X와 Y다. 이름은 x와 y 두 개뿐이지만, 스코핑과 섀도잉 때문에 이 이름들은 표현식 전체에서 서로 다른 값들을 참조한다.

첫 바인딩 let x = |x| x;는 이미 두 기능을 모두 보여 준다. let x는 x가 |x| x로 정의된 새 스코프를 도입한다. 그리고 let x는 곧바로 함수 매개변수 x에 의해 섀도잉된다. 함수 본문은 let 바인딩 x가 아니라 함수 매개변수 x를 반환한다.

다음 바인딩 let y = |y| x y;에서는 |x| x 스코프를 벗어났다. 이제 x는 let 바인딩을 참조하며, 이는 우리가 그것을 함수로 사용하고 있으니 좋은 일이다. 또한 매개변수 y가 let으로 바인딩된 y를 섀도잉하는 유사한 상황을 볼 수 있다.

그 다음 let x = 3;으로 다시 한 번 x를 섀도잉한다. 이 섀도잉은 let x = |x| x;와 같은 스코프에서 일어나므로, 이전 바인딩은 더 이상 사용할 수 없다.

마지막 y x는 각 이름에 대한 최신 바인딩을 사용하며, 런타임에서는 (|y| (|x| x) y) 3과 동일해진다. 이름 해석 후에는 이 모든 것을 계산해 두고, 각 이름에 대해 고유한 Var만 남긴다:

let v0 = |v1| v1;
let v2 = |v3| v0 v3;
let v4 = 3;
v2 v4

이름 해석은 마지막 쐐기돌(keystone)이었다. 우리는 아치를 완성했다! 꽤 긴 여정이었지만 이제 컴파일러의 모든 패스를 갖추었다. 언제나 그렇듯, 레포에서 전체 코드를 확인할 수 있다. 이름 해석이 만들어 낸 Ast<Var>를 타입 추론에 넣어 완전한 파이프라인을 만들 수 있다. 실제로 다음 글에서 바로 그것을 할 것이다.