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

Discussion of Common Lisp

### 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)
Code: Select all
`(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):
Code: Select all
`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:

Code: Select all
`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
Code: Select all
`(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?.
enderw88@gmail.com

Posts: 20
Joined: Sun Nov 28, 2010 10:34 pm

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

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.

nuntius

Posts: 498
Joined: Sat Aug 09, 2008 10:44 am
Location: Burlington, MA

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

Thanks, so as a general rule should I avoid using TICK for data initialization?
enderw88@gmail.com

Posts: 20
Joined: Sun Nov 28, 2010 10:34 pm

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

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.
Ramarren

Posts: 613
Joined: Sun Jun 29, 2008 4:02 am
Location: Warsaw, Poland

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

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.
gugamilare

Posts: 406
Joined: Sat Mar 07, 2009 6:17 pm
Location: Brazil

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

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.
enderw88@gmail.com

Posts: 20
Joined: Sun Nov 28, 2010 10:34 pm

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

enderw88@gmail.com 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.
Ramarren

Posts: 613
Joined: Sun Jun 29, 2008 4:02 am
Location: Warsaw, Poland