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

[Brian Rogoff <bpr@shell5.ba.best.com>]

On Thu, 6 Aug 1998, Matthew Heaney wrote:
> 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.

Fortunately, Ada has renaming, subtypes, 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.

Thats a stronger argument. An STL like solution is to provide some sort of 
adaptor on a collection to give the semantics you want. I guess when I'm 
using Push/Pop/Get_Top/etc I'm not thinking of using iterators anyways,
but I'm directly dealing with a stack and its elements.

... snip ...

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

I guess I rarely use data structures directly now anyways :-), but in any
case I am pretty much in agreement with you here.

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

No. I'd provide a stack adaptor (STL terminology) and apply that to a 
given collection to provide the desired stack semantics. I haven't
finished writing all of the stack/queue/etc. adaptors, since so far this 
AGL is a one man spare time show (remember, I'm really just a lowly 
C/Verilog/VHDL programmer) and I have limited time, but I think you can
see this isn't conceptually hard.

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

You don't.  

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

As we've dicussed before, you don't translate "word for word", even
between very similar languages, or you get oddities like 

"Can you him tomorrow pick up?" for "Kun je hem morgen afhalen?"

you have to have a sense of what translates and what doesn't. The main 
ideas of the STL translate quite well to Ada 95, some concepts don't need 
to be translated in the same way, and so on. Remember, the STL is based on 
earlier attempts in Scheme and Ada 83. Also, very similar libraries were 
proposed by Bishop (IEEE Transactions on SW Eng v16n4 1990 p389-402) in 
Ada 83, and I'm also stealing ideas from other sources (Stephen Leake,
take a bow), and adding new touches all the time as my knowledge of Ada 
95 deepens. But the proof of the pudding is in the source code, so if you
have some question about whether the library maps well to Ada, see the 
source.

-- Brian

PS: Its working on iteration libraries that made me something of a 
    downward-closure fanatic. Sure, I can do lots with generics, but 
    a genuine downward closure feature in Ada would make lots of code 
    less clunky.