Efficiently Building Lists

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: 1

(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 accum2, a macro which makes accumulating elements easy and efficient.

(defmacro accum (accfn &body body)
  (let ((ghead (gensym "HEAD"))
        (gtail (gensym "TAIL"))
        (garg  (gensym "ARG")))
    `(let* ((,ghead (list nil))
            (,gtail ,ghead))
       (macrolet ((,accfn (,garg)
                    `(setf ,',gtail
                           (setf (cdr ,',gtail)
                                 (list ,,garg)))))
         (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!

The Ret Macro

The ret macro is simple, but useful. It allows you to bind a variable and simultaneously specify the final value of that variable as the result of the ret expression, hence the name “ret”, a blend of let and return. Here is the implementation of ret:

(defmacro ret (var val &body body)
  `(let ((,var ,val))

And now for an example. If you want to write a function that converts a hash-table into an alist, here is how you could do that using ret.

(defun table->alist (table)
  (ret result '()
    (maphash (lambda (k v)
               (push (cons k v) result))

Personally, I find code using ret to be much clearer than the equivalent code using let. When writing the let version, I commonly find myself forgetting to return the value I want to at the end. Ret eliminates this problem by returning the result for me. The only downside I see to using ret is that it has the same problem as all of the “do” macros (dotimes, dolist, etc), they change where the resulting value comes from. Even so, this problem is much more mild with ret because ret will always change the control flow, whereas the “do” macros may or may not change the final value depending on the number of arguments passed to them.