낮춰진 로우의 심장

언어 만들기

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

이 글은 이전 글에서 이어서 로우를 lowering(낮추기)합니다.

지난번에는 lower_ty_scheme를 로우를 지원하도록 업그레이드했고, 그 증거(evidence)를 사용해 lower_ast를 어떻게 안내할지 살펴봤습니다. 이번에는 로우를 lowering하는 핵심으로 들어갑니다: 증거 항(evidence term)을 생성하고 적용하는 것입니다.

우리가 부분적으로 업데이트된 lower에서 멈췄던 것을 떠올려 봅시다:

rust
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();
  
  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);

  todo!()
}

lower_ast 안으로 들어가기 직전까지 와 있습니다. 하지만 먼저 LowerAst에 새 필드가 몇 개 생겼습니다. 하나는 우리가 이미 알고 있는(ev_to_var) 것이고, 다른 하나는 아직 모르는(solved) 것입니다. lower_ast를 업데이트하면서 solved가 어떻게 쓰이는지 알게 될 겁니다.

빠른 복습

우리는 Row AST 노드들을 lowering할 것이니, 그 노드들이 무엇인지 다시 상기해 봅시다. 먼저 Label과 Unlabel 노드가 한 쌍입니다:

rust
enum Ast<V> {
  // ... our base nodes
  // Label a node turning it into a singleton row
  Label(NodeId, Label, Box<Self>),
  // Unwrap a singleton row into it's underlying value
  Unlabel(NodeId, Box<Self>, Label),
  // ...
}

이 노드들은 일반 AST를 싱글턴 로우(singleton row)로 넣었다 빼는 역할을 합니다. Label은 동반된 Label을 사용해 Ast를 감싸 로우로 만듭니다.

Label(노드가 아니라 타입)은 단지 String의 별칭입니다:

rust
type Label = String;

Unlabel은 Label의 짝입니다. 싱글턴 로우를 받아서, 지정된 필드의 값을 꺼내어 원래 값을 돌려줍니다.

Label과 Unlabel 다음으로, 곱(product) 로우 타입을 위한 노드를 봅시다:

rust
enum Ast<V> {
  // ...
  // Concat two products
  Concat(NodeId, Box<Self>, Box<Self>),
  // Project a product into a sub product
  Project(NodeId, Direction, Box<Self>),
  // ...
}

Concat은 두 개의 곱 로우를 받아 더 큰 곱으로 합칩니다. 이 노드는 레코드를 만드는 방식입니다. Label과 결합하면 { x: 3, y: 42 } 같은 레코드를 Ast로 다음과 같이 표현할 수 있습니다:

rust
Concat(
  ...,
  Label(..., "x", Int(3)),
  Label(..., "y", Int(42))
)

반대로 Project는 레코드를 분해합니다. 큰 레코드를 받아 그 부분집합(sub product)을 반환합니다. { x: 3, y: 42 }로 돌아가면, Project는 { x: 3 }, { y: 42 }, {}, 심지어 { x: 3, y: 42 }도 반환할 수 있습니다. Project의 출력은 타입 추론이 결정합니다.

마지막으로 합(sum) 로우 타입을 위한 노드 두 개가 있습니다. 하나는 도입(introduce)이고 하나는 분해(destruct)입니다:

rust
enum Ast<V> {
  // ...
  // Inject a value into a sum type
  Inject(NodeId, Direction, Box<Self>),
  // Branch on a sum type to two handler functions
  Branch(NodeId, Box<Self>, Box<Self>),
  // ...
}

Inject는 로우를 받아 더 큰 합 타입으로 넣습니다. Project처럼 더 큰 합 타입은 타입 추론에 의존합니다. 예를 들어 다음 Ast:

rust
Inject(Label("A", Int(2)))

는 다음과 같은 다양한 합 타입을 가질 수 있습니다:

• enum { A(Int) }
• enum { A(Int), B(Int) }
• enum { A(Int), B(Int), C(Int) }
• …

Inject의 짝인 Branch는 합 타입을 분해합니다. Branch는 더 작은 합 타입을 처리하는 두 함수(handler function)를 받아, 더 큰 합 타입을 받는 함수로 합칩니다. 예를 들어 enum { X(Int), Y(Int) } 타입의 값이 있다면 다음 항(term)으로 분기할 수 있습니다:

rust
Branch(
  ...,
  Fun(..., x, Unlabel(..., Var(x), "X")),
  Fun(..., y, Unlabel(..., Var(y), "Y")))

이 분기는 두 함수를 받습니다. 각각은 입력으로 enum { X(Int) }와 enum { Y(Int) }를 받고, 둘 다 Int를 반환합니다. Branch는 이를 enum { X(Int), Y(Int) } -> Int 함수로 결합합니다.

타입 체크에서 로우 노드에 대한 메타데이터를 두 개의 새 출력으로 유지합니다: row_to_ev와 branch_to_ret_ty입니다:

rust
struct TypesOutput {
  row_to_ev: HashMap<NodeId, Evidence>,
  branch_to_ret_ty: HashMap<NodeId, Type>,
}

row_to_ev는 Ast의 각 로우 노드에 대한 엔트리를 가지며, 타입 체크 중 해당 노드에 대해 풀린 로우 결합(row combination) 증거를 제공합니다. branch_to_ret_ty는 비슷하지만 Branch 노드에 대해서만 엔트리를 가지며 각 분기의 반환 타입을 제공합니다.

lower_ast로

lower_ast는 평소와 같은 형태입니다:

rust
impl LowerAst {
  fn lower_ast(
    &mut self, 
    ast: Ast<TypedVar>
  ) -> IR {
    match ast {
      // All our cases for the base AST...
    }
  }
}

Label과 Unlabel부터 케이스를 추가해 봅시다:

rust
Ast::Label(_, _, body) => self.lower_ast(*body),
Ast::Unlabel(_, body, _) => self.lower_ast(*body),

이는 간단합니다. 라벨을 지우고 본문을 lowering합니다. Concat부터 본격적으로 시작합니다:

rust
Ast::Concat(id, left, right) => {
  let param = self
    .row_to_ev
    .get(&id)
    .cloned()
    .map(|ev| self.lookup_ev(ev))
    .expect("ICE: Concat AST node lacks an expected evidence");

  let concat = IR::field(IR::Var(param), 0);
  let left = self.lower_ast(*left);
  let right = self.lower_ast(*right);
  IR::app(IR::app(concat, left), right)
}

meta 필드가 Option<ast::Evidence> 인스턴스였음을 기억하세요. 타입 체크 후에는 항상 Some이므로 존재한다고 가정할 수 있습니다. lookup_ev를 호출하면 Var를 반환합니다. lookup_ev 구현은 잠시 뒤에 살펴봅니다.

lookup_ev가 준 Var는 lowering된 증거 항이라서 lower_ev_ty에서 본 큰 곱 타입을 가집니다. 그 곱 타입의 첫 번째 필드가 concat 연산임을 알고 있습니다. 변수에 0번 필드 접근을 감싸서 concat을 꺼냅니다. 그리고 lowering된 left와 right를 증거의 concat 항에 적용(apply)합니다.

즉, Concat 노드를 사실상 지웠습니다. Ast의 명시적 노드였던 것이 IR의 평범한 함수 호출로 바뀝니다. 이렇게 하면 컴파일해야 할 언어가 줄어들고, 로우 실행도 쉬워집니다. 저는 Concat 노드를 어떻게 실행할지 모르지만, 컴퓨터는 Lisp 머신 시절부터 함수를 실행해 왔습니다.

lookup_ev 살펴보기

이제 lookup_ev를 들여다보며 증거에 대한 Var를 어떻게 얻는지 이해해 봅시다:

rust
770| fn lookup_ev(&mut self, ev: Evidence) -> Var {
...|   // Lookup the variable for our evidence.
835| }

별다를 게 없어 보이죠. 그런데 잠깐, 항상 저 줄 번호가 있었나요? 왜 이렇게 줄이 많죠? lookup 함수일 뿐 아닌가요?

lookup_ev는 먼저 ev_to_var에서 ev를 조회해서 이미 변수가 있는지 확인합니다:

rust
fn lookup_ev(&mut self, ev: Evidence) -> Var {
  self
    .ev_to_var
    .entry(ev)
    // ... more entry work
}

풀리지 않은(unsolved) 증거는 lower_ty_scheme에서의 작업 덕분에 항상 타입 스킴에 등장하고 이미 변수를 갖습니다. 하지만 풀린(solved) 증거는 타입 스킴에 나타나지 않으므로, 처음 마주칠 때 변수가 없습니다. 더 나쁜 점은, 증거가 풀렸기 때문에 단지 변수만이 아니라 실제 IR 항(term)을 생성해야 한다는 의무가 생긴다는 것입니다.

우리는 이것을 lookup_ev에서 지연(lazy) 방식으로 합니다. 풀린 증거에 대한 항을 생성할 때, 그것을 변수에 바인딩하고 그 변수를 ev_to_var에 저장해 이후 재사용합니다. Rust의 Entry API가 이를 쉽게 해줍니다:

rust
self
  .ev_to_var
  .entry(ev)
  .or_insert_with_key(|ev| {
    // We can generate our evidence here 
    // and it gets cached for free.
  })

or_insert_with_key 내부에서는 ev가 풀린 증거라고 가정합니다. 그렇지 않다면 스킴에 등장했어야 하며 이미 변수가 있어야 합니다:

rust
let Evidence::RowEquation {
  left: ast::Row::Closed(left),
  right: ast::Row::Closed(right),
  goal: ast::Row::Closed(goal),
} = ev
else {
  panic!("ICE: Unsolved evidence appeared in AST that wasn't in type scheme");
};

