Meta-Programming in Rust

Metaprogramming in Rust

@dplaindoux@functional.cafe

Self-Promotion

Apacen an Open Source Declarative Type Dependent System Prover in Prolog (Strategy, Proof Tree, Holes etc.).

Immofix Simuréno an Expert System Dedicated to Real-Estate Matchmaking and Negotiation, Integrating Sustainability Criteria.

Kaptngo a Secure Distributed System for Decentralized Executions with Streamlined Communications.

Metaprogramming in Rust

Metaprogramming / Definition

"A computer programming technique in which programs have the ability to treat other programs as their data." (wikipedia)

Homoiconicity / Definition

"A language is homoiconic if a program written in it can be manipulated as data using the language."
(wikipedia)

Metaprogramming approaches

Compilers thanks to Abstract Syntax Tree (AST)
Dynamic via evaluation function e.g. Javascript
Representation manipulation e.g. Lisp, Prolog
Runtime via API e.g. OCaml, Scala, Swift, Rust etc.
Java Annotation Processing (JSR 269)?

Metaprogramming in Rust

Two different approaches

Declarative Macros
Syntax extension with rewriting rules

Procedural Macros
Syntax extension as execution of a function

Macros by Example

Language extension proposition: Comprehension.

Comprehension

Syntactic construction following the form of the mathematical set-builder notation

  P = { (x,y) | x ∈ [1,3], y ∈ [1,x], y ≠ 2 }
  // P = { (1, 1), (2, 1), (3, 1), (3, 3) }

List comprehension generalisation (P. Wadler)
Scala For Comprehension

Scala For Comprehension Example

for

Scala For Comprehension Example


  for a <- 1 to 3

Scala For Comprehension Example


  for a <- 1 to 3
      b <- 1 to a if b != 2

Scala For Comprehension Example


  for a <- 1 to 3
      b <- 1 to a if b != 2
      yield (a,b)

Scala For Comprehension Syntax


  expr ::=
     ...
     | "for" comprehension

Scala For Comprehension Syntax


  expr ::=
     ...
     | "for" comprehension

  comprehension ::=
       ident "<-" expr "yield" expr

Scala For Comprehension Syntax


  expr ::=
     ...
     | "for" comprehension

  comprehension ::=
       ident "<-" expr "yield" expr
     | ident "<-" expr "if" expr "yield" expr

Scala For Comprehension Syntax


  expr ::=
     ...
     | "for" comprehension

  comprehension ::=
       ident "<-" expr "yield" expr
     | ident "<-" expr "if" expr "yield" expr
     | ident "<-" expr "if" expr comprehension

Scala For Comprehension Syntax


  expr ::=
     ...
     | "for" comprehension

  comprehension ::=
       ident "<-" expr "yield" expr
     | ident "<-" expr "if" expr "yield" expr
     | ident "<-" expr "if" expr comprehension
     | ident "<-" expr comprehension

Scala For Comprehension Transpilation


  for a <- 1 to 3
      b <- 1 to a if b != 2
      yield (a,b)

: List[(Int,Int)]

Scala For Comprehension Transpilation


  (1 to 3).???????(a =>
  for b <- 1 to a if b != 2
      yield (a,b))

???????: List[Int] -> (Int -> List[(Int,Int)]) -> List[(Int,Int)]

Scala For Comprehension Transpilation


  (1 to 3).flatMap(a =>
  for b <- 1 to a if b != 2
      yield (a,b))

flatMap: List[A] -> (A -> List[B]) -> List[B]

Scala For Comprehension Transpilation


  (1 to 3).flatMap(a =>
  for b <- (1 to a).??????????(b => b != 2)
      yield (a,b))

??????????: List[Int] -> (Int -> Bool) -> List[Int]

Scala For Comprehension Transpilation


  (1 to 3).flatMap(a =>
  for b <- (1 to a).withFilter(b => b != 2)
      yield (a,b))

withFilter: List[A] -> (A -> Bool) -> List[A]

Scala For Comprehension Transpilation


  (1 to 3).flatMap(a =>
           (1 to a).withFilter(b => b != 2).???(b =>
            (a,b)))

