Subj : Re: Getting Started in Programming & Scripting
To   : comp.lang.c,comp.programming
From : Rob Thorpe
Date : Tue Sep 20 2005 10:59 am

<Groups clipped a little>
Dave Thompson wrote:
> On 12 Sep 2005 15:47:25 -0700, "Rob Thorpe"
> <robert.thorpe@antenova.com> wrote:
> <snip>
> > Yes.  Several programming languages have no concept of pointer that's
> > visible to the programmer.  For example Lisp, Java and Perl have no
> > pointers.  Perl has references which refer, somehow, to another perl
> > object - effectively equivalent to a pointer.
> >
> And in Java _all_ objects use (aliasing) references.  (Classic and I'm
> pretty sure standard) BASIC has no pointers. FWIW awk has no pointers,
> although arrays (not scalars) are by-reference to functions.
>
> Classic FORTRAN and COBOL have no manipulable pointers; they do have
> call-by-reference (formally FORTRAN also allows value-result but
> that's not feasible for large data).  F90 added pointers that are very
> type-strict but still can dangle, plus F90 added and F95 and a TR
> incorporated into F03 enhanced a more restricted form that are
> memory-safe; I haven't checked on recent COBOL.

Ah, I'd forgotten about Basic, and didn't know about recent versions of
Fortran or Cobol.

> > Lisp's don't have pointers per se.  Each name in a lisp program and
> > almost everything else is "bound" to a piece of data of some type, and
> > can be freely rebound.  Some of these data types can store sequences of
> > values.  So, altogether there is no need for visible pointers.
> >
> > (There are naturally tons of pointers in actual implementation, but
> > they're invisible to the programmer).
> >
> 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.

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

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.

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.

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.

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.

.