abstract data type 
Author Message
 abstract data type

Quote:

>What is the meanings of abstract data type?
>A brief description & example of it?

An ADT is a package that contains all the data and all the operations
that are required to handle variables of a new, user-defined type.
The inner workings (in particular, the data fields and any shared
internal functions) are cloaked from the caller.

"But this sounds like an object!" you cry.  Well, yes, it does, and
since ADTs have been around forever, you can understand why, to old
computer science types, OOP is just not that big a deal.  OOP adds
one new feature:

        class A { ... virtual function foo()... }
        class B inherits from A { ... foo() ... }
        class C inherits from A { ... foo() ... }
        variable D is a B.
        variable E is a C.
        variable F is a pointer to an A.

        function bar()
                if some-condition-or-other
                        put D's address into F
                else
                        put E's address into F
                call F->foo()

This may be hard to swallow ... and in fact, when I've posted
the essence of this before, it's started religious wars, for
reasons that baffle me ... but this is indeed the difference
between ADTs and OOP.  ADTs don't have the concept of inheritance
and virtual functions; that was The Suppposed Great Leap Forward.
(Was it Alan Kay and Smalltalk that first implemented it?)  
So for the sceptical, OOP is mostly a ripoff of existing ADT
technology, and it's not clear to them that the additional
power is either (1) very useful, or (2) worth the additional
complexity of having classes and inheritance and friends and
all the rest of the nightmare that has become modern-day software
engineering.  When you read the OOP literature, you will find that
almost all of the supposed benefits of objects (encapsulation,
method calls, etc) are actually just ripped off from ADTs.  And
note this very simple point, which may get me flamed yet again:
if your app doesn't use pointers to base-class objects that
define methods that are overridden in derived classes (like A
above) then you don't need OOP.  ADTs would be just fine.

Case in point: the best functional languages (ML, Haskell,
OCaml) have wonderful ADT facilities, and large-scale programs
written in these languages can be (and have been) very successful.
OCaml added OOP features; that's what the 'O' stands for in its
name ... and very few OCaml users even bother with the OOP stuff.
There is just very little need for it.  Programs tend to be cleaner
and easier to understand and so forth without it; and a good ADT is
easier to reuse than most 'objects', because you don't have so
much baggage to understand and try to fit in to your app .. the
superclasses and so forth.

Please don't think I'm an anti-OOP Nazi, because I'm not.  I use
OOP every day of my working life, and sometimes there are gains
there to be taken advantage of.  And of course it's all in how
you use it.  Yet, in the end, ADTs seem to me to be about as
indispensible as opposable thumbs, and objects add maybe 5% more.
Sometimes that little bit of extra power is worth the complexity
that you have to carry around inthe language and runtime .. and
sometimes it's not.

I can tell you this: a good ADT programmer could quickly come up
with ten ADTs for you that, if well-written, you could take and use
right away: String, List, Map, Graph, Tree, ...  But a good OOP
programmer who buys into the inheritance concept would have a
harder time, and would probably make architectural tradeoffs (like
maybe making a generic Container base class, then deriving List
and Map from it) and then you'd have to understand all the ins and
outs of those tradeoffs, and maybe you would use his stuff, and
maybe not ... and if not, you'd probably have to toss the whole
mess.  Just like C++ programmers typically do with other peoples'
class libraries, until management lowers the cannon and hauls it
up to their desks and says Thou Shalt Use MFC (or Tools.h or STL or
The Booch Components or Whatever).  ADTs are lightweight and tend
to be handed around like beer at a party.  If you like one, you use
it, nothing complicated about that.  If you improve it, then others
can import it into their development process easily.  Clean, simple.

Another case in point: take a look at Limbo, the new language designed
by Dennis Ritchie (author of C) for Lucent.  You think Ritchie knows
anything about programming languages?  In Limbo (part of Inferno) he's
added some cool stuff to the language, including interprocess
communication, strings, slices of arrays, and so forth .. but there
isn't a single OOP feature.  There is, however, extensive and explicit
support for ADTs.

Okay ... let the flames begin.

Dwight



Mon, 30 Jul 2001 03:00:00 GMT  
 abstract data type

Quote:

