매치 타입

매치 타입 (Match Types)

**매치 타입(match type)**은 검사 대상(scrutinee)의 타입에 따라 오른쪽 변(right-hand side) 중 하나로 환원돼요. 예를 들어 볼게요:

type Elem[X] = X match
  case String => Char
  case Array[t] => t
  case Iterable[t] => t

출처: Scala 3 Reference

본문

이 타입은 다음과 같이 환원돼요:

Elem[String]       =:=  Char
Elem[Array[Int]]   =:=  Int
Elem[List[Float]]  =:=  Float
Elem[Nil.type]     =:=  Nothing

여기서 =:=는 왼쪽과 오른쪽이 서로의 하위 타입(subtype)임을 뜻해요.

일반적으로 매치 타입은 다음과 같은 형태를 가져요:

S match { P1 => T1 ... Pn => Tn }

여기서 S, T1, ..., Tn은 타입이고, P1, ..., Pn은 타입 패턴(type pattern)이에요. 패턴 안의 타입 변수는 예전과 마찬가지로 소문자로 시작해요.

매치 타입은 재귀적인 타입 정의의 일부가 될 수 있어요. 예:

type LeafElem[X] = X match
  case String => Char
  case Array[t] => LeafElem[t]
  case Iterable[t] => LeafElem[t]
  case AnyVal => X

재귀적인 매치 타입 정의에는 상한(upper bound)을 줄 수도 있어요:

type Concat[Xs <: Tuple, +Ys <: Tuple] <: Tuple = Xs match
  case EmptyTuple => Ys
  case x *: xs => x *: Concat[xs, Ys]

이 정의에서는 환원 가능 여부와 무관하게 Concat[A, B]의 모든 인스턴스가 Tuple의 하위 타입임이 보장돼요. 이는 재귀 호출 x *: Concat[xs, Ys]가 타입 검사를 통과하는 데 필요한 조건이에요. *:가 오른쪽 피연산자로 Tuple을 요구하거든요.

의존 타입 부여 (Dependent Typing)

매치 타입으로 **의존 타입이 부여된 메서드(dependently typed method)**를 정의할 수 있어요. 예를 들어, 앞서 정의한 LeafElem 타입의 값 레벨(value-level) 대응물이 있어요(결과 타입으로 매치 타입을 쓰는 점을 주목하세요):

type LeafElem[X] = X match
  case String => Char
  case Array[t] => LeafElem[t]
  case Iterable[t] => LeafElem[t]
  case AnyVal => X
def leafElem[X](x: X): LeafElem[X] = x match
  case x: String      => x.charAt(0)
  case x: Array[t]    => leafElem(x(0))
  case x: Iterable[t] => leafElem(x.head)
  case x: AnyVal      => x

매치 표현식을 위한 이 특별한 타입 부여 방식은 다음 조건들이 모두 충족될 때만 사용돼요:

• 매치 표현식의 패턴에 가드(guard)가 없을 때
• 매치 표현식 검사 대상의 타입이 매치 타입 검사 대상 타입의 하위 타입일 때
• 매치 표현식과 매치 타입의 케이스 개수가 같을 때
• 매치 표현식의 패턴이 모두 타입드 패턴(Typed Pattern)이면서, 그 타입들이 매치 타입 안의 대응하는 타입 패턴과 =:=일 때

참고로, 각 케이스 본문은 해당 매치 타입 케이스의 오른쪽에 있는 타입을 가져야 한다고 기대되지만, 그렇다고 매치 타입 인자가 제약된다는 뜻은 아니에요. 앞선 예시를 쓰면, 마지막 케이스 본문은 X를 따라야 하는데, 이것이 X를 AnyVal로 제약하지는 않아요. 그래서 본문 안의 LeafElem[X]는 환원되지 못하고 그대로 '막힌' 상태, 즉 추상 타입으로 남아 있게 되죠.

매치 타입의 표현 (Representation of Match Types)

매치 타입

S match { P1 => T1 ... Pn => Tn }

의 내부 표현은 Match(S, C1, ..., Cn) <: B이에요. 여기서 각 케이스 Ci는 다음과 같은 형태죠:

[Xs] =>> P => T

여기서 [Xs]는 패턴 Pi에 묶인 변수들의 타입 파라미터 절이에요. 케이스에 묶인 타입 변수가 없으면 타입 파라미터 절은 생략되고 함수 타입 P => T만 남아요. 따라서 각 케이스는 단항 함수 타입(unary function type)이거나, 단항 함수 타입에 대한 타입 람다(type lambda)예요.

B는 매치 타입의 선언된 상한이고, 그런 상한이 주어지지 않으면 Any예요. 논의에 영향을 주지 않는 곳에서는 생략할게요. 검사 대상, 상한, 패턴 타입은 모두 1차 타입(first-order type)이어야 해요.

매치 타입의 환원 (Match Type Reduction)

매치 타입의 환원은 매치 표현식의 의미론을 따르는데, 형태가 S match { P1 => T1 ... Pn => Tn }인 매치 타입은, 모든 s: S에 대해 s: S match { _: P1 => T1 ... _: Pn => Tn }이 타입 Ti의 값으로 평가될 때에만 Ti로 환원돼요.

컴파일러는 다음 환원 알고리즘을 구현해요:

