Dispatch Dinámico en Rust y Monomorfización

#rust Posteado: 23 May 2024 8 minutos

Hay una gran diferencia entre usar genéricos y recibir un trait sin especificar implementación. En el primer caso el compilador monomorfiza, en el segundo se produce dispatch dinámico en tiempo de ejecución.

Introducción

Todo esto ha surgido a raíz de traducir a rust¹ el capítulo 5 del Crafting Interpreters.

Ejemplo en Scala

En rust tenemos dos formas de llamar/usar implementaciones de una clase abstracta o interfaz. En scala podríamos hacer algo parecido a esto²:

trait Expr[T]:
    def accept(visitor: Visitor[T]): T

trait Visitor[T]:
    def visit(expr: Unary[T]): T
    def visit(expr: Binary[T]): T

case class Binary[T](l: Expr[T], op: String, r: Expr[T]) extends Expr[T]:
    def accept(visitor: Visitor[T]): T =
      visitor.visit(this)

case class Unary[T](op: String, r: Expr[T]) extends Expr[T]:
    def accept(visitor: Visitor[T]): T =
      visitor.visit(this)

case class LiteralExpr[T](value: T) extends Expr[T]:
    def accept(visitor: Visitor[T]): T = value

class AstPrinter extends Visitor[String]:
    def visit(expr: Unary[String]): String =
      s"${expr.op} ${expr.r.accept(this)}"

    def visit(expr: Binary[String]): String =
      s"${expr.op} ${expr.l.accept(this)} ${expr.r.accept(this)}"

val expression = Unary("-", Binary(LiteralExpr("1"), "+", LiteralExpr("2")))
val printer = AstPrinter()
val result = expression.accept(printer)

En este ejemplo tenemos dos cosas distintas. La sobrecarga de AstPrinter permite en tiempo de compilación saber a qué método llamar según reciba un Unary o un Binary. Si tenemos que llamar a un método de un Expr[Int] o de un Expr[String] también se decide en tiempo de compilación.

Type Erasure

Java

En Java se produce el borrado de los genéricos al compilar. Todas las ocurrencias del tipo genérico se sustituye o por el tipo límite superior que se haya definido o, si no se ha definido, por Object. Al final solo sirve como mecanismo de seguridad al programar.

TODO Scala

En Scala pasa algo similar, pero sí retiene más información. Recuero haber leído bastante sobre esto (type erasure) en el contexto de los summon types, pero no me acuerdo prácticamente de nada. REVISAR.

Sobreescritura

En caso de usar herencia, qué método se llama, si el del padre o el del hijo, sí se decide en tiempo de ejecución. Si hacemos algo como:

val expression: Expr[String] = Unary(...)

Si Expr fuese una clase abstracta que implementase el método accept en vez de un trait, sí que se decidiría en tiempo de ejecución qué se ejecutaría, si el accept de Unary, que es el tipo real, o el de Expr al haber definido val expression: Expr[String]. Se ejecutaría aquél (Unary).

Dispatch Dinámico en Rust

