단형화로 다형성 추방하기

언어 만들기

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

오늘 글에 앞서 base 단순화 패스가 있다. 하지만 그 패스는 단형화를 이해하는 데 필수는 아니다. 단형화는 로워링에서 소개한 IR에만 의존한다. 본격적으로 들어가기 전에 IR을 다시 훑어보자.

컴파일러 내부로 더 깊이 들어갈수록, 우리는 기계어와 우리 사이에 있는 고수준 기능들을 하나씩 벗겨낸다. 언어 기능들 중 상당수는 하드웨어에 직접 대응하는 명령이 없기 때문에, 제거하거나 그에 상응하는 다른 형태로 번역해야 한다. 오늘 도마 위에 오를 기능은 **다형성(polymorphism)**이다.

다형성은 지금까지 가까운 동료였고, 우리의 IR 설계 전체가 다형성을 더 잘 수용하기 위해 존재해왔다. 하지만 내가 본 어떤 컴퓨터에도 “타입 함수에 타입을 적용하라” 같은 명령은 없다. 언어에서 다형성을 제거하는 대표적인 방법은 두 가지다.

• 타입 소거(Type Erasure)
• 단형화(Monomorphization)

제목에서 어느 쪽을 선택할지 스포일러가 되었지만, 트레이드오프를 이해하기 위해 둘 다 살펴보자.

타입 소거

이름 그대로 타입 소거는, 타입 함수(type function)와 타입 적용(type application)이 나타나는 모든 곳에서 그것들을 그냥 제거함으로써 다형성을 지워버린다. 더 단순한 해결책을 상상하기 어렵다. 하드웨어로 다형성을 표현할 수 없으니, 아예 표현하지 않겠다는 것이다. 그런데 여기서 문제가 생긴다.

타입 함수를 지워버린 뒤 남는 타입 변수들은 어떻게 표현할까? 코드는 이미 타입 체크가 끝났으니 존재하지 않는 메서드를 호출한다든지 하는 문제는 걱정하지 않아도 된다. 하지만 실용적인 관점에서 고민이 남는다. 메모리에서 제네릭 타입 T를 어떻게 표현할까? T가 usize 같은 타입을 의미한다면 값은 레지스터에 놓일 것이다. 하지만 T가 Box<(usize, usize)> 같은 타입을 의미한다면 힙을 가리키는 포인터가 될 것이다.

타입을 지워버리면 서로 다른 메모리 레이아웃을 구분할 수 있는 능력도 잃는다. 임의의 타입을 인자로 받고 반환할 수 있게 하려면, 타입 T에 대해 가능한 “가장 낮은 공통 분모”의 메모리 레이아웃을 택해야 한다. 그래서 제네릭 타입 T는 “정체를 알 수 없는 힙 값에 대한 포인터”로 표현된다. Rust 용어로는 Box<dyn Any>라고 생각할 수 있다. 이를 **균일 표현(uniform representation)**이라 부른다.

제네릭을 포인터로 표현하면 전달과 반환이 매우 단순해진다. 포인터만 주고받으면 되고, 그것이 무엇을 가리키는지 신경 쓸 필요가 없다. 하지만 아직 끝이 아니다. 다시 T가 usize인 경우를 생각해 보자. usize는 포인터가 아니고, 그것을 포인터로 취급하는 것은 역사적으로도 미정의 동작의 온상이었다. usize를 제네릭 함수에 넘기기 전에, Box<usize>로 박싱해서 포인터로 바꿔야 한다. 레지스터로 전달되고 스택에 놓일 타입들은 모두 이렇게 힙에 할당해 포인터 뒤에 숨겨야 타입 소거 제네릭에 참여할 수 있다.

타입 소거는 여러 언어에서 사용된다. Java, Haskell, Swift 등에서 이를 효과적으로 활용한다. 가비지 컬렉션이 있는 언어들은 종종 타입 소거를 선호하는데, 균일 표현이 GC를 더 쉽게 만들기 때문이다.

단형화

단형화는, 각 타입 인스턴스화(instantiation)마다 함수의 새 복사본을 생성함으로써 다형성을 제거한다. 타입 적용을 만날 때마다 우리는:

• 적용되는 모든 타입을 수집하고
• 함수 본문의 새 복사본을 만들고
• 새 본문에서 각 타입 변수를 적용된 타입으로 치환한다

그 결과 다형성이 제거된 “새 함수”를 얻고, 기존의 적용은 그 새 함수를 사용하도록 바꾼다. 여기에는 타입 소거에서의 메모리 레이아웃 문제가 없다. 타입 T가 usize였다면 그대로 usize이고, 있는 그대로 전달/반환한다. 더 좋은 점은, 함수 본문에서 구체적인 타입을 알게 되었으니 그 정보를 바탕으로 추가 최적화도 가능하다는 것이다.

