Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!uunet!bywater!arnor!lusitania!lowry
From: lowry@arnor.uucp
Newsgroups: comp.lang.misc
Subject: Re: C's sins of commission
Message-ID: <1990Oct15.204343.2907@arnor.uucp>
Date: 15 Oct 90 20:43:43 GMT
References: <64618@lanl.gov) <2883@igloo.scum.com) <2171@enea.se> <1990Oct8.135551.21639@arnor.uucp> <1990Oct10.101527.2247@maths.nott.ac.uk>
Sender: news@arnor.uucp (NNTP News Poster)
Reply-To: lowry@lusitania.watson.ibm.com (Andy Lowry)
Organization: IBM T. J. Watson Research Center
Lines: 56

In article <1990Oct10.101527.2247@maths.nott.ac.uk>, anw@maths.nott.ac.uk (Dr A. N. Walker) writes:
|> In article <1990Oct8.135551.21639@arnor.uucp>
|> lowry@lusitania.watson.ibm.com (Andy Lowry) writes:
|> >I personally have written a great deal of code in Hermes and have
|> >found the lack of pointers to be no hindrance.
|> [...]
|> >Of course, our compiler and run-time system make heavy use of pointers
|> >and shared data for reasons of efficiency, but this is completely
|> >hidden from the Hermes programmer.
|> 
|> 	In other words, here is a construct which is incredibly
|> useful for writing compilers and other programs, but which the
|> ordinary programmer is unable to use.

The point I meant to make is that indirect addressing is a fact of
life in most of today's computer architectures.  Therefore, pointers
will certainly be found in efficient implementations of many programs.
This does not mean that the pointers need to show through in the
languages in which the programs are written.  Many computers also have
segment registers, process status registers, data caches, and other
such features, but I'm not ordinarily aware of them when I write
programs.  When we implemented the Hermes run-time system, we did, in
fact, make heavy use of pointers.  This is because we wrote the system
in C, where pointers are indispensible.  We believe that we have
designed Hermes in such a way that pointers are not indispensible.

|> 	When, as a mathematician [well, as a game player, really],
|> I think of a tree or a graph, I think naturally and easily of each
|> node as being some information plus a collection of pointers to other
|> nodes.  I draw them that way.  You may think of them differently;
|> but I think I should be allowed, within my chosen language, to program
|> them my way, and not have to pummel them into some other shape.

I expect you actually think of them as a collection of nodes and arcs.
At least that's how they're normally presented in mathematical books
and articles.  Computer programmers typically represent the arcs as
arrays or lists of pointers to successor nodes.  This moves away from
the conceptualization and biases the implementation in some very
significant ways.  For example, without substantial extra baggage,
such a representation will never support following the arcs backward
as easily or cheaply as forward.

The Hermes programmer could represent a graph precisely in the
standard conceptual manner--as a collection of nodes and a collection
of arcs, where each arc is a record containing two node id's.  The
compiler and run-time system would choose representations and
algorithms based on a number of factors, perhaps including observed or
anticipated access patterns, hints from the programmer, etc.  If the
access patterns were to change, a recompilation could adapt these
choices as needed to maintain efficiency.  This is much cheaper and
less error-prone than re-engineering a C program because reverse
traversals are suddenly needed in a structure that has only forward
pointers.
-- 
Andy Lowry, lowry@ibm.com, (914) 784-7925
IBM Research, 30 Saw Mill River Road, P.O. Box 704, Yorktown Heights, NY  10598