13 ms·

Writing Complex Macros in Rust: Reverse Polish Notation

99 points by jgrahamc 9y ago

cheez 9y 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.
- navaati 9y 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.
  - foldr 9y ago
    Rust macros actually work more at the token level than at the AST level.
    - navaati 9y ago
      Oh I see, thx !
    - RReverser 9y ago
      They work on both - for example, if you specify $expr:expr, it will actually parse it as an expression node and won't allow to simply pass it into another macro as $pat:pat because of AST node type mismatch even if actual tokens are still compatible.
      - foldr 9y ago
        That's a good point. What I was trying to get at is that Rust macros don't let you manipulate ASTs in any straightforward way. So they are not best thought of as AST -> AST transforms.
  - kibwen 9y ago
    Rust macros are Scheme macros, there's no similarity to C.
- ChrisSD 9y 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#macro-parsing-and-expansion https://danielkeep.github.io/practical-intro-to-macros.html#...
- fleetfox 9y ago
  Would Lisp macros make sense in language that is not homoiconic?
  - maxiepoo 9y ago
    Yes: http://calculist.org/blog/2012/04/17/homoiconicity-isnt-the-point/ http://calculist.org/blog/2012/04/17/homoiconicity-isnt-the-...
    - mcguire 9y ago
      Fine. Would lisp macros make sense in a language that isn't fully parenthesized?
      - wtetzner 9y ago
        Yes: https://www.cs.utah.edu/~rafkind/papers/honu-2012.pdf https://www.cs.utah.edu/~rafkind/papers/honu-2012.pdf Honu is a language with Javascript-like syntax, but has support for syntax-case style macros.
      - Avshalom 9y ago
        Factor https://factorcode.org/ https://factorcode.org/ by comparison to gp's article Facotr macros are easy because instead of knowing exactly where and what the arguments are in Factor the reader doesn't have to care.
  - kazinator 9y 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 9y 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 https://doc.rust-lang.org/proc_macro/index.html [1]: https://github.com/dtolnay/syn https://github.com/dtolnay/syn [2]: https://github.com/dtolnay/quote https://github.com/dtolnay/quote
- wtetzner 9y ago
  They're actually closer to syntax-rules in Scheme.
pleasecalllater 9y 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 9y 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.
- steveklabnik 9y 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 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.
zwieback 9y 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.
- RReverser 9y ago
  Yeah just used it as a (hopefully) simple and familiar example to explain macro mechanics.
inurigakko 9y ago
Rust is probably the most advanced programming language with the worst syntax. Prolog and Erlang are a joy after Rust.
- carlmr 9y 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.
  - fb03 9y 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...
    - steveklabnik 9y ago
      We're still committed to improving tooling, so please file bugs! I've used the "Native Debug" extension with VS: Code in the past. I've heard that if you have a CLion license, it (with the Rust plugin) is pretty solid at debugging, but I don't own one of those.
      - carlmr 9y ago
        I know you are. I didn't mean to take a jab at you. Rust is amazing for how young the language still is. I also don't have a CLion license, but I've also heard from multiple sources that that is right now the best IDE. What do you mean by "Native Debug" extension for VSCode? The normal Rust plugin built on top of Racer often shows Racer as crashed, and doesn't underline errors while typing. It also doesn't really seem to know the type of a variable most of the time. I'm writing in too many languages at once. Autocompletion usually gives me enough of a hint that I remember what to type. VSCode being my favorite editor, so I'm glad that I don't need to install another IDE right now. EDIT: I just checked it out, and apparently you can install the Rust plugin with IntelliJ Community Edition. Which is free.
deleted 9y ago
[deleted]
mcguire 9y ago
Rust macros strike me as closely related to Scheme hygienic macros; is there a compare-n-contrast anywhere?
- DC-3 9y ago
  I believe Rust took direct inspiration from Scheme (or at the very least functional languages in general).
- deleted 9y ago
  [deleted]