• 검사 대상 타입 S가 값의 공집합(예: Nothing이나 String & Int)이면 환원하지 않는다.
• 각 패턴 Pi를 순서대로 살핀다.
  • S <: Pi이면 Ti로 환원한다.
  • 그렇지 않으면, S와 Pi가 서로소(disjoint)라는 증명을 시도한다. 다시 말해, 타입 S의 값 s가 동시에 타입 Pi가 될 수 없다는 증명을 시도하는 거예요.
  • 그런 증명을 찾으면 다음 케이스(Pi+1)로 넘어가고, 찾지 못하면 환원하지 않는다.

서로소 증명은 Scala 타입의 다음 성질들에 의존해요:

• 클래스의 단일 상속
• final 클래스는 확장될 수 없음
• 서로 다른 값을 가진 상수 타입(constant type)은 서로 교차하지 않음
• 서로 다른 값을 가리키는 싱글턴 경로는 교차하지 않음(예: 객체 정의나 싱글턴 enum 케이스)

S <: Pi를 계산할 때 패턴의 타입 파라미터는 최소로 인스턴스화(minimally instantiated)돼요. Xs의 모든 타입 변수가 공변적·불변적으로 나타나는 Is에서 가능한 한 작고, Xs의 타입 변수가 반변적으로 나타나는 Is에서는 가능한 한 크면, Xs에 대한 인스턴스화 Is는 최소예요. 여기서 '작다'와 '크다'는 <:를 기준으로 이해해요. 다만, 공변적 또는 반변적 위치의 람다 케이스에 대해 패턴이 매칭된다면 타입 파라미터는 '크게' 되지 않아요.

단순화를 위해 여기까지는 제약 처리(constraint handling)를 생략했어요. 하위 타입 검사의 완전한 정식화에서는 이를 "제약과 타입 쌍을 받아 성공과 새 제약을 돌려주거나 실패를 돌려주는 함수"로 설명해요. 환원 맥락에서는 하위 타입 검사 S <: [Xs := Is] P가 입력 제약 안의 모든 변수들의 범위를 그대로 두는 것으로 이해해요. 즉, 검사 대상을 패턴과 매칭함으로써 제약 안의 기존 변수들을 인스턴스화할 수 없어요.

매치 타입에 대한 하위 타입 규칙 (Subtyping Rules for Match Types)

매치 타입에는 다음 규칙들이 적용돼요. 단순화를 위해 환경과 제약은 생략해요.

1. 첫 번째 규칙은 두 매치 타입 사이의 구조적 비교예요:

S match { P1 => T1 ... Pm => Tm }  <:  T match { Q1 => U1 ... Qn => Un }

다음을 만족하면 성립해요:

S =:= T,  m >= n,  Pi =:= Qi and Ti <: Ui for i in 1..n

즉, 검사 대상과 패턴이 같고 대응하는 본문들이 하위 타입이어야 해요. 케이스 재배치(re-ordering)는 허용되지 않지만, 하위 타입이 슈퍼타입보다 더 많은 케이스를 가질 수는 있어요.

2. 두 번째 규칙은 매치 타입과 그 환원 결과(redux)가 서로의 하위 타입이라는 걸 말해요:

S match { P1 => T1 ... Pn => Tn }  <:  U
U  <:  S match { P1 => T1 ... Pn => Tn }

S match { P1 => T1 ... Pn => Tn }이 U로 환원되면 성립해요.

3. 세 번째 규칙은 매치 타입이 상한을 따른다는 거예요:

(S match { P1 => T1 ... Pn => Tn } <: B)  <:  B

종료 (Termination)

매치 타입 정의는 재귀적일 수 있어서, 매치 타입을 환원하는 동안 무한 루프에 빠질 가능성이 있어요.

환원이 하위 타입과 연결되어 있기 때문에, 우리는 이미 순환 감지 메커니즘을 갖추고 있어요. 덕분에 다음 코드는 이미 꽤 그럴듯한 오류 메시지를 보여줘요:

type L[X] = X match
  case Int => L[X]

def g[X]: L[X] = ???

   |  val x: Int = g[Int]
   |                ^
   |Recursion limit exceeded.
   |Maybe there is an illegal cyclic reference?
   |If that's not the case, you could also try to
   |increase the stacksize using the -Xss JVM option.
   |A recurring operation is (inner to outer):
   |
   |  subtype LazyRef(Test.L[Int]) <:< Int

내부적으로 Scala 컴파일러는 선택된 스택 오버플로우를 타입 오류로 바꿔서 이런 순환을 감지해요. 하위 타입 검사 중에 스택 오버플로우가 발생하면, 그 예외를 잡아서 오버플로우를 일으킨 하위 타입 검사들의 추적(trace)을 보여주는 컴파일 타임 오류로 바꾸죠. 전체 스택 트레이스를 보여주지는 않아요.

매치 타입의 변성 (Match Types Variance)

매치 타입 안의 모든 타입 위치(검사 대상, 패턴, 본문)는 **불변(invariant)**으로 간주돼요.

관련 연구 (Related Work)

매치 타입은 Haskell의 **닫힌 타입 패밀리(closed type families)**와 비슷한 점이 있어요. 차이점은 몇 가지가 있는데:

• 타입 등식(type equality) 대신 하위 타입(subtyping)을 쓴다.
• 매치 타입 환원은 기저 제약을 조이지 않지만, 타입 패밀리 환원은 통일(unify)한다. 이런 접근 방식의 차이는 Scala의 지역적 타입 추론(local type inference)과 Haskell의 전역적 타입 추론(global type inference)의 차이를 그대로 반영해요.