Irreal

Yesterday we talked about some of the difficulties in using setf in a macro and how these difficulties can sometimes be overcome by using the mysterious define-modify-macro. Today, I want to look at a more general approach that will also explain how define-modify-macro works.

Last time, we wrote the += macro to implement the C += operator. That worked out well so we might decide to do a -= and then a *= and so on. After awhile we realize that we’re repeating the same pattern over and over so we decide to write a general version, op=, that will take the operator we want as an argument. That is we want to write

(op= + x y)

instead of

(+= x y)

That way we have only one macro and it works for any operator:

(op= floor x y) → (setf x (floor x y))

We can’t use define-modify-macro here because it requires the name of the function at the time of the call to define-modify-macro and we want to make op= take the function as an argument. We also can’t write

(defmacro op= (op x y)
  `(setf ,x (,op ,x ,y)))

because of the problems we discussed last time.

To help us with problems like this, Common Lisp provides the function get-setf-expansion. To see how it works, let’s call it on the place we used last time, (aref a i):

CL-USER> (get-setf-expansion '(aref a i))
(#:G1409 #:G1410)
(A I)
(#:G1408)
(CCL::ASET #:G1409 #:G1410 #:G1408)
(AREF #:G1409 #:G1410)

The call returns 5 values. The second is a list of input arguments for the aref and the first is a list of corresponding temporaries into which those arguments should be evaluated. The third is a list (always of length 1) of a temporary into which the final value to be stored should be put. The fourth value is code to store the final value and the fifth is code to retrieve the value referenced by the setf argument.

We want our macro to expand into something like

(let* ((#:G1409 A)
       (#:G1410 I)
       (#:1408 (op (aref #:G1409 #:G1410) y)))
  (CCL::ASET #:G1409 #:G1410 #:G1408))

Notice that if the i variable is something like (incf i) this still works because i is evaluated only once.

With that skeleton, it’s pretty easy to write the macro

(defmacro op= (op place y)
  (multiple-value-bind (temps args val setter getter)
      (get-setf-expansion place)
    `(let* ,(append (mapcar #'list temps args)
                    `((,(car val) (,op ,getter ,y))))
       ,setter)))

When we expand it we get

CL-USER> (macroexpand '(op= + (aref a i) 3))
(LET* ((#:G1470 A) (#:G1471 I) (#:G1469 (+ (AREF #:G1470 #:G1471) 3))) (CCL::ASET #:G1470 #:G1471 #:G1469))
T

which is a slightly less well-formatted version of our skeleton. When we try it out, we get the expected result

CL-USER> (let ((a #(2 4 6 8)) (i 2))
           (op= + (aref a i) 3)
           a)
#(2 4 9 8‍)

The idea for the op= macro is based on Paul Graham’s _f macro from On Lisp, a great book for learning about macros.

We’re now in a position to understand define-modify-macro. What it does is to take its arguments and then build a defmacro much like op=‘s. The resulting macro calls get-setf-expansion, sets up a let* just like op=, and then inserts ,setter as the body of the let*.

One of the wonders of Common Lisp is the generalized variable. Roughly speaking, a generalized variable is an expression that can serve as the first argument to setf. The official explanation, as given in Common Lisp the Language, 2ed., is here. A convenient way of thinking about generalized variables is that they name a place that can contain a Lisp object.

The easiest such case is a simple variable such as x. In the expression

(setf x (* x 3))

x is the name of a place that will hold a value 3 times larger than its current value after the setf is executed. Notice that since x can occur as the first argument to setf it is a (trivial) example of a generalized variable.

A meatier example is (car x). The (car x) names a place (the car of the cons x) that can hold a value. As with the previous example, we can use the name of that place to both get and set the object it contains:

(setf (car x) (* (car x) 3))

Things get interesting when we try to use setf in macros. For example, suppose we want to write a macro that implements the C += operator. We might try something like

(defmacro += (x y)
  `(setf ,x (+ ,x ,y)))

This seems to work pretty well.

CL-USER> (let ((a #(2 4 6 8)) (i 2))
           (+= (aref a i) 3)
           a)
#(2 4 9 8‍)

But suppose we want to increment two entries in a row

(defun incr2 (a i)         
  (+= (aref a i) 3)
  (+= (aref a (incf i)) 3))

CL-USER> (let ((a #(2 4 6 8)) (i 1))
           (incr2 a i)
           a)
#(2 7 11 8‍)

What happened? Instead of #(2 7 9 8‍) we got #(2 7 11 8‍). The experienced macro writer will see immediately that the problem is that the += macro evaluates its first argument twice. Most of the time, as in the example before last, that doesn’t matter but in the last example it causes i to be incremented twice. Expanding the macro call (+= (aref a (incf i)) 3) shows what happened

CL-USER> (macroexpand '(+= (aref a (incf i)) 3))
(CCL::ASET A (INCF I) (+ (AREF A (INCF I)) 3))
T

The first (incf i) increments i to 2 so that the result will be stored in the 3^rd slot of the array. The second (incf i) increments i to 3 so that we add 3 to the 4^th slot of the array and store 11 in slot 3.

The usual way of handling this sort of thing is to evaluate the variable once into a temporary and then use the temporary in the rest of the macro. But that doesn’t work here because setf is itself a macro and needs the name of the place to figure out how to get and store the value. Fortunately, there’s an easy way of addressing this problem for the += macro. Instead of our previous definition, we use

(define-modify-macro += (y) +)

What’s happening here is not obvious but this says to create a macro named += that takes two arguments, the place to be set and y, operates on them with +, and stores the result in place. See the Common Lisp HyperSpec for the details on define-modify-macro.

With this definition of += things work correctly

CL-USER> (let ((a #(2 4 6 8)) (i 1))
           (+= (aref a (incf i)) 3)
           a)
#(2 4 9 8‍)

In this example, place is (aref a (incf i)) so the result is equivalent to

(let ((i (incf i)))
  (setf (aref a i) (+ (aref a i) 3)))

although that is not the actual expansion.

Next time, we’ll look at some macros using setf that require more general methods. After that, it will be easier to see what define-modify-macro is actually doing.