coggins@proline.cs.unc.edu (Dr. James Coggins) (11/15/88)
In article <10854@ulysses.homer.nj.att.com> jss@hector.UUCP (Jerry Schwarz) writes: >In article <5263@thorin.cs.unc.edu> coggins@cs.unc.edu (Dr. James Coggins) writes: >> >>(an ADT consists of data, procedures, and axioms that define consistent >>states of the structure. Most discussions and all implementations forget >>about the axioms.) >> >I do not think this is a correct description of Abstract Data Types. No, I did get this one right. An ADT is a set of domains D, a designated domain d an element of D, a set of functions F and a set of axioms A. The triple (D,F,A) denotes the ADT d. Example: structure NATNO declare ZERO() -> natno ISZERO -> boolean SUCC(natno) -> natno ADD(natno,natno) -> natno EQ(natno,natno) -> boolean for all x,y in natno, ISZERO(ZERO()) ::= true ISZERO(SUCC(x)) ::= false ADD(ZERO(),y) ::= y ADD(SUCC(x),y) ::= SUCC(ADD(x,y)) EQ(x,ZERO) ::= if ISZERO(x) then true else false EQ(ZERO,SUCC(y)) ::= false EQ(SUCC(x), SUCC(y)) ::= EQ(x,y) end An implementation of an ADT d is a mapping from d to a set of other data structures e specifying how every object of d is represented by objects of type e. Also, the functions of d must be written using the functions of e. Thus, we say the integers are represented by bit strings, boolean is represented by zero and one, etc. The axioms do not imply a representation. (above is from a data structures text I have used, Horowitz and Sahni, Fundamentals of Data Structures, Computer Science Press, 1982.) Now that I have your attention, I want to make one additional point that I will try to expand on Some Day Soon: A source of considerable confusion and much unenlightening heat is that we often get sloppy about the IMPORTANT distinctions among architecture, implementation, and realization. (See Brooks, Mythical Man-Month for fuller discussion). The fact that our normal modes of expression of data structures (programming languages) fail to separate them is a large source of our sloppiness. It is almost impossible within current programming languages to divorce an architecture from an implementation and a realization of it. This failure to distinguish these levels is why I believe that lots of the code sharing that could happen isn't happening and probably won't with our current modes of expression. To buy somebody's elegant architecture means that you have little choice but to also buy into the implementation and realization assumptions of the author. When it works, great. It often doesn't work. C++ header files embody architecture and bind it to an implementation. They are inseparable because of the strong type checking. There may be a work-around involving abstract classes and smart pointers, but you won't like it. --------------------------------------------------------------------- Dr. James M. Coggins coggins@cs.unc.edu Computer Science Department "Make it in Massachusetts" - ad slogan UNC-Chapel Hill "I made it OUT of Massachusetts" Chapel Hill, NC 27514-3175 - my slogan ---------------------------------------------------------------------