Subj : Re: Getting Started in Programming & Scripting
To   : comp.lang.c,comp.programming
From : Dave Thompson
Date : Thu Sep 29 2005 07:30 pm

On 20 Sep 2005 09:59:16 -0700, "Rob Thorpe"
<robert.thorpe@antenova.com> wrote:

> <Groups clipped a little>

And we're actually OT in clc but I don't read c.prog.

> Dave Thompson wrote:
<snip>
> > Lisp "pointers" are quite visible, although (at least classically)
> > they refer only to cons cells, so might as well be cell ids. E.g.
> >   ; A is bound to list (1 2 3) which is a cell whose left (CAR) is 1
> >   ; and right (CDR) is a pointer to a cell with left 2
> >   ; and right pointer to cell with left 3 and right NIL.
> >   ; This can also be written explicitly (1 . (2 . (3 . NIL)))
> >   (SETQ B (CDR A))
> >   (RPLACA B 9)
> >   ; A (or what it is bound to) is now (1 9 3)
> 
> No, not quite CAR refers to the first element of a pair, CDR the second
> element of that pair.  A list is formed by a list of pairs. The data is
> stored in the CARs and the link to the next pair being stored in the
> CDR.  This leads to CAR and CDR being called FIRST and REST.
> 
That's what I said. Each cell is (at least logically) a pair; the
first cell's left/CAR is the first element and its right/CDR "is"
(points to) the second cell, and so on down the list. (I only gave the
example to length 3, which IMO is enough to make the pattern clear,
though for programmers it might be better to just state the rule.)

> In the above code if A is (1 2 3):
> (setq A '(1 2 3))
> 
> (car A) is 1
> (cdr A) is the list (2 3) , *not* 2
> 
(cdr a) is the list (2 3); (car (cdr a)) aka (cadr a) is 2 

> If I do:
> (setq b (cdr A)) b is set to (2 3)
> then:
> (rplaca b 9) b is set to (9 3) because rplaca is a destructive
> operation.
> 
Right. And (cdr a) is still EQ (the same cell as) b, so a is (1 9 3).
Hence, at least as seen by the programmer, these are pointers.

> These functions can be thought of as implying pointer operations, but
> the concept isn't really necessary.  Conceptually CAR and CDR access
> the elements of a pair, which the lisp implementation deals with.
> 
CAR and CDR access the halves of a pair a.k.a. cell, but a pair has
identity and is referencable and mutable.

> They need not be implemented quite as the programmer may expect either.
>  There have been lisp implementations where pairs & lists are
> represented in quite subtle ways.
> 
True; I should have said 'vanilla' or 'canonical' Lisp. I was trying
to be brief, especially with my (recently worse) off-line delay.

> I think programmers of lower level languages like C are more
> comfortable thinking of this as pointer manipulation, which is OK.
> 
> > Conventionally a lot of Lisp code is pure-functional and never
> > modifies existing data structures, so aliasing doesn't matter, except
> > when you compare cells for identity (EQ).
> 
> Yep, and use the few modifying operations that exist for efficiency.

- David.Thompson1 at worldnet.att.net

.