Macro magic – implementing an xor macro

Posted: August 4, 2012 in Uncategorized
Tags: ,

Clojure already comes with built-in and and or macros. There are a couple of interesting things to note about these:

  • They are macros rather than functions. This enables them to have short-circuiting behaviour (a function couldn’t do this, since functions evaluate all their arguments).
  • The downside is that you can’t use them in higher order functions – (reduce and some-collection) won’t work since and isn’t a function.
  • They work with “truthiness” rather than boolean values. This is consistent with how the rest of Clojure works, and it has the nice side-effect that it enables you to use the Common Lisp idiom (or value default-value) to provide a default value in case of nils.

Anyway, suppose we want a similar macro that provides the XOR function (which isn’t yet in Clojure core)? How should we do this?

Let’s start by defining the trivial cases. This is often a good idea whenever you suspect that you may want to implement the more general case using recursion, and it can give you a warm glow that you are at least making some progress:

(defmacro xor
  ([] nil)
  ([a] a))

(xor)
=> nil

(xor true)
=> true

(xor nil)
=> nil

Note a few of points about the above:

  • You can have macros with multiple arity, just like you can with functions. No real surprise here since macros are ultimately just functions that get executed at compile-time, but it is useful in many cases.
  • We provide a zero-arity version – it is often worth thinking about the zero-argument case, since it is possible that your macro will get applied to an empty collection of arguments
  • xor with zero arguments evaluates to nil – sometimes it’s hard to immediately see what the zero-arg result should be. with xor it helps to think of xor as “bit parity” – with an even number of set bits in the input the output should be false, and this includes the zero case. So (xor) should be false.

Now we can add in the 2-argument case:

(defmacro xor 
  ([] nil)
  ([a] a)
  ([a b]
    `(let [a# ~a
           b# ~b]
      (if a# 
        (if b# nil a#)
        (if b# b# nil)))))

Again there are a few interesting things to note about this:

  • We use auto-gensyms (a# and b#) in a let statement at the start. This is an important pattern to use whenever you need the macro parameters more than once, as it ensures that the full code for a and b only gets expanded once. If you don’t do this, then you risk expanding the code for a and b multiple times, which in some cases can result in a significant performance and code size overhead (imagine if a and b were both large remotely executed computations….)
  • We define all 4 cases with nested if statements. Since if is the fundamental conditional construct in Clojure, it is both very efficient and correctly understands “truthiness”
  • We return a#, b# or nil – We could also use true/false but in the case it makes sense to use truthy/nil mainly to be consistent with  how and and or work (you don’t want to surprise your users!). true/false is more common when you are defining a predicate.
  • There is no short-circuiting – but this shouldn’t surprise us since (unlike and and or) xor needs to evaluate all inputs before it can determine the final truthiness value.

Finally we can tackle the general case. The key observation here is that xor can be defined recursively by applying xor to subsets of it’s own arguments:

(defmacro xor 
  ;; ......... other cases ..........
  ([a b & more]
   `(xor (xor ~a ~b) (xor ~@more))))

This feels good – our general case is a pretty simple recursive application of the basic cases. Does it work?

(xor nil 1 1 1)   => 1
(xor nil 1 1 nil) => nil
(xor nil nil)     => nil
(xor 1 1 1 1 1)   => 1
(xor 1 1 1 1 1 1) => nil

This is not the most comprehensive test suite ever – but it looks like we have success!

EDIT

As amalloy and Sgeo have rightly pointed out in the comments, xor doesn’t need to be a macro (as it doesn’t have the short-circuiting behaviour that necessitates the use of a macro with and and or). I wrote it as a macro for illustrative purposes (this post was after all intended as an exploration of the ideas involved in writing a simple recursive macro), but there are pros and cons of doing it either way:

  • As a macro, you gain consistency with and and or plus a minor performance benefit from avoiding function call overheads at runtime. This might be necessary for code generation or if you  have identified a particularly performance-sensitive piece of code that you need to optimise.
  • As a function, you get more flexibility in terms of use in higher order functions and the implementation itself is a bit simpler / more maintainable. As a consequence, using a function is usually the better solution in general purpose code.

I’ll leave it to the reader’s discretion to decide which approach is most appropriate in your particular case.

Advertisements
Comments
  1. Sgeo says:

    If it’s not short-circuiting, why make it a macro? To illustrate how to write macros, possibly? But in that case, it should be explained that this might not be a good idea in real code. (I should note that I have little experience in Clojure, but am aware that Lisp-family communities tend to discourage using macros where functions would fit.)

    • mikera7 says:

      Hi Sego – you make a good point – I think there are two reasons main reasons it is useful to have xor as a macro:
      a) consistency with the existing and/or macros
      b) performance – the benefit of performing macro expansion at compile time often results in code that is faster than a function call.

  2. amalloy says:

    I 100% agree that there is no excuse for this to be a macro. Consistency is irrelevant because and/or have a *reason* to be macros; it’d be more useful to be consistent with, for example, any? and every? The performance argument is absurd – a single jump to the start of the function, and a jump back out, will never in a million years be your bottleneck.

    In addition to there being no argument for making a macro, there is an argument for *not* making it a macro: the extra complexities required by writing macros made you get the implementation wrong without noticing! Aside from having misbalanced ()s, which I assume was a copy/paste error, you neglected the ` at the start of the macro definition, which makes it fail for any non-literal arguments. For example (let [x true, y false] (xor x y)) yields nil, because the symbols x and y are both truthy.

    Please, don’t teach any readers that this is what macros are good for.

    • mikera7 says:

      Hi Alan I think you can argue for doing it either way – I’ve personally found this useful as a macro (for code generation) and I think consistency among related functions is very important. Anyway thanks for the corrections!

  3. I don’t think consistency with and and or is important, since calls to macros and functions look the same, and the other common Boolean operator, not, is a function.

    Consistency might matter in Smalltalk, where calls to short-circuit operators look different (they have an explicit lambda around one argument: a and: [b]), and this apparently has caused confusion. Or in Template Haskell, where macro calls look different from function calls (although of course this application of macros doesn’t arise in Haskell).

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s