LIST vs TICK in a LET causing a global side-effect?!?

I am writing some numerical routines and trying to observe a strict functional approach. Today I got bitten by a bug I can't explain with my understanding of how LET, LIST and QUOTE work.

I had the following code (significantly simplified to show the bug without cluttering up with the actual purpose of the code)

(defun digit-magic ()
  (let ((dig-list '(1 2 3 4 5 6 7 8 9))
	(i 0))
    (remove-if #'null
	       (loop until (or (> i 100000) (null dig-list)) do
		      (if (zerop (mod i 10000))
			  (progn (format t "~d: ~a~%" i dig-list)
				 (force-output)))
		      (setf i (1+ i))
		      (setf dig-list (next-permutation dig-list))))))

It would run as I expected the first time invoked after compilation (SBCL 1.0.55):

CPE-PROJECT> (digit-magic)
0: (1 2 3 4 5 6 7 8 9)
10000: (1 3 9 8 4 6 7 2 5)
20000: (1 5 9 7 6 3 4 2 8)
30000: (1 7 9 6 2 3 4 5 8)
40000: (1 9 8 5 3 6 7 2 4)
50000: (2 3 9 5 7 4 6 1 8)
60000: (2 5 9 4 1 3 6 7 8)
70000: (2 7 9 3 4 6 8 1 5)
80000: (2 9 8 1 6 4 5 3 7)
90000: (3 2 9 1 4 5 6 7 8)
100000: (3 5 8 9 2 6 7 1 4)
NIL

Any further invocations would not however run properly:

EULER-PROJECT> (digit-magic)
0: (1 2 3 4 5 6 7 9 9 8 6 9 9 8 6 9 9 7 6 8 8 7 5 7 9 9 8 5 9 9 8 5 9 9 7
    5 8 8 7 5 6 9 9 8 5 9 9 8 5 9 9 6 5 8 8 6 5 6 9 9 7 5 9 9 7 5 9 9 6 5
    7 7 6 5 6 8 8 7 5 8 8 7 5 8 8 6 5 7 7 6 4 6 7 9 9 8 6 9 9 8 6 9 9 7 6
    8 8 7 4 7 9 9 8 4 9 9 8 4 9 9 7 4 8 8 7 4 6 9 9 8 4 9 9 8 4 9 9 6 4 8
    8 6 4 6 9 9 7 4 9 9 7 4 9 9 6 4 7 7 6 4 6 8 8 7 4 8 8 7 4 8 8 6 4 7 7
    6 4 5 7 9 9 8 5 9 9 8 5 9 9 7 5 8 8 7 4 7 9 9 8 4 9 9 8 4 9 9 7 4 8 8
    7 4 5 9 9 8 4 9 9 8 4 9 9 5 4 8 8 5 4 5 9 9 7 4 9 9 7 4 9 9 5 4 7 7 5
    4 5 8 8 7 4 8 8 7 4 8 8 5 4 7 7 5 4 .....lots more data

When I changed the LET form to

(let ((dig-list (list 1 2 3 4 5 6 7 8 9))

The problem went away. Can someone explain to me how I am getting crosstalk between two separate invocations of the same function through a locally defined variable? I have verified that my (next-permutation) function is non-destructive, but even if it were how does the LET '(1 2 3 4... not reinitialize the same every time?.

Basically, '(1 2 3) returns a list literal (not evaluated because of QUOTE), while (list 1 2 3) returns a function that will be executed at run-time.

Modifying any literal will result in undefined behavior. Lots of possibilities: may persist, may not persist, may fail since the literal is in read-only memory, etc.

Thanks, so as a general rule should I avoid using TICK for data initialization?

To fully understand this you must remember how Common Lisp is processed. The first step is the reading phase, which transforms the text source into a tree of objects. Those objects are first-class language objects, which is how macros work, by operating on that object tree before the evaluation/compilation. Some of this objects can be directly handed over to the run-time by using QUOTE. Also self-evaluating objects, like vectors. They still remain parts of the source object tree, and if you modify them then all future invocations of the code within the image will be affected in an undefined way.

Simplifying what Ramarren said, if you want to be able to modify the data, don't use TICK or QUOTE, and don't use array notation like #a(1 2 3). In those cases, construct the data with the appropriate functions, like LIST, VECTOR or MAKE-ARRAY.

Ramarren wrote:To fully understand this you must remember how Common Lisp is processed. The first step is the reading phase, which transforms the text source into a tree of objects. Those objects are first-class language objects, which is how macros work, by operating on that object tree before the evaluation/compilation. Some of this objects can be directly handed over to the run-time by using QUOTE. Also self-evaluating objects, like vectors. They still remain parts of the source object tree, and if you modify them then all future invocations of the code within the image will be affected in an undefined way.

That was the key. Thank you. I can't decide if this is to be avoided or exploited...(feature or bug). Certainly for what I was doing it was bad.

[email protected] wrote: That was the key. Thank you. I can't decide if this is to be avoided or exploited...(feature or bug). Certainly for what I was doing it was bad.

The "in undefined way" is important. Since the standard specifies the undefinedness explicitly, the implementation is allowed, but not required, to make an assumption that the source object tree (which can be actually a graph) is immutable, and perform optimizations on it, like coalescing constants, which would make any attempt to exploit it unpredictable, since the behaviour would depend not only on an implementation, but optimization settings and mode of compilation. It can even cause memory access violation if the source object tree has been marked as read only after it has been read.