타입 추론에서 첫 번째 오류를 넘어가기

URL: https://thunderseethe.dev/posts/types-base/

Title: 타입 추론에서 첫 번째 오류를 넘어가기

언어 만들기

지난 글에서 우리는 완전하고 동작하는 타입 추론 시스템을 만들었다. 훌륭한 성취였고, 당시에는 완성품이었다. 나는 ‘언어 만들기’ 시리즈의 나머지를 쓰러 갔고, 여러분은 그걸 읽으러 갔다(그랬기를 바란다). 언어를 더 작성해 오면서 내 야망은 더 구체화되었다. 처음에 이 시리즈는 컴파일러를 쓰는 것을 목표로 했고, 사실 어떤 컴파일러든 충분히 도전적이기만 하면 됐다. 하지만 이제는 ‘그냥 아무 컴파일러’가 아니라, Language Server Protocol (LSP)을 지원하는 쿼리 기반 컴파일러가 될 것이다.

현대에 와서는 사용자가 편집 중에도 호출할 수 있도록 의도하며 컴파일러를 작성하는 것이 필수라고 생각한다. 한 번에 몰아서 컴퓨터에 넣기 위해 미리 펀치 카드를 조립하던 시대는 끝났다. 사람들은 휴대폰으로도 코드를 끄적일 수 있고, 그렇게 하는 동안 타입 오류가 어디 있는지 알려주길 기대한다. 하지만 우리의 꿈을 이루려면 타입 추론에 몇 가지 변화가 필요하다.

현재의 타입 추론은 아직 대화형(interactive) 사용을 처리할 준비가 되어 있지 않다. 대화형 사용에서는 부분적으로 구성된 입력도 우아하게 처리할 수 있어야 한다. 사용자가 함수 하나를 타이핑하는 도중이라도 파일 안의 나머지 함수들은 계속 타입 체크를 하고 싶다. 그 목표를 위해 타입 추론에 다음 세 가지 개선이 필요하다:

• Ast에 NodeId 추가
• 새로운 Ast 노드 Hole 추가
• 여러 오류 보고

NodeId는 트리의 각 노드마다 붙는 유일한 식별자다. 노드를 유일하게 식별할 수 있으면 AST에 대한 메타데이터를 추적하기가 쉬워진다. NodeId를 사용하면 각 노드의 타입을 추적하는 HashMap<NodeId, Type> 같은 해시맵을 둘 수 있다. 또는 컴파일러 프런트엔드를 구성하면서 각 AST 노드의 소스 위치를 추적하기 위해 HashMap<NodeId, Range<usize>>를 쓰고 싶을 수도 있다.

또한 새로운 Ast 케이스인 Hole이 필요하다. Hole은 AST의 빠진 부분을 나타낸다. 타입 추론 이전의 패스들이 잘못된 입력을 만나면 Hole을 만들어낼 것이다. 타입 추론은 Hole을 처리하되, 타입 추론을 막지 않으면서도 결과를 바꾸지 않도록 해야 한다. AST에 오류가 있다고 해서 올바른 타입의 추론까지 영향을 받으면 안 된다.

Hole은 우리가 이미 유효하지 않다고 판단한 프로그램의 일부를 블랙박스로 취급함으로써 이 목표를 달성한다. Hole도 타입을 가질 수 있지만, 항상 무엇과도 유니파이될 수 있는 타입 변수로서만 부여된다. Hole은 자체적으로 타입을 만들어내지 않으며, Hole과의 어떤 유니피케이션도 성공한다.

마지막으로, 첫 번째 오류에서 멈추지 말고 여러 오류를 보고하고 싶다. 이 과정에서는 주의가 필요하다. 하나의 오류가 도움이 안 되는 연쇄 오류를 대량으로 만들어내기 쉽다. 우리는 AST의 특정한 잘못된 조각에 대해 단 하나의 오류만 제공하되, AST의 서로 다른 여러 잘못된 부분을 보고할 수 있기를 원한다.

AST 식별 추가하기 Link to heading

타입 추론에서 NodeId를 추가하는 일은 간단하다. 우리는 ID를 생성하는 책임을 지지 않기 때문이다. Var와 마찬가지로, 어떤 이전 패스가 NodeId를 올바르게 조립해서 우리에게 넘겨준다고 가정한다. Var와의 유사성은 여기서 끝나지 않는다. NodeId 역시 u32를 감싼 래퍼일 뿐이다:

