Rust 로 복잡한 매크로를 작성하기: 역폴란드 표기법

Rust에는 흥미로운 기능이 많지만 그중에도 강력한 매크로 시스템이 있습니다. 불행히도 The Book[1]과 여러가지 튜토리얼을 읽고 나서도 서로 다른 요소의 복잡한 리스트를 처리하는 매크로를 구현하려고 하면 저는 여전히 어떻게 만들어야 하는지를 이해하는데 힘들어 하며, 좀 시간이 지나서 머리속에 불이 켜지는 듯한 느낌이 들면 그제서야 이것저것 매크로를 마구 사용하기 시작 합니다. :) (맞아요, 난-매크로를-써요-왜냐하면-함수나-타입-지정이나-생명주기를-쓰고-싶어하지-않아서 처럼과 같은 이유는 아니지만 다른 사람들이 쓰는걸 봤었고 실제로 유용한 곳이라면 말이죠)

CC BY 2.0 image by Conor Lawless

그래서 이 글에서는 제가 생각하는 그런 매크로를 쓰는 데 필요한 원칙을 설명하고자 합니다. 이 글에서는 The Book의 매크로 섹션을 읽어 보았고 기본적인 매크로 정의와 토큰 타입에 대해 익숙하다고 가정하겠습니다.

이 튜토리얼에서는 역폴란드 표기법 (Reverse Polish Notation, RPN)을 예제로 사용합니다. 충분히 간단하기 때문에 흥미롭기도 하고, 학교에서 이미 배워서 익숙할 지도 모르고요. 하지만 컴파일 시간에 정적으로 구현하기 위해서는 재귀적인 매크로를 사용해야 할 것입니다.

2 3 + 4 *

역폴란드 표기법(후위 또는 후치 표기법으로 불리기도 합니다)은 모든 연산에 스택을 사용하므로 연산 대상을 스택에 넣고 [이진] 연산자는 연산 대상 두개를 스택에서 가져와서 결과를 평가하고 다시 스택에 넣습니다. 따라서 다음과 같은 식을 생각해 보면:

이 식은 다음과 같이 해석됩니다:

2를 스택에 넣음
3을 스택에 넣음
스택에서 두 값을 가져옴 (3과 2), 연산자 +를 적용하고 결과 (5)를 스택에 다시 넣음
4를 스택에 넣음
스택에서 마지막 두 값을 가져옴 (4와 5), 연산자 * 를 적용하고 (4 * 5) 결과 (20)을 스택에 다시 넣음
식의 끝. 스택에 들어 있는 결과값은 20 한가지.

수학에서 사용되고 대부분의 현대적인 프로그래밍 언어에서 사용되는 일반적인 중위 표기법에서는 (2 + 3) * 4 로 표현이 됩니다.

macro_rules! rpn {
  // TODO
}

println!("{}", rpn!(2 3 + 4 *)); // 20

이제 역폴란드 표기법을 컴파일 시간에 평가하여 Rust가 이해할 수 있는 중위 표기법으로 변환해 주는 매크로를 작성해 보도록 합시다.

스택에 숫자를 넣는 것 부터 시작해 봅시다.

macro_rules! rpn {
  ($num:tt) => {
    // TODO
  };
}

매크로는 현재 문자에 매칭하는 것을 허용하지 않으므로 expr은 사용할 수 없는데 숫자 하나를 읽어들이기 보다는 2 + 3 ...와 같은 문자열과 매칭할 수 있기 때문입니다. 따라서 (문자/식별자/유효기간 등과 같은 기본 토큰 또는 더 많은 토큰을 포함하고 있는 ()/[]/{} 스타일의 괄호식) 토큰 트리를 하나만 읽어들일 수 있는 일반적인 토큰 매칭 기능인 tt를 사용하도록 하겠습니다.

이제 스택을 위한 변수가 필요 합니다.

우리는 이 스택이 컴파일 시에만 존재하기를 원하므로 매크로는 실제 변수를 사용할 수 없습니다. 따라서 그 대신에 전달 가능한 별도의 토큰 열을 갖고 축적자 같이 사용되게 하는 트릭을 쓰도록 합니다.

macro_rules! rpn {
  ([ $($stack:expr),* ] $num:tt) => {
    // TODO
  };
}

이 경우, (간단한 숫자 뿐 아니라 중간 형태의 중위 표현식을 위해서도 사용할 것이므로) 스택을 쉼표로 분리된 expr 의 열로 표현하고 다른 입력에서 분리하기 위해 각괄호로 둘러싸도록 합시다:

