Odd Sort Behavior

[Neigel]

I recently wrote a cryptarithmetic solver for a school project and have been tweaking it to try to improve it for fun. In the program, it takes the two operands and sum as lists, and creates a fourth list of unique variables in the problem. For example, from the problem EAT + THAT = APPLE, it creates the list (A H T P L E). It then assigns domains for each variable of 0-9 and trims the domains based some simple rules (such A in this case must equal 1). The program then sorts the domains by length, shortest-first, so that the most-restricted-value is leading when it sttarts to look for the answer.

Everything works, which I was happy for. I am new to lisp and it has been fun learning how to use it.

Now for the caveat. It works when I run it on Allegro CL, but does not on GNU CLisp. I have tracked down the problem to the sort function. When I sort the list of variables, it changes (A H T P L E) to (A T E H P L) as it should, but it is also changing the value of the list of variables for the sum. That is, it also changes the list (A P P L E) to (A P H P L).

I find this very odd. The sort function is not touching the sum list in any way I can tell. As I mentioned, this happens with GNU CLisp, but not with Allegro. I would prefer to use GNU as it runs leaps and bounds faster on my machine, but this oddness is throwing me off.

[nuntius]

Two things.

SORT "destructively sorts" the sequence and returns the sorted sequence.
In reality, some systems do a destructive sort and others don't -- in all cases, you really need to do something like (setf x (sort x #'string<)).
If you don't want the original list to be destroyed, you can do something like (setf x (sort (copy-seq x) #'string<)).

Second, I'm not an Allegro user, but it should run at least as fast as Clisp. Allegro probably takes a longer time to start up, and you may have to compile the code to get speed, but it should be faster in the right conditions. Clisp generally isn't the fastest implementation, but its fast startup and quick bytecode interpreter make it a good choice for small command-line scripts.

[Neigel]

I understand that Sort is destructive, and I have no issue with that. My issue is that I have two separate lists in the program, say list1 and list2. And when I call (setf list2 (sort list2 #'string)), in addition to sorting list2, I find that the contents of list1 have changed. This seems very odd to me. And this does not occur in Allegro, only Clisp.

[nuntius]

Consider the following code.

Code: Select all

(defparameter *l1* (list 1 2 3 4 5))
(defparameter *l2* (list 1 2 3 4 5))
(defparameter *l3* *l1*)
(setf *l1* (sort *l1* #'>))

After the sort, the state of *l2* is unchanged and the state of *l3* is undefined (could be the original list, could be the sorted list, could be garbage).

At the time of the sort operation, *l1* and *l3* are to references to the same structure -- sort is destroying the structure, not the variable.

Is this what you are seeing?

[edgar-rft]

CLISP 2.48 (yes I know it's obsolete) tells me:

Code: Select all

[1]> (defparameter list1 (list 'a 'p 'p 'l 'e))
LIST1
[2]> (defparameter list2 (list 'a 'h 't 'p 'l 'e))
LIST2
[3]> (setf list2 (sort list2 #'string<))
(A E H L P T)
[4]> list1
(A P P L E)
[5]> list2
(A E H L P T)

This means that the problem must be that your lists share elements. Probably this is caused be the code that constructs the lists. Could you please tell or post the code how you construct these lists?

Example what happens if list1 and list2 share elements:

Code: Select all

[6]> list1
(A P P L E)
[7]> (setf list2 (append (list 'a 'h 't) (cddr list1)))
LIST2
[8]> list2
(A H T P L E)
[9]> (setf list2 (sort list2 #'string<))
(A E H L P T)
[10]> list1
(A P L P T)
[11]> list2
(A E H L P T)

This is exactly the effect you describe. Sorting list2 modifies list1 because both lists share the tail (cddr list1) => (P L E). If you modify one of these three elements in one of both lists, then the other list will be modified, too. This is normal Lisp behaviour.

- edgar