struct NodeId(u32);

새로운 NodeId는 Ast의 각 케이스에 박혀 들어간다:

#[derive(Debug, Eq, Clone)]
pub enum Ast<V> {
  /// A local variable
  Var(NodeId, V),
  /// An integer literal
  Int(NodeId, i32),
  /// A function literal (lambda, closure).
  Fun(NodeId, V, Box<Ast<V>>),
  /// Function application
  App(NodeId, Box<Ast<V>>, Box<Ast<V>>),
}

좀 반복적인데

모든 노드에 NodeId가 있다면, 이를 별도 필드로 빼낼 수는 없을까?

struct Ast<V> {
  id: NodeId,
  kind: AstKind<V>
}
enum AstKind<V> {
  Var(V),
  Fun(V, Box<V>),
  // ...the rest of our cases
}

물론 가능하다! 사실 많은 프로덕션 컴파일러에서는 이 방식이 일반적이다. 사람들은 모든 노드에 메타데이터를 붙이는 것을 정말 좋아한다. 다만 우리는 이 표현을 생략하기로 했다. 이런 표현은 패턴 매칭을 더 장황하게 만들고, 우리는 가독성에 초점을 두고 있기 때문이다. 다음 같은 코드를 쓰고 싶지 않았다:

Ast {
  id: ast.id,
  kind: match ast.kind {
    //...
  }
}

하지만 이는 순전히 스타일 취향이다. 여러분의 언어에서는 원하는 대로 하라.

이제 노드들이 식별 가능해졌다. AST에 메타데이터를 붙이기 시작할 수 있다. 뒤에서 보겠지만, 우리는 HashMap<NodeId, TypeError>로 트리에 오류를 붙이는 데 이를 사용할 것이다.

그런데 이 문제에 NodeId가 정말 최선의 해법일까? HashMap<Ast, TypeError> 같은 걸로 대신하면 번거로움을 줄일 수 있지 않을까? 즉각적인 문제가 하나 있다. Ast에는 정체성(identity) 개념이 없다. 예를 들어 Int(3)이 두 번 나타나는 AST에서, 하나에는 오류를 붙이고 다른 하나에는 붙이지 않고 싶을 수 있다. 하지만 둘 다 해시맵에서는 같은 키로 해시된다. NodeId는 서로 다른 두 Int(3) 인스턴스에 대해 서로 다른 유일 u32를 제공하므로, 해시맵에서 다른 키를 갖게 된다.

성능이라는 더 현실적인 걱정도 있다. 노드를 키로 하는 해시맵은 키로 쓰기 위해 노드 전체를 복사하고, 그것을 해싱한다. 성능이 우리의 최우선 고려 사항은 아니지만, 큰 트리에서는 비용이 꽤 커진다. NodeId는 노드 크기와 무관하게 u32 하나만 해시하면 된다.

사이드 테이블을 Ast로 키잉하는 것만으로는 부족하다. 우리는 노드의 내용(content)뿐 아니라 AST에서의 **위치(position)**도 추적하고 싶다. 좋아, 위치를 추적해야 한다면 Ast에 메타데이터를 직접 붙이면 되지 않을까? 우리는 AST를 구성하는 과정에서 노드 인스턴스를 여러 개 만들기도 한다. 각 노드가 자신의 메타데이터를 가지고 있다면 메타데이터 인스턴싱은 공짜 아닌가? 메타데이터를 Ast에 직접 박아 넣는 건 쉬울 것이다:

struct Ast<V> {
  kind: AstKind<V>,
  error: Option<TypeError>,
  type: Type,
}
enum AstKind<V> {
  Var(V),
  Fun(V, Box<V>),
  // ...the rest of our cases
}

이 접근은 분명히 동작하며, Ast를 키로 쓰는 것보다 낫다. 하지만 우리는 관심사의 분리가 잘 되지 않기 때문에 이 방식을 피한다. 이제 Ast 노드를 만들 때, 모든 패스에서 관심 가질 수 있는 메타데이터를 항상 제공해야 한다:

Ast {
  kind: Var(Var(0)),
  error: None,
  ty-
}

