Creación de macros complejas en Rust: notación polaca inversa

(Esta es una publicación cruzada de un tutorial publicado originalmente en mi blog personal )

Entre otras características interesantes, Rust tiene un sólido sistema macro. Lamentablemente, incluso después de leer el libro y varios tutoriales, cuando trataba de implementar una macro, que implicaba el procesamiento de listas complejas de diferentes elementos, seguía teniendo problemas para entender cómo se hacía, y me llevó un tiempo hasta que me dí cuenta y comencé a usar macros indiscriminadamente para todo :) (de acuerdo, no para todo, como si dijera uso macros porque no quiero usar funciones y especificar tipos y duraciones como he visto que hacen algunos, pero en realidad es útil)

CC BY 2.0 Imagen de Conor Lawless

Por lo tanto, esta es mi opinión sobre la descripción de los principios de creación de estas macros. Se supone que ha leído la sección Macros del libro y que está familiarizado con las definiciones básicas de macros y con los tipos de token.

Tomaré la notación polaca inversa como ejemplo para este tutorial. Es interesante porque es bastante simple, es posible que el tema le resulte familiar, ya que seguramente lo vio en la escuela o la universidad y, sin embargo, para implementarla de manera estática en el momento de la compilación, usted debe usar un método recursivo de macros.

La notación polaca inversa (también denominada notación posfija) utiliza una pila para todas sus operaciones, por lo tanto, cualquier operando se inserta en la pila, y cualquier operador [binario] toma dos operandos de la pila, evalúa el resultado y lo vuelve a colocar en su lugar. Por lo tanto, la expresión a continuación:

2 3 + 4 *

2 3 + 4 *

se traduce en lo siguiente:

1. Poner 2 en la pila.

2. Poner 3 en la pila.

3. Tomar los dos últimos valores de la pila ( 3 y 2), aplicar el operador + y volver a colocar el resultado ( 5) en la pila.

4. Poner 4 en la pila.

5. Tomar los dos últimos valores de la pila ( 4 y 5), aplicar el operador * ( 4 * 5) y volver a colocar el resultado ( 20) en la pila.

6. Fin de la expresión, el valor único de la pila es el resultado ( 20).

En una notación infija más común, que se utiliza en matemáticas y en la mayoría de los lenguajes de programación modernos, la expresión sería (2 + 3) * 4.

macro_rules! rpn {
  // TODO
}

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

Así que vamos a crear una macro que evaluaría la notación polaca inversa (RPN) en el momento de la compilación convirtiéndola en una notación infija que Rust comprenda.

Comencemos por hacer avanzar números a la pila.

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

Las macros actualmente no permiten literales coincidentes, y expr no funcionará para nosotros ya que puede hacer coincidir accidentalmente una secuencia como 2 + 3 ... en lugar de tomar un solo número, por lo tanto, recurriremos a tt - un buscador de coincidencias de token genérico que coincida con un solo árbol de token (independientemente de si se trata de un token primitivo como literal/identificador/duración/etc. o ()/ []/ {} - expresión entre paréntesis que contiene más tokens):

Ahora, necesitaremos una variable para la pila.

Las macros no pueden usar variables reales, ya que queremos que esta pila solo exista en el momento de la compilación. Por lo tanto, el truco consiste en tener una secuencia de token separada que se pueda hacer circular y usar como una especie de acumulador.

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

En nuestro caso, la representaremos como una secuencia separada por comas de expr (ya que la usaremos no solo para números simples sino también para expresiones infijas intermedias) y la encerraremos entre corchetes para separarla del resto de la entrada:

Ahora, una secuencia de token no es en realidad una variable - no se puede modificar in situ y hacer algo con esta después. Pero usted puede crear una copia nueva de esta secuencia de token con las modificaciones necesarias y volver a designar de manera recursiva la misma macro.

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

Si usted proviene de un entorno de lenguaje funcional o ha trabajado antes con una biblioteca que proporciona datos inmutables, es probable que ambos métodos - mutación de datos mediante la creación de una copia modificada y procesamiento de listas con recursividad - le resulten familiares.

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

Ahora, obviamente, el caso con un número simple es bastante improbable y no resulta muy interesante para nosotros, por lo tanto, tendremos que hacer coincidir todo lo demás después de ese número como una secuencia de cero o más tokens tt, que se puede pasar a la siguiente invocación de nuestra macro para una coincidencia y procesamiento posteriores:

En este punto aún nos falta el soporte del operador. ¿Cómo hacemos coincidir a los operadores?

Si nuestra RPN fuera una secuencia de tokens que quisiéramos procesar exactamente de la misma manera, simplemente podríamos usar una lista como $($token:tt)*. Lamentablemente, eso no nos permitiría revisar la lista y hacer avanzar un operando o aplicar un operador según cada token.

El libro dice que “el sistema macro no se ocupa de analizar la ambigüedad”, y eso es cierto para una sola bifurcación de macros - no podemos hacer coincidir una secuencia de números seguidos por un operador como $($num:tt)* +  porque + también es un token válido y podría hacerse coincidir por el grupo tt, pero aquí es donde las macros recursivas vuelven a ayudar.

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)*)
  };
}

Si tiene diferentes bifurcaciones en su definición de macro, Rust las probará una por una, para que podamos poner nuestras bifurcaciones para el operador antes del número uno y, de esta manera, evitar cualquier tipo de conflicto:

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)*)
  };
}

