Re: Problem with Booch iterators

[mheaney@on2.com (Matthew Heaney)]

Simon Wright <simon@pushface.org> wrote in message news:<x7visz0ps4z.fsf@smaug.pushface.org>...
> mheaney@on2.com (Matthew Heaney) writes:
> 
> > You have identified what I consider to be a serious flaw in the
> > Booch Components.  The problem is that record components must be
> > definite; unconstrained subtypes must be given a constraint.
> > 
> > The BC iterator factory functions return Iterator'Class, which is
> > indefinite.  You cannot use T'Class as a record component.
> 
> But then, given a non-STL mindset, why would you want to? 

First of all, it is incorrect to associate "definite iterator subtype"
with "STL."  The issue of definite vs. indefinite subtypes has nothing
to do with STL vs. non-STL.

Second of all, this is the wrong question to ask.  It's not up to the
library designer to require that the library user give his reasons for
wanting a definite subtype.  It's up the the library designer to give
his reasons for making the iterator subtype indefinite.

In other words, the question is "Why would you, the library designer,
not want to provide an iterator subtype that is definite?"

The library designer cannot possibly anticipate all the myriad things
a user will do with the library.  It is like asking "What is the set
of all compilable Ada programs?" or "What is the set of all
grammatically correct English sentences?"  You don't know, and you
can't know, so don't bother trying.

It is far better to simply design the library to be flexible, and then
allow the user to do as he pleases, without making a moral judgement
about what is "good."  The biggest favor a library designer can do for
a library user is to stay out of his way.


> In the STL,
> iterators are related to the notion of pointer; in the BCs, they
> aren't (to anything like the same extent).

Iterators are a way of getting at the elements in a container.  In the
STL, iterators have the same syntax as a pointer.

But we're talking about definite vs. indefinite subtypes here, which
is an orthogonal issue.  The fact that BC iterators aren't "related
to" pointers may be true (I don't happen to think so, but that is
another matter), but that's not a reason why the BC iterator type is
indefinite.


>  In the original BCs,
> iterators were limited too, so you had to have a concrete iterator per
> concrete container type .. well, actually, for half of them (the
> leaves were foo_Iterator, foo_Non_Iterator).

One reason for having definite subtypes (here, non-abstract
non-classwide iterator types) is that you don't have a dispatching. 
Obviously, if I know the specific type of the container, then I should
be able to ask the container for an iterator, whose subtype is
definite.

The only time it would make sense for a container to return an
indefinite iterator subtype is if this were a Factor Method pattern,
and this is a dispatching operation, e.g.

  procedure Print (Stack : Stack_Type'Class) is
     Iter : Iterator_Type'Class := 
        Dispatching_Factory_Method (Stack);
  begin
     ...

But we're talking about a factory "function" for iterators, not a
factory "method" (the former doesn't dispatch, the latter does).  In
other words, we have something like this:

   Stack : Stack_Types.Unbounded.Stack_Type;

   Iter : Iterator_Type := Nondispatching_Factory_Function (Stack);

In this case, it is entirely NOT appropriate for the factory function
to return anything other than a definite, non-abstract, specific type.

 
> I would like to know just how many real C++ programs use iteration
> ranges other than begin() .. end().

One obvious case is naming the range of "equivalent" keys in a sorted
multiset or multimap.  Another example is sorting a sequence
container, and then manipulating the "equal" items, which are
guaranteed to be adjacent.

Another example is finding items in a sequence container: you want to
start the next search starting from the position returned by the
current search (it would be horribly inefficient --and probably
wouldn't even work-- to have to start from the beginning of the
sequence each time you do a search).

But it doesn't really matter, because you can iterate over the entire
container using a range (as in your question), but the opposite is not
true: if you only allow iteration over a container, then there's no
way to iterate over a subrange.

Yes, a design guideline is that you should design around the common
case (and let's assume for the sake of argument that that's iteration
over the entire container range), but here that guideline is in
tension with our goal that the library be flexible.

 
> > > It also suggests that types of arguments of subrountines should be
> > > changed from Iterator'Class to the appropriate concrete types.
> > 
> > Yes.
> 
> Well, in Charles I guess that Iterator'Class is a pretty meaningless
> concept.

If dynamic polymorphism for containers were needed by a user, then he
could implement that himself using an Adapter pattern.  Dynamic
polymorphism does NOT need to be provided by the library itself.