Hi all,
I've come to appreciate that this binding:
(let* ((x (list 1 2 3))
(y x))
...)
Produces this structure of cons cells:
x <- [ 1 | -]-->[ 2 | -]-->[3 | . ]
^
|
y <- [ 1 | -]-----+
This structure must be understood when performing destructive modification
and the shared structure must be the same in all implementations for them
to return the same results, e.g.:
(let* ((x (list 1 2 3))
(y x))
(setf (second x) 7)
(format t "X=~A; Y=~A." x y)) => X=(1 7 3); Y=(1 7 3).
What part of the HyperSpec specifies that Y must share the CDR of X
instead of (a) simply being a pointer to X or (b) not sharing any
structure of X (there is an implicit (copy-list x))?
Thanks,
Adam
Adam Warner <······@consulting.net.nz> writes:
> Hi all,
>
> I've come to appreciate that this binding:
>
> (let* ((x (list 1 2 3))
> (y x))
> ...)
>
> Produces this structure of cons cells:
>
> x <- [ 1 | -]-->[ 2 | -]-->[3 | . ]
> ^
> |
> y <- [ 1 | -]-----+
Why do you think that? To the extent my Lisp implementation is
conformant, this demonstrates that that's not what happens:
CL-USER(35): (let* ((x (list 1 2 3))
(y x))
(eq x y))
T
> This structure must be understood when performing destructive
> modification and the shared structure must be the same in all
> implementations for them to return the same results, e.g.:
>
> (let* ((x (list 1 2 3))
> (y x))
> (setf (second x) 7)
> (format t "X=~A; Y=~A." x y)) => X=(1 7 3); Y=(1 7 3).
>
> What part of the HyperSpec specifies that Y must share the CDR of X
> instead of (a) simply being a pointer to X or (b) not sharing any
> structure of X (there is an implicit (copy-list x))?
None. X and Y are both references to the same cons cell, namely the
cons cell created by the call to LIST that contains 1 as its CAR and
the rest of the list as its CDR.
-Peter
--
Peter Seibel ·····@javamonkey.com
Lisp is the red pill. -- John Fraser, comp.lang.lisp
Hi Peter Seibel,
>> Hi all,
>>
>> I've come to appreciate that this binding:
>>
>> (let* ((x (list 1 2 3))
>> (y x))
>> ...)
>>
>> Produces this structure of cons cells:
>>
>> x <- [ 1 | -]-->[ 2 | -]-->[3 | . ]
>> ^
>> |
>> y <- [ 1 | -]-----+
>
> Why do you think that?
The misunderstanding arose out of DOLIST and not modifying the CDR of the
list being traversed over, plus the silly idea that since one can SETF X
without changing Y that at least the first cons cell must be copied (of
course Y doesn't change because the pointer to X is replaced without
disturbing the original structure).
Had I (setf (first x) 7) minutes before I would have avoided this very
public mistake :-)
> None. X and Y are both references to the same cons cell, namely the
> cons cell created by the call to LIST that contains 1 as its CAR and
> the rest of the list as its CDR.
Many thanks Peter.
Regards,
Adam
Adam Warner <······@consulting.net.nz> writes:
>
> Hi all,
>
> I've come to appreciate that this binding:
>
> (let* ((x (list 1 2 3))
> (y x))
> ...)
>
> Produces this structure of cons cells:
>
> x <- [ 1 | -]-->[ 2 | -]-->[3 | . ]
> ^
> |
> y <- [ 1 | -]-----+
Not quite the correct picture. The correct picture would have x and y
both bound to exactly the same cons cells. Y does not get its own
leading cons cell:
x <-- [ 1 | -]-->[ 2 | -]-->[3 | . ]
|
y <---+
If you set (first x) you will also affect (first y)
> What part of the HyperSpec specifies that Y must share the CDR of X
> instead of (a) simply being a pointer to X
Y can't be a pointer to X, since X is a symbol. You would get a pointer
to X by binding Y to 'X instead. Y must be bound to the value of X. It
doesn't just share the CDR, but the entire list that X is bound to.
That is why (eq x y) => T.
I'm not quite sure where in the Spec such behavior is nailed down. I
would suspect it is really a consequence of the object identity and
binding semantics in the specification.
> or (b) not sharing any
> structure of X (there is an implicit (copy-list x))?
Because the Spec doesn't say there is a copy-list. In fact it probably
does require that (eql x y), which for lists implies (eq x y). With a
copy-list operation x and y would not be eq (unless they were NIL).
--
Thomas A. Russ, USC/Information Sciences Institute
Hi Thomas A. Russ,
>> What part of the HyperSpec specifies that Y must share the CDR of X
>> instead of (a) simply being a pointer to X
>
> Y can't be a pointer to X, since X is a symbol. You would get a pointer
> to X by binding Y to 'X instead. Y must be bound to the value of X. It
> doesn't just share the CDR, but the entire list that X is bound to.
> That is why (eq x y) => T.
>
> I'm not quite sure where in the Spec such behavior is nailed down. I
> would suspect it is really a consequence of the object identity and
> binding semantics in the specification.
>
>> or (b) not sharing any
>> structure of X (there is an implicit (copy-list x))?
>
> Because the Spec doesn't say there is a copy-list. In fact it probably
> does require that (eql x y), which for lists implies (eq x y). With a
> copy-list operation x and y would not be eq (unless they were NIL).
Thanks Thomas. My gaff also helped me to appreciate:
(a) Do not confuse assignment and destructive modification. Assignment
replaces a value with a new value. Destructive modification alters the
internal structure of a value.
My concerns began from this code:
(let ((x '(1 2 3)))
(dolist (e x)
(print e)
(setf x (cdr x))))
I was concerned I could be destructively modifying X which could change
the iteration over the list in undefined ways. In fact only the value that
X points to is changed (I am just pointing to different entry points
within a static data structure). The data structure DOLIST iterates over
remains completely unmolested.
(b) Common Lisp's identity abstraction is consistent because characters
and numbers, which can be copied at any time, are also immutable. If there
was a way to destructively modify a character or number then this
abstraction would break down. The corollary is that identity could be
abstractly preserved for lists even if they were copied at any time so
long as they were immutable. Being immutable it would not be possible to
destructively modify a list and break the abstraction.
The identity abstraction EQL allows us to consistently believe for (let*
((x 3) (y x)) ...) that:
x <- 3
|
y <--+
Even though there may be no link between the values of X and Y:
x <- 3
y <- 3
If there was a way to destructively modify the 3 then the abstraction
would be broken as Y will not return the destructively modified value of X
in the second implementation. But since X can only be assigned or bound to
a new value it's impossible to break the abstraction, e.g.:
Implem. 1: (setf x 4) Implem. 2: (setf x 4)
x <- 3 x <- 4 3 x <- 3 x <- 4
| => | =>
y <--+ y <-----+ y <- 3 y <- 3
[EQ does let us detect when the identity abstraction diverges from
machine level identity which is why it's a low level operation and not the
default equality (identity) predicate in Common Lisp]
Regards,
Adam