매크로와 엘라보레이션을 이용해 도메인 지식을 타입 시스템에 주입하는 ‘타입 테일러링’ 개념을 소개하고, 정규식/SQL 등에서 지나치게 보수적인 타입을 자동으로 보정하는 방법과 이를 지원하기 위한 언어 기능을 설명한다.
URL: https://lambdaland.org/posts/2024-07-15_type_tailoring/
Title: 타입 테일러링으로 언어를 더 빠르게 진화시키기
프로그래밍 언어는 너무 느립니다! 실행 속도를 말하는 게 아니라, 진화 속도를 말하는 겁니다. 프로그래머들은 늘 새로운 라이브러리와 임베디드 DSL을 만들어내지만, 호스트 프로그래밍 언어—특히 타입 시스템—는 이런 것들의 도메인 특화적 측면을 이해하지 못합니다.
정규식을 생각해봅시다. 대부분의 프로그래머는 [a-z]+([0-9][0-9]) 같은 정규식이 매칭에 성공하면 첫 번째 캡처 그룹에 두 자리 숫자를 캡처한다는 것을 이해합니다. 그런데 Rust나 Typed Racket에서 아래 코드를 쓰면 타입 체커가 불평합니다.
예: Rust
use regex::Regex;
fn main() {
let re = Regex::new(r"[a-z]+([0-9][0-9])").unwrap();
if let Some(caps) = re.captures("dent42") {
println!("id number: {}", caps.get(1));
}
}
에러:
rustc [E0277]: `Option<regex::Match<'_>>` doesn't implement `std::fmt::Display`
the trait `std::fmt::Display` is not implemented for `Option<regex::Match<'_>>`
예: Typed Racket
#lang typed/racket
(define (user-idnum (username : String)) : Number
(define re "[a-z]+([0-9][0-9])")
(define m (regexp-match re username))
(if m
(string->number (second m))
(error "bad username")))
(printf "id number: ~a\n" (user-idnum "dent42"))
에러:
example.rkt:7:22: Type Checker: Polymorphic function `second' could not be applied to arguments:
Types: (List* a r (Listof t)) -> (r : ((! (cadr (0 0)) False) | (: (cadr (0 0)) False)) : (cadr (0 0)))
(Listof a) -> a
Arguments: (Pairof String (Listof (U False String)))
Expected result: String
(U τ₁ τ₂) 문법은 타입 τ₁, τ₂의 _유니언 타입_을 뜻합니다(각각이 어떤 타입이든). Typed Racket에서 Option<String>에 해당하는 것은 (U String False)입니다.
문제는 첫 번째 캡처 그룹을 가져오는 것(caps.get(1) in Rust, (second m) in Typed Racket)이 선택적 타입을 반환한다는 점입니다(Rust에서는 Option<regex::Match>, Typed Racket에서는 (Listof (U False String))). 하지만 우리는 5번째 줄에서 정규식 매치가 성공했다면, 매칭한 정규식에 캡처 그룹이 1개 있었으니 caps.get(1)(또는 (second m))도 반드시 성공해야 한다는 것을 알고 있습니다. 그 대신 Rust에서는 언랩을 강요받습니다:
println!("id number: {}", caps.get(1).unwrap().as_str());
Typed Racket에서도 이 코드가 실행되어야 한다는 것을 타입 체커에게 납득시키기 위해 캐스트와 체크를 수동으로 끼워 넣어야 합니다.
이건 작은 예시일 뿐이고, 핵심은 이것입니다: 타입 시스템은 보통 정규식의 구조를 알 만큼 똑똑하지 않습니다—컴파일러가 보는 것은 불투명한 문자열뿐입니다. 이 문제는 정규식에만 해당하지 않습니다. 종종 문자열로 임베딩되는 SQL 쿼리도 마찬가지입니다. 쿼리가 잘못되면 보통 런타임에서야 알게 됩니다.
해결책은 어떤 모습일까요? 어떤 사람들은 타입 시스템이 더 잘 이해할 수 있도록 조합 가능한 객체로 정규식을 작성하는 새로운 방식을 시도했습니다. 좋은 접근이지만, 프로그램을 다시 써야 하고(기존 정규식 문자열을 유지하기 어렵고), 알려진 크기의 리스트(캡처 결과)를 더 효율적으로 인덱싱하는 문제도 해결하지 못합니다.
또 다른 선택지는 타입 시스템을 더 똑똑하게 만드는 것입니다. 하지만 이것도 단점이 있습니다. 언어 구현자들은 타입 체커를 건드리는 것을 꺼리곤 하는데—그럴 만합니다! 타입 체커의 정확성에 너무 많은 것이 의존합니다. 게다가 타입 체커가 정규식을 이해하게 만들었다고 해도, 내일 누군가 새로운 라이브러리를 만들면 또다시 타입 체커가 이해하지 못하는 상황이 벌어질 겁니다.
여기 더 매력적인 옵션이 있습니다. 언어가 제공하는 메타프로그래밍 도구를 사용해 타입 시스템에 새 기술을 가르칠 수 있습니다. 언어 설계자가 뭘 해주길 기다리지 않고도 언어의 최종 사용자(end-user) 가 할 수 있는 일이죠. 이를 타입 테일러링(type tailoring) 이라고 부릅니다.
Type Tailoring_은 제 지도교수 Ben Greenman 및 공저자 Stephen Chang, Matthias Felleisen과 함께 쓴 논문의 제목이자 주제입니다. 이 논문은 유럽 객체지향 프로그래밍 학회 (ECOOP)에 채택되었습니다. ACM 학회 OOPSLA처럼 ECOOP도 최근 몇 년간 객체지향 프로그래밍을 넘어서 더 다양한 주제를 다루고 있습니다. 이름만 남았죠. ¯_(ツ)/¯ 프리프린트는 여기에서 받을 수 있습니다.
문제를 어떻게 해결할지, 높은 수준에서 개략을 그려보면 이렇습니다:
re.captures 함수가 이 정보를 받아 자신의 타입을 업데이트한다.caps의 타입에도 더 활용되어, get(0)이나 get(1)이 항상 성공한다는 사실을 나타낸다.몇 년 전 제 지도교수는 Typed Racket용 trivial 라이브러리를 만들었습니다. 이 라이브러리는 아래 코드를 테일러링하여 타입 체크를 통과하면서도 효율적으로 실행되게 할 수 있습니다.
trivial 라이브러리는 Racket 패키지로 제공됩니다. 시스템에 Racket이 설치되어 있다면 raco pkg add trivial을 실행해 설치하세요.
#lang typed/racket
(require trivial trivial/list) ;; 프로그램을 테일러링하려면 이 줄을 추가
(define (user-idnum (username : String)) : Number
(define re "[a-z]+([0-9][0-9])")
(define m (regexp-match re username))
(if m
(string->number (second m))
(error "bad username")))
(printf "id number: ~a\n" (user-idnum "dent42"))
테일러링 전
Type Checker: Polymorphic function `second' could not be applied to arguments:
Types: (List* a r (Listof t)) -> (r : ((! (cadr (0 0)) False) | (: (cadr (0 0)) False)) : (cadr (0 0)))
(Listof a) -> a
Arguments: (Pairof String (Listof (U False String)))
Expected result: String
테일러링 후
id number: 42
trivial 라이브러리가 어떻게 동작하는지에 대한 구체적 내용은 이 글 맨 끝의 § 부록: trivial 라이브러리는 어떻게 동작하나?를 참고하세요.
문제는 Rust처럼 Typed Racket도 정규식 매칭 결과에 대해 지나치게 보수적인 타입을 부여해야 한다는 점입니다. 그 결과 프로그래머는 캐스트를 삽입해야 합니다. trivial 라이브러리는 Typed Racket 프로그램을 분석해 이러한 캐스트와 체크를 자동으로 삽입할 수 있습니다. 사용자가 보기에는 기대한 대로 이 코드가 Just Works™ 하는 결과가 됩니다.
또 주목할 점은 trivial이 라이브러리 라는 사실입니다. 컴파일러나 타입 체커를 수정할 필요가 전혀 없습니다. 즉, 일반적인 언어 사용자도 컴파일러를 망가뜨리거나 빌드 파이프라인을 어지럽히지 않고 자신만의 테일러링을 만들 수 있습니다.
타입 테일러링이 동작하려면 무엇이 필요할까요? 잠깐 뒤로 물러서서, 애초에 무엇을 해야 하는지부터 보죠. 문제는 타입 체커가 우리가 아는 만큼 프로그램에 대해 알지 못한다는 것입니다. 타입 체커를 가르치기 위해 우리가 할 수 있는 일은 _엘라보레이션(elaboration) 단계_를 프로그래밍하는 것입니다. 표면 문법(surface syntax)에는 보통 모든 지점에 타입 주석이 달려 있지 않습니다. 엘라보레이션은 프로그래머가 쓴 문법을 받아, 필요한 곳에 타입과 타입 홀(type hole)을 추가합니다. 이렇게 엘라보레이션된 문법은 제약 조건 솔버로 보내져 타입 체크와 타입 추론을 수행합니다.
엘라보레이션 단계를 어떻게 프로그래밍할까요? 매크로가 있는 거의 모든 언어는 매크로 확장(macroexpansion) 이후 타입 체크를 수행합니다. 이것이 타입 테일러링에 결정적으로 중요합니다. 타입 체커가 만족하도록, 체크/캐스트/타입 주석 등 필요한 무엇이든 추가하는 매크로를 작성할 수 있습니다.
타입 테일러링을 작동시키기 위해 반드시 필요한 핵심 기능은 다음과 같습니다:
syntax-case나 Rust의 macro_rules!)는 패턴 → 패턴 변환으로 문법을 재배열할 수 있을 뿐, 임의의 재작성(arbitrary rewrites)은 수행할 수 없습니다.이 세 가지는 테일러링이 가능해지기 위한 필수 요소입니다. 이 외에도 아래 기능들 중 일부가 있으면 좋습니다:
어떤 언어도 이 모든 기능을 지원하지는 않습니다—그 점이 오히려 흥미롭습니다. 탐구할 여지가 남아 있다는 뜻이니까요! 논문에서는 각 기능과 그것이 가능하게 하는 테일러링을 자세히 다룹니다. 또한 몇 가지 언어를 비교해 어떤 기능을 얼마나 지원하는지 보여주는 차트도 포함했습니다.
우리는 “type tailoring(타입 테일러링)”이라는 용어를 만들었지만, 아이디어 자체를 발명한 것은 아닙니다. 프로그래머들은 오래전부터 타입 시스템이 도메인 특화 관심사를 이해하길 원해왔습니다. 우리가 찾은, 이미 타입 테일러링을 하고 있던 프로젝트 몇 가지는 다음과 같습니다:
Rust의 SQLx 라이브러리는 컴파일 타임에 데이터베이스에 접근해 코드 속 스키마가 실제 DB 설정과 일치하는지 확인합니다. 쿼리가 잘못되면 컴파일 타임에 경고해줍니다.
Julia의 StaticArrays 패키지는 정적으로(컴파일 타임에) 크기가 알려진 리스트를 튜플로 재작성합니다. 이렇게 하면 컴파일러가 리스트 길이를 추적할 수 있고, 많은 경계 검사(bounds checks)를 자동으로 제거합니다—수치 계산을 많이 할 때 유용합니다.
Elixir의 Phoenix 웹 프레임워크는 템플릿 파일의 라우트가 라우트 핸들러와 일치하는지 검사합니다. 오타를 내거나 어떤 라우트의 핸들러 구현을 빼먹으면 Phoenix가 컴파일 타임에 경고해줍니다. 이 기능은 verified routes라고 부릅니다.
물론 이는 극히 일부에 불과합니다. 이 프로젝트들이 어떻게 타입 테일러링을 사용하고 있는지, 그리고 우리가 발견한 다른 예시들은 논문을 참고해주세요.
우리 논문의 큰 기여는 다음과 같습니다:
타입 테일러링 이라는 용어를 도입합니다. 아이디어는 여러 언어에서 다양한 형태로 나타났지만, 그 노력을 하나로 묶는 근거와 논리가 없었습니다. 이제 현상을 식별했으니, 이를 직접적이고 의식적으로 논의하고 지원할 수 있습니다.
테일러링이 동작하기 위한 핵심 요소들을 식별했습니다. 언어 설계자들은 이를 활용해 자신의 언어에서 타입 테일러링을 더 잘 지원하도록 설계할 수 있습니다.
사용자에게, 테일러링이 사용 편의성과(ergonomics) 의존 타입 시스템에서나 보던 기능을 어떻게 균형 있게 제공할 수 있는지 보여줍니다.
또한 우리는 두 개의 라이브러리를 만들었습니다. Racket용 trivial은 벡터, 정규식 등 다양한 것을 테일러링하고, Rhombus용 Dyn은 테일러링을 통해 Rhombus를 점진적 타입(gradually-typed) 언어로 바꿉니다. 앞으로 더 많은 것이 만들어질 거라 기대합니다.
다시 말하지만 자세한 내용은 논문을 봐주세요. 논문에는 아티팩트도 함께 제공되며, 논문 속 모든 코드가 들어 있습니다. Docker 컨테이너를 다운로드해서 코드를 실행하고 우리의 주장을 검증할 수 있습니다. 재현 가능한 연구 만세!
질문이 있다면 이메일로 연락해주세요. (이메일은 논문과 블로그의 연락처에도 있습니다.) 올해 비엔나에서 열리는 ECOOP에 오신다면 알려주세요. 현장에서 직접 이야기해요!
§ 해결책의 개략에서 본 trivial 라이브러리 예시는 다음과 같습니다:
#lang typed/racket
(require trivial trivial/list) ;; 프로그램을 테일러링하려면 이 줄을 추가
(define (user-idnum (username : String)) : Number
(define re "[a-z]+([0-9][0-9])")
(define m (regexp-match re username))
(if m
(string->number (second m))
(error "bad username")))
(printf "id number: ~a\n" (user-idnum "dent42"))
보통 Typed Racket은 m의 타입이 second에 적용하기엔 너무 일반적이라서 이 코드를 거부합니다. 아래는 trivial 라이브러리가 이 예시를 테일러링해 동작하게 만드는 과정입니다:
먼저 문자열 리터럴 "[a-z]+([0-9][0-9])" 같은 값을 감싸는 암묵적 #%datum 폼을 오버라이드합니다. 이를 통해 문자열을 읽어 컴파일 타임에 유의미한 정보를 수집할 수 있습니다.
라이브러리는 문자열에 매칭된 괄호 쌍이 하나 있다는 것을 봅니다. 또한 괄호 안 패턴이 전부 숫자(digit)로만 구성되어 있다는 것도 봅니다. 그리고 이 정보를 해당 문자열의 문법 객체(syntax object)에 syntax property로 붙입니다.
이 정보는 식별자 re의 모든 등장(occurrence)으로 전파됩니다.
라이브러리는 regexp-match도 오버라이드하여, 첫 번째 인자에 붙은 syntax property를 확인합니다. 이 경우 re가 캡처 그룹이 1개인 문자열임을 확인합니다. 그리고 m의 반환 타입을 (Pairof String (Listof (U False String)))에서 (U (List String String) False)로 업데이트합니다.
if 문의 참(true) 브랜치에서, Typed Racket은 자동으로 m의 타입을 (List String String)으로 정제(refine)할 수 있습니다.
trivial 라이브러리는 second를 오버라이드하여 인자의 타입을 검사합니다. (List String String)이 이 호출이 성공하기에 충분히 길다는 것을 확인하므로, 더 빠른 unsafe 조회 함수로 테일러링합니다.
string->number도 매치에 대한 정보를 보도록 오버라이드됩니다. 2단계에서 매치가 숫자로만 구성됨을 확인할 수 있었기 때문에, 반환 타입을 (U Complex False)에서 Number로 업데이트합니다.
할 일이 정말 많죠! 멋진 점은 trivial이 이 모든 일을 꽤 일반화된 방식으로 해낸다는 것입니다. 한 구성요소는 문자열을 다루고, 다른 구성요소는 정규식을 다루며, 또 다른 구성요소는 알려진 크기의 리스트를 다룹니다. 그리고 Typed Racket의 스코핑 규칙을 존중하는 syntax property를 통해 이 정보를 공유할 수 있습니다. 다른 메타프로그래밍과도 잘 어울립니다. 예를 들어 if를 not-if로 바꿔 브랜치를 뒤집는 매크로를 작성할 수도 있겠지만, 그 경우에도 변수 m에 대한 필요한 정보는 올바른 곳으로 전파되었을 것입니다.
불행히도 현재 형태로는 이 예시를 Rust에서 동작하게 만들 방법이 없습니다(적어도 지금으로서는). 이는 언어마다 지원하는 테일러링의 종류가 다르기 때문입니다. 논문에서는 언어가 테일러링을 지원할 수 있는 다양한 차원을 모두 탐구합니다.
여기 작은 테일러링을 만드는 방법이 있습니다. 이 테일러링에서는, 인덱스가 범위 내(in-bounds)임이 알려진 배열 조회를 빠른 unsafe 조회로 바꾸고 싶습니다. 의존 타입 언어라면 인덱스와 벡터의 타입을 보고(벡터 타입이 길이를 포함하므로) 이를 수행할 수 있을 겁니다. Racket에는 그런 힘이 없습니다. 하지만 테일러링을 통해 그 힘을 조금 가져올 수 있습니다.
이 섹션은 논문의 §3.8에서 거의 그대로 가져왔습니다. 이 코드는 실제로 실행됩니다!
테일러링하고 싶은 예시는 다음과 같습니다. 벡터의 길이와 인덱스를 안다면, 경계 검사를 생략하는 unsafe-vector-ref로 테일러링하거나, 인덱스가 범위를 벗어나면 에러로 테일러링할 수 있습니다. 반대로 벡터 길이나 인덱스를 모르면, 경계 검사를 수행하는 안전한 vector-ref를 유지합니다:
(vector-ref (vector 5 2 8) 1) ; 테일러링 → (unsafe-vector-ref (vector 5 2 8) 1)
(vector-ref (vector 4 9 1) 4) ; 테일러링 → error: out of bounds
(vector-ref (read-vec) 9) ; 테일러링 → (vector-ref (read-vec) 9)
구현은 이렇게 합니다:
#lang racket
(provide
(rename-out [tailored-vector-ref vector-ref]))
코드 조각 1: mini-tailoring.rkt, 5개 중 1
(provide (rename-out …))는 이 모듈이 임포트될 때 함수 tailored-vector-ref를 vector-ref라는 이름으로 내보내라(export) 고 말합니다. 즉, 이 모듈이 임포트되면 vector-ref 호출은 자동으로 모두 tailored-vector-ref를 사용하게 됩니다.
(require
(only-in racket/unsafe/ops unsafe-vector-ref)
(for-syntax
racket/base syntax/parse ;; 메타프로그래밍 지원
(only-in "tailoring-api.rkt"
⇝ ;; 확장 **순서(Order)** 를 제어
φ ;; 정적 정보(**메타데이터**)를 읽고/쓰기 위한 API
V ;; 벡터 길이 정보용 도메인 특화 키(**위생성(Hygiene)**)
I))) ;; 정수 값 정보용 도메인 특화 키(**위생성(Hygiene)**)
코드 조각 2: mini-tailoring.rkt, 5개 중 2
이제 몇 가지 헬퍼를 임포트합니다. racket/unsafe/ops는 테일러링 대상인 unsafe-vector-ref를 제공합니다. 이 함수는 잘못 사용하면 세그폴트를 일으킬 수 있으므로 조심해야 합니다. syntax/parse는 훌륭한 syntax-parse 매크로 기능을 제공하므로 가져옵니다. 또한 tailoring-api.rkt에서 네 가지 심볼을 가져오는데, 각각은 언급할 가치가 있습니다:
⇝: 부분식(subexpression)에 대해 매크로 확장을 트리거하는 syntax class입니다. 이를 통해 테일러링이 구성요소들에 대한 정적 정보를 발견할 수 있습니다.φ: Racket의 syntax property를 사용해 정적 정보를 저장/검색하는 함수입니다.V, I: 벡터 길이와 정수 값 정보를 조회하기 위한 유일한 키들(gensym으로 생성)입니다. 유일하므로 다른 테일러링이 실수로 이 정보와 충돌하지 않습니다.tailoring-api.rkt 파일은 작고, 사실상 이런 편의 함수를 제공할 뿐입니다. 아티팩트에서 찾을 수 있습니다.
이제 테일러링의 핵심으로 들어갑니다. 테일러링은 소스 코드를 정적으로 재작성해야 하므로 매크로입니다. 먼저 입력 문법 객체 stx를 파싱하여 두 부분식 e1, e2를 추출하고 확장합니다:
(define-syntax (tailored-vector-ref stx)
(syntax-parse stx
[(_ e1:⇝ e2:⇝)
코드 조각 3: mini-tailoring.rkt, 5개 중 3
이제 테일러링은 확장된 표현식들에 필요한 정적 정보가 있는지 검사합니다. 구체적으로는 벡터 길이(키: V)와 정수 값(키: I)을 찾습니다:
#:do [(define n (φ #'e1.⇝ V))
(define i (φ #'e2.⇝ I))]
#:when (and (integer? n)
(integer? i))
코드 조각 4: mini-tailoring.rkt, 5개 중 4
정보가 있으면, 안전한 경우 unsafe-vector-ref로 확장하고, 그렇지 않으면 에러를 발생시키는 코드로 확장합니다. 정보가 없다면 평범한 vector-ref로 폴백합니다:
(if (and (<= 0 i) (< i n))
#`(unsafe-vector-ref e1.⇝ e2.⇝)
#`(error 'Index-Exn))]
[(_ e1:⇝ e2:⇝)
#`(vector-ref e1.⇝ e2.⇝)]))
코드 조각 5: mini-tailoring.rkt, 5개 중 5
이게 전부입니다! Racket 프로그램은 이 테일러링을 임포트해 아래 코드를 더 빠르게 실행할 수 있습니다:
#lang racket
(require "mini-tailoring.rkt")
(vector-ref (vector 5 2 8) 1) ; (unsafe-vector-ref (vector 5 2 8) 1)로 테일러링됨
이 프로그램을 파일로 저장한 다음 raco expand <filename>을 실행해 확장된 버전을 확인해보세요. 확장된 코드에 unsafe-vector-ref가 나타나는 것을 볼 수 있을 겁니다.