It is a common problem to need to build up a list of objects and keep all of the objects in the same order they were generated in. The idiom I see everyone use to solve this problem is to push the objects onto the head of a list as they are generated. Unfortunately, doing this reverses the initial order of the elements, so in order to preserve the ordering, a call to either reverse or nreverse is needed. For example, here is code from Alexandria that converts an alist into a plist: ¹

(defun alist-plist (alist)
  (let (plist)
    (dolist (pair alist)
      (push (car pair) plist)
      (push (cdr pair) plist))
    (nreverse plist)))

A better method to build up a list is to add the elements to the tail of the list. By adding them to the tail, you avoid having to reverse the list later. This is the same technique that some implementations of Loop use for the collect clause in order to efficiently collect objects into lists. In order to build up a list this way, you need to keep track of the head of the list (what you are ultimately going to return) and the tail of the list (where you add the next element). Doing all of that by hand would be painful. Instead we can write a macro to handle that for us automagically. Here is an implementation of accum², a macro which makes accumulating elements easy and efficient.

(defmacro accum (accfn &body body)
  (let ((ghead (gensym "HEAD"))
        (gtail (gensym "TAIL"))
        (garg  (gensym "ARG&")))
    <code>(let* ((,ghead (list nil))
            (,gtail ,ghead))
       (macrolet ((,accfn (,garg)
                    </code>(setf ,',gtail
                           (setf (cdr ,',gtail)
                                 (list ,,garg)))))
         ,@body
         (cdr ,ghead)))))

Accum is an example of a macro that writes a macro, or code that writes code that writes code. In order to explain how accum works, I am going to show how to rewrite alist-plist using accum and then explain how accum expands into code that does what we desire. Here is an implementation of alist-plist that uses accum instead of using nreverse:

(defun alist-plist (alist)
  (accum a
    (dolist (pair alist)
      (a (car pair))
      (a (cdr pair)))))

The above is both simpler and more efficient than the original version! Now for an explanation as to how it works. Accum works by generating a macrolet binding. Macrolet allows for the creation of lexically scoped macros. The lexically scoped macro is named by whatever is passed in as the accfn argument to accum, in this case a. That macro, named a, will take its argument and generate code that will evaluate the argument, and add the result of that to the tail of the list. Similar to how push is a macro that takes an argument and generates code that adds the result of evaluating that to the front of the list passed in as its second argument. After accum is expanded, the code will look like the following:

(defun alist-plist (alist)
  (let* ((#:head1460 (list nil))
         (#:tail1461 #:head1460))
    (macrolet ((a (#:arg1462)
                 `(setf #:tail1461
                        (setf (cdr #:tail1461)
                              (list ,#:arg1462)))))
      (dolist (pair alist)
        (a (car pair))
        (a (cdr pair)))
      (cdr #:head1460))))

As you should be able to see, a becomes a local macro which does what I described above.

I find accum to be one of many similar macros. Macros that abstract out a common pattern, and at the same time, are more efficient than what a human would normally write by hand. While many of these macros may be trivial, they both simplify code and make it faster!

1. It is important to preserve order since an alist/plist can have multiple keys that are the same, in which case the first one in the list is generally the desired key.
2. This implementation of accum uses nested backquotes. For an explanation as to how double backquotes are processed, see Appendix C of Common Lisp the Language