아차, 타입에는 뭘 넣지? 아직 타입 체크를 안 했는데, 나중에 대체될 걸 알면서 아무 타입이나 찍어야 하나? 그리고 type을 어떻게 대체하지? 지금까지 Ast는 불변(immutable)이었다. 그럼 가변으로 만들어야 하는 건가.

메타데이터를 다 묶어 넣으면 컴파일의 모든 단계에서 그 모든 메타데이터를 다 상대해야 한다. 내게는 이것이 더 취약한 코드로 이어지고, 불변조건(invariant)을 더 쉽게 망치게 만든다고 느껴진다. 메타데이터를 HashMap<NodeId, Metadata>에 넣으면, 각 사용 사례에 맞는 관련 메타데이터만 들고 다닐 수 있다. 필요한 데이터만 유지하고 이를 Ast 자체와 분리하면, 컴파일러 패스들 사이의 결합도를 더 잘 낮출 수 있다.

Note

여기서는 해시맵을 선호하며 메타데이터를 트리에 박아 넣는 것을 곁눈질하고 있지만, 이는 트레이드오프다. 추가 해시맵을 들고 다니는 것도 공짜가 아니고, 노드 ID에 대한 해시 룩업도 공짜가 아니다. 실제 컴파일러에서는 특히 자주 쓰이는(또는 충분히 작은) 데이터는 트리에 넣어두는 등, 혼합된 접근을 흔히 볼 수 있다. 별도 컬렉션에 두면 성능이 의미 있게 떨어지기 때문이다.

홀리 AST, 배트맨! Link to heading

다음 리노베이션은 AST에 새 케이스를 추가하는 것이다:

enum Ast<V> {
  // ...our existing cases
  Hole(NodeId, V),
}

Hole은 오류 보정(error correction)에 관한 것이다. 컴파일러는 반쯤 만들어진 상태의 코드를 보게 될 것이다. Hole은 (현재 시점에서) 유효하지 않은 AST의 일부를 나타낸다. 본질적으로, 유효하지 않은 부분을 블랙박스로 취급함으로써 AST를 막힘 없이 처리하게 해준다.

사용자가 매개변수는 올바르지만 본문은 잘못된 부분 함수(partial function)를 구성한다고 상상해보자. 우리는 이를 다음처럼 표현할 수 있다:

Fun(Var(0), Hole(Var(1)))

Hole이 단지 NodeId가 아니라 변수 V를 들고 있는 이유를 생각해볼 가치가 있다. 한 가지 이유는 진단(diagnostics)에서 홀에 이름을 붙일 수 있으면 편리하기 때문이다. 더 중요한 이유는 TypedVar를 통해 Hole 노드에 타입을 붙일 수 있기 때문이다.

Hole의 타입을 추론하는 목표는 그것의 타입을 정확히 결정하는 것이 아니다. 홀은 프로그램의 유효하지 않은 구간을 나타내므로 그건 불가능하다는 것을 이미 알고 있다. 홀은 단지 유효한 프로그램 구간에 대해 타입 추론이 진행되도록 막힌 것을 풀어주는 역할을 한다. 우리의 논리는 “유효하지 않은 AST는 어떤 타입에도 기꺼이 들어갈 수 있다”이다.

여기서는 폭발 원리(principle of explosion)가 작동한다. 유효하지 않은 AST는 우리의 불변조건을 모순시키므로, 거기서 무엇이든 도출해도 된다. 무한 루프를 도는 함수가 어떤 타입을 반환한다고 취급할 수 있는 것과 같다. 어떤 타입을 고르든 그 함수는 절대 반환하지 않으니 공허하게(vacuously) 참이다.

홀에는 어떤 타입이든 부여할 수 있지만, 타입은 신중하게 골라야 한다. 기술적으로는 모든 홀에 Int 타입을 줄 수도 있다. 그러나 그렇게 하면 홀이 타입 추론에 과도한 영향을 미친다. 홀이 타입 변수를 만나면 그 변수는 Int와 유니파이되어 버리고, 이는 타입 추론 결과를 의미 있게 바꿔버린다. 홀의 타입 지정에서 우리의 목표는 홀을 방해물에서 치워서, AST의 유효한 부분을 타이핑하는 중요한 작업으로 돌아가는 것이다.