위키피디아에는 이 아이디어를 잘 보여주는 짧은 예제가 있다:

rust
fn id<T>(x: T) -> T {
  x
}

fn main() {
  let int = id::<i32>(10);
  let string = id::<&str>("some text");
  println!("{int}, {string}");
}

id의 각 적용은 적용된 타입에 특화된 새 함수를 만든다( Rust에서 타입 적용은 ::<>로 표기한다):

rust
fn id_i32(x: i32) -> i32 {
  x
}

fn id_str(x: &str) -> &str {
  x
}

fn main() {
  let int = id_i32(10);
  let string = id_str("some text");
  println!("{int}, {string}");
}

단형화는 우리의 모국어인 Rust가 사용하는 방식이다. 다른 언어들도 부분적으로 단형화를 쓰지만, Rust는 “항상” 단형화를 하는 몇 안 되는 언어 중 하나다. C++은 단형화를 사용하지 않지만, 템플릿 시스템은 단형화와 계보를 공유하며 사실상 항상 사용된다. 각 템플릿 함수는 인스턴스화마다 한 번씩 복사되고, 함수 정의는 적용되는 모든 곳에서 볼 수 있어야 한다.

트레이드오프

지금까지 단형화를 좋은 쪽으로만 그렸지만, 전부는 아니다. 구체 타입을 알 수 있어서 가능한 최적화는 큰 이점이지만 공짜는 아니다. 무엇보다도, 타입 인스턴스화마다 함수 복사본을 만들어야 한다. 이 복사본들은 빠르게 늘어나 바이너리 크기를 부풀리고 컴파일 시간도 늘린다.

또한 단형화는 컴파일 시점에 프로그램 전체가 존재해야 한다는 요구를 만든다. 함수가 적용되는 곳마다 복사본을 만들기 때문에, 함수 정의는 적용되는 모든 곳에서 이용 가능해야 한다. 이는 사실상 **분리 컴파일(separate compilation)**의 기회를 차단한다. 분리 컴파일은 컴파일러 성능에 매우 중요하다. 컴파일을 여러 부분으로 나눠 병렬로 돌리거나, 점진적으로 처리해 캐시할 수 있게 해주기 때문이다.

타입 소거의 장단점은 단형화의 트레이드오프를 거울처럼 반영한다. 타입 소거는 인스턴스화가 몇 개든 함수 본문을 하나만 유지하면 된다. 모든 인스턴스화가 같은 본문을 쓰므로 컴파일 시 함수 정의가 반드시 필요하지도 않다. 시그니처만 알면 충분하니 분리 컴파일이 가능해진다.

물론 구체 타입을 알 때 가능한 최적화 기회는 잃는다. 어떤 경우에는 usize처럼 원래 박싱되지 않던 값을 박싱해야 해서 성능이 나빠질 수도 있다. 그렇다면 단형화가 명백한 승자인 것처럼 들릴지도 모른다. 컴파일 시간을 희생하고 런타임 성능을 얻는 거래를 싫어할 사람이 있을까? Rust 컴파일 시간에 대한 소동만 봐도, 실제로는 그렇지 않다는 걸 알 수 있다. 많은 사람들이 그 트레이드오프를 불편해한다.

게다가 단형화가 항상 더 빠르다고 단정할 수도 없다. 값 박싱은 작은 타입에는 성능 손해지만, 큰 타입에는 종종 성능 이득이 될 수 있다. 사실상 같은 함수의 복사본이 많아지면 명령 캐시(instruction cache) 압박도 커진다. 실제로 많은 컴파일러는 상황에 따라 타입 소거와 단형화를 섞어 쓴다.

GHC는 기본이 타입 소거지만, 동일 모듈 안에 있는 코드에 대해서는 공격적으로 단형화한다. 작은 함수들은 GHC의 오브젝트 파일 안에 포함될 수 있어서, 모듈 경계를 넘어 단형화될 수 있다.

구현

트레이드오프를 이해한 뒤, 우리 언어에서는 단형화를 사용하기로 하자. 분리 컴파일의 이점을 잃지만, 간단한 토이 언어에서 분리 컴파일이 필요할 만큼 큰 코드를 작성한다는 건 요원한 일이다. 규모가 작으니 컴파일 시간도 걱정하지 않는다. 이런 문제들은 사람들이 실제로 쓰는 성공한 언어들의 고민이다.

이렇게 길게 설명했지만, base에서의 단형화 구현은 다소 김이 빠진다. 단형화는 타입 적용을 찾아서 바꿔치기하는 작업이다. 그런데 우리 언어는 타입 추론에서 일반화할 때 최상위 아이템(top-level item)에 대해서만 타입 함수를 도입한다. 그에 따라 타입 적용도 최상위 아이템에만 나타난다.

