Writing Complex Macros in Rust: Reverse Polish Notation

https://blog.cloudflare.com/writing-complex-macros-in-rust-reverse-polish-notation/

by jgrahamc • 8 years ago

99 77 8 years ago

blog.cloudflare.com

cheez• 8 years ago

It looks like Rust doesn't have your dad's Lisp macros and more like C-style macros on steroids. Disclaimer: I haven't read The Book.

navaati2• 8 years ago

Well C macros work at the text-level, Rust macros run at the AST level (but not the type level, that is you cannot construct syntactically incorrect stuff but you can construct wrong-typed stuff).

So I don't really know lisp macros but I guess it's still closer than to C.

foldr2• 8 years ago

Rust macros actually work more at the token level than at the AST level.

kibwen3• 8 years ago

Rust macros are Scheme macros, there's no similarity to C.

ChrisSD• 8 years ago

I don't think "C-style macros on steroids" is at all a good description. Rust's macros and C's really aren't that similar.

If you want a short introduction to what Rust's macros actually are then try this: https://danielkeep.github.io/practical-intro-to-macros.html#...

fleetfox• 8 years ago

Would Lisp macros make sense in language that is not homoiconic?

maxiepoo• 8 years ago

Yes: http://calculist.org/blog/2012/04/17/homoiconicity-isnt-the-...

kazinator7• 8 years ago

Many Lisp dialects are not homoiconic, as defined in the Wikipedia page for "homoiconic".

Homoiconic means that procedures are stored in representation in which they are written, or more or less.

A Lisp that compiles everything entered at the REPL isn't homoiconic. The input looks like (lambda (...) ...), but the storage is some block of x86 machine code with an environment vector.

POSIX shells are homoiconic. When you type set, you see your functions, in source code form (modulo reformatting).

The thing you want for metaprogramming is a smart internal representation of program text (not same as the external one).

shmolyneaux• 8 years ago

There is a common set packages [0][1][2] that provide macros that are more similar to lisp-style macros (when operating on structs). [2] in particular implements quasi-quoting in rust.

[0] https://doc.rust-lang.org/proc_macro/index.html [1]: https://github.com/dtolnay/syn [2]: https://github.com/dtolnay/quote

wtetzner2• 8 years ago

They're actually closer to syntax-rules in Scheme.

pleasecalllater• 8 years ago

So it looks like people repeat how C++ templates are bad, and Rust macros are good. Can someone tell me what's the real difference? I'm not sure I get it, but I feel like both are good or both are bad.

jackninja1• 8 years ago

Those are like different concepts. While Rust macros work on the AST and take AST nodes as arguments C++ templates are a whole meta language that also allows for code execution. I would say that Rust macros mainly do code generation while C++ templates also allow for computation.

steveklabnik7• 8 years ago

C++ templates are used for two different features in Rust: generics, and a more broad "metaprogramming."

The other threads talk a bit about general metaprogramming, so let's talk about the other bit. On the generics side, here's an illustrative example, taken from http://en.cppreference.com/w/cpp/language/function_template

  #include <iostream>
   
  template<typename T>
  void f(T s)
  {
      std::cout << s << '\n';
  }
   
  int main()
  {
      f(7);
  }

Here, the function f will take any type T, and print it out. in this case, 7 is an int, so T is int.

In Rust, here's the same function:

  fn f<T>(s: T) {
      println!("{}", s);
  }

  fn main() {
      f(7);
  }

here, 7 is an i32, so T is i32. But, we get a compilation error in Rust:

  error[E0277]: the trait bound `T: std::fmt::Display` is not satisfied
   --> src/main.rs:2:22
    |
  2 |       println!("{}", s);
    |                      ^ `T` 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 `T`
    = help: consider adding a `where T: std::fmt::Display` bound
    = note: required by `std::fmt::Display::fmt`

  error: aborting due to previous error

This illuminates a core difference between Rust's generics and C++'s templates: in the C++ case, the code is typechecked after the code is expanded. So it works. However, we don't even need that `main` to cause a compilation error in Rust; it only checks the body of the function. In this case, Rust says "Hey, you accept any T, but you try to print it out. What if a type isn't printable? That wouldn't work!"

The fix is:

  use std::fmt::Display;

  fn f<T: Display>(s: T)

  // or in near-future Rust, a slightly nicer syntax, still needs the 'use' line too:

  fn f(s: impl Display)

This changes the signature to say "we take any type T that implements the Display trait." Now we know that the body of the function works properly.