타입이 달린 홀(typed hole)을 쓰는 아이디어는 Hazel의 논문 Total Type Error Localization and Recovery with Holes에서 가져왔다. 강력 추천한다. 이 논문은 타입 홀을 도입하고, 점진적 타이핑(gradual typing)을 약간 사용해 타입 추론을 방해하지 않게 만드는 방법을 설명한다. 각 홀에는 어떤 타입과도 유니파이되는 오류 타입(기호는 ?)이 할당된다. ?가 어떤 타입과도 같게 만듦으로써, 홀은 스스로 타입 오류를 만들지 않고 유효한 AST의 타입 추론에도 영향을 주지 않는다.

우리는 유사한 아이디어를 쓰되, 목적을 달성하는 기존 개념인 타입 변수를 재사용하겠다. 홀에는 항상 새로운 타입 변수를 할당한다. Hazel의 오류 타입처럼, 새 타입 변수는 어떤 타입과도 유니파이될 수 있다. 다만 오류 타입과 달리, 첫 유니피케이션 이후에는 타입 변수가 해결(solved)되므로, 다른 타입을 만나면 홀의 유니피케이션이 실패할 가능성이 생긴다. 실제로는 문제가 되지 않는다고 느꼈지만, 우리 언어에는 아직 분기(branching) 구성 요소가 없으니 나중에 내가 틀렸음을 인정해야 할지도 모른다.

Hole을 위한 타입 추론 변경은 실제로는 최소한이다. infer에 케이스 하나를 추가한다:

Ast::Hole(id, v) => {
  let var = self.fresh_ty_var();
  (
    GenOut::new(vec![], Ast::Hole(id, TypedVar(v, Type::Var(var)))),
    Type::Var(var),
  )
}

홀은 검사하지 않는다. 끝.

다수의 오류들 Link to heading

마지막 수정 사항은 첫 번째 오류에서 멈추지 않고 여러 오류를 보고하는 것이다. 타입 추론의 첫 단계인 infer와 check는 항상 제약(constraint) 목록을 만들어낸다. 여기에서는 오류 보고를 걱정할 필요가 없다. 제약을 오류 보고에 더 적합하게 수정할 필요는 있겠지만, 우리의 노력은 유니피케이션에 집중될 것이다.

먼저 여러 오류를 저장할 방법이 필요하다. TypeInference에 새 필드를 추가한다:

struct TypeInference {
  // ... our previous fields
  errors: HashMap<NodeId, TypeError>,
}

Hazel에서 또 하나 가져온 아이디어로, 우리는 트리에 타입 오류를 마킹(mark up)한다. 이렇게 하면 두 가지를 달성한다: 어떤 노드든 오류는 최대 하나만 갖고, 트리의 계층 구조가 오류의 계층 구조를 제공한다. 어떤 노드에 오류가 있으면, 그 하위 노드에 붙은 오류는 무의미하다는 것을 알 수 있으므로 무시할 수 있다. 물론 하위 노드 오류가 유용하다고 생각하면 보고해도 된다. 핵심은 한 뿌리 문제로 인해 오류가 폭발적으로 증가하는 것을 막을 수 있어야 한다는 것이다.

여러 오류를 보고하는 김에, 우리가 보고하는 오류도 개선하려 한다. 그러려면 TypeError에 새 케이스들이 필요하다:

enum TypeError {
  InfiniteType {
    type_var: TypeVar,
    ty: Type,
  },
  UnexpectedFun {
    expected_ty: Type,
    fun_ty: Type,
  },
  AppExpectedFun {
    inferred_ty: Type,
    expected_fun_ty: Type,
  },
  ExpectedUnify {
    checked: Type,
    inferred: Type,
  },
}

InfiniteType과 ExpectedUnify 두 케이스는 익숙하지만 이름이 바뀌었다. 이 둘이 과거 TypeError의 두 케이스였다. 새로 추가된 두 케이스도 구조적으로는 ExpectedUnify와 같다: 타입 두 개. 실제로 이 두 케이스는 너무 비슷해서, 유니피케이션은 이들을 동일하게 취급한다. unify_ty_ty는 예전 TypeError처럼 생긴 UnificationError를 생성한다:

enum UnificationError {
  TypeNotEqual(Type, Type),
  InfiniteType(TypeVar, Type),
}

unification은 UnificationError를 TypeError로 바꾼다. 이는 UnexpectedFun과 AppExpectedFun이 TypeNotEqual과 동일한 정보를 담고 있기 때문에 가능하다. 이들은 단지 “불일치가 어디서 발생했는지”를 명시하여 더 구체적인 오류 메시지를 보고할 수 있게 한다. 유니피케이션 단계에 도달할 즈음에는, 오류가 어디에서 발생했는지를 알려주는 Ast는 버려졌다. 우리는 Constraint가 이 정보를 AST에서 유니피케이션으로 전달해주길 기대한다. 제약은 provenance(근거/출처)라는 새 타입을 사용해 이를 수행한다:

enum Provenance {
  UnexpectedFun(NodeId),
  AppExpectedFun(NodeId),
  ExpectedUnify(NodeId),
}

자, 이게 TypeError로 어떻게 매핑될지 너무 뻔하지 않은가. 각 NodeId는 오류가 난 AST 노드를 가리킨다. 노드를 유일하게 식별하는 또 하나의 이점이다. 이 새 타입을 Constraint에 넣는다:

enum Constraint {
  // TODO: NodeId might be better represented by some kind of like provenance. Not sure yet.
  TypeEqual(Provenance, Type, Type)
}

알고 보니 그 주석은 기묘하게 예지력이 있었다. 블로그 같은 문서도 썩어간다는(docs bitrot) 교훈을 준다. 이제 제약을 발생시키는 곳마다 provenance를 제공해야 한다.

이 변화는 말보다 더 큰 변화다. 오류 보고를 위해 단순히 각 제약을 수정하는 것만으로는 부족하다. 우리는 오류를 더 잘 보고하기 위해 타입을 추론하는 방식 자체를 바꿀 것이다. 첫 번째 변화는 App에서 함수 타입을 인자 타입보다 먼저 추론하도록 하는 것이다:

Ast::App(id, fun, arg) => {
  let fun_id = fun.id();
  let (fun_out, supposed_fun_ty) = self.infer(env.clone(), *fun);
  let mut constraint = fun_out.constraints;
  let (arg_ty, ret_ty) = match supposed_fun_ty {
    Type::Fun(arg, ret) => (*arg, *ret),
    ty => {
      let arg = self.fresh_ty_var();
      let ret = self.fresh_ty_var();

      constraint.push(Constraint::TypeEqual(
        Provenance::AppExpectedFun(fun_id),
        ty,
        Type::fun(Type::Var(arg), Type::Var(ret)),
      ));

      (Type::Var(arg), Type::Var(ret))
    }
  };

  let arg_out = self.check(env, *arg, arg_ty);
  constraint.extend(arg_out.constraints);
  (
    GenOut::new(
      constraint,
      Ast::app(id, fun_out.typed_ast, arg_out.typed_ast),
    ),
    ret_ty,
  )
}

이제 함수에 대해 infer를 호출하고, 결과가 함수 타입인지 확인한다. 함수 타입이 아니라면, 새 함수 타입(새 타입 변수들로 구성)에 대한 제약을 추가하는데, 이때 새 provenance인 AppExpectedFun을 사용한다. 원래는 인자 타입을 먼저 추론하고 그것으로 함수 타입을 체크했다. 이 접근은 타입 변수를 아주 잘 활용하지만, “인자가 함수가 아닌 대상에 적용되었다”는 상황을 판별하기 어렵다.

다음 provenance는 check 수정이다:

(Ast::Fun(id, arg, body), ty) => {
  let mut constraints = vec![];
  let (arg_ty, ret_ty) = match ty {
    Type::Fun(arg, ret) => (*arg, *ret),
    ty => {
      let arg = self.fresh_ty_var();
      let ret = self.fresh_ty_var();

      constraints.push(Constraint::TypeEqual(
        Provenance::UnexpectedFun(id),
        ty,
        Type::fun(Type::Var(arg), Type::Var(ret)),
      ));

      (Type::Var(arg), Type::Var(ret))
    }
  };
  let env = env.update(arg, arg_ty.clone());
  let body_out = self.check(env, *body, ret_ty);
  constraints.extend(body_out.constraints);
  GenOut {
    constraints,
    typed_ast: Ast::fun(id, TypedVar(arg, arg_ty), body_out.typed_ast),
  }
}

