Path: utzoo!attcan!uunet!cs.utexas.edu!wuarchive!zaphod.mps.ohio-state.edu!rpi!uupsi!cmcl2!lanl!jlg
From: jlg@lanl.gov (Jim Giles)
Newsgroups: comp.lang.misc
Subject: Re: Answers, Chapter 1: TeX (was C's sins... and others)
Message-ID: <3791@lanl.gov>
Date: 24 Oct 90 21:59:39 GMT
References: <26740@megaron.cs.arizona.edu>
Organization: Los Alamos Natl Lab, Los Alamos, N.M.
Lines: 56

From article <26740@megaron.cs.arizona.edu>, by gudeman@cs.arizona.edu (David Gudeman):
> In article  <3681@lanl.gov> jlg@lanl.gov (Jim Giles) writes:
> ][I argue that pointers are bounded just like arrays]
> ]Really?  I don't know _any_ language that has pointers that places
> ]bounds on where it can point.
> 
> We are comparing pointers to indexes here.  [...]

_ONE_ of the things that we are comparing pointers to is indexing.
That's one of the problems with pointers (at least, pointers a`la C)
is that many _different_ functionalities are all rolled up into
the pointer mechanism.

So, let's get a definition straight here.  When I say bounded (in the
context of a pointer discussion), I mean that the address of an object
is limited by its declaration (or, at least, its initialization - which
may be dynamic) to a specific memory location.  This means that an
inspection of the declaration and of the present location is sufficient
to determine whether the present reference is "in bounds".

With pointers, you can't make such a simple determination.  No matter
what memory location it references, it _may_ be a legal and intended
one.  This makes debugging pointers incrementally harder - especially
in large codes.  The compiler _can't_ make any simple automatic bounds
checks (although, in C it can perhaps automatically limit index
calculations).  Even the user with an interactive debugger may be
hard pressed to determine whether the pointer is correct or not.

Arrays (even dynamic ones) are always allocated by the compiler or
a compiler generated allocator (at least, according to the language
model I've been presenting) - so you _know_ that they are located
distinctly from other objects with sufficient space for their declared
length (unless the compiler is broken - in which case all bets are off
anyway).

Boundedness and aliasing are _slightly_ different concepts.  Clearly
something that is unbounded is potentially aliased to everything (or,
everything of the same underlying type).  Something that's bounded
_may_ still be aliased: this may even be desireable.

I recommend two mechanisms to implement boundedness: 1) all objects
are distinct; 2) operations allowing aliasing between distinct variables
must be explicitly requested when these variables are declared.  This
means that even those things which _are_ allowed to be aliased are
bounded to be aliased only to others of a small "family" of variables.
Variables _not_ in this "family" are _known_ not to be aliased to
anything within it (in fact, the constraint can be enforced by the
compiler and loader alone - no run-time support is needed - whether
run-time checks might be more efficient is a different question).

The bottom line is that I can think of some applications for bounded
aliasing, and certainly bounded non-aliased variables are very useful,
but I can't think of any application except the low-level memory manager
which needs unbounded memory access.

J. Giles