하지만 base 언어에는 최상위 아이템이 없다. base IR 어디에서도 타입 적용을 언급하지 않는 것을 볼 수 있다. 너무 걱정하진 말자. 아직 할 일이 조금 있긴 하지만, “진짜 단형화”에 비하면 사소한 수준이다.

타입 적용은 없지만, IR의 맨 위에는 타입 함수가 있다. IR에서 타입 함수를 제거하려면 그 함수에 어떤 타입을 대입할지 추측해야 한다. 최상위 아이템이 없으니 이 추측은 쉽다. 모두 Int다.

너무 좋은 얘기처럼 들릴 수 있다. 정말 모든 타입 변수가 Int일까? 우리의 Type은 비다형적인 경우로 Int와 Fun 두 가지만 고려하면 된다. 어떤 변수가 Fun 타입으로 풀리는 유일한 경우는, 우리가 함수를 다른 함수에 인자로 넘길 때다.

하지만 최상위 아이템이 없는 상태에서는, 이런 “함수 전달”이 항상 두 개의 타입 변수로 분해된다. 함수 자체를 하나의 타입으로 표현하기보다는, 함수의 인자 타입과 반환 타입을 나타내는 새로운 타입 변수를 도입한다. 다음 코드를 보자:

text
let id = |x| x;
id(|y| y + 1);

여기서 id의 인자는 함수 타입이지만, 전체 항의 타입은:

text
Type::fun(Type::Var(0), Type::Var(0))

로 된다.

로컬하게 추론할 때는 함수 타입을 항상 인자/반환 타입으로 분해할 수 있을 만큼의 정보가 있다. 함수 타입을 항상 분해할 수 있다면, 우리가 만나는 어떤 변수에 대해서도 남는 타입 후보는 하나뿐이다: Int.

짧은 복습

미들엔드 패스들은 모두 공통의 IR 위에서 동작한다:

rust
enum IR {
  Var(Var),
  Int(i32),
  Fun(Var, Box<Self>),
  App(Box<Self>, Box<Self>),
  TyFun(Kind, Box<Self>),
  TyApp(Box<Self>, Type),
  Local(Var, Box<Self>, Box<Self>),
}

우리 IR은 명시적으로 타입이 붙어 있고, 제네릭은 타입 함수와 타입 적용으로 표현한다. 또한 필수는 아니지만 단순화에서 매우 유용한 Local도 도입한다. IR과 함께, AST의 타입에서 로워링된 Type이 있다:

rust
enum Type {
  Int,
  Var(TypeVar),
  Fun(Box<Self>, Box<Self>),
  TyFun(Kind, Box<Self>),
}

Type에는 AST에는 없던 Kind가 있다. 값(value)에 타입(type)이 있듯이, 타입에도 킨드(kind)가 있다. base의 Kind는 공허하다:

rust
enum Kind {
  Type
}

Type이라는 킨드를 가진 것이 Type이다. 사실이라고 믿지만, 이런 식의 순환적인 명제를 정말 공리로 둘 필요가 있나 싶기도 하다. IR에 대해 알아야 할 것은 이것이 전부다. 다시 단형화로 돌아가자.

(거의) 볼 게 없는 구현

base에서의 단형화 구현은 다음이 전부다:

rust
fn trivial_monomorph(
  ir: IR
) -> IR {
  let mut types = vec![];
  let mut fun = &ir;
  // Assume all types are Int.
  // This can't be wrong for base because we don't yet support any interesting types.
  // Any function getting passed around will use a function type not a
  while let IR::TyFun(_, body) = fun {
    types.push(Type::Int);
    fun = body;
  }
  instantiate(ir, types)
}

IR을 입력으로 받아, IR 루트에서 모든 타입 함수를 찾아내고, 그 자리에 모두 Int를 인스턴스화한다. instantiate도 그리 대단하진 않다:

rust
fn instantiate(
  ir: IR, 
  types: Vec<Type>
) -> IR {
  types.into_iter().fold(ir, |ir, ty| {
    let IR::TyFun(_, body) = ir else {
      panic!("ICE: Applied a type to a non type function IR in monomorph");
    };
    simplify_base::subst_ty(*body, ty)
  })
}

새 코드를 쓰는 것도 아니다! 구현의 핵심은 subst_ty에 있는데, 이건 단순화(simplification)에서 이미 쓰던 메서드다. 현재로서는 단형화가 정말 이것뿐이다. 못 믿겠다면 레포를 확인해 보자. 아이템을 도입하고 나면 훨씬 더 실질적인 작업이 될 것이다. 그때까지는 단형화가 컴파일 여정 중 잠깐의 휴식을 제공한다.

다음 패스인 클로저 변환(closure conversion)은 씹을 거리가 많다.