타입 추론

타입 추론 (Type inference)

제네릭 함수를 쓸 때 모든 타입 인자를 항상 직접 적으셔야 할까요? 아닙니다. Go는 함수를 사용하는 문맥(context) 에서 빠진 타입 인자를 알아서 추론해 줘요. 이때 추론의 근거가 되는 게 함수 타입 파라미터의 constraint까지 포함된 주변 상황이에요. 타입 인자를 추론할 수 있고, 그 추론된 타입 인자로 instantiation(인스턴스화)까지 성공하면 타입 추론은 성공해요. 반대로 성공하지 못하면 타입 추론은 실패하고, 프로그램은 유효하지 않게 돼요.

타입 추론의 핵심은 타입 쌍 사이의 관계를 이용한다는 점이에요. 예를 들어 함수 인자는 해당 함수 파라미터에 assignable(할당 가능)해야 하죠. 이 사실 하나가 인자의 타입과 파라미터의 타입 사이에 관계를 만들어 줍니다. 이 두 타입 중 하나라도 타입 파라미터를 포함하고 있다면, 타입 추론은 그 할당 가능 관계가 만족되도록 타입 파라미터를 대체할 타입 인자를 찾아요. 비슷하게, 타입 인자는 자기 파라미터의 constraint를 satisfy(만족)해야 한다는 사실도 추론에 이용돼요.

출처: Go Specification

본문

이렇게 서로 맞춰진 타입 쌍 하나하나는 type equation(타입 방정식)에 대응돼요. 하나의 방정식에는 하나 또는 여러 개의 타입 파라미터가 들어갈 수 있고, 그 타입 파라미터는 하나의 제네릭 함수에서 왔을 수도, 여러 제네릭 함수에서 왔을 수도 있어요. 타입 인자를 추론한다는 건, 바로 이렇게 모인 타입 방정식 묶음을 해당 타입 파라미터들에 대해 푸는 일이에요.

예를 들어 다음 코드를 볼게요.

// dedup returns a copy of the argument slice with any duplicate entries removed.
func dedup[S ~[]E, E comparable](S) S { … }

type Slice []int
var s Slice
s = dedup(s)   // same as s = dedup[Slice, int](s)

프로그램이 유효하려면 타입 Slice를 가진 변수 s가 함수 파라미터 타입 S에 할당 가능해야 해요. 그런데 여기서 타입 추론은 할당의 방향성을 무시해요. 복잡도를 줄이기 위해서죠. 그래서 Slice와 S 사이의 타입 관계를 (대칭적인) type equation Slice ≡ₐ S로 표현할 수 있어요 — 반대로 S ≡ₐ Slice로 써도 상관없구요. 여기서 ≡ₐ의 아래첨자 ₐ는 LHS와 RHS 타입이 assignability(할당 가능성) 규칙에 따라 맞아야 한다는 뜻이에요. 자세한 내용은 type unification 섹션을 참고하세요.

마찬가지로, 타입 파라미터 S는 자기 constraint인 ~[]E를 만족해야 해요. 이건 S ≡꜀ ~[]E로 표현할 수 있어요. 여기서 X ≡꜀ Y는 "X는 constraint Y를 만족한다"는 뜻이에요. 정리하면 방정식 두 개가 나옵니다.

	Slice ≡ₐ S      (1)
	S     ≡꜀ ~[]E   (2)

이제 이 방정식들을 타입 파라미터 S와 E에 대해 풀 수 있어요. (1)에서 컴파일러는 S의 타입 인자가 Slice임을 추론해요. 그리고 Slice의 underlying type이 []int이고, 그 []int가 constraint의 []E와 맞아야 하므로, 컴파일러는 E가 int여야 한다고 추론합니다. 그래서 이 두 방정식에 대해 타입 추론은 다음을 얻어요.

	S ➞ Slice
	E ➞ int

type equation 묶음이 주어지면, 풀어야 할 타입 파라미터는 인스턴스화가 필요한 함수들의 타입 파라미터이면서, 동시에 명시적 타입 인자가 따로 제공되지 않은 것들이에요. 이런 타입 파라미터를 bound type parameter(바운드 타입 파라미터)라고 불러요. 위 dedup 예시에서 S와 E는 dedup에 bound된 거예요. 그리고 제네릭 함수 호출의 인자가 그 자체로 제네릭 함수일 수도 있는데, 그러면 그 함수의 타입 파라미터도 bound 타입 파라미터 묶음에 포함돼요. 함수 인자의 타입은 다른 함수의 타입 파라미터(예를 들어 함수 호출을 감싸는 제네릭 함수의 타입 파라미터)를 포함할 수도 있어요. 그런 타입 파라미터들은 type equation에는 나타날 수 있지만, 그 문맥에서는 bound되지 않아요. type equation은 항상 bound 타입 파라미터에 대해서만 풀려요.