이전에는 매치 암이 (Ast::Fun(...), Type::Fun(...))였고, 함수가 함수 타입을 만날 때만 발화했다. 이제는 어떤 ty든 매치하고, 그 타입이 함수 타입이 아니면 UnexpectedFun provenance를 사용해 제약을 생성한다. 이전 방식에서는 함수가 아닌 타입일 때 (ast, expected_ty) 케이스로 떨어져 거기서 제약을 만들게 했다. 하지만 provenance를 지정하고 싶으므로 함수 케이스에서 직접 처리해야 한다.

마지막으로 가장 소박한 변화는 (ast, expected_ty)에서 일어난다:

(ast, expected_ty) => {
  let id = ast.id();
  let (mut out, actual_ty) = self.infer(env, ast);
  out.constraints.push(Constraint::TypeEqual(
    Provenance::ExpectedUnify(id),
    expected_ty,
    actual_ty,
  ));
  out
}

동작은 사실상 같지만, 제약에 ExpectedUnify provenance를 붙인다. 제약은 provenance를 들고 unification까지 가며, 거기서 오류를 구성한다:

if let Err(kind) = self.unify_ty_ty(left, right) {
  let (node_id, mark) = match kind {
    UnificationError::InfiniteType(type_var, ty) => (
      provenance.id(), 
      TypeError::InfiniteType { type_var, ty }
    ),
    UnificationError::TypeNotEqual(left, right) => match provenance {
      Provenance::UnexpectedFun(node_id) => (
        node_id,
        TypeError::UnexpectedFun {
          expected_ty: left,
          fun_ty: right,
        },
      ),
      Provenance::AppExpectedFun(node_id) => (
        node_id,
        TypeError::AppExpectedFun {
          inferred_ty: left,
          expected_fun_ty: right,
        },
      ),
      Provenance::ExpectedUnify(node_id) => (
        node_id,
        TypeError::ExpectedUnify {
          checked: left,
          inferred: right,
        },
      ),
    },
  };
  self.errors.insert(node_id, mark);
}

여기서 UnificationError와 Provenance가 결합되어 TypeError를 만든다. 새 오류는 errors에서 해당 node_id를 마킹한다. 이렇게 해서 끝이다. 타입 추론에서 여러 오류를 보고할 수 있게 됐다.

강력한 힘에는 type_infer 시그니처의 변화가 따른다. 이제 여러 오류가 있을 수 있으니 Result<(Ast<TypedVar>, TypeScheme), TypeError>를 반환하는 것은 더 이상 말이 안 된다. (와, 정말 길다.) Result<(Ast<TypedVar>, TypeScheme), HashMap<NodeId, TypeError>>를 반환할 수도 있겠지만, 이미 축 처진 반환 타입에 더 부담을 주기보다, 타입이 달린 AST와 그 오류들을 둘 다 반환하기로 한다:

struct TypeInferOut {
  ast: Ast<TypedVar>,
  scheme: TypeScheme,
  errors: std::collections::HashMap<NodeId, TypeError>,
}

type_infer는 타입이 달린 AST와 오류를 모두 담은 TypeInferOut을 반환한다. 오류와 AST를 함께 반환하는 동기는 대화형 사용을 지원하기 위해서다. 처음 문제가 보이면 AST 전체를 버리는 대신, 오류가 있더라도 AST에서 건질 수 있는 것을 최대한 건지고 싶다. 또한 AST를 포함하면 다른 프런트엔드 패스들로 오류를 전달해 진단을 보고할 때, 오류를 해당 패스의 AST와 매칭하기가 쉬워진다. 우리는 이런 오류 내성을 **resilience(회복탄력성)**라고 부른다.

대화형 사용을 위해서는 모든 프런트엔드 패스가 회복탄력적이어야 한다. 하지만 그건 미래 글의 문제다. 지금은 회복탄력적인 타입 추론을 달성했다. 여기서 우리는 타입이 달린 AST를 로워링으로 이어가거나, 타입 추론을 계속해서 로우 타입(row types)으로 나아갈 수 있다.