타입 체커를 탈출하기: 구현

언어 만들기

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

이 글은 이전 로워링 글을 바탕으로 한다. 지난번에 로워링에 대한 이론을 조금 더 쌓았으니, 이번에는 구현을 해 보자.

지난 글에서의 IR과 Type에 대한 지식을 무기로, 마침내 코드를 쓸 수 있다:

rust
fn lower(
  ast: Ast<TypedVar>, 
  scheme: ast::TypeScheme
) -> (IR, Type) {
  let (ir_ty, types) = lower_ty_scheme(scheme);

  todo!()
}

한 줄 끝냈다. 대단한 진전이다(특히 지난 글과 비교하면)!

Base AST 복습

베이스 타입 체커를 다룬 지 좀 됐다. 안에 뭐가 있었는지 잘 기억이 안 나니, 다시 감을 잡기 위해 훑어 보자.

베이스 AST는 다음과 같다:

rust
enum Ast<V> {
  /// 로컬 변수
  Var(NodeId, V),
  /// 정수 리터럴
  Int(NodeId, i32),
  /// 함수 리터럴
  /// (람다, 클로저 등)
  Fun(NodeId, V, Box<Self>),
  /// 함수 적용
  App(NodeId, Box<Self>, Box<Self>), 
}

NodeId는 Ast의 각 노드를 유일하게 식별한다:

rust
struct NodeId(u32);

제네릭 V는 변수의 타입이다. 시작할 때는 Var로 출발한다:

rust
struct Var(usize);

타입 체크가 끝날 즈음에는 TypedVar로 승급된다:

rust
struct TypedVar(Var, Type);

자연스럽게 다음 질문은 “Type이 뭐지?”가 된다:

rust
struct TypeVar(u32);
enum Type {
  // 타입 변수
  Var(TypeVar),
  // 정수 타입
  Int,
  // 함수 타입
  Fun(Box<Self>, Box<Self>),
}

lower는 Ast<TypedVar>와 함께, 타입 체크가 만들어낸 TypeScheme도 받는다. TypeScheme는 타입이 지정된 AST 안에 등장하는 아직 해결되지 않은 타입 변수들을 모두 바인딩한다:

rust
struct TypeScheme {
  unbound: BTreeSet<TypeVar>,
  ty: Type,
}

이제 타입 체커에서 어떤 것이 넘어오는지 전부 알았으니, 로워링으로 돌아가자.

타입 스킴 로워링

로워링의 첫 단계는 TypeScheme를 로워링하는 것이다. TypeScheme부터 시작하는 이유는, 이것이 타입을 어떻게 로워링할지에 대한 정보를 주기 때문이다. 타입은 TypeScheme 자체에도 나타나고 Ast에도 나타난다. 즉, 타입을 어떻게 로워링할지 알기 전까지는 Ast도 로워링할 수 없다. lower_ty_scheme의 시그니처는 다음과 같다:

rust
fn lower_ty_scheme(
  scheme: ast::TypeScheme
) -> (Type, LowerTypes) {
  todo!()
}

lower_ty_scheme는 먼저 바인딩된 타입 변수를 처리하는 것으로 시작한다. 타입 스킴은 AST 타입에 등장하는 모든 일반화된 타입 변수를 추적한다는 점을 떠올려 보자. 타입 스킴은 이런 타입 변수가 도입될 수 있는 유일한 장소다. 이 AST의 각 TypeVar는 TyFun 노드에 의해 바인딩되는 IR TypeVar가 된다. 즉 AST TypeVar를 드브뤼앙 인덱스(DeBruijn indices)로 변환해야 한다.

다행히도 이는 간단하다. 타입 스킴에는 우리가 볼 모든 타입 변수가 담겨 있고, 또한 우리가 그들을 보게 될 순서대로 들어 있다. 한 번만 드브뤼앙 인덱스로 변환해 두면, Ast 안에서 로워링해야 하는 모든 타입에 대해 제대로 동작할 것을 알 수 있다:

rust
let ty_env = scheme
  .unbound
  .into_iter()
  .rev()
  .enumerate()
  .map(|(i, tyvar)| (tyvar, TypeVar(i)))
  .collect();

scheme.unbound의 각 타입 변수에 대해 인덱스를 가져와 그것을 드브뤼앙 인덱스로 사용한다. 중요한 점은 역순으로 한다는 것이다. 결과는 ty_env, 즉 HashMap<ast::TypeVar, TypeVar>다. 예를 들어 다음 타입 스킴이 있다고 하자:

rust
let a = TypeVar(4);
let b = TypeVar(23);
let c = TypeVar(149);
let foo = TypeScheme {
  unbound: btree_set![a, b, c],
  ty: Type::fun(Type::Var(a), Type::fun(Type::Var(b), Type::Var(c)))
};

타입 환경은 이렇게 된다:

rust
// 지어낸 `hash_map!` 매크로는 양해 바란다.
let ty_env = hash_map![
  a: TypeVar(2),
  b: TypeVar(1),
  c: TypeVar(0)
];