There are advantages and disadvantages to both approaches. In some senses, the tradeoffs are the same as any duck typed vs not situation: the C++ approach is far more flexible, but the Rust approach has stronger guarantees. We also chose the style we did because we prefer the nicer errors; C++ template errors are notoriously complex, though many say they get used to how to read them over time.

Additionally, neither languages' story is complete here. C++20 has a new feature called "Concepts" that gives you some degree of similar features here, but it's complex and I haven't read the version that was merged into the draft of C++20, so maybe someone else can elaborate on it. Rust is also adding a 'const fn' feature that gives you access to similar tricks to constexpr in C++, as well as more features for our bounded generics.

pjmlp5• 8 years ago

Your example in C++17,

    #include <iostream>
    #include <string>
    #include <type_traits>

    class Display {
        virtual std::string fmt() = 0;
    }; 
    
    template<typename T>
    void f(T s)
    {
        static_assert(std::is_base_of<Display, T>::value, "Error: T must implement Display interface");

        std::cout << s << '\n';
    }
     
    int main()
    {
        f(7);
    }

Gives the following error with clang,

  <source>:12:7: error: static_assert failed "Error: T must implement Display interface"
        static_assert(std::is_base_of<Display, T>::value, "Error: T must implement Display interface");
        ^             ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  <source>:19:7: note: in instantiation of function template specialization 'f<int>' requested here
        f(7);
        ^
  1 error generated.
  Compiler returned: 1

Of course the downside is having the library author spending extra effort to write those checks.

Rusky• 8 years ago

Concepts (lite, the version that is still around) are "one-way." They constrain what types you can use as template arguments, but they do not constrain what templates can do.

Which means the templates themselves can still impose additional requirements based only on their internals, leading to the same bad error messages for users and lack of checking for library authors that we have without concepts.

taeric5• 8 years ago

Both make debugging harder. Rust, though, keeps a lot more safety in the whole process. The resulting code is syntactically what the macro author meant, by the types.

And, nobody really steps through code anymore. So a lot of the difficulty argument is moot.

fb033• 8 years ago

And, nobody really steps through code anymore.

I don't follow. What other technique is in, compared to code stepping?

Sometimes I put a breakpoint in and step thru code to help me figure if something is working properly or maybe live-inspect the return value of something that comes from the outside world. Maybe I'm missing some new fundamental technique to dev/debug?

Thanks in advance. (genuine question)

pjmlp5• 8 years ago

I do, but Visual Studio debugger lets me chose what I step into to.

pcwalton• 8 years ago

C++ templates are intertwined with parsing and typechecking, while Rust has two separate features that cover the same ground: macros, which are purely parse time, and generics, which are purely run at typechecking time. This has advantages and disadvantages. The advantage of C++'s model is that it has one feature instead of two, and this allows for features like SFINAE that Rust has no analogue to. The advantages of Rust's model are that (1) the implementation is a lot simpler; (2) you can typecheck generics before they're expanded, which is a big improvement in ergonomics; (3) generics cover 90% of the use cases, so you rarely have to reach for macros.

justinpombrio• 8 years ago

C++ templates also aren't general purpose macros. For example, in Rust you can write a macro that takes an expression `e` and replaces it with `e + 1`.

However, I believe you can't do that with C++ templates. C++ template parameters can be types or primitive values, but not expressions. And the body of a template has to be some sort of declaration, e.g. a function definition or struct definition, but not an expression or statement.

lucozade2• 8 years ago

As a, slightly facetious, addition. I think Rust macros are better than either the C preprocessor or C++ templates because they're so bloody confusing.

They require someone with a great deal of energy, knowledge and will to win in order to tease anything useful out of them. This, I submit, is a feature. It dissuades the programmer who believes they are better than they are from being too clever by half.

There are worse things in the programming sphere than crap meta-programming but it does have its own circle in hell.

I appreciate that the Rust team are working hard to spoil my happy idyll but happy I remain for now.

kibwen3• 8 years ago

I tend to agree with the argument that Rust macros are deliberately ugly so that people will only reach for them as a last resort (learning the hard-won lesson from Lisp, as it were), but there's no way that Rust macros are any more confusing than the C preprocessor or C++ templates. Have you ever tried to write a C macro that actually expands to what you want it to, in all possible contexts? And the less said about the horrors of C++ templates, the better. No, the fact that Rust macros have severe (deliberate) limitations is what makes them tractable; there's no shenangians comparable to `#define true false`.

devit• 8 years ago

