태그드 유니온과 패턴 매칭이 AST/IR 구현에서 실제로 주는 이점과 한계, 그리고 더 강력한 패턴 매칭으로 나아갈 여지를 살펴본다.
최근 Nelson Elhage가 뉴스레터 글 Tagged unions are overrated를 올렸다. 그 글에서 그는 기존 언어들에서 태그드 유니온과 패턴 매칭이 가진 몇 가지 문제를 설명하고, 태그드 유니온을 쓰지 않고도 언어의 AST와 IR을 충분히 괜찮게 구성할 수 있는 방법을 이야기한다.
(계속 읽기 전에 링크된 글을 먼저 읽는 것을 추천한다.)
Nelson은 여러 분야에서 일해 온 숙련된 엔지니어다. 특히 Ruby용 타입 체커인 Sorbet을 C++로 만들었고, 이는 꽤 빠르다.
나는 Nelson만큼의 경험이 있지는 않지만, 지난 약 1.5년 동안 C++로 작성된 컴파일러를 작업해 왔고, C++에 대한 개인적인 경험은 Nelson의 것과 꽤 달랐다. 내 개인 취향을 대략 가늠할 수 있도록 말하자면, 바인딩을 동반한 패턴 매칭(즉, 매칭을 하면서 페이로드를 이름에 바인딩하는 것)과 철저성(exhaustivity) 검사에 대한 언어 지원은 내가 C++을 작성할 때 가장 그리워하는 단 하나의 기능이라고까지 말할 수 있고, 그 감정은 시간이 지나도 크게 바뀌지 않았다.
그래서 내 관점과 Nelson의 관점 사이에 왜 이렇게 큰 단절이 생기는지 더 깊이 파고들어 보면 흥미롭겠다고 생각했다.
글의 앞부분에서 Nelson은 다음과 같이 지적한다.
At this point I’ve worked on a number of compilers, both toy and production, in a wide range of languages, including Go, C++, Java, Rust, and Haskell. With that experience, my considered opinion is this: Tagged unions and pattern-matching on them are vastly overrated for implementing language ASTs and IRs. They are nice to have, but they rarely make a substantial difference in the development of a compiler, typechecker, or similar.
(Nelson은 나중에 “I want to pause again to emphasize that this opinion is scoped: I think tagged unions are overrated for implementing IRs.”라고 다시 강조하기도 한다.)
놀랍게도, 나는 이 주장에 동의한다! (몇 가지 단서가 있긴 하지만. 😉) AST와 IR이라는 특정한 경우에 대해서는, 내가 관찰한 바가 다음과 같다.
초기 도입(bring-up) 기간이 지나면, AST나 IR에 새 케이스가 추가되는 일은 매우 드물다. 그래서 새 케이스를 추가하는 사람은 태그드 유니온이 있을 때보다 더 많은 문제에 부딪힐 수 있겠지만, 이 비용은 정기적인 유지보수 동안 자주 발생하는 비용이 아니다.
인스턴스 체크를 하는 것은 느낌상 투박할 수 있지만, 일단 그 허들을 넘고 나면 이는 큰 장벽이 아니라 작은 마찰원(friction)이라는 것을 깨닫게 된다.
태그드 유니온을 흉내 낸 클래스 계층은 태그드 유니온이 일반적으로 잘 제공하지 못하는 몇 가지 편의성을 제공한다: 타입을 점진적으로 좁히기(gradual narrowing)와 여러 계층(level)을 빠르게 가로지르는 능력.
이게 무슨 뜻일까?
태그드 유니온에서는 보통 평평한 계층이 가장 저항이 적은 경로가 된다. 계층이 깊어질수록 분해(= 매칭)와 구성(construction)이 빠르게 번거로워지기 때문이다. 구성 쪽은 작은 헬퍼 함수로 어느 정도 극복할 수 있지만, 대부분의 언어는 패턴을 의미 있게 조합하는 방법이 부족하다.
정확성 관점에서 보면, 더 평평한 계층은 타입이 “너무 커지는” 문제를 만들기 때문에, 어떤 케이스는 도달할 수 없다는 것을 알고 있는 지점들에 assert와 fatal_error를 여기저기 뿌리게 된다. 몇 개 함수만을 위해 전용 타입을 만들고(거기에 양방향 변환까지!) 유지하는 일이 지나치게 부담스러울 수 있기 때문이다.
반대로 클래스에서는 계층을 여러 단계 캐스팅으로 벗겨 내는 일이 문법적으로 가볍기 때문에, 더 세분화된 계층을 갖는 것이 매칭 지점마다 상시로 공유되는 부담이 되지 않는다. 나는 이것이 좋은 설계를 장려한다고 주장하고 싶다. 타입이 더 좁을수록 “믿어줘, 런타임에서 이 경로는 안 타”라고 말하는 것과 다름없는 코드 경로가 줄어들기 때문이다.
여기까지 보면 내가 거의 전적으로 Nelson과 동의하는 것처럼 보일 수 있다. 그럼 함정은 무엇일까?
내 생각에 AST를 이야기할 때 사람들이 흔히 하는 단순화는, 서로 다른 종류의 노드를 가진 트리 구조와 노드 간의 is-a 관계를 떠올리고 그것을 AST라고 부르는 것이다.
어떤 의미에서는 맞지만, AST는 그것보다 더 많은 것을 담고 있다! 논쟁의 여지 없이, 까다로운 코드의 대부분은 노드 내부에 있다. 까다로운 코드는 최소 두 가지 방식으로 재앙의 처방전이다.
구체적인 예를 들자면, Swift 컴파일러에는 오랫동안 다음 타입들이 있었다: (source)
enum class FunctionTypeRepresentation : uint8_t {
Swift = 0,
Block,
Thin,
CFunctionPointer,
Last = CFunctionPointer,
};
/// A class which abstracts out some details necessary for
/// making a call.
class ExtInfo {
// If bits are added or removed, then TypeBase::AnyFunctionTypeBits
// and NumMaskBits must be updated, and they must match.
//
// |representation|noEscape|throws|
// | 0 .. 3 | 4 | 5 |
//
enum : unsigned {
RepresentationMask = 0xF << 0,
NoEscapeMask = 1 << 4,
ThrowsMask = 1 << 5,
NumMaskBits = 6
};
unsigned Bits; // Naturally sized for speed.
};
(어떤 의미에서는 지금은 더 복잡해지기까지 했다. 😅.)
C++이나 Swift 컴파일러에 익숙하지 않다면, 여기서 무슨 일이 벌어지는지 빠르게 요약해 보겠다.
ExtInfo 타입은 함수 타입의 호출 규약(calling convention)에 대한 정보를 담고 있는데, 그중 한 측면이 표현(representation)이며 이것이 FunctionTypeRepresentation이다.Bits 필드는 6비트 분량의 정보를 담는다. “representation” 하나와, 함수가 @escaping인지 여부, throws인지 여부를 나타내는 2비트를 저장한다.
FunctionTypeRepresentation을 저장한다. 하지만 때로는 다른 타입을 저장하게 되는 경우가 있는데, 이것이 마스크가 2비트가 아니라 4비트인 이유다(FunctionTypeRepresentation은 4가지 케이스이므로 보통이라면 2비트면 충분하다).때로는 한 가지를 저장하다가 일시적으로 다른 것을 저장하는 복잡성 외에도, 내가 보여 준 코드에는 드러나지 않은 추가 복잡성이 있다: 어떤 조합은 불법(illegal)이다.
이 지점에서 몇 가지 운영상의 질문이 생긴다.
ExtInfo 값이 실제로 만들어지나? 그렇다면 어떤 컴파일러 패스가 이런 불법 값을 만들까?ExtInfo 값이 실제로 AST 안에 저장되나(아니면 일시적으로만 만들어지나)?내가 한때 그랬던 것처럼 이 구조를 의미 있게 바꾸려 한다면, 이것은(예의를 갖춰 말하자면) 꽤 골치 아프다.
문제를 더 악화시키는 것은, 이 타입의 API가 한 번에 한 “필드”씩 바꾸는 방식이어서, 어떤 합법 값에서 다른 합법 값으로 가고 싶을 때 강제로 일시적으로 불법 ExtInfo 값을 만들어야 하는 경우가 있었다(혹은 덜 인체공학적인 API를 사용해야 했다). 그 결과, 불법 값을 검사하는 중앙화된 assertion을 추가했을 때, 아주 특정한 이상한 코드를 컴파일할 때만 쓸데없이(assertion이) 터지는 일이 자주 발생했다!
물론 어떤 언어에서든 혼란스러운 코드는 작성할 수 있다는 점은 인정한다. 언어 기능이 혼란스러운 코드 작성을 마법처럼 막아 주지는 않는다. 또한 이것이 다소 극단적인 예시라는 점도 인정한다.
그렇지만, 만약 C++에 Swift나 Rust처럼 레이아웃 최적화를 포함한 태그드 유니온에 대한 네이티브 지원이 있었다면, 이는 아마 처음부터 훨씬 이해하기 쉬운 형태로 작성되었을 것이라고 의심한다. 혹은 이 예시처럼 내부를 손으로 최적화해야만 하더라도, 더 저수준의 타입 자체가 API의 일부일 필요는 없다. API에서는 레이아웃이 더 나쁜 고수준의 합(sum) 타입을 쓰고, 가장 저수준 함수들에서만 둘 사이의 변환을 두면 된다.
내가 여기서 말하고 싶은 요점은, 다른 도메인들과 마찬가지로, AST나 IR의 작은 일부(예를 들어 특정 AST 노드의 한 필드)를 태그드 유니온으로 모델링하고 싶을 때가 자주 있다는 것이다. 합 타입을 정의하고 패턴 매칭을 사용할 수 없다는 것은, 코드를 읽거나 바꾸려는 사람에게 작지만 반복적으로 부과되는 세금 같은 부담을 만든다. 불변식(invariant)의 복잡도에 따라, 겉보기엔 무해해 보이는 데이터 타입에서도 이 부담은 놀랄 만큼 커질 수 있다.
물론 어느 정도는 우회 방법이 있다. 예를 들면, 어떤 불변식이 성립하는지를 명확히 해 주는 assert를 더 많이 둘 수 있다. 하지만 “이해 가능한 코드”를 작성하는 장벽이 더 높아졌기 때문에, 그 이점은 동일하지 않다.
(Conor McBride를 패러프레이즈하자면) 타입이 프로그램의 중력이라면, 언어의 타입 시스템은 당신이 실제로 작성하는 타입들의 중력과 같다. 태그드 유니온과 패턴 매칭은 가장 흔한 데이터 표현인 “이것 아니면 저것”을 위한 마찰을 줄여 준다. 그렇다고 해서 무언가의 여러 경우를 표현할 때 항상 태그드 유니온이 기본 선택이어야 한다는 뜻일까? 아니다. 하지만 매우 자주 좋은 출발점이 된다.
글의 뒤쪽에서 Nelson은 패턴 매칭이 우리가 바라는 만큼 강력하지 않다는 점을 지적한다.
My next comment is on the flip side — the limits of pattern-matching in languages that do support it. In my experience, it often ends up being less powerful and convenient than you’d like.
…
To me, this is a compelling argument that, even if C++ had language-level pattern-matching, it would be necessary to invent our own pattern-matching system to support these complex and non-type-specific matchers, anyways. So what would we really be gaining from that language support?
나는 ML 스타일의 패턴 매칭(혹은 대중적인 언어들에서의 변형)이 보통 그리 강력하지 않다는 Nelson의 지적에는 동의한다. 하지만 두 번째 문단의 주장에는 몇 가지 이유로 동의하지 않는다.
동시에, 복잡한 매칭이 필요한 경우 더 강력한 해법이 필요하다는 점에도 동의한다. 다행히 이 영역에는 참고할 만한 멋진 작업들이 이미 꽤 있다.
Haskell에는 패턴을 조합하는 데 사용할 수 있는 pattern synonyms가 있다. 완전히 1급(first-class) 패턴은 아니지만 여전히 꽤 유용하다. 사용자 정의 패턴(데이터 타입 선언을 바탕으로 컴파일러가 합성하는 패턴이 아닌)에 대한 철저성 관계는 특정 compiler pragma를 사용해 지정할 수 있다.
optics에 대한 작업: 함수형 프로그래밍 언어 맥락에서 optics에 관한 연구와 구현이 많이 있었고, 가장 대표적으로는 Haskell의 lens 라이브러리가 있다. Prism은 패턴 매칭을 표현하는 optic의 한 종류로, 패턴을 1급으로 캡처하고 다른 선택(selection) 형태와도 잘 조합되도록 해 준다. 다만 철저성 검사는 잃게 된다.
optics라는 아이디어는 대중화되어 다른 언어로도 퍼졌다. 예를 들어 Javascript용 Ramda 라이브러리(깃허브 스타 20.3k)는 렌즈에 대한 제한적인 지원을 제공한다.
Perl 계열(그중 Raku 포함)은 정규식 매칭과 사용자 정의 문법(grammar)을 정의할 수 있는 강력한 기능을 제공한다.
행 다형성(row polymorphism)을 갖는 구조적 합 타입: OCaml은 확장/축소가 가능한 구조적 합 타입에 대한 언어 지원을 제공한다(OCaml 용어로는 “polymorphic variants”라고 부른다). Purescript에는 이 기능을 구현한 purescript-variant 라이브러리가 있다.
Egison은 복잡하고 확장 가능한 패턴을 지원한다.
Mathematica는 패턴과 치환 규칙(replacement rules)을 사용하는 데 있어 정말 좋은 지원을 제공한다.
여기서 내가 놓친 관련 작업도 분명 많을 것이다.
이런 사례들을 보면, 주류 언어에서의 패턴 매칭을 더 강력하게 만드는 데에는 꽤 큰 여지가 있다고 생각한다. 그래서 직접 패턴 매칭 라이브러리를 손으로 굴릴 의지가 있는 사람들(그리고 흔히 따라오는 지저분한 타입 에러들)만이 아니라, 모두가 그 혜택을 볼 수 있게 될 것이다.
태그드 유니온과 패턴 매칭은 “작은 범위(in the small)”에서 작업할 때 강력한 도구라고 생각한다. 하지만 현재로서는 “큰 범위(in the large)”에서는 동일하게 잘 작동하지 않는다. AST나 IR의 노드 계층은, 첫눈에는 태그드 유니온이 완벽하게 맞는 것처럼 보일 수 있지만, 클래스가 태그드 유니온에 비해 실질적인 이점을 제공하는 사례 중 하나다.
언어 기능의 힘을 생각할 때 나는 종종 “항복점(yield point)” 관점으로 생각하는 것을 좋아한다. 개념이 낯설다면, 위키피디아의 설명을 옮기면 다음과 같다.
In materials science and engineering, the yield point is the point on a stress-strain curve that indicates the limit of elastic behavior and the beginning of plastic behavior. Below the yield point, a material will deform elastically and will return to its original shape when the applied stress is removed. Once the yield point is passed, some fraction of the deformation will be permanent and non-reversible and is known as plastic deformation.
항복점은 점진적인 열화가 시작되는 지점을 포착한다. 즉각적인 대재앙은 아니지만, 원래 의도하지 않았을지도 모르는 방식으로 시스템을 늘이고 있다는 뜻이다.
오늘날, 주류 언어들의 패턴 매칭 기능(또는 그 부재)을 고려하면, 태그드 유니온과 패턴 매칭의 항복점은 비교적 낮다. 하지만 이는 한탄할 일이 아니라, 오히려 훌륭한 기회다. 덜 대중적인 언어들에서 패턴 매칭 기능을 합성해 보기도 하고, ML 스타일의 패턴 매칭을 확장하면서도 주류 언어 사용자들에게 뛰어난 조합성(composability)과 인체공학을 제공하는 설계를 찾아내어, 항복점을 더 멀리 밀어낼 수 있다.