> ... but this is indeed the difference
> between ADTs and OOP.  ADTs don't have the concept of inheritance
> and virtual functions; that was The Suppposed Great Leap Forward.

From a purely technical view: yes.

But this difference is IMHO the *big* one. When you
are starting to build a large system, you first try to modellize
it by describing the objects, to what classes they
belong and how they relate. So let's suppose you are doing
such a description in free speech. Later you are listening
to the recording of that description. I would bet you'll
find yourself having done specialization and generalisations
over and over again. And there is no chance to avoid this because
this IMHO is the main principle of humans to handle the
descriptions of complex systems.

If a language doesn't have a feature to support this pricipal
of generalisations/specialization like inheritance with
virtual functions, it becomes very hard to translate the
output of the analysis phase into an implementation, which
reflects that analysis.

Quote:
> Yet, in the end, ADTs seem to me to be about as
> indispensible as opposable thumbs, and objects add maybe 5% more.
> Sometimes that little bit of extra power is worth the complexity

Ok, this "little bit of extra power" maybe worth the flame war :-)

Greetings,
Michael

--
Michael Schneider



Tue, 31 Jul 2001 03:00:00 GMT  
 abstract data type

: > ... but this is indeed the difference
: > between ADTs and OOP.  ADTs don't have the concept of inheritance
: > and virtual functions; that was The Suppposed Great Leap Forward.

: From a purely technical view: yes.

: But this difference is IMHO the *big* one. When you
: are starting to build a large system, you first try to modellize
: it by describing the objects, to what classes they
: belong and how they relate. So let's suppose you are doing
: such a description in free speech. Later you are listening
: to the recording of that description. I would bet you'll
: find yourself having done specialization and generalisations
: over and over again. And there is no chance to avoid this because
: this IMHO is the main principle of humans to handle the
: descriptions of complex systems.

: If a language doesn't have a feature to support this pricipal
: of generalisations/specialization like inheritance with
: virtual functions, it becomes very hard to translate the
: output of the analysis phase into an implementation, which
: reflects that analysis.

But inheritance is only one way to support generalization/specialization.
Specialization can be achieved through separation of interface from
implementation as with SML's structures and signatures, or through Haskell's
module system.

Generalization can be achieved, and some would argue should be achieved,
through composition and not through inheritance (due to the static nature of
inheritance and the inevitable coupling between super and subclasses).

Dan Russell
Kingston University



Tue, 31 Jul 2001 03:00:00 GMT  
 abstract data type


Quote:
>But inheritance is only one way to support generalization/specialization.
>Specialization can be achieved through separation of interface from
>implementation as with SML's structures and signatures, or through Haskell's
>module system.

Yes, exactly.  The particular type of generalization that is OOP just
does not seem so powerful, to this user, in practice as to warrant the
complexity in language ... and in thinking ... that OOP support tends
to entail.  ML modules and functors are enough, when combined with
polymorphic typing and the boxing that this entails.  Ocaml even does
cross-module inlining to make the pain of abstraction easier to bear.

Quote:
>Generalization can be achieved, and some would argue should be achieved,
>through composition and not through inheritance (due to the static nature of
>inheritance and the inevitable coupling between super and subclasses).

And it is just this coupling that defeats much of the supposed benefit
of OOP.  You end up having to know a great deal more about the super-
class than you want to know, when you derive a subclass from it.  You
have to, because you are extending it, and you need to know just what
is in it and when, during construction, for instance.  Just these kind
of issues tend to make the nice pretty pictures of the class hierarchy
actually quite messy in practice, just to get thing to run fast enough
to be usable for real programs.  C++ is of course a disaster in this
area, with private data being listed in typical class header files,
thus forcing recompilation of all users when the implementation
changes ...

Dwight



Wed, 01 Aug 2001 03:00:00 GMT  
 abstract data type
I think I'm about to expose my idiocy for all to see, but in the
interests of targeting a less 'academic' set of users, perhaps, I need
to ask:

I'm *very* familliar with the OOP structure as defined by python
(quite possibly one of the best RAD languages in existance).  I'm
becoming quite fond of Haskell, as its pure functional orientation and
lazy evaluation are beautiful things to behold (even if Monads are
abstruse and impenetrable, oftimes, and the state of the interpreters
and compilers on Alpha/64bit machines is loose, and there's little to
no discussion anywhere outside of abstract whitepapers about using
things like STArray ... but I digress).  Where my thinking fails is
understanding how to map my understanding of Pythonic Objects to
Haskell ADTs and modules.

