GADT 스타일 열거형을 활용한 Rust의 제로 코스트 '태그리스 파이널'

소개: 태그리스 파이널의 매력

함수형 프로그래밍 세계에서 "태그리스 파이널" 패턴은 임베디드 도메인 특화 언어(DSL)를 만들기 위한 훌륭한 추상화입니다. 이 패턴을 사용하면 언어 연산을 위한 인터페이스를 정의하고, 핵심 프로그램 로직을 바꾸지 않은 채 여러 인터프리터(예: 평가용, 보기 좋게 출력하는 용도, 최적화용)를 작성할 수 있습니다.

Rust와 같은 시스템 언어에서 핵심적인 시험대는, 제로 코스트 성능이라는 본질적 약속을 희생하지 않고도 이러한 고수준 추상화를 채택할 수 있는지입니다. 이 글에서는 일반화 대수적 데이터 타입(GADT)에 의존하는 이 패턴의 "태그리스 이니셜" 변형을 Rust로 구현하는 방법을 살펴봅니다. 신중한 타입 수준 프로그래밍을 통해 이러한 표현력 있는 구조를 만들고, 컴파일러가 이를 완전히 제거하여 최적의 어셈블리 코드를 생성하게 할 수 있음을 보이겠습니다.

목표: "태그리스 이니셜" 인코딩

Serokell의 태그리스 파이널 소개 같은 자료에서 설명하는 "태그리스 이니셜" 인코딩은 GADT로 표현식을 나타냅니다. Haskell에서는 다음과 같습니다.

data Expr a where
    IntConst :: Int                       -> Expr Int
    Lambda   :: (Expr a -> Expr b)        -> Expr (Expr a -> Expr b)
    Apply    :: Expr (Expr a -> Expr b)   -> Expr a -> Expr b
    Add      :: Expr Int -> Expr Int      -> Expr Int

eval :: Expr a -> a
eval (IntConst x) = x
eval (Lambda f)   = f
eval (Apply f x)  = eval (eval f x)
eval (Add l r)    = (eval l) + (eval r)

표현식 Expr a의 타입은 그것이 만들어 낼 값의 타입(a)과 연결되어 있다는 점에 주목하세요. 우리의 목표는 이 구조와 그 eval 함수를 Rust에서 재현하고, 계산된 결과 외에는 아무것도 남지 않도록 컴파일되는지 확인하는 것입니다.

첫 번째 살펴보기: Rust 표현식과 그 어셈블리

바로 시작해 보겠습니다. 다음은 GADT 스타일 인코딩을 사용해 복잡한 표현식을 구성하는 Rust 함수입니다. 여러 정수 상수, 람다(고차 람다 포함), 그리고 적용을 정의합니다.

fn expr(u: isize, v: isize, w: isize) -> Gadt<cu::Int, impl Attic> {
    let a = int_const(u);
    let b = int_const(v);
    let c = add::<(), _, _>(a, b);
    let d = lambda::<(), _, _, _, _, _>(move |x| {
        let a = int_const(u * 2 + v * 3 + w * 5);
        add::<(), _, _>(a, x)
    });
    let e = apply::<(), _, _, _>(d, c);
    let f = lambda::<(), _, _, _, _, _>(move |x| {
        let a = int_const(u * 3 + v * 5 + w * 13);
        add::<(), _, _>(add::<(), _, _>(a, x), c)
    });
    let j = lambda::<(), _, _, _, _, _>(move |x: Gadt<_, _>| -> Gadt<_, _> {
        apply::<(), _, cu::Int, _>(x, e)
    });
    apply::<(), _, _, _>(j, f)
}

#[inline(never)]
pub extern "C" fn eval_expr(u: isize, v: isize, w: isize) -> isize {
    expr(u, v, w).eval()
}

이는 무겁고 복잡한 구조처럼 보입니다. 하지만 릴리스 모드로 컴파일한 뒤 eval_expr의 어셈블리를 살펴보면 놀라운 결과를 볼 수 있습니다.

playground::eval_expr: # @playground::eval_expr
# %bb.0:
	leaq	(%rdx,%rdx,2), %rax
	leaq	(%rdx,%rax,4), %r8
	addq	%rsi, %rdx
	leaq	(%rdx,%rdx,4), %rdx
	leaq	(%rsi,%rdi,2), %rax
	leaq	(%rax,%rax,2), %rcx
	leaq	(%rdi,%rsi,2), %rax
	addq	%r8, %rax
	addq	%rdx, %rax
	addq	%rcx, %rax
	retq

