Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!sdd.hp.com!zaphod.mps.ohio-state.edu!think.com!mintaka!bloom-beacon!eru!hagbard!sunic!mcsun!ukc!edcastle!aiai!jeff
From: jeff@aiai.ed.ac.uk (Jeff Dalton)
Newsgroups: comp.lang.misc
Subject: Re: Re^4: Some things that pointer-less languages can't do efficiently
Message-ID: <3717@skye.ed.ac.uk>
Date: 7 Nov 90 21:25:39 GMT
References: <26739:Oct1023:44:2690@kramden.acf.nyu.edu> <65450@lanl.gov> <10397:Oct1212:55:1090@kramden.acf.nyu.edu> <3975@goanna.cs.rmit.oz.au> <415@data.UUCP> <+CI6:YD@xds13.ferranti.com> <418@data.UUCP> <83N6E05@xds13.ferranti.com>
Reply-To: jeff@aiai.UUCP (Jeff Dalton)
Organization: AIAI, University of Edinburgh, Scotland
Lines: 48

In article <83N6E05@xds13.ferranti.com> peter@ficc.ferranti.com (Peter da Silva) writes:
>First of all... what's a pointer? It's not a machine address. A pointer is
>a token that refers to a value, such that it can refer to any value in
>the domain of the language, and that more than one such token can refer
>to a given value. The operation of getting to the value referred to is
>called dereferencing.

When a language has pointers, this usually means that "pointer" or
"pointer to TYPE" is a kind of value.  Pointers can be assigned to
variables, passed as parameters, etc.

Lisp and Scheme do not have pointers in that sense, unless you regard
*all* values as pointers (modulo certain cases where compiler code may
hold certain values directly).  If you do that, it is often better
(when thinking about Lisp) to factor out the phrase "pointer to" and
regard all objects as being held directly (rather than indirectly, at
the other ends of pointers).  

Aliasing is still possible, because two variables may hold the same
object or hold objects that overlap.  However (modulo displaced arrays
in CL?) different arrays never overlap, and there is no value that can
turn out to be, say, a pointer to the 3rd element of an array.
Whether aliasing is a problem for programmers depends on how, and
how often, they use side effects to modify objects.

Now let's talk about dereferencing.  (CAR X) and (CDR X) dereference
X, in a sense.  They do a deref plus a structure access.  But there
isn't any X in Lisp such that X is a pointer to Y, and no operation
that given a "pointer to Y" will return Y.  So the closest we can come
here is to say "a cons is a pair of pointers".

Some Lisps (eg, ZetaLisp) do have such things.  They are an additional
data type (not present in standard Common Lisp or Scheme, for example)
called (in ZetaLisp) "locatives".  And additional property of locatives,
something otherwise impossible, is that they can point into objects,
such as to the 3rd element of a vector.

In any case, it is important to note that a cons need not be
implemented as a pair of pointers.  In particular, it is possible
to use cdr-coding or an even more compressed form where the cars
are not pointers either.  So the equation between a cons and a
pair of pointers is not a completely straightforward one.

Note that I have not tried to argue that Lisp does or does not have
pointers, only to describe what the actual situation is.  Whether it
counts as having pointers I leave to you.

-- Jeff