Gleam 컴파일러의 case exhaustiveness 검사기가 패턴 누락과 도달 불가능한 분기를 찾아내는 방식, 그리고 그 배경이 된 연구를 살펴봅니다.
결정, 또 결정.
내가 이 글을 쓰는 지금, 나는 앞으로 10분 동안 살아가기 위해서만도 여러 겹으로 중첩된 결정을 저글링하고 있다. 내 앞에 놓인 결정들이 내 안락함을 뒷받침하는 것들이라는 점에서 나는 특권적이다. 각각은 평범하지만 복잡한 부수 효과를 지닌다. 햇살이 강해지고 있다. 가방에 손을 넣어 모자를 꺼낼까? 그렇다면 노트도 꺼내 무언가를 그릴까? 무언가를 그릴 거라면, 내 앞에 펼쳐진 아름다운 도시의 무한한 가능성 중 무엇을 그려야 할까?
나는 이 글을 쓰는 대신 햇볕 화상의 위험을 감수하는 동시에, 세상에서 작은 낙서 하나를 빼앗고 있다.
컴퓨터의 주요 업무 중 하나는 결정을 내리는 것이며, 오늘의 주제는 프로그램이 처리하려는 선택들이 유효한지 판단하기 위해 컴파일러가 밟을 수 있는 단계를 추적하는 일이다. Gleam의 컴파일러는 훌륭하고 방대한 장인정신의 산물이며, 나는 Gleam City의 작은 길 하나, 즉 case exhaustiveness에 관한 그 논리를 따라 머릿속 산책을 함께하고 싶다.
Gleam이라는 프로그래밍 언어에서는 case expressions를 지정할 수 있다. 이 언어 부분집합 안에서 compiler-core/src/exhaustiveness.rs의 목적은 case에 제시된 모든 패턴이 주제가 가질 수 있는 모든 값을 포괄하는지 판단하고, 반대로 이전 절이 이미 같은 상황과 일치하기 때문에 절대 실행될 수 없는 절이 있는지 판단하는 것이다. 처리되지 않은 값이 프로그램 실행 중 충돌을 일으키는 대신 Gleam 프로그램이 컴파일될 때 이를 알아내 준다니, 정말 훌륭한 사용자 경험 아닌가!
pub fn to_string(is_cool: Bool) -> String {
case is_cool {
True -> "cool"
False -> "uncool"
}
}
이 코드에서 False 절을 제거하면 컴파일되지 않는다는 사실이 있다. exhaustiveness.rs의 논리에서 내게 특별한 점은, 가능하다면 사용자에게 정확히 어떤 case가 빠졌는지를 알려 주려 한다는 것이다. "The missing patterns are: False"라고 정중히 알려 준다. 이런 메시지를 제공하는 일은 결코 쉽지 않으며, 따라서 Gleam이 사용자 친화성에 얼마나 헌신하는지 내게 잘 보여 준다.
타입이 있는 함수형 언어는 1970년대부터 잡초처럼 자라기 시작했지만, 우리 파일에 중요한 이론은 적어도 내게는 1984~5년 무렵 Lennart Augustsson의 패턴 매칭 컴파일 논문, 제목이 "Compiling Pattern Matching"인 글에서 시작된다.
덧붙임: 이 논문을 읽으면, 어쩌면 나처럼 Augustsson 씨가 "matching" 대신 "mathing"을 쓴 것이 오타인지 궁금해질 것이다. 여러 번 나오기 때문이다. 어쨌든 꽤 "mathy"한 주제다. 우리 뇌의 패턴 매칭에 관한 농담이 분명 어딘가에 있을 텐데.
Augustsson은 이후 작업의 토대라고 내가 생각하는 틀을 제시한다. case expression의 절들을 선행 constructor별로 묶고, 하위 부분에 새 변수를 도입한 뒤, 그 하위 부분에 대해서도 반복하라는 것이다! 훌륭하지만 다소 빽빽한 읽을거리다. 논문 후반부는 하위 부분을 실제 LML 명령으로 바꾸는 방법론을 자세히 다룬다. 가령 하위 부분이 아무것과도 일치하지 않을 때 중첩된 case 미로의 default 항목으로 literal jump(GOTO?)하는 방식이다. 다시 말해 각 default는 재시도를 강제하고, 최상위 default(실패를 의미함)에 도달할 때까지 런타임에 그렇게 될 것이다. 중첩은 완전히 재귀적으로 전개된 셈이다.
덧붙임: 자신만의 ML 변형을 쓰는 건 엄청난 과시다...
Gleam의 Decision::Switch 동작을 보면 Augustsson의 _case 하위 부분이 아무것과도 일치하지 않았을 때의 jump_가 유령처럼 느껴진다. 고대 역사와 달리 Gleam은 컴파일되므로 Switch의 default는 실제 정적 타입 데이터 구조의 노드다(런타임 규칙과는 반대다). 또한 Augustsson의 jump가 하나로 하던 두 작업을 분리했다. 즉 Switch는 재시도하여 중첩된 수프의 다른 곳에서 계속 매칭하고, 모든 다른 선택지를 벗어나면 암묵적으로 일어나던 일은 타입으로서의 Decision::Fail이 맡는다. 이 조합의 핵심은 트리가 만들어진 뒤 컴파일 타임에 Fail을 찾는 것이며, 이는 최초의 case expression이 불완전하다는 증거다. Fail이 정확히 어디에서 일어나는지 알면 missing_patterns.rs로 이어지고, 이 파일은 트리를 거꾸로 되짚어 절대 매칭되지 않을 구체적 상황을 찾아 사용자에게 전달한다. 결국 실패할 jump가 무엇인지 알아내는 이런 (런타임) 단언이라는 개념은 정말 거대한 어깨 위에 서 있다!
절대 매칭되지 않을 그 구체적 상황의 이름은 요즘 아이들이 말하는 "witness"다. Luc Maranget(고양이 깜짝 등장에 주의)은 2007년 논문 "Warnings for pattern matching"에서 이를 "counter-example"이라고 부른다. 잠시 후 witness로 돌아오겠다.
"프로그래머들은 때때로 ‘non-exhaustive match’ 경고 앞에서 꽤 당황한다. ‘non-matching value’의 예시는 그들이 정말 non-exhaustive match를 작성했다는 점을 납득시키는 데뿐 아니라 코드를 고치는 데에도 큰 도움이 된다." -- Luc Maranget, 2007
순진한 함수형 프로그래밍 인류학자 같은 역할극을 하며 살펴본 바로는, 1990년대는 함수형 언어의 붐이었다. Augustsson의 LML은 Haskell HBC의 일부가 되었고, Clean('95), OCaml('96), Erlang('98년에 공개) 등이 나왔다. 21세기 전환점 무렵에는 case expression의 트리 크기 측면(의도적으로 거의 다루지 않았다)에 관한 연구가 정점에 이르고, 진단을 얼마나 인체공학적으로 만들 수 있는지, 매칭 패턴을 얼마나 풍부하게 만들 수 있는지로 옮겨간 듯하다. 그렇게 Maranget의 논문으로 이어진다! witness를 찾기 위해 제안된 방법론은 다음과 같다(이 옆길 이야기는 미안하지만 매우 흥미롭다).
주제는 열로, 절은 행으로 행렬을 배열한다.
주어진 열에 집중한다. (나중을 위해 정신적으로 준비해 두자면 자연스럽게 재귀하므로, 나는 "첫 번째"가 아니라 "주어진"이라고 말한다.)
그 열의 constructor들은 해당 타입이 가질 수 있는 모든 case를 포괄하는가?
* 아니라면 constructor 하나가 빠졌다! 누락된 constructor와 함께 4단계로 간다(숫자와 문자열 같은 오래된 타입은 보통 적어 둘 constructor가 너무 많으므로, 이들에게는 "그 밖의 모든 것" 절이 필요하다. { "a" -> "my answer 1", "aa" -> "my answer 2", ..ad nauseam} 같은 문자열 case expression을 상상해 보라).
* 그렇다면 적어도 좋다! 각 constructor에 대해 4단계를 수행한다.
* 열에 문자 그대로 아무것도 없다면, 그 열을 건너뛰고 다음 열에 대해 2단계로 돌아간다.
주어진 constructor에 층 하나를 뚫어 넣고, 이를 specialize하여 들어간다. MyType(r), rest...는 r, rest...가 된다. 이제 실제로 새 행렬 위에 있다!
* 이 내부 행렬에 절이 없다면, 잠정적으로 witness를 찾은 것이니 저장하고 계속한다. (...4단계를 거쳐야 하는 다른 모든 constructor와 함께.)
반복한다! (Halters는 쇠스랑을 내려놓아라. 각 반복은 실제로 무언가를 소비하므로 패턴은 반드시 바닥난다.) witness가 남으면, 짜잔, 누락된 패턴이 있다. witness가 없다면 이 case는 종결이다. (알겠지?)
덧붙임: 기묘한 용어다.
"이렇게 즐거운 카니발 놀이기구라니. Gleam은 이 행렬을 어떻게 다룰까?" 독자가 소리 내어 궁금해한다. 우선 막대사탕을 들고 빙글빙글 모자를 쓴 에너지다. 둘째로, 멋진 부분은 바로 그것이다! 다루지 않는다. 대신 Gleam은 절을 branch 목록으로 표현하고, 각 branch는 [variable] is [pattern] 같은 check의 목록이다. Jules Jacobs의 노트와 Yorick Peterse의 구현 방식이다.
트리 구축과 Maranget 얘기가 나왔으니, 그의 다른 논문이 더 관련 있다. 그래서 실제로 오늘의 Gleam 코드에서 (두 번이나!) 인용된다. "Compiling Pattern Matching to good Decision Trees"(Maranget, 2008년, 방금 논의한 논문보다 1년 뒤)는 짐작했겠지만 OCaml의 backtracking compiler(그것이 바로 Augustsson의 중첩 jump-case 미로인가?) 성능을 따라잡도록 트리를 _컴파일_하는 방법을 다룬다. Backtracking의 장점은 "코드 크기에 대한 선형 보장"이다. 단점은 "하위 항을 두 번 이상 검사할 수 있음"이다. Maranget은 절을 트리로 구축하는 순서를 현명하게 선택하면 그 깊이를 줄일 수 있음을 보여 준다.
다음과 같은 열을 우선하라.
True나 Circle 타입뿐 아니라 Ok(x), Ok(False) 등을 뜻하기 때문이다)마지막 열 우선 방법의 예로, 실제로는 주어진 열을 cell마다 아래로 살핀다. 각 cell에는 constructor([] / [x, ..rest] 같은 것)가 있거나, 그 cell이 구체적으로 신경 쓰지 않는 상태(_, r)가 있다. 신경 쓰지 않는 첫 인스턴스까지 세고, 짜잔, 그 수로 열의 순위를 매겨 그에 따라 트리를 정렬한다!
Gleam은 행렬 형태로 의사결정을 만들지 않는다. 대신 전체 트리를 만들기 때문이다(행렬 방식도 잘 작동할 듯하지만, 이 방식으로는 진단 그리고 JavaScript backend의 기반을 공짜로 얻는다). 하지만 다음에 어떤 test를 검사할지 정하는 엔진은 Maranget/Jacobs 전략 둘의 조합인 듯하다. constructor가 가장 적은 타입의 variable을 선택하고(즉 list에는 2개, int에는 무한히 많다), 동률이면 남은 check가 더 많이 관련된 var를 선택한다.
현명하게 선택하면 트리가 더 작아진다. 다음 같은 경우 자연스러운 상태는
case a, b {
Some(x), 1 -> "one"
None, 2 -> "two"
_, _ -> "buckle my shoe"
}
마지막 절이 다음처럼 여러 번 복제되는 것이기 때문이다.
(a를 기준으로 먼저 트리를 분할한다고 가정하면)
- Some: clause 1, & a copy of clause 3
- None: clause 2, & a copy of clause 3
그다음
- Some:
- b is 1: clause 1, copy of clause 3
- b is anything: copy of clause 3
- None:
- b is 2: clause 2, copy of clause 3
- b is anything: copy of clause 3
그러므로 "buckle my shoe" 절은 4개가 복제된다. 물론 그중 일부는 사후에 자연스럽게 쓸모없어진다. 예를 들어 a와 b가 Some, 1인 경우에는 절 1이 매칭하므로, 절 3의 복사본은 실행될 수 없음을 확실히 안다. 트리가 작을수록 컴파일 타임에 막다른 곳을 찾아내기 쉽고, 이는 처리되지 않은 패턴이 하나 있다는 사실뿐 아니라 줄기까지 거슬러 올라가면 특정 누락 항목을 얻는다는 증명이 된다.
exhaustiveness.rs를 읽으며 가장 즐거웠던 부분은 어떤 논문에서도 찾지 못한 기능을 살펴볼 때였다(어느 논문에도 없다고 완전히 단언하는 것은 아니다. 내가 찾지 못한 잠재적 실력 문제에 대비해 말을 아끼는 것이다). 몇 가지를 보자.
case s {
"lewis" <> rest -> ...
}
문자열은 다른 문자열의 부분집합일 수 있으므로, 이것은 완전히 새로운 종류의 상황을 도입한다! 우리는 case expression에서 하나의 상황이 참인 것을 다루는 데 익숙하다, 그렇지 않은가? 게다가 트리 구성을 꽤 어렵게 만드는 inline guards도 있다.
case s {
"lewis" <> rest if rest == " likes" -> "lewis likes gleam"
"lew" <> rest -> "lew-" <> rest
_ -> "idk"
}
이 경우 트리로 순회하면서 우리의 단계를 되짚는 것은 불가능하다.
그렇다
아니다
"이런!"에 주목하라. "lew"가 "lewis"의 부분집합이라는 사실을 알기 때문에, 우리는 여전히 절 2를 반드시 시도해야 한다. "그걸 어떻게 아는가?"라고 묻는다면, Gleam은 같은 level에서 지금까지 본 string prefix를 기억해 두었다가, 주어진 더 짧은 prefix를 각각의 더 긴 prefix의 "이런!" 구역에 추가한다. 이미 깊이 순회하고 있을 때도 이를 검사할 수 있게 하기 위해서다.
그렇다
아니다
compiler-core/src/exhaustiveness.rs에서 참고하려면 특히 overlap_candidates와 descendant_candidates를 살펴보라.
commit history를 보면, 이 string-prefix 참신성은 현재의 만족스러운 상태에 이르기까지 다듬어진 방식에서 빛난다고 말할 수 있다. 완전히 끝나기 전까지 여기에는 더 탐구할 것이 있으리라 돈을 걸겠다. guard와 prefix/subset에 기반한 매칭을 다루는 논문이 실제로 있다면 알려 달라! 그렇다고 이 기능이 조금도 덜 멋진 것은 아니다.
Bit array 논리: "Efficient Manipulation of Binary Data"는 가변 segment 크기를 지닌 bit array 매칭을 다뤘지만, Gleam은 다른 타입의 exhaustiveness에 맞추어 몇 단계 더 나아가는 듯하다. 컴파일러는 패턴이 불가능한지 검사하고, 순회 중 이전에 이미 test가 수행되었는지 기억한다. 또한 JS와 BEAM 동작을 다듬어 통일하는 생성 코드를 굳이 내보낼지 말지도 결정한다. 예를 들어 주어진 bit array length variable이 음수일 수 있는 가능성을 감지하면(정확히는 절대 음수가 아니라고 확신할 수 없다면), raise하는 대신 그냥 통과시키는 코드를 내보낸다. 마찬가지로 NaN/Infinity가 실제로 float segment와 매칭하지 않는다는 점도 고려한다.
Type-narrowing: 예를 들어 다음을 보자.
pub fn area(s: Shape) -> Float {
let shape = Circle(67.0)
case shape {
Circle(r) -> 3.14 *. r *. r
}
}
우리 컴파일러는 Shape가 될 수 있는 다른 모든 shape를 빠뜨렸다고 여기서 불평해야 할까? Square, Rhombus, 이들은 내 강력한 정신이 이름 댈 수 있는 shape의 일부에 불과하다. (박수.)
Gleam의 컴파일러는 shape라는 Shape의 구체적 instantiation을 기억하고, 그것이 Circle일 수밖에 없음을 확실히 알기에 이 expression을 만족스럽게 여긴다. 그뿐 아니라, 여기서 Square 같은 case를 처리했다면 dead branch를 추가했다고 충실히 알려 줄 것이다. 이는 다음과 같은 상황에도 적용된다.
pub fn describe(s: Shape) -> String {
case s {
Circle(r) -> {
case s {
Circle(_) -> "round and awesome"
}
}
Square(side) -> "four sides and boring"
// ... for my other shapes
}
}
내부의 s case가 Square 상황을 처리하지 않는다는 경고는 나오지 않는다.
멋지지 않은가! 컴파일러는 진행하며 얻는 실용적 정보를 철저히 활용하는 듯하다.
오류에서 구체적 instance 출력하기: 다시 witness로 돌아가, 트리에서 막다른 곳을 찾고 뿌리를 찾기 위해 끝까지 거꾸로 순회할 때를 보자. Gleam은 그 경로를 그저 출력하고 끝내지 않는다. 컴파일러는 내가 function을 import하는 고유한 naming을 알고 있으므로, 내가 farm.Unmilkable(_)을 빠뜨렸다고 보고하는 대신,
import farm.{Milkable, Unmilkable} // it will tell me I'm missing `Unmilkable(_)`
import farm.{Milkable, Unmilkable as TooSkinny} // I'm missing `TooSkinny(_)`
import farm as barn // `barn.Unmilkable(_)`
import farm // `farm.Unmilkable(_)`
정확히 사용된 상태로 번역하는 실제 mechanism은 live LSP 쪽 type-printer에서 재사용되는 듯하다! multi-subject case를 위한 comma separation, label field 줄이기, 다른 module의 internal type을 printer가 출력하지 않기 같은 삶의 질을 위한 다른 논리도 많다(잠깐만, 사실 그 마지막은 "quality"라기보다는 어떤 신비한 security model일 수도 있겠지만, 나는 멋지다고 생각한다).
여기서 마쳐야겠다. 컴퓨터를 쳐다보기에는 너무 아름다운 날이다. 나는 일어난다. 따뜻하고 향기로운 바닷바람을 따라가자. 이것이 Gleam의 case exhaustiveness checker가, 그 탄생 배경인 문헌을 구현하고 뛰어넘으며 코드에서 좀처럼 보기 힘든 수준의 사용자를 위한 배려를 보장하는 방식으로 나를 놀라게 한 지점들이다. 이는 Gleam codebase라는 바다의 한 방울일 뿐이다. 지금까지 마주친 거의 모든 file에 관해 글을 쓸 수 있을 것이다. 친애하는 독자여, 당신도 이를 잘 공부하고, 바라건대 그 소스의 일부를 자신의 프로그램을 위해 마음에 새기길 바란다!