One big difference between Lisp and most other programming languages is its use of recursion instead of iteration.

So while I was working on some text-parsing code, I fell in to this simple pattern:

(defun process (list)
  (if list
      (cons (do-something (first list))
	    (process (rest list)))))

Ah, the joys of Lisp-2.

If do-something were actually a function, this example would be better written:

(mapcar #'do-something list)

But the CL Hyperspec explicitly states, “For list traversal operations, the cdr chain of the list is not allowed to be destructively modified.” Stepping through the list myself means I can modify its structure along the way. I can insert new CONS cells into the list, or even rebind list to something else. This makes it easy to convert a flat list like this:

• Heading 1
• Paragraph
• Paragraph
• Heading 2
• Paragraph
• Paragraph

Into a structured tree like this:

• Heading 1
  • Paragraph
  • Paragraph
• Heading 2
  • Paragraph
  • Paragraph

Here I encounter the Lisper’s Dilemma: to CONS or not to CONS. Articles and books about Lisp frequently say “CONS is expensive, avoid it where possible.” The pattern above does a lot of CONSing, effectively rebuilding its input. But when I tried to modify my code to use destructive list operations like rplaca and nconc I quickly ran into problems. Destructive operations are tricky at the best of times. Using them while experimenting with new code is just plain asking for trouble. The CONSing code I ended up with was plenty fast enough for my purposes.

I think the constant repetition of “CONS is expensive” is disingenuous for Lisp, especially when it comes to teaching new programmers about its advantages. Yes, CONS is computationally inefficient, but its benefits in readability and maintainability make it is very programmer-efficient.