Re: Static Polymorphism (Was Re: Naming of Tagged Types...)

[Matthew Heaney <matthew_heaney@acm.org>]

Brian Rogoff <bpr@shell5.ba.best.com> writes:

> I wonder why you would want to name the iterator type Stack_Iterator,
> since it seems to defeat the goals you describe for minimal rewriting
> when changing implementation?
>  
> For example, if you wanted to replace the stack with a deque, or a singly 
> linked list, you have to rename all occurrences of Stack_Iterator.

Yes, you would have to change the iterator, but you also have to change
all the stack instances, all the operation calls from Push to Add, the
selector from Get_Top to Get_Front, etc, etc, etc.

So I don't accept the premise of your argument.  The reason I chose a
stack in the first place is because I needed an ordered collection, that
has First-In Last-Out semantics.

If my requirements changed, and I needed a collection with different
semantics (say, I suddenly need First-In, First-Out) semantics, then
it's a Good Thing that I have to change all object declarations from
Stack_Type to Queue_Type.

If I didn't care about the collection being ordered, then certainly a
stack was _not_ the correct choice as my collection abstraction.  The
correct choice would be a Container_Type, which is an unordered
collection.

But to go from a stack to a list?  Why?  These are _really_ different
abstractions.  A stack is monolithic; a list polylithic.  The only time
I ever use a list is to implement a monolithic collection like a stack
or queue or container.  

Like an array, a list is a data structure that should only be used to
implement higher-level abstractions.  Never use a list (or array)
directly as a data structure.

> If you take a look at the collection library at
> http://www.best.com/~bpr/agl.html which is also "tagged-type-free",
> you'll see that I copied from the C++ STL, and named the iterators
> based on the kinds of iteration they support, Unidirectional,
> Bidirectional, Random_Access, etc., rather than on the data structures
> they iterate over. This gives you what you are calling "static
> polymorphism", and allows you to write many algorithms in terms of
> iterators alone.

I see your point of view; let me think about it for a while.  I only
implemented simple, one-way iterators (from front-to-back, or
top-to-bottom, etc). 

The implementation of the data structure can really limit what kinds of
iteration it supports.  For example, if you want to traverse a stack
from bottom to top, you really need to implement the stack using a
doubly-linked list, and, you have to have to a bottom pointer in
addition to the normal top pointer.

I'm not even sure some iteration schemes should be allowed.  For
example, does it make a lot of sense to have a random-access iterator
for a stack?  If so, then what's the point of using an ordered
collection?  And how do you implement a random-access iterator for a
stack implemented as a linked list?

Probably only one programmer in a thousand needs to randomly access a
stack.  In that case, he can just write a child to do that special thing
he needs.
 
> If you can tolerate reading C++, check out the STL, you'll find that you 
> share some design goals with its authors.

I'd really like to study the STL; I have the Stepanov book.  I'd bet I
could learn a lot of cool stuff.

But, as we have discussed in the past, the STL is a library highly
optimized for programming in C++.  Trying to apply STL ideas to Ada95
would be like trying to translate argot from French to English - how
well does it really translate?

In Ada95, a client can write a child package to extend the structure
with whatever custom operations the client requires.  Maybe that's the
better design choice, because it would keep the library simple, instead
of trying to anticipate all the myriad variations of iteration.