Problem with Booch iterators

Problem with Booch iterators

[Victor Porton]

There are a serious misdesign of Booch iterators:

Declaring a record component of type Iterator'Class,
I get error "unconstrained subtype in component declaration".

So for every non-abstract collection type, a concrete iterator
type should be visibly declared. It also suggests that types of
arguments of subrountines should be changed from Iterator'Class
to the appropriate concrete types.

Simon, why you've used Iterator'Class everywhere?

Re: Problem with Booch iterators

[Simon Wright]

porton@ex-code.com (Victor Porton) writes:

> There are a serious misdesign of Booch iterators:
> 
> Declaring a record component of type Iterator'Class,
> I get error "unconstrained subtype in component declaration".
> 
> So for every non-abstract collection type, a concrete iterator
> type should be visibly declared. It also suggests that types of
> arguments of subrountines should be changed from Iterator'Class
> to the appropriate concrete types.
> 
> Simon, why you've used Iterator'Class everywhere?

Given the way the BC iterators work, I don't know what good having
iterators in records is going to do you.

I don't like the idea of unbound iterators floating around (I suppose
though it's no worse than a Text_IO.File_Type).

I guess I don't see what it is you're trying to do with the BCs that
is causing you so much grief.

Since there are at least 3 projects using the BCs to earn themselves
money (even if I don't see any of it, except indirectly) I won't make
backwards-incompatible changes; and I'm reluctant to add operations
and features, unless it can be done in a way which doesn't increase
the footprint. I would be more inclined to remove things .. BC_Lite, I
guess.

Re: Problem with Booch iterators

[Victor Porton]

In article <x7vheeq34xd.fsf@smaug.pushface.org>,
	Simon Wright <simon@pushface.org> writes:
> porton@ex-code.com (Victor Porton) writes:
> 
>> There are a serious misdesign of Booch iterators:
>> 
>> Declaring a record component of type Iterator'Class,
>> I get error "unconstrained subtype in component declaration".
>> 
>> So for every non-abstract collection type, a concrete iterator
>> type should be visibly declared. It also suggests that types of
>> arguments of subrountines should be changed from Iterator'Class
>> to the appropriate concrete types.
>> 
>> Simon, why you've used Iterator'Class everywhere?
> 
> Given the way the BC iterators work, I don't know what good having
> iterators in records is going to do you.

Iterator ranges, see my other message.

> I don't like the idea of unbound iterators floating around (I suppose
> though it's no worse than a Text_IO.File_Type).

What is "unbound iterator"?

> Since there are at least 3 projects using the BCs to earn themselves
> money (even if I don't see any of it, except indirectly) I won't make
> backwards-incompatible changes; and I'm reluctant to add operations
> and features, unless it can be done in a way which doesn't increase
> the footprint. I would be more inclined to remove things .. BC_Lite, I
> guess.

Changing Iterator'Class to concrete iterators in some subrountines' 
specification does not add real incompatibility: in any case passing
a wrong iterator type is a mistake.

Well, to archive good backward compatibility we need something like
Concrete_Iterator'Class in subrountines' specs. Automatic type
conversions will do the thing we need.

Re: Problem with Booch iterators

[Ted Dennison]

porton@ex-code.com (Victor Porton) wrote in message news:<3dcd00f3$0$307$bed64819@news.gradwell.net>...
> Declaring a record component of type Iterator'Class,
> I get error "unconstrained subtype in component declaration".

I'm missing something. Booch aside, is there are situation where you
could *ever* do that? If you want a field that can contain an object
of any type within a class, you have to use a pointer, don't you?

Re: Problem with Booch iterators

[Matthew Heaney]

porton@ex-code.com (Victor Porton) wrote in message news:<3dcd00f3$0$307$bed64819@news.gradwell.net>...
> There are a serious misdesign of Booch iterators:
> 
> Declaring a record component of type Iterator'Class,
> I get error "unconstrained subtype in component declaration".

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.

The Charles library was optimized for flexibility, and therefore the
iterators in Charles are all "definite" subtypes, which means you can
use them as record components (or array components, or container
elements).

 
> So for every non-abstract collection type, a concrete iterator
> type should be visibly declared. 

Yes.

> It also suggests that types of
> arguments of subrountines should be changed from Iterator'Class
> to the appropriate concrete types.

Yes.

Re: Problem with Booch iterators

[Simon Wright]

mheaney@on2.com (Matthew Heaney) writes:

> porton@ex-code.com (Victor Porton) wrote in message news:<3dcd00f3$0$307$bed64819@news.gradwell.net>...
> > There are a serious misdesign of Booch iterators:
> > 
> > Declaring a record component of type Iterator'Class,
> > I get error "unconstrained subtype in component declaration".
> 
> 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? In the STL,
iterators are related to the notion of pointer; in the BCs, they
aren't (to anything like the same extent). 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).

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

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

Re: Problem with Booch iterators

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

Re: Problem with Booch iterators

[Georg Bauhaus]

Matthew Heaney <mheaney@on2.com> wrote:
: 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.

Is it still an adequate characterization if I rewrite this as follows:
If dynamic polymorphism for containers is wanted by a library user,
then he will have to implement that himself, for example using
an Adapter pattern.  Dynamic polymorphism is not provided by the
library itself.

-- georg

Re: Problem with Booch iterators

[Simon Wright]

mheaney@on2.com (Matthew Heaney) writes:

> Simon Wright <simon@pushface.org> wrote in message news:<x7visz0ps4z.fsf@smaug.pushface.org>...
> > mheaney@on2.com (Matthew Heaney) writes:

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

Definite vs indefinite ITERATOR subtypes has quite a lot to do with a
Booch view of iteration (where most of the time all you need to do is
iterate over the whole container, which indeed is my experience -- but
since I'm using Booch I guess it's not surprising) and an STL/Charles
view, where you give people loads of flexibility but (out of the box)
the ability to shoot themselves in the foot (eg by using iterators
from different container instancess in the same iteration.

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

I can't remember the exact reasons, but the driving force was probably
to have the concept of iteration defined at a high level
(BC.Container) and yet have container- and form-specific iteration.

Grady's C++ BCs have iterators defined at the specific container kind
level (eg Maps, not Maps.Unbounded in Ada terms) -- there's no
equivalent of BC.Container.

Dave Weller's Ada 95 BCs had

   type Container is abstract new Controlled with private;

   type Iterator (C : access Container'Class) is limited private;

and with each actual Container having (private) iteration-support
methods.

I changed to the present style in the 20020604 release; the release
notes say

   In response to a report from T E Dennison, speeded up the creation
   of Iterators. Note, this requires that iterators be declared of
   type Containers.Interator'Class, and initialized at the point of
   declaration.

So there was some reason for it! (I think the problem was related to
the various different kinds of state needed to support iteration for
different containers).

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

I don't quite see why (in the abstract) it's wrong to make
judgements. Most _language_ designers (except perhaps Larry Wall) make
judgements about what is good.

I think it's a matter of how far you want to go -- safety vs
flexibility. Not that I'm claiming the BCs are that safe, indeed we've
recently discussed a nasty problem with the current BC iterators
(creating an iterator over a temporary). I do see where you're coming
from, but of course the BCs are what they are and there's no point in
contemplating a major change and annoying users.