드브뤼앙 인덱스는 몇 개의 TyFun을 건너뛰는지를 세기 때문에, a는 TypeVar(0)이 아니라 TypeVar(2)를 받는다는 것을 기억하자. 이것이 ty_env를 만들 때 scheme.unbound를 뒤집는 이유다. 다시 lower_ty_scheme로 돌아오면, ty_env를 사용해 TypeScheme의 type 필드를 로워링한다.

rust
let lower = LowerTypes { env: ty_env };
let lower_ty = lower.lower_ty(scheme.ty);

LowerTypes는 타입을 재귀적으로 순회하는 동안 타입 환경을 들고 있기 위한 헬퍼 구조체다:

rust
struct LowerTypes {
  env: HashMap<ast::TypeVar, TypeVar>,
}

여기에는 lower_ty라는 메서드 하나가 정의되는데, 너무 짧아서 나눌 필요도 없다:

rust
impl LowerTypes {
  fn lower_ty(&self, ty: ast::Type) -> Type {
    match ty {
      ast::Type::Int => Type::Int,
      ast::Type::Var(v) => Type::Var(self.env[&v]),
      ast::Type::Fun(arg, ret) => {
        let arg = self.lower_ty(*arg);
        let ret = self.lower_ty(*ret);
        Type::fun(arg, ret)
      }
    }
  }
}

self.env[&v]는 env에 없는 v를 만나면 패닉이 날 수 있다. 패닉이 나도 괜찮지만, 더 우아하게 하려면 get을 쓰고 expect로 좋은 에러 메시지를 줄 수도 있다. 만약 실제로 패닉이 난다면, 그것은 scheme.unbound에 나열되지 않은 변수를 포함한 타입이 있다는 뜻이므로 컴파일러 버그다.

lower_ty는 결코 Type::TyFun을 만들지 않는다는 점도 주목하자. ast::Type은 타입 변수를 도입할 수 없으므로 TyFun으로 타입 변수를 바인딩할 필요가 없다. 우리가 아는 것처럼, 타입 변수는 오직 TypeScheme에서만 도입된다.

이제 lower_ty_scheme에서 마지막으로 남은 일은 타입 변수들에 대한 TyFun을 도입하는 것이다.

rust
let bound_lower_ty = 
  (0..lower.env.len())
    .fold(lower_ty, |ty, _| Type::ty_fun(Kind::Type, ty));

타입 스킴이 바인딩하는 타입 변수마다 lower_ty를 TyFun으로 감싼다. AST에서는 ast::TypeScheme와 ast::Type을 구분하지만, 로워링에서는 그 구분이 사라진다. ast::TypeScheme와 ast::Type 모두 IR의 Type로 변한다. 예를 들어 위의 foo 타입 스킴을 로워링하면 다음 IR 타입이 만들어진다:

text
TyFun(Kind::Type, 
TyFun(Kind::Type, 
TyFun(Kind::Type, 
  Fun(
    Var(TypeVar(2), 
    Fun(TypeVar(1), TypeVar(0)))))))

foo.unbound에 있는 각 변수마다 TyFun이 하나씩 생기고, TypeVar는 드브뤼앙 인덱스로 변환되었다. 전부 합치면 lower_ty_scheme는 다음과 같다:

rust
fn lower_ty_scheme(scheme: ast::TypeScheme) -> (Type, LowerTypes) {
  let ty_env = scheme
    .unbound
    .into_iter()
    .rev()
    .enumerate()
    .map(|(i, tyvar)| (tyvar, TypeVar(i)))
    .collect();

  let lower = LowerTypes { env: ty_env };
  let lower_ty = lower.lower_ty(scheme.ty);
  let bound_lower_ty = (0..lower.env.len()).fold(lower_ty, |ty, _| {
    Type::ty_fun(Kind::Type, ty)
  });
  (bound_lower_ty, lower)
}

이제 lower에 또 한 줄을 추가할 시간이다:

rust
fn lower(ast: Ast<TypedVar>, scheme: ast::TypeScheme) -> (IR, Type) {
  let (ir_ty, types) = lower_ty_scheme(scheme);

  // New!
  let mut lower_ast = LowerAst {
    supply: VarSupply::default(),
    types,
  };
  let ir = lower_ast.lower_ast(ast);
  todo!()
}

이번에는 몇 줄이나 추가했다. 오, 이런!

Ast 로워링

LowerAst는 LowerTypes와 목적이 비슷하다:

rust
struct LowerAst {
  supply: VarSupply,
  types: LowerTypes,
}

이 구조체는 우리가 작성할 재귀적 AST 함수들을 위한 상태를 보관한다. VarSupply는 AST 변수를 IR 변수로 매핑하고, 새로운 IR 변수를 생성하기 위해 존재한다. 내부 구현은 흥미로운 편은 아니지만 전체 코드에서 볼 수 있다. 여기서는 메서드 하나를 지원한다고만 해 두자:

rust
impl VarSupply {
  fn supply_for(&mut self, var: ast::Var) -> VarId {
    // 지루한 내용...
  }
}

supply_for는 내부적으로 캐시한다. 동일한 ast::Var를 넣으면 동일한 VarId를 받는다. 계속하자. LowerAst는 lower_ast라는 메서드 하나를 제공한다:

rust
impl LowerAst {
  fn lower_ast(&mut self, ast: Ast<TypedVar>) -> IR {
    match ast {
      //...
    }
  }
}

이 패턴은 이제 익숙하다. ast를 매치해서 각 경우에 대해 IR 텀을 만든다. 먼저 변수부터 보자:

rust
Ast::Var(_, TypedVar(var, ty)) => IR::Var(Var::new(
  self.supply.supply_for(var),
  self.types.lower_ty(ty),
)),

TypedVar는 IR의 Var로 바뀐다. 앞에서 타입 변환 코드를 작성해 둔 덕분에 변환은 아주 쉽다. ast::Var는 VarSupply를 통해 Var로 변환하고, ast::Type은 LowerTypes로 로워링한다. self.types는 lower_ty_scheme에서와 동일한 ty_env를 사용하므로, 타입을 동등하게 로워링한다고 확신할 수 있다.

rust
Ast::Int(_, i) => IR::Int(i),

또다시 Int는 일관된 무료 보너스다. Fun도 크게 더 복잡하지 않다:

rust
Ast::Fun(_, TypedVar(var, ty), body) => {
  let ir_ty = self.types.lower_ty(ty);
  let ir_var = self.supply.supply_for(var);
  let ir_body = self.lower_ast(*body);
  IR::fun(Var::new(ir_var, ir_ty), ir_body)
}

코드는 좀 늘었지만 놀랄 것은 없다. Fun 노드를 분해한 뒤, 각 부분을 로워링하고, IR Fun으로 다시 결합한다. 마지막은 App이다:

rust
Ast::App(_, fun, arg) => {
  let ir_fun = self.lower_ast(*fun);
  let ir_arg = self.lower_ast(*arg);
  IR::app(ir_fun, ir_arg)
}

여기도 직관적이다. 각 부분을 로워링해서 IR App으로 재조립한다.

거의 아무것도 안 한 것처럼 느껴질 수도 있다. 각 케이스는 AST 노드를 같은 이름의 IR 노드로 바꾸기만 한다. 이는 AST가 람다 계산이고 IR이 System F라는 사실에 뿌리를 두고 있다. 람다 계산을(람다 계산의 상위집합인) System F로 번역하는 것은 큰 일이 필요 없다.

로워링의 완결성

lower_ast를 완성했으니 lower로 돌아가자. 남은 작업이 하나 있다. 로워링된 타입을 TyFun 노드로 감쌌던 것처럼, 로워링된 Ast도 TyFun 노드로 감싸야 한다:

rust
fn lower(ast: Ast<TypedVar>, scheme: ast::TypeScheme) -> (IR, Type) {
  let (ir_ty, types) = lower_ty_scheme(scheme);
  let mut lower_ast = LowerAst {
    supply: VarSupply::default(),
    types,
  };
  let ir = lower_ast.lower_ast(ast);

  // New!
  let bound_ir = 
    (0..lower_ast.types.env.len())
      .fold(ir, |ir, _| IR::ty_fun(Kind::Type, ir));
  (bound_ir, ir_ty)
}

로워링에서 가장 중요한 부분은 이 무심한 코드 조각 안에 들어 있다. AST의 텀은 타입에 대한 개념이 없다. 타입은 오로지 타입 스킴과 타입 안에만 나타난다. 반면 IR에서는, 텀 수준에서 타입을 바인딩하는 텀이 존재한다.

텀 안에서 타입을 표현하는 것의 영향은 매우 크다. 어떤 최적화가 텀에서 ty_fun들을 제거한다면, 우리는 다형성을 제거하고 있다는 것을 안다. ty_fun이 없는 텀을 보면, 그 텀은 제네릭일 수 없다는 것도 안다. 다형성이 어디에 존재하는지 판단하는 것은 단형화(monomorphization)와 머신 코드 방출에 핵심적이다. 이 둘은 간단한 컴파일러를 완성하기 전 방문하게 될 패스들이다.

이제 lower 함수는 암묵적으로 타입이 매겨진 AST를 명시적으로 타입이 매겨진 IR로 번역한다. 여기서는 로워링이 의식적인 절차처럼 보일 수도 있지만, 더 화려한 타입 체커들에서 기능을 더해 갈수록 점점 흥미로워질 것이다. 화려한 기능이 없더라도, 우리는 컴파일러 완성을 향해 또 한 걸음 나아갔다. 여기서 여정은 갈라진다. row 로워링으로 갈 수도 있고, 단순화(simplification)로 넘어갈 수도 있다.