여기서 토큰 열은 실제 변수는 아닙니다 - 내용을 바꾸거나 나중에 다른 일을 시킬 수는 없습니다. 대신에 이 토큰 열에 필요한 변경을 해서 새 복사본을 만들 수 있고 재귀적으로 같은 매크로를 다시 부를 수 있습니다.

macro_rules! rpn {
  ([ $($stack:expr),* ] $num:tt) => {
    rpn!([ $num $(, $stack)* ])
  };
}

함수형 언어의 기본 지식이 있거나 불변 데이터를 제공하는 라이브러리를 이용해 본 적이 있다면, 이런 접근 방법 - 변경된 복사본을 만드는 것으로 데이터를 변경하거나 재귀를 통해 리스트를 처리하는 - 은 이미 익숙할 것입니다:

macro_rules! rpn {
  ([ $($stack:expr),* ] $num:tt $($rest:tt)*) => {
      rpn!([ $num $(, $stack)* ] $($rest)*)
  };
}

이제 분명한 것은 간단한 숫자만의 경우라면 별로 있을것 같지 않고 크게 흥미롭지도 않을 것이므로 그 숫자 이후의 0개나 그 이상의 tt 토큰을 찾도록 합니다. 이것은 추가적인 매칭과 처리를 위해 이 매크로의 다음번 호출에 전달될 수 있습니다:

이 시점에서는 아직 연산자를 지원하지 않습니다. 연산자는 어떻게 매칭해야 할까요?

우리의 RPN이 완전히 동일한 방법으로 처리하기를 원하는 토큰 열이라 한다면, 단순히 $($token:tt)* 처럼 리스트를 사용할 수 있습니다. 불행히도 이렇게 하면 리스트를 돌아보거나 연산 대상을 집어 넣거나 각 토큰에 따라 연산자를 적용하는 기능을 만들 수 없습니다.

The Book은 "매크로 시스템의 파싱은 명확해야 한다"라고 하고 있으며 이는 단일 매크로 가지에 있어서는 사실입니다 - +는 유효한 토큰이며 tt 그룹에 매칭이 될 수도 있으므로 $($num:tt)* + 와 같은 연산자 뒤에 오는 숫자의 열은 매칭할 수 없는데, 여기서 재귀적 매크로의 도움을 받을 수 있습니다.

macro_rules! rpn {
  ([ $($stack:expr),* ] + $($rest:tt)*) => {
    // TODO
  };
  
  ([ $($stack:expr),* ] - $($rest:tt)*) => {
    // TODO
  };
  
  ([ $($stack:expr),* ] * $($rest:tt)*) => {
    // TODO
  };
  
  ([ $($stack:expr),* ] / $($rest:tt)*) => {
    // TODO
  };

  ([ $($stack:expr),* ] $num:tt $($rest:tt)*) => {
    rpn!([ $num $(, $stack)* ] $($rest)*)
  };
}

여러분의 매크로 정의에 복수의 가지가 있다면 Rust는 이것들을 하나씩 시도하므로 숫자 처리 이전에 연산자 가지를 놓는 방식으로 충돌을 방지할 수 있습니다:

macro_rules! rpn {
  ([ $b:expr, $a:expr $(, $stack:expr)* ] + $($rest:tt)*) => {
    rpn!([ $a + $b $(, $stack)* ] $($rest)*)
  };

  ([ $b:expr, $a:expr $(, $stack:expr)* ] - $($rest:tt)*) => {
    rpn!([ $a - $b $(, $stack)* ] $($rest)*)
  };

  ([ $b:expr, $a:expr $(, $stack:expr)* ] * $($rest:tt)*) => {
    rpn!([ $a * $b $(,$stack)* ] $($rest)*)
  };

  ([ $b:expr, $a:expr $(, $stack:expr)* ] / $($rest:tt)*) => {
    rpn!([ $a / $b $(,$stack)* ] $($rest)*)
  };

  ([ $($stack:expr),* ] $num:tt $($rest:tt)*) => {
    rpn!([ $num $(, $stack)* ] $($rest)*)
  };
}

앞에서 이야기 했듯이 연산자는 스택의 마지막 두 숫자에 적용되므로 이것들은 별도로 매칭해서 그 결과를 "평가" 하고 (일반적인 중위 표현식을 구성) 다시 집어 넣습니다:

저는 이렇게 대놓고 반복하는 것을 그리 좋아하지 않습니다만 문자와 같이 연산자에 매칭하는 토큰 타입은 따로 없습니다.

