flitter@atisun.dt.navy.mil (Lance Flitter) (11/08/90)
Greetings. I was wondering if someone would venture a good description of the difference between Abstract Data Types and Objects. Is there a difference? Is one a subset of the other? -- Lance Flitter - David Taylor Research Center, USN flitter@dtrc.dt.navy.mil VOICE (301) 227-3379 FAX (301) 227-5753
paulb@minster.york.ac.uk (11/13/90)
In article <4255@oasys.dt.navy.mil> flitter@atisun.dt.navy.mil (Lance Flitter) writes: > Greetings. I was wondering if someone would venture a good description >of the difference between Abstract Data Types and Objects. Is there a >difference? Is one a subset of the other? This is something that has been discussed quite a bit here at York recently. We reached the conclusion that an object-oriented programming language is basically a superset of abstract data types. A class is an simply abstract data type, and an object is an instantiation of that ADT. Another way of looking at it is to notice that objects are *unique*, i.e. two objects whose instance variables contain the same values are *different* objects, whereas a value in an ADT-language is just a value, and has no existence in it's own right. Whether uniqueness is an advantage or not is, of course, debatable. It certainly causes some problems (just look at the implementation of sets in SmallTalk to see what I mean). My own preference would be for a good ADT language. Paul. +--------------------------+-----------------------------------------------+ |Paul Butcher | JANET: paulb@uk.ac.york.minster | |Dept. of Computer Science | EARN: paulb@minster.york.ac.uk | |University of York | UUNET: ..!uunet!mcsun!ukc!minster!paulb | |York YO1 5DD ENGLAND | ARPA: paulb%york.minster@nsfnet-relay.ac.uk | |Tel: (0904) 432760 | Alternative address: | | (+44 904) 432760 | PRAB1@uk.ac.york | +--------------------------+-----------------------------------------------+ Note: The above are my views, not necessarily those of the department.
thomasw@hpcupt1.cup.hp.com (Thomas Wang) (11/13/90)
My opinion is that: Object oriented language == ADT + inheritance -Thomas Wang (Everything is an object.) wang@hpdmsjlm.cup.hp.com thomasw@hpcupt1.cup.hp.com
zhou@brazil.psych.purdue.edu (Albert Zhou) (11/13/90)
My understanding about the difference between ADT and OOP is that ADT just contains data structure while an object contains both the data structure and algorithm. In another word, an object alone can do a task, while ADT just prepare the materials for the task.
sakkinen@tukki.jyu.fi (Markku Sakkinen) (11/13/90)
In article <658426218.13725@minster.york.ac.uk> paulb@minster.york.ac.uk writes: >In article <4255@oasys.dt.navy.mil> flitter@atisun.dt.navy.mil (Lance Flitter) writes: >> Greetings. I was wondering if someone would venture a good description >>of the difference between Abstract Data Types and Objects. Is there a >>difference? Is one a subset of the other? > >This is something that has been discussed quite a bit here at York >recently. We reached the conclusion that an object-oriented programming >language is basically a superset of abstract data types. A class is an >simply abstract data type, and an object is an instantiation of that ADT. > >Another way of looking at it is to notice that objects are *unique*, >i.e. two objects whose instance variables contain the same values are >*different* objects, whereas a value in an ADT-language is just a value, >and has no existence in it's own right. > >Whether uniqueness is an advantage or not is, of course, debatable. It >certainly causes some problems (just look at the implementation of sets >in SmallTalk to see what I mean). My own preference would be for a good >ADT language. There has been no tidewave of answers to the original question yet: it is important but difficult. Likely almost everyone has an idea that is a little different from others; I'm offering a variation of the above. Historically, Objects are older than ADT's. In Simula (67) the essential novelty of objects was the packaging of functionality together with data. Abstraction and encapsulation have entered the picture of OOP much later. An object is a natural extension of a variable in a conventional, imperative programming language; therefore it is also natural to distinguish objects by identity (uniqueness) and not by the values they contain, just like conventional variables. Other influences to current OOPL's have come notably from semantic data models and from frame-based AI systems; of course also from programming languages that incorporate ADT ideas (CLU, Ada, Modula-2, ...). Objects in Simula and in some (not most) newer OOPL's can have one property that clearly does not fit within the ADT framework: an internal activity, not only operations (methods) that can be invoked. In some respects, OOPL's can be more restricted than typical ADT's. The ADT approach puts no restrictions on how binary (and ternary or higher degree) operations or functions on a type may be defined. In contrast, Smalltalk and some other OOPL's don't allow an object to see inside another objects even of the same class. Among the most distinctive traits of OOP are _inheritance_ ('prefixing' in Simula) and _late binding_ (for which many use the overstatement 'message passing'), especially in combination. Some people suggest the following definition at least as an approximation: OOP = ADT + inheritance + late binding (Sorry, I don't remember the origin just now.) The three-stage classification of Prof. Peter Wegner from OOPSLA'87 seems to be quite popular, and he presented it again in the first issue of OOPS Messenger (published by ACM SIGMOD). - Object-based: the class of all languages that support objects. - Class-based: the subclass that requires all objects to belong to a class. - Object-oriented: the subclass that requires classes to support inheritance. Incidentally, I don't see this classification as very relevant; it is a rather arbitrary choice among the many aspects in which existing, more or less object-oriented languages differ from each other. One can also suspect some kind of grudge against the Ada community behind this scheme, because it just nicely leaves Ada in the lowest category. - However, don't miss Wegner's new article, "Concepts and Paradigms of Object-Oriented Programming": it gives a very broad perspective. There are some new OOPL's that abandon classes altogether and are instead based on the principle of existing objects acting as prototypes for new ones. One can hardly speak about ADT's in such languages. Contrary to what "paulb" said, many languages based on ADT's are identity-oriented and _not_ value-oriented. This is true even of the best-known pioneering ADT language, CLU. The basic datatypes are an exception, but so are they in Smalltalk. (I think this exception is ugly; we had a good fight over this issue in this group some months ago.) On the other hand, many ideas and features typical of OOPL's can be adapted also into a value-oriented language that does not support object identity. For instance, the OOPS+ database programming language, which has been developed in the Esprit KIWI project, seems to take an essentially value-oriented approach (there was a paper at ECOOP'88). Markku Sakkinen Department of Computer Science and Information Systems University of Jyvaskyla (a's with umlauts) Seminaarinkatu 15 SF-40100 Jyvaskyla (umlauts again) Finland SAKKINEN@FINJYU.bitnet (alternative network address)
craig@Neon.Stanford.EDU (Craig D. Chambers) (11/14/90)
In article <1990Nov13.094257.15308@tukki.jyu.fi> sakkinen@jytko.jyu.fi (Markku Sakkinen) writes: >In article <658426218.13725@minster.york.ac.uk> paulb@minster.york.ac.uk writes: >>In article <4255@oasys.dt.navy.mil> flitter@atisun.dt.navy.mil (Lance Flitter) writes: >>> Greetings. I was wondering if someone would venture a good description >>>of the difference between Abstract Data Types and Objects. Is there a >>>difference? Is one a subset of the other? >> >>This is something that has been discussed quite a bit here at York >>recently. We reached the conclusion that an object-oriented programming >>language is basically a superset of abstract data types. A class is an >>simply abstract data type, and an object is an instantiation of that ADT. > >Among the most distinctive traits of OOP are _inheritance_ ('prefixing' >in Simula) and _late binding_ (for which many use the overstatement >'message passing'), especially in combination. Some people suggest >the following definition at least as an approximation: > OOP = ADT + inheritance + late binding >(Sorry, I don't remember the origin just now.) > >The three-stage classification of Prof. Peter Wegner from OOPSLA'87 >seems to be quite popular, and he presented it again in the first >issue of OOPS Messenger (published by ACM SIGMOD). >- Object-based: the class of all languages that support objects. >- Class-based: the subclass that requires all objects to belong to a class. >- Object-oriented: the subclass that requires classes to support inheritance. I agree most with the first "equation" for defining OOP. Inheritance seems to come in two flavors as well: subtyping (inheritance of specification/interface) and code sharing (inheritance of implementation). To me, late binding (and the accompanying subtyping in a statically-typed language) is the most important feature of object-oriented programming over abstract data type programming. Inheritance of implementation seems like something that could be moved out of the core language and into the programming environment, where more flexible and adaptive code sharing/automatic programming could be done without cramming a lot of functionality into a language mechanism. Inheritance rules seem overly complicated in most modern languages (e.g. CLOS, Eiffel, C++, and even Self), and are one aspect of an object-oriented that's likely to change or be outdated in 5 years. So why date a language with a complex feature that would be more malleable and adaptive in a programming environment? Of course, I'd have to implement such a wonderful system to convince most people; at this point, it's just an idea that may never pan out. So my official prediction for 1991 is that OO languages will continue to include code inheritance as a built-in language mechanism. In contrast to Peter Wegner's taxonomy, I'd relegate the presence or absence of classes to a minor role in classifying object-based languages. Here's my brief taxonomy: object-based: languages with objects (data structures with associated methods) object-oriented: object-based languages with message passing (selecting message implementation based at least in part on the implementation of argument objects; late binding) inheritance-based: object-based languages with code inheritance (either in the language or the environment) object-oriented-inheritance-based: object-oriented languages with code inheritance Other languages design choices and features, such as classes vs. self-sufficient objects, multiple dispatching, strong encapsulation, static typing and subtyping, parallelism, and physical distribution, can be mixed and matched to create an object-oriented language with particular characteristics for a particular purpose, but to me they're all object-oriented as long as they have objects and message passing. I only give a name to languages with inheritance because inheritance has a large impact on the structure of programs in the language, and so could reasonably be argued to deserve its own categorization. ADT-based languages are typically object-based with strong encapsulation added in to enforce the "abstract" part of the name. This taxonomy is motivated by identifying features that I consider to be powerful programming tools, rather than an attempt to distinguish existing programming languages and give them different labels, as was Peter Wegner's (much more extensive) taxonomy. -- Craig Chambers
matt@bacchus.esa.oz (Matt Atterbury) (11/14/90)
In article <-283749996@hpcupt1.cup.hp.com> thomasw@hpcupt1.cup.hp.com (Thomas Wang) writes:
My opinion is that:
Object oriented language == ADT + inheritance
-Thomas Wang
(Everything is an object.)
Where then is the A in ADT (*ABSTRACT* data type). I see an ADT as
a _generic_ (or even _abstract_ :-) description of an
object/class/data type. Best examples that come to mind are things
in OOSC (Meyer) and Smalltalk, where (eg.) an abstract stack (or
queue, or state table, etc) is defined, which *requires* the
specifics to be added before it can be used - Eiffel's STACK is
useless by itself since you must have of stack of something, so
STACK [INT] or STACK [DRAWABLE] etc etc, and this "something" must
provide the methods required by the ADT (see Smalltalk's Set where
the objects being Set'ed (!) must provide == (or similar)).
I would say STACK is an ADT because it is an abstraction of stack,
and that INT (perhaps a bad choice since it is 'built in') is NOT.
This definition gets a bit murky when talking about (eg.) NUMBER
(a superclass of INT) - is it an ADT or an SDT (specific DT for
want of a better term) or something in between (my vote).
Therefore, I disagree that "OOL == ADT + inheritance" since that
means that there are SDTs - no specific classes are defined that
actually 'do the work' - like saying all you can have is
STACK [SET], when you really need STACK [INT] too.
--
-------------------------------------------------------------------------------
Matt Atterbury [matt@bacchus.esa.oz] Expert Solutions Australia, Melbourne
UUCP: ...!uunet!munnari!matt@bacchus.esa.oz "klaatu barada nikto"
ARPA: matt%bacchus.esa.oz.AU@uunet.UU.NET "life? don't talk to me about life!"
chandra@mrsvr.UUCP (B. Chandramouli) (11/15/90)
From article <1990Nov13.212012.3662@Neon.Stanford.EDU>, by craig@Neon.Stanford.EDU (Craig D. Chambers): > Inheritance of implementation seems like something that could be moved > out of the core language and into the programming environment, where > more flexible and adaptive code sharing/automatic programming could be > done without cramming a lot of functionality into a language > mechanism. > -- Craig Chambers Replacing Inheritance with Code sharing/Reuse facilities provided by the programming environment will work only for cases where you have access to the source code. You need inheritance provided by the language when you want to subclass from a class that is part of a standard class library provided by a vendor for which you have only the object code and not the source. chandra
bachww@motcid.UUCP (William W. Bach) (11/15/90)
flitter@atisun.dt.navy.mil (Lance Flitter) writes: > Greetings. I was wondering if someone would venture a good description >of the difference between Abstract Data Types and Objects. Is there a >difference? Is one a subset of the other? Abstract Data Types require barbarian procedures to rape the structure and plunder the data. Objects are well behaved and courteously ask each other to carry their intended wished. At least this is kind of what Dan Ingalls said back in 81... [ING81] Ingalls, Daniel H., "Design Principles Behind Smalltalk,"Byte, August 1981. Bud Bach -- Bud Bach ...!uunet!motcid!bachww
pcg@cs.aber.ac.uk (Piercarlo Grandi) (11/16/90)
On 14 Nov 90 16:18:52 GMT, chandra@mrsvr.UUCP (B. Chandramouli) said: chandra> From article <1990Nov13.212012.3662@Neon.Stanford.EDU>, by chandra> craig@Neon.Stanford.EDU (Craig D. Chambers): craig> Inheritance of implementation seems like something that could be moved craig> out of the core language and into the programming environment, where craig> more flexible and adaptive code sharing/automatic programming could be craig> done without cramming a lot of functionality into a language craig> mechanism. If only... But we are still stuck with linkers out of the black lagoon -- oops, sorry using technology from the fifties. Sixties technology (shared libraries, dynamic link resolution) is only now becoming better known. chandra> Replacing Inheritance with Code sharing/Reuse facilities chandra> provided by the programming environment will work only for chandra> cases where you have access to the source code. I would not be so sure. Reuse is not just about reusing source. That is mandatory only for inlining. Hey, after all a linker is a great tool belonging to the programming environment that provides _implementation_ reuse. What Craig Chambers is hinting at above is clearly smarter linkers, maybe with smarter libraries, e.g. something a little better than Ada's program library facility. chandra> You need inheritance provided by the language when you want to chandra> subclass from a class that is part of a standard class library chandra> provided by a vendor for which you have only the object code chandra> and not the source. Ahem. Really? I have ever more the impression that you have a very narrow definition of code sharing and reuse. -- 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
sakkinen@tukki.jyu.fi (Markku Sakkinen) (11/16/90)
In article <PCG.90Nov15184256@teachk.cs.aber.ac.uk> pcg@cs.aber.ac.uk (Piercarlo Grandi) writes: >On 14 Nov 90 16:18:52 GMT, chandra@mrsvr.UUCP (B. Chandramouli) said: > ... >chandra> You need inheritance provided by the language when you want to >chandra> subclass from a class that is part of a standard class library >chandra> provided by a vendor for which you have only the object code >chandra> and not the source. > >Ahem. Really? I have ever more the impression that you have a very >narrow definition of code sharing and reuse. Narrow definition? I did not see any claim of inheritance being everything one needs for code sharing and reuse. Please share (without making us inherit) some of your broad vision with us in the newsgroup and tell how inheritance in this sense can be practically replaced by other means in commonly available environments. Markku Sakkinen Department of Computer Science and Information Systems University of Jyvaskyla (a's with umlauts) Seminaarinkatu 15 SF-40100 Jyvaskyla (umlauts again) Finland SAKKINEN@FINJYU.bitnet (alternative network address)
holliday@csgrad.cs.vt.edu (Glenn Holliday) (11/18/90)
In article <4255@oasys.dt.navy.mil> flitter@atisun.dt.navy.mil (Lance Flitter) writes: > Greetings. I was wondering if someone would venture a good description >of the difference between Abstract Data Types and Objects. Is there a >difference? Is one a subset of the other? ADT provides a nice theoretic basis for playing with objects (we're talking model flavor of theory here). Eiffel fits closely with ADT theory. But I haven't seen anyone fitting inheritance into this. -- Glenn | holliday@csgrad.cs.vt.edu OR Holliday | glenn%bayberry@chado.fidonet.org OR | GHOLLID@access.nswc.navy.mil (Internet)
pcg@cs.aber.ac.uk (Piercarlo Grandi) (11/19/90)
On 16 Nov 90 06:16:12 GMT, sakkinen@tukki.jyu.fi (Markku Sakkinen) said:
sakkinen> In article <PCG.90Nov15184256@teachk.cs.aber.ac.uk>
sakkinen> pcg@cs.aber.ac.uk (Piercarlo Grandi) writes:
pcg> On 14 Nov 90 16:18:52 GMT, chandra@mrsvr.UUCP (B. Chandramouli)
pcg> said:
chandra> You need inheritance provided by the language when you want to
chandra> subclass from a class that is part of a standard class library
chandra> provided by a vendor for which you have only the object code
chandra> and not the source.
pcg> Ahem. Really? I have ever more the impression that you have a very
pcg> narrow definition of code sharing and reuse.
In other words, the C/Fortran idea of code dharing and reuse. One for
examples that excludes overloading, generics, etc... The assumption here
is that the fairly tight coupling of reuse of interface and of
implementation, as provided by inheritnace, is the only alternative.
sakkinen> Narrow definition? I did not see any claim of inheritance
sakkinen> being everything one needs for code sharing and reuse.
Well, he is saying that his goal is reuse of implementation as object
code, and that the only real technology for that is inheritance provided
by language; this is indeed a narrow view. There are other technologies;
for example dynamic linkers, library mechanisms a la Ada, etc... that
solve the code reuse without source problems. Also, note that (as
somebody else has already noted in this thread) you still need, in
many current environments, to do reuse of interface in source.
Instead, for example, Ada compilers are required to implement generics
without the source, and, at least partially, also interface reuse
(even if I do not like much how either feature is actually realized)
without source ("WITH p; PACKAGE q is NEW p.r(FLOAT);").
sakkinen> tell how inheritance in this sense can be practically replaced
sakkinen> by other means in commonly available environments.
It cannot, because as I had observed elsewhere the basic code reuse
technology in commonly available environments is the linker, and
commonly available linker designs go back to the fifties, as they are
based on static binding with component identification based on name
alone.
C++ 2.x uses the clever but sad trick of encoding type information in
the name of a component to fool linkers out of the fifties in doing
componenent resolution also on type ("type safe linkage" pah!).
Better solutions can be readily imagined, and have been implemented, as
long as commonly available linkers are thrown out of the window.
Inheritance is not the solution to reuse of implementation in object
form; better tools that support object form reuse directly are the
solution, as the original poster said:
From article <1990Nov13.212012.3662@Neon.Stanford.EDU>, by
craig@Neon.Stanford.EDU (Craig D. Chambers):
craig> Inheritance of implementation seems like something that could be moved
craig> out of the core language and into the programming environment, where
craig> more flexible and adaptive code sharing/automatic programming could be
craig> done without cramming a lot of functionality into a language
craig> mechanism.
I would venture as far as saying that inheritance is not the solution to
the reuse problem in general, and I seem to remember that you have a
paper on this subject :-).
--
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