For example, I have a set of genetic algorithm operations classes in
Python.  'Classes' (insomuch as Python classes can be refered to as
such; in my mind, they are descriptions of objects ...) exist at the
top level in Python two Python modules, allele.py (containing the
Allele classs, describing the various kinds of alleles, logically
enough) and farm.py (containing the actual engines which can
execute/evaluate alleles).  Within allele.py, there is one base
functional Allele class, and several classes which inherit /from/
Allele with slightly different functions in place of the basic
methods, for instance, Allele (base) only supports single-point
crossover while DoubleCrossover is a mix-in class which, when
inherited from by an object *before* Allele, overrides the
Allele.crossover method with one which does double-point crossover.
Allele also contains overrides for the '+' operator when its handed
two Allelle objects which invokes the 'crossover' method and returns a
new Allele.  There is, additionally, an Allele.mutate method which has
several mix-in classes which do different kinds of mutation and which
can be inherited from, so that if you wanted x to be an Allele with
two-point crossover and Gaussian mutation you'd say:

Quote:
> from allele import Allele, DoubleCrossover, Gaus{*filter*}ate
> class myAllele (DoubleCrossover, GaussMuste, Allele)

> x = myAllele()

Now, given that structure, how would one impliment a similar result in
Haskell with ADTs, modules and type classes?  Knowing how to actually
*use* such things together to solve real problems doesn't seem to be
treated anywhere in a real sense.  There seems to be a strong lack of
'cookbook-style' documentation for Haskell; much of it concentrates on
high-level discussions of program proofs and fascination with
structure rather than 'how to solve problems.'  In this, I prefer
Thompson's book to Bird's, though Bird's has much more on the
mechanics of the language.

--

Sometimes you bleed just to know you're alive.
====================================================================
"Robert Smith is a gorgeous man, better than myself in nearly every
way, I think.  Chiseled from Florentine marble, smart as a whip,
rich as Croesus, strong as a bear, the ladies love him.  Me?
Chiseled from sourdough batter, smart as a rod puppet, strong as a
gopher, rich as a novelty salesman, the ladies whisper amongst
themselves 'Who is that icky guy?'  Still, I have ... oh, who am I
kidding?  There's nothing to mitigate it."



Thu, 02 Aug 2001 03:00:00 GMT  
 abstract data type

Quote:

>Where my thinking fails is
>understanding how to map my understanding of Pythonic Objects to
>Haskell ADTs and modules.

Yes, python is quite wonderfully OOP.  But there is a price to pay
for the power and flexibility that you demonstrate: it is slower than
molasses.  Python is, as you know, a generalized, interpreted version
of Modula-3, and the method lookups are done by searching hash tables
at runtime -- so you really do get marvelous inheritance and all that.
If you're looking for strong functional benefits without giving up
OOP completely, you might look at Objective Caml - it's got real
objects and inheritance and polymorphism and all of that, but in a
functional framework rather than a procedural framework.... much
more OOP than Haskell, I think.  

You may find, though, that most experienced functional programmers
use modules and functors as their ADTs, and they don't miss OOP very
much.  OOP comes with baggage - runtime, as with python, or source-
level, as with C++, when OOP tries to be fast - and its advantages
are debatable over ADTs as implemented in standard procedural
languages.  When you then move into the functional realm and find a
lambda-oriented language (like Ocaml) that is lightning fast and has
functors to boot, including things like cross-module inlining and a
very fast native-code compiler, you don't find yourself missing OOP
very much.  Most of us Ocaml users don't bother with the object stuff,
because we don't need to.  Its ADT implementation is so exquisite,
and its expressivity is so profound, that staying within its
functional paradigm doesn't feel like a burden ... even for containers
that might be part of the usual OOP inheritance tree, or of an STL-
like generic programming framework.