하지만 할 수 있는 일은 평가를 담당하는 도우미를 추가 하고 명시적인 연산자 가지를 그쪽으로 위임하는 일입니다.

매크로에서는 외부 도우미를 사용할 수는 없지만 확실한 것은 여러분의 매크로가 이미 존재 한다는 것이므로, 사용할 수 있는 트릭은 유일한 토큰 열로 "표식"이 되어 있는 동일 매크로에 가지를 만들고 일반 가지에서 했던 것 처럼 재귀적으로 호출하는 것입니다.

@op를 그런 표식으로 사용하고 그 안에서 tt를 통한 어떤 연산자라도 받아들이도록 합니다(우리는 연산자만을 이 도우미에게 전달하므로 이러한 문맥에서는 tt는 애매한 점이 없습니다).

macro_rules! rpn {
  (@op [ $b:expr, $a:expr $(, $stack:expr)* ] $op:tt $($rest:tt)*) => {
    rpn!([ $a $op $b $(, $stack)* ] $($rest)*)
  };

  ($stack:tt + $($rest:tt)*) => {
    rpn!(@op $stack + $($rest)*)
  };
  
  ($stack:tt - $($rest:tt)*) => {
    rpn!(@op $stack - $($rest)*)
  };

  ($stack:tt * $($rest:tt)*) => {
    rpn!(@op $stack * $($rest)*)
  };
  
  ($stack:tt / $($rest:tt)*) => {
    rpn!(@op $stack / $($rest)*)
  };

  ([ $($stack:expr),* ] $num:tt $($rest:tt)*) => {
    rpn!([ $num $(, $stack)* ] $($rest)*)
  };
}

그리고 스택은 더 이상 각각의 개별 가지에서 확장될 필요가 없습니다 - 앞에서 [] 으로 둘러 쌓았기 때문에 또 다른 토큰 나무(tt)로서 매칭될 수 있고 이후에 도우미에게 전달이 됩니다:

macro_rules! rpn {
  // ...
  
  ([ $result:expr ]) => {
    $result
  };
}

이제 어떤 토큰이라도 해당하는 가지에서 처리가 되므로 스택에 하나의 아이템만 있고 다른 토큰이 없는 마지막 경우만 처리하면 됩니다:

이 시점에서 빈 스택과 RPN 표현식으로 이 매크로를 실행 하면 이미 제대로 된 결과를 만들어 냅니다:

println!("{}", rpn!([] 2 3 + 4 *)); // 20

운동장

하지만 이 스택은 내부적인 구현 사항이라 사용자가 매번 빈 스택을 전달하도록 하기를 바라지는 않으므로, 시작 지점으로 사용될 수 있고 []을 자동적으로 추가해 주는 가지를 하나 더 추가합니다:

macro_rules! rpn {
  // ...

  ($($tokens:tt)*) => {
    rpn!([] $($tokens)*)
  };
}

println!("{}", rpn!(2 3 + 4 *)); // 20

운동장

println!("{}", rpn!(15 7 1 1 + - / 3 * 2 1 1 + + -)); // 5

이제 우리의 매크로는 위키피디아의 RPN페이지에 있는 복잡한 표현식 예제도 잘 처리 합니다!

오류 처리

이제 올바른 RPN 표현식에 대해서는 모든것이 잘 되는 것 같습니다만, 실제 사용 가능한 매크로가 되려면 잘못된 입력도 잘 처리해서 적절한 오류 메시지를 표시하도록 해야 합니다.

println!("{}", rpn!(2 3 7 + 4 *));

일단 중간에 숫자 하나를 넣어서 어떻게 되는지 보도록 하면:

error[E0277]: the trait bound `[{integer}; 2]: std::fmt::Display` is not satisfied
  --> src/main.rs:36:20
   |
36 |     println!("{}", rpn!(2 3 7 + 4 *));
   |                    ^^^^^^^^^^^^^^^^^ `[{integer}; 2]` cannot be formatted with the default formatter; try using `:?` instead if you are using a format string
   |
   = help: the trait `std::fmt::Display` is not implemented for `[{integer}; 2]`
   = note: required by `std::fmt::Display::fmt`

출력:

괜찮은 것 같지만 표현식 내의 실제 오류에 대한 정보는 제공하지 않으므로 유용해 보이지는 않습니다.

