🚀 go-pugleaf

On 9 Nov 90 06:24:07 GMT, brnstnd@kramden.acf.nyu.edu (Dan Bernstein) said:

brnstnd> In article <1990Nov8.174042.24789@maths.nott.ac.uk>
brnstnd> anw@maths.nott.ac.uk (Dr A. N. Walker) writes:

(probably me)> What you want to do is to represent entities, not be
(probably me)> concerned about how the relevant encoding is done.

anw> Just so, which is exactly why I am happy for my entities to include
anw> pointers to other entities, and to let the compiler worry about how
anw> it is actually done in machine code.

Pah. pointers are just a thin veneer on the underlying implementation.
The thing you want to implement is a *relationship*; a pointer is a way
to implement a relationship, and an address is a way to represent a
pointer. Both are by no means the only choices. When designing the
application, neither level is necessary or useful (except that xertain
8design* chocies may be legitimately be influenced by the expected
relative costs of the possible implementations and representations).

brnstnd> Exactly! I really do think about data structures as boxes
brnstnd> containing other boxes, some of which contain arrows to boxes.
brnstnd> When I draw them, that's how I draw them, not as some abstract
brnstnd> ``list'' or ``tree'' or ``recursive data structure'' (not that
brnstnd> I know how you draw those).

Ah no, this cannot pass. Lists and trees are *implementations*, and when
you draw them you draw specific encodings of such implementations.
Designs are quite a different thing.

The way *I* think about data structures as typed mappings over entities
(entity-category-relationship!), and then I wonder which is the best
implementation for the mapping, based on things like time and space
complexity for the most frequent operations needed, cost of
encoding/decoding, cardinality of the domains, sparseness (trees and
lists are both good for sparse mappings, trees are faster for random
access, lists have smaller space overhead, etc... -- boxes enter the
picture only when I have to represent the implementations).

	Please, please have a reread of Hoare's seminal paper on data
	abstraction in "Structured Programming", Academic Press. And
	when you have finished it, go read the next essay on control
	abstraction by Dahl. Another very recommended source is
	Wiederhold's "Database Design", McGraw Hill, second part (the
	first part is about implementation and representation).

IMNHO we are still quite far apart on having compatible notions of the
distinction between design and implementation, and the difference
between the design of an implementation (a pointer that is encoded as an
address) and the implementation of a design (a pointer that represents a
relationship).

Abstraction level mixup, I am afraid. I wish that data design were
considered a fundamental discipline, not just an esoteric trick for
DBAs. Most large programs have more sophisticated data designs than many
databases, yet DBAs are told about data design 9with a smattering of
implementation) and programmers are only told about representations
(with a smattering of implementation).
--
Piercarlo Grandi                   | ARPA: pcg%uk.ac.aber.cs@nsfnet-relay.ac.uk
Dept of CS, UCW Aberystwyth        | UUCP: ...!mcsun!ukc!aber-cs!pcg
Penglais, Aberystwyth SY23 3BZ, UK | INET: pcg@cs.aber.ac.uk