Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!sdd.hp.com!uakari.primate.wisc.edu!aplcen!haven!umbc3!gmuvax2!2113av
From: 2113av@gmuvax2.gmu.edu (John Porter)
Newsgroups: comp.lang.misc
Subject: Re: C's sins of commission
Message-ID: <2915@gmuvax2.gmu.edu>
Date: 17 Nov 90 05:46:16 GMT
References: <27376@megaron.cs.arizona.edu> <-M.6315@xds13.ferranti.com>
Reply-To: 2113av@gmuvax2.UUCP (John Porter)
Organization: George Mason Univ. Fairfax, Va.
Lines: 43

Piercarlo Grandi:
> ]Ah no, this cannot pass. Lists and trees are *implementations*, and when
> ]you draw them you draw specific encodings of such implementations.

David Gudeman:
> No, this cannot pass.  Lists and trees are mental structures that
> humans use to visualize things.

Peter da Silva:
I must agree with Piercarlo here.
The basic things that people work with are "chunks of data". Lists, trees,
tries, and so on are methods of implementing these databases in efficient
ways. There's nothing fundamental about them.

John Porter resonds:
I'm not normally one to be argumentative, and I find it fascinating
that "wars" can arise over topics as basic to c.s. as lists, trees, etc.
But I feel compelled to register my agreement with Mr. Gudeman here;
lists, trees, etc., ARE concepts, NOT implementations.  (That is why they
are called "abstract data types".)
Mr. Piercarlo's assertion that "when you draw them you draw specific
implementations of them" is, it seems patently obvious to me, quite false.
A circle, a box, a line, an arrowhead, they say nothing, imply nothing
about any implementation; they do not imply that there is, was, or ever
will be an implementation, in a computer program or anywhere else.
You don't say "I implemented this
chunk of data with a tree", you say "I implemented this tree with
dynamically allocated structs, each containing pointers to parent and
children", or whatever your implementation happens to be.  As a concrete
example, contrast the just-described tree implementation with the 
following:
A binary tree can be implemented in a static array, where element
number one is the head; from any given node (identified by its index into
the array), you can reach the left child by multiplying the indes by 2;
find the right child immediately past the left child.
This implemenation is sometimes called "heap", but that is confusing.
Note. No pointers. An entirely different implemenation, but a tree
none-the-less.  The concept is the same.

-- John Porter

#	"Everybody could stand a HUNDRED chest x-rays a year.
#	 They ought to have them, too."	J. Frank Parnell