Lo explicado en el capítulo que comentaba del Crafting Interpreters lo he traducido en primera instancia en Rust como sigue:

    trait Expr<T> {
      fn accept(&self, visitor: &dyn Visitor<T>) -> T;
  }

  trait Visitor<T> {
      fn visit_binary_expr(&self, expr: &Binary<T>) -> T;
      fn visit_grouping_expr(&self, expr: &Grouping<T>) -> T;
      fn visit_literal_expr(&self, expr: &LiteralExpr) -> T;
      fn visit_unary_expr(&self, expr: &Unary<T>) -> T;
  }

  struct Binary<'a, T> {
      pub left: Box<dyn Expr<T>>,
      pub operator: Token<'a>,
      pub right: Box<dyn Expr<T>>,
  }

  impl<'a, T> Expr<T> for Binary<'a, T> {
      fn accept(&self, visitor: &dyn Visitor<T>) -> T {
          visitor.visit_binary_expr(self)
      }
  }

  struct Grouping<T> {
      pub expression: Box<dyn Expr<T>>,
  }

  impl<'a, T> Expr<T> for Grouping<T> {
      fn accept(&self, visitor: &dyn Visitor<T>) -> T {
          visitor.visit_grouping_expr(self)
      }
  }

  struct LiteralExpr {
      pub value: Literal<'static>,
  }

  impl<'a, T> Expr<T> for LiteralExpr {
      fn accept(&self, visitor: &dyn Visitor<T>) -> T {
          visitor.visit_literal_expr(self)
      }
  }

  struct Unary<'a, T> {
      pub operator: Token<'a>,
      pub right: Box<dyn Expr<T>>,
  }

  impl<'a, T> Expr<T> for Unary<'a, T> {
      fn accept(&self, visitor: &dyn Visitor<T>) -> T {
          visitor.visit_unary_expr(self)
      }
  }

  struct AstPrinter;

  impl Visitor<String> for AstPrinter {
      fn visit_binary_expr(&self, expr: &Binary<String>) -> String {
          format!(
              "({} {} {})",
              expr.operator.lexeme,
              expr.left.accept(self),
              expr.right.accept(self)
          )
      }

      fn visit_grouping_expr(&self, expr: &Grouping<String>) -> String {
          format!("(group {})", expr.expression.accept(self))
      }

      fn visit_literal_expr(&self, expr: &LiteralExpr) -> String {
          match &expr.value {
              Literal::Number(n) => format!("{}", n),
              Literal::String(s) => format!("\"{}\"", s),
          }
      }

      fn visit_unary_expr(&self, expr: &Unary<String>) -> String {
          format!("({} {})", expr.operator.lexeme, expr.right.accept(self))
      }
  }

  #[test]
fn test_generate_ast() {
    let expression = Binary {
        left: Box::new(Unary::<String> {
            operator: Token {
                _type: TokenType::Minus,
                lexeme: "-",
                literal: None,
                line: 1,
            },
            right: Box::new(LiteralExpr {
                value: Literal::Number(123.0),
            }),
        }),
        operator: Token {
            _type: TokenType::Star,
            lexeme: "*",
            literal: None,
            line: 1,
        },
        right: Box::new(Grouping {
            expression: Box::new(LiteralExpr {
                value: Literal::Number(45.67),
            }),
        }),
    };

    let printer = AstPrinter;
    println!("{}", expression.accept(&printer));

    assert!(false);
}

Lo importante aquí es el uso de Box y dyn. No me atrevía a gastarlo mucho porque no los tenía muy claros, creo que ahora he entendido algo mejor para qué sirven. Gracias a ellos, como resumen, podemos replicar el pasar objetos no concretos que implementen ciertos trait a otras funciones/métodos.

`&dyn Trait` y `Box<dyn Trait>`

En rust, tanto &dyn Trait como Box<dyn Trait> sirven para trabajar, como decía anteriormente, con objetos que implementan un trait. La forma en que manejan la memoria puede ser (no siempre) completamente distinta.

`&dyn Trait`

Simplemente es una referencia como podemos observar por el & a un objeto. Qué tipo de objeto no está claro. Lo único que sabemos es que tiene que implementar un trait específico, en este caso lo he llamado Trait.

Como es una referencia, la propiedad del objeto no pasa al cliente, sino que la mantiene quién creó el objeto. Por lo tanto el objeto no se mueve (obvio). Y, también obviamente, al ser una referencia también, su tamaño en memoria es fijo: el tamaño de un puntero.

Su vida útil está ligada a la vida útil del objeto al que la referencia apunta. Este objeto puede estar en el stack o en el heap. No lo podemos saber, lo único que sabemos es que el puntero mismo está en el stack.

trait Trait { fn method(&self); }

struct MyStruct;

impl Trait for MyStruct {
    fn method(&self) { println!("method called for MyStruct"); }
}

fn use_trait(instance: &dyn Trait) { instance.method(); }

let my_struct = MyStruct {};
use_trait(&my_struct);

`Box<dyn Trait>`

En cambio, cuando tenemos un Box, sabemos a ciencia cierta que el puntero, que está él sí en el stack, apunta a una dirección de memoria dinámica (en el heap).

Box tiene la propiedad, por lo quien tenga la propiedad de Box, que sí puede pasarse/moverse, tiene la propiedad del objeto al que apunta. Y hasta que el Box no se deshecha (se hace el Drop), no se libera la memoria del objeto contenido. Por lo tanto tenemos mucha más libertad con su tiempo de vida, puesto que al poder moverlo podemos mantener el Box entre distinto clientes y hasta que el último no lo deseche podemos seguir usándolo.

Su tamaño también es fijo (el tamaño del puntero).

