행 타입 로워링, 확실히

URL: https://thunderseethe.dev/posts/lowering-rows-intro/

Title: 행 타입 로워링, 확실히

언어 만들기

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

이번 글은 이전 패스에서 행 타입을 추론했던 내용을 바탕으로, 행(row)들을 로워링(lowering)하는 작업을 다룹니다. 또한 기본 언어에 대해 수행했던 로워링을 확장합니다.

지난번에는 types/base를 IR로 로워링했습니다. 흥미롭긴 했지만, 사실상 Ast:: 접두사를 IR:: 접두사로 바꾼 것에 불과한 건 아닌가 하는 불안도 있다고 고백했었습니다. 오늘은 types/rows를 로워링하면서 그런 걱정을 덜어보려 합니다. 훨씬 더 “지각 변동”에 가까운 로워링이죠. 행 타입은 우리 언어에서 데이터 타입을 제공한다는 점을 기억하세요. 행은 표면 언어(syntax)와 타입 체커에서는 훌륭하지만, 메모리 상에서 이를 표현해야 하는 순간부터는 매력이 조금씩 사라집니다.

행을 순진하게 구현하면 런타임에서 HashMap이나 어떤 형태의 연관 배열(associative array)로 표현하게 됩니다. 컴파일이 매우 쉬워진다는 장점이 있지만, 그 대가로 런타임의 행이 해시맵이 됩니다. 이 시리즈가 런타임 구현에 관한 시리즈라면 만족할 수도 있겠지만, 이건 컴파일에 관한 시리즈입니다. 더 촘촘한 메모리 표현으로 “컴파일해 나갈” 방법이 분명히 있어야 합니다.

다행히도 무한한 지식의 샘인 Abstracting Extensible Datatypes 논문은 행을 로워링하는 방법에 대해 많은 이야기를 해주면서도 런타임에서 행을 직접 다루는 이야기는 하지 않습니다. 그들은 행을 System F 기반의 계산체계로 로워링합니다 — 어, 우리랑 똑같네요! — 다만 데이터에 대한 몇 가지 확장이 있습니다. 물론 IR::Int 같은 프리미티브도 데이터이긴 하지만, 행을 처리하려면 더 많은 도움이 필요합니다.

그들의 권고에 따라, 우리는 IR에 두 가지 새 구성 요소를 추가합니다: 튜플(tuple)과 태그드 값(tagged value). Rust를 해본 사람이라면 튜플은 익숙하죠. 만약 Rust를 모르는데도 이 시리즈를 여섯 편이나 따라오셨다면, 축하와 애도를 전합니다. 진짜 대단한 분이네요. 상으로 링크를 드립니다.

태그드 값도 Rust에서 다른 이름으로 보긴 했습니다: enum. 태그드 값이란, 어떤 값을 정수 태그와 함께 저장해서 그 값이 어떤 enum 변형(variant)인지 표시하는 방식입니다. 튜플 (tag, value)처럼 생각할 수 있죠. Rust는 내부적으로(일부 레이아웃 최적화를 제외하면) enum을 태그드 값으로 표현합니다.

행 로워링은 Ast의 Prod와 Sum 행을 IR의 튜플과 태그드 값으로 매핑할 것입니다. 눈썰미 좋은 분이라면 튜플과 태그드 값이 행과 전혀 닮지 않았다는 것을 알아챘을 겁니다. 행에는 필드가 있고, 연결(concat)하거나 투영(project)할 수 있으며, 분기(branch)하거나 주입(inject)할 수 있습니다. 튜플은 그런 걸 할 수 없죠. 그냥… 순서대로 놓여 있을 뿐입니다.

행 로워링 기법

논문도 행이 튜플과 전혀 닮지 않았다는 사실을 잘 알고 있습니다. 그래서 로워링 과정에서 불일치를 해결하기 위해 두 가지 기법을 사용합니다: **증거 전달(Evidence Passing)**과 라벨 제거(Label Erasure). 이 두 기법을 통해 행을 더 단순한 튜플/태그드 값으로 변환하면서도 우리가 사랑하는 행 연산을 유지할 수 있습니다. 로워링이 끝나면, 동일한 행 연산(concat, branch 등)을 튜플과 태그드 값 위에서 수행하게 됩니다.