또한 생성될 증거 항을 위한 새 변수를 하나 만듭니다:

rust
let param = self.supply.supply();

그 다음 로우에 대한 메타데이터를 계산해야 합니다. lowering된 로우는 라벨 대신 인덱스를 사용합니다. left와 right가 결합되어 goal을 만든다는 것은 알지만, left(또는 right)의 어떤 인덱스가 goal의 어떤 인덱스로 매핑되는지는 아직 모릅니다.

순진하게는 goal이 [left[0], left[1], ..., right[0], right[1], ...] 형태일 거라 생각할 수 있습니다. 하지만 그렇지 않습니다. 로우는 필드(라벨) 기준으로 사전식(lexicographic) 정렬되기 때문입니다. lowering 단계에서는 필드를 유지하지 않지만, 사라지기 전에 필드를 이용해 left, right, goal 사이의 인덱스 매핑을 계산합니다. 이 매핑은 goal.fields를 순회하면서 구합니다:

rust
let goal_indices = goal
  .fields
  .iter()
  .map(|field| {
    left
      .fields
      .binary_search(field)
      .map(RowIndex::Left)
      .or_else(|_| {
        right
          .fields
          .binary_search(field)
          .map(RowIndex::Right)
      })
      .expect("ICE: Invalid solved row combination.")
  })
  .collect::<Vec<_>>();

goal의 각 필드에 대해, left 또는 right에서 해당 필드를 찾습니다. 무엇을 찾았는지 기억하기 위해 래퍼 enum RowIndex를 씁니다:

rust
enum RowIndex {
  Left(usize),
  Right(usize),
}

fields가 정렬되어 있으니 .binary_search로 인덱스를 찾을 수 있습니다. 결과적으로 goal_indices는 Vec<RowIndex>인데, 사실상 Map<usize, RowIndex>처럼 생각할 수 있습니다. goal의 각 인덱스를 구성 요소 로우의 인덱스로 매핑합니다. 그런 다음 각 로우의 값 타입을 lowering합니다:

rust
let left_values = self.types.lower_closed_row_ty(left.clone());
let right_values = self.types.lower_closed_row_ty(right.clone());
let goal_values = self.types.lower_closed_row_ty(goal.clone());

이 모든 것이 새 헬퍼 구조체 LowerSolvedEv를 구성합니다:

rust
let lower_solved_ev = LowerSolvedEv {
  supply: &mut self.supply,
  left: left_values,
  right: right_values,
  goal: goal_values,
  goal_indices,
};

여기엔 중요한 메서드가 하나 있습니다: lower_ev_term입니다.

중요한 메서드 하나: lower_ev_term

lower_ev_term은 lower_ev_ty의 짝입니다. LowerSolvedEv를 만들 때 사용한 증거에 대한 IR 항을 생성합니다:

rust
fn lower_ev_term(mut self) -> IR {
  IR::tuple([
    self.concat(),
    self.branch(),
    IR::tuple([self.prj_left(), self.inj_left()]),
    IR::tuple([self.prj_right(), self.inj_right()]),
  ])
}

익숙해 보이길 바랍니다. lower_ev_ty의 결과와 거의 정확히 평행 구조인데, Type을 만드는 대신 IR을 만듭니다.

concat부터 시작

각 연산이 어떻게 생성되는지 concat부터 봅시다:

rust
fn concat(&mut self) -> IR {
  let vars = self.make_vars([self.left_prod(), self.right_prod()]);
  todo!()
}

lower_ev_ty에서 concat은 left와 right 튜플을 받아 goal 튜플을 반환하는 함수임을 알고 있습니다. 그 함수를 만들기 위한 첫 단계는 함수 파라미터용 변수를 만드는 것입니다. 몇 개의 헬퍼 함수가 이 일을 도와줍니다. 하나씩 보겠습니다. 먼저 left_prod입니다.

left_prod는 left의 Type들로부터 Type::Prod를 만듭니다:

rust
fn left_prod(&self) -> Type {
  Type::prod(Row::Closed(self.left.clone()))
}

그냥 타이핑을 줄이기 위한 함수입니다. 예상대로 right_prod도 right에 대해 같은 일을 합니다:

rust
fn right_prod(&self) -> Type {
  Type::prod(Row::Closed(self.right.clone()))
}

작은 비밀 하나. lower_ev_term을 끝내기 전까지 goal_prod, left_sum, right_sum, goal_sum도 보게 될 겁니다. 각각 무엇을 만드는지는 독자의 연습 문제로 남겨둡니다.

이 둘은 금방 끝냈습니다. 마지막 헬퍼는 make_vars입니다. 보통은 코드를 단순하게 유지하려고 합니다. 저는 단순한 사람입니다. 이 블로그가 폭발적으로 성공하지 않았다면, 저는 GitHub 이슈에서 나무로 가구를 만들고 있었을 겁니다.

그러니까, 다음 코드를 가볍게 보여드리는 게 아닙니다:

