내려진 로우의 타입

언어 만들기

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

이 글은 이전 글에서 이어서 로우(row)를 로워링(lowering)합니다.

지난번에는 로우 타입을 어떻게 로워링할지 배웠고, IR과 Type에 로우 관련 보강을 추가했습니다. 오늘은 그 보강을 사용해 lower_ty_scheme를 업데이트하여 Evidence에 대한 타입을 생성하겠습니다.

빠른 복습

types/rows에서 필요한 것들을 빠르게 정리해봅시다.

먼저 Type입니다:

enum Type {
  Int,
  Var(TypeVar),
  Fun(Box<Self>, Box<Self>),
  Prod(Row),
  Sum(Row),
  Label(Label, Box<Self>),
}

기본 Type에 Prod, Sum, Label이 추가된 형태입니다.

• Prod는 로우를 감싸 곱(product) 타입으로 만듭니다.
• Sum은 로우를 감싸 합(sum) 타입으로 만듭니다.
• Label은 타입으로부터 싱글턴 로우(singleton row)를 만드는 방법입니다.

오늘의 주인공인 Row는 다음과 같습니다:

enum Row {
  Open(RowVar),
  Closed(ClosedRow),
}

로우는 열려 있거나(open) 닫혀 있을(closed) 수 있습니다. 열린 로우는 Type::Var 같은 변수 타입처럼, 아직 해결되지 않은(unsolved) 로우를 나타냅니다. RowVar는 TypeVar와 비슷하지만 Type이 아니라 Row로 해결(solved)된다는 점만 다릅니다.

ClosedRow는 필드에서 타입으로의 매핑을 통해, 해결된 로우를 표현합니다:

struct ClosedRow {
  fields: Vec<Label>,
  values: Vec<Type>,
}

ClosedRow는 HashMap<Label, Type>처럼 생각할 수 있습니다. 다만 fields의 특정한 순서를 유지하고, values를 제외한 fields만 손쉽게 비교하기 위해 그렇게 저장하지 않습니다. 오늘 보겠지만, 둘을 분리해 저장하면 라벨을 지우는(erasing labels) 작업도 쉬워집니다.

Row가 강화된 Type와 함께, TypeScheme도 확장됩니다:

struct TypeScheme {
  unbound_rows: BTreeSet<RowVar>,
  unbound_tys: BTreeSet<TypeVar>,
  evidence: Vec<Evidence>,
  ty: Type,
}

로우가 강화된 타입 스킴은 해결되지 않은 로우 변수들을 unbound_rows에 추적합니다. 또한 기존 TypeScheme의 친구들인 unbound_tys와 ty도 그대로 포함합니다. unbound_tys는 unbound_rows처럼 해결되지 않은 타입 변수를 추적합니다. ty는 우리의 Type으로, 스킴의 핵심입니다.

추가된 또 하나인 evidence는 해결되지 않은 로우 조합을 저장합니다. 로우 제약(row constraints)이 도입되면서, 로우 제약을 해결하는 데 실패할 가능성이 생깁니다. 이런 경우 그 제약을 증거(evidence)로 바꾸어 타입 스킴 안에 보관합니다(로우/타입 변수처럼). 따라서 Evidence는 다음과 같습니다:

enum Evidence {
  RowEquation { 
    left: Row, 
    right: Row, 
    goal: Row 
  },
}

이제 로워링에 필요한 것은 전부 준비되었습니다. 다시 본론으로 돌아갑시다.

lower의 짧은 방문

모든 장부가 정돈되어 있으니, lower를 잠깐 열어 lower_ty_scheme가 이제 어떻게 쓰이는지 봅시다:

fn lower(out: TypesOutput) -> (IR, Type) {
  let lowered_scheme = lower_ty_scheme(out.scheme);

  todo!("We'll cover the rest later.");
}

TypesOutput은 로우 기능을 위해 새로 생겼지만, 이전에 lower에 넘기던 것들을 담고 있습니다:

struct TypesOutput {
  typed_ast: Ast<TypedVar>,
  scheme: TypeScheme,
  row_to_ev: HashMap<NodeId, Evidence>,
  branch_to_ret_ty: HashMap<NodeId, Type>,
}