표현식 트리 전체와 람다, apply 호출은 모두 일련의 산술 명령어(leaq, addq)로 축약되었습니다. 인터프리터 루프도, 동적 디스패치도, 메모리 할당도 없습니다. 이것이 실현된 "제로 코스트" 약속입니다.

인터프리터: 단순한 eval 구현

어떻게 이것이 가능할까요? 평가 로직은 Eval 트레이트에 정의되어 있습니다. Gadt 타입에 대한 구현은 구성 요소에 재귀적으로 eval을 호출하는 단순한 match 문입니다.

pub trait Eval<Cur: Cursor, Att: Attic> {
    fn eval(self) -> SolOf<Cur, Att>;
}

impl<Cur: Cursor, Att: Attic> Eval<Cur, Att> for Gadt<Cur, Att> {
    fn eval(self) -> SolOf<Cur, Att> {
        match self.0 {
            Enum::IntConst(v01, a) => v01.vu_cast::<_, _, _, _>(&a)(v01.get(a)),
            Enum::Lambda(v02, f) => v02.vu_cast::<_, _, _, _>(&f)(v02.get(f)),
            Enum::Apply(v03, t) => v03._vu_cast::<_, _, _, _, _>(&t)({
                let (f, a) = v03.get(t);
                let f = f.eval();
                f(a).eval()
            }),
            Enum::Add(v04, t) => v04.vu_cast::<_, _, _, _>(&t)({
                let (a, b) = v04.get(t);
                let a = a.eval();
                let b = b.eval();
                a + b
            }),
        }
    }
}

언뜻 보면 런타임 오버헤드를 수반할 표준 인터프리터처럼 보입니다. 최적화의 핵심은 Gadt와 Enum 타입의 정의에 있습니다.

막 뒤의 마법: GADT와 유사한 열거형

이 기법의 핵심은 Rust의 never 타입(!)을 사용하여, 주어진 타입 시그니처마다 실제로 생성 가능한 배리언트가 하나뿐이도록 보장하는 enum입니다. 컴파일러는 컴파일 시점에 어떤 배리언트가 사용되는지 알기 때문에, 이는 사실상 열거형에서 "태그"를 제거합니다.

pub struct Gadt<Cur: Cursor, Att: Attic>(
    Enum<Cur::_V01<Att>, Cur::_V02<Att>, Cur::_V03<Att>, Cur::_V04<Att>, Cur, Att>,
);

pub enum Enum<V01: Ng, V02: Ng, V03: Ng, V04: Ng, Cur: Cursor, Att: Attic> {
    __Ph__(!, Ph<(V01, V02, V03, V04, Cur, Att)>),
    IntConst(V01, V01::NGuard<isize, Cur, cu::Int, Att>),
    Lambda(
        V02,
        V02::NGuard<
            Att::Fun<ReprOf<Att, Cur::_1, Att::_1>, ReprOf<Att, Cur::_2, Att::_2>>,
            Cur,
            cu::ReprFun<Cur::_1, Cur::_2>,
            Att,
        >,
    ),
    Apply(
        V03,
        V03::NGuard<
            (
                ReprOf<Att, cu::ReprFun<Att::DomCur, V03::CGuard<Cur>>, Att::FunAtt>,
                ReprOf<Att, Att::DomCur, _1Of<Att::FunAtt>>,
            ),
            Cur,
            V03::CGuard<Cur>,
            _2Of<Att::FunAtt>,
        >,
    ),
    Add(
        V04,
        V04::NGuard<
            (ReprOf<Att, cu::Int, Att::_1>, ReprOf<Att, cu::Int, Att::_2>),
            Cur,
            cu::Int,
            Att,
        >,
    ),
}

V01부터 V04까지의 타입은 Attic 트레이트가 제어합니다. 이를 !로 설정하면 해당 배리언트를 생성하는 것이 불가능해집니다. ! 타입의 값은 결코 만들 수 없으므로, 컴파일러는 그 코드 경로에 도달할 수 없음을 증명할 수 있습니다. NGuard 트레이트는 !로 "비활성화된" 배리언트의 크기가 0이 되도록 보장하는 도우미이며, 이로써 enum이 유일하게 활성화된 배리언트의 크기로 축소될 수 있습니다.

핵심 구성 요소: Cursor와 Attic

조율을 담당하는 두 트레이트는 Cursor와 Attic입니다. 이들은 타입 수준 구성 시스템으로 함께 작동합니다.

