7.9 Structure Traversal and Side Effects

X3J13 voted in January 1989 to restrict side effects during the course of a built-in operation that can execute user-supplied code while traversing a data structure.

Consider the following example:

Depending on the details of the implementation of dolist, this bit of code could easily print

(which is perhaps what was intended), but it might as easily print

Here is a plausible implementation of dolist that produces the first result:

But here is a plausible implementation of dolist that produces the second result:

The X3J13 recognizes and legitimizes varying implementation practices: in general it is an error for code executed during a “structure-traversing” operation to destructively modify the structure in a way that might affect the ongoing traversal operation. The committee identified in particular the following special cases.

For list traversal operations, the cdr chain may not be destructively modified.

For array traversal operations, the array may not be adjusted (see adjust-array) and its fill pointer, if any, may not be modified.

For hash table operations (such as with-hash-table-iterator and maphash), new entries may not be added or deleted, except that the very entry being processed by user code may be changed or deleted.

For package symbol operations (for example, with-package-iterator and do-symbols), new symbols may not be interned in, nor symbols uninterned from, the packages being traversed or any packages they use, except that the very symbol being processed by user code may be uninterned.

X3J13 noted that this vote is intended to clarify restrictions on the use of structure traversal operations that are not themselves inherently destructive; for example, it applies to map and dolist. Destructive operators such as delete require even more complicated restrictions and are addressed by a separate proposal.

The X3J13 vote did not specify a complete list of the operations to which these restrictions apply. Table 7.1 shows what I believe to be a complete list of operations that traverse structures and take user code as a body (in the case of macros) or as a functional argument (in the case of functions).

In addition, note that user code should not modify list structure that might be undergoing interpretation by the evaluator, whether explicitly invoked via eval or implicitly invoked, for example as in the case of a hook function (a defstruct print function, the value of *evalhook* or *applyhook*, etc.) that happens to be a closure of interpreted code. Similarly, defstruct print functions and other hooks should not perform side effects on data structures being printed or being processed by format, or on a string given to make-string-input-stream. You get the idea; be sensible.

Note that an operation such as mapcar or dolist traverses not only cdr pointers (in order to chase down the list) but also car pointers (in order to obtain the elements themselves). The restriction against modification appears to apply to all these pointers.