Combining Recycling with Shared Structure

Although you can use recycling functions whenever the arguments to the recycling function won’t be used after the function call, it’s worth noting that each recycling function is a loaded gun pointed footward: if you accidentally use a recycling function on an argument that is used later, you’re liable to lose some toes.

To make matters worse, shared structure and recycling functions tend to work at cross-purposes. Nondestructive list functions return lists that share structure under the assumption that cons cells are never modified, but recycling functions work by violating that assumption. Or, put another way, sharing structure is based on the premise that you don’t care exactly what cons cells make up a list while using recycling functions requires that you know exactly what cons cells are referenced from where.

In practice, recycling functions tend to be used in a few idiomatic ways. By far the most common recycling idiom is to build up a list to be returned from a function by “consing” onto the front of a list, usually by **PUSH**ing elements onto a list stored in a local variable and then returning the result of **NREVERSE**ing it.7

This is an efficient way to build a list because each **PUSH** has to create only one cons cell and modify a local variable and the **NREVERSE** just has to zip down the list reassigning the **CDR**s. Because the list is created entirely within the function, there’s no danger any code outside the function has a reference to any of its cons cells. Here’s a function that uses this idiom to build a list of the first n numbers, starting at zero:8

(defun upto (max)
  (let ((result nil))
    (dotimes (i max)
      (push i result))
    (nreverse result)))
(upto 10) ==> (0 1 2 3 4 5 6 7 8 9)

The next most common recycling idiom9 is to immediately reassign the value returned by the recycling function back to the place containing the potentially recycled value. For instance, you’ll often see expressions like the following, using **DELETE**, the recycling version of **REMOVE**:

(setf foo (delete nil foo))

This sets the value of foo to its old value except with all the **NIL**s removed. However, even this idiom must be used with some care—if foo shares structure with lists referenced elsewhere, using **DELETE** instead of **REMOVE** can destroy the structure of those other lists. For example, consider the two lists *list-2* and *list-3* from earlier that share their last two cons cells.

*list-2* ==> (0 4)
*list-3* ==> (1 2 0 4)

You can delete 4 from *list-3* like this:

(setf *list-3* (delete 4 *list-3*)) ==> (1 2 0)

However, **DELETE** will likely perform the necessary deletion by setting the **CDR** of the third cons cell to **NIL**, disconnecting the fourth cons cell, the one holding the 4, from the list. Because the third cons cell of *list-3* is also the first cons cell in *list-2*, the following modifies *list-2* as well:

*list-2* ==> (0)

If you had used **REMOVE** instead of **DELETE**, it would’ve built a list containing the values 1, 2, and 0, creating new cons cells as necessary rather than modifying any of the cons cells in *list-3*. In that case, *list-2* wouldn’t have been affected.

The **PUSH**/**NREVERSE** and **SETF**/**DELETE** idioms probably account for 80 percent of the uses of recycling functions. Other uses are possible but require keeping careful track of which functions return shared structure and which do not.

In general, when manipulating lists, it’s best to write your own code in a functional style—your functions should depend only on the contents of their list arguments and shouldn’t modify them. Following that rule will, of course, rule out using any destructive functions, recycling or otherwise. Once you have your code working, if profiling shows you need to optimize, you can replace nondestructive list operations with their recycling counterparts but only if you’re certain the argument lists aren’t referenced from anywhere else.

One last gotcha to watch out for is that the sorting functions **SORT**, **STABLE-SORT**, and **MERGE** mentioned in Chapter 11 are also recycling functions when applied to lists.10 However, these functions don’t have nondestructive counterparts, so if you need to sort a list without destroying it, you need to pass the sorting function a copy made with **COPY-LIST**. In either case you need to be sure to save the result of the sorting function because the original argument is likely to be in tatters. For instance:

CL-USER> (defparameter *list* (list 4 3 2 1))
*LIST*
CL-USER> (sort *list* #'<)
(1 2 3 4)                      ; looks good
CL-USER> *list*
(4)                            ; whoops!