URL: https://thunderseethe.dev/posts/type-inference/

파서 없이 언어 타입체킹하기

언어 만들기

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

이 글은 시리즈의 첫 번째 글로, 간단한 함수형 언어를 위한 타입 추론에 대해 다룬다.

나는 언어를 설계하고 싶다. 더 구체적으로는, 내가 지어낸 프로그래밍 언어의 컴파일러를 구현하고 싶다. 이런 생각을 한 게 처음은 아니다. 사실 나는 이전에도 한두번이아니라여러번 이런 갈증을 느꼈다. 왜 그렇게 여러 번 실패했는데도 이 모험으로 다시 돌아오는지 스스로도 설명하기 어렵다. 하지만 내가 왜 매번 실패하는지는 말할 수 있다. 반짝이는 새 프로젝트를 신선한 눈으로 시작할 때마다, 나는 재빨리 렉서를 뚝딱 만든다.

하지만 파서를 만들기 시작하면 진행 속도는 기어가듯 느려진다. 끝없이 문법을 가지고 잡다한 논쟁(바이크셰딩)을 하거나 연산자 우선순위를 어떻게 할지 고민하느라 시간을 보낸다. 어찌어찌 추상 구문 트리(AST)를 만들어내고 나면, 나는 예외 없이 완전히 기운이 빠져버린다. 그렇게 언어는 미완성 사이드 프로젝트 더미에 추가되고, 영원히 텅 빈 저장소로 남아 의욕 없는 야망만 담게 된다. 시도를 거듭할수록 이 패턴은 점점 더 뚜렷해졌다.

그럼 한 발 물러서서 생각해보자. 나는 왜 애초에 렉서와 파서부터 시작하는 걸까? 컴파일러 구축은 대략 몇 개의 큰 단계로 생각할 수 있고, 각 단계의 출력은 다음 단계의 입력으로 들어간다:

컴파일러는 실행 시 이 단계들을 순서대로 수행하니, 그것들을 만드는 것도 순서대로 하는 게 자연스럽게 느껴진다. 문제는 언어 만들기에 대한 교육 자료가 이 인식을 더 강화한다는 점이다. 교육 자료는 텍스트를 파싱하는 다양한 방법에 엄청 집중한다. 훌륭한 자료인 Crafting Interpreters조차도 파싱을 대충 넘어가는 이유를 설명하는 노트를 굳이 포함할 정도다. 이런 파싱 과잉 강조는, (적어도 나에게는) 파싱이 새 언어를 시작하기에 가장 좋은 지점이라는 믿음을 심어줄 수 있다. 하지만 반드시 그 순서대로 만들어야 한다는 규칙은 없다. 오히려, 언어를 처음부터 설계한다면 이런 방식은 비실용적이다. 의미론을 먼저 알지 못한 채 문법을 만들려고 하는 건 함정이다. 바퀴가 몇 개인지도, 엔진이 어떻게 바퀴를 구동할지도 모르는 상태에서 차량의 실내를 설계하려는 것과 같다. 편안하게 4명이 탈 수 있게 실내를 설계했는데, 나중에 알고 보니 만들고 있는 게 오토바이라면 곤란해진다!

그렇다면 내 파싱 문제를 어떻게 극복할까? 그냥 렉서나 파서를 쓰지 않으면 된다. 파서를 쓰기 시작하지 않으면 파서 작성에 막힐 일도 없다. 언어의 내부를 더 설계한 뒤에 나중에 파서를 추가해도 된다. 내 바람은, 다른 단계들(타입 체크, 코드 생성 등)을 먼저 갖춰 놓으면, 언젠가 파서를 쓸 때 어떤 모양이어야 하는지 안내해줄 거라는 점이다. 파서를 쓰는 목표는 AST를 만들어내는 것이다. 하지만 프로토타이핑 단계에서는 AST를 반드시 텍스트에서 파싱할 필요가 없다. AST를 먼저 설계해두고, 필요할 때 임시로(ad hoc) 구성하면 된다. 그러면 질문이 바뀐다. 렉싱/파싱으로 시작하지 않는다면 어떤 단계부터 시작해야 할까? 답은 타입 추론(놀랍게도)이다. 하지만 왜 타입 추론으로 시작하는지가 중요하다.

타입부터 시작하는 이유를 이해하려면, Practical Foundations for Programming Languages의 설명을 보면 된다:

타입은 프로그래밍 언어 이론의 중심적 조직 원리다. 언어 기능은 타입 구조의 발현이다. 언어의 문법은 타입을 정의하는 구성 요소에 의해 지배되며, 의미론은 그 구성 요소들 사이의 상호작용에 의해 결정된다.

타입은 언어 설계의 다른 모든 부분에 영향을 주므로, 먼저 확실히 해두는 것이 중요하다. 반대로, 타입을 설계하고 나면 언어의 문법과 의미론은 타입 시스템으로부터 자연스럽게 따라 나와야 한다.

---

배경 Link to heading

이 글은 프로그래밍 언어 설계 전반에 대한 훌륭한 입문서가 되지는 않을 것이다. 이미 그에 대한 좋은 자료가 많이 있다:

• Crafting Interpreters
• Types and Programming Languages

우리는 타입 추론 구현에 집중한다(간결함을 위해 타입, 다형성, AST의 정의조차 다루지 않는다). 여기에서 다루는 아이디어는 새롭지 않다. 이 글의 목표는 여러 출처에 흩어져 있는 좋은 아이디어를 하나로 묶는 것이다. 나는 여러 자료를 읽고 rustc와 GHC 소스 코드를 살펴보며 타입 추론을 어떻게 하는지에 대한 감을 잡았다. 하지만 모든 개념을 함께 엮어주는 좋은 자료를 찾지 못했고, 그래서 직접 쓰기로 했다.

우리는 Rust로 언어를 만든다. Rust 같은 저수준 언어를 왜 고르고, 더 고수준이며 덜 장황한 Haskell이나 OCaml 같은 언어를 택하지 않느냐고 궁금해할 수도 있다. 이 언어들은 컴파일러 문헌에서 자주 등장하는데, 그럴 만한 이유가 있다. 컴파일 과정에 등장하는 트리 순회를 표현하기 매우 자연스럽기 때문이다. 하지만 나는 OCaml을 모른다. Haskell은 더 익숙하지만, 우리가 만들 타입 추론은 변이(mutation)를 많이 사용할 것이므로 불변의 순수성을 중시하는 Haskell은 잘 맞지 않는다. Rust는 트리 순회에 충분히 함수형 스타일을 제공하면서도 변이를 허용한다. 따라서 Rust를 사용할 것이다. Rust가 익숙하지 않다면 cheats.rs에 빠르게 따라잡을 수 있는 촘촘한 요약이 있다.

---

추상 구문 트리(AST) Link to heading

파싱의 핵심 목적은 텍스트 파일을 AST로 변환하는 것이다. 우리는 파싱을 건너뛰므로, 이미 구성된 AST에서 시작하겠다. AST가 기억나지 않는다면 이 블로그 글을 참고하라. 언어는 새 것이므로 작게 시작하고, 점진적으로 더 화려한 AST 노드를 추가해 나갈 것이다. 처음에는 AST가 단 4개 노드만 갖도록 하자: 변수, 정수 리터럴, 함수 리터럴, 함수 적용.

enum Ast<V> {
  /// 지역 변수
  Var(V),
  /// 정수 리터럴
  Int(i32),
  /// 함수 리터럴 
  /// (람다, 클로저 등)
  Fun(V, Box<Self>),
  /// 함수 적용
  App(Box<Self>, Box<Self>), 
}

이보다 더 단순하긴 어렵다. 쓸 만한 언어라고 하긴 힘들지만, 튜링 완전하긴 하다. 우리의 목적에는 최소한의 타입 추론 시스템을 세팅하기에 충분하다.

우리는 AST를 타입 매개변수 V로 파라미터화한다. V는 Var와 Fun에서 쓰이는 AST의 변수 타입이다. 처음에는 AST의 변수 타입 매개변수가 다음과 같을 것이다:

struct Var(usize);

단순화를 위해 변수를 usize로 표현한다. 더 정교한 컴파일러라면 intern된 문자열일 수도 있다고 상상할 수 있다. AST를 타입 체크한 뒤에는, 각 변수에 타입을 주석으로 달게 된다:

struct TypedVar(Var, Type);

Rust에서는 재귀 타입에 간접층이 필요하다. 값을 박싱하면 코드 예제가 꽤 시끄러워지므로, 그 소음을 숨길 헬퍼 메서드를 몇 개 정의하자:

impl<V> Ast<V> {
  fn fun(
    arg: V, 
    body: Self
  ) -> Self {
    Self::Fun(
      arg, 
      Box::new(body))
  }

  fn app(
    fun: Self, 
    arg: Self
  ) -> Self {
    Self::App(
      Box::new(fun), 
      Box::new(arg))
  }
}

---

타입 Link to heading

타입을 추론하기 전에, 어떤 타입을 추론할 수 있는지부터 알아야 한다. 우리의 Type 타입(말장난 같다)은 Ast에 의해 결정된다. Ast가 만들어낼 수 있는 모든 값들을 포괄하는 타입이 필요하다. Ast는 4가지 경우만 있으므로, 각각을 보고 어떤 값을 만들어내는지 판단해보자:

• Var - AST가 만들어내는 어떤 값이든 만들어낼 수 있다(하지만 그 자체는 값이 아니다)
• Int - 정수 리터럴은 값이며, 정수의 타입이 필요하다
• Fun - 함수 리터럴도 값이며, 함수의 타입이 필요하다
• App - 함수 적용은 평가되면 값을 반환하지만, 적용 자체는 값이 아니다

따라서 Ast가 만들어낼 수 있는 값은 두 가지다: Int와 Fun. 이 값들을 위한 타입도 두 가지가 필요하다. 또한 타입 변수(type variable)를 위한 타입도 필요하다. 이 타입 변수는 어떤 값의 타입이라기보다는, 다형성을 지원하기 위해 “아직 모르는 타입”을 표현하는 데 쓰인다. 이를 바탕으로 Type을 정의하면 다음과 같다:

struct TypeVar(u32);
enum Type {
  // 타입 변수
  Var(TypeVar),
  // 정수 타입
  Int,
  // 함수 타입
  Fun(Box<Self>, Box<Self>),
}

Var와 마찬가지로 TypeVar도 내부적으로는 숫자일 뿐이다. Type은 AST와 동일하게 재귀 트리이므로 노드를 박싱해야 한다. 박싱을 덜 귀찮게 하기 위해 비슷한 헬퍼 메서드를 도입하자:

impl Type {
  fn fun(
    arg: Self, 
    ret: Self
  ) -> Self {
    Self::Fun(
      Box::new(arg), 
      Box::new(ret))
  }
}

---

타입 추론 알고리즘 Link to heading

높은 수준에서 보면, 타입 추론의 목표는 AST에서 얻는 문맥 정보로 각 AST 노드의 타입을 추론하는 것이다. 사소한 경우는 쉽다. 예를 들어 Int AST 노드를 보면 언제나 타입이 Int임을 안다. 하지만 항상 그렇게 간단하진 않다. App 노드의 타입을 알고 싶다면, 그 App 노드에서 호출되는 함수의 반환 타입을 봐야 한다. 그런데 그 함수의 타입을 아직 모를 수도 있다. 그 함수가 전체 AST 항(term)의 입력 매개변수를 가리키는 변수일 수도 있기 때문이다. 그런 경우, 전체 항의 타입을 알기 전에는 함수의 타입을 알 수 없고, 이는 순환적으로 보인다.

이 순환을 깨는 방법은 충분한 정보를 얻을 때까지 타입을 “즉시” 추론하지 않는 것이다. 타입을 바로 결정하는 대신, 모르는 타입을 만나면 그 타입에 대한 제약(constraint)을 추적한다. 그 다음 AST 전체를 한 번 훑고 나면, 모인 제약들이 모든 타입을 추론하기에 충분해져야 한다.

말이 조금 두루뭉술하게 들릴 수도 있다. 어떻게 항상 타입을 알아낼 만큼 충분한 제약을 생성한다고 확신할 수 있을까? 답은 수학이다! 자세한 내용은 여기서 다루지 않겠지만, 우리는 많은 사람들이 마련해둔 멋진 증명들에 기대어 “항상 추론 가능한” 타입 시스템을 설계할 것이다. 더 알고 싶다면 Hindley-Milner (HM) 타입 시스템을 찾아보라.

요컨대 우리는 타입에 대한 정보를 추적할 것이다. 그리고 그 추적은 “모르는 타입”을 나타내는 타입 변수에서 수행한다. 노드를 만날 때마다 그 노드에 새 타입 변수를 부여하고, 그 변수에 대한 제약을 방출한다. 해당 노드에 의존하는 다른 노드들은 그 타입 변수를 재사용하며, 그 타입 변수에 대한 자신만의 제약을 만든다. 이것이 Algorithm J나 그 사촌인 Algorithm W 같은 HM 타입 시스템 구현의 기반이다.

다만 그런 구현과 우리의 구현 사이에는 중요한 차이가 하나 있다. Algorithm J는 제약을 만나는 즉시 해결하려고 시도하며, 앞서 본 순환 논리를 피하기 위해 영리한 자료구조를 사용한다. 반면 우리의 구현은 한 번의 패스에서 모든 제약을 생성하고, 별도의 패스에서 그것들을 모두 푼다. 이를 3개의 분리된 패스로 시각화할 수 있다: 제약 생성, 제약 해결, 마지막으로 타입 치환(substitution).

제약 생성 이후에 제약 해결을 수행하는 이런 분리는 “가면서 푸는(solve as you go)” 방식보다 좋은 성질을 제공한다. AST로부터 제약 집합을 생성한 다음 제약만을 대상으로 풀기 때문에, 제약 해결 단계는 AST에 대해 아무것도 알 필요가 없다. 즉 AST가 바뀌어도 제약 해결 코드는 수정할 필요가 없다. 지금은 AST 노드가 4개뿐이라 이점이 작지만, 대부분의 언어는 100개가 넘는 AST 노드를 가진다. 모든 케이스를 제약 생성 단계에서 처리하고, 그 복잡성이 제약 해결 단계로 새지 않게 하는 것은 복잡도 관리에 큰 이득이다.

또한 제약을 명시적 목록으로 가지면 오류 보고도 쉬워진다. 각 제약에 소스 범위(span)를 연관시킬 수 있고, 타입 오류가 났을 때 이 span을 이용해 더 똑똑한 오류 메시지를 출력할 수 있다. 이 장점들에 대한 더 자세한 설명은 Simon Peyton Jones의 LambdaAle 강연 Type Inference as Constraint Solving을 참고하라.

여기서 우리의 타입 추론 포부는 잠시 멈춰두자. AST, Type, 그리고 타입 추론 알고리즘은 구현을 위한 강력한 기반을 제공한다. 다음 글에서는 양방향 타입 시스템을 이용해 제약 생성을 구현할 것이다. 그리고 물론, 미리 건너뛰고 싶다면 전체 소스 코드는 동반 저장소에서 확인할 수 있다.