Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!sun-barr!lll-winken!uunet!mcsun!ukc!dcl-cs!aber-cs!athene!pcg From: pcg@cs.aber.ac.uk (Piercarlo Grandi) Newsgroups: comp.lang.misc Subject: Re: C's sins of commission Message-ID: Date: 10 Nov 90 15:53:08 GMT References: <1990Nov2.172508.6393@maths.nott.ac.uk> <1990Nov8.174042.24789@maths.nott.ac.uk> <24573:Nov906:24:0790@kramden.acf.nyu.edu> Sender: pcg@aber-cs.UUCP Organization: Coleg Prifysgol Cymru Lines: 62 Nntp-Posting-Host: odin In-reply-to: brnstnd@kramden.acf.nyu.edu's message of 9 Nov 90 06:24:07 GMT 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