• Attic: 이 트레이트는 어떤 Enum 생성자가 비활성화되는지에 관한 실제 정보를 보관합니다. 기본 상태에서는 모든 _V* 타입을 !로 설정하여 모든 배리언트를 사실상 비활성화합니다. 생성자를 활성화하려면 특정 Attic 구현이 !이 아닌 타입을 제공합니다.
• Cursor: 이 트레이트는 필터 또는 뷰 역할을 하며, 표현식 트리의 각 지점에서 Attic의 어떤 구성을 적용할지 선택합니다.

pub trait Attic {
    // ... 기본값은 `!` ...
    type _V01: NGuard = !;
    type _V02: NGuard = !;
    type _V03: NGuard = !;
    type _V04: NGuard = !;
    // ... 그 밖의 연관 타입 ...
}

pub trait Cursor {
    // ... Attic의 구성을 사용 ...
    type _V01<Att: Attic>: NGuard = Att::_V01;
    type _V02<Att: Attic>: NGuard = Att::_V02;
    type _V03<Att: Attic>: NGuard = Att::_V03;
    type _V04<Att: Attic>: NGuard = Att::_V04;
    // ... 그 밖의 연관 타입 ...
}

이 메커니즘을 통해 Enum 배리언트 중 하나만 유효한 Gadt 타입을 구성할 수 있으며, 그 결과 eval의 패턴 매칭은 컴파일 시점에 완전히 예측 가능해집니다.

제로 코스트 증명: never 타입 실험

이 불변 조건을 깨뜨리면 어떻게 될까요? 실험을 해보겠습니다. Attic 트레이트에서 !를 ((),)처럼 구체적인 크기 0 타입으로 바꿉니다. 이는 이제 이론적으로 모든 배리언트를 생성할 수 있다는 뜻입니다.

// Attic에서 기본값을 변경합니다:
// 이전: type _V01: NGuard = !;
// 이후: type _V01: NGuard = ((),); // V02, V03, V04도 동일하게 변경

갑자기 컴파일러는 어떤 배리언트가 활성 상태인지 더 이상 보장할 수 없습니다. 이제 태그(판별값)를 포함하고 런타임 검사를 수행해야 합니다. 생성되는 어셈블리는 크게 늘어납니다.

playground::eval_expr: # @playground::eval_expr
# %bb.0:
	pushq	%r15
	pushq	%r14
	pushq	%r13
	pushq	%r12
	pushq	%rbx
	subq	$32, %rsp
    ...
	callq	<playground::Gadt<Cur,Att> as playground::Eval<Cur,Att>>::eval
    ...
	callq	<playground::Gadt<Cur,Att> as playground::Eval<Cur,Att>>::eval
    ...
	popq	%r15
	retq

이제 eval에 대한 명시적인 호출이 보입니다. 추상화는 더 이상 제로 코스트가 아니며 런타임에 해석되고 있습니다. 이는 never 타입이 태그 없음을 달성하고 컴파일러 최적화를 가능하게 하는 핵심 구성 요소임을 보여줍니다.

단순히 eval에 #[inline(always)]를 추가하면 이를 해결할 수 있다고 생각할 수도 있습니다. 실제로 이 간단한 경우에는 인라이닝이 최적화기가 호출을 풀어내고 훨씬 나은 어셈블리를 생성하도록 도울 수 있습니다. 하지만 이는 견고한 해결책이 아닙니다. 최적화기의 뛰어난 능력에 의존하며, DSL이 중첩되거나 서로 다른 크레이트에 걸쳐 정의되는 더 복잡하고 모듈화된 프로그램에서는 실패할 가능성이 큽니다. never 타입 접근법은 구조적으로 최적화를 보장합니다.

결론

Rust의 타입 시스템, 특히 never 타입(!)을 신중하게 활용하면 "태그리스 이니셜" 패턴을 성공적으로 구현할 수 있습니다. 우리는 주어진 타입마다 하나의 배리언트만 생성 가능한 GADT 스타일 열거형을 만들었으며, 이를 통해 런타임 태그의 필요성을 사실상 제거했습니다. 덕분에 컴파일러는 추상화를 완전히 꿰뚫어 보고 복잡한 표현식 트리를 순수한 계산 등가물로 축소할 수 있습니다.

이 기법은 시스템 언어에 기대되는 성능을 타협하지 않으면서 Rust에서 고수준의 표현력 있는 DSL을 구축할 수 있는 강력한 청사진을 제공합니다.

전체 코드는 직접 실험해 볼 수 있습니다.

• Rust Playground
• 전체 소스가 담긴 Gist