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

Discussion of Common Lisp
Post Reply
[email protected]
Posts: 20
Joined: Sun Nov 28, 2010 10:34 pm

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

Post by [email protected] » Mon Feb 20, 2012 4:58 pm

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

nuntius
Posts: 538
Joined: Sat Aug 09, 2008 10:44 am
Location: Newton, MA

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

Post by nuntius » Mon Feb 20, 2012 6:30 pm

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.

[email protected]
Posts: 20
Joined: Sun Nov 28, 2010 10:34 pm

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

Post by [email protected] » Mon Feb 20, 2012 7:51 pm

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

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

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

Post by ramarren » Mon Feb 20, 2012 11:57 pm

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.

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

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

Post by gugamilare » Tue Feb 21, 2012 9:54 am

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.

[email protected]
Posts: 20
Joined: Sun Nov 28, 2010 10:34 pm

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

Post by [email protected] » Tue Feb 21, 2012 9:55 am

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.

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

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

Post by ramarren » Tue Feb 21, 2012 10:03 am

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

Post Reply