C++ templates are bad because they are untyped generics (e.g. C++ doesn't check that the key type for an hashmap is hashable, and instead you get a bunch of errors that there is no "hash" overload accepting certain arguments when you try to call a method on the hashmap).

C++ tried to add a type system for templates with "concepts" but it was scrapped.

Rust instead has properly typed generics instead using the trait system, resulting in proper static checking and proper error messages (although without higher kinded types and const generics currently, that C++ instead supports).

Rust also has a powerful macro system, which is unrelated to templates, although you can use them to have kinds of abstractions that the language doesn't support directly (like higher kinded types, const generic or abstracting over mutability), at the cost of having to explicitly perform instantiation, not having inference and having a higher cognitive burder.

steveklabnik7• 8 years ago

C++ tried to add a type system for templates with "concepts" but it was scrapped.

concepts was merged into the C++2020 draft recently, so not entirely scrapped! I forget if it was full-blown concepts or "concepts lite" though.

pjmlp5• 8 years ago

Concepts are on track for C++20 and they are already available on gcc to play with.

Besides that, it is already possible to use typed templates in C++, at least with any C++14 compiler and even better on C++17, even if it requires a bit more of effort for the implementer of the generic code.

Basically by making use of type traits, static asserts, constexpr if and enable_if.

Yes, it isn't as clean as Rust but as shown by Andrei Alexandrescu with D, it opens the door for very powerful designs.

earenndil• 8 years ago

C++ doesn't check that the key type for an hashmap is hashable

I thought it was possible to do something like this? (disclaimer: I don't use c++)

class Hashable { abstract char *hash() = 0; } template<typename T: Hashable, typename U> class Hashmap { vector<U> buckets; // etc. }

kazinator7• 8 years ago

instead you get a bunch of errors that there is no "hash" overload

Since you get some kind of compile-time diagnostic, then effectively, the type is checked. Just, within static time, not as early as you'd like, with not as a relevant a diagnostic.

ISO C++ doesn't dictate the wording of diagnostics; a C++ implementation could work backward from that error, or do whatever else, in order to phrase the diagnostic in terms of a problem in the template.

zwieback• 8 years ago

As an hp-er I'm all for RPN but that code is making my eyes bleed. I'm assuming it's just an example and not some kind of endorsement.

RReverser2• 8 years ago

Yeah just used it as a (hopefully) simple and familiar example to explain macro mechanics.

inurigakko• 8 years ago

Rust is probably the most advanced programming language with the worst syntax. Prolog and Erlang are a joy after Rust.

carlmr4• 8 years ago

What is so terrible about the syntax? My biggest problem with Rust isn't the language, but the tooling which is still not quite there yet.

I find the syntax ok, and you do get used to the snake_case.

fb033• 8 years ago

I'm there with you. Have you found something consistent/stable to debug Rust code? I find the integration with VS:Code to be quite flimsy and friends have been saying that's like the pinnacle of Rust tooling right now, to have a fully loaded VS:Code with the Rust plugins...

jandrese• 8 years ago

My impression has always been that it probably feels right at home for people with mathematical backgrounds, and mildly line-noisy for people coming from traditional programming backgrounds.

Stuff like this:

  fn map<T, U, F>(vector: &[T], function: F) -> Vec<U>
    where F: for<'a> Fn(&'a T) -> U {
    ...

It's not too hard to read once you're in the ecosystem, but there's a lot of non-alphanumerics in there, and you know each one of them is super important to getting the thing working.

mcguire3• 8 years ago

Prolog and Erlang are untyped. Er, dynamically typed. That changes quite a lot.

quotheth• 8 years ago

I personally find Rust quite a joy to read.

mcguire3• 8 years ago

Rust macros strike me as closely related to Scheme hygienic macros; is there a compare-n-contrast anywhere?

DC-3• 8 years ago

I believe Rust took direct inspiration from Scheme (or at the very least functional languages in general).

kibwen3• 8 years ago

The original designers of the macro system absolutely had Scheme firmly in mind (source: I was there). The most telling giveaway is that the identifier for declaring macros, "macro_rules", is a reference to Scheme's "syntax-rules". As for a comparison, Rust macros have to jump through hoops to account for the fact that Rust has syntax (and types), and the Rust system isn't entirely hygienic yet (work in progress).

agumonkey2• 8 years ago

RISP

tomsmeding• 8 years ago

I didn't actually try out the code, so I don't know whether it actually works regardless, but this looks really suspicious:

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

Is that not, like, operator precedence gone really wrong? Or is this the rust stringifier in trace_macros messing up without anything going wrong in the actual AST?

agumonkey2• 8 years ago

I'd say macroexpansion is precedence agnostic.

folding * over 4, 3+7, 2

   */ 4, 3+7, 2
   */ 3+7 * 4, 2
   */ 2 * 3+7 * 4

   => 2 * 3 + 7 * 4

so basically, beware

dbaupp• 8 years ago

The trace_macros! stringifier isn't inserting parens when required: due to the use of 'expr' the macro is treating 3 + 7 as a single node X, and then the multiplication with 4 is, in the AST, X * 4 (i.e. correct). The thing that is being printed there is the recursive rpn invocation in the @op branch, and specifically the '$a $op $b', which is a "disconnected" sequence of AST items/token trees. Once it's forced to be parsed as an expression (that is, when matched against the recursive '$... : expr' rules), the printer handles it correctly. For instance, the last 'to' line of the output in the example you quote, or, if that example is changed to 'rpn!(2 3 7 + 4 * 5)', the trace_macros output includes:

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

kazinator7• 8 years ago

Here is my ten minute implementation in TXR Lisp:

Trying rpn-compile at the REPL:

  $ txr -i rpn.tl
  1> (rpn-compile '(3))
  (let* () 3)
  2> (rpn-compile '(3 4 +))
  (let* ((#:g0266 4)
         (#:g0267 3)
         (#:g0268 (+ #:g0266 #:g0267)))
    #:g0268)
  3> (rpn-compile '(3 4 + 5 6 + *))
  (let* ((#:g0269 4)
         (#:g0270 3)
         (#:g0271 (+ #:g0269 #:g0270))
         (#:g0272 6)
         (#:g0273 5)
         (#:g0274 (+ #:g0272 #:g0273))
         (#:g0275 (* #:g0274 #:g0271)))
    #:g0275)
  4> (rpn-compile '(3 4 + dup *))
  (let* ((#:g0276 4)
         (#:g0277 3)
         (#:g0278 (+ #:g0276 #:g0277))
         (#:g0279 (* #:g0278 #:g0278)))
    #:g0279)

Code in rpn.tl:

  (defstruct rpn-compile-time nil
    temps
    lets
    stack)
  
  (defun allocate-temp (rct)
    (push (gensym) rct.temps)
    (first rct.temps))
  
  (defun compile-expr (rct expr)
    (if (member expr rct.temps)
      expr
      (let ((temp (allocate-temp rct)))
        (push ^(,temp ,expr) rct.lets)
        temp)))
  
  (defun compile-dup (rct)
    (let ((top (compile-expr rct (pop rct.stack))))
      (push top rct.stack)
      (push top rct.stack)))
  
  (defun compile-swap (rct)
    (swap (first rct.stack) (second rct.stack)))
  
  (defun compile-binop (op rct)
    (let* ((left (compile-expr rct (pop rct.stack)))
           (right (compile-expr rct (pop rct.stack)))
           (sum (compile-expr rct ^(,op ,left ,right))))
      (push sum rct.stack)))
  
  (defvar *compile-table*
    ^#H(() (dup ,(fun compile-dup))
           (swap ,(fun compile-swap))
           (+ ,(op compile-binop '+))
           (- ,(op compile-binop '-))
           (* ,(op compile-binop '*))
           (/ ,(op compile-binop '-))))
  
  (defun rpn-compile (exprs)
    (let ((rct (new rpn-compile-time)))
      (each ((word exprs))
        (iflet ((fun [*compile-table* word]))
          [fun rct]
          (push word rct.stack)))
      ^(let* ,(reverse rct.lets) ,(first rct.stack))))

Having this function, making the macro is trivial. At the REPL again:

  5> (defmacro rpn (. exprs) (rpn-compile exprs))
  rpn
  6> (rpn 2 2 +)
  4

jnordwick• 8 years ago

Does the evaluate at compile time to a constant or does it produce that series of let bindings?

kazinator7• 8 years ago

Nope; it makes the let bindings. The job of reducing to a constant is better left to the processing of the let rather than duplicated in the macro.

If you have a compiler which can reduce (let ((x 3)) ((y 4)) (+ x y)) to 5, why replicate that in a macro.

If you do not have one (as is the case here), then it's better to work on getting one than compensating for it in macros.

Yet, with the following small change to compile-expr, whereby we avoid generating temps for constant expressions, we can at least get some nicer-looking output:

  (defun compile-expr (rct expr)
    (cond
      ((member expr rct.temps) expr)
      ((constantp expr) expr)
      (t (let ((temp (allocate-temp rct)))
           (push ^(,temp ,expr) rct.lets)
           temp))))

  1> (rpn-compile '(3 4 + 5 6 + *))
  (let* ((#:g0266 (+ 4 3))
         (#:g0267 (+ 6 5))
         (#:g0268 (* #:g0267 #:g0266)))
    #:g0268)

Writing Complex Macros in Rust: Reverse Polish Notation

Related Stories