Книга: Practical Common Lisp

Combining Recycling with Shared Structure

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 PUSHing elements onto a list stored in a local variable and then returning the result of NREVERSEing it.[137]

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 CDRs. 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]

(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] 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 NILs 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.[140] 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!

Оглавление книги