Peter Siebel - Practical Common Lisp

(defparameter *x* (list 1 2 3))

(nconc *x* (list 4 5 6)) ==> (1 2 3 4 5 6)

*x* ==> (1 2 3 4 5 6)

NSUBSTITUTE and variants can be relied on to walk down the list structure of the list argument and to SETF the CAR s of any cons cells holding the old value to the new value and to otherwise leave the list intact. It then returns the original list, which now has the same value as would've been computed by SUBSTITUTE . [136] The string functions NSTRING-CAPITALIZE , NSTRING-DOWNCASE , and NSTRING-UPCASE are similar—they return the same results as their N-less counterparts but are specified to modify their string argument in place.

The key thing to remember about NCONC and NSUBSTITUTE is that they're the exceptions to the rule that you can't rely on the side effects of recycling functions. It's perfectly acceptable—and arguably good style—to ignore the reliability of their side effects and use them, like any other recycling function, only for the value they return.

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. [137] For example, in an examination of all uses of recycling functions in the Common Lisp Open Code Collection (CLOCC), a diverse set of libraries written by various authors, instances of the PUSH / NREVERSE idiom accounted for nearly half of all uses of recycling functions.

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: [138] There are, of course, other ways to do this same thing. The extended LOOP macro, for instance, makes it particularly easy and likely generates code that's even more efficient than the PUSH / NREVERSE version.

(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 idiom [139] This idiom accounts for 30 percent of uses of recycling in the CLOCC code base. 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 footo its old value except with all the NIL s removed. However, even this idiom must be used with some care—if fooshares 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 4from *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. [140] SORT and STABLE-SORT can be used as for-side-effect operations on vectors, but since they still return the sorted vector, you should ignore that fact and use them for return values for the sake of consistency. 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*