어떤 일이 일어나는지 알기 위해서는 매크로를 디버깅해야 합니다. 이를 위해서 trace_macros 기능을 사용하도록 합니다(다른 부가적인 컴파일러 기능처럼 Rust의 일일 빌드가 필요할 것입니다). println! 을 추적하고 싶은 건 아니므로 RPN 표현식을 변수로 분리 합니다:

#![feature(trace_macros)]

macro_rules! rpn { /* ... */ }

fn main() {
  trace_macros!(true);
  let e = rpn!(2 3 7 + 4 *);
  trace_macros!(false);
  println!("{}", e);
}

운동장

note: trace_macro
  --> src/main.rs:39:13
   |
39 |     let e = rpn!(2 3 7 + 4 *);
   |             ^^^^^^^^^^^^^^^^^
   |
   = note: expanding `rpn! { 2 3 7 + 4 * }`
   = note: to `rpn ! ( [  ] 2 3 7 + 4 * )`
   = note: expanding `rpn! { [  ] 2 3 7 + 4 * }`
   = note: to `rpn ! ( [ 2 ] 3 7 + 4 * )`
   = note: expanding `rpn! { [ 2 ] 3 7 + 4 * }`
   = note: to `rpn ! ( [ 3 , 2 ] 7 + 4 * )`
   = note: expanding `rpn! { [ 3 , 2 ] 7 + 4 * }`
   = note: to `rpn ! ( [ 7 , 3 , 2 ] + 4 * )`
   = note: expanding `rpn! { [ 7 , 3 , 2 ] + 4 * }`
   = note: to `rpn ! ( @ op [ 7 , 3 , 2 ] + 4 * )`
   = note: expanding `rpn! { @ op [ 7 , 3 , 2 ] + 4 * }`
   = note: to `rpn ! ( [ 3 + 7 , 2 ] 4 * )`
   = note: expanding `rpn! { [ 3 + 7 , 2 ] 4 * }`
   = note: to `rpn ! ( [ 4 , 3 + 7 , 2 ] * )`
   = note: expanding `rpn! { [ 4 , 3 + 7 , 2 ] * }`
   = note: to `rpn ! ( @ op [ 4 , 3 + 7 , 2 ] * )`
   = note: expanding `rpn! { @ op [ 4 , 3 + 7 , 2 ] * }`
   = note: to `rpn ! ( [ 3 + 7 * 4 , 2 ] )`
   = note: expanding `rpn! { [ 3 + 7 * 4 , 2 ] }`
   = note: to `rpn ! ( [  ] [ 3 + 7 * 4 , 2 ] )`
   = note: expanding `rpn! { [  ] [ 3 + 7 * 4 , 2 ] }`
   = note: to `rpn ! ( [ [ 3 + 7 * 4 , 2 ] ] )`
   = note: expanding `rpn! { [ [ 3 + 7 * 4 , 2 ] ] }`
   = note: to `[(3 + 7) * 4, 2]`

이제 출력을 보면 이 매크로가 단계별로 어떻게 재귀적으로 평가되는지 알 수 있습니다:

   = note: expanding `rpn! { [ 3 + 7 * 4 , 2 ] }`
   = note: to `rpn ! ( [  ] [ 3 + 7 * 4 , 2 ] )`

잘 따라가 보면 다음 단계가 문제라는 것을 알 수 있습니다:

[ 3 + 7 * 4 , 2 ]는 ([$result:expr]) => ... 가지에 최종 표현식으로 매칭되지 않으므로 그 대신 마지막 가지인 ($($tokens:tt)*) => ... 에 매칭이 되므로 빈 스택 []이 앞에 추가 되고서 원래의 [ 3 + 7 * 4 , 2 ]는 일반적인 $num:tt에 매칭되어 단일 최종 값으로 스택에 들어가게 됩니다.

이런 일을 방지하기 위해서 어떤 스택과도 매칭이 되는 마지막 두 가지 시이에 가지를 하나 더 추가하도록 합니다.

이것은 토큰이 다 떨어졌을 때만 해당할 것이지만 스택에는 최종값 하나만 들어있지 않을 것이므로 이를 컴파일 오류로 취급하고 내장된 compile_error! 매크로를 사용해서 적절한 오류 메시지를 출력 하도록 합니다.

주의할 것은 이 문맥에서는 메시지 문자열을 만들기 위해서 런타임 API를 사용하는 format!을 사용할 수 없으므로 그 대신에 메시지를 만들어 내기 위해서 내장된 concat!과 stringify! 매크로를 사용 합니다.

