Path: utzoo!attcan!uunet!ncrlnk!ncrcae!ece-csc!mcnc!thorin!proline!coggins
From: coggins@proline.cs.unc.edu (Dr. James Coggins)
Newsgroups: comp.lang.c++
Subject: Architecture, Implementation, Realization
Message-ID: <5331@thorin.cs.unc.edu>
Date: 15 Nov 88 14:34:21 GMT
References: <5155@thorin.cs.unc.edu> <6639@spool.cs.wisc.edu> <5263@thorin.cs.unc.edu> <10854@ulysses.homer.nj.att.com>
Sender: news@thorin.cs.unc.edu
Reply-To: coggins@proline.UUCP (Dr. James Coggins)
Organization: University Of North Carolina, Chapel Hill
Lines: 70

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
---------------------------------------------------------------------