첫 번째 기법인 증거 전달은 컴파일 세계에서 오랜 전통을 갖고 있습니다. 트레이트(trait) 같은 기능을 가진 언어(Rust, Haskell, Swift 등)는 트레이트를 나타내는 증거(evidence)를 결국 어딘가로 전달합니다. Haskell의 딕셔너리 전달(dictionary passing)을 들어본 적이 있다면, 그것이 타입 클래스에 대한 증거 전달입니다. Swift는 심지어 메모리 관리에도 증거 전달을 씁니다. 각 Swift 타입은 자신을 이동/복제/파괴하기 위한 증거를 가지고 있으며, 그 증거가 전달됩니다.

이런 계보 덕분에 우리는 튼튼한 토대 위에 서 있다고 확신할 수 있습니다. 증거 전달은 실제 컴파일러에서 이미 충분히 검증된 기법입니다. 우리는 그걸 행에 맞게 살짝 가져와서 비틀어 쓰기만 하면 됩니다.

증거 전달의 핵심은 타입 체커에서 해결되지 않은 제약(unsolved constraints)에 있습니다. 행을 타입 체크할 때 봤듯이, 해결되지 않은 행 제약은 일반화(generalization) 과정에서 증거로 바뀌고 타입 스킴(type scheme)에 들어갑니다. 이제 어떤 항목(item)을 호출하는 쪽은 그 증거를 해결하고 우리에게 _전달_할 책임이 생깁니다. 타입 체커에서는 이것이 인스턴스화(instantiation)로 암묵적으로 처리됩니다. 하지만 로워링에서는 더 문자 그대로 드러납니다.

각 증거 조각을 나타내는 실제 IR 텀(term)을 만듭니다. 타입 체커가 어떤 행 조합을 해결했다면, 로워링은 그 해결된 증거에 대한 IR 텀을 생성합니다. 타입 스킴에 남아 있는 미해결 증거는, lower가 만들어내는 IR 텀의 추가 함수 파라미터가 됩니다. 타입 체커가 제약을 인스턴스화하고 해결하는 지점에서는, 로워링이 IR 텀을 생성해서 함수 인자로 넘기게 됩니다.

이는 타입 함수를 도입했던 것과 정신적으로 닮았습니다. base를 로워링할 때, 큰 변화 중 하나는 이전에는 순수하게 타입 정보였던 것을 표현하기 위한 텀 노드(term node)를 도입한 것이었습니다. 증거 전달은 그 경로의 자연스러운 연장입니다. 이제 우리는 타입 정보를 텀으로 표현할 뿐 아니라, 생성된 증거 텀이 최종 IR 텀의 동작에도 영향을 미치게 됩니다.

두 번째 기법인 라벨 제거는 더 소박하지만 똑같이 중요합니다. 라벨은 행을 정확히 타입 체크하는 데 핵심이지만, 로워링에서는 더 이상 필요하지 않습니다. 우리는 모든 행과 Ast에서 라벨을 제거할 것입니다. 라벨 자체를 지우면서도, 라벨이 제공하던 중요한 성질 하나는 유지합니다. 바로 행에서 값들의 **순서(order)**입니다. 라벨이 행을 정렬해 주고 있었고, 로워링에서는 라벨 대신 인덱스를 사용해 그 순서를 보존할 것입니다.

라벨을 지우고 나면, 행은 단지 타입 벡터(vector of types)가 됩니다. 이는 목표 데이터 표현으로 자연스럽게 매핑됩니다.

• 튜플로서, 벡터는 각 인덱스에 있는 필드의 타입을 나타냅니다.
• 태그드 값으로서, 벡터는 각 태그에 해당하는 값의 타입을 나타냅니다.

기계는 숫자에는 강하고 단어에는 약하니까(기계어 말장난은 무시해주세요), 이런 로워링은 아주 좋습니다.

작업의 큰 그림

이제 두 도구인 증거 전달과 라벨 제거에 익숙해졌으니, 행 로워링의 고수준 그림을 그릴 수 있습니다. 타입 체크 동안, Row 관련 AST 노드들은 각각 자기 안에 증거를 저장합니다.

• Concat
• Branch
• Project
• Inject

그 증거는 목표 행(goal row)을 만들기 위해 왼쪽 행(left row)과 오른쪽 행(right row)을 어떻게 결합해야 하는지를 알려주는 “행 조합(row combination)”입니다. 우리는 그 증거로부터, 각 AST 노드가 해당 행 조합에 대해 수행해야 할 동작을 구현하는 IR 텀을 생성할 것입니다.

