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’’

AI.Repository@cs.cmu.edu