trait Trait { fn method(&self); }

struct MyStruct;

impl Trait for MyStruct {
    fn method(&self) { println!("method called for MyStruct"); }
}

fn use_box_trait(instance: Box<dyn Trait>) { instance.method(); }

let my_struct = MyStruct {};
use_box_trait(Box::new(my_struct));

Uso común

Por lo tanto, podemos tener un elemento que se haya creado como Box y pasarlo a una función que espera un &dyn Trait.


trait Trait {
    fn method(&self);
}

struct MyStruct;

impl Trait for MyStruct {
    fn method(&self) {
        println!("method called for MyStruct");
    }
}

fn use_trait(instance: &dyn Trait) {
    instance.method();
}

use_trait(&*Box::new(MyStruct {}));

Pero para ello hemos primero de desreferenciar el Box con *, y luego pasar la referencia del elemento que contiene con &.

Dispatch

En ambos casos el dispatch es dinámico. Rust utiliza una tabla de métodos virtuales (vtable³) para determinar qué método llamar en tiempo de ejecución, similar a cómo vimos qué ocurre en Java con el polimorfismo (creo que también en C++):

cuando llamamos a un método a través de una referencia de tipo &dyn Trait o Box<dyn Trait>, Rust consulta la vtable para encontrar qué implementación correcta del método debe usar
en cuanto al rendimiento, el dispatch dinámico introduce una pequeña penalización frente al estático: implica una indirección adicional en tiempo de ejecución.

Si comparamos fríamente con la JVM, aquí Rust tiene una ligera desventaja, puesto que aquélla sí es capaz en tiempo de compilación de saber qué ha de llamar. Cuando recibimos un Visitor[T] sí sabemos tras compilar qué ha de ejecutarse, mientras rust no lo sabe. En este caso no es comparable con el polimorfismo. Por resumir, todo nuestro código de ejemplo de Scala tiene dispatch estático, pero en cambio cada vez que tenemos un dyn en nuestro código más o menos equivalente de Rust tenemos dispatch dinámico⁴.

Monomorfización

Cuando usamos genéricos, Rust realiza una monomorfización: el compilador generará tantas versiones especializadas del código como tantos tipos concretos implementen el trait. Es similar a lo que ocurre con las template de C++.

Nuestro ejemplo de Expr y Visitor es complicado de modificar para usarlos, pero podemos poner un ejemplo sencillo para que se entienda mejor.

trait Trait {
    fn method(&self);
}

struct MyStruct;

impl Trait for MyStruct {
    fn method(&self) {
        println!("MyStruct method called");
    }
}

struct MyStruct2;

impl Trait for MyStruct2 {
    fn method(&self) {
        println!("MyStruct2 method called");
    }
}

fn use_trait<T: Trait>(instance: &T) {
    instance.method();
}

fn main() {
    let my_struct = MyStruct;
    let my_struct2 = MyStruct2;

    use_trait(&my_struct);
    use_trait(&my_struct2);
}

Cuando el compilador encuentra la función genérica use_trait, crea dos versiones: una para MyStruct y otra para MyStruct2. Cada vez que llamo a use_trait se convierte en una llamada directa al método correspondiente, sin necesidad de dispatch dinámico.

Podemos pensar que, de forma muy simplificada, se genera algo como

fn use_trait_mystruct(instance: &MyStruct) {
    instance.method();
}

fn use_trait_mystruct2(instance: &MyStruct2) {
    instance.method();
}

fn main() {
    let my_struct = MyStruct;
    let my_struct2 = MyStruct2;

    use_trait_mystruct(&my_struct);
    use_trait_mystruct2(&my_struct2);
}

De forma más o menos acertada, hay muchas implementaciones en github. ↩︎
Esta implementación podría hacerse con pattern matching, también se comenta en el libro. Intento seguir la forma en que se hace allí para poder forzarme a hacer cosas con rust que no me saldrían a hacer de natural y así practicar/aprender mejor ciertos aspectos del lenguaje que no controlo tanto. Tal como ha sido en este caso. ↩︎
Una vtable es una estructura que contiene punteros a las implementaciones concretas de los métodos del trait. ↩︎
Insisto que actualmente (mayo 2024) tengo poca idea de Rust, y espero que esto no sea una burrada. Tampoco creo que llegue nunca a ser un experto. ↩︎