Macro expanding to same operator

Question

Many Lisp-family languages have a little bit of syntax sugar for things like addition or comparison allowing more than two operands, if optionally omitting the alternate branch etc. There would be something to be said for implementing these with macros, that would expand (+ a b c) to (+ a (+ b c)) etc; this would make the actual runtime code cleaner, simpler and slightly faster (because the logic to check for extra arguments would not have to run every time you add a pair of numbers).

However, the usual macro expansion algorithm is 'keep expanding the outermost form over and over until you get a non-macro result'. So that means e.g. + had better not be a macro that expands to +, even a reduced version, or you get an infinite loop.

Is there any existing Lisp that solves this problem at macro expansion time? If so, how does it do it?

Answer 1

This is an addendum to Rainer's answer: this answer really just gives some examples.

First of all compiling things like arithmetic operations is a hairy business because you there's a particular incentive to try and turn as much as possible into the operations the machine understands and failing to do that can result in enormous slowdowns in numerically intensive code. So typically the compiler has a lot of knowledge of how to compile things, and it is also allowed a lot of freedom: for instance in CL (+ a 2 b 3) can be turned by the compiler into (+ 5 a b): the compiler is allowed to reorder & coalesce things (but not to change the evaluation order: it can turn (+ (f a) (g b)) into something like (let ((ta (f a)) (tb (g b))) (+ tb ta)) but not into (+ (g b) (f a))).

So arithmetic is usually pretty magic. But it's still interesting to look at how you can do this with macros and why you need compiler macros in CL.

(Note: all of the below macros below are things I wrote without much thought: they may be semantically wrong.)

Macros: the wrong answer

So, addition, in CL. One obvious trick is to have a 'primitive-two-arg' function (which presumably the compiler can inline into assembly in good cases), and then to have the public interface be a macro which expands into that.

So, here is that

(defun plus/2 (a b)
  ;; just link to the underlying CL arithmetic
  (+ a b))

And you can then write the general function in terms of that in the obvious way:

(defun plus/many (a &rest bcd)
  (if (null bcd)
      a
    (reduce #'plus/2 bcd :initial-value a)))

And now you can write the public interface, plus as a macro on top of this:

(defmacro plus (a &rest bcd)
  (cond ((null bcd)
         a)
        ((null (rest bcd))
         `(plus/2 ,a ,(first bcd)))
        (t
         `(plus/2 (plus/2 ,a ,(first bcd))
                  (plus ,@(rest bcd))))))

And you can see that

• (plus a b) expands to (plus/2 a b)'
• (plus a b c) expands to (plus/2 (plus/2 a b) (plus c)) and thence to (plus/2 (plus/2 a b) c).

And we can do better than this:

(defmacro plus (a &rest bcd)
  (multiple-value-bind (numbers others) (loop for thing in (cons a bcd)
                                             if (numberp thing)
                                             collect thing into numbers
                                             else collect thing into things
                                             finally (return (values numbers things)))
    (cond ((null others)
           (reduce #'plus/2 numbers :initial-value 0))
          ((null (rest others))
           `(plus/2 ,(reduce #'plus/2 numbers :initial-value 0)
                    ,(first others)))
          (t
           `(plus/2 ,(reduce #'plus/2 numbers :initial-value 0)
                    ,(reduce (lambda (x y)
                               `(plus/2 ,x ,y))
                             others))))))

And now you can expand, for instance (plus 1 x y 2.0 3 z 4 a) into (plus/2 10.0 (plus/2 (plus/2 (plus/2 x y) z) a)), which I think looks OK to me.

But this is hopeless. It's hopeless because what happens if I say (apply #'plus ...)? Doom: plus needs to be a function, it can't be a macro.

Compiler macros: the right answer

And this is where compiler macros come in. Let's start again, but this time the function (never used above) plus/many will just be plus:

(defun plus/2 (a b)
  ;; just link to the underlying CL arithmetic
  (+ a b))

(defun plus (a &rest bcd)
  (if (null bcd)
      a
    (reduce #'plus/2 bcd :initial-value a)))

And now we can write a compiler macro for plus, which is a special macro which may be used by the compiler:

The presence of a compiler macro definition for a function or macro indicates that it is desirable for the compiler to use the expansion of the compiler macro instead of the original function form or macro form. However, no language processor (compiler, evaluator, or other code walker) is ever required to actually invoke compiler macro functions, or to make use of the resulting expansion if it does invoke a compiler macro function. – CLHS 3.2.2.1.3

(define-compiler-macro plus (a &rest bcd)
  (multiple-value-bind (numbers others) (loop for thing in (cons a bcd)
                                             if (numberp thing)
                                             collect thing into numbers
                                             else collect thing into things
                                             finally (return (values numbers things)))
    (cond ((null others)
           (reduce #'plus/2 numbers :initial-value 0))
          ((null (rest others))
           `(plus/2 ,(reduce #'plus/2 numbers :initial-value 0)
                    ,(first others)))
          (t
           `(plus/2 ,(reduce #'plus/2 numbers :initial-value 0)
                    ,(reduce (lambda (x y)
                               `(plus/2 ,x ,y))
                             others))))))

Note that the body of this compiler macro is identical to the second definition of plus as a macro above: it's identical because for this function there are no cases where the macro wants to decline the expansion.

You can check the expansion with compiler-macroexpand:

> (compiler-macroexpand '(plus 1 2 3 x 4 y 5.0 z))
(plus/2 15.0 (plus/2 (plus/2 x y) z))
t

The second value indicates that the compiler macro did not decline the expansion. And

> (apply #'plus '(1 2 3))
6

So that looks good.

Unlike ordinary macros a macro like this can decline to expand, and it does so by returning the whole macro form unchanged. For instance here's a version of the above macro which only deals with very simple cases:

(define-compiler-macro plus (&whole form a &rest bcd)
  (cond ((null bcd)
         a)
        ((null (rest bcd))
         `(plus/2 ,a ,(first bcd)))
        (t                              ;cop out
         form)))

And now

 > (compiler-macroexpand '(plus 1 2 3 x 4 y 5.0 z))
(plus 1 2 3 x 4 y 5.0 z)
nil

but

> (compiler-macroexpand '(plus 1 2))
(plus/2 1 2)
t

OK.

Answer 2

Common Lisp provides compiler macros.

These can be used for such optimizations. A compiler macro can conditionally decline to provide an expansion by just returning the form itself.