최상위 함수(아이템)를 언어에 추가하고, 사용자 제공 타입 주석을 기반으로 타입을 검사하며, rigid/flexible 변수 구분과 인스턴스화를 통해 아이템 호출을 타입 추론기에 통합한다.
URL: https://thunderseethe.dev/posts/check-top-level-items/
Title: Checking Types of Top Level Functions
이 글은 언어 만들기 시리즈의 일부다. Rust로 프로그래밍 언어를 구현하는 방법을 가르치는 시리즈다.
이 글은 최상위 함수에 대한 타입 검사를 다룬다. row 언어를 최상위 함수와 타입 검사로 확장한다.
지난 시즌에는 시간이 참 빨리도 흘렀는데, row type을 사용해 대수적 데이터 타입을 지원하도록 추가했다. 곱 타입과 합 타입을 모두 갖췄으니 우리의 타입 추론은 거의 완성에 가까워 보인다. 다만 스코프 측면이 조금 부족하다. 최상위 함수를 호출할 방법이 없다.
더 나쁜 건, 최상위 함수 자체가 아예 없다는 점이다. 최상위 함수(이후부터는 간단히 아이템(item)이라고 부르겠다)는 어떤 이름이 AST의 한 인스턴스에 연관된 것이다. AST는 그 아이템의 본문 역할을 하고, 이름은 다른 AST들이 그 아이템을 참조하는 방법이다. 거의 모든 프로그래밍 언어에는 최상위 함수를 정의하는 개념이 있다(하지만 우리 언어에는 아직 없다!). Rust의 fn, JavaScript의 function, Python의 def, 등등.
타입 추론을 돌아보면, 어디에 아이템을 추가해야 할지 명확하지 않다. type_infer는 AST를 받는데, 모든 AST 노드를 살펴봐도 최상위 함수를 정의하거나 참조하는 노드는 없다. 이 지점에서 반론이 나올 수 있다. 변수도 있고, 함수형 언어이니 최상위 함수를 변수로 넣으면 되지 않느냐고 말이다. 아이템을 정의하고 로컬 함수처럼 변수로 호출하면 간단하다. 실제로 가능하다. 프로그램을 “모든 최상위 함수를 어떤 표현식의 변수 바인딩으로 묶는 방식”으로 구성할 수 있다. 흔히 main을 호출하는 형태로 말이다:
let
-- 하나의 최상위 아이템
f = ...
-- 또 다른 최상위 아이템
g = ...
-- main도 최상위 아이템
main = f (g 3)
in main
하지만 우리는 그렇게 프로그램을 조직하지 않을 것이다.
다들 잠깐 무릎 꿇고 들어라. 마치 결승에서 지고 난 뒤 유소년 축구 코치처럼, 이제부터는 이념(ideology) 얘기를 좀 하겠다. 최상위 함수는 변수일 수 있지만, 그래야만 할까? 컴파일러 아키텍처를 생각할 때 많은 관심사는 작업을 어떻게 분할할 수 있는지에 달려 있다. 작업을 덩어리로 나눌 수 있을 때마다 캐싱과 병렬화의 기회가 생긴다. 아이템은 코드에서 작업을 나누기 위한 자연스러운 경계가 된다.
예를 들어 컴파일러는 아이템을 그룹으로 나누고 각 그룹을 병렬로 컴파일할 수 있다. 컴파일러는 아이템의 타입을 컴파일 간에 저장해 두었다가 다음 컴파일 때 해당 아이템의 본문이 바뀌지 않았다면 저장된 타입을 재사용할 수 있다. 로컬 변수와 아이템을 섞어버리면 작업을 효율적으로 분리할 능력을 잃는다.
아이템이 제공하는 구분은 또 다른 용도가 있다. 로컬 변수는 항상 어떤 타입을 갖지만, 아이템은 타입 스킴(type scheme)을 갖는다. 로컬 변수에도 타입 스킴을 허용할 수 있는데, 이를 let 일반화(let generalization)라고 부른다. 우리는 이 기능을 하지 않을 것이다. 이유는 Let Should not be Generalised에 잘 정리돼 있다. 요약하자면, let 일반화는 실제로 자주 등장하지 않고, 아이템만 일반화하면 많은 것들을 크게 단순화할 수 있다.
이념만이 결정의 이유는 아니다. 실용적인 측면에서도 로컬 변수와 아이템은 서로 다르게 컴파일하고 싶다. 로컬 변수는 레지스터나 스택 슬롯 접근으로 바뀐다. 반면 아이템은 다른 코드 섹션으로의 호출이다.
아이템 경계를 따라 작업을 나누고 싶다는 목표에서 또 하나의 결정이 나온다. 아이템 정의는 추론(infer)이 아니라 검사(check)한다. 즉 모든 아이템 정의에는 사용자가 제공한 타입 애노테이션이 있어야 한다. 아이템 정의의 타입을 추론할 수도 있지만, 우리가 이를 하지 않음으로써 중요한 성질을 얻는다.
최상위 정의의 타입 추론은 원격 작용(action at a distance)을 일으킨다. 어떤 아이템의 본문을 바꿔 추론된 타입이 달라지면, 코드베이스의 전혀 다른 곳에서 seemingly 관련 없어 보이는 타입 에러가 발생할 수 있다. 그 에러가 바뀐 아이템 호출 지점에 생긴다는 보장도 없다. 이런 단점 때문에 Haskell처럼 최상위 타입 추론을 지원하는 언어들은 아이템에 타입 애노테이션을 달 것을 권장한다. 우리는 애노테이션을 필수로 요구함으로써 이 원격 작용을 아예 피한다.
이 장점만으로도 애노테이션을 강제할 가치가 충분하다. 하지만 이점은 거기서 끝나지 않는다. 가독성 측면에서 모든 최상위 정의에 애노테이션이 달려 있으면 훌륭한 문서가 된다. 구현 측면에서도 타입 체커가 쉬워진다. 모든 아이템에 애노테이션이 있다면 아이템 호출을 만나자마자 그 타입을 즉시 알 수 있다. 따라서 타입 체커는 그 타입을 조회하고 계속 진행하기만 하면 된다.
이 말은 곧, 어떤 두 아이템이든 서로 병렬로 검사할 수 있다는 뜻이다. 모든 아이템의 타입이 이미 준비돼 있으므로 아이템들 사이에 데이터 의존성이 없다. 만약 아이템 타입을 추론하도록 허용한다면, 아이템 호출을 만날 때마다 그 아이템의 타입을 알아내러 가야 한다. 이는 임의의 작업이 될 수 있다. 호출한 아이템이 또 다른 아이템을 부르고… (재귀 아이템 얘기는 시작도 하지 말자). 이를 해결하려면 호출되는 모든 아이템의 타입을 미리 추론해 캐시하면 된다. 문제 해결… 같지만 새 문제가 생긴다. 어떤 아이템이 호출되는지 어떻게 알아서 타입을 캐시할 것인가? 이제 AST를 한 번 훑어 호출된 아이템을 모으고, 다시 한 번 훑어 실제 타입 검사를 해야 한다.
물론 이런 것들이 극복 불가능한 문제는 아니다. Haskell과 OCaml은 이런 이슈를 극복할 수 있다는 명확한 증거다. 하지만 새로운 언어에 아이템을 추가하면서, 트레이드오프를 한 번 뒤로 물러나 평가할 가치는 있다. 개인적으로는 최상위 추론을 지원하느니 아이템에 시그니처를 요구하는 편이 노력 대비 가치가 더 크다.
무릎의 흙을 털어라. 이 글에서 이념 얘기는 이쯤 하자. 이제 실제 작업을 시작하자. 아이템을 지원하려면 다음이 필요하다:
type_checkItemIdItemItem을 처리하도록 추론 엔진 업데이트아, 제약(constraints)이나 유니피케이션(unification) 로직은 아이템 지원을 위해 건드릴 필요가 없다.
type_check아이템 정의는 사용자가 제공한 애노테이션과 대조해 검사된다. 이 애노테이션은 타입 스킴을 제공하고, 우리는 아이템 본문이 실제로 그 타입 스킴과 일치하는지만 검사하면 된다. 이미 양방향 타입 시스템을 위한 check 함수가 있으니 쉬워 보인다. 우선 매우 단순한 type_check를 만들어 보자:
fn type_check(
ast: Ast<Var>,
signature: TypeScheme
) -> Result<Ast<TypedVar>, TypeError> {
let mut ctx = TypeInference::default();
// `infer` 대신 `check`로 시작한다.
let mut out = ctx.check(
im::HashMap::default(),
ast,
signature.ty);
// 해결(solve) 과정에서 사용될 수 있도록 애노테이션의 evidence를 추가한다.
out
.constraints
.extend(signature
.evidence.iter()
.map(|ev| match ev {
Evidence::RowEquation { left, right, goal } =>
Constraint::RowCombine(RowCombination {
left: left.clone(),
right: right.clone(),
goal: goal.clone(),
}),
}));
ctx.unification(out.constraints)?;
// 여전히 치환(substitute)은 필요하지만 ast에 대해서만 하면 된다.
let subst_ast = ctx.substitute_ast(out.typed_ast);
// 끝
Ok(subst_ast.value)
}
타입 스킴을 타입과 evidence로 분해한다. AST를 그 타입에 대해 검사해 제약 집합을 만든다. 타입 스킴에서 온 evidence도 제약에 추가해서 해결 과정에서 사용할 수 있게 한다. 검사는 타입을 “생성”할 필요는 없지만, 치환을 얻기 위해서는 여전히 제약을 해결해야 한다. 최종 타입이 없더라도, 타입이 달린 AST는 치환을 적용해야 한다. 간단한 예제로 아이템 검사가 어떤 느낌인지 보자.
어떤 함수(인자)를 받아서 그것을 다른 인자에 적용하는 아이템 본문이 있다고 하자:
let f = Var(0);
let x = Var(1);
let body = Ast::fun(f, Ast::fun(x, Ast::app(Ast::Var(f), Ast::Var(x))));
이를 다음 시그니처로 검사해 보자:
let a = TypeVar(0);
let signature = TypeScheme {
unbound_tys: set![a],
unbound_rows: set![],
evidence: vec![],
ty: Type::fun(
Type::fun(Type::Var(a), Type::Var(a)),
Type::fun(Type::Var(a), Type::Var(a))
)
};
기대하는 typed AST가 나오고 타입 에러가 나지 않으니 성공한 것이다:
assert_eq!(
type_check(ast, signature),
Ok(Ast::fun(
TypedVar(f, Type::fun(Type::Var(a), Type::Var(a))),
Ast::fun(
TypedVar(x, Type::Var(a)),
//... 이 부분은 신경 쓰지 않는다
)))
);
좋다! 이렇게 아이템을 검사할 수 있게 됐다. 좋은 엔지니어로서, 시그니처를 일부러 틀리게 바꿔 타입 에러가 나오는지도 확인해 보자. 본문은 그대로 두고 잘못된 시그니처를 준다:
let a = TypeVar(0);
let signature = TypeScheme {
unbound_tys: set![a],
unbound_rows: set![],
evidence: vec![],
ty: Type::fun(
Type::fun(Type::Var(a), Type::Var(a)),
Type::fun(Type::Int, Type::Int)
)
};
이제 f는 a -> a인데 인자 x는 Int 타입이다. 즉 Int가 a가 아니라는 타입 에러가 나야 한다:
assert_eq!(
type_check(ast, signature),
Ok(Ast::fun(
TypedVar(f, Type::fun(Type::Int, Type::Int)),
Ast::fun(
TypedVar(x, Type::Int),
_..._
)))
);
어…? 흠. 이건 좋지 않다. 타입 체커가 너무 “잘” 동작했다. 타입 변수 a를 Int로 잘못 “해결”해 버렸다. 보통 추론에서는 그게 정확히 우리가 원하는 행동이다. 하지만 지금은 애노테이션이 함수가 반드시 a -> a여야 한다고 명시했다. 우리는 이를 풀어버리면 안 된다.
type_check를 추가하기 전에는 타입 추론만 지원했다. 타입 추론이 타입(또는 row) 변수를 도입하는 유일한 방법은 infer나 check 중에 fresh 변수를 만드는 것이었다. 하지만 이제 타입 검사를 지원하면서, 타입(또는 row) 변수를 도입하는 새로운 방법이 생겼다. 사용자가 애노테이션의 일부로 변수를 제공할 수 있다.
이 변수들은 제약 생성 중 도입된 변수들과 모양은 같지만, 동작은 Int 같은 기본 타입에 더 가깝다. 이 변수들은 풀 수 없고, 오직 자기 자신과만 같다. 애노테이션 타입 검사는 이제껏 무시할 수 있었던 변수의 구분을 드러냈다. 다행히 이런 문제는 처음 겪는 게 아니다. 우리가 맞닥뜨린 것은 유니피케이션 변수(unification variable)와 “타입” 변수(type variable)의 차이다.
유니피케이션 변수는 지금까지 우리가 써온 것이다. 제약 생성 중 만들고, 유니피케이션 중 해결하고, (지금까지는) 마지막에 일반화했다. 유니피케이션 변수는 사랑스럽다. 새로 합류한 타입/row 변수는 애노테이션으로만 도입된다. 애노테이션이 제공한 것이므로 풀 수 없다. 이 “풀 수 없음” 때문에 두 변수는 흔히 rigid와 flexible로 불린다. 유니피케이션 변수는 풀릴 수 있으니 flexible이고, 타입 변수는 풀릴 수 없으니 rigid다.
두 종류의 변수가 생기면서, 이제 죄값으로 리팩터링을 많이 해야 한다. 대부분은 단순 작업이라 자세한 설명은 생략한다. repo의 자세한 변경 내역에서 확인할 수 있다. 리팩터링 목록:
TypeVar를 TypeUniVar로 이름을 바꾼다.Var 케이스의 이름을 Unifier로 바꾼다.RowVar도 같은 방식으로 (RowUniVar로), Row::Open도 (Row::Unifier로) 바꾼다.이 3가지를 끝내면 타입 체커의 동작은 완전히 동일하지만, 이제 모든 것을 “타입 변수” 대신 “유니피케이션 변수”라고 부르게 된다. 당신에게는 3개의 불릿 포인트일 뿐이겠지만, 내게는 며칠 밤샘이었다. 잠깐 숨 돌리자. 여기서 왜 이렇게 이름을 바꾸는지 설명해 보자.
이름 바꾸는 대신 기존 TypeVar는 그대로 두고, 새 변수 종류를 다른 이름으로 도입할 수도 있다. 하지만 우리의 목표는 유니피케이션 변수를 타입 체커의 순수한 구현 상세로 만드는 것이다. 필요한 유니피케이션 변수는 전부 제약 생성 중에 도입되고, 치환 과정에서 제거된다. 장기적으로 이는 컴파일러 전체에 좋다.
유니피케이션 변수는 타입 체커 내부에서는 흔하지만, 그 밖에서는 존재하지 않는다. 이전에는 컴파일러 다른 부분과 타입 체커가 단 하나의 변수 종류를 공유했다. 이제 두 종류가 됐으니 각 단계에서 어떻게 사용될지 생각해 볼 가치가 있다. 컴파일러의 다른 단계는 row 변수와 타입 변수를 다룬다. 유니피케이션 변수에는 관심이 없다. 타입이 어떻게 풀리는지는 그들 알 바가 아니다. 유니피케이션 변수는 타입 검사의 구현 디테일이므로, 그 목적을 반영하도록 이름을 바꾸는 것이다.
이제 새로운 변수 종류를 도입하자. 먼저 TypeVar와 RowVar를 만든다:
#[derive(PartialEq, Eq, PartialOrd, Ord, Clone, Copy, Debug, Hash)]
pub struct TypeVar(pub u32);
#[derive(PartialEq, Eq, PartialOrd, Ord, Clone, Copy, Debug, Hash)]
pub struct RowVar(pub u32);
다음으로 “새” 변형 Type::Var와 Row::Open을 추가한다.
enum Type {
/// rigid 타입 변수
Var(TypeVar),
// ... 나머지 케이스들
}
enum Row {
/// rigid row 변수
Open(RowVar),
// ... 나머지 케이스들
}
마지막으로 유니피케이션이 이 새 변형을 처리하도록 수정한다. 이 변형들은 풀 수 없으므로 Type::Int처럼 동작한다. 자기 자신과만 같아야 한다:
fn unify_ty_ty(...) -> Result<(), TypeErrorKind> {
// ... 정규화하고 타입으로 match
// rigid 변수에 대한 새 match 케이스
(Type::Var(a), Type::Var(b)) if a == b => Ok(()),
// ... 나머지는 그대로
}
row에 대해서도 unify_row_row에서 동일하게 한다:
fn unify_row_row(...) -> Result<(), TypeErrorKind> {
// ..정규화하고 row로 match
// rigid 변수에 대한 새 match 케이스
(Row::Open(left), Row::Open(right)) if left == right => Ok(()),
// ... 나머지 유니피케이션 케이스들
// RowsNotEqual 케이스도 업데이트하여
// 두 `Row::Open`이 같지 않을 가능성을 포함한다.
(left, right) => Err(TypeErrorKind::RowsNotEqual((left, right))),
}
}
이전에는 RowsNotEqual이 ClosedRow에서만 발생할 수 있었다. 이제 유니피케이션 변수와 row 변수를 분리했으니, 두 row 변수가 같지 않을 수도 있다. 간단한 수정으로, RowsNotEqual이 ClosedRow가 아니라 임의의 Row를 받도록 업데이트한다:
enum TypeErrorKind {
// 예전에는 (ClosedRow, ClosedRow)였다.
RowsNotEqual((Row, Row)),
// ...
}
이제 Type에는 두 변수 종류를 위한 두 변형이 있다: Type::Unifier와 Type::Var. 리팩터링은 거의 끝났다. 마지막으로 손봐야 할 부분은 치환(substitution)이다. 타입 추론의 끝에서 치환은 남아 있는 유니피케이션 변수를 해결하고 Type을 TypeScheme으로 바꾼다.
rigid/flexible 구분 이전에는 변수 치환이 단순했다. 치환 맵에 있으면 대응 타입으로 바꾸고, 없으면 그대로 둔다. 지금도 대부분은 동일하지만, “해결되지 않은 유니피케이션 변수”를 다르게 처리하고 싶다. 그대로 두는 대신, fresh 타입 변수(또는 row 변수)로 바꿀 것이다. 이렇게 하면 유니피케이션 변수가 타입 체커 밖으로 새어 나가지 않게 된다.
이 변경은 비교적 간단하다. TypeInference에 새 필드를 추가한다:
struct TypeInference {
//... 이전에 보던 것들
subst_unifiers_to_tyvars: HashMap<TypeUniVar, TypeVar>,
next_tyvar: u32,
subst_unifiers_to_rowvars: HashMap<RowUniVar, RowVar>,
next_rowvar: u32,
// 아이템 타입 추론에서 나중에 필요하다.
item_wrappers: HashMap<NodeId, ItemWrapper>,
}
유니피케이션 변수를 대응하는 변수로 바꾸는 헬퍼 메서드를 추가한다:
impl TypeInference {
fn tyvar_for_unifier(&mut self, var: TypeUniVar) -> TypeVar {
*self.subst_unifiers_to_tyvars.entry(var)
.or_insert_with(|| {
let next = self.next_tyvar;
self.next_tyvar += 1;
TypeVar(next)
})
}
fn rowvar_for_unifier(&mut self, var: RowUniVar) -> RowVar {
*self.subst_unifiers_to_rowvars.entry(var)
.or_insert_with(|| {
let next = self.next_rowvar;
self.next_rowvar += 1;
RowVar(next)
})
}
}
이 헬퍼는 해당 유니피케이션 변수를 이미 변환했는지 확인하고, 했다면 생성된 변수를 반환한다. 아니라면 next_tyvar/next_rowvar로 새 변수를 만들어 저장한다. 이걸 바탕으로 substitute_* 메서드들을 바꾸는 건 쉽다. substitute_ty 업데이트를 보면 다른 것들도 추론 가능하다:
fn substitute_ty(&mut self, ty: Type) -> SubstOut<Type> {
match ty {
Type::Var(v) => SubstOut::new(Type::Var(v)),
Type::Unifier(v) => {
let root = self.unification_table.find(v);
match self.unification_table.probe_value(root) {
Some(ty) => self.substitute_ty(ty),
None => {
let tyvar = self.tyvar_for_unifier(root);
SubstOut::new(Type::Var(tyvar)).with_unbound_ty(tyvar)
}
}
}
// 나머지 케이스는 그대로...
}
}
대부분 동일하지만, 해결되지 않은 unifier를 만나면 tyvar_for_unifier를 호출해 변환하고 Type::Unifier 대신 Type::Var를 반환한다.
여기서 새 필드 item_wrappers도 있다. 이 맵은 NodeId를 이용해 각 Item에 메타데이터를 붙인다. 각 아이템마다 ItemWrapper를 저장한다:
struct ItemWrapper {
types: Vec<Type>,
rows: Vec<Row>,
evidence: Vec<Evidence>
}
아이템을 타입 체크하는 동안 ItemWrapper가 채워진다. 우리는 새 연산인 “인스턴스화(instantiation)”를 도입할 것이고, wrapper는 아이템을 인스턴스화하며 만들어낸 타입들을 저장한다. 타입 체크가 끝날 때 ItemWrapper도 (나머지 Ast처럼) 치환을 적용한다.
휴, 리팩터링은 이쯤이면 충분하다. 타입 검사에 대한 근본적인 오해가 이런 대가를 치르게 했다. 이제 새 기능을 추가하자.
아이템은 기존 변수들과 근본적으로 다르다. 변수는 명시적으로 로컬 변수를 나타낸다. AST 어딘가에 있는 fun 노드에 의해 반드시 바인딩돼야 한다. 반면 아이템은 로컬이 아니어야 하며, AST의 fun 노드로 바인딩될 수 없다. 따라서 아이템에 별도의 식별자를 주자:
#[derive(PartialEq, Eq, PartialOrd, Ord, Clone, Copy, Debug, Hash)]
pub struct ItemId(pub usize);
ItemId는 Var와 모양은 똑같지만 타입이 다르므로 서로 헷갈릴 수 없다. ItemId가 새 타입이니, 새 AST 변형 Item도 필요하다:
#[derive(Debug, PartialEq, Eq)]
pub enum Ast<V> {
// 기존 케이스들...
// 최상위 정의에 대한 참조
Item(NodeId, ItemId),
}
자연스러운 질문이 생긴다. 아이템이 fun 노드로 바인딩되지 않는다면, 어떤 아이템이 사용 가능한지 어떻게 알며(더 중요하게) 그들의 타입은 어떻게 아는가?
이는 중요한 질문이고, 만약 우리가 파서와 이름 해석기(name resolver)를 작성하고 있었다면 답을 해야 한다. 하지만 우리는 타입 체커를 작성 중이니, 슬쩍 빠져나가자. 타입 체커 단계에 도달했을 때는 이름 해석이 이미 스코프 내 아이템들을 결정해 주었을 것이다. 게다가 모든 아이템은 애노테이션을 가지므로 타입도 알고 있다. 이 “가짜로 이미 알고 있음”을 ItemSource 구조체로 담자:
#[derive(Default)]
struct ItemSource {
types: HashMap<ItemId, TypeScheme>,
}
ItemSource에는 각 ItemId별 엔트리가 있고, 그 엔트리는 해당 ItemId의 애노테이션 타입을 가진다. TypeInference는 ItemSource 인스턴스를 저장한다:
struct TypeInference {
// ... 이전에 보던 것들
// ... 방금 추가한 var converter 필드들
item_source: ItemSource,
}
이 ItemSource는 스코프 내 모든 ItemId에 대한 엔트리를 가진다. 스코프 밖의 ItemId를 만나는 걱정은 하지 않아도 된다. 그건 이름 해석이 처리한다. ItemSource를 입력으로 받는 새 type_infer와 type_check 메서드를 추가하자. 원래라면 ItemSource는 이름 해석이 만들어 타입 체커에 넘겨주겠지만, 그건 우리의 관심사가 아니다:
fn type_infer_with_items(
item_source: ItemSource,
ast: Ast<Var>,
) -> Result<TypesOutput, TypeError> {
let mut ctx = TypeInference {
item_source,
//... 일반적인 기본값들
};
// ... 나머지는 모두 동일
}
fn type_check_with_items(
item_source: ItemSource,
ast: Ast<Var>,
signature: TypeScheme,
) -> Result<TypesOutput, TypeError> {
let mut ctx = TypeInference {
item_source,
//... 일반적인 기본값들
};
// ... 나머지는 모두 동일
}
Item 호출 타입 추론하기모든 아이템의 타입 스킴을 사용할 수 있으니, 새 Item 노드의 타입을 추론하는 방법을 구현할 수 있다:
fn infer(&mut self, env: im::HashMap<Var, Type>, ast: Ast<Var>) -> (InferOut, Type) {
match ast {
// ...
Item(id, item_id) => {
let ty_scheme = self.item_source.type_of_item(item_id);
// 타입 스킴의 각 타입/row 변수에 대해 fresh unifier를 만든다.
let mut wrapper_tyvars = vec![];
let tyvar_to_unifiers = ty_scheme
.unbound_tys
.iter()
.map(|ty_var| {
let unifier = self.fresh_ty_var();
wrapper_tyvars.push(Type::Unifier(unifier));
(*ty_var, unifier)
})
.collect::<HashMap<_, _>>();
let mut wrapper_rowvars = vec![];
let rowvar_to_unifiers = ty_scheme
.unbound_rows
.iter()
.map(|row_var| {
let unifier = self.fresh_row_var();
wrapper_rowvars.push(Row::Unifier(unifier));
(*row_var, unifier)
})
.collect::<HashMap<_, _>>();
// 스킴을 인스턴스화하여 변수를 방금 생성한 fresh unifier에 매핑한다.
// 이후에는 fresh unifier만 참조하는 제약들과 타입을 얻게 된다.
let (constraints, ty) =
Instantiate::new(id, &tyvar_to_unifiers, &rowvar_to_unifiers).type_scheme(ty_scheme);
let wrapper = ItemWrapper {
types: wrapper_tyvars,
rows: wrapper_rowvars,
evidence: constraints
.clone()
.into_iter()
.filter_map(|c| match c {
Constraint::RowCombine(_, row_combo) => Some(Evidence::RowEquation {
left: row_combo.left,
right: row_combo.right,
goal: row_combo.goal,
}),
_ => None,
})
.collect(),
};
self.item_wrappers.insert(id, wrapper);
(
InferOut::new(
constraints,
Ast::Item(
id,
item_id)),
ty
)
}
// ...
}
}
이 코드를 부분별로 보자. 먼저 type_of_item(item_id)는 뭘까?
impl ItemSource {
fn type_of_item(&self, item_id: ItemId) -> TypeScheme {
self.types[&item_id].clone()
}
}
음… 특별할 건 없다. 그렇다면 tyvar_to_unifiers와 rowvar_to_unifiers는 뭘 하는 걸까?
이건 인스턴스화(instantiation)의 일부다. 인스턴스화는 일반화(generalization)의 반대 연산이다. 추론의 끝에서 타입을 치환할 때, 타입의 자유 변수들을 추적해 타입 스킴으로 감싼다. 이 글 기준으로는 유니피케이션 변수를 타입 변수로 변환하는 작업도 함께 한다.
인스턴스화는 그 반대로 동작한다:
이 작업이 끝나면 fresh unifier만 사용하는 제약 리스트와 타입을 얻게 된다. 변수(로컬 변수)와 달리, 변수는 여러 번 나타나도 항상 동일한 타입을 갖지만, 아이템은 각 참조마다 고유한 타입을 갖는다. 이는 의도된 설계다. 아이템 참조는 각각 고유하며 고유한 타입을 가져야 한다(변수는 암묵적으로 같은 것을 참조하므로 다르다). 따라서 유니피케이션 변수/타입 변수 분리를 하지 않았더라도, 아이템의 타입 스킴은 각 참조마다 fresh 유니피케이션 변수를 쓰도록 인스턴스화해야 한다.
인스턴스화를 살짝 들여다보겠지만, 자세한 내용은(일반화와 비슷한 단순 작업이라) 다루지 않는다. 관심 있다면 repo에서 볼 수 있다.
struct Instantiate<'a> {
id: NodeId,
tyvar_to_unifiers: &'a HashMap<TypeVar, TypeUniVar>,
rowvar_to_unifiers: &'a HashMap<RowVar, RowUniVar>,
}
impl<'a> Instantiate<'a> {
fn type_scheme(&self, ty_scheme: TypeScheme) -> (Vec<Constraint>, Type) {
let constraints = ty_scheme
.evidence
.into_iter()
.map(|ev| self.evidence(ev))
.collect();
let ty = self.ty(ty_scheme.ty);
(constraints, ty)
}
fn evidence(&self, ev: Evidence) -> Constraint { ... }
fn row(&self, row: Row) -> Row { ... }
fn ty(&self, ty: Type) -> Type { ... }
}
type_scheme은 최상위 진입점이다. 기본적으로 타입 스킴 전체를 fold하는 코드다. 우리가 만날 수 있는 각 종류(Evidence, Row, Type)에 대해, 인스턴스를 받아 변수들을 유니피케이션 변수로 치환한 새 인스턴스를 돌려주는 함수를 갖는다. 모두 fold한 다음 생성한 제약 리스트와 타입을 반환한다.
타입 스킴을 타입으로 인스턴스화하면 끝이다. 인스턴스화된 제약과 타입을 아이템의 InferOut으로 반환한다. 이로써 아이템 지원에 필요한 모든 작업이 마무리됐다. 사용자 애노테이션에 대한 검사 지원을 추가하고, 그에 따른 결과를 처리했으며, 스코프 내 아이템을 TypeInference에 제공하는 방식을 추가했고, 마지막으로 새 Item으로 아이템 호출 타입을 추론했다. 타입 추론 엔진에 대한 비교적 소박한 확장이지만 중요한 확장이다. 다음은 아이템 로워링이다.