- kibwen 9y 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).
agumonkey 9y ago
RISP
tomsmeding 9y 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?
- agumonkey 9y 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 9y 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 ] }` ...
kazinator 9y 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 9y ago
  Does the evaluate at compile time to a constant or does it produce that series of let bindings?
  - kazinator 9y 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)

99 points by jgrahamc 9y 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.

navaati 9y 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.
- foldr 9y ago
  Rust macros actually work more at the token level than at the AST level.
  - navaati 9y ago
    Oh I see, thx !
  - RReverser 9y ago
    They work on both - for example, if you specify $expr:expr, it will actually parse it as an expression node and won't allow to simply pass it into another macro as $pat:pat because of AST node type mismatch even if actual tokens are still compatible.
    - foldr 9y ago
      That's a good point. What I was trying to get at is that Rust macros don't let you manipulate ASTs in any straightforward way. So they are not best thought of as AST -> AST transforms.
- kibwen 9y ago
  Rust macros are Scheme macros, there's no similarity to C.
ChrisSD 9y 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#macro-parsing-and-expansion https://danielkeep.github.io/practical-intro-to-macros.html#...
fleetfox 9y ago
Would Lisp macros make sense in language that is not homoiconic?
- maxiepoo 9y ago
  Yes: http://calculist.org/blog/2012/04/17/homoiconicity-isnt-the-point/ http://calculist.org/blog/2012/04/17/homoiconicity-isnt-the-...
  - mcguire 9y ago
    Fine. Would lisp macros make sense in a language that isn't fully parenthesized?
    - wtetzner 9y ago
      Yes: https://www.cs.utah.edu/~rafkind/papers/honu-2012.pdf https://www.cs.utah.edu/~rafkind/papers/honu-2012.pdf Honu is a language with Javascript-like syntax, but has support for syntax-case style macros.
    - Avshalom 9y ago
      Factor https://factorcode.org/ https://factorcode.org/ by comparison to gp's article Facotr macros are easy because instead of knowing exactly where and what the arguments are in Factor the reader doesn't have to care.
- kazinator 9y 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 9y 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 https://doc.rust-lang.org/proc_macro/index.html [1]: https://github.com/dtolnay/syn https://github.com/dtolnay/syn [2]: https://github.com/dtolnay/quote https://github.com/dtolnay/quote
wtetzner 9y ago
They're actually closer to syntax-rules in Scheme.

pleasecalllater 9y 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 9y 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.
steveklabnik 9y 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 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.

zwieback 9y 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.

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

inurigakko 9y ago

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

carlmr 9y 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.
- fb03 9y 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...
  - steveklabnik 9y ago
    We're still committed to improving tooling, so please file bugs! I've used the "Native Debug" extension with VS: Code in the past. I've heard that if you have a CLion license, it (with the Rust plugin) is pretty solid at debugging, but I don't own one of those.
    - carlmr 9y ago
      I know you are. I didn't mean to take a jab at you. Rust is amazing for how young the language still is. I also don't have a CLion license, but I've also heard from multiple sources that that is right now the best IDE. What do you mean by "Native Debug" extension for VSCode? The normal Rust plugin built on top of Racer often shows Racer as crashed, and doesn't underline errors while typing. It also doesn't really seem to know the type of a variable most of the time. I'm writing in too many languages at once. Autocompletion usually gives me enough of a hint that I remember what to type. VSCode being my favorite editor, so I'm glad that I don't need to install another IDE right now. EDIT: I just checked it out, and apparently you can install the Rust plugin with IntelliJ Community Edition. Which is free.

deleted 9y ago

[deleted]

mcguire 9y ago

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

DC-3 9y ago
I believe Rust took direct inspiration from Scheme (or at the very least functional languages in general).
deleted 9y ago
[deleted]
kibwen 9y 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).

agumonkey 9y ago

RISP

tomsmeding 9y 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?

agumonkey 9y 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 9y 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 ] }` ...

kazinator 9y 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 9y ago
Does the evaluate at compile time to a constant or does it produce that series of let bindings?
- kazinator 9y 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)