From: Tim Groner
Subject: simple programming problem
Date: 
Message-ID: <umgroner.877486706@castor>
I have two "lists" in a let statement, one is a copy
of the other and I want to change the the car of the
first list to a different value.  But when I do this,
the car of the second list changes to the new value
as well.  How do I keep the copy of the first list 
from being changed? (seems to me like the way I'm doing
it, the second list isn't a copy and mearly shares
a pointer...

Here's what I've got:


(let ((x '(1 2 3)) (y))
   (setq y x)
   (setf (car y) 100)
   (append (list x) (list y)))

((100 2 3) (100 2 3))
-- 
To reply, remove '.s.p.a.m.THIS' from my e-mail address

Tim Groner
http://home.cc.umanitoba.ca/~umgroner

From: Kent M Pitman
Subject: Re: simple programming problem
Date: 
Message-ID: <sfwwwj52k68.fsf@world.std.com>
Tim Groner <········@cc.s.p.a.m.THIS.umanitoba.ca> writes:

> I have two "lists" in a let statement, one is a copy
> of the other

Not the way you wrote the code.  When you do
 (setq y x)
you end up with both y and x pointing to the same list.
You may want something like
 (setq y (copy-list x))
if you want the list's backbone to be copied (individual
elements will still not be copied).

Assignments in Lisp, and argument passing, are done by just
moving pointers around.  No structure is copied as would be
in languages like Pascal and C.

Incidentally, you should NEVER side-effect a piece of constant
structure.  Doing:

 (let ((x '(1 2 3)))
   (setf (car x) 100))

is a no-no.  In some implementations, you might get an error
because you end up modifying a read-only memory page.  In other
implementations, you may end up destroying a shared constant.
For example, if you write:

 (defun foo () '(1 2 3))
 (defun bar () '(1 2 3))

the implementation is allowed to share these pointers because 
you are required to never side-effect constant structure.  If
you do (setf (car (foo)) 4), it could happen that (bar)
later returns (4 2 3) not because Lisp is supposed to share these,
but because it is allowed to, and because you have broken your
contract with the implementation.
From: ·····@orsi.com
Subject: Re: simple programming problem
Date: 
Message-ID: <877722714.18881@dejanews.com>
In article <···············@world.std.com>,
  ······@world.std.com (Kent M Pitman) wrote:
>
> Tim Groner <········@cc.s.p.a.m.THIS.umanitoba.ca> writes:
>
> > I have two "lists" in a let statement, one is a copy
> > of the other
>
> Not the way you wrote the code.  When you do
>  (setq y x)
> you end up with both y and x pointing to the same list.
> You may want something like
>  (setq y (copy-list x))
> if you want the list's backbone to be copied (individual
> elements will still not be copied).
>
> Assignments in Lisp, and argument passing, are done by just
> moving pointers around.  No structure is copied as would be
> in languages like Pascal and C.
>
> Incidentally, you should NEVER side-effect a piece of constant
> structure.  Doing:
>
>  (let ((x '(1 2 3)))
>    (setf (car x) 100))

Is (let ((x (list 1 2 3)))
     (setf (car x) 100))
OK?

I'm not sure what constitutes "constant structure".  The folks at Franz
have warned me about this, and I have observed from experience that the
(list...) form does not create constant structure (although it is a list
of constants).

> [rest snipped, possibly unwisely??]

-------------------==== Posted via Deja News ====-----------------------
      http://www.dejanews.com/     Search, Read, Post to Usenet
From: Kent M Pitman
Subject: Re: simple programming problem
Date: 
Message-ID: <sfw90viu4d5.fsf@world.std.com>
·····@orsi.com writes:

> ······@world.std.com (Kent M Pitman) wrote:
> > Incidentally, you should NEVER side-effect a piece of constant
> > structure.  Doing:
> >  (let ((x '(1 2 3)))
> >    (setf (car x) 100))
>
> Is (let ((x (list 1 2 3)))
>      (setf (car x) 100))
> OK?
> 
> I'm not sure what constitutes "constant structure".  The folks at Franz
> have warned me about this, and I have observed from experience that the
> (list...) form does not create constant structure (although it is a list
> of constants).

Yes, it doesn't matter that it contains constants.  It matters that the
side-effect is done to something that was constructed for you 
in that image by an operator whose job is to make you fresh, modifiable
structure.  LIST is such an operator.  It makes you a new cons backbone
so you can modify any aspect of any of those conses.

In particular, the compiler is not permitted to treat
(list 1 2) the same as '(1 2) even though it contains all constants
exactly because (list 1 2) makes a new list with new identity each time
(and one you can modify) while '(1 2) uses the same list with the
same identity each time, and might be merged ("coalesced") identitywise
with other equal constant forms.

If it helps, (LIST 1 2 3) is the same as 
 (CONS 1 (CONS 2 (CONS 3 NIL))
so it makes 3 conses.  Those three conses can be RPLACA'd or RPLACD'd
safely.  If you did
 (CONS 1 '(2 3))
you'd have made only one fresh cons.  In that case, you can only modify
the first cons in the list backbone but you can't modify the second and
third cons.
 (CONS 1 (CONS 2 '(3)))
makes 2 fresh conses and leaves the third unmodifiable.
 (LIST* 1 2 '(3))
is the same as
 (CONS 1 (CONS 2 '(3)))
From: Gareth McCaughan
Subject: Re: simple programming problem
Date: 
Message-ID: <86ra99kgp7.fsf@g.pet.cam.ac.uk>
Kent Pitman wrote:

> Yes, it doesn't matter that it contains constants.  It matters that the
> side-effect is done to something that was constructed for you 
> in that image by an operator whose job is to make you fresh, modifiable
> structure.  LIST is such an operator.  It makes you a new cons backbone
> so you can modify any aspect of any of those conses.

Just out of curiosity, is this actually made explicit in the Standard?
The entry for LIST in the HyperSpec just says `LIST returns a list
containing the supplied objects', and that on its own doesn't
guarantee that an implementation won't (say) begin by searching
all CONS cells to see whether it already has a list containing
the supplied objects... (It's clear from the wording of the
remaining text that LIST is *intended* to build a new list, but
it doesn't seem to be stated.)

-- 
Gareth McCaughan       Dept. of Pure Mathematics & Mathematical Statistics,
·····@dpmms.cam.ac.uk  Cambridge University, England.
From: Barry Margolin
Subject: Re: simple programming problem
Date: 
Message-ID: <62t848$l7r@pasilla.bbnplanet.com>
In article <··············@g.pet.cam.ac.uk>,
Gareth McCaughan  <·····@dpmms.cam.ac.uk> wrote:
>Kent Pitman wrote:
>> Yes, it doesn't matter that it contains constants.  It matters that the
>> side-effect is done to something that was constructed for you 
>> in that image by an operator whose job is to make you fresh, modifiable
>> structure.  LIST is such an operator.  It makes you a new cons backbone
>> so you can modify any aspect of any of those conses.
>
>Just out of curiosity, is this actually made explicit in the Standard?

It's described the other way around.  The standard says that you're not
allowed to modify "literal objects" (effectively a synonym for "constant
object"), and the glossary entry for "literal" says that this is an object

  referenced directly in a program rather than being computed by the
  program; that is, appearing as data in a quote form, or, if the object is
  a self-evaluating object, appearing as unquoted data.

A call to an operator such as CONS or LIST doesn't meet this definition, so
it's not a literal.

There actually are some exceptions to this definition, not mentioned in the
glossary.  A call to INTERN or FIND-SYMBOL may return a constant object,
because it's explicitly defined to pull an existing symbol out of a
package, and that symbol may have been created as part of a QUOTE form.
And LOAD-TIME-VALUE has an optional read-only-p parameter that can be used
to make its value a constant object.

-- 
Barry Margolin, ······@bbnplanet.com
GTE Internetworking, Powered by BBN, Cambridge, MA
Support the anti-spam movement; see <http://www.cauce.org/>
Please don't send technical questions directly to me, post them to newsgroups.
From: Kent M Pitman
Subject: Re: simple programming problem
Date: 
Message-ID: <sfw4t65zplu.fsf@world.std.com>
Gareth McCaughan <·····@dpmms.cam.ac.uk> writes:

> Just out of curiosity, is this actually made explicit in the Standard?

It's a good question.  It's some places clearer than others. 


In the late days of editing, I made a glossary term called "fresh" and
I started adding the term "fresh" to things that return fresh
structure.  LIST's definition is absent this.  I realized when we were
done that we also need a term for non-fresh.  I made a note to myself to
try out the term "fragile" (meaning you should treat it with care and 
expect it might share with some system structure), but I never actually
got anyone to review any text containing the term so don't know if it
would have gone over.

The definition of "fresh" from the Glossary in the HyperSpec is:

 fresh adj. 1. (of an object yielded by a function) having been
 newly-allocated by that function. (The caller of a function that
 returns a fresh object may freely modify the object without fear that
 such modification will compromise the future correct behavior of that
 function.) 2. (of a binding for a name) newly-allocated; not shared
 with other bindings for that name.

(Incidentally, anyone who has not seen the HyperSpec and thinks it is
"mostly like CLTL2 in presentation" will be in for a big shock. The
Glossary, for example, is nowhere present in CLTL2 and is one of the
parts I am most proud of.  On paper it's about 70 pages and it defines
a huge amount of terminology that CLTL2 leaves you fishing for in
very random places.  The HyperSpec prefers to centralize it.
Anyplace the HyperSpec uses a term formally,  that formal term is
clickable and you can get to the glossary definition directly.)

Applied correctly, the term "fresh" in the definition of LIST would say:

 LIST returns a fresh list containing the supplied objects. 

It presently does not say "fresh".  But it goes on to say some other
things that might or might not be argued to imply that construction
of fresh structure is reliably underway.  The absence of the term "fresh"
doesn't mean it's not fresh--it just leaves greater question.  It's 
possible there is another passage elsewhere that accidentally makes 
the issue clear, but you're right to suggest that it should be located 
here.

In CLTL, for example, the definition of left-to-right order of
evaluation was omitted in the "obvious" place, but can still be found
in three non-obvious places.  Those are (if memory serves me) SETF,
DEFSETF, and arithmetic contagion.  Each has a passage that talks about
some peripheral situation that "preserves the normal left-to-right
order of evaluation".  Could be LIST is similarly saved.  But it's
no substitute for saying things clearly.

I've made a note that this general issue should be clearer in future
editions.

Incidentally, it's not the only such issue on which we are unclear.
There are a great deal of things which we assume "not to cons" which
sometimes do.  And there are a bunch of things we assume to operate
with a certain algorithmic complexity that sometimes surprise us.
Implementors sometimes hate it when we pin them on some of these 
things, but increasingly I think these are good areas for us to record
user intuitions.