rust
fn make_vars<const N: usize>(&mut self, tys: [Type; N]) -> [Var; N] {
  tys.map(|ty| {
    let id = self.supply.supply();
    Var::new(id, ty)
  })
}

make_vars는 var를 만들 뿐 아니라 Rust의 좀 더 고급 기능인 Const Generics도 사용합니다. Const Generics는 여기서 가볍게만 짚겠습니다. 더 궁금하다면 링크에서 자세히 읽어보세요.

여기서 하는 일은 임의 크기의 배열 [Type; N]을 받아 같은 크기의 배열 [Var; N]을 반환하게 해주는 것입니다. Vec로도 쉽게 구현할 수 있지만, 배열은 패턴 매칭이 가능하고 Vec은 불가능하기 때문에 이렇게 합니다.

구현 자체는 단순합니다. 각 타입마다 변수를 하나 생성해 반환합니다. 이제 concat으로 돌아가 함수를 생성합니다:

rust
IR::funs(vars.clone(), {
  todo!()
})

IR::funs는 IR::fun과 비슷하지만 여러 변수를 지원합니다. 만든 vars를 넘겨 두 개의 파라미터를 갖는 함수를 만듭니다. 함수 본문은 입력을 이어붙여(concatenate) 만든 튜플이 될 것입니다. 튜플을 만들기 전에 각 인덱스에 어떤 요소가 들어갈지 결정해야 합니다:

rust
let [left, right] = vars;
let mut elems = self.goal_indices.iter().map(|row_index| match row_index {
  RowIndex::Left(i) => unwrap_prj(*i, self.left.len(), left.clone()),
  RowIndex::Right(i) => unwrap_prj(*i, self.right.len(), right.clone()),
});

튜플은 goal 로우를 나타내므로 goal_indices를 순회하며 요소를 결정할 수 있습니다. 각 인덱스에서 row_index에 따라 left 또는 right 변수의 요소를 접근합니다. unwrap_prj는 싱글턴 로우 관련 엣지 케이스를 처리하면서 IR::Field를 만드는 또 다른 헬퍼입니다:

rust
fn unwrap_prj(
  index: usize, 
  len: usize, 
  prod: Var
) -> IR {
  unwrap_single(len, prod, |ir| IR::field(ir, index))
}

그리고 unwrap_single은 다음과 같습니다:

rust
fn unwrap_single(
  len: usize, 
  var: Var, 
  else_fn: impl FnOnce(IR) -> IR
) -> IR {
  if len == 1 {
    IR::Var(var)
  } else {
    else_fn(IR::Var(var))
  }
}

이 단계에서 라벨을 지워버리기 때문에, 싱글턴 로우는 그 내부 값과 구분되지 않게 됩니다. Ast::Label("x", Ast::Int(3))는 IR::Int(3)으로 lowering됩니다. 그러면 projection에 문제가 생깁니다. lowering된 싱글턴 로우의 필드를 접근하려고 하면 터집니다.

다행히 논문이 이미 이 문제를 예상했습니다. 로우에 접근할 때마다 먼저 싱글턴인지 확인하고, 싱글턴이면 필드 접근 대신 값을 직접 반환합니다. unwrap_single이 이 로직을 처리하고, unwrap_prj는 IR::field로 항상 호출하도록 감싼 래퍼입니다.

이제 elems는 필드 접근(또는 싱글턴이면 값)을 순회하는 이터레이터입니다. 이를 이용해 최종 goal 튜플을 만듭니다:

rust
if self.goal_indices.len() == 1 {
  elems.next().unwrap()
} else {
  IR::tuple(elems)
}

하지만 인덱싱뿐 아니라 튜플 구성에서도 싱글턴을 고려해야 합니다. goal이 싱글턴 로우라면 튜플을 만들지 않고 단일 값을 그대로 반환합니다. 그렇지 않다면 elems를 IR::tuple에 넘겨 제대로 된 튜플을 만듭니다.

이 모든 결과로 concat에 대해 생성되는 IR은 대략 다음과 같은 모양입니다:

rust
// We aren't super worried about the details.
// We just want a sense of the structure
let left = Var(...);
let right = Var(...);
IR::Fun(left, IR::Fun(right, IR::Tuple(vec![
  IR::Field(IR::Var(left), 0),
  IR::Field(IR::Var(right), 0),
  IR::Field(IR::Var(right), 1),
  IR::Field(IR::Var(left), 1)
])

두 입력 로우 left와 right에 맞춤화된 스프레드 연산자를 만든 셈입니다.

branch 생성에 착수하기

다음은 branch입니다. 높은 수준의 형태는 concat과 비슷하지만 구현은 더 복잡합니다.

rust
fn branch(&mut self) -> IR {
  let left_sum = self.left_sum().shifted();
  let right_sum = self.right_sum().shifted();
  let goal_sum = self.goal_sum().shifted();
  let ret_ty = Type::Var(TypeVar(0));

  todo!()
}

branch의 첫 단계는 필요한 타입들을 준비하는 것입니다. 각 로우에 대한 Sum 타입을 만듭니다. lower_ev_ty에서 branch는 반환 타입을 위한 타입 변수를 도입한다는 것을 기억하세요. TyFun을 도입하므로 그 안에 중첩된 타입들은 shift해야 합니다. 필요한 변수를 도입합니다:

rust
let vars = self.make_vars([
  Type::fun(left_sum.clone(), ret_ty.clone()),
  Type::fun(right_sum.clone(), ret_ty.clone()),
  goal_sum,
]);

concat처럼 branch도 두 개를 받아 세 번째를 반환한다고 생각할 수 있습니다. 다만 여기서 두 개는 함수입니다. 또한 커링(currying)을 지원하기 때문에, 함수를 반환하는 것과 파라미터를 하나 더 받는 것은 동일한 IR 항입니다:

rust
// Returning a function.
IR::Fun(left, IR::Fun(right, IR::Fun(goal, <body>)))
// Taking an extra parameter.
IR::Fun(left, IR::Fun(right, IR::Fun(goal, <body>)))

branch를 두 파라미터를 받아 값을 반환한다고 생각하겠지만, 실제 항은 세 값을 받고 ret_ty를 반환하는 모양이 됩니다. vars가 준비되면 구조를 쌓기 시작합니다:

rust
IR::ty_fun(
  Kind::Type,
  IR::funs(vars.clone(), {
    todo!()
  }),
)

반환 타입을 바인딩하기 위해 ty_fun을 도입합니다. branch를 어떻게 lowering하는지 우리가 제어하므로, branch에 타입을 적용하는 경우만 존재함을 압니다. 따라서 반환 타입은 Kind::Type이라고 가정해도 안전합니다. 사실 TypeScheme을 lowering할 때만 Kind::Row 변수를 만들 수 있습니다.

궁극적으로 우리는 goal_sum -> ret_ty 함수를 만들어야 합니다. ret_ty를 얻기 위한 수단은 많지 않습니다. left_sum -> ret_ty인 left를 호출하거나, right_sum -> ret_ty인 right를 호출하는 것뿐입니다. 문제는 goal_sum 타입의 값이 left_sum이나 right_sum 타입이 아니라는 점입니다.

이를 해결하기 위해 새 Case 구문을 사용합니다. branch는 goal_sum 값을 case로 분기합니다. 각 Case의 Branch에서 값을 left_sum 또는 right_sum으로 다시 감싸고 해당 함수를 호출합니다. concat의 elems처럼 각 Branch는 goal_indices를 사용해 left를 호출할지 right를 호출할지 결정합니다:

rust
let [left_var, right_var, goal_var] = vars;
let goal_len = self.goal.len();
let mut branches = self
  .goal_indices
  .clone()
  .into_iter()
  .map(|row_index| {
    todo!()
  });

Field가 아니라 Branch를 구성하므로 RowIndex에서 더 많은 메타데이터가 필요합니다:

rust
let (i, ty, len, var, sum) = match row_index {
  RowIndex::Left(i) => (
    i,
    self.left[i].clone().shifted(),
    self.left.len(),
    left_var.clone(),
    left_sum.clone(),
  ),
  RowIndex::Right(i) => (
    i,
    self.right[i].clone().shifted(),
    self.right.len(),
    right_var.clone(),
    right_sum.clone(),
  ),
};

RowIndex로부터 다섯 가지를 결정합니다:

• left 또는 right로의 인덱스
• 해당 인덱스의 타입
• left 또는 right의 길이(unwrap용)
• 호출해야 하는 함수를 담고 있는 변수
• left 또는 right의 sum 타입

모든 것을 모았으면 Branch를 만들 수 있습니다:

rust
let [case_var] = self.make_vars([ty]);
IR::branch(case_var.clone(), {
  IR::app(
    IR::Var(var),
    unwrap_single(
      len, 
      case_var, 
      |ir| IR::tag(sum, i, ir)),
  )
})

goal_sum에서 나온 값은 브랜치 안에서 case_var로 바인딩됩니다. unwrap_single을 통해 (싱글턴 엣지 케이스를 처리하며) case_var를 sum, i, len을 사용해 새로운 태그 값으로 감싼 후 선택된 함수 var에 적용합니다. 이렇게 만든 branches 이터레이터로 goal_var에 대한 Case를 구성합니다:

rust
let mut branches = self
  .goal_indices
  .clone()
  .into_iter()
  .map(|row_index| {
    // ... excluded for space
  });
if goal_len == 1 {
  IR::app(branches.next().unwrap().as_fun(), IR::Var(goal_var))
} else {
  IR::case(ret_ty, IR::Var(goal_var), branches)
}

여기서도 goal이 싱글턴일 때를 고려해야 합니다. 싱글턴이면 case를 만들 수 없습니다. 싱글턴 goal은 태그 값이 아니라 그냥 값이기 때문입니다. 대신 첫(이자 유일한) 브랜치를 함수로 바꾸고 goal_var를 직접 넘깁니다.

이는 동작함을 확신할 수 있습니다. goal이 싱글턴이면 유일한 브랜치가 반드시 unwrap된 값을 받아야 합니다. goal이 싱글턴이 되는 경우는 다음뿐입니다:

• left가 싱글턴이고 right가 비어 있음
• right가 싱글턴이고 left가 비어 있음

두 경우 모두 브랜치는 싱글턴 Sum 타입으로 작업합니다. goal이 싱글턴이 아니라면 goal_var와 branches로 정상적으로 case를 구성합니다. 결국 다음과 같은 항을 만들게 됩니다:

rust
let left = Var(...);
let right = Var(...);
let goal = Var(...);
// Don't worry about the types here.
let case = Var(...);
IR::TyFun(Kind::Type,
  IR::Fun(left, IR::Fun(right, IR::Fun(goal,
    IR::Case(ret_ty, goal, vec![
      // Pretend branch is a tuple struct, so it's easier to write.
      Branch(case, 
        IR::App(IR::Var(left), IR::Tag(left_sum, 0, IR::Var(case)))),
      Branch(case, 
        IR::App(IR::Var(right), IR::Tag(right_sum, 0, IR::Var(case)))),
      Branch(case, 
        IR::App(IR::Var(right), IR::Tag(right_sum, 1, IR::Var(case)))),
      Branch(case, 
        IR::App(IR::Var(left), IR::Tag(left_sum, 1, IR::Var(case)))),
    ])))))

prj_left와 prj_right 둘러보기

휴, 많았습니다. 제발 prj와 inj는 더 단순하길 바랍니다. prj_left부터 봅시다:

rust
696| fn prj_left(&mut self) -> IR {
...|   todo!()
710| }

줄 번호가 다시 나왔네요. 이번에는 더 친절해 보이긴 합니다. 안을 보죠:

rust
let [goal] = self.make_vars([self.goal_prod()]);
let left_indices = self.left_indices();
IR::fun(goal.clone(), {
  if self.left.len() == 1 {
    unwrap_prj(left_indices[0], self.goal.len(), goal)
  } else {
    IR::tuple(
      left_indices
        .into_iter()
        .map(|i| unwrap_prj(i, self.goal.len(), goal.clone())),
    )
  }
})

새로운 게 없네요—잠깐, left_indices는 처음 보는데요?

… 젠장.

prj_left는 goal 튜플을 left 튜플로 바꾸는 함수입니다. 이를 위해 goal 튜플의 어떤 인덱스가 left에서 왔는지, 그리고 그것이 goal에서 어디에 놓였는지 알아야 합니다.

goal_indices는 goal의 각 인덱스를 구성 요소의 인덱스로 매핑합니다. left_indices는 그 반대입니다. left_indices는 left의 모든 인덱스를 goal에서의 인덱스로 매핑합니다. 이때는 모든 인덱스가 goal 안의 인덱스이므로 RowIndex 없이 표현할 수 있습니다.

rust
fn left_indices(&self) -> Vec<usize> {
  let mut left = self
    .goal_indices
    .iter()
    .enumerate()
    .filter_map(|(goal_index, row_index)| match row_index {
      RowIndex::Left(left_indx) => Some((*left_indx, goal_index)),
      _ => None,
    })
    .collect::<Vec<_>>();
  left.sort_by_key(|(key, _)| *key);
  left.into_iter().map(|(_, goal_index)| goal_index).collect()
}

이 코드는 goal_indices를 순회하며 RowIndex::Left인 것만 뽑고, left 인덱스로 정렬한 뒤 goal 인덱스 벡터를 반환합니다. 만약 goal_indices가 vec![RowIndex::Left(0), RowIndex::Right(0), RowIndex::Left(2), RowIndex::Left(1)]라면, left_indices는 vec![0, 3, 2]가 됩니다. 이것이 유일한 새 헬퍼이고, 이제 prj_left의 핵심을 말할 수 있습니다:

rust
IR::fun(goal.clone(), {
  if self.left.len() == 1 {
    unwrap_prj(left_indices[0], self.goal.len(), goal)
  } else {
    IR::tuple(
      left_indices
        .into_iter()
        .map(|i| unwrap_prj(i, self.goal.len(), goal.clone())),
    )
  }
})

prj_left의 구현은 concat과 많이 닮았습니다. 단일 파라미터 함수로 goal -> left를 매핑합니다. left가 싱글턴이면 튜플을 만들지 않고 goal의 첫 인덱스 접근을 반환합니다. 그렇지 않으면 goal 파라미터에 대한 필드 접근들로 튜플을 구성합니다.

다행히 prj_right에는 더 이상 놀랄 게 없습니다:

rust
fn prj_right(&mut self) -> IR {
  let [goal] = self.make_vars([self.goal_prod()]);
  let right_indices = self.right_indices();
  IR::fun(goal.clone(), {
    if self.right.len() == 1 {
      unwrap_prj(right_indices[0], self.goal.len(), goal)
    } else {
      IR::tuple(
        right_indices
          .into_iter()
          .map(|i| unwrap_prj(i, self.goal.len(), goal.clone())),
      )
    }
  })
}

right_indices가 정확히 무엇인지는 몰라도 left_indices의 반대라는 건 알 수 있습니다. right 로우의 인덱스를 goal의 인덱스로 매핑하는 Vec를 만들겠죠. 나머지는 prj_left와 동일하되 오른쪽입니다.

inj_left와 inj_right 이해하기

마무리는 inj_left와 inj_right입니다. 이 함수들은 left 또는 right 합 타입 값을 goal 합 타입으로 _주입(inject)_합니다. 합 타입을 다루지만 branch와 달리 함수가 아닌 값입니다. 그래도 Case가 필요합니다. 먼저 inj_left입니다:

rust
fn inj_left(&mut self) -> IR {
  let [left_var] = self.make_vars([self.left_sum()]);
  IR::fun(left_var.clone(), {
    let branches = self
      .left_enumerated_values()
      .map(|(i, ty)| {
        let [branch_var] = self.make_vars([ty]);
        IR::branch(branch_var.clone(), {
          unwrap_single(self.goal.len(), branch_var, |ir| {
            IR::tag(self.goal_sum(), i, ir)
          })
        })
      })
      .collect::<Vec<_>>();
    if self.left.len() == 1 {
      IR::app(branches[0].as_fun(), IR::Var(left_var))
    } else {
      IR::case(self.goal_sum(), IR::Var(left_var), branches)
    }
  })
}

inj_left는 left_sum 값을 받는 함수입니다. 그 값에 대해 case 매칭하고 각 브랜치는 태그 값을 풀어 goal 태그 값으로 다시 감쌉니다. 브랜치 생성에는 left_indices뿐 아니라 각 인덱스의 값 타입도 필요합니다. 이것이 left_enumerated_values()의 역할입니다:

rust
fn left_enumerated_values(
  &self
) -> impl Iterator<Item = (usize, Type)> {
  self.left_indices()
      .into_iter()
      .zip(self.left.clone())
}

이 함수에서 가장 무서운 부분은 반환 타입입니다. 하는 일은 left_indices와 타입들 self.left를 zip하는 것뿐입니다. 이 타입은 브랜치 변수를 올바르게 구성하는 데 필요합니다:

rust
.map(|(i, ty)| {
  let [branch_var] = self.make_vars([ty]);
  IR::branch(branch_var.clone(), {
    unwrap_single(self.goal.len(), branch_var, |ir| {
      IR::tag(self.goal_sum(), i, ir)
    })
  })
})

출력이 또 다른 Sum 타입이므로, 브랜치 본문은 인덱스 i로 태그 값을 만들기만 하면 됩니다. 그리고 branch와 마찬가지로 싱글턴 로우를 처리하며 Case를 구성합니다:

rust
if self.left.len() == 1 {
  IR::app(branches[0].as_fun(), IR::Var(left_var))
} else {
  IR::case(self.goal_sum(), IR::Var(left_var), branches)
}

inj_right는 inj_left의 판박이입니다:

rust
fn inj_right(&mut self) -> IR {
  let [right_var] = self.make_vars([self.right_sum()]);
  IR::fun(right_var.clone(), {
    let branches = self
      .right_enumerated_values()
      .map(|(i, ty)| {
        let [branch_var] = self.make_vars([ty]);
        IR::branch(branch_var.clone(), {
          unwrap_single(self.goal.len(), branch_var, |ir| {
            IR::tag(self.goal_sum(), i, ir)
          })
        })
      })
      .collect::<Vec<_>>();
    if self.right.len() == 1 {
      IR::app(branches[0].as_fun(), IR::Var(right_var))
    } else {
      IR::case(self.goal_sum(), IR::Var(right_var), branches)
    }
  })
}

여기서도 right_enumerated_values가 무엇을 하는지는 상상력에 맡깁니다. 이로써 증거 연산은 모두 끝났습니다. 이제 증거를(매우 큰) IR 항으로 lowering하는 법을 알게 됐습니다.

lookup_ev 마무리하기

긴 여정을 거쳐 lookup_ev로 돌아옵니다:

rust
fn lookup_ev(&mut self, ev: Evidence) -> Var {
  self
    .ev_to_var
    .entry(ev)
    .or_insert_with_key(|ev| {
      // ...previous work
      let term = lower_solved_ev.lower_ev_term();

      todo!()
    })
}

더 좋은 소식은 남은 게 많지 않다는 점입니다:

rust
let ty = self.types.lower_ev_ty(ev.clone());
let var = Var::new(param, ty);
self.solved.push((var.clone(), term));
var

증거의 타입과 VarId param으로 새 변수 var를 만듭니다. 생성된 term과 함께 solved 벡터에 저장하고, ev_to_var의 엔트리로서 var를 반환합니다. 다음에 이 증거를 다시 보더라도 다시 만들 필요가 없습니다.

lower_ast로 돌아와서

스택을 한 번 더 되감으며, lookup_ev 뒤에서 일어난 모든 작업 덕분에 lower_ast를 새롭게 보게 됩니다. 다음 케이스인 Branch로 돌아갑니다:

rust
Ast::Branch(id, left, right) => {
  todo!()
}

Branch는 증거와 반환 타입 둘 다 있습니다. 먼저 증거를 가져와 lowering된 항을 얻습니다:

rust
let param = self
  .row_to_ev
  .get(&id)
  .cloned()
  .map(|ev| self.lookup_ev(ev))
  .expect("ICE: Branch AST node lacks an expected evidence");

다음으로 반환 타입을 가져와 증거에 적용합니다.

rust
let ret_ty = self
  .branch_to_ret_ty
  .get(&id)
  .map(|ty| self.types.lower_ty(ty.clone()))
  .expect("ICE: Branch AST node lacks expected type");
let branch = IR::ty_app(IR::field(IR::Var(param), 1), TyApp::Ty(ret_ty));

branch에 타입을 적용한 다음, left와 right를 lowering해 인자로 넘깁니다:

rust
let left = self.lower_ast(*left);
let right = self.lower_ast(*right);
IR::app(IR::app(branch, left), right)

Branch 케이스는 여기까지입니다. 다음은 Project입니다:

rust
Ast::Project(id, direction, body) => {
  let param = self
    .row_to_ev
    .get(&id)
    .cloned()
    .map(|ev| self.lookup_ev(ev))
    .expect("ICE: Project AST node lacks an expected evidence");

  let term = self.lower_ast(*body);
  let direction_field = match direction {
    ast::Direction::Left => 2,
    ast::Direction::Right => 3,
  };
  let prj_direction = 
    IR::field(
      IR::field(
        IR::Var(param), 
        direction_field), 
      0);
  IR::app(prj_direction, term)
}

concat과 branch와 같은 아이디어입니다. 다만 Project에는 Left 또는 Right 방향이 있습니다. 방향에 따라 증거 항의 두 번째 또는 세 번째 요소를 꺼내야 합니다. 그 다음에는 항상 인덱스 0을 접근해 prj를 얻습니다.

Inject도 동일하지만 마지막에 0 대신 1을 꺼냅니다:

rust
Ast::Inject(id, direction, body) => {
  let param = self
    .row_to_ev
    .get(&id)
    .cloned()
    .map(|ev| self.lookup_ev(ev))
    .expect("ICE: Inject AST node lacks an expected evidence");

  let term = self.lower_ast(*body);
  let direction_field = match direction {
    ast::Direction::Left => 2,
    ast::Direction::Right => 3,
  };
  let inj_direction = 
    IR::field(
      IR::field(
        IR::Var(param), 
        direction_field),
      1);
  IR::app(inj_direction, term)
}

영웅의 귀환

이것으로 lower_ast의 새 케이스는 모두 끝났습니다. 이제 lower로 돌아가 추가한 것들을 다듬고 마무리하면 됩니다.

rust
fn lower(
  out: TypesOutput
) -> (IR, Type) {
  // ...Everything up to lower_ast
  let ir = lower_ast.lower_ast(ast);
  let solved_ir = lower_ast
    .solved
    .into_iter()
    .fold(ir, |ir, (var, solved)| IR::local(var, solved, ir));
}

lower_ast 동안 우리가 해결한 각 증거는 로컬 변수로 바인딩됩니다. 해결되지 않은 증거는 함수 파라미터가 됩니다:

rust
let param_ir = params
  .into_iter()
  .rfold(solved_ir, |ir, var| IR::fun(var, ir));

마지막으로 항을 타입 함수들로 감쌉니다:

rust
let bound_ir = lowered_scheme
  .kinds
  .into_iter()
  .fold(param_ir, |ir, kind| IR::ty_fun(kind, ir));

이제 Kind가 두 개이므로 더 주의해야 합니다. lowered_scheme의 kinds는 ty_fun을 올바른 순서로 생성하도록 보장합니다.

rust
(bound_ir, lowered_scheme.scheme)

이로써 3부작을 마칩니다. 드디어 로우가 낮아졌습니다. 기본 lowering을 할 때는 Ast가 IR에 저작권 클레임을 걸 것 같아 걱정됐는데, 로우 lowering은 이게 변형적(transformative) 콘텐츠임을 확실히 해줬습니다. 이 단계에서 IR이 Ast와 어떻게 갈라져 한 단계 더 낮은 추상화가 되는지 명확해집니다. 다음은 아이템(items) 처리인데, 예전의 부딪힘보다는 더 잘 되길 바랍니다.