타입이 붙은 AST를 기반 언어의 중간 표현(IR)로 변환(로어링)하고, System F 기반 IR과 타입 표현, 그리고 IR의 type_of()를 통해 타입을 재구성하는 방법을 다룬다.
URL: https://thunderseethe.dev/posts/lowering-base-ir/
이 글은 언어 만들기 시리즈의 일부입니다. Rust를 사용해 프로그래밍 언어를 구현하는 방법을 알려주는 시리즈죠.
이 글에서는 타입이 붙은 AST를 기반 언어의 중간 표현(intermediate representation, IR)으로 바꾸는 과정을 다룹니다. 이는 이전 패스에서 기반 언어에 대해 타입을 추론했던 결과물을 토대로 합니다.
우리는 타입 체크에 너무 오래 머물러 있었습니다. 이제는 파서를 고르다 빠지는 늪과 맞먹는 타르 핏(tar pit) 수준이 되어버렸죠. 이 늪에서 빠져나갈 유일한 희망은 더 깊이 파고드는 것입니다. 그렇지 않으면 끝없이 매력적으로 붙일 수 있는 타입 체커 기능들을 두고 계속 고민만 하게 될 테니까요. 언제든 더 나이 들고 현명해진 뒤에 타입 체커로 돌아올 자유는 있습니다. 하지만 이 시리즈 이름은 “언어 만들기”이지 “동기가 증발할 때까지 타입 체크하기”가 아니잖아요.
다행히도, 더 깊이 파고드는 건 바로 다음 컴파일러 패스의 주제입니다. 바로 **로어링(lowering)**입니다. 로어링은 타입이 붙은 AST를 중간 표현(IR)으로 변환하는 과정입니다. 이는 컴파일러가 프론트엔드에서 백엔드로 넘어가는 근본적인 전환점이기도 합니다.
컴파일러 프론트엔드에서 쓰는 AST는 사용자가 코드를 작성하기 쉽도록 많은 양보를 합니다. 사용자는 타입 같은 뻔한 메타데이터를 일일이 쓰고 싶어하지 않죠. AST도 그걸 압니다. 사용자가 생략한 타입은 AST가 대신 추론해 줍니다. AST에서 에러가 보인다면, 대개는 사용자가 코드를 잘못 쓴 탓일 가능성이 큽니다. 우리는 친절한 진단 메시지로 그 사실을 알려줘야 합니다.
하지만 IR로 넘어가면 그런 배려는 사라집니다. 이제는 사용자보다 컴파일러에 유용한 표현이 더 중요해집니다. IR은 프론트엔드와 머신 코드 생성 사이(그래서 ‘중간’이라는 이름이죠)에 놓여 있습니다. 머신 코드로 번역되기 전에 최적화를 수행할 수 있도록 존재합니다. 그래서 IR은 사용자가 작성하기엔 고역일 메타데이터—예컨대 메모리 레이아웃이나 호출 규약—를 명시적으로 드러냅니다(reify).
이 전환과 함께 오류에 대한 태도도 바뀝니다. 로어링 단계에서는 AST가 이미 타입 체크를 성공적으로 통과했다는 걸 알고 있습니다. 따라서 예상치 못한 무언가를 만나면, 그건 이제 사용자 오류가 아니라 컴파일러 내부 오류(ICE) 때문이라는 보장을 갖습니다. 그러니 더 이상 Result 같은 복구 가능한 오류 처리가 필요 없습니다. 오류를 만나면 즉시 panic!할 겁니다(그리고 어쩌면 울지도요).
패닉은 컴파일러에 우리가 고쳐야 할 버그가 있음을 뜻합니다. 실전에서는 컴파일러가 실제로 패닉하면 안 되겠죠. 우리가 컴파일러에 버그를 넣을 리도 없고요. 탄탄한 컴파일러라면 더 우아하게 오류 처리를 합니다. 하지만 여기서는 구현이 단순하다는 이유로 패닉이면 충분합니다.
이제 올바른 마인드셋을 장착했으니, 로어링 구현으로 들어가 봅시다. 이 패스는 lower 함수로 캡슐화됩니다:
fn lower(
ast: Ast<TypedVar>,
scheme: ast::TypeScheme
) -> (IR, Type) {
todo!()
}
lower는 타입 체커의 출력인 Ast<TypedVar>와 TypeScheme를 받아, 각각 IR과 Type으로 변환합니다.
IR은 우리 중간 표현을 나타내는 새로운 트리 자료형입니다:
enum IR {
Var(Var),
Int(i32),
Fun(Var, Box<Self>),
App(Box<Self>, Box<Self>),
TyFun(Kind, Box<Self>),
TyApp(Box<Self>, Type),
Local(Var, Box<Self>, Box<Self>),
}
IR은 Ast와 거의 똑같아 보입니다. 이는 우리의 IR이 System F를 기반으로 하기 때문입니다. System F는 람다 대수 같은 또 다른 계산 체계(calculus)로, 흔히 **다형 람다 대수(polymorphic lambda calculus)**라고도 불립니다. 이름 그대로 람다 대수에 두 개의 새 노드—타입 함수와 타입 적용—를 더한 것이죠.
AST가 람다 대수라면, System F 기반 IR이 Ast와 비슷하게 생기고 몇 개 노드만 추가되는 건 자연스럽습니다. “다형 람다 대수”라는 이름이 암시하듯, 새 노드 둘은 다형성과 관련됩니다:
TyFun - 타입 함수(type function). 항(term) 안에서 타입 변수를 바인딩하는 함수.TyApp - 타입 적용(type application). 타입 함수를 어떤 타입에 적용해 항(term)을 만들어 냄.이 노드들은 Fun과 App을 그대로 닮았습니다. 값 함수는 항(term)을 받아 항(term)을 만들지만, 타입 함수는 타입을 받아 항(term)을 만듭니다. TyFun과 TyApp은 IR에서 제네릭(generics)을 구현하기 위해 함께 동작합니다. TypeScheme에 있는 각 타입 변수는 IR에서 TyFun 노드로 바인딩됩니다.
우리 타입 변수는 Fun의 Var 같은 일반적인 이름 대신 DeBruijn 인덱스를 사용합니다. DeBruijn 인덱스를 쓰면 두 타입이 같은지 효율적으로 검사할 수 있습니다. DeBruijn 인덱스가 뭔지 몰라도 괜찮습니다. Type을 다룰 때 더 이야기할 거예요.
제네릭을 인스턴스화하고 싶을 땐 TyApp으로 어떤 타입을 TyFun에 적용합니다. 타입을 적용하면 TyFun 노드가 사라지고 내부의 항(term)이 남는데, 이때 바인딩된 타입 변수가 등장하는 모든 위치는 적용한 타입으로 치환됩니다. 값에 대한 App이 Fun에 대해 똑같이 동작하는 것과 동일합니다.
제네릭을 IR의 노드로 표현하면 다형성이 발생하는 위치를 매우 쉽게 확인할 수 있습니다. 그리고 다형성이 발생하지 않는 위치도 쉽게 확인할 수 있는데, 이는 어떤 최적화가 적용 가능한지 판단할 때 대단히 중요합니다. System F에 대해선 이론적으로 많은 연구가 있습니다. 여기서는 다루지 않지만 관심이 있다면 다음을 참고하세요:
우리가 System F를 쓰는 동기는 다형성 처리 방식에 있습니다. 이론적 토대는 덤 정도로 생각하면 됩니다.
마지막 새 노드 Local은 더 관료적(bureaucratic)입니다. 오늘은 Local 사용처를 여기서 보진 않을 거예요. 하지만 이후 패스에서 필요하므로, 미래 대비(future proofing) 차원에서 지금 추가합니다. Local은 어떤 값을 로컬 변수에 바인딩해, 이후 표현식에서 참조할 수 있게 합니다. Rust의 let 같은 것입니다.
Local을 함수 노드로 표현할 수도 있습니다. 즉, 명시적 로컬 대신 함수와 적용을 쓰는 거죠. IR::Local(x, <defn>, <body>) 같은 로컬은 다음처럼 표현될 수 있습니다:
IR::app(IR::fun(x, <body>), <defn>)두 표현은 동작이 동일합니다.
그런데도 우리가 그렇게 하지 않는 이유는 최적화 때문입니다. 두 항은 동작은 같지만 컴파일은 다르게 합니다. Fun 노드는 람다(또는 클로저)를 뜻합니다. 변수들을 캡처해서 어딘가(신만이 아는 곳)로 반환될 수 있죠. 그 가능성을 처리해야 합니다.
하지만 소박한 Local은 그렇지 않습니다. 현재 정의(definition) 안에서의 _로컬_이기 때문에 무엇도 캡처할 걱정이 없습니다. 트리에서 이 둘을 서로 다른 노드로 유지하면, 컴파일할 때 서로 다른 사용 사례를 쉽게 구분할 수 있습니다.
IR에서 또 다른 차이는 변수입니다. Var는 AST의 TypedVar와 유사합니다:
struct Var {
id: VarId,
ty: Type,
}
이제 우리는 미타입 변수를 갖지 않으니 구분할 필요가 없습니다. VarId는 익숙한 정수 카운터입니다:
struct VarId(u32);
이는 통상의 유일성 보장들을 모두 갖습니다. 어떤 항(term) 안의 모든 VarId는 유일합니다.
우리 IR은 타입이 붙어 있다는 점이 눈에 띕니다. 로어링이 목표로 하는 많은 IR은 무타입(untyped)입니다. 어차피 모든 타입이 맞는지 이미 체크했는데, 타입을 굳이 유지할 필요가 있을까요?
이 선택의 일부는 System F 사용에서 비롯됩니다. 타입이 없다면 TyFun과 TyApp이 할 일이 별로 없죠. 또 다른 이유는 저(그리고 바라건대 여러분)의 정신 건강입니다.
앞으로 우리는 여러 컴파일러 패스에서 IR을 많이 변형할 것입니다. 타입은 우리가 IR을 난도질한 뒤에도 그 의미가 우리가 생각하는 것과 같은지 sanity check를 하게 해줍니다. 로어링 테스트를 작성하면서, IR을 타입 체크해보는 것만으로도 제가 넣은 버그들이 꽤 잡혔습니다.
다행히 IR의 타입 체크에 많은 시간을 쓰진 않아도 됩니다. 유니피케이션(unification)을 통해 타입을 알아내는 어려운 일은 이미 끝냈으니까요. IR은 유니피케이션이 만들어낸 모든 작업 결과를 저장하므로, 어떤 추론도 하지 않고 타입을 재구성할 수 있습니다.
IR의 Type을 보고, type_of로 IR 항(term)의 타입을 빠르게 구성하는 방법을 알아봅시다:
enum Type {
Int,
Var(TypeVar),
Fun(Box<Self>, Box<Self>),
TyFun(Kind, Box<Self>),
}
Type은 AST의 타입과 거의 같고, 새 친구 TyFun만 추가됐습니다. TyFun은 IR::TyFun의 타입입니다. IR::Fun의 타입이 Fun인 것과 마찬가지죠. 다만 TyFun은 타입이 아니라 Kind를 받습니다. Kind는 TyFun에 올바른 _종류(kind)_의 타입을 넘기고 있는지 보장합니다. 값에 대해 올바른 _타입_이 Fun에 전달되는지 타입이 보장하는 것과 같은 역할이죠. 우리 Kind 사용은 꽤 심심합니다:
enum Kind {
Type,
}
모든 Type은 kind Type입니다. 나중엔 더 흥미로워질 겁니다. Row kind를 도입할 거예요. 지금은 kind를 망칠 일은 없다고 생각해도 됩니다.
이제 Type이 어떻게 생겼는지 알았으니, IR에 대해 타입을 구성할 수 있습니다:
impl IR {
fn type_of(&self) -> Type {
match self {
// ...
}
}
}
첫 두 경우는 단순합니다:
IR::Var(v) => v.ty.clone(),
IR::Int(_) => Type::Int,
정수는 Int 타입을 갖습니다. IR의 Var는 유니피케이션 덕분에 항상 자신의 타입을 갖고 있으니 그대로 반환하면 됩니다. 다음은 함수입니다:
IR::Fun(arg, body) => Type::fun(arg.ty.clone(), body.type_of()),
IR::TyFun(kind, body) => Type::ty_fun(*kind, body.type_of()),
두 함수 노드는 비슷하게 타입을 가집니다. body의 type_of와 인자(또는 kind)를 사용해 각각의 함수 타입을 구성합니다. App은 타입을 얻기 위해 처음으로 조금 일을 해야 하는 경우입니다:
IR::App(fun, arg) => {
let Type::Fun(fun_arg_ty, ret_ty) = fun.type_of() else {
panic!("ICE: IR used non-function type as a function")
};
if arg.type_of() != *fun_arg_ty {
panic!("ICE: Function applied to wrong argument type");
}
*ret_ty
}
코드가 타입 체크를 통과했다는 걸 아니까 fun이 함수 타입이라고 가정할 수 있고, 아니라면 패닉합니다. 또한 함수의 fun_arg_ty가 arg의 type_of와 같다고 가정할 수 있으며, 다르면 패닉합니다. 그 모든 검사가 통과되면 App의 타입은 함수의 반환 타입입니다.
여기서 arg.type_of() != *fun_arg_ty를 조금 더 깊게 생각해볼 가치가 있습니다. 왜 이것이 눈에 띄는지 설명하기 전에 배경을 깔아봅시다.
우리의 TyFun은 Kind만 받고 TypeVar를 받지 않습니다. 타입 함수는 타입 변수를 바인딩하기 위해 존재하는데, 바인딩하는 타입 변수를 들고 있지 않다는 건 이상해 보입니다. IR::Fun은 바인딩하는 Var를 들고 있는데, 왜 Type::TyFun은 다를까요? 덜 섬세하게 설계된 IR이라면 TyFun(TypeVar, Box<Self>) 같은 타입 함수 노드를 썼을지도 모릅니다.
그런 설계는 타입 동등성에 문제를 일으킵니다. 이를 보기 위해, 이런 대체 TyFun을 쓰는 두 타입 foo와 bar를 생각해봅시다:
let a = TypeVar(1493);
let foo = TyFun(a, Fun(Var(a), Var(a)));
let b = TypeVar(762);
let bar = TyFun(b, Fun(Var(b), Var(b)));
a와 b가 다르므로 foo와 bar는 같지 않습니다. 하지만 사실 같아야 합니다. 타입 변수가 문법적으로는 다르지만, 목적상으로는 동일하거든요. 우리는 이런 사소한 이름 차이는 무시하고 싶습니다. 이름은 타입 함수를 적용할 때 어디에 치환(substitute)할지 추적하기 위해 존재할 뿐이니까요.
foo와 bar에서 a와 b는 같은 방식으로 치환되므로 foo와 bar는 같아야 합니다. 어떤 타입이든 foo와 bar에 TyApp할 수 있고, 항상 동일한 타입이 나오죠. foo는 bar와 같지 않을 수 있어도, TyApp(foo, Int)는 TyApp(bar, Int)와 같습니다. 이 정도면 우리는 두 타입이 같다고 봐도 충분합니다. 이런 방식으로 동등성을 보는 것을 알파 동치(alpha equivalence)라고 합니다.
이 이름 차이를 무시하는 건 실제로는 까다롭습니다. 두 타입을 같게 만드는 이름 치환을 찾을 수 있다면, 둘은 알파 동치입니다. a를 b로 푸는(substitute) 치환을 찾아 foo에서 모든 a를 b로 바꾸면 되겠죠. 반대로 b를 a로 풀어 bar를 업데이트할 수도 있습니다.
듣기만 해도 익숙하지 않나요? 어디서 또 타입 변수를 같게 만들기 위해 치환을 찾죠? 바로 유니피케이션입니다! 이건 유니피케이션을 다른 이름으로 부르는 것에 불과합니다. 우리는 그걸 타입 체커에 두고 나오기로 했잖아요. 물론 이 접근도 가능은 하지만 비용이 크고 실수하기 쉽습니다. type_of 검사에서는 더 빠른 방법이 필요합니다.
다시 돌아오면, 우리의 실제 TyFun이 Kind만 들고 있는 이유는 타입 변수를 DeBruijn 인덱스로 표현하기 때문입니다. DeBruijn 인덱스는 가독성을 희생하는 대신 알파 동치를 효율적으로 검사하도록 특별히 설계되었습니다. DeBruijn 인덱스가 낯설다면, 제가 여기에서 작동 방식을 설명해 두었습니다. 이 글에서는 “우리가 DeBruijn 인덱스를 쓰고 있고, 덕분에 ==가 빠르다”는 점이 중요합니다. 이는 TypeScheme를 IR Type으로 로어링하는 방식에도 영향을 줍니다.
이제 접선 이야기를 마무리하고 type_of()의 마지막 경우로 돌아갑시다:
IR::TyApp(ty_fun, ty) => {
let Type::TyFun(_, ret_ty) = ty_fun.type_of() else {
panic!("ICE: Type applied to a non-forall IR term");
};
ret_ty.subst(ty.clone())
}
값에 대한 App과 마찬가지로, ty_fun이 TyFun 타입이라고 가정합니다. App과 달리 마지막에는 ret_ty에 subst를 호출합니다. subst는 TyFun이 바인딩한 타입 변수가 등장하는 모든 곳을 ty로 치환합니다.
그런데 subst는 ty로 바꿔야 할 TypeVar를 받지 않고 단지 Type만 받습니다. 타입이 DeBruijn 인덱스를 사용하기 때문에, 어떤 타입 변수를 치환해야 하는지 항상 알 수 있습니다. subst는 항상 TypeVar(0)부터 치환을 시작합니다. 이는 합리적입니다. TyFun(_, ret_ty)와 ret_ty 사이에는 TyFun 노드가 없으니까요.
즉, ret_ty에서 TypeVar(0)을 ty로 치환합니다. 다만 ret_ty 자체에 TyFun 노드가 있을 수도 있습니다. 다행히 subst는 그런 경우 치환해야 할 TypeVar를 올바르게 조정하는 것도 처리합니다. 시간 관계상 subst의 자세한 구현은 다루지 않겠습니다. 구현은 전체 코드에서 확인할 수 있습니다.
type_of의 Local 처리도 잠깐 들르고 가겠습니다. 금방 끝납니다:
IR::Local(v, defn, body) => {
if v.ty != defn.type_of() {
panic!("ICE: Type mismatch local variable has different type from it's definition.")
}
body.type_of()
}
가정 검증에 덜 관심이 있었다면 더 짧게 쓸 수도 있습니다. Local의 타입은 body의 타입입니다. 모든 Var가 이미 자신의 Type으로 주석(annotated)되어 있으므로, v를 위해 별도의 환경(environment)을 수정할 필요도 없습니다.
이로써 type_of()를 완성했습니다. 우리가 type_of()를 마치 타입 체커처럼 이야기하긴 했지만, 사실 이는 타입 체커라기보다 린트(lint)에 가깝습니다. type_of()를 호출해야만 하는 강제성은 없습니다. 변환 패스들이 IR을 어떻게든 망가뜨리고도 type_of()를 체크하지 않으면 그만이죠.
실제로 타입이 붙은 IR을 쓰는 몇 안 되는 컴파일러인 GHC도 자체 type_of()가 있고, 정확히 그렇게 합니다. GHC는 디버그 빌드에서는 type_of()를 켜지만, 릴리스 빌드에서는 꺼버립니다. type_of()는 실제 타입 체커보다 훨씬 가볍습니다.
이제 로어링에 대해 알아야 할 건 다 다뤘으니—
뭐라고요?
코드를 한 줄도 안 썼다고요?
lower 함수가 아직도 거대한 to-do라고요?
fn lower(
ast: Ast<TypedVar>,
scheme: ast::TypeScheme
) -> (IR, Type) {
todo!("Remember me?")
}
흠, 지금은 그걸 고칠 시간이 없습니다. 하지만 다음 글에서는 할 일이 산더미입니다. 새로 이해한 IR과 Type을 바탕으로, 드디어 제대로 코드를 작성해볼 겁니다.