Are functional languages like ML and Ocaml and Haskell God's gift to
programmers?  Well ... yes ... but I still write a lot (actually, a
heck of a lot) of Perl and C++ code.  You just can't beat Perl in
its problem domain.  Or python .. what an extraordinary language.
Makes you wish that Modula-3 hadn't bitten the dust, because then
you could have used a python implementation as a rough, quick-and-
dirty cut, and translated to Modula-3 if you wanted speed.  But
even without that option, python is about as good as it gets for
scripting, when speed isn't an issue.

I ramble.  I'm tired, I'm thirsty, and it's your turn ...

Dwight



Thu, 02 Aug 2001 03:00:00 GMT  
 abstract data type
On Sun, 14 Feb 1999 03:57:24 GMT, Dwight VandenBerghe

Quote:

>for the power and flexibility that you demonstrate: it is slower than
>molasses.  Python is, as you know, a generalized, interpreted version

Actually, you can squeeze some pretty amazing speed out of Python by
intelligent coding and the use of its more functional paradigms, but
it doesn't compete with raw C speed.  It doesn't try to, it simply
subsumes the slow bits rewritten in C as modules and away you go,
using them from within Python glue.  But I'm sure I don't need to
evangelize Python here; several posters to clf are equally if not more
active in clp.  The point I mean to make is that speed isn't my
concern, there is always a way to speed things up, to take the 10% of
the code sucking 90% of the time and make it arbitrarily fast.  What
I'm interested in is the understanding of how to express algorithms
and entities in various ways.

Quote:
>functional framework rather than a procedural framework.... much
>more OOP than Haskell, I think.  

Perhaps, but I already have an OOP 'toolkit' in my head; what I
want/need to learn is how, within Haskell, say, to make use of ADTs
and class types to do what I already know how to do using OOP
constructions.  Post I replied to originally suggested that ADTs are
at the root of OOP, and I intuitively grasp that.  Its all the rest of
the claims that I'm a bit hazy on, and I seek clarity.

Quote:
>because we don't need to.  Its ADT implementation is so exquisite,
>and its expressivity is so profound, that staying within its
>functional paradigm doesn't feel like a burden ... even for containers
>that might be part of the usual OOP inheritance tree, or of an STL-
>like generic programming framework.

Well, yes, maybe, but I'm your typical Engineer: show me, don't wax
eloquent over the advantages without displaying your wares, kind sir.
I provided an example in my post for a reason, because it gives a
concrete starting-point for what I understand and a sample of the sort
of things I'm trying to do.  Show me, then, how to do what I do with
ADTs and such functional power as might be brought to bear.

Quote:
>even without that option, python is about as good as it gets for
>scripting, when speed isn't an issue.

And even for larger things than scripting; Python's my
swiss-army-knife.  Scheme used to be, once upon a time (as scary as
some might find that).

--

Sometimes you bleed just to know you're alive.
====================================================================
"Robert Smith is a gorgeous man, better than myself in nearly every
way, I think.  Chiseled from Florentine marble, smart as a whip,
rich as Croesus, strong as a bear, the ladies love him.  Me?
Chiseled from sourdough batter, smart as a rod puppet, strong as a
gopher, rich as a novelty salesman, the ladies whisper amongst
themselves 'Who is that icky guy?'  Still, I have ... oh, who am I
kidding?  There's nothing to mitigate it."



Thu, 02 Aug 2001 03:00:00 GMT  
 abstract data type

Quote:

>I think I'm about to expose my idiocy for all to see, but in the
>interests of targeting a less 'academic' set of users, perhaps, I need
>to ask:

ignorance /= idiocy