Como dije antes, los operadores se aplican a los dos últimos números de la pila, por lo tanto, tendremos que lograr una coincidencia por separado, “evaluar” el resultado (construir una expresión infija regular) y volver a colocarlo:

En realidad no me gustan mucho esas repeticiones tan obvias, pero, al igual que con los literales, no hay ningún tipo de token especial que coincida con los operadores.

Lo que podemos hacer, sin embargo, es agregar un auxiliar que sería responsable de la evaluación y delegar cualquier bifurcación para el operador explícita a este.

En las macros, no se puede utilizar un auxiliar externo, pero de lo único que puede estar seguro es que sus macros ya están en escala, por lo tanto, el truco habitual es tener una bifurcación en la misma macro “marcada” con alguna secuencia de token única, y designarla de manera recursiva como lo hicimos con las bifurcaciones regulares.

Usaremos @op como marcador, y aceptaremos cualquier operador a través de tt dentro de este ( tt sería inequívoco en ese contexto, ya que solo pasaremos operadores a este auxiliar).

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)*)
  };
}

Y la pila ya no necesita expandirse en cada bifurcación separada, ya que la encerramos entre [] corchetes anteriormente, se puede hacer coincidir como cualquier otro árbol de tokens (tt), y luego pasar a nuestro auxiliar:

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

Ahora las bifurcaciones correspondientes procesan los tokens, y nosotros debemos manejar el proceso final cuando la pila contenga un solo elemento, y ya no quedan más tokens:

En este punto, si usted invoca esta macro con una pila vacía y una expresión RPN, ya arrojará un resultado correcto:

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

Sitio de prueba

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

macro_rules! rpn {
  // ...

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

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

Sin embargo, nuestra pila es un detalle de la implementación y realmente no quisiéramos que cada usuario pase una pila vacía, por lo tanto, agregaremos otra bifurcación de captura general al final que serviría como punto de entrada y agregaría [] de manera automática:

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

Sitio de prueba

Nuestra macro incluso funciona para expresiones más complejas, ¡como la de la página de Wikipedia sobre RPN!

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

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`

Ahora todo parece funcionar sin inconvenientes para las expresiones RPN correctas, pero para que una macro esté lista para funcionar, debemos estar seguros de que también pueda gestionar las entradas no válidas, con un mensaje de error razonable.

En primer lugar, intentaremos insertar otro número en el medio y ver qué sucede:

Resultado:

#![feature(trace_macros)]

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

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

De acuerdo, eso indudablemente no parece útil, ya que no brinda ninguna información relevante con respecto al error real en la expresión.

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]`

Para averiguar qué sucedió, deberemos depurar nuestras macros. Para ello, utilizaremos una característica trace_macros (y, como para cualquier otra característica del compilador opcional, necesitará una versión nocturna de Rust). No queremos rastrear la designación println!, por lo tanto, separaremos nuestro cálculo de RPN a una variable:

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

Sitio de prueba

En el resultado, ahora veremos cómo nuestra macro se está evaluando de manera recursiva, paso a paso:

Si analizamos detenidamente el seguimiento, advertiremos que el problema se origina en estos pasos:

Puesto que a [ 3 + 7 * 4 , 2 ] la bifurcación ([$result:expr]) => ... no lo hizo coincidir como expresión final, nuestra bifurcación ($($tokens:tt)*) => ... de captura general final antepuso una pila vacía con [] y luego al original [ 3 + 7 * 4 , 2 ] el genérico $num:tt lo hizo coincidir y se empujó hacia la pila como único valor final.

Para evitar que esto suceda, insertaremos otra bifurcación entre estas dos últimas que coincidirían con cualquier pila.

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)*)
  };
}

Solo se afectaría cuando nos quedamos sin tokens, pero la pila no tenía exactamente un valor final, por lo tanto, podemos tratarlo como un error de compilación y producir un mensaje de error más útil usando una macro incorporada compile_error!.

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

Tenga en cuenta que no podemos usar format! en este contexto, ya que este utiliza API en tiempo de ejecución para dar formato a una cadena, y tendremos que limitarnos a las macros incorporadas concat! y stringify! para dar formato a un mensaje:

Sitio de prueba

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

El mensaje de error ahora resulta más comprensible y contiene al menos algunos detalles sobre el estado actual de la evaluación:

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

Pero, ¿qué pasaría si perdemos algún número?

Sitio de prueba

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

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)
    ))
  };

  // ...
}

Lamentablemente, esto todavía no es muy útil:

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

Si trata de usar trace_macros, tampoco va a ampliar la pila aquí por alguna razón, pero, afortunadamente, lo que sucede es relativamente claro - @op tiene condiciones muy específicas en cuanto a lo que se debe hacer coincidir (se esperan al menos dos valores en la pila) y, cuando no se puede, a @, $num:tt la hace coincidir y la empuja a la pila.

Para evitar esto, de nuevo, agregaremos otra bifurcación para que coincida con todo lo que comience con @op que aún no se ha hecho coincidir, y que genera un error de compilación:

Sitio de prueba

Intentémoslo nuevamente:

¡Mucho mejor! Ahora, nuestra macro puede evaluar cualquier expresión de RPN durante la compilación y controla correctamente los errores más comunes, así que nos detendremos aquí y consideremos que está lista para funcionar:)

Podríamos agregar muchas mejoras más pequeñas, pero me gustaría dejarlas afuera de este tutorial de demostración.

No dude en comentarme si esto le ha resultado útil y/o qué temas le gustaría que incluyamos en Twitter.