Panic, a strange behavior of lisp program

From: smartnose <smartn...@xxxxxxxxx>
I type program
(setq list1 '(4 5 3))
(setq list2 '(1))
(setq list1 (union list1 list2))
(setq list1 (sort list1 '<))
(I fixed the obvious typo where you had a space between list and 2.)

That's not legal Common Lisp, because the initial values of list1
and list2 are quoted constants which are *never* supposed to be
changed, and after calling UNION there is structure sharing between
that constant value of list2 and the return value, and after the
setq there's shared structure between the new value of list1 and
the constant value of list2, and then you try to do sort which is a
destructive operation which is not allowed for constant values.

I wish that all Lisp implementations would *enforce* constant
structures. For example, when the read-eval-print loop gets
(setq list2 '(1))
after it expands the reader macro to get
(setq list2 (quote (1)))
when is recursively evaluating that form, at the point where it is
ready to evaluate the sub-form (quote (1)), it should unpurify a
pure page, copy (1) to that page, re-purify it, discard the
original copy of (1) or let the GC deal with it later. Then later
when SORT is called with a parameter that includes some that (1)
structure on a pure page, and SORT tries to modify it, an exception
would be thrown something like:
Attempt to modify data on pure page,
specifically attempt to do RPLACD on constant value (1),
called from (sort list1 '<))
Then you'd know right there that your code was wrong.

Now there are two ways to fix *that* problem, one of which is to
"fix" it wrongly by satifying the literal spec but not fixing the
bug you reported:
(setq list1 (list 4 5 3))
(setq list2 (list 1))
(setq list1 (union list1 list2))
(setq list1 (sort list1 '<))
the other of which is to *really* fix the bug:
(setq list1 '(4 5 3))
(setq list2 '(1))
(setq list1 (union list1 list2))
(setq list1 (sort (copy-list list1) '<))

Referring back to the original non-CL code:
These code runs perfect,

Given that your original code wasn't valid CL in the first place,
it's impossible for it to run perfectly. At best one of two things
happened:
- You got an error that you were trying to modify read-only
(constant) data, which is what I said I wish would happen, but
no this isn't what happened to you;
- The CL implementation violated CL assumptions by modifying
constant data thereby postponing feedback to you that you had
done something wrong. That's what really happened. It's sorta
like you run a red light, and no cop stops you, so you think you
got by with it, then weeks later you get a ticket in the mail
saying that you are being fined $300 for breaking the law, as
proven by an automated camera. OK, I'm exaggerating a little,
but still I like the idea of getting an error the moment I try
to do something that isn't even valid Common Lisp, rather than
have the implementation do something illegal and I don't find
out until later.

but when I checked the value of list2. It's changed!

Yeah, because your implementation didn't respect the fact that a
quoted list is supposed to be ***constant***, not possible to be
changed by subsequent program operations such as your call to SORT.

(print list2)
5

Now *that* really doesn't make sense. If the implementation
performs SORT by doing RPLACD to re-link cells, then I would expect
that the value of list2 might be (1 3 4 5) now. Or if the
implementation performs SORT by doing RPLACA to replace single
elements while keeping the chain of CONS cells unchanged, then I
would expect the value of list2 might be (5). Are you sure the
latter isn't what you meant, like you omitted the parens around 5
when posting?

It seems that common lisp merge the memories of list1 and list2.

Yes. UNION is allowed to share list structure with either/both of
the original lists if it means less CONSing. What it's *not*
allowed to do is modify either (to avoid all CONSing whatsoever)
use NUNION if you want that.

Is this what lisp are supposed to do? Shouldn't it return a new
list instead?

If you're asking about UNION, read the spec where it clearly says
that sharing of structure is possible. No actually although CLtL
clearly says that, the CL HyperSpec doesn't say that, it only says
that the result may be EQ to either of the parameters, it doesn't
say that any other sharing may be possible. Kent, please comment on
this apparent mistake in conversion from CLtL to ANSI-CL. Did I
mis-read the HyperSpec, or was a mistake made between ANSI-CL and
CLHS, or was a mistake made between CLtL and ANSI-CL, or did I
mis-read CLtL? If the mistake is from CLtL to ANSI-CL, is there a
Web page that lists all such "obvious" mistakes. In your opinion,
should CL implementations conform to strict ANSI-CL in cases like
this, thereby going along with that error, or should CL
implemetations revert to obeying CLtL specification, thereby
avoiding the mistake?

I'm confused.

And your implementation of CL, which failed to signal an error when
you destructively modified some constant structure by calling SORT
on a shared structure, helped to confuse you.
.

Relevant Pages

  • RE: Incident investigation methodologies
    ... However, what sort of reaction ... Speculation gets you nowhere. ... > malware we encounter. ... > of what makes public lists useful - you can get some ...
    (Incidents)
  • Re: Detailed explanation of how a QuickSort Works
    ... Firstly, if you consider the simple "Bubble Sort" algorithm, it works by running through the entire data set, one item at a time, comparing each item to the previous item and swapping them if they are not already in the correct order. ... by simply running through the entire list just once (and splitting it into two smaller lists) you have cut the sorting time in half. ...
    (microsoft.public.vb.general.discussion)
  • Re: Ordering Products
    ... algorithms. ... lists with constrained item transpositions. ... I think while the built in sort works as a convenience, ... Overall it's about 10 times slower than pythons built in sort for large ...
    (comp.lang.python)
  • Re: Ordering Products
    ... > Kay Schluehr wrote: ... >> It would be interesting to examine some sorting algorithms on factor ... >> lists with constrained item transpositions. ... > I think while the built in sort works as a convenience, ...
    (comp.lang.python)
  • Re: Audiocd missing from KDE 3.5.3?
    ... Did this get left out of kdemultimedia by mistake ... looking in the kde.org bug lists. ... It is something with the spec as I managed to compile it just ...
    (Fedora)