From: jlg@cochiti.lanl.gov (J. Giles)
Newsgroups: comp.lang.misc
Subject: Re: Pointers
Date: 12 Nov 92 20:09:50 GMT
Organization: Los Alamos National Laboratory

In article <id.6HVU.OC@ferranti.com>, peter@ferranti.com (peter da silva) writes:
|> In article <1992Nov5.014143.15635@newshost.lanl.gov> jlg@cochiti.lanl.gov (J. Giles) writes:
|> >    First: in both, you should avoid having loops.  In the case of GO TO,
|> >    you should try not to branch backward.  In the case of pointers, you 
|> >    should try to avoid cyclic data structures.
|> 
|> If you think I'm going to give up doubly-linked circular lists because you
|> don't like pointers, you've got another think coming.

Ok, give it to me.  You claim I've got it comming, so let's have it.
I collect them you know.

Seriously, I'm glad I don't have to maintain your code.  I only
use such things as circular lists when they are the best choice
available - which is almost never.  Yes, I sometimes use them.
But they require extra work (because you can't tell, when traversing
the list, whether you've reached the end of it without additional
information that is not *locally* contained in the list).  They
also have some practical drawbacks by making reference counting
garbage collection schemes much more complicated (so much so that
they are usually abandoned).  Now presumably your circular lists
are at least constrained to have the *whole* list within the cycle.
If you don't do that, then I'm *really* glad I don't have to work
with your code.

Lists are somewhat less difficult to allow to cycle than trees
or arbitrary graphs (though the latter *need* to cycle more often).  
If I have to support arbitrary directed graphs, I don't use raw 
pointers at all.  The decreased legibility and reliability of such 
an implementation is not acceptable.  I *may* use pointers *inside* 
the implementation for efficiency reasons, but all the operations 
on them will be handled through an interface which imposes a better 
visible structure on the data.  

For example: the graph G is defined as G(V,E), where V is a set of
vertices (which might contain data of some type) and E is a set of
edges.  The set of edges consists of ordered pairs of vertices:and
maybe some information of some data type (since edges and vertices 
are duals of each other, both may be associated with data).  That's 
the *logical* appearance of them, internally they may be implemented 
as pointers between the vertices - however, that implementation is 
irrelevant and can be replaced with other possibilities should more
efficient means for a *given* problem become apparent.
  
All this gives a structured data type to which the theorems and 
algorithms of graph theory can be applied directly.  If I had used 
pointers as my "surface level" implementation, the application of 
graph theory would have been obscured by the pointer manipulations.

Not only that, but if a more efficient implementation becomes 
apparent (like storing the set of vertices as a contiguous 
sequence instead of a linked list - more efficient if deleting
and inserting vertices is rare), *if* such a decision is made,
the explicit pointer implementation *you* recommend would have
to be completely rewritten in detail.  All *I* have to do is replace
the access functions (or macros, or whatever abstraction method
I use).

|> [...]
|> OK, I'll throw away all my generic symbol table code because it's
|> politically incorrect. Not.

I could care less what you do.  I don't have to suffer through
your code.  If you prefer tinkering with arcane sequences of
confusing code, that's your business.  I prefer to write algorithms
which visibly resemble the graph theoretic concepts they implement.

My recommendations are just that: recommendations.  If you choose
to follow them, fine.  If not, fine.  Political correctness consists
of more stringent measures: like censorship or the attempt to *force*
others to conform.  I engaged in neither of these.  In fact, I consis-
tently oppose people who recommend actions which *force* others to
conform.

So, I will repeat my recommendations in a different form: use pointers
as little as possible; when you have to use them, conceal them under
an interface which implements the *exact* semantics you have in mind;
*NEVER* access your data except through the interface; *IF* a section
of code is found to be a time-critical element then you can expand
your interface routines in-line for better efficiency - but the
code should be written and debugged before you do so.  You should
end up using *raw* pointers as seldom as you use *raw* GOTOs.

|> [...]
|> As for your analogies, an analogy is like instant coffee.

C.A.R. Hoare proved that the concepts of pointers and GOTOs are
*isomorphic* - which is a lot stronger than a mere analogy.  The
consequence of this observation is that *any* valid argument against
GOTOs is equally valid against pointers.  Period.  As I keep saying,
you cannot do any coding at all without GOTOs, it's just that most 
of the ones you use are hidden under an interface (IF/ELSE, DO/ENDDO,
SELECT/CASE, procedure calls, etc.) which capture the *specific* semantics
of the flow control the user has in mind.  The same kinds of interfaces
need to be designed and applied to data structures to eliminate *raw*
pointer instances.

-- 
J. Giles