Pushing to Lists

Fiddling with some Common Lisp code a few weeks ago, I needed to push items onto the end of a list. After thinking for a moment, I wrote this:

(defun push-end (object place)
  (nconc place (list object))

Since I was fiddling in LispWorks at the time, I discovered that LispWorks already defines its own push-end as a macro which works like this:

CL-USER> (macroexpand '(push-end object place))
(LET* ((#:ITEM563 OBJECT))
  (LET* ((#:NEW-VALUE562 (APPEND PLACE (LIST #:ITEM563))))
    (SETQ PLACE #:NEW-VALUE562)))

Leaving aside the peculiar nested let* and gensyms, this is still very different. Redefining my function as my-push-end, here are the differences:

Both destructively modify their second argument:

(defvar *x* '(a b c))

(push-end 'd *x*)  -->  (A B C D)
*x*  -->  (A B C D)

(my-push-end 'e *x*)  -->  (A B C D E)
*x*  -->  (A B C D E)

My version also works on quoted lists, but LispWorks’ version does not:

(my-push-end 'd '(a b c))  -->  (A B C D)

(push-end 'd '(a b c))
  -->  Error: Couldn't find a setf expansion for (QUOTE (A B C)).

But LispWorks’ version correctly handles temporary bindings, whereas mine does not:

(let ((temp-x *x*))
  (push-end 'f temp-x))  -->  (A B C D E F)
*x*  -->  (A B C D E)

(let ((temp-x *x*))
  (my-push-end 'f temp-x))  -->  (A B C D E F)
*x*  -->  (A B C D E F)

This explains why push is implemented using setf instead of nconc, and why LispWorks’ push-end is implemented the same way. The only way to ensure that these macros handle temporary variables correctly is to operate only on bindings and not touch their list values directly.

Of course, operating directly on lists with nconc is slightly more efficient, so in situations without global variables it might be preferable. However, in complex code, subtle bugs might emerge from modifying lists. A good compiler should optimize away the extra assignments in the push-end macro when they aren’t needed. In LispWorks, I ran:

(disassemble #'my-push-end)  -->  16 lines of assembler

;; must wrap the macro in a lambda to disassemble:
(disassemble #'(lambda (obj place) (push-end obj place)))
  -->  20 lines of assembler

So my function requires four fewer assembly instructions than LispWorks’ macro. Perhaps in some extremely list-intensive code that would make a difference, but for anything else I’d go with the slightly safer macro.

2 thoughts on “Pushing to Lists”

  1. The result of destructively modifying literal data like ‘(A B C) is undefined. Don’t do it.

    In most of the cases when you think you need to push something on the end of a list, you actually don’t; PUSH+NREVERSE is often more suitable. When you really do need to push things on the end of a list, keeping a pointer to the tail of the list is handy.

    Counting instructions to see how you’re doing is a little premature at this point.

  2. Zach B.: “Counting instructions to see how you’re doing is a little premature at this point.”

    Definitely premature, but fun nonetheless. :)

Comments are closed.