로워링 중에 이런 AST 노드 중 하나를 만나면, 대응하는 증거 텀에서 생성된 연산(operation)을 꺼내 씁니다. 생성된 연산을 호출(call)한 결과가 원래의 row 노드를 대체합니다. 이 과정을 끝내면, 모든 Row AST 노드는 지워지고, 생성된 연산들을 사용하는 IR 텀만 남게 됩니다.

말은 그럴듯하지만 꽤 추상적이죠. 증거를 위한 생성 텀은 어떻게 생겼을까요? 각 증거는 우리 4가지 행 노드에 대한 구현을 제공해야 합니다. 우리는 이미 IR에 튜플을 추가하고 있으므로, 4필드 튜플로 각 연산을 담아두겠습니다.

Project와 Inject는 방향(direction)이 있습니다: Left 또는 Right. 이를 반영하기 위해 생성 텀 안에 각각 두 버전을 두겠습니다. 방향을 가진 연산들을 납작하게 펼치지 않고, 별도의 튜플 안에 중첩해 넣습니다. 증거 텀의 전체 레이아웃은 다음과 같습니다.

( <concat impl>
, <branch impl>
, (<project left impl>, <inject left impl>)
, (<project right impl>, <inject right impl>)
)

여기서 각 impl은 해당 행 연산을 수행하는 IR 함수입니다. 이제 조금 더 구체적으로 예시를 통해 보겠습니다. 다음과 같은 증거에 대한 텀을 생성한다고 해봅시다.

Evidence::RowEquation {
  left: Row::Closed(ClosedRow {
    fields: vec!["a", "d"],
    values: vec![Type::Int; 2],
  }), 
  right: Row::Closed(ClosedRow {
    fields: vec!["b", "c"],
    values: vec![Type::Int; 2],
  }), 
  goal: Row::Closed(ClosedRow {
    fields: vec!["a", "b", "c", "d"],
    values: vec![Type::Int; 4],
  }) 
}

여기서는 타입이 그리 중요하지 않으니 전부 Type::Int를 썼습니다. 우리가 집중할 것은 필드가 생성된 텀에서 사용되는 인덱스를 어떻게 이끄는지입니다.

IR 인스턴스 자체를 전부 쓰지는 않겠습니다. 너무 길어서 읽기 어려울 테니까요. 대신 Rust 문법으로 아이디어를 전달하겠습니다. 첫 번째로 생성되는 연산은 concat입니다.

fn concat(
  left: (Int, Int), 
  right: (Int, Int)
) -> (Int, Int, Int, Int) {
  (left[0], right[0], right[1], left[1])
}

concat은 두 product 타입을 이어붙이므로 튜플을 다룹니다. left와 right 행을 나타내는 튜플 두 개를 입력으로 받아, goal을 나타내는 튜플을 반환합니다. 이때 goal 튜플에서 필드의 순서가 중요합니다.

출력이 (left[0], left[1], right[0], right[1])일 것 같지만, 그러면 필드 순서를 무시하게 됩니다. 우리는 구현에서 라벨을 지우더라도, 증거에 있는 필드에 근거해 좌/우 인덱스 연산들의 순서를 정합니다. left의 필드가 ["a", "d"]이기 때문에 a와 d가 goal의 fields에서 나타나는 위치에 맞춰, 튜플의 처음과 끝에 배치됩니다.

Rust는 우리의 행 타입이 가진 익명(sum) 타입을 지원하지 않습니다. 그래서 예시에서는 enum을 도입하되, 실제로는 익명 sum 타입이라는 점을 기억하세요.

enum Left {
  A(Int),
  D(Int)
}

enum Right {
  B(Int),
  C(Int),
}

enum Goal {
  A(Int),
  B(Int),
  C(Int),
  D(Int),
}

이 enum들을 가지고 branch 연산을 정의해봅시다.

fn branch<T>(
  left: fn(Left) -> T, 
  right: fn(Right) -> T, 
) -> impl Fn(Goal) -> T {
  move |goal| match goal {
    Goal::A(x) => left(Left::A(x)),
    Goal::B(x) => right(Right::B(x)),
    Goal::C(x) => right(Right::C(x)),
    Goal::D(x) => left(Left::D(x)),
  }
}

