Path: utzoo!attcan!uunet!zaphod.mps.ohio-state.edu!ncar!noao!arizona!gudeman
From: gudeman@cs.arizona.edu (David Gudeman)
Newsgroups: comp.lang.misc
Subject: The semantic "level" of pointers
Message-ID: <26699@megaron.cs.arizona.edu>
Date: 23 Oct 90 03:53:11 GMT
Organization: U of Arizona CS Dept, Tucson
Lines: 74

In article  <65610@lanl.gov> jlg@lanl.gov (Jim Giles) writes:
]
]However, nomenclature aside, these features are clearly much higher
]level than pointers: the lowest level data structuring tool above the
]bit.

I think I've discovered the source of our disagreement, it is that we
have different ideas of what a "pointer" is.  I would say that the
level of a pointer is the same as the level of whatever it points to.
It seems that by your definition of "pointer", all pointers point at
machine memory, and are therefore machine level constructs.  However,
there are higher level pointers as well.  C pointers point into low
level data structures and are therefore low level.  Yes, they are
sometimes _used_ as pointers to memory by programmers who are making
assumptions about the implementation, but C lends itself to that sort
of thing in many areas.  On the other hand, a pointer into a high
level structure _must_ have the same high level characteristics or
else it isn't really a pointer to the high level structure.  Here is
an example:

Suppose you have Icon lists as a data structure.  Icon lists are
actually random-access concatenatable double-ended queues
(racdeques?).  They change size for various operations such as pop and
push.  They are indexed with expressions such as L[i] which produces
the ith element of list L.  Negative i indexes |i| from the end of the
list, so that L[-1] is the last element in the list (L[1] is the first
element).  An out-of-bounds reference causes the expression to "fail".
I won't go into the meaning of that now, but it is often used as a
primitive form of exception handling (though in reality it is very
different from an exception).

Now you could create a new data type in Icon that is a pointer into
lists.  The operations would be:

  pointer(L,i) -- produces a pointer to list L to the ith position
     (defaults to 1).  Fails if i is not a legal index for L.

  subject(p) -- produces the list that p points into.

  pos(p) -- produces the index in subject(p) that p points to.

  p + i -- produces a pointer to subject(p)[pos(p) + i].  Fails if the
     position is not in the list p points to.

  p[i] -- produces the value of subject(p)[pos(p) + i].  Fails if the
     value is out of range.

Icon programmers will see many more possibilities by analogy with Icon
list operations.

These pointers have to be called high level because their behaviour is
so different from anything in the machine.  They point to a list
structure whose elements are not laid out sequentially in memory, but
the pointer navigates among the blocks to get you the specified index
transparently.  After a garbage collection the list that p points to
has probably moved, but the pointer abstraction will track it down for
you and still give the correct results transparently.

So what's it good for?  Well I've often thought this abstraction would
be nice for recursive list algorithms.  Presently you have to pass a
list and index (tail() is incompatible with the other list
operations), but with pointers, you could just pass a single pointer.
I also prefer pointers for reasons of abstraction.  When you use
integer indexes you are using an integer, not just as a number, but as
a representation of a list position.  It seems to me that the idea of
a list position is prevelant enough that the programmer should be
given an appropriate abstraction in the language and not forced to
use integers to simulate them (just as it should not be necessary to
use pointers to simulate recursive data structures).
-- 
					David Gudeman
Department of Computer Science
The University of Arizona        gudeman@cs.arizona.edu
Tucson, AZ 85721                 noao!arizona!gudeman