???: List[Int] -> (Int -> (Int,Int)) -> List[(Int,Int)]

Scala For Comprehension Transpilation


  (1 to 3).flatMap(a =>
           (1 to a).withFilter(b => b != 2).map(b =>
            (a,b)))

map: List[A] -> (A -> B) -> List[B]

Scala For Comprehension Transpilation Sketch


  comprehension ::=

Scala For Comprehension Transpilation Sketch


  comprehension ::=
       i:ident "<-" e:expr "yield" r:expr =>
       { e.map(i => r) }

Scala For Comprehension Transpilation Sketch


  comprehension ::=
       i:ident "<-" e:expr "yield" r:expr =>
       { e.map(i => r) }

     | i:ident "<-" e:expr "if" c:expr "yield" r:expr =>
       { e.withFilter(i => c).map(i => r) }

Scala For Comprehension Transpilation Sketch


  comprehension ::=
       i:ident "<-" e:expr "yield" r:expr =>
       { e.map(i => r) }

     | i:ident "<-" e:expr "if" c:expr "yield" r:expr =>
       { e.withFilter(i => c).map(i => r) }

     | i:ident "<-" e:expr "if" c:expr r:comprehension =>
       { e.withFilter(i => c).flatMap(i => r) }

Scala For Comprehension Transpilation Sketch


  comprehension ::=
       i:ident "<-" e:expr "yield" r:expr =>
       { e.map(i => r) }

     | i:ident "<-" e:expr "if" c:expr "yield" r:expr =>
       { e.withFilter(i => c).map(i => r) }

     | i:ident "<-" e:expr "if" c:expr r:comprehension =>
       { e.withFilter(i => c).flatMap(i => r) }

     | i:ident "<-" e:expr c:comprehension =>
       { e.flatMap(i => c) }

For Comprehension
with Declarative Macros

Declarative Macro Anatomy


  #[macro_export]
  macro_rules! macro_name { // Cannot by a keyword



  }

Declarative Macro Anatomy


  #[macro_export]
  macro_rules! macro_name {
    pattern_with_bindings_1 => {{ production_rule_1 }};


  }

Declarative Macro Anatomy


  #[macro_export]
  macro_rules! macro_name {
    pattern_with_bindings_1 => {{ production_rule_1 }};
    pattern_with_bindings_2 => {{ production_rule_2 }};
    ...
  }

Declarative Macro Physiology

Similar resolution to pattern matching
Find first successful pattern and apply production rule

Recursive definitions are allowed

For Comprehension Declarative Macro

macro_rules! for {













}

For Comprehension Declarative Macro

macro_rules! foreach {













}

For Comprehension Declarative Macro

macro_rules! foreach {
     // i:ident "<-" e:expr "yield" r:expr =>
     // { e.map(i => r) }











}

For Comprehension Declarative Macro

macro_rules! foreach {
     ($i:ident <- ($e:expr) yield $r:expr) => {{
     // { e.map(i => r) }
     }}










}

For Comprehension Declarative Macro

macro_rules! foreach {
     ($i:ident <- ($e:expr) yield $r:expr) => {{
        $e.map(move |$i| $r)
     }}












}

For Comprehension Declarative Macro

macro_rules! foreach {
     ($i:ident <- ($e:expr) yield $r:expr) => {{
        $e.map(move |$i| $r)
     }};
     // i:ident "<-" e:expr "if" c:expr "yield" r:expr =>
     // { e.withFilter(i => c).map(i => r) }










}

For Comprehension Declarative Macro

macro_rules! foreach {
     ($i:ident <- ($e:expr) yield $r:expr) => {{
        $e.map(move |$i| $r)
     }};
     ($i:ident <- ($e:expr) if ($c:expr) yield $r:expr) => {{
     // { e.withFilter(i => c).map(i => r) }
     }};










}

For Comprehension Declarative Macro

macro_rules! foreach {
     ($i:ident <- ($e:expr) yield $r:expr) => {{
        $e.map(move |$i| $r)
     }};
     ($i:ident <- ($e:expr) if ($c:expr) yield $r:expr) => {{
        $e.filter(move |&$i| $c).map(move |$i| $r)
     }}










}