macro_rules! rpn {
  // ...

  ([ $result:expr ]) => {
    $result
  };

  ([ $($stack:expr),* ]) => {
    compile_error!(concat!(
      "Could not find final value for the expression, perhaps you missed an operator? Final stack: ",
      stringify!([ $($stack),* ])
    ))
  };

  ($($tokens:tt)*) => {
    rpn!([] $($tokens)*)
  };
}

운동장

error: Could not find final value for the expression, perhaps you missed an operator? Final stack: [ (3 + 7) * 4 , 2 ]
  --> src/main.rs:31:9
   |
31 |         compile_error!(concat!("Could not find final value for the expression, perhaps you missed an operator? Final stack: ", stringify!([$($stack),*])))
   |         ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
...
40 |     println!("{}", rpn!(2 3 7 + 4 *));
   |                    ----------------- in this macro invocation

이제 좀 더 의미 있는 오류 메시지가 되었고 적어도 현재의 평가 상태에 대해 약간의 상세한 정보를 제공 합니다:

하지만 숫자가 없다면 어떻게 될까요?

println!("{}", rpn!(2 3 + *));

운동장

error: expected expression, found `@`
  --> src/main.rs:15:14
   |
15 |         rpn!(@op $stack * $($rest)*)
   |              ^
...
40 |     println!("{}", rpn!(2 3 + *));
   |                    ------------- in this macro invocation

불행히도 이건 큰 도움이 되지는 않습니다:

만약 trace_macros를 사용하려 하는데 이유가 있어 스택을 보여주지 않는다고 해도, 어떻게 되고 있는지는 비교적 명확합니다 - @op는 매칭되는 조건이 매우 구체적입니다(스택에서 최소 두개의 값이 있어야 합니다). 그렇지 않을 경우 @는 더 탐욕적인 $num:tt에 매칭이 되어 스택에 들어 갑니다.

이걸 피하기 위해서는 아직 매칭되지 않은 @op로 시작하는 모든 것에 매칭하는 가지를 하나 더 추가 하고 컴파일 오류를 만들어 냅니다:

macro_rules! rpn {
  (@op [ $b:expr, $a:expr $(, $stack:expr)* ] $op:tt $($rest:tt)*) => {
    rpn!([ $a $op $b $(, $stack)* ] $($rest)*)
  };

  (@op $stack:tt $op:tt $($rest:tt)*) => {
    compile_error!(concat!(
      "Could not apply operator `",
      stringify!($op),
      "` to the current stack: ",
      stringify!($stack)
    ))
  };

  // ...
}

운동장

error: Could not apply operator `*` to the current stack: [ 2 + 3 ]
  --> src/main.rs:9:9
   |
9  |         compile_error!(concat!("Could not apply operator ", stringify!($op), " to current stack: ", stringify!($stack)))
   |         ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
...
46 |     println!("{}", rpn!(2 3 + *));
   |                    ------------- in this macro invocation

다시한번 해 봅시다:

훨씬 낫네요! 이제 우리의 매크로는 컴파일 시간에 어떤 RPN도 평가할 수 있고 대부분의 흔한 실수를 잘 처리할 수 있습니다. 이제 여기까지 하도록 하고 실제 사용 가능하다고 해 두지요. :)

추가할 작은 기능은 더 많지만, 이 데모 튜토리얼의 범위를 넘어서는 것으로 하겠습니다.

이 글이 유용했는지, 또는 알고 싶은 주제가 있다면 트위터로 알려 주세요!

(역주) The Rust Programming Language를 가리키는 말입니다 ↩︎

This is a Korean translation of a existing post by Ingvar Stepanyan, translated by Junho Choi.

Cloudflare 블로그

Rust 로 복잡한 매크로를 작성하기: 역폴란드 표기법

오류 처리

Workers Builds: integrated CI/CD built on the Workers platform

Elephants in tunnels: how Hyperdrive connects to databases inside your VPC networks

Billions and billions (of logs): scaling AI Gateway with the Cloudflare Developer Platform

Durable Objects aren't just durable, they're fast: a 10x speedup for Cloudflare Queues

Rust 로 복잡한 매크로를 작성하기: 역폴란드 표기법​

오류 처리

Workers Builds: integrated CI/CD built on the Workers platform

Elephants in tunnels: how Hyperdrive connects to databases inside your VPC networks

Billions and billions (of logs): scaling AI Gateway with the Cloudflare Developer Platform

Durable Objects aren't just durable, they're fast: a 10x speedup for Cloudflare Queues

Rust 로 복잡한 매크로를 작성하기: 역폴란드 표기법