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

Postby enderw88@gmail.com » 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?.
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?!?

Postby 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.
User avatar
nuntius
 
Posts: 500
Joined: Sat Aug 09, 2008 10:44 am
Location: Burlington, MA

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

Postby enderw88@gmail.com » Mon Feb 20, 2012 7:51 pm

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

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

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

Postby enderw88@gmail.com » 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.
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?!?

Postby Ramarren » Tue Feb 21, 2012 10:03 am

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


Return to Common Lisp

Who is online

Users browsing this forum: No registered users and 3 guests

cron