branch는 값을 직접 다루는 대신 함수들을 다루기 때문에 concat보다 더 복잡합니다. branch는 두 함수 fn(Left) -> T와 fn(Right) -> T를 받아서, 세 번째 함수 fn(Goal) -> T로 합칩니다. Rust에서는 함수를 반환하려면 클로저가 필요하므로 impl Fn(Goal) -> T로 씁니다. 우리 언어에서는 이것이 일반 IR::Fun 노드가 됩니다. 우리는 클로저와 함수를 구분하지 않습니다.

left와 right 함수가 어떤 타입을 반환하는지 모르기 때문에, 세 함수가 모두 같은 타입을 반환하도록 타입 변수 T를 사용합니다. 구현은 다음과 같습니다.

• Goal enum에 대해 match합니다.
• 각 분기에서 enum을 언랩(unwarp)하고 Left 또는 Right로 다시 래핑(rewrap)합니다.
• 다시 래핑된 enum을 인자로 left 또는 right에 디스패치합니다.

concat과 마찬가지로, 분기 순서도 증거에 있는 필드 순서를 기반으로 정해집니다.

다음으로 project 함수들은 goal 튜플을 받아서 left 또는 right 튜플을 구성합니다. prj_left는 left 튜플을 담당합니다.

fn prj_left(
  goal: (Int, Int, Int, Int)
) -> (Int, Int) {
  (goal[0], goal[3])
}

여기서도 필드가 우리를 안내합니다. left가 ["a", "d"]이므로, goal에서 a와 d의 인덱스를 사용해 튜플을 구성합니다. prj_right도 비슷하게 right 튜플을 담당합니다.

fn prj_right(
  goal: (Int, Int, Int, Int)
) -> (Int, Int) {
  (goal[1], goal[2])
}

inject 함수들은 project와 비슷하지만 반대 방향으로 동작합니다. Left 또는 Right enum을 받아서 Goal enum을 만듭니다. branch와 달리 값에 대해 직접 동작합니다. inj_left는 Left enum을 받습니다.

fn inj_left(left: Left) -> Goal {
  match left {
    Left::A(x) => Goal::A(x),
    Left::D(x) => Goal::D(x),
  }
}

inj_right는 예상대로 Right enum을 받습니다.

fn inj_right(
  right: Right
) -> Goal {
  match right {
    Right::B(x) => Goal::B(x),
    Right::C(x) => Goal::C(x),
  }
}

마지막으로, 증거 텀은 이 모든 함수를 큰 튜플 하나에 모아둔 것입니다.

( concat
, branch
, (prj_left, inj_left)
, (prj_right, inj_right)
)

다시 말하지만 여기서는 Rust 문법으로 썼지만, 실제 구현은 이 동작을 수행하는 IR 텀들을 생성하게 됩니다. 그 크기는… 상당할 것입니다. 결국 어떤 행 연산이든 처리할 준비가 되어 있어야 하니까요. 하지만 실제로는 한 번에 이런 연산 중 하나만 필요합니다. 예를 들어 Concat 노드를 로워링할 때는, 텀의 0번째 인덱스에서 구현을 꺼내 나머지는 버리면 됩니다.

행 IR 노드

이제 구현으로 들어갈 만큼 이해가 충분합니다. lower를 수정하기 전에, 데이터 타입에 필요한 새 노드부터 보겠습니다. IR에 튜플과 태그드 값을 지원하도록 다음을 추가합니다.

enum IR {
  // Our previous cases...
  // Create a product type.
  Tuple(Vec<Self>),
  // Select a field out of a product.
  Field(Box<Self>, usize),
  // Create a sum type.
  Tag(Type, usize, Box<Self>),
  // Case match on a sum.
  Case(Type, Box<Self>, Vec<Branch>),
}

새 값을 구성하는 노드 Tuple과 Tag가 있고, 분해하는 노드 Field와 Case도 필요합니다. 예시 Rust 코드에서 [0]과 match를 썼는데, 각각 Field와 Case에 해당합니다. 우리의 Case는 Rust의 match처럼 화려한 패턴 매칭을 지원하지 않습니다. 단지 스크러티니(scrutinee)의 tag 값에 따라 해당 Branch로 디스패치할 뿐입니다.

Branch는 다음과 같습니다.

struct Branch {
  param: Var,
  body: IR,
}