기존의 Ast<TypedVar>와 TypeScheme에 더해, 타입 체킹이 만들어낸 두 개의 사이드테이블 row_to_ev와 branch_to_ret_ty가 있습니다. 로우 노드를 로워링할 때 이것들을 사용합니다.

lowered_scheme이란?

그리 나빠 보이진 않네요. lower_ty_scheme는 예전엔 튜플을 반환했지만, 이제는 lowered_scheme라는 무언가를 반환합니다:

fn lower_ty_scheme(scheme: ast::TypeScheme) -> LoweredTyScheme {
  // You already know this isn't gonna look the same
}

lowered_scheme가 LoweredTyScheme인 건 자연스럽습니다. 하지만 LoweredTyScheme가 뭔지 모르겠네요:

struct LoweredTyScheme {
  scheme: Type,
  lower_types: LowerTypes,
  kinds: Vec<Kind>,
  ev_to_ty: BTreeMap<ast::Evidence, Type>,
}

여기서 변화의 첫 단서를 얻습니다. 이전에는 (Type, LowerTypes)만 반환했는데, 이제 ev_to_ty와 kinds라는 두 가지 반환값이 더 생겼습니다. 그리고 그냥 큰 튜플에 집어넣지 않고 이름을 붙여둔 건 현명한 선택이었습니다. 저는 아마 튜플을 키웠을 겁니다.

ev_to_ty는 스킴에 있는 각 evidence에 대해 생성한 Type을 추적합니다. 이 타입은 해결되지 않은 evidence마다 추가하는 함수 파라미터 타입이 됩니다. kinds는 ast::TypeScheme를 로워링하면서 생성되는 각 TypeVar의 Kind를 추적합니다. 사실 지난번에도 할 수는 있었지만, Kind가 하나뿐일 때는 의미가 없었습니다. 그런데 Kind가 두 개가 되면, 각 TypeVar의 kind가 실제로 중요해집니다.

lower_ty_scheme 업데이트

lower_ty_scheme에서 가장 먼저 하는 일이 ty_env를 만드는 것은 변함이 없습니다:

fn lower_ty_scheme(scheme: ast::TypeScheme) -> LoweredTyScheme {
  let mut kinds = todo!();
  let ty_env = todo!("Use kinds to do this");

  todo!();
}

kinds는 kind를 더 꼼꼼하게 추적하기 위한 Vec<Kind>입니다. TypeScheme는 기대하는 변수 개수를 알려주므로, 각 변수에 대해 Kind를 미리 할당할 수 있습니다:

let mut kinds = vec![Kind::Type; scheme.unbound_tys.len() + scheme.unbound_rows.len()];

kinds는 기본값이 Kind::Type이고, ty_env를 구축하면서 각 엔트리를 업데이트합니다. ty_env는 지난번과 비슷하게 구성하지만, 이제는 로우 변수와 타입 변수를 모두 다룹니다:

let ty_env = scheme
  .unbound_tys
  .into_iter()
  .map(AstTypeVar::Ty)
  .chain(scheme.unbound_rows.into_iter().map(AstTypeVar::Row))
  .rev()
  .enumerate()
  .map(|(i, tyvar)| {
    kinds[i] = tyvar.kind();
    (tyvar, TypeVar(i))
  })
  .collect();

타입 변수와 로우 변수의 순서를 정해야 합니다. 로우 다음 타입이든, 타입 다음 로우든 어느 쪽이든 상관은 없지만, 여기와 lower에서 같은 순서를 유지해야 합니다. 우리가 택할 순서는 타입들 다음 로우들입니다.

ty_env는 이제 두 종류의 변수를 담아야 합니다: ast::TypeVar와 ast::RowVar. 이를 위해 AstTypeVar라는 간단한 래퍼 enum을 둡니다(TyApp처럼):

enum AstTypeVar {
  Ty(ast::TypeVar),
  Row(ast::RowVar),
}

여기에는 보조 메서드 kind() 하나가 있습니다:

impl AstTypeVar {
  fn kind(&self) -> Kind {
    match self {
      AstTypeVar::Ty(_) => Kind::Type,
      AstTypeVar::Row(_) => Kind::Row,
    }
  }
}

이 메서드는 ty_env 구성에서 사용됩니다. 각 AstTypeVar의 kind를 kinds[i]에 저장합니다. 이 과정이 끝나면 ty_env와 kinds 벡터가 준비됩니다. 다음 단계인 타입 로워링은 겉으로는 변하지 않았습니다:

