From: carroll@balin.cis.udel.edu (Mark C. Carroll)
Newsgroups: comp.lang.misc
Subject: Re: Pointers
Date: 15 Nov 92 19:57:32 GMT
Organization: University of Delaware, Newark

In article <Bxnqv5.J71@mentor.cc.purdue.edu> hrubin@pop.stat.purdue.edu (Herman Rubin) writes:
>In article <1992Nov12.200950.8846@newshost.lanl.gov> jlg@cochiti.lanl.gov (J. Giles) writes:
>
>			.......................
>
>>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.
>
>Why do some people find it necessary to hide simple devices under 
>interfaces?  The insistence on the use of these interfaces is like
>the joke about the mathematician who pours the water out of the bucket
>and turns off the stove to reduce the problem to the previous case.
>

Why do people find the need to destroy abstractions in favor of
incomprehensible low-level implementations?

In virtually any computer program, there is a conceptual data
structure, such as a list, a tree, a graph, a stream, etc. The
conceptual data structure has some set of natural operations and
properties. When the conceptual data structure is mapped into an
implementation, the low-level implementation of the structure does not
necessarily preserve the properties of the structure. The idea of
interfaces is to present the _conceptual_ data structure, and not the
implementation data structure. 

If you're a half-decent programmer, there is *no* performance penalty
for building the structure behind an interface. But all users of the
structure can work with the structure as if it is the conceptual
structure, rather than the implementation structure.

For example (in C), if you need to implement a list, you can create a
structure:

typedef struct _list {
   value v;
   struct _list *next;
} *list;

Then, all of your users have to muck with pointers. They have to be
careful to not create cycles, and to deallocate entries at the right
time, etc.

On the other hand, you can present an interface, with a set of operations:

	list new_list()
	value value_at_cursor(list);
	void cursor_tobegin(list)
	void cursor_forward(list);
	void insert_at_cursor(list,value)
	value remove_value_at_cursor(list);
	void destroy_list()

This interface has all of the properties of the conceptual structure
that the previous implementation models. But it is *guaranteed* to
preserve those properties. It also relieves the user of the structure
from having to deal with the grunginess of the implementation model.
And finally, if I decide that my structure isn't a good implementation
model, I can *transparently* change it - my users don't even realize
that it's changed!

(An example of all this comes from my current project. I use a
heirarchical symbol table. I initially implemented the table as a
hashtable. After building 20,000 lines of code on top of this, I
unexpectedly discovered that most of the time, each level of the
heirarchy contained less than 10 elements - so my hashtable was a very
poor way to implement it - it was slower than the alternatives, and
wasted an enormous amount of memory. So I changed the implementation
of use association lists. I didn't have to rewrite a *single* line of
code outside of my symbol table implementation, because my code used
the interface to the type, and the properties of the type didn't change
a bit.

In addition, I didn't pay *any* performance penalty for implementing my
datatype behind an interface.)


	<MC>
-- 
|| Mark Craig Carroll: <MC>     ||"I prize the cloudy, tearing sky,
|| Univ of Delaware, Dept of CIS|| for the thoughts that flap and fly.
|| Grad Student/Labstaff Hacker || For staying in and reading by.
|| carroll@udel.edu             || For sitting under" -Karen Peris
Newsgroups: comp.lang.misc