Writing Complex Macros in Rust: Reverse Polish Notation

Re:Writing Complex Macros in Rust: Reverse Polish Notation by kazinator on Thursday February 01, 2018 @03:42PM (#16285668)

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

[ Parent | on HN ]

Re:Writing Complex Macros in Rust: Reverse Polish Notation by jnordwick on Thursday February 01, 2018 @04:27PM (#16286065)

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

[ Parent | on HN ]

Re:Writing Complex Macros in Rust: Reverse Polish Notation by kazinator on Thursday February 01, 2018 @08:33PM (#16287627)

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)

[ Parent | on HN ]