let lower = LowerTypes { env: ty_env };

let lower_ty = lower.lower_ty(scheme.ty);

lower_ty 파고들기

lower_ty를 들여다보면 새로운 변경점들이 있습니다. 새로 추가된 것을 보기 전에, lower_ty의 기본 구조를 떠올려봅시다:

fn lower_ty(&self, ty: ast::Type) -> Type {
  match ty {
    // ...some cases
  }
}

ast의 각 로우 타입을 로워링하기 위한 케이스를 추가합니다. 적응을 위해 Label부터 시작해봅시다:

ast::Type::Label(_, ty) => self.lower_ty(*ty),

쉽네요. 라벨을 지우고 ty를 로워링합니다. 다음은 Prod와 Sum을 한 쌍으로 처리합니다:

ast::Type::Prod(row) => Type::prod(self.lower_row_ty(row)),
ast::Type::Sum(row) => Type::sum(self.lower_row_ty(row)),

둘 다 lower_row_ty를 호출합니다. Prod는 IR의 Prod 타입으로 감싸고, Sum은 IR의 Sum 타입으로 감쌉니다. 좋습니다. 그런데—

lower_row_ty란?

이름에서 짐작할 수 있듯 lower_row_ty는 ast::Row를 Row로 로워링합니다:

fn lower_row_ty(
  &self, 
  row: ast::Row
) -> Row {
  match row {
    ast::Row::Open(var) => Row::Open(self.env[&AstTypeVar::Row(var)]),
    ast::Row::Closed(closed_row) => Row::Closed(self.lower_closed_row_ty(closed_row)),
  }
}

• Open 로우면, 인덱스를 찾아 TypeVar로 바꾼 뒤 Row::Open으로 만듭니다.
• Closed 로우면, 새 헬퍼 lower_closed_row_ty로 넘깁니다.

아직 전부는 아닙니다. 더 깊이 들어가야 합니다.

lower_closed_row_ty 한 단계 더 깊게

문맥상 lower_closed_row_ty는 ClosedRow를 IR의 대응물로 바꾸는 함수입니다. 내부를 보면 놀랄 건 없습니다:

fn lower_closed_row_ty(
  &self, 
  closed_row: ast::ClosedRow
) -> Vec<Type> {
  closed_row
    .values
    .into_iter()
    .map(|ty| self.lower_ty(ty))
    .collect()
}

ClosedRow의 fields는(암묵적으로) 지우고, values의 각 타입을 로워링해 IR 타입들의 Vec을 만듭니다. 꽤 파고들었지만, lower_ty와 그 로우 관련 자손들에서 바뀐 것은 이게 전부입니다.

lower_ev_ty로 가는 길목에서 lower_ty_scheme를 잠깐 스쳐 지나가 봅시다. $200은 가져가지 마세요:

fn lower_ty_scheme(scheme: ast::TypeScheme) -> LoweredTyScheme {
  // ...picking up where we left off.
  let lower_ty = lower.lower_ty(scheme.ty);

  let mut ev_to_ty = BTreeMap::new();
  let ev_tys = scheme
    .evidence
    .into_iter()
    .map(|ev| {
      let ty = lower.lower_ev_ty(ev.clone());
      ev_to_ty.insert(ev, ty.clone());
      ty
    })
    .collect::<Vec<_>>();
  
  todo!()
}

스킴의 각 evidence는 lower_ev_ty로 타입으로 로워링됩니다. 이 타입들은 두 가지 역할을 합니다:

• ev_to_ty에서 evidence를 그 타입에 매핑합니다.
• 그 타입을 ev_tys: Vec<Type>로 수집합니다.

lower_ev_ty 거리

드디어 오늘 작업의 핵심에 도착했습니다. 지난번에 배웠듯, 각 evidence는 로워링 과정에서 IR의 항(term)과 연결됩니다. lower_ev_ty는 그 항을 직접 생성하진 않지만, 그 항의 타입을 생성합니다.

해결되지 않은 evidence는 로워링된 IR 항의 함수 파라미터가 됩니다. 파라미터에 어떤 값을 제공할지는 호출자 책임이지만, 우리는 파라미터의 타입을 제공해야 합니다. lower_ev_ty의 시그니처는 소박합니다:

fn lower_ev_ty(
  &self, 
  evidence: ast::Evidence
) -> Type {
  todo!()
}

최종 반환 타입은 evidence 항의 형태를 그대로 반영합니다:

fn lower_ev_ty(
  &self, 
  evidence: ast::Evidence
) -> Type {
  todo!("We have some work before we return that type");

  Type::prod(Row::Closed(vec![
    concat,
    branch,
    Type::prod(Row::Closed(vec![
      prj_left, 
      inj_left
    ])),
    Type::prod(Row::Closed(vec![
      prj_right, 
      inj_right
    ])),
  ]))
}

이 Type을 만들기 전에, 도와줄 Type들의 슈퍼팀을 구성해야 합니다:

let ast::Evidence::RowEquation { left, right, goal } = evidence;

let left = self.lower_row_ty(left);
let (left_prod, left_sum) = (
  Type::prod(left.clone()), 
  Type::sum(left));

let right = self.lower_row_ty(right);
let (right_prod, right_sum) = (
  Type::prod(right.clone()), 
  Type::sum(right));

let goal = self.lower_row_ty(goal);
let (goal_prod, goal_sum) = (
  Type::prod(goal.clone()), 
  Type::sum(goal));

evidence 안의 각 로우를 로워링합니다. 그리고 각 로우를 Prod와 Sum 타입으로 모두 감쌉니다. 이렇게 내려진 로우들은 evidence의 각 구성요소를 타이핑하는 데 쓰이며, 먼저 concat부터 시작합니다:

let concat = 
  Type::funs(
    [ 
      left_prod.clone(), 
      right_prod.clone()
    ], 
    goal_prod.clone());

아주 직관적입니다. concat은 left_prod와 right_prod를 받아 goal_prod를 반환합니다. 아마 left_prod와 right_prod를 이어붙이겠지만, 지금은 그게 중요한 게 아닙니다. branch는 더 복잡합니다:

let branch = {
  let a = TypeVar(0);
  Type::ty_fun(
    Kind::Type,
    Type::funs(
      [
        Type::fun(left_sum.clone().shifted(), Type::Var(a)),
        Type::fun(right_sum.clone().shifted(), Type::Var(a)),
        goal_sum.clone().shifted(),
      ],
      Type::Var(a),
    ))
};

branch가 복잡한 이유는, 두 함수를 입력으로 받고 세 번째 함수를 반환하기 때문입니다. 입력들의 타입이 복잡해질 뿐 아니라, 세 함수가 모두 동일한 타입을 반환하도록 보장해야 합니다. 하지만 반환 타입을 미리 알 수 없으므로, 세 함수가 같은 타입을 반환하게 만들기 위해 타입 변수를 도입할 수밖에 없습니다.

이런 형태의 ty_fun 사용은 이전에는 본 적이 없습니다. 이전에는 TypeScheme가 타입 변수를 전부 모아줬기 때문에, Type의 최상위에서만 ty_fun을 썼습니다. 하지만 branch처럼 다른 Type 내부에 ty_fun이 들어가면, 주의할 점이 있습니다. 이는 우리가 타입에서 드브루인 인덱스(De Bruijn Indices)를 사용하기 때문입니다.

드브루인 인덱스를 사용할 때, 어떤 타입을 ty_fun 안에 넣으면 그 안의 인덱스를 조정해야 합니다. 이제 인덱스가 자신의 바인딩 ty_fun에 도달하려면 ty_fun 노드 하나를 더 건너뛰어야 하기 때문입니다. 이 조정은 shifted()가 담당하며, 각 타입 변수를 1씩 증가시킵니다.

따라서 branch의 타입에 포함된 각 타입은 ty_fun을 고려해 shift합니다. branch를 처리하고 나면, prj_left와 inj_left는 훨씬 단순합니다:

let prj_left = 
  Type::fun(goal_prod.clone(), left_prod);
let inj_left = 
  Type::fun(left_sum, goal_sum.clone());

prj_left는 goal_prod를 받아 left_prod로 투영(project)합니다. inj_left는 반대로 left_sum을 받아 더 큰 goal_sum으로 주입(inject)합니다. 대응되는 prj_right와 inj_right는 대칭성을 보입니다:

let prj_right = 
  Type::fun(goal_prod, right_prod);
