Jan> Jan Vroonhof <vroonhof(a)math.ethz.ch&gt; writes: Jan> Here is an easier one Jan> (let ((lijst '(a b c))) Jan> (mapcar Jan> (lambda (x) Jan> ;; Make list shorter behind mapcar's back Jan> (delete 'c lijst)) Jan> lijst)) This Cltl2 fragment implies this user code is NOT sensible. -------------------------------------------------------------------------------- 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 ----------------------------------------------------------------------------- Jan> The problem is this code in in mapcar1 Jan> if (LISTP (seq)) Jan> { Jan> for (i = 0; i < leni; i++) Jan> { Jan> args[1] = XCAR (seq); Jan> seq = XCDR (seq); Jan> result = Ffuncall (2, args); Jan> if (vals) vals[gcpro1.nvars++] = result; Jan> } Jan> } Jan> It blindingly believes that XCDR(seq) will always be a cons cell, Jan> although it calls user code which could have modified the list it is Jan> iterating over. But we still shouldn't crash. I will take care of this bug. Jan> P.S. What should this do? Jan> (let ((lijst '(1 2 3)) Jan> (addme '(4 5 6))) Jan> (mapcar (lambda (x) Jan> ;; Make list longer behing mapcar's back Jan> (nconc lijst addme) Jan> (setq addme nil) Jan> x) Jan> lijst)) Anything we want, including inflooping, as long as we don't crash.

Jan Vroonhof writes: Here's a patch that fixes this. Recommended for 21.1 and 21.2. 1999-12-16 Kyle Jones <kyle_jones(a)wonderworks.com&gt; * fns.c (mapcar1): when iterating over a list, check for CONSP each iteration because bad user code might have modified the list. Call Fcdr/Fcar if CONSP check fails so that malformed lists cause an error to be signaled instead of crashing. --- src/fns.c 1999/10/24 03:48:39 1.30.2.23 +++ src/fns.c 1999/12/17 04:13:14 ＠＠ -3070,8 +3070,19 ＠＠ { for (i = 0; i < leni; i++) { - args[1] = XCAR (seq); - seq = XCDR (seq); + /* Use XCAR/XCDR to avoid function call overhead if we can. + Otherwise call Fcar and Fcdr to get exceptions signaled + if the Lisp code mangles the list. */ + if (CONSP (seq)) + { + args[1] = XCAR (seq); + seq = XCDR (seq); + } + else + { + args[1] = Fcar (seq); + seq = Fcdr (seq); + } result = Ffuncall (2, args); if (vals) vals[gcpro1.nvars++] = result; }