Common Lisp the Language, 2nd Edition

Next: Multiple Values Up: Control Structure Previous: The ``Program Feature''

# 7.9. Structure Traversal and Side Effects

X3J13 voted in January 1989 (MAPPING-DESTRUCTIVE-INTERACTION) 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:

    (let ((x '(apples peaches pumpkin pie)))
      (dolist (z x)
        (when (eq z 'peaches)
          (setf (cddr x) '(mango kumquat)))
        (format t " S " (car z))))

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

    apples peaches mango kumquat

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

    apples peaches pumpkin pie

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

    (defmacro dolist ((var listform &optional (resultform ''nil))
                      &body body)
      (let ((tailvar (gensym "DOLIST")))
        `(do ((,tailvar ,listform (cdr ,tailvar)))
             ((null ,tailvar) ,resultform)
           (let ((,var (car ,tailvar))) ,@body))

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

    (defmacro dolist ((var listform &optional (resultform ''nil))
                      &body body)
      (let ((tailvar (gensym "DOLIST")))
        `(do ((,tailvar ,listform))
             ((null ,tailvar) ,resultform)
           (let ((,var (pop ,tailvar))) ,@body))

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.

    Table 7-1: Structure Traversal Operations Subject to Side Effect Restrictions
    -----------------------------------------------------------------------------
    adjoin                   maphash                 reduce
    assoc                    mapl                    remove
    assoc-if                 maplist                 remove-duplicates
    assoc-if-not             member                  remove-if
    count                    member-if               remove-if-not
    count-if                 member-if-not           search
    count-if-not             merge                   set-difference
    delete                   mismatch                set-exclusive-or
    delete-duplicates        nintersection           some
    delete-if                notany                  sort
    delete-if-not            notevery                stable-sort
    do-all-symbols           nset-difference         sublis
    do-external-symbols      nset-exclusive-or       subsetp
    do-symbols               nsublis                 subst
    dolist                   nsubst                  subst-if
    eval                     nsubst-if               subst-if-not
    every                    nsubst-if-not           substitute
    find                     nsubstitute             substitute-if
    find-if                  nsubstitute-if          substitute-if-not
    find-if-not              nsubstitute-if-not      tree-equal
    intersection             nunion                  union
    certain loop clauses     position                with-hash-table-iterator
    map                      position-if             with-input-from-string
    mapc                     position-if-not         with-output-to-string
    mapcan                   rassoc                  with-package-iterator
    mapcar                   rassoc-if
    mapcon                   rassoc-if-not
    -----------------------------------------------------------------------------

Next: Multiple Values Up: Control Structure Previous: The ``Program Feature''