팬의 시선으로 살펴본 Gleam의 case 완전성 검사

Gleam 컴파일러가 case 패턴의 누락과 도달 불가능한 분기를 찾는 과정을 설명합니다. 패턴 매칭 연구를 바탕으로 결정 트리와 누락 패턴 진단을 만들고, 문자열 접두사와 비트 배열, 타입 좁히기까지 처리하는 방식을 코드와 함께 살펴봅니다.

주제: 언어 컴파일러 개발 도구

에디터 노트

Gleam의 강점으로 제시된 부분은 완전성 검사 자체보다 누락된 입력을 구체적인 패턴으로 되짚어 알려주는 진단입니다. 글은 이 진단이 Augustsson과 Maranget의 패턴 매칭 연구를 바탕으로 하며, 문자열 접두사나 비트 배열처럼 단순한 생성자 분기로 설명하기 어려운 경우까지 처리한다고 보여줍니다. 댓글도 완전한 패턴 매칭을 새 발명처럼 다루지 말아야 한다는 점에 동의하고, Gleam을 기존 아이디어를 선별해 조합한 언어라고 봅니다. 글의 사례는 그 조합과 세부 구현을 구체적으로 뒷받침하지만, Gleam의 모든 기능이 연구 논문에 없다는 대목은 필자의 검색 범위에 한정된 판단입니다. 구현의 독자성보다 기존 연구를 사용자 친화적인 오류 메시지와 실제 언어 기능으로 연결한 방식이 이 글에서 확인되는 주장입니다.

AI 요약

Gleam의 컴파일러는 case 표현식에서 가능한 값이 모두 처리되는지 확인하고, 앞선 분기에 이미 잡혀 실행될 수 없는 분기도 찾아냅니다. 예를 들어 Bool 값을 다루는 case에서 False 분기를 빼면 컴파일 오류를 내는 데 그치지 않고 누락된 패턴이 False라고 알려줍니다. 글은 이런 진단을 구현하는 compiler-core/src/exhaustiveness.rs를 중심으로 패턴 매칭 연구와 Gleam의 구현을 따라갑니다.

패턴에서 누락 사례를 찾기까지

글은 1980년대 Lennart Augustsson의 패턴 매칭 컴파일 연구에서 출발합니다. case 분기를 첫 번째 생성자에 따라 묶고, 생성자의 하위 요소마다 새 변수를 도입해 재귀적으로 처리하는 방식입니다. Gleam에서는 결정 트리의 Switch 노드가 다른 검사로 넘어가는 동작을 맡고, Decision::Fail이 더는 분기를 찾지 못한 상태를 나타냅니다. 트리 구성 뒤 Fail이 발견되면 컴파일러가 트리를 거슬러 올라가 어떤 입력이 처리되지 않았는지 찾아냅니다.

누락 사례를 구체적인 패턴으로 제시하는 방식은 Luc Maranget의 2007년 논문과 연결됩니다. 이 논문은 값의 열과 분기의 행으로 만든 행렬을 살펴보며 빠진 생성자를 찾습니다. 생성자 종류가 무한한 문자열이나 숫자는 나머지 값을 나타내는 경우를 따로 고려하고, 생성자 안쪽으로 들어가 하위 패턴을 반복 검사합니다. 이 과정에서 찾아낸 누락 사례를 witness라고 부릅니다. Maranget은 구체적인 반례를 보여주면 프로그래머가 누락 경고를 이해하고 코드를 고치는 데 도움이 된다고 설명합니다.

결정 트리의 크기와 검사 순서

Maranget의 2008년 연구는 패턴 매칭 결정 트리를 작게 만드는 방법을 다룹니다. 백트래킹 방식은 코드 크기를 선형으로 유지하는 장점이 있지만, 하위 항목을 여러 번 검사할 수 있습니다. Gleam은 분기 목록을 행렬로 직접 표현하는 대신 각 분기를 변수와 패턴의 검사 목록으로 나타내고 트리를 만듭니다. 검사 순서를 정할 때는 가능한 생성자 수가 적은 타입을 우선하고, 동률이면 남은 검사 중 더 많이 등장하는 변수를 고릅니다.

검사 순서는 분기 복제에도 영향을 줍니다. 두 변수를 함께 검사하는 case에서 첫 번째 변수부터 나누면 와일드카드 분기가 여러 갈래에 복사될 수 있습니다. 필요 없는 복제까지 생기면 트리가 커지고, 누락 사례를 찾는 과정도 복잡해집니다. 글은 작은 트리가 실행 코드와 누락 패턴 진단 모두에 도움이 된다고 설명합니다.

문자열 접두사, 비트 배열과 타입 정보

일반적인 생성자 패턴과 달리 문자열 접두사는 서로 겹칠 수 있습니다. "lewis"로 시작하는 문자열을 검사한 뒤 가드 조건이 실패해도, 더 짧은 "lew" 접두사 분기는 여전히 적용될 수 있습니다. Gleam은 같은 단계에서 이미 확인한 접두사를 기록하고, 더 긴 접두사의 검사에서 가드 실패가 발생하면 해당 접두사 후보도 검사하도록 분기를 복사합니다. 글은 이 로직을 overlap_candidates와 descendant_candidates에서 찾을 수 있다고 안내합니다.

비트 배열 패턴에서는 불가능한 패턴과 이미 수행한 검사를 확인합니다. JavaScript와 BEAM의 동작을 맞추기 위한 코드를 생성할지도 판단합니다. 예컨대 길이 변수가 음수일 가능성을 배제하지 못하면 예외를 발생시키는 대신 다음 분기로 넘어가는 코드를 만들고, NaN이나 Infinity가 부동소수점 세그먼트와 일치하지 않는 경우도 고려합니다.

컴파일러는 변수의 구체적인 타입 정보도 기억합니다. Shape 타입 변수가 Circle 값으로 좁혀진 뒤에는 Circle만 다루는 case를 허용하고, Square 같은 분기를 추가하면 도달 불가능하다고 알릴 수 있습니다. 중첩 case에서도 바깥 분기에서 확인한 타입 정보를 활용합니다. 누락 패턴을 출력할 때는 사용자가 모듈이나 이름을 어떻게 가져왔는지 반영해 Unmilkable(_), TooSkinny(_) 또는 barn.Unmilkable(_)처럼 표시합니다.

Lobsters 반응

@toastal — 이 글이 ML 계열 언어가 1990년대 중반부터 ADT와 완전한 패턴 매칭을 제공해 왔다고 짚은 점이 좋습니다. 이런 개념을 마치 어떤 언어에서 새로 나온 것처럼 다루는 경우가 너무 많습니다.
- @lpil — 전적으로 동의합니다. Gleam에서 새로운 것은 거의 없고, 훌륭한 사람들의 좋은 아이디어를 골라 모았습니다.
- @hwj — 완전한 패턴 매칭은 제가 OCaml을 좋아하는 주된 이유 중 하나입니다.

원문: Oyster / 번역·요약: Trawling

원문 보기 ↗토론 보기 ↗