Re: Queue

[Brian Rogoff <bpr@bpr.best.vwh.net>]

I thought I replied, but my reply didn't even show up on Google groups.
&@#$ing computers!

On Wed, 28 Nov 2001, Mats Karlssohn wrote:
> Brian Rogoff wrote:
> %<
> > Interestingly enough, there was a proposal to do something like this
> > (very much like the C++ STL) in Ada circa 1990. I mentioned it loooong
> > ago, maybe in 1997 when there was some discussion of the STL here. I
> > forget the author's name, but she was a prof at some South African
> > university. What's interesting to me is that this was completely
> > independent of the STL line of work. I can dig up the ref if anyone is
> > interested.
>
> Please do! I'd like to read that.


@article{ bishop90effect,
    author = "J. M. Bishop",
    title = "The Effect of Data Abstraction on Loop Programming
Techniques",
    journal = "IEEE Transactions on Software Engineering",
    volume = "16",
    number = "4",
    publisher = "IEEE Computer Society",
    address = "Washington, DC",
    pages = "389--402",
    year = "1990"
}

> > Doing an STL like library in Ada is certainly possible, but it will never
> > fit as snugly with Ada as the STL does with C++, for a number of reasons.
>
> I haven't really dug into this subject, would you care to expand on
> this issue and perhaps suggest ways to make it fit better with Ada.

Well, for one thing pointer traversal using ++, --, etc is a common idiom
in C and C++, and since those operators, and [], are overloadable in C++,
STL code for traversing an ADT looks like low level pointer bumbing code.
C also has that ability to refer just beyond the end of an array and that
notion maps well to the one off the end iterator value.

The excessive instantiations that you need in an Ada version of the STL
become ponderous IMO. I believe this is a fundamental problem with Ada
generics, and perhaps even a fundamental issue in statically typed
languages, namely, when do we prefer explicit (manifest?) types and when
do we prefer implicit types. My own opinion is that I'd like a language
with both. Ada has only the first, and while modern high level languages
(think ML and Haskell here) provide both I'm a bit unsatisfied with the
way it all fits together (not to drift too far, but I'd like something
like Haskell's type classes and not just ML's universal style of
polymorphism, *and* I want a decent module system). I guess I'm not meant
to be happy with any programming language :-).

One of the things that annoys me about Ada is the fact that there is a lot
of nice notation that I, the programmer, can't change. It would be nice if
there were a more generalized notion of 'First and 'Last, since that's
what Ada programmers would like to use in an Ada "STL". If you just map
the STL concepts onto Ada directly, using, say, Incr, Decr, Pred, Succ
Get_Value, Set_Value, etc., instead of the C shorthand, Ada programmers
will still complain that the resulting library doesn't "look like" Ada.
Sorry, nothing can be done about that.

Just so I don't sound entirely negative, generic formal package
parameters, and the signature trick, really make something like the STL,
or Bishop's approach, a lot cleaner in Ada 95 than was possible in Ada 83.
It also makes the STL easier to understand, since you can express the
notion of "iterator category" (I think that's what Alex Stepanov called
it, I can't remember since it was a few years ago) pretty directly with
a few signatures (Forward_Iterator_Sig, Bidirectional_Iterator_Sig, etc.).

Sorry for rambling, I guess I'll ramble off now...

-- Brian