algorithms and ADTs (was Re: efficient idiomatic queue?)

[Alex Martelli]

"Aahz Maruch" <aahz at panix.com> wrote in message
news:a22rj5$bs6$1 at panix3.panix.com...
> In article <a20osj$78u$1 at serv1.iunet.it>, Alex Martelli <aleax at aleax.it>
wrote:
> >
> > [...]
>
> Um, what's an ADT?

Sorry -- I should not have used a three-letter-acronym (TLA) without
expanding it at least once, no matter how well-known I could assume
it to be to the specific poster I was responding to.

ADT = "Abstract Data Type".  When teaching algorithms and data
structures, one approach is to "implement" an algorithm in terms
of abstract operations on some underlying data type, each operation
defined in terms of its just-as-abstract semantics and performance
characteristics.  The issue of *implementing* an ADT in concrete
terms is then neatly separated from that of *using* it.  As far as
I know the original idea came from abstract algebra, where one
does much the same with abstract structures -- one separates the
issue of "what can I prove about a monoid" (the latter being
abstractly defined in terms of its axioms) from the issue of
proving whether a given algebraic structure is indeed a monoid.

Of course, ADT's also mesh well with the concept of separation
between interface and implementation as used in actual software
design.  Performance characteristics are rarely specified in
the latter case, but there are important exceptions (for example,
C++'s Standard Library does have O(N) performance specs for
various operations as part of its overall specifications).


Alex