타입 추론이 지원하는 범위는 두 가지예요. 첫째, 제네릭 함수의 호출이에요. 둘째, 제네릭 함수가 (제네릭이 아닌) 함수 타입에 assignable해야 하는 어떤 문맥에서든 제네릭 함수를 사용하는 경우예요. 두 번째에는 제네릭 함수를 변수에 할당하거나(다른 함수에 인자로 넘기는 것 포함), 제네릭 함수를 함수 타입으로 변환하는 일 등이 들어가요.

타입 추론은 이 각각의 경우에 맞는 방정식 묶음 위에서 동작해요. 방정식은 다음과 같아요 (가독성을 위해 타입 인자 목록은 생략할게요):

  • 함수 호출 f(a₀, a₁, …)에서, f 또는 함수 인자 aᵢ가 제네릭 함수인 경우: f의 대응되는 함수 인자와 파라미터의 각 쌍 (aᵢ, pᵢ)에서, aᵢ가 untyped constant가 아니라면 방정식 typeof(pᵢ) ≡ₐ typeof(aᵢ)가 생겨요. 만약 aᵢ가 untyped constant cⱼ이고, typeof(pᵢ)가 bound 타입 파라미터 Pₖ라면, 쌍 (cⱼ, Pₖ)는 type equation과는 별도로 모아둬요.
  • 제네릭 함수 f가 (제네릭이 아닌) 함수 타입 T에 assignable해야 하는 문맥에서: typeof(f) ≡ₐ T.

추가로, 각 타입 파라미터 Pₖ와 그에 대응하는 type constraint Cₖ는 type equation Pₖ ≡꜀ Cₖ를 만들어요.

타입 추론은 typed operand에서 얻은 타입 정보를 untyped constant보다 우선해요. 그래서 추론은 두 단계로 진행됩니다.

  1. type unification(타입 유니피케이션)을 이용해 bound 타입 파라미터에 대해 type equation을 푼다. unification이 실패하면 타입 추론도 실패해요.
  2. 아직 타입 인자가 추론되지 않은 각 bound 타입 파라미터 Pₖ에 대해, 같은 타입 파라미터를 가진 쌍 (cⱼ, Pₖ)이 하나 이상 모였다면, 그 모든 쌍의 상수 cⱼ들의 constant kind를 constant expressions에서와 같은 방식으로 결정해요. 그 Pₖ에 대한 타입 인자는 결정된 constant kind의 default type이 돼요. constant kind가 서로 충돌해서 결정할 수 없다면 타입 추론은 실패해요.

이 두 단계를 거치고도 모든 타입 인자를 찾지 못했다면 타입 추론은 실패해요. 반대로 두 단계가 모두 성공하면, 타입 추론은 각 bound 타입 파라미터에 대한 타입 인자를 결정한 거예요:

	Pₖ ➞ Aₖ

타입 인자 Aₖ는 **합성 타입(composite type)**일 수 있어요. 즉 다른 bound 타입 파라미터 Pₖ를 요소 타입으로 담고 있거나(심지어 그냥 또 다른 bound 타입 파라미터일 수도 있어요), 반복적인 단순화 과정을 거치면서 각 타입 인자 안의 bound 타입 파라미터가 해당 타입 파라미터의 타입 인자로 치환돼요. 이 과정은 각 타입 인자가 bound 타입 파라미터에서 완전히 자유로워질 때까지 반복돼요.

만약 타입 인자들이 bound 타입 파라미터를 통해 자기 자신을 가리키는 순환 참조를 포함하게 되면, 단순화가 실패하고 따라서 타입 추론도 실패해요. 그렇지 않으면 타입 추론은 성공합니다.

Type unification (타입 유니피케이션)

타입 추론은 type unification을 통해 type equation을 풀어요. unification은 방정식의 LHS와 RHS 타입을 재귀적으로 비교해요. 이때 어느 한쪽 또는 양쪽 모두가 bound 타입 파라미터이거나 그것을 포함할 수 있고, LHS와 RHS가 (문맥에 따라 동일해지거나 할당 호환이 되도록) 맞아떨어지게 하는 타입 인자를 찾아요.