let inj_right = 
  Type::fun(right_sum, goal_sum);

이제 슈퍼팀의 모든 멤버가 모였으니, 최종 evidence 타입을 조립할 수 있습니다:

fn lower_ev_ty(
  &self, 
  evidence: ast::Evidence
) -> Type {
  // ...We did some work before we return that type
  Type::prod(Row::Closed(vec![
    concat,
    branch,
    Type::prod(Row::Closed(vec![
      prj_left, 
      inj_left
    ])),
    Type::prod(Row::Closed(vec![
      prj_right, 
      inj_right
    ])),
  ]))
}

이는 예시 레이아웃과 정확히 대응됩니다. Evidence는 로우에 대해 수행하고 싶은 각 연산마다 함수가 하나씩 들어 있는 큰 튜플입니다. 테스트도 추가하겠지만, 틀렸다면 이렇게까지 직접적으로 대응되진 않았을 겁니다.

lower_ty_scheme로 돌아가기

lower_ty_scheme로 돌아오면, evidence 타입들을 사용해 전체 항의 타입에 파라미터를 추가합니다:

fn lower_ty_scheme(scheme: ast::TypeScheme) -> LoweredTyScheme {
  // We saw this earlier
  let ev_tys = ...;
  
  // But now we use it to add params to our lower_ty.
  let evident_lower_ty = Type::funs(ev_tys, lower_ty);
  todo!()
}

여기가 바로 Evidence를 “전달”하는 부분입니다. AST에서는 evidence가 암묵적으로 전달되지만, 로워링에서는 더 명시적으로 처리하여, 해결되지 않은 evidence 각각을 함수 파라미터로 바꿉니다. 함수 파라미터 타입의 순서에 주의해야 합니다. 호출자가 evidence 항을 올바른 타입에 전달하려면, scheme.evidence와 동일한 순서여야 합니다.

evidence 파라미터까지 모두 포함한 타입에는 이제 변수들에 대한 TyFun도 필요합니다:

let bound_lower_ty = kinds
  .iter()
  .fold(evident_lower_ty, |ty, kind| Type::ty_fun(*kind, ty));

지난번과 크게 다르진 않지만 이제 Kind가 중요합니다. 따라서 kinds 벡터를 사용해 각 TyFun이 어떤 Kind를 가져야 하는지 결정합니다. 마지막으로 lower에서 필요한 모든 것을 패키징해 반환합니다:

LoweredTyScheme {
  scheme: bound_lower_ty,
  lower_types: lower,
  kinds,
  ev_to_ty
}

lower로 돌아가기

lower로 돌아오자마자 ev_to_ty 필드를 바로 활용합니다:

fn lower(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 = 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();
  
  todo!()
}

스킴의 각 evidence는 Var를 하나씩 갖게 됩니다. 다른 Var들과 달리, 이 Var들은 어떤 ast::Var 인스턴스에도 연결되지 않습니다. IR에만 존재하는 고유한 변수입니다. 이는 VarSupply에 새로운 함수 supply가 필요하다는 뜻이기도 합니다.

supply는 supply_for와 달리 ast::Var 없이도 새로운 Var를 생성합니다. 구현은 여전히 흥미롭지 않지만, 전체 코드에서 확인할 수 있습니다.

생성된 Var들은 params 벡터로 모이고, Evidence에서 Var로의 맵에도 저장됩니다. params는 최종 IR 항에 evidence마다 Fun 노드를 추가하는 데 쓰입니다. ev_to_var는 AST를 로워링하는 동안 특정 evidence를 참조할 때 사용할 변수를 알려줍니다. 그리고 ev_to_var로 새롭고 개선된 LowerAst를 구성합니다:

let mut lower_ast = LowerAst {
  supply,
  types: lowered_scheme.lower_types,
  ev_to_var,
  solved: vec![],
  row_to_ev: out.row_to_ev,
  branch_to_ret_ty: out.branch_to_ret_ty,
};
let ir = lower_ast.lower_ast(out.typed_ast);

LoweredTyScheme처럼 이것도 새로운 필드가 몇 개 있습니다. ev_to_var는 이미 익숙하죠. solved는 lower_ast 동안 해결된 evidence를 위해 사용할 것입니다. 이에 대해서는 다음 글에서 더 다룹니다.