Jonathan Amsterdam is a graduate student at MIT's artificial intelligence laboratory,. He has articles published in several magazines, including the April, 1988 issue of DDJ. He can be reached at Room 814, 545 Technology Squ., Cambridge, MA 02139.
More than any other language, Lisp gives you the power to alter and augment the system--and, if you are not careful, the rope to hang yourself in the process. There are many reasons for Lisp's extensibility: interpreted execution, which permits you to use the full power of Lisp when writing macros; a uniform representation of programs to be manipulated easily; and a simple and uniform syntax, which allows macros to take on the appearance of built-in functions and control structures. The extensible nature of Lisp is one reason, in fact, that MIT professor Joel Moses once compared it to a ball of mud: no matter how much mud you add to Lisp, he said, it still looks like a ball of mud. In this article, I examine the ways you can extend the language using macros.
With two exceptions, a Lisp macro is evaluated just like any other Lisp function. The first exception is that the macro's arguments are not evaluated, the second exception is that the value of the result issued in subsequent computation. The following macro, which is a useful device for those programmers who find Lisp's function names too cryptic, illustrates these exceptions:
(defmacro first (x)
(list 'car x))This macro makes first a synonym for car, so (first '(a b)) causes first to execute on the list '(a b). The operation first returns (car '(a b)), which is then evaluated to yield a. Used interpretively, macros are no cheaper than functions, but when Lisp code is compiled, the initial evaluation (called macro expansion) is done at compiletime, so there is no loss of efficiency. For all practical purposes, using first is the same as using car. Therefore, you can think of Lisp macros as extensions to the compiler.
Note that you could have used the backquote notation to create the macro just given like this:
(defmacro first (x)
`(car ,x))The first symbol on the second line is not the familiar Lisp quotation mark, but is a backquote (the accent grave to francophones). Backquotes act just like quotation marks, except that any form inside a backquote that's preceded by a comma is evaluated.
You can see how Lisp macros can be used to replace functions, or sequences of statements, by a single call. These sorts of macros are commonly used, but they're not terribly interesting; you can get the same effects with C's macro preprocessor. Time is too precious to waste discussing them, so let's move on to more exciting things. Many of the macros I'll be discussing already exist in full-featured Lisps, like Common Lisp, but for expository purposes I'll assume a very bare-bones Lisp, with no control structures except for function calling, cond, prog, and go. So to write a simple loop, you'd have to write something like the code in Example 1, this page. There's nothing wrong with this code, except that it's ugly. If you had a while loop, you could have instead written the much prettier code in Example 2, this page. To define a while loop, you can write a macro like the one in Example 3, this page. There is, however, some syntax in Example 3 that I need to explain.
The &rest keyword indicates that the remaining arguments to the macro should be gathered together into a single list named body. The ,@ following inside the backquote evaluates the form, as does the comma, but it then appends this value into the resulting list, instead of consing it in. The effect of this is to remove one layer of parentheses from the form. Expanding the while macro in the code in Example 1 results in (> = i 10) being bound to test and ((print i) (setq i (+ i 1))) being bound to body. The program of Example 2 is shown in Example 4, this page.
The while loop looks just like ordinary, built-in Lisp. Since all of Lisp--even control flow--looks like functions applied to arguments, macros fit in quite nicely. In languages like C that have a variety of syntactic constructs, macros, which usually have the syntax of function calls, look out of place when you use them to define control structure.
You can improve the while loop by writing a for loop, thereby allowing the computation to be expressed as shown in Example 5, this page. The complete macro is shown in Listing One, starting on page 56. in the Listing, I've assumed that first, second, and third are defined either as macros or functions in the obvious way. This macro is the first one illustrated so far that performs some computation instead of immediately returning a form. In this case, the computation is trivial--just taking apart its first argument--but in general, you can perform any computation.
To illustrate further, examine the macro in Listing Two, page 56, that performs simple loop unrolling: if the macro notices that the bounds of the iteration are within one of each other, the macro won't generate loop code at all. This macro is quite interesting: it will generate different code at compile-time depending on its arguments. If Lisp macros are compiler extensions, then we have just written part of an optimizing compiler.
We'll return to iteration in a moment, but first I'd like to discuss self a clever macro that's been lurking around for years and that has finally stepped into the limelight because of its incorporation into Common Lisp.self is interesting because it's an extensible macro. In its simplest form, you can use self like setq:
(setf a 3)
But you can also use self to set almost anything, such as elements of lists or arrays:
(setf (car a-list) 'x) (setf (aref an-array 3) nil)
You can extend self so that it can handle new forms. The key to providing this extensibility is Lisp's property-list feature. The self macro does no work by itself: instead, it looks at the first element of the form that it receives, and calls the function on the self-method property of the symbol. Before making the call, however, self expands any macros in the form by calling the built-in function macroexpand shown in Example 6 on this page. The self methods perform all the work. Example 7, page 24, shows how the macro for car might look. This macro expands (setf (car a-list) 'x) into (rplaca a-list 'x). Before using it, we must install it on car's property list. in most Lisps, you'd use putprop for this, but just to show you how far Common Lisp has incorporated setf the only (documented) way to add a property to a property list in Common Lisp is as follows:
(setf (get 'car 'setf-method) 'car-setf-method)
Example 8, page 24, shows how to define the setf-method for aref assuming the function aset exists.
You can combine iteration with extensibility to produce an extensible iteration macro. I'll call this macro for as well, because it will subsume our earlier attempt. This macro will let you say something like:
(for (i from 1 to 10) ...)
to iterate over a range of numbers,
(for (el in '(abc)) ...)
to iterate over the elements of a list,
(for (subl on '(abc))...)
to iterate over successive sublists--in this case the lists (a b c), (b c), (c)
and
()
and
(for (ael array-elements of a) ...)
to iterate over the elements of an array.
The syntax of our macro is fairly straightforward: after for, there is a list consisting of a variable name, a keyword that indicates the type of iteration, and some additional items describing the iteration. You could write the macro to test for each keyword in turn and output the appropriate code, but that wouldn't allow the user to extend it. Instead, we'll use the property-list feature. This new macro (implemented in Listing Three, page 56) looks on the property list of the keyword for the value of the property for-expander; this should be a function of two arguments, the variable name and the item following the keyword. The function will return a list of three items: initialization code that will be executed before the loop begins; a piece of test code that will be run before each iteration; and update code that will be run after the body executes on each iteration. The initialization code and the update code should be lists of statements. Let's do two of the earlier mentioned four examples. The function for numbers, is shown in Example 9, this page.
There is one additional feature: you can get an infinite loop by omitting to and writing only (i from 3). Doing this can be useful, as you'll see later. Next, we need to install num-expander on the property list of from:
(setf (get 'from 'for-expander) 'num-expander)
The function for list elements is given in Example 10 , this page. This function is a little tricky because the iteration variable, which steps over sublists, is hidden. Since the macro needs to come up with its own variable, it creates a brand new symbol using the Lisp function gensym. The other two examples of for, along with any others you can think of, are left as exercises.
Here's another small extension to the for macro. Often, you might like to iterate over two different sequences in the same loop. For instance, imagine that you wanted to put the elements of a list into an array. One approach is shown in Example 11, this page, but this technique will perform extra work, using cdr down on the list from the beginning for each element. A better approach is to iterate over the list and the integers simultaneously, as shown in Example 12, this page. Since for is defined to terminate as soon as any of the iteration clauses terminates, you can omit the to in the counting clause. Note the word do: You must include it to distinguish the body of the loop from the clauses. Alternatively, you could have enclosed all the clauses in a list, but sometimes it is worth adding a keyword to get rid of a layer of parentheses.
The for macro is actually a small example of what you can do with iteration. A bigger step is the loop macro of Symbolics Common Lisp, whose fine-grained model of iteration allows for more complex control-flow patterns. For example, the functions you write to extend loop must return not 3, but 6 values. The complete code for for can be found in Listing Four, page 58.
Let's turn from control abstraction to data abstraction, and implement a simple record package in Lisp. Assume your Lisp has arrays and you want to implement records in terms of those arrays. You would probably want to write:
(defrecord complex
real imag)to define a record for complex numbers,
(make-complex 3 4)
to construct the number with a real part 3 and an imaginary part 4,
(complex-real c)
to extract the real part of the complex number c, and
(setf (complex-imag c) 5)
to set the imaginary part of c. Furthermore, imagine that you'd like accessing components to be no more expensive than array references, so the accessing functions need to be macros. What's interesting about defrecord, then, is that it's a macro-generating macro. It is actually very straightforward to write (see Listing Five on page 58). The only tricky part--and believe me this comes only with considerable macro-writing experience--is keeping straight how many times to evaluate something.
Since defrecord returns more than one form, it wraps them all in a progn. First it defines the make function and then, for each record component, an accessor macro. Because self already knows about aref and expands macros automatically, you don't have to do anything else to get self to work correctly on the records.
There are scores of extensions you could add to defrecord. I'll describe the way to implement a few of them, leaving the code to you.
As it stands now, records are just arrays and accessor functions are just array references, so there's no protection: you could use complex-imag to access a record of another type. To ensure that you are using record selectors only on records of the appropriate type, you could put the name of the record into the zeroth slot of each record created, and have the accessor functions check this tag before they do anything. Since each accessor macro will no longer be a simple aref you'll have to write self functions as well, which will also need to check the record type.
At the same time, you could also address another typing issue. Right now, you could put a Lisp symbol into a slot of a complex record, where only numbers should go. This ability, of course, is a problem (or feature, depending on your point of view) with Lisp, but you can have it both ways. Let's extend the defrecord syntax so that
(defrecord complex
(real number)
(imag number))is allowed, so that you can place only numbers in the record's slots. Now setf functions, in addition to checking that they're being used on the right kind of record, also need to check the type of value they're supposed to store into a slot. To associate code--in this case, the numberp function--with the names of types, use property lists; that way, your type system will be extensible.
All this type-checking will take time, so you might want to provide an option to turn it off. You could easily arrange matters so that
(defrecord (complex :no-type-checking)
(real number)
(imag number))would result in no generation of type-checking code. For compatibility with other records' type-checking code, you'd still want to put the record name in each record you create.
Another problem is that the records print like arrays. if you tag the records with their names as I suggested earlier, you can take care of this problem by replacing your Lisp's primitive printing function with one of your own. On receipt of an array, your own function first checks to see if there's a symbol in the zeroth element, and then looks on that symbol's property list for a printing function. While adding this function, you can provide a default printing function for users of defrecord, so they don't have to do any extra work to have their records print nicely. Before long, you'll wonder how you ever lived without macros.
_ADDING EXTENSIONS TO LISP_
by
Jonathan Amsterdam
[LISTING ONE]
(defmacro for (var-from-to &rest body)
(let ((var (first var-from-to))
(from (second var-from-to))
(to (third var-from-to)))
`(prog (,var)
(setq ,var ,from)
loop
(cond ((> ,var ,to) (go end)))
,@body
(setq ,var (+ ,var 1))
(go loop)
end)))
----------------------------------------------------------------
[LISTING TWO]
(defmacro for (var-from-to &rest body)
(let ((var (first var-from-to))
(from (second var-from-to))
(to (third var-from-to)))
(cond
((and (numberp from) (numberp to) (< (- to from) 2))
;; If from and to are both numbers, and they differ by at most 1...
(cond ((< (- to from) 0)
;; they differ by < 0, hence there's no loop to generate
nil)
((= (- to from) 0)
;; they're the same, so just a single iteration
`(let ((,var ,from))
,@body))
(t
;; else, they differ by one: so two iterations
`(let ((,var ,from))
,@body
(setq ,var ,to)
,@body))))
(t ;; the general case
`(prog (,var)
(setq ,var ,from)
loop
(cond ((> ,var ,to) (go end)))
,@body
(setq ,var (+ ,var 1))
(go loop)
end)))))
----------------------------------------------------------------
[LISTING THREE]
(defmacro for (clause &rest body)
(let* ((code (funcall (get (second clause) 'for-expander)
(first clause) (cddr clause)))
(init (first code))
(test (second code))
(update (third code)))
`(prog ()
,@init
loop
(cond (,test (go end)))
,@body
,@update
(go loop)
end)))
----------------------------------------------------------------
[LISTING FOUR]
(defmacro for (&rest forms)
(let* ((do-part (member 'do forms))
(body (cdr do-part))
(clauses (ldiff forms do-part)) ;clauses = everything before "do"
(init nil)
(test nil)
(update nil))
(dolist (clause clauses)
(let ((code (funcall (get (second clause) 'for-expander)
(first clause) (cddr clause))))
(setq init (append init (first code)))
(push (second code) test)
(setq update (append update (third code)))))
(setq test (cons 'or (nreverse test)))
`(prog ()
,@init
loop
(cond (,test (go end)))
,@body
,@update
(go loop)
end)))
----------------------------------------------------------------
[LISTING FIVE]
(defmacro defrecord (name &rest components)
`(progn
,@(accessor-macro-defs name components)
(defun ,(symbol-append 'make- name) ,components
(let ((new-record (make-array ,(length components))))
,@(component-setting-list name components)
new-record))))
(defun component-setting-list (name components)
(let ((set-list nil))
(for (comp in components)
do
(push `(setf (,(accessor-name name comp) new-record) ,comp)
set-list))
set-list))
(defun accessor-macro-defs (name components)
(let ((def-list nil))
(for (i from 0 to (- (length components) 1))
do
(push `(defmacro ,(accessor-name name (nth i components)) (x)
(list 'aref x ,i))
def-list))
def-list))
(defun symbol-append (&rest symbols)
(intern (apply #'string-append symbols)))
(defun accessor-name (rec-name comp-name)
(symbol-append rec-name '- comp-name))
Example 1.
(prog (i)
(setq i 1)
loop
(cond ((> i 10) (go end)))
(print i)
(setq i (+ i 1))
(go loop)
end)
Example 2.
(setq i 1)
(while (<= i 10)
(print i)
(setq i (+ i 1)))
Example 3.
(defmacro while (test &rest body)
`(prog ()
loop
(cond ((not ,test) (go end)))
,@body
(go loop)
end))
Example 4.
(prog ()
loop
(cond ((not (>= i 10)) (go end)))
(print i)
(setq i (+ i 1))
(go loop)
end)
Example 5.
(for (i 1 10)
(print i))
Example 6.
(defmacro setf (form value)
(setq form (macroexpand form))
(cond
((symbolp form)
`(setq ,form ,value))
(t
(funcall (get (car form) 'setf-method) form value))))
Example 7.
(defun car-setf-method (form value)
`(rplaca ,(second form) ,value))
Example 8.
(defun aref-setf-method (form value)
(let ((array (second form))
(indices (cddr form)))
`(aset ,array ,value ,@indices)))
Example 9.
(defun num-expander (var from-to)
(let ((from (first from-to))
(to (third from-to)))
(list `((setq ,var ,from)) ; initialization
(if to
`(> ,var ,to)) ; test
`((setq ,var (1+ ,var)))))) ; update
Example 10.
(defun list-el-expander (var list)
(setq list (car list))
(let ((sublis-var (gensym)))
(list `((setq ,sublis-var ,list)
(setq ,var (car ,sublis-var))) ;initialization
`(null ,sublis-var) ;test
`((setq ,sublis-var (cdr ,sublis-var))
(setq ,var (car ,sublis-var)))))) ;update
Example 11.
(for (i from 0 to (- (length list) 1))
(setf (aref array i) (nth i list)))
Example 12.
(for (el in list)
(i from 0)
do (setf (aref array i) el))