Quote:
>For example, I have a set of genetic algorithm operations classes in
>Python.  'Classes' (insomuch as Python classes can be refered to as
    ...
>Now, given that structure, how would one impliment a similar result in
>Haskell with ADTs, modules and type classes?                        

I'm ignorant of genetic programming, but am aware of a package, PolyGP,
that's writen in Haskell, see this page:
  http://www.cs.ucl.ac.uk/staff/T.Yu/research.html
   (there's a slideshow, some papers, and a tar file).

A web search also turns up a Master's thesis by Mans Vestin:
http://www.cs.chalmers.se/~patrikj/poly/
  (the paper doesn't seem to address double crossover, though).

The answer to your question may be "it can't be done in Haskell"; I don't
know.  One aspect that could be difficult to model is the *before*
ordering in the inherited/mixedin classes in your example.

John Atwood



Thu, 02 Aug 2001 03:00:00 GMT  
 abstract data type

Quote:

>The point I mean to make is that speed isn't my concern,
>there is always a way to speed things up, to take the 10% of
>the code sucking 90% of the time and make it arbitrarily fast.

This is a wildly optimistic view.

The 90-10 rule is pretty accurate for programs that no-one has
tried to make run fast.  But when you're dealing with large programs,
once you fix the obvious problems in the few hot-spots, you end up
with a much flatter profile, and it becomes very hard to improve
performance signficantly.

--

WWW: <http://www.cs.mu.oz.au/~fjh>  |   but source code lives forever"



Fri, 03 Aug 2001 03:00:00 GMT  
 abstract data type

Quote:


> >The point I mean to make is that speed isn't my concern,
> >there is always a way to speed things up, to take the 10% of
> >the code sucking 90% of the time and make it arbitrarily fast.

> This is a wildly optimistic view.

> The 90-10 rule is pretty accurate for programs that no-one has
> tried to make run fast.  But when you're dealing with large programs,
> once you fix the obvious problems in the few hot-spots, you end up
> with a much flatter profile, and it becomes very hard to improve
> performance signficantly.

Amen to that. In one significant example I've looked at, the 90-10 rule
actually _was_ pretty close to the mark. But that approximately 10%
consisted of several hundreds of procedures, with no evident 'kings'
among them.

                        Thomas
--

Software Architecture Research Centre           avoid +junk to mail me
Ericsson Utvecklings AB, Open Systems
             A short-liv'd reptile in the dust of earth.



Fri, 03 Aug 2001 03:00:00 GMT  
 abstract data type

Quote:

> Within allele.py, there is one base
> functional Allele class, and several classes which inherit /from/
> Allele with slightly different functions in place of the basic
> methods, for instance, Allele (base) only supports single-point
> crossover while DoubleCrossover is a mix-in class which, when
> inherited from by an object *before* Allele, overrides the
> Allele.crossover method with one which does double-point crossover.
> Allele also contains overrides for the '+' operator when its handed
> two Allelle objects which invokes the 'crossover' method and returns a
> new Allele.  There is, additionally, an Allele.mutate method which has
> several mix-in classes which do different kinds of mutation and which
> can be inherited from, so that if you wanted x to be an Allele with
> two-point crossover and Gaussian mutation you'd say:

> > from allele import Allele, DoubleCrossover, Gaus{*filter*}ate
> > class myAllele (DoubleCrossover, GaussMuste, Allele)

> > x = myAllele()

> Now, given that structure, how would one impliment a similar result in
> Haskell with ADTs, modules and type classes?

Overridable methods can be regarded as an implicit higher-order argument
to the object. The idea is to replace inheritance -- mixins in
particular -- with parameterisation over functions. I.e. your Allele
module will have a constructor function that takes suitable crossover
and mutate functions as arguments. Instead of mixins, a set of those
functions is supplied by the module. Using curried notation you could
then say

        makeMy = make doubleCrossover gaus{*filter*}ate

Of course this gets complicated when you have more than just two
overridable methods. However, some of these methods might only be needed
by a single other method each, so that abstraction can be done on a
finer level.

I admit that many OO designs are much too complex for this kind of
transformation to be handy. But while one might take this as a proof
that OO really buys you something, I would argue that the opposite is
true: OO encourages designs that are too involved to remain
understandable and to be trusted. You get away without doing proper
decomposition. I regard this as a serious drawback of OO's flexibility.

Quote:
> There seems to be a strong lack of
> 'cookbook-style' documentation for Haskell; much of it concentrates on
> high-level discussions of program proofs and fascination with
> structure rather than 'how to solve problems.'

You may be right about that. Same seems to be true for FP in general.

        - Andreas



Sat, 04 Aug 2001 03:00:00 GMT  
 abstract data type
On Tue, 16 Feb 1999 18:07:41 +0100, Andreas Rossberg

Quote:

>Of course this gets complicated when you have more than just two
>overridable methods. However, some of these methods might only be needed
>by a single other method each, so that abstraction can be done on a
>finer level.

And, in fact, in this case there are upwards of five overridable
methods, which probably wouldn't be impossible to use a factory
function to forge, but it certainly becomes unwieldy, especially given
that Haskell (in particular) doesn't have default argument support, as
yet.

Quote:
>I admit that many OO designs are much too complex for this kind of
>transformation to be handy. But while one might take this as a proof
>that OO really buys you something, I would argue that the opposite is
>true: OO encourages designs that are too involved to remain
>understandable and to be trusted. You get away without doing proper
>decomposition. I regard this as a serious drawback of OO's flexibility.

I don't think I can buy that argument, based on the fact that this
"proper decomposition" seems to have very little connection to the
realities of actually engineering software and less to do with
academic approaches to writing software.  The OO can express an
algorithm 'intuitively' in a way that its easy to write, I don't jump
from that to it being 'a serious drawback in OO's flexibility;'
perhaps I'm simply not schooled properly.

And, of course, this has nothing to do with ADTs and how to use them
to express such structures, which would address the original poster's
contention that ADts and proper functional deconstruction could do
anything OOP can do, clearer and more conscisely.  Thus I presented a
real problem from something I'm working on.  That you've responded
that many OO designs are too complex to respond well to the kind of
decomposition you provided does not support the original poster's
point and I remain unsatisfied and, sadly, yet ignorant on this point.

Quote:
>You may be right about that. Same seems to be true for FP in general.

This may be why you see much more use on non-FP languages in the
field, because of a lack of tools with which to teach how FP languages
can be used, not just talked about.

--

Sometimes you bleed just to know you're alive.
====================================================================
"Robert Smith is a gorgeous man, better than myself in nearly every
way, I think.  Chiseled from Florentine marble, smart as a whip,
rich as Croesus, strong as a bear, the ladies love him.  Me?
Chiseled from sourdough batter, smart as a rod puppet, strong as a
gopher, rich as a novelty salesman, the ladies whisper amongst
themselves 'Who is that icky guy?'  Still, I have ... oh, who am I
kidding?  There's nothing to mitigate it."



Sun, 05 Aug 2001 03:00:00 GMT  
 abstract data type

Quote:

>> There seems to be a strong lack of 'cookbook-style' documentation
>> for Haskell;
> You may be right about that. Same seems to be true for FP in general.

I have previously lamented the lack of a "Software Patterns in
Haskell"-like source, which I think is what you're asking for here.

If you program OO (and preferably C++), there's a rather rich set of
solution designs that you can model your code around, giving you a
terminology to describe your designs as well as the general solution.

Now, I suspect working with FP is significantly different from working
with procedural/imperative/OO languages that we need our own set of
patterns -- has anybody retrofitted OO patterns onto e.g. Haskell with
any success, btw?

The difficulty then becomes how to identify problem classes, and their
general solutions.  Here's an example pattern, totally off the top of
my head, and probably ill chosen and trivial, but something I used in
a population simulator at one time:

---8<--
Pattern:  Iterative Sequence
Use when: you wish to find a solution for an iterative function,
        ie. a function depending on its previous values
        X_n = f(X_(n-1), X_(n-2)...)

Solution:
        * design the function f as above, and the initial value i

        * apply this function recursively to a list starting with i,
          like so
                solution = i:(map f solution)

Examples:
        Newton iteration [...]
        [...]

Variations:
        * f is a function of multiple variables [...]
        * termination on convergence with some accuracy [...]
        * changing f under way (eg. a predator is suddenly introduced)
        [..]

---8<--

So - what classes of problems are solved by FP, and how?  Your turn! :-)

-kzm
--
If I haven't seen further, it is by standing in the footprints of giants



Sun, 05 Aug 2001 03:00:00 GMT  
 
 [ 16 post ]  Go to page: [1] [2]

 Relevant Pages 

1. Abstract Data Types book

2. Abstract Data Type problem

3. Abstract data types in Haskell

4. Abstract Data Type in FP

5. Abstract Data Types book

6. Abstract data types and uniform treatment of opertors

7. abstract data type linked list

8. abstract data types and structures

9. Abstract data types and structures

10. Abstract data types: FP and OOP?

11. Abstract DAta Types

12. Abstract Data Types book

 

 
Powered by phpBB® Forum Software