이를 위해 타입 추론은 bound 타입 파라미터 → 추론된 타입 인자의 매핑(map)을 유지해요. 이 map은 unification 중에 조회되고 갱신됩니다. 처음에는 bound 타입 파라미터들이 알려져 있지만 map은 비어 있어요. unification 중에 새로운 타입 인자 A가 추론되면, 타입 파라미터에서 인자로 가는 P ➞ A 매핑이 map에 추가돼요. 반대로 타입을 비교할 때, 이미 알려진 타입 인자(map에 항목이 존재하는 타입 인자)는 해당 타입 파라미터 자리를 대신해요. 추론이 진행될수록 map은 점점 채워지고, 모든 방정식을 고려하거나 unification이 실패할 때까지 계속돼요. unification 단계가 하나도 실패하지 않고, map이 모든 타입 파라미터에 대한 항목을 갖추면 타입 추론은 성공해요.

예를 들어 bound 타입 파라미터 P가 포함된 다음 type equation을 볼게요.

	[10]struct{ elem P, list []P } ≡ₐ [10]struct{ elem string; list []string }

타입 추론은 빈 map에서 시작해요. unification은 먼저 LHS와 RHS 타입의 최상위 구조를 비교합니다. 둘 다 길이가 같은 배열이므로, 요소 타입이 유니파이되면 이 둘도 유니파이돼요. 두 요소 타입 모두 struct이므로, 필드 수와 필드 이름이 같고 필드 타입이 유니파이되면 됩니다. P의 타입 인자는 아직 알려지지 않았으므로(map에 항목이 없으므로), P를 string과 유니파이하면 P ➞ string 매핑이 map에 추가돼요. 이제 list 필드의 타입을 유니파이하려면 []P와 []string을, 즉 P와 string을 유니파이해야 해요. 이 시점에 P의 타입 인자는 알려져 있으므로(map에 P 항목이 있으므로), 그 타입 인자 string이 P 자리를 대신해요. 그리고 string은 string과 동일하므로 이 unification 단계도 성공합니다. LHS와 RHS의 유니파이가 끝났어요. type equation이 하나뿐이고, 실패한 unification 단계가 없고, map이 완전히 채워졌으므로 타입 추론은 성공해요.

unification은 두 타입이 identical(동일)해야 하는지, assignment-compatible(할당 호환)이어야 하는지, 아니면 구조적으로만 같으면 되는지에 따라 exact(정확) unification과 loose(느슨한) unification을 조합해서 사용해요. 각각의 type unification rules는 Appendix에 자세히 적혀 있어요.

X ≡ₐ Y 형태의 방정식, 즉 X와 Y가 할당(파라미터 전달과 return 문 포함)에 관여하는 타입인 경우에는, 최상위 타입 구조는 느슨하게 유니파이될 수 있지만 요소 타입은 정확히 유니파이돼야 해요. 이는 할당 규칙과 일치해요.

P ≡꜀ C 형태의 방정식, 즉 P가 타입 파라미터이고 C가 그에 대응하는 constraint인 경우에는 unification 규칙이 조금 더 복잡해요:

  • C의 타입 집합에 있는 모든 타입의 underlying type이 같은 U이고, P가 알려진 타입 인자 A를 가진다면, U와 A는 느슨하게 유니파이되어야 해요.
  • 마찬가지로, C의 타입 집합에 있는 모든 타입이 같은 요소 타입과 충돌하지 않는 채널 방향을 가진 채널 타입이고, P가 알려진 타입 인자 A를 가진다면, C의 타입 집합에서 가장 제한적인 채널 타입과 A는 느슨하게 유니파이되어야 해요.
  • P가 알려진 타입 인자가 없고, C가 underlying(tilde) 타입이 아닌 정확히 하나의 type term T를 포함한다면, unification은 P ➞ T 매핑을 map에 추가해요.
  • C가 위에서 설명한 U 타입을 갖고 있지 않고, P가 알려진 타입 인자 A를 가진다면, A는 C의 모든 메서드를(있으면) 가져야 하고, 대응하는 메서드 타입은 정확히 유니파이되어야 해요.

type constraint로부터 type equation을 풀 때, 하나의 방정식을 푸는 게 추가 타입 인자를 추론할 수 있고, 그게 다시 그 타입 인자에 의존하는 다른 방정식을 풀 수 있게 만들어줘요. 그래서 타입 추론은 새로운 타입 인자가 추론되는 한 unification을 반복합니다.

더 알아보기