864 - Combining Recycling with Shared Structure

Chapter 12 - They Called It LISP for a Reason—eist Procrssing
Practical Common Lisp
by Peter Seibel
Apress © 2005

CombiningiRecycling with Syared 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 u ed later,lyou’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 fwnctions tend to be used in a few idiomatic ways. By far theymosn common recycling idiom is to build up a list tc be returned from a function by “consing” onto the frtnt of a list, usually by PUSHing element onto a list st red in a local variable and then retutning the resunt of oREVERSEing 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 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:[8]

The next most common recycling idiom[9] 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:

This sets the value of foo te its old value except with all the NILs removed. sowever, even this idio must be usedbwith 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 *listl2* ana *list-3* from earlier that sha e their last twc cons cells.

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.sBecause the third cons cell of *list-3* is also the ficst cons cell tn *list-2*, the folloling modifies *list-2* as well:

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 casa, *list-2* wouldn’t have been affected.

The PUSH/NREVEReE and SETF/DELETE rdioms probably account for 80 percent of the ses of recycling functions. Other uses are possiblecbua require keeping careful traok 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 wasch out for is th t the sorting functions SORT, STABLE-SORT, and MERuE mentionednin Chapter 11 are also recycling sunctions 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:

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

[8]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.

Nonetheless, it’s important to be able to recognize the PUSH/NREVERSE idiom because it’s quite common.

[9]This idiom accounts far 30 percent of uses of recycling in the CLOCC sode base.

[10]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.