For Comprehension Declarative Macro

macro_rules! foreach {
     ($i:ident <- ($e:expr) yield $r:expr) => {{
        $e.map(move |$i| $r)
     }};
     ($i:ident <- ($e:expr) if ($c:expr) yield $r:expr) => {{
        $e.filter(move |&$i| $c).map(move |$i| $r)
     }};
     // i:ident "<-" e:expr "if" c:expr r:comprehension =>
     // { e.withFilter(i => c).flatMap(i => r) }








}

For Comprehension Declarative Macro

macro_rules! foreach {
     ($i:ident <- ($e:expr) yield $r:expr) => {{
        $e.map(move |$i| $r)
     }};
     ($i:ident <- ($e:expr) if ($c:expr) yield $r:expr) => {{
        $e.filter(move |&$i| $c).map(move |$i| $r)
     }};
     ($i:ident <- ($e:expr) if ($c:expr) $($r:tt)+) => {{
     // { e.withFilter(i => c).flatMap(i => r) }

     }}



}

For Comprehension Declarative Macro

macro_rules! foreach {
     ($i:ident <- ($e:expr) yield $r:expr) => {{
        $e.map(move |$i| $r)
     }};
     ($i:ident <- ($e:expr) if ($c:expr) yield $r:expr) => {{
        $e.filter(move |&$i| $c).map(move |$i| $r)
     }};
     ($i:ident <- ($e:expr) if ($c:expr) $($r:tt)+) => {{
        $e.filter(move |&$i| $c)
          .flap_map(move |$i| foreach!($($r)+))
     }}



}

For Comprehension Declarative Macro

macro_rules! foreach {
     ($i:ident <- ($e:expr) yield $r:expr) => {{
        $e.map(move |$i| $r)
     }};
     ($i:ident <- ($e:expr) if ($c:expr) yield $r:expr) => {{
        $e.filter(move |&$i| $c).map(move |$i| $r)
     }};
     ($i:ident <- ($e:expr) if ($c:expr) $($r:tt)+) => {{
        $e.filter(move |&$i| $c)
          .flap_map(move |$i| foreach!($($r)+))
     }};
     // i:ident "<-" e:expr r:comprehension =>
     // { flatMap(i => r) }

}

For Comprehension Declarative Macro

macro_rules! foreach {
     ($i:ident <- ($e:expr) yield $r:expr) => {{
        $e.map(move |$i| $r)
     }};
     ($i:ident <- ($e:expr) if ($c:expr) yield $r:expr) => {{
        $e.filter(move |&$i| $c).map(move |$i| $r)
     }};
     ($i:ident <- ($e:expr) if ($c:expr) $($r:tt)+) => {{
        $e.filter(move |&$i| $c)
          .flap_map(move |$i| foreach!($($r)+))
     }};
     ($i:ident <- ($e:expr) $($r:tt)+) => {{
     // { flatMap(i => r) }
     }}
}

For Comprehension Declarative Macro

macro_rules! foreach {
     ($i:ident <- ($e:expr) yield $r:expr) => {{
        $e.map(move |$i| $r)
     }};
     ($i:ident <- ($e:expr) if ($c:expr) yield $r:expr) => {{
        $e.filter(move |&$i| $c).map(move |$i| $r)
     }};
     ($i:ident <- ($e:expr) if ($c:expr) $($r:tt)+) => {{
        $e.filter(move |&$i| $c)
          .flap_map(move |$i| foreach!($($r)+))
     }};
     ($i:ident <- ($e:expr) $($r:tt)+) => {{
        $e.flat_map(move |$i| foreach!($($r)+))
     }};
}

For Comprehension Applied


  let r : Vec<_> =
    foreach! {
      a <- (1..=3)
      b <- (1..=a) if (b != 2)
      yield (a,b)
    }
    .collect();

For Comprehension Applied


  let r : Vec<_> =

      (1..=3).flat_map(move |a|
        foreach! { b <- (1..=a) if (b != 2)
                 yield (a,b) })

    .collect();