겉보기엔 Fun 노드와 동일합니다. 하지만 Case가 Fun 리스트를 갖도록 하지 않고 별도 노드로 둔 이유는, 최적화기(optimizer)가 더 쉽게 일할 수 있도록 하기 위해서입니다. 함수형 언어로서 우리는 Fun 노드에 대해 최적화를 매우 적극적으로 적용하고 싶습니다. 그런데 그 최적화를 Branch에 실수로 적용하고 싶진 않습니다.

또 한 가지. Tag와 Case는 둘 다 Type 멤버를 가집니다. Tag에서 이 Type은 태그드 값의 전체 Sum 타입을 기억합니다. 예를 들어 IR::Tag(..., 0, IR::Int(343)) 같은 태그드 값은 수많은 Sum 타입 중 어느 것에도 속할 수 있습니다. 하지만 특정 태그드 값에 대해서 타입 체커는 구체적인 Sum 타입 하나를 찾아냅니다. 우리는 그 타입을 IR::Tag 안에 저장해두어 타입을 재구성할 수 있게 합니다.

Case는 반환 타입을 기억하기 위해 Type을 저장합니다. Case의 반환 타입은 항상 자명하지 않습니다. 예를 들어 다음의 반환 타입은 무엇일까요?

match an_enum {
}

분기(branch)가 하나도 없다면 어떤 타입이든 될 수 있습니다. 전제 자체가 이상하다고 생각할 수도 있지만, 증거를 생성할 때 빈 행(empty row)이 포함되면 이런 일이 실제로 생깁니다. 일반적으로는 문제지만, 어떤 특정 Case에 대해서는 타입 체커가 반환 타입을 이미 찾아냈을 것입니다(아니면 타입 에러). 그래서 쉬운 해결책은 타입 체크에서 얻은 반환 타입을 Case에 저장하는 것입니다.

행 타입 노드

IR에 추가를 하고 나면, Type에도 추가가 필요합니다.

enum Type {
  // Our base types...
  Prod(Row),
  Sum(Row),
}

Product는 IR::Tuple의 타입이고, Sum은 IR::Tag의 타입입니다. IR에 4개 노드를 추가했는데 타입은 2개만 추가하니 싸게 먹힌 것처럼 보입니다. 하지만 Row를 열어보면…

enum Row {
  Open(TypeVar),
  Closed(Vec<Type>),
}

어라, 결국 네 개 타입을 ‘추가 단계(extra steps)’로 넣은 느낌이네요. 어쨌든 라벨을 지우기 때문에 Closed 행은 Vec<Type>가 됩니다. 타입 체크에서 사용했던 별도의 RowVar 대신, IR에서는 open row를 TypeVar로 표현합니다. 타입 TypeVar와 행 TypeVar의 구분은 새로 추가한 Kind로 합니다.

enum Kind {
  Type,
  Row,
}

이제 조심하지 않으면 kind를 망가뜨릴 수 있게 됐네요. 만세! Row와 새 Kind의 결과로, IR의 TyApp에도 작은 수정이 필요합니다.

enum IR {
  // ...
  TyApp(Box<Self>, TyApp),
  // ...
}

이전처럼 Type을 받는 대신, 이제 TyApp를 받습니다.

enum TyApp {
  Ty(Type),
  Row(Row),
}

TyApp는 타입 함수 적용 시 Type 또는 Row를 넘기기 위한 용도로만 존재합니다. 타입 함수에 Row를 적용할 수 있게 되면서, TypeVar에 Row를 치환(substitute)할 수 있는 새로운 가능성이 열립니다. 이를 위해 subst 함수를 Row도 지원하도록 백스테이지에서 수정할 것입니다. 또한 이런 잡무를 처리하는 김에, type_of도 새 추가분을 처리하도록 업데이트해야 합니다. 이제 type_of에 익숙해졌으니 이런 업데이트는 그다지 흥미롭진 않습니다. 전체 코드에서 확인할 수 있습니다.

여기까지 정말 많은 내용을 다뤘습니다. 무엇을 해야 하는지 알고, 앞으로 닥칠 행들을 위해 IR과 Type도 준비했습니다. 하지만 아직 할 일이 많습니다. 다음 글에서는, 우리가 추가한 것들을 이용해 타입 스킴에 있는 증거를 로워링해 보겠습니다.