IR에서 최상위 함수(아이템)를 지원하기 위해 타입 스킴을 타입 함수로 내리고, 호출 지점에서 인스턴스화 정보를 이용해 타입/로우/증거 인자를 올바른 순서로 적용하는 과정을 다룬다.
URL: https://thunderseethe.dev/posts/lowering-items/
Title: Lowering Top Level Items
언어 만들기
이 글은 언어 만들기 시리즈의 일부입니다. Rust로 프로그래밍 언어를 구현하는 방법을 가르치는 시리즈입니다.
이 글에서는 이전 패스에서 얻은 최상위 함수를 로워링합니다. IR에서 아이템(최상위 함수)을 지원하도록 row 언어를 확장합니다.
지난번에는 rows를 높은 곳에 떠 있는 AST 노드에서 끌어내려 우리의 보잘것없는 IR이라는 현실로 떨어뜨리는 3부작에 착수했습니다. 이번 목표는 그리 거창하지 않습니다. 아이템을 로워링할 겁니다. 제목이 “.Items”이지 “.Items[0]”이 아니라는 걸 보고 얼마나 안도했는지 모릅니다.
아이템은 우리 언어의 최상위 함수를 나타냅니다. 아이템을 타입 체크했던 이전 작업에서, 아이템은 허용되는 타입이 로컬 변수와 다르다는 것을 배웠습니다. 로컬 변수의 타입은 어떤 타입 변수도 도입하면 안 되지만, 아이템은 뻔뻔하게 타입 변수를 도입할 수 있습니다. 이는 아이템은 타입 스킴(type scheme)을 가지는 반면, 로컬 변수는 모노타입(monotype)만으로 버텨야 하기 때문입니다.
로워링은 타입 스킴/타입 구분을 제거하지만, 중요한 차이 하나는 남깁니다. 아이템은 타입 스킴을 가졌기 때문에 IR의 아이템 타입은 타입 함수(type function)를 갖게 됩니다. lower의 끝에서 아이템의 IR을 타입 함수로 감싸는 것을 이미 본 적이 있습니다. 이는 로컬 변수가 갖지 못하는 새로운 능력을 줍니다. 아이템은 여러 타입으로 인스턴스화될 수 있습니다.
동시에 새로운 책임도 생깁니다. 아이템을 호출할 때, 그 호출에 맞는 타입을 어떤 것으로 넘겨야 하는지 알아내야 합니다. 아이템은 여러 인스턴스화를 지원하므로, 로컬 변수와 달리 아이템 호출의 타입이 무엇인지 즉시 명확하지 않습니다.
다행히 타입 체킹이 이미 대부분의 일을 해두었습니다. 타입 체킹은 유니피케이션(unification)을 사용해 각 아이템 호출에 어떤 타입이 전달되는지 추론했습니다. 우리가 할 일은 타입 체킹에서 저장해 둔 작업 결과를 이용해 로워링된 아이템 호출에 타입을 적용하기만 하면 됩니다.
빠른 복습
types/items에서, 새 AST 노드는 하나만 필요했습니다:
enum Ast<V> {
// ...our other nodes
Item(NodeId, ItemId),
}
이는 두 개의 새 타입을 도입합니다:
ItemIdItemWrapper.ItemId는 예상한 대로 단순합니다:
struct ItemId(usize);
이는 ast::Var와 비슷한 역할을 합니다. 아직 작성하지 않은 어떤 이름 해석(name resolution) 패스가 Item을 만날 때마다 고유한 ItemId를 할당한다고 상상해볼 수 있습니다.
ItemWrapper는 좀 더 복잡합니다:
struct ItemWrapper {
types: Vec<Type>,
rows: Vec<Row>,
evidence: Vec<Evidence>
}
ItemWrapper의 역할은 각 아이템 호출에 대한 인스턴스화 결과를 저장하는 것입니다. 아이템을 인스턴스화할 때, 도입된 모든 변수와 증거(evidence)를 담은 ItemWrapper를 item_wrappers에 저장합니다.
item_wrappers는 각 Item에 대해 엔트리를 가지는 NodeId → ItemWrapper 맵입니다:
struct TypesOutput {
//...our other outputs
item_wrappers: HashMap<NodeId, ItemWrapper>,
}
아이템은 AST 자체 밖의 새 데이터가 필요합니다. 그래서 ItemSource도 만듭니다. 이는 스코프 안에 있는 모든 아이템의 타입 스킴을 담는 타입입니다. 이것도 역시 아직 작성하지 않았지만 언젠가는 꼭 쓸 이름 해석 패스의 산출물이라고 상상할 수 있습니다:
struct ItemSource {
types: HashMap<ItemId, TypeScheme>,
}
아이템에는 애노테이션이 있어야 한다는 요구 사항 덕분에 ItemSource를 구성하는 일은 아주 쉽습니다. 아이템의 타입 스킴을 결정하기 위해 추가 처리를 할 필요가 없습니다. 소스 코드에서 각 ItemId와 TypeScheme를 모아 ItemSource로 조립하기만 하면 됩니다.
여정을 시작하며
우리는 오랜 친구 lower 함수에서 여정을 시작합니다:
fn lower_with_items(
item_source: ast::ItemSource,
out: TypesOutput,
) -> (IR, Type) {
// ...some code
}
어… 음. 우리 옛 친구가 이렇게 생겼던가요.
아, 여기 있네요. 충분히 스크롤하지 않았습니다:
fn lower(
out: TypesOutput,
) -> (IR, Type) {
lower_with_items(
ast::ItemSource::default(),
out)
}
좋습니다. 근데 lower도 제가 기억하던 모습은 아닌데요. 아이템 타입 체크할 때도 한 번 이런 일이 있었습니다. lower 함수는 한 번에 아이템 하나를 처리합니다. 하지만 다른 아이템을 호출할 수 있게 하려면, lower가 처리하는 단일 아이템 바깥의 정보가 필요합니다.
완전한 컴파일러라면 소스 파일에서 다른 아이템들도 파싱해 들고 있었겠죠. 하지만 우리는 (아직) 그렇지 않습니다. 대신 ItemSource로 필요한 아이템 메타데이터를 제공하는 방식으로 흉내낼 수 있습니다. 타입 체크에서 이 트릭을 써서 아이템의 TypeScheme를 얻었습니다. 여기서도 다시 써서 IR 아이템의 Type을 얻겠습니다.
편의를 위해 lower를 제공하고, item_source에는 기본값을 넘기게 합니다. 대부분의 컴파일에는 아이템이 있겠지만, 테스트에는 유용합니다. 타입 체크와 달리(그때는 ItemSource를 무에서 끌어내야 했지만), 로워링은 ast::ItemSource에서 출발할 수 있습니다. lower_with_items는 새 IR ItemSource가 아니라 ast::ItemSource를 받도록 해서 이를 드러냅니다.
새 lower 함수 정착시키기
이름 바꾸기와 파라미터 추가로 낯선 땅에 와 있는 느낌이지만, lower_with_items를 대충 훑어보면 보이는 것보다 익숙하다는 걸 알 수 있습니다:
fn lower_with_items(
item_source: ast::ItemSource,
out: TypesOutput
) -> (IR, Type) {
let lowered_scheme = lower_ty_scheme(out.scheme);
let mut supply = VarSupply::default();
let mut params = vec![];
let ev_to_var: HashMap<ast::Evidence, Var> =
lowered_scheme.ev_to_ty
.into_iter()
.map(|(ev, ty)| {
let param = supply.supply();
let var = Var::new(param, ty);
params.push(var.clone());
(ev, var)
})
.collect();
let mut lower_ast = LowerAst {
supply,
types: lower_ty,
ev_to_var,
solved: vec![],
row_to_ev: out.row_to_ev,
branch_to_ret_ty: out.branch_to_ret_ty,
item_wrappers: out.item_wrappers,
item_source: lower_item_source(item_source),
item_supply: ItemSupply::default(),
};
let ir = lower_ast.lower_ast(out.typed_ast);
let solved_ir = lower_ast
.solved
.into_iter()
.fold(ir, |ir, (var, solved)| IR::local(var, solved, ir));
let param_ir = params
.into_iter()
.rfold(solved_ir, |ir, var| IR::fun(var, ir));
let bound_ir = lowered_scheme.kinds
.into_iter()
.fold(param_ir, |ir, kind| IR::ty_fun(kind, ir));
(bound_ir, lowered_scheme.scheme)
}
강조된 줄만이 우리의 주의를 요합니다. 그래도 믿음직한 lower가 새 별칭 아래 여전히 존재하는 걸 보니 안심이 됩니다.
아이템 소싱하기
첫 번째 새 줄은 lower_item_source 함수를 도입합니다. 정의를 살짝 보면:
fn lower_item_source(
items: ast::ItemSource
) -> ItemSource {
todo!()
}
ast::ItemSource에서 ItemSource로 우리를 실어 나르는 함수입니다. ast::ItemSource는 ast::ItemId를 TypeScheme에 매핑합니다. 새 ItemSource도 비슷한 역할을 합니다:
struct ItemSource {
items: HashMap<ast::ItemId, Type>,
}
로워링에서는 TypeScheme가 Type으로 바뀝니다. 따라서 ItemSource가 ast::ItemId를 Type에 매핑하는 것이 자연스럽습니다. 이에 따라 lower_item_source의 본문은 직관적입니다:
fn lower_item_source(
items: ast::ItemSource
) -> ItemSource {
ItemSource {
items: items
.types
.into_iter()
.map(|(item_id, ty_scheme)| {
let (ir_ty, _, _) = lower_ty_scheme(ty_scheme);
(item_id, ir_ty)
})
.collect(),
}
}
아이템의 타입 스킴들을 순회합니다. lower_ty_scheme는 각 스킴을 IR 타입으로 바꿉니다. 이를 새 ItemSource에 모아 구현을 마칩니다.
여기서 ItemSource를 어떻게 로워링했는지 잠깐 옆길로 새보죠. 우리는 ast::ItemSource를 lower 함수에 넘깁니다. 그러면 중복 작업이 꽤 생깁니다. lower_with_items는 우리가 로워링하는 아이템마다 한 번씩 호출됩니다. 각 호출은 같은 ast::ItemSource를 로워링합니다(당장은 아이템이 서로 다른 스코프에 있을 수 있다는 문제는 무시합시다).
설명 목적상, item source 로워링을 포함시켜 어떻게 동작하는지 보여줬습니다. 하지만 가상의 컴파일러라면 이를 처리하는 접착(glue) 코드가 있을 것입니다. 그 코드는 한 곳에서 ast::ItemSource를 로워링하고, lower_with_items 각 호출에 이를 전달하겠죠.
아이템 공급하기
lower_with_items에서 볼 것은 이게 전부입니다. item_source는 LowerAst의 필드로 들어갑니다. 이제 다른 새 LowerAst 필드인 item_supply로 넘어갑니다.
item_supply는 놀랍게도 ItemSupply의 인스턴스입니다. VarSupply를 본떠 ItemSupply는 ast::ItemId를 새 IR id인 ItemId로 변환합니다. 로워링에서 ast::Var를 재사용하지 않는 것처럼, ast::ItemId도 재사용하지 않습니다. 대신 IR 전용 ID를 도입합니다:
struct ItemId(u32);
유사점은 근거까지 이어집니다. IR에만 존재하는 아이템을 생성하고 싶어질 겁니다. 그런 IR 전용 아이템에 ast::ItemId를 부여하기보다는, 지금 대응 관계를 끊는 게 더 쉽습니다. 필요하다면 ast::ItemId → ItemId 매핑을 기억해둘 수 있습니다. 그러면 어떤 아이템이 생성된 것이고 어떤 아이템이 Ast(따라서 사용자 코드)에서 온 것인지 쉽게 구분할 수 있습니다.
아이템 로워링하기
두 새 필드가 도입되었으니 이제 실제 로워링을 시작할 수 있습니다. 로워링이 필요하다면 lower_ast를 보세요:
impl LowerAst {
fn lower_ast(
&mut self,
ast: Ast<TypedVar>
) -> IR {
match ast {
// our lower cases...
}
}
}
match에 새 케이스 하나만 추가하면 됩니다:
Ast::Item(id, item_id) => {
todo!()
}
Ast::Item을 로워링하려면, 먼저 로워링 결과가 들어갈 대상이 필요합니다. IR에는 로워링이 겨냥할 새 Item 케이스가 필요합니다:
enum IR {
//...our previous cases
Item(Type, ItemId),
}
여기서 Item이 왜 Type을 포함하는지 의문이 들 수 있습니다. 방금 ItemSource에 아이템의 타입을 전부 넣지 않았나요? 좋은 지적이고, 성능이 우선이라면 정확히 그렇게 했을 겁니다. 하지만 여기서 우선순위는 단순함입니다.
Item에 Type을 캐시해두면 type_of가 타입을 만들기 위해 ItemSource를 요구하지 않아도 됩니다. 또한 타입을 손에 쥐고 있는 것은 우리가 IR에서 수행할 각종 순회(traversal)에도 도움이 됩니다. 물론 각 순회에 ItemSource를 스레딩할 수도 있지만, 그건 앞으로 작성할 모든 순회 인터페이스마다 복잡도를 더합니다. 타입을 내장하면 이 문제를 완전히 피할 수 있습니다.
이제 IR이 준비되었으니 다시 lower_ast로 돌아갑니다:
Ast::Item(id, item_id) => {
let ty = self.item_source.lookup_item(item_id);
todo!()
}
곧바로 미구현에 발목이 잡힙니다. lookup_item을 보러 가죠:
impl ItemSource {
fn lookup_item(
&self,
item: ast::ItemId
) -> Type {
self.items[&item].clone()
}
}
다행히 볼 것은 별로 없습니다. ast::ItemId를 받으면 그 아이템의 Type을 반환합니다. 타입 체크가 self.items에 반드시 존재하도록 보장해줍니다.
자, 다음 미구현이 튀어나오기 전에 빠르게 진도를 좀 나가봅시다:
Ast::Item(wrapper, item_id) => {
let ty = self.item_source.lookup_item(item_id);
let item_ir = IR::Item(ty, self.item_supply.supply_for(item_id));
let wrapper = self
.item_wrappers
.get(&id)
.cloned()
.expect("ICE: Item lacks expected wrapper");
todo!()
}
아, supply_for에 걸렸군요. 그래도 속도 덕분에 한 줄은 더 썼습니다.
찾아온 ty로 IR::Item을 구성합니다. 구성 과정에서 supply_for를 사용해 ast::ItemId를 ItemId로 변환합니다. supply_for는 VarSupply::supply_for와 비슷하지만 아이템용입니다. 구현은 별로 흥미롭지 않으니 전체 코드를 참고하세요.
애플리케이션 적용 순서 정하기
IR::Item을 만드는 것은 로워링의 첫 단계일 뿐입니다. 아이템 본문을 로워링할 때 타입 변수와 증거에 대한 타입 함수 및 함수로 감싸는 것을 떠올려봅시다. 마찬가지로 아이템 호출을 로워링할 때는, 그 추가 함수들에 대응하는 추가 인자를 적용해야 합니다.
이 인자들은 타입 체커에는 존재하지 않았지만, 우리가 무엇인지 알아낼 충분한 정보를 저장해 두었습니다. 그게 각 Item 노드마다 ItemWrapper를 저장하는 이유입니다. 이 구조체는 아이템을 어떻게 인스턴스화했는지를 기억합니다.
인스턴스화에서 나온 정보는 우리가 아이템에 인자를 추가하는 데 딱 필요합니다. 일반화(generalization)가 아이템에 타입 함수를 추가하는 정보를 갖고 있다면, 그 보완물인 인스턴스화(instantiation)는 추가된 타입 함수를 적용하는 정보를 갖고 있는 게 자연스럽습니다. ItemWrapper는 답을 다 갖고 있지만, 올바른 순서로 적용해야 합니다.
인자를 넘길 때는 함수가 감싸진 순서와 같은 순서로 정렬되어야 합니다. 우리는 IR을 다음 순서로 감쌉니다:
따라서 인자를 넘길 때는 역순이어야 합니다:
역순으로 하면 인자가 해당 함수들과 맞물립니다. 간단한 예시로 이유를 볼 수 있습니다. 다음 타입을 가진 항 ir을 생각해봅시다:
Type::ty_fun(Kind::Type,
Type::ty_fun(Kind::Row,
Type::fun(<ev_type>, ...)
만약 같은 순서로 인자를 적용하려고 하면:
IR::ty_app(
IR::ty_app(
IR::app(ir, <ev_term>),
Row::Open(...)),
Type::Var(...))
문제가 바로 보입니다. 우리는 <ev_term>를 타입 함수에 적용하고 있습니다. 더 나쁘게는 Type::Var(...)를 함수에 타입 적용(type apply)하고 있죠.
역순은 이 문제를 깔끔하게 해결하므로, ItemWrapper에 대해 그 순서를 사용하겠습니다. 순서가 정해졌으니 먼저 타입을 적용합니다:
let ty_ir = wrapper.types.into_iter().fold(item_ir, |ir, ty| {
IR::ty_app(ir, TyApp::Ty(self.types.lower_ty(ty)))
});
각 타입을 순회하며 원래 ir을 ty_app 노드로 감쌉니다. rows도 같은 방식으로 적용합니다:
let row_ir = wrapper.rows.into_iter().fold(ty_ir, |ir, row| {
IR::ty_app(ir, TyApp::Row(self.types.lower_row_ty(row)))
});
마지막으로 증거 파라미터는 값이므로 일반 애플리케이션으로 적용합니다:
wrapper.evidence.into_iter().fold(row_ir, |ir, ev| {
let param = self.lookup_ev(ev);
IR::app(ir, IR::Var(param))
})
이로써 item 케이스가 완성되고 Ast::Item(...)은 다음으로 변환됩니다:
IR::app(
IR::ty_app(
IR::ty_app(
IR::Item(...),
<type>),
<row>),
<evidence)
아이템에 나머지 인자들을 넘기는 것은 걱정할 필요가 없습니다. 그것들은 이미 AST에서 Ast::App 노드로 표현되어 있습니다. 로워링이 알아서 처리해줄 겁니다.
여기서 약간의 속임수가 있었음을 고백해야 합니다. 사실 AST를 로워링하면서 TyApp 노드를 구성한 건 이번이 처음입니다. TyApp는 처음부터 있었지만 지금까지 필요하지 않았습니다. 이렇게 오래 속여서 미안합니다.
하지만 이해해 주세요. 사용할 방법도 없이 홀로 타입 함수를 소개할 수는 없었거든요. 젤리 없는 땅콩버터가 뭐냐고요? 베이컨 없는 달걀? 토스트 없는 콩?
지금까지 타입 애플리케이션을 쓰지 않았던 이유는 인스턴스화와 일반화의 이중성(duality)에 있습니다. 우리는 타입 스킴을 위해서만 타입 함수를 도입하고, 타입 스킴은 아이템을 일반화할 때만 도입됩니다. 따라서 우리는 아이템을 인스턴스화할 때만 타입 함수를 소비합니다(증거 항은 둘 다 아주 약간 쓰긴 합니다만).
이게 아이템을 IR로 로워링하기 위해 필요한 변경의 전부입니다. 작지만 중요한 IR 확장입니다. 여기서의 변화만 보면 확 눈에 띄진 않지만, 이전에는 없던 새 기능이 생겼습니다: 재귀입니다.
참조하고 싶은 모든 아이템은 ItemSource에 들어 있습니다. 그런데 거기엔 우리가 지금 로워링하고 있는 바로 그 아이템도 포함될 수 있습니다. Var는 이런 가능성을 공유하지 않습니다. Var는 재귀적일 수 없으므로, (현재로서는) 우리가 재귀가 되는 유일한 방법은 Item을 호출하는 것입니다.
재귀는 로워링에는 아무 문제를 일으키지 않습니다. 아이템들은 애노테이션되어 있으므로, 어떤 아이템 정의도 처리하지 않고 ItemSource를 채울 수 있습니다. 하지만 컴파일러의 다음 단계들에서는 아이템이 재귀 가능성을 도입한다는 사실을 염두에 두어야 합니다. 그렇지 않으면 컴파일러 패스가 영원히 끝나지 않는 일을 겪을 수도 있으니까요.