For Comprehension Applied


  let r : Vec<_> =

      (1..=3).flat_map(move |a|
        (1..=a).filter(move |&b| b != 2)
               .map(move |b|(a,b)))

    .collect();

For Comprehension Applied


  let r : Option<i32> =
    foreach! {
      a <- (Some(1))
      b <- (Some(2)) if (b != 2)
      c <- (Some(3))
      yield a + b + c
    };

For Comprehension Applied


              let r: Option<i32> = foreach! {
     ______________________________^
    |             a <- (Some(1))
    |             b <- (Some(2)) if (b != 2)
    |             c <- (Some(3))
    |             yield a + b + c
    |         };
    |_________^ `Option<i32>` is not an iterator

For Comprehension Declarative Macro

macro_rules! foreach {
     ($i:ident <- ($e:expr) yield $r:expr) => {{
        $e.map(move |$i| $r)
     }};
     ($i:ident <- ($e:expr) if ($c:expr) yield $r:expr) => {{
        $e.filter(move |&$i| $c).map(move |$i| $r)
     }};
     ($i:ident <- ($e:expr) if ($c:expr) $($r:tt)+) => {{
        $e.filter(move |&$i| $c)
          .flap_map(move |$i| foreach!($($r)+))
     }};
     ($i:ident <- ($e:expr) $($r:tt)+) => {{
        $e.flat_map(move |$i| foreach!($($r)+))
     }};
}

For Comprehension Declarative Macro

macro_rules! foreach {
     ($i:ident <- ($e:expr) yield $r:expr) => {{
        $e.map(move |$i| $r)
     }};
     ($i:ident <- ($e:expr) if ($c:expr) yield $r:expr) => {{
        $e.filter(move |&$i| $c).map(move |$i| $r)
     }};
     ($i:ident <- ($e:expr) if ($c:expr) $($r:tt)+) => {{
        $e.filter(move |&$i| $c)
          .map(move |$i| foreach!($($r)+)).flatten()
     }};
     ($i:ident <- ($e:expr) $($r:tt)+) => {{
        $e.map(move |$i| foreach!($($r)+)).flatten()
     }};
}

For Comprehension Applied


  let r : Result<i32, ()> =
    foreach! {
      a <- (Ok(1))
      b <- (Ok(2))
      c <- (Ok(3))
      yield a + b + c
    };

Declarative Macros limitations


  ($a:ident <- ($e:expr) yield $result:expr) => {{ ...

Declarative Macros limitations


  ($a:ident <- $e:expr yield $result:expr) => {{ ...

Declarative Macros limitations


  ($a:ident <- $e:expr yield $result:expr) => {{ ...
                       ^^^^^ not allowed after `expr` fragments

Declarative Macros limitations


  ($a:ident <- $e:expr yield $result:expr) => {{ ...
                       ^^^^^ not allowed after `expr` fragments

Pattern limitation
Direct transformation without manipulation

For Comprehension
with Procedural Macros

Procedural Macro Anatomy


  #[proc_macro]
  pub fn foreach(input: TokenStream) -> TokenStream {
      ...
  }

Procedural Macro Physiology

Syn library
For parsing a stream of tokens into a syntax tree

Quote macro
For turning syntax tree into a stream of tokens

For Comprehension Procedural Macro Recipe

Design the Abstract Syntax Tree aka AST ADT
syn::parse::Parse implementation for this Syntax Tree
quote::ToTokens implementation for this Syntax Tree

TokenStream -{Parse}-> AST -{ToTokens}-> TokenStream

For Comprehension Syntax


  expr ::=
     ...
     | "for" comprehension

  comprehension ::=
       ident "<-" expr "yield" expr
     | ident "<-" expr "if" expr "yield" expr
     | ident "<-" expr "if" expr comprehension
     | ident "<-" expr comprehension

For Comprehension Syntax


  expr ::=
     ...
     | "for" comprehension

  comprehension ::=
       ident "<-" expr ("if" expr)? "yield" expr

     | ident "<-" expr ("if" expr)? comprehension

For Comprehension Syntax


  expr ::=
     ...
     | "for" comprehension

  comprehension ::=
     ident "<-" expr ("if" expr)? ("yield" expr | comprehension)

For Comprehension Syntax Tree


pub enum Comprehension {
    // ident <- value (if condition)? yield result
    MappingAndYield {
        ident: syn::Ident,
        value: syn::Expr,
        condition: Option<syn::Expr>,
        result: syn::Expr,
    },
    // ident <- value (if condition)? comprehension
    ...
}

For Comprehension Syntax Tree


pub enum Comprehension {
    // ident <- value (if condition)? yield result
    ...,
    // ident <- value (if condition)? comprehension
    ChainedMapping {
        ident: syn::Ident,
        value: syn::Expr,
        condition: Option<syn::Expr>,
        comprehension: Box<Comprehension>,
    },
}

For Comprehension Parser


  impl syn::parse::Parse for Comprehension {

    //
    fn parse(input: ParseStream) -> syn::Result<Self> {




      ...
    }
  }

For Comprehension Parser


  impl syn::parse::Parse for Comprehension {

    // ident ...
    fn parse(input: ParseStream) -> syn::Result<Self> {
      let ident = input.parse::<syn::Ident>()?;



      ...
    }
  }

For Comprehension Parser


  impl syn::parse::Parse for Comprehension {

    // ident "<-" ...
    fn parse(input: ParseStream) -> syn::Result<Self> {
      let ident = input.parse::<syn::Ident>()?;
      let _ = input.parse::<syn::Token![<-]>()?;


      ...
    }
  }

For Comprehension Parser


  impl syn::parse::Parse for Comprehension {

    // ident "<-" expr ...
    fn parse(input: ParseStream) -> syn::Result<Self> {
      let ident = input.parse::<syn::Ident>()?;
      let _ = input.parse::<syn::Token![<-]>()?;
      let value = input.parse::<syn::Expr>()?;

      ...
    }
  }

For Comprehension Parser


  impl syn::parse::Parse for Comprehension {

    // ident "<-" expr ("if" ...)? ...
    fn parse(input: ParseStream) -> syn::Result<Self> {
      let ident = input.parse::<syn::Ident>()?;
      let _ = input.parse::<syn::Token![<-]>()?;
      let value = input.parse::<syn::Expr>()?;
      let cond = if input.lookahead1().peek(syn::Token![if]) ...
      ...
    }
  }

For Comprehension ToTokens


  impl quote::ToTokens for Comprehension {
    fn to_tokens(&self, tokens: &mut TokenStream) {
      tokens.extend(self.to_token_stream())
    }

    fn to_token_stream(&self) -> TokenStream {
      match self {
        Comprehension::MappingAndYield {
          ident, value, condition, result,
        } => {
          if condition.is_none() {
            quote! { #value.map(move |#ident| #result) }
          } else {
            ...

For Comprehension Procedural Macro


  #[proc_macro]
  pub fn foreach(input: TokenStream) -> TokenStream {


  }

For Comprehension Procedural Macro


  #[proc_macro]
  pub fn foreach(input: TokenStream) -> TokenStream {
    let c = parse_macro_input!(input as Comprehension);

  }

For Comprehension Procedural Macro


  #[proc_macro]
  pub fn foreach(input: TokenStream) -> TokenStream {
    let c = parse_macro_input!(input as Comprehension);
    quote! { #c }.into()
  }

For Comprehension Applied


  let r : Result<i32, ()> =
    foreach! {
      a <- Ok(1)
      b <- Ok(2) if a != 1
      c <- Ok(3)
      yield a + b + c
    };

Experiment
the Celma Project

Celma

Library for generalised parser combinators with a dedicated meta-language in Rust

A JSON Parser in Celma


  parsec_rules! {
    let json    = (string|null|boolean|array|object|number)
    let number  = NUMBER                              -> {}
    let string  = STRING                              -> {}
    let null    = "null"                              -> {}
    let boolean = ("true"|"false")                    -> {}
    let array   = ('[' (_=json (',' _=json)*)? ']')   -> {}
    let object  = ('{' (_=attr (',' _=attr)*)? '}')   -> {}
    let attr    = (STRING ":" json)                   -> {}
  };

Regressio ad infinitum

Bootstrap

A Celma Parser in Celma


  parsec_rules! {
    ...

    let rule:{ASTParsecRule<char>} =



    ...
  };

A Celma Parser in Celma


  parsec_rules! {
    ...

    let rule:{ASTParsecRule<char>} =
      "let" n=ident i=kind? o=(':' _=kind)? '=' b=parsec
      -> { mk_rule(n, i, o, b) }

    ...
  };

Celma in Celma Perspective

Capability to manipulate parser at compile time!

Generation of "Classical" Parser Combinator
Generation of Optimised Parser from the AST

flap: A Deterministic Parser with Fused Lexing
Jeremy Yallop, Ningning Xie and Neel Krishnaswami

Conclusion

Two approaches declarative or procedural
Capability to embed rich DSL in Rust

Rust References

Syn Crate Parser for Rust source code
Quote Crate Rust Quasi-Quoting
Compile Time Reflection in Rust (Thesis)
And more ...

Additional References

Comprehending Monads
Philip Wadler

Theory and Practice of Unparsed Patterns for Metacompilation
Christian Rinderknecht and Nic Volanschi

Metacompilation in Rust

Metaprogramming in Rust

Self-Promotion

Metaprogramming in Rust

Metaprogramming / Definition

Homoiconicity / Definition

Metaprogramming approaches

Metaprogramming in Rust

Two different approaches

Macros by Example

Comprehension

Scala For Comprehension Example

Scala For Comprehension Example

Scala For Comprehension Example

Scala For Comprehension Example

Scala For Comprehension Example

Scala For Comprehension Syntax

Scala For Comprehension Syntax

Scala For Comprehension Syntax

Scala For Comprehension Syntax

Scala For Comprehension Syntax

Scala For Comprehension Transpilation

Scala For Comprehension Transpilation

Scala For Comprehension Transpilation

Scala For Comprehension Transpilation

Scala For Comprehension Transpilation

Scala For Comprehension Transpilation

Scala For Comprehension Transpilation

Scala For Comprehension Transpilation Sketch

Scala For Comprehension Transpilation Sketch

Scala For Comprehension Transpilation Sketch

Scala For Comprehension Transpilation Sketch

Scala For Comprehension Transpilation Sketch

For Comprehension with Declarative Macros

Declarative Macro Anatomy

Declarative Macro Anatomy

Declarative Macro Anatomy

Declarative Macro Anatomy

Declarative Macro Physiology

For Comprehension Declarative Macro

For Comprehension Declarative Macro

For Comprehension Declarative Macro

For Comprehension Declarative Macro

For Comprehension Declarative Macro

For Comprehension Declarative Macro

For Comprehension Declarative Macro

For Comprehension Declarative Macro

For Comprehension Declarative Macro

For Comprehension Declarative Macro

For Comprehension Declarative Macro

For Comprehension Declarative Macro

For Comprehension Declarative Macro

For Comprehension Declarative Macro

For Comprehension Applied

For Comprehension Applied

For Comprehension Applied

For Comprehension Applied

For Comprehension Applied

For Comprehension Declarative Macro

For Comprehension Declarative Macro

For Comprehension Applied

Declarative Macros limitations

Declarative Macros limitations

Declarative Macros limitations

Declarative Macros limitations

For Comprehension with Procedural Macros

Procedural Macro Anatomy

Procedural Macro Physiology

For Comprehension Procedural Macro Recipe

For Comprehension Syntax

For Comprehension Syntax

For Comprehension Syntax

For Comprehension Syntax Tree

For Comprehension Syntax Tree

For Comprehension Parser

For Comprehension Parser

For Comprehension Parser

For Comprehension Parser

For Comprehension Parser

For Comprehension ToTokens

For Comprehension Procedural Macro

For Comprehension
with Declarative Macros

For Comprehension
with Procedural Macros

Experiment
the Celma Project