Version 1.1 of acs/ac-00112.txt

Unformatted version of acs/ac-00112.txt version 1.1
Other versions for file acs/ac-00112.txt

!standard 5.5(00)          05-10-20 AC95-00112/01
!class Amendment 05-10-20
!status received no action 05-10-20
!status received 05-04-12
!subject Real Iterators for Ada
!summary
!appendix

From: Randy Brukardt
Date: Tuesday, April 12, 2005  10:58 PM


Now I've gone and done it; I can't stop thinking about how to define decent
iterators for Ada. For the record (there are a number reasons we couldn't do
this now, not the least of which is that this would need AI-359, which was
dropped in Atlanta), here is one way to define decent iterators.

First, we'd need a predefined generic signature package:

   generic
      type Container_Type (<>) is private;
      type Element_Type is private;
      type Scratch_Type is private;
      with procedure Start_Iteration (Container : in out Container_Type;
                                      Scratch : out Scratch_Type;
                                      In_Reverse : in Boolean) is <>;
      with procedure Next_Iteration (Container : in out Container_Type;
                                     Scratch : in out Scratch_Type;
                                     Element : out Element_Type;
                                     Done : out Boolean) is <>;
      with procedure Stop_Iteration (Container : in out Container_Type;
                                     Scratch : in out Scratch_Type) is <>;
   package Iteration_Signature is
      -- This is a signature package with no operations.
   end Iteration_Signature;

There would be an attribute Iterator on types. It could be specified to an
instance of Iteration_Signature.

Then when the compiler saw:

    for E in My_Container loop
        ...
    end loop;

it would take the type of My_Container, and see if the Iterator attribute
was specified. If it was, E would take the Element_Type of the specified
signature package. The compiler would generate something like (if the type
of My_Container is T):

    declare
       S : Scratch_Type;
       E : Element_Type;
       Done : Boolean;
    begin
       T'Iterator.Start_Iteration (My_Container, S, In_Reverse => False);
       loop
           T'Iterator.Next_Iteration (My_Container, S, E, Done);
           if Done then goto Finished; end if;
           ... -- Body of loop here.
       end loop;
     <<Finished>> T'Iterator.Stop_Iteration (My_Container, S);
    exception
       when others => T'Iterator.Stop_Iteration (My_Container, S);
              raise;
    end;

The reason for the scratch space is so that the iterators could be task
safe. (If the scratch space was kept in the Container, it could only work
for one task at a time. Of course, Ada.Containers, like the rest of the
runtime, is only task safe when separate objects are used, so this wouldn't
be a real concern there, but it would seem bad to not support the
possibility in the core language.)

The definition of the containers packages would include an appropriate
instance of Iteration_Signature and a specification of the Iterator
attribute, something like:

    package Iterator is new Iteration_Signature (Map, Cursor, Cursor,
Start_Iteration,
         Next_Iteration, Stop_Iteration);
    for Map'Iterator use Iterator;

[The scratch space might be a Cursor here.]

This would be a bit messy in the containers packages, but the uses would be
very clean. And there are a lot more uses than containers packages.

I'm sure the details would change once the experts started picking it apart,
but this general idea would work well.

****************************************************************

From: Tucker Taft
Date: Wednesday, April 13, 2005  8:28 AM

It is worth mentioning that C# has iterators,
and that Java 1.5 just added them.  The Java
iterator is based on two (generic) interfaces:

   interface Iterator<T> {
       boolean hasNext();
       T next();
       void remove();
   }

   interface Iterable<T> {
       Iterator iterator();
   }

where "T" is the type of the element in the iterable object.

The syntax for a "foreach" loop is:

   for (T element: iterable_obj) {
      ... element ...
   }

where iterable_obj must be of a type that implements Iterable<T>.

The foreach loop, I believe, translates into:

   {
      Iterator<T> iter = iterable_obj.iterator();
      while (iter.hasNext()) {
          T element = iter.next();
          ... element ...
      }
   }

In Ada, a generic signature is a reasonable replacement for
a generic interface.  Unfortunately, we never solved the
problem of pre-instantiating generic signatures, which
still suffer from the freezing of private types by instantiations.
(It is frustrating that we never came up with an acceptable
version of AI-359.)

Just establishing a widely agreed-upon "signature" (be it
a real generic signature, or simply a naming convention)
for "active" iterators would be a big step.  The big
problem with "passive" iterators (those that take generic
formal subprograms or access-to-subprograms) is the early
exit problem.  I have yet to see an elegant solution
that uses formal or access-to- subprograms that supports
early exit from the loop.

As a specific comment on Randy's proposal, I would require
that the iterator object (which Randy chooses to call
"Scratch space") be Controlled if there is some need
for cleanup.  Requiring an exception handler is unfriendly,
sometimes inefficient at run-time, and doesn't handle
aborts or ATCs properly.

I would start with an active iterator that is pleasant for human
programmers to use, and then make the syntactic sugar
of a "foreach" construct a second step.  Randy's looks
pretty unfriendly for humans.

****************************************************************

From: Florian Weimer
Date: Wednesday, April 13, 2005  10:17 AM

> Then when the compiler saw:
>
>     for E in My_Container loop
>         ...
>     end loop;

      for Transaction in Database loop
         ...
      end loop;

would be nice as well.

>     declare
>        S : Scratch_Type;
>        E : Element_Type;
>        Done : Boolean;
>     begin
>        T'Iterator.Start_Iteration (My_Container, S, In_Reverse => False);
>        loop
>            T'Iterator.Next_Iteration (My_Container, S, E, Done);
>            if Done then goto Finished; end if;
>            ... -- Body of loop here.
>        end loop;
>      <<Finished>> T'Iterator.Stop_Iteration (My_Container, S);
>     exception
>        when others => T'Iterator.Stop_Iteration (My_Container, S);
>               raise;
>     end;

However, if you abuse this iterator functionality for transactions,
you need some way to access the exception because you only want to
re-execute the loop body when a deadlock occurs (and not for other
exceptions).

****************************************************************

From: Randy Brukardt
Date: Wednesday, April 13, 2005  1:14 PM

Tucker writes:

...
> In Ada, a generic signature is a reasonable replacement for
> a generic interface.  Unfortunately, we never solved the
> problem of pre-instantiating generic signatures, which
> still suffer from the freezing of private types by instantiations.
> (It is frustrating that we never came up with an acceptable
> version of AI-359.)

Yes, I mentioned that. Of course, that's because you didn't want the partial
instantiation to be a limited view. :-) [None of the problems that killed it
in Atlanta could have happened in a limited view.]

> Just establishing a widely agreed-upon "signature" (be it
> a real generic signature, or simply a naming convention)
> for "active" iterators would be a big step.  The big
> problem with "passive" iterators (those that take generic
> formal subprograms or access-to-subprograms) is the early
> exit problem.  I have yet to see an elegant solution
> that uses formal or access-to- subprograms that supports
> early exit from the loop.

Absolutely. Plus its just a lot of extra text that obscures what's really
going on.

> As a specific comment on Randy's proposal, I would require
> that the iterator object (which Randy chooses to call
> "Scratch space") be Controlled if there is some need
> for cleanup.  Requiring an exception handler is unfriendly,
> sometimes inefficient at run-time, and doesn't handle
> aborts or ATCs properly.

Yes, I thought about that, and didn't do it because I was concerned about
overhead. But this was just intended to put ideas on the record; I'm sure it
would get changed a lot before it actually got implemented.

This structure was designed to be similar to what the containers need to do
(since they're have to clear their "tamper" bit on exit). But there are
other ways to do that.

> I would start with an active iterator that is pleasant for human
> programmers to use, and then make the syntactic sugar
> of a "foreach" construct a second step.  Randy's looks
> pretty unfriendly for humans.

The only way these things are friendly for humans is with a For loop of some
sort. Otherwise, they're just too error prone. Familarity (like knowing that
you always need "Cursor := Cursor.Next;" at the botton of a list traversal)
helps, but it isn't perfect.

That's especially true with the containers, where the passive iterator has
protection against interference from other operations, while the active form
does not. (And that's intentional, of course). This was intended to be a
better way to write *passive* iterators, not a way to write *active*
iterators -- they have different requirements and purposes.

****************************************************************

From: Randy Brukardt
Date: Wednesday, April 13, 2005  1:20 PM

> However, if you abuse this iterator functionality for transactions,
> you need some way to access the exception because you only want to
> re-execute the loop body when a deadlock occurs (and not for other
> exceptions).

Not sure what you mean here. If the iterator raises an exception, the loop
is going to be terminated. That's what you'd expect to happen, since the
handler has to be outside of the loop:

   begin
      for E in O loop
          ...
      end loop;
   exception
      when ... =>
   end;

It would be unnatural to do anything else. If you need retrying, you would
do that *inside* the iterator itself (and never let the exception
propagate). But if you've got multiple exit/continue conditions, a passive
iterator isn't going to work. The whole idea is that you go from item to
item deterministically; any disruption and you can't use a passive iterator.

****************************************************************

From: Adam Beneschan
Date: Wednesday, April 13, 2005  1:35 PM

> Now I've gone and done it; I can't stop thinking about how to define decent
> iterators for Ada. For the record (there are a number reasons we couldn't do
> this now, not the least of which is that this would need AI-359, which was
> dropped in Atlanta), here is one way to define decent
> iterators. . .

> it would take the type of My_Container, and see if the Iterator attribute
> was specified. If it was, E would take the Element_Type of the specified
> signature package. The compiler would generate something like (if the type
> of My_Container is T):

>     declare
>        S : Scratch_Type;
>        E : Element_Type;
>        Done : Boolean;
>     begin
>        T'Iterator.Start_Iteration (My_Container, S, In_Reverse => False);

I realize this is all very preliminary.  One question that comes to
mind immediately: Not all iterators are going to be willing to support
a "reverse" mode.  How do we handle this?  Disallow "reverse" entirely
when the "for" statement is used in this way?  Provide some sort
mechanism that would allow the compiler to reject "reverse" when the
iterator doesn't support it?  For example, provide two generic
signatures, Iteration_Signature and Reversible_Iteration_Signature?
The obvious way would be to let Start_Iteration raise Program_Error or
something if In_Reverse=True and the iterator doesn't support it, but
is a mechanims that allows this error to be detected at compile-time
better?

The second thought that comes to mind is that I'm not going to want
just one iterator per container.  If I have a type that represents a
collection of library books, I may want to be able to say things like

    for Book in Books_In_Alphabetical_Order(My_Library) loop ...

    for Book in Books_In_Catalog_Order(My_Library) loop ...

    for Book in Books_In_Order_By_Author(My_Library) loop ...

This certainly seems doable within Randy's proposal by having these
functions return objects of three different types, possibly all
containing just one component (an access to My_Library), and with
these three types *possibly* having different packages as their
'Iterators.  It's doable (I think), but whether that's the best way to
do it, I don't know.  I'm just throwing this out because I know that
I'd want to do stuff like the above, and I think it ought to be
considered when deciding on the best mechanism for implementing this
concept.

I'm not expecting an immediate discussion of these issues---just file
them for later when (and if) this feature is discussed in earnest.

****************************************************************

From: Matthew Heaney
Date: Wednesday, April 13, 2005  3:59 PM

> The second thought that comes to mind is that I'm not going to want
> just one iterator per container.  If I have a type that represents a
> collection of library books, I may want to be able to say things like
>
>     for Book in Books_In_Alphabetical_Order(My_Library) loop ...
>
>     for Book in Books_In_Catalog_Order(My_Library) loop ...
>
>     for Book in Books_In_Order_By_Author(My_Library) loop ...
>
> This certainly seems doable within Randy's proposal by having these
> functions return objects of three different types, possibly all
> containing just one component (an access to My_Library), and with
> these three types *possibly* having different packages as their
> 'Iterators.  It's doable (I think), but whether that's the best way to
> do it, I don't know.  I'm just throwing this out because I know that
> I'd want to do stuff like the above, and I think it ought to be
> considered when deciding on the best mechanism for implementing this
> concept.

Well, you can easily implement this yourself using the container library
we have now:

package Library_Types is
    type Library is limited private;
    type Book is ...;

    procedure Insert (L : in out Library; B : in Book);
    procedure Delete (L : in out Library; B : in Book);

    -- active iterator
    type Alpha_Cursor is private; --book title
    function Has_Element (C : Alpha_Cursor) return Boolean;
    function First (L : Library) return Alpha_Cursor;
    function Next (C : Alpha_Cursor) return Alpha_Cursor;
...
    generic
       with procedure Process (B : in Book) is <>;
    procedure Get_Books_By_Author
      (L : in Library;
       N : in String);

    type Author_Cursor is private;

private

    package Cat_Maps is
      new Ada.Containers.Hashed_Maps (Cat_Num, Book, ...);

    function Compare_Alpha (C1, C2 : Cap_Maps.Cursor)
      return Boolean;

    package Alpha_Sets is
       new Ada.Containers.Ordered_Sets
         (Cat_Maps.Cursor,
          Compare_Alpha);
...
    type Library is limited record
       Cat_Map : Cat_Maps.Map;
       Alpha_Set : Alpha_Sets.Set;
       Author_Set : Author_Sets.Set;
    end record;

end Library_Types;

The idea is to store the books in some canonical container (in the
example above, a hashed map that uses the catalog number as the key),
and then use another pair of sets that are references to the entries in
the map.

The set containers have a nested generic package Generic_Keys, that
allows you to get key-based view of the set.  So for example, if you
want to look up a book by author (that what Get_Books_By_Author does),
then you can use an instantiation of Author_Sets.Generic_Keys to return
a map cursor, and then dereference the map cursor to get a book.

(I'm fibbing a little bit because I'm thinking you might need a multiset
instead of a (unique) set, because an author can have several books.
But you might be able to do it anyway, since you only really need to
search for the author's book that sorts into the lowest position.)

Note that you don't need to use a set container for the Alpha_Set or
Author_Set.  A vector that you keep sorted would work just as well, and
would be more space efficient.  You can search a sorted vector using a
binary search.

Hmmmm... I sense an ai302/example is brewing...

****************************************************************

From: Bob Duff
Date: Wednesday, April 13, 2005  4:50 PM

Are we working on Ada 1X already?  ;-)

I've done quite a lot of thinking about how to do iterators in Ada.
I agree without your idea to base it on some sort of for loop syntax:

>     for E in My_Container loop
>         ...
>     end loop;

But I prefer to include the component type:

    for E: Element_Type in My_Container loop
        ...
    end loop;

I think you need to be able to have multiple iterators associated with
each container type.  So the thing after "in" should really be an
iterator:

    for E: Element_Type in Backward_Iterator(My_Container) loop
        ...
    end loop;

If you give the name of a container, that would be short-hand for the
"standard" iterator of that type.  Perhaps the user would say "for
Container_Type'Standard_Iterator use..." or something, and then:

    for E: Element_Type in My_Container loop
        ...
    end loop;

----------------

I think it's important to distinguish 'in' and 'in out' parameters.
So if My_Container is a variable, then E is a variable (basically,
an 'in out' parameter passed to the loop body).  And if My_Container is
constant, then so is E.

----------------

> ...It
> also has the advantage of reinforcing that these are "safe" uses (for loops
> being the only "safe" loops, in that you don't have to explicitly terminate
> them).

I'm not sure what you mean by that.  This new kind of 'for' loop can
loop forever, unlike Ada's 'for' loop.  Looping forever is quite
useful.  You can make infinite-sized data structures that are lazily
computed -- as in Haskell.

You might want to say "for all prime numbers X, ...".  Of course, you'll
want a premature exit in that loop.  You don't need to actually
construct a list of all prime numbers in order to be able to express
such a thing!

----------------

I always get confused by the terminology.  An "active" iterator is what
AI-302 calls "cursor" -- it has operations to start, stop, and get-next
or whatever.  A "passive" iterator is written as a loop body or
something, and takes an "Action" procedure as a parameter, which it
calls for each item.  Is that right?

So you propose to write iterators in the active/cursor style.
I think that's insufficient.  Writing a passive iterator is sometimes
much easier.  Consider for example an iterator that wants to walk a tree
or other complicated data structure.  It's easy if you write a recursive
passive iterator.  Doing it as an active iterator requires making the
recursion stack explicit, which is a huge pain.

You are correct that it's more important to make *clients* of the
iterator simple, as opposed to the iterator itself.  But still, I don't
like to see stumbling blocks placed in the way of making nice
abstractions (such as iterators).

So I think the programmer who writes the iterator should be able to
choose either active or passive style.  Likewise, the client should be
able to choose either style, independently of what style the iterator is
written in.  So if you want to iterate through all elements, you would
say "for E ...".  But you could also choose a "get next" style in more
complicated cases (like when you write a recursive descent parser, you
don't say "for all tokens", you say "give me the next token" all over).

The implementation of all this requires a very lightweight coroutine
mechanism.  You can turn a passive iterator into an active one using Ada
tasks, but it's pretty ugly, and quite inefficient.

----------------

Another thing I want is to be able to iterate multiple sequences in lock
step:

    for E1: T1 in X1, E2: T2 in X2 loop
        ...

which would mean perform the body on the first elements of both
sequences, then the second elements of both, and so on.

Normally, all sequences would be the same length.  But if sequence ends
before the others, you would want some sort of indication of this
exceptional situation, and you would want to know *which* one(s) gave
out first.

Note that the two sequences might be completely different abstractions
from completely different packages.  Consider for example a compiler for
a language that has formal parameters and actual parameters.  When
compiling a call, you might want to iterate through pairs
(formal, actual).  But you don't want to have to write a pair-iterator,
because that doesn't belong to either package.

----------------

I very much agree with:

> The need to separately define a procedure to do part of the job is
> unnatural, confusing, and requires writing a lot of extra stuff that has
> nothing to do with the problem. It is separated from its use, and inside
> out.

particularly the "inside out" part.  It's *really* annoying to have to
write the body of the loop as a separate procedure, and put it before
the actual loop.  The generic way is even worse, because you also have
to instantiate the loop in the wrong spot.  Passing access-to-procedure
is a little better.

I think this problem could be alleviated by having anonymous
procedures.  Like lambda in Lisp, or anonymous blocks in Smalltalk.
This would be more powerful than iterators.  It would allow things like
a tree walker, which takes a Pre_Action and a Post_Action.
The syntax isn't quite as pretty as "for ...", but at least the
action (or loop body) appears in the right place, and doesn't need
a junk name.

----------------

Premature exit is needed, and it's currently a big pain.
The *usual* case is that you don't want premature exit.
So I think the iterator itself should not have extra
junk for that, and if you don't want premature exit,
the loop body shouldn't have to say anything about it
(like passing around Done flags).

You can exit from a passive iterator by raising an exception.
But that's overkill.  Exceptions are for when you want to jump
somewhere, and you don't know where you're jumping to (the caller
decides where to jump to, by having a handler).  In other words, the
callee decides whether to jump ("raise") and the caller decides where to
jump to.  But loop exits know (statically) where they're jumping to.
Furthermore, exceptions are likely to be to inefficient.

----------------

Don't tie iterators too closely to "container types" in your mind.  One
of the powerful uses of iterators is to have "virtual" containers -- you
don't actually need to construct any data structure, because you can
create the items one by one as they are needed.

Consider for example an Ada compiler implementing the visibility rules.
You want to say "give me all the things called X that are immediately
visible".  On top of that, you can build "give me all the ones that are
not hidden".  And you could have "give me all the potentially
use-visible things called X".  And on top of that, you can build "give
me all the use-visible ones".  And on top of all that, you can build
"give me all the directly visible things called X".  With sufficiently
powerful iterator features, you can do all that without actually
constructing lists of symbol-table entries.

----------------

Nobody should design iterators for any language without looking at
Sather first.  It has an *extremely* elegant solution, such that
iterators actually subsume all kinds of loops (even the lowly
'while' is just an iterator in Sather).

I think Sather's iterators have some error-prone properties.
I would sacrifice some of the elegance in order to get rid
of the error-pronedness.  But Sather is definitely a good
starting point.

----------------

I don't think your proposal allows for iteration through a sequence of
Strings; it seems to require definite subtype.  Iterating through a
sequence of Strings (etc) should be allowed, without messing around with
pointers.

I also want to be able to iterate when the items are limited.

If the items are large, I want to be able to iterate without copying
them, whether or not they are limited.

----------------

Somebody mentioned "reverse" in this discussion.  I think order-of-items
is a property of the iterator.  You can define a forward iterator, a
reverse one, and perhaps others, as desired (iterate tree nodes
in top-down, bottom-up, breadth-first etc orders).  So the "reverse"
keyword doesn't make sense -- we can't expect the compiler to
automagically contruct a backward iterator.  If you want to iterate
backward, you have to write another iterator.

----------------

I'm annoyed that AI-359 got canned.  Not just for signature generics.
This would have fixed one of those annoying restrictions that make Ada
so frustrating to use.  You try to do something that seems perfectly
reasonable, and some language lawyers explain why you can't do it based
on some arcane mumbo jumbo having to do with freezing rules and the
like.  Sigh.

****************************************************************

From: Florian Weimer
Date: Wednesday, April 13, 2005  5:11 PM

> Not sure what you mean here. If the iterator raises an exception, the loop
> is going to be terminated. That's what you'd expect to happen, since the
> handler has to be outside of the loop:
>
>    begin
>       for E in O loop
>           ...
>       end loop;
>    exception
>       when ... =>
>    end;
>
> It would be unnatural to do anything else. If you need retrying, you would
> do that *inside* the iterator itself (and never let the exception
> propagate).

The point is that the loop *body* throws the exception, and when it is
encountered, the transaction must be aborted, the loop restarted, and
a new transaction begun.

Today, you're likely using something like this:

   <<Retry_Transaction>>
   Begin_Transaction (T);
   begin
      --  Transaction body.  Uses T.
      ...
      Commit_Transaction (T);
   exception
      when Deadlock_Exception =>
         Abort_Transaction (T);
         goto Retry_Transaction;
   end;

You can encapsulate this in a generic subprogram, but the result is
still a syntactic heavyweight.  Your iterator proposal comes quite
close to providing an alternative, but doesn't quite make it (AFAICS,
the only change required is to pass an Exception_Occurrence to
Stop_Iterator (Null_Occurrence on normal exit), and rely on
Stop_Iterator to reraise the exception).

****************************************************************

From: Randy Brukardt
Date: Wednesday, April 13, 2005  5:44 PM

Bob Duff wrote:

> Are we working on Ada 1X already?  ;-)

Why not? It's a lot more fun than deciding the length of minus signs in the
text of the Standard. :-)

But I really do need to work on those minus signs, so I'll keep this real
brief.

...
> I think you need to be able to have multiple iterators associated with
> each container type.  So the thing after "in" should really be an
> iterator:
>
>     for E: Element_Type in Backward_Iterator(My_Container) loop
>         ...
>     end loop;

I didn't want a "visible" iterator, because it makes the abstraction much
heavier than it needs to be. Your idea of including the element type would
sufficiently distiguish between elements.

In any case, I was concentrating on a way to connect the iterator profile
(which necessarily has to be generic) with the syntax. The rest of it is
trivial (and thus will be argued about for 10 years, I would guess).

...
> > ...It also has the advantage of reinforcing that these are "safe" uses
(for loops
> > being the only "safe" loops, in that you don't have to explicitly
terminate
> > them).
>
> I'm not sure what you mean by that.  This new kind of 'for' loop can
> loop forever, unlike Ada's 'for' loop.  Looping forever is quite
> useful.  You can make infinite-sized data structures that are lazily
> computed -- as in Haskell.

It's certainly possible to use the structure for things other than "normal"
iteration. But these are really to be used for containers (of course, the
container may be virtual or non-local, like the database example). In the
intended use:
   (1) Each element is visited exactly once;
   (2) The iteration is not distrubed by operations on the container (the
       container and/or iterator should detect abuse);
   (3) Termination (if appropriate) is handled by the iterator, not the
user.

Of course, all of these depend on the appropriate construction of the
underlying iterator. That's OK; the situation is very similar to that of
Storage_Pools. If a storage pool doesn't actually return memory to the
caller, things will go very bad. This is not that dangerous, but certainly
the behavior wouldn't be defined if the above aren't met.

Note that the active iterators in Ada.Containers (and indeed in most cases
in practice) do not meet any of these. Since (2) isn't done, neither is
(1) - a modification to the container may cause elements to be missed or
duplicated. User-beware is never a good policy.

...
> I always get confused by the terminology.  An "active" iterator is what
> AI-302 calls "cursor" -- it has operations to start, stop, and get-next
> or whatever.  A "passive" iterator is written as a loop body or
> something, and takes an "Action" procedure as a parameter, which it
> calls for each item.  Is that right?

Right. The user only write the action, not the mechanics of the loop.

> So you propose to write iterators in the active/cursor style.
> I think that's insufficient.  Writing a passive iterator is sometimes
> much easier.  Consider for example an iterator that wants to walk a tree
> or other complicated data structure.  It's easy if you write a recursive
> passive iterator.  Doing it as an active iterator requires making the
> recursion stack explicit, which is a huge pain.

I suppose, but I don't see how you could write a "recursive passive
iterator". In any case, the mechanics of a loop require the state to be
saved somehow, and that's the iterators job. Having the compiler do it is
way too complicated. You mention co-routines later, but there is no
appropriate memory allocation scheme for those. I don't think this would
ever fly if it *required* heap use (that's the same reason I avoided
controlled types, even though it would be better if the scratch space was
controlled).

...
> Premature exit is needed, and it's currently a big pain.
> The *usual* case is that you don't want premature exit.
> So I think the iterator itself should not have extra
> junk for that, and if you don't want premature exit,
> the loop body shouldn't have to say anything about it
> (like passing around Done flags).

I agree. The Done flag in my proposal was simply to support *normal*
termination. You can't use a special value returned from Get_Next for that
(because you don't know the termination value, and there may not be one),
and an exception is too expensive.

As long as the underlying iterator supports proper termination (probably by
being controlled), then a normal loop exit works fine. And that's better by
far than the current state.

...
> I don't think your proposal allows for iteration through a sequence of
> Strings; it seems to require definite subtype.  Iterating through a
> sequence of Strings (etc) should be allowed, without messing around with
> pointers.

That's right, and that's a consequence of wanting to avoid heap use (so the
real-time and safety folks don't get all in a tizzy).

> I also want to be able to iterate when the items are limited.
>
> If the items are large, I want to be able to iterate without copying
> them, whether or not they are limited.

You'd have to use references for that, and certainly an iterator on "access
Lim" would work. Why wouldn't it?

...
> Somebody mentioned "reverse" in this discussion.  I think order-of-items
> is a property of the iterator.  You can define a forward iterator, a
> reverse one, and perhaps others, as desired (iterate tree nodes
> in top-down, bottom-up, breadth-first etc orders).  So the "reverse"
> keyword doesn't make sense -- we can't expect the compiler to
> automagically contruct a backward iterator.  If you want to iterate
> backward, you have to write another iterator.

One of the properties of the iterator type was forward or backward.
Certainly, other combinations are possible, but those are pretty
fundemental -- and we already have the keyword sitting around - rather
underused.

...
> I'm annoyed that AI-359 got canned.  Not just for signature generics.
> This would have fixed one of those annoying restrictions that make Ada
> so frustrating to use.  You try to do something that seems perfectly
> reasonable, and some language lawyers explain why you can't do it based
> on some arcane mumbo jumbo having to do with freezing rules and the
> like.  Sigh.

But that's fully your fault (and Tucker's, for trying to make you happy).
The problems that we ran into that got it killed in Atlanta come from trying
to export too much from the partial instance. My original limited view
proposal did not have those problems! And it solved the number 1, 2, and 3
problems with such instances:
   (1) You can't export a container of a private type;
   (2) You can't export a signature package of a private type;
   (3) You can't have a recursive reference to a container of a private
type;

But trying to put actual containers of a private type into the private type
is awful; it's privacy and contract breaking. I spent so much time killing
that off that we never thought about staticness and inherited operations and
the like until Steve Baird, the killer of many good ideas, started coming
out with these bizarre cases. That sowed enough doubt to get it killed.

Anyway, that's water under the dam.

****************************************************************

From: Bob Duff
Date: Wednesday, April 13, 2005  6:24 PM

> But that's fully your fault (and Tucker's, for trying to make you happy).

If I read the minutes, will I understand why it's my fault?
Is there any chance of revisiting this issue?

Surely I'm not the only Ada programmer who has wanted to say
"package ... is new Some_Container(Some_Private_Type)"!

****************************************************************

From: Randy Brukardt
Date: Wednesday, April 13, 2005  6:50 PM

> > But that's fully your fault (and Tucker's, for trying to make you happy).
>
> If I read the minutes, will I understand why it's my fault?

Perhaps. It got tangled up in minutia. But if you would have been satisfied
with my proposal, perhaps it would have been adopted (and then we could have
tried to figure out how to safely expand it, if that proved necessary).

> Is there any chance of revisiting this issue?

You would have had to convince Pascal to put it on the agenda for this
meeting. And I'm sure he would have required a full proposal by the deadline
(noon CST today).

> Surely I'm not the only Ada programmer who has wanted to say
> "package ... is new Some_Container(Some_Private_Type)"!

Actually, you're the only one I ever heard of. It's never happened to me,
but then again I've never used any generic container library. I'd expect
that it might happen once Ada.Containers gets in use. But whether that is
worth having static and non-static views of the same constant, and partially
defined operators, is hard to say. (But, as I've said before, the limited
view I advocated didn't export any of that stuff, so there wasn't a
problem.)

****************************************************************

From: Jeffrey Carter
Date: Wednesday, April 13, 2005  7:52 PM

> I always get confused by the terminology.  An "active" iterator is what
> AI-302 calls "cursor" -- it has operations to start, stop, and get-next
> or whatever.  A "passive" iterator is written as a loop body or
> something, and takes an "Action" procedure as a parameter, which it
> calls for each item.  Is that right?

You are correct. That is the terminology used in the AI, and presumably
in the ARM. Thus an "active" iterator is passive: it does nothing. It
only appears in statements written by the client. And a "passive"
iterator is active: it visits each Element in the structure and passes
it to a client-supplied subprogram.

Now, if we can just get rid of confusing terms such as "subprogram",
"procedure", and "function", and replace them with "method", and use
"prototype" for something that isn't, and maybe replace "type" with
"class", then we might be on the road to a confusing language. Confusing
languages seem to be popular, but I still don't think it's a good thing.

****************************************************************

From: Matthew Heaney
Date: Thursday, April 14, 2005  10:03 AM

>> I always get confused by the terminology.  An "active" iterator is what
>> AI-302 calls "cursor" -- it has operations to start, stop, and get-next
>> or whatever.  A "passive" iterator is written as a loop body or
>> something, and takes an "Action" procedure as a parameter, which it
>> calls for each item.  Is that right?
>
>
> You are correct. That is the terminology used in the AI, and presumably
> in the ARM. Thus an "active" iterator is passive: it does nothing. It
> only appears in statements written by the client. And a "passive"
> iterator is active: it visits each Element in the structure and passes
> it to a client-supplied subprogram.

How soon we forget!  The terms "active" and "passive" iterator have
standard definitions in software engineering literature, including Ada
books going back almost 20 years.

These terms are even discussed in the Ada95 Quality and Style Guide:

<http://www.adaic.com/docs/95style/html/sec_8/8-3-6.html>

In fact, on 11 Feb 2004, I posted to this list quotations on this very
topic from some popular software engineering titles.  I have reproduced
below my response to Jeff from 14 months ago.

[See the !appendix of AI-302-4 for this message. - ED]

****************************************************************

From: Jeffrey Carter
Date: Thursday, April 14, 2005   1:42 PM

Matthew Heaney wrote:
>
> How soon we forget!

I didn't forget. Matt was wrong then and he's wrong now. His standard
reply, "Because others got it wrong, Ada should get it wrong, too," is
not convincing.

The most interesting part of the collection of quotes is that Booch got
it wrong, Gamma and others get it better with "internal" and "external",
and everyone else needs to explain why the terms are used in the reverse
order from common sense, a good indication that they're not the right names.

****************************************************************

From: Jeffrey Carter
Date: Wednesday, April 13, 2005  7:58 PM

> But I really do need to work on those minus signs, so I'll keep this real
> brief.

I'd prefer it if you would keep it really brief. Using an adjective as
an adverb may be becoming more common, but I still don't think it's at
the point that it's acceptable in the ARM.

****************************************************************

From: Tucker Taft
Date: Thursday, April 14, 2005  2:18 PM

Jeff,
    I sympathize with your concern about active and passive,
but if we use them at all, we have to stick with the established
meaning for these terms.  It is one thing to invent your
own terminology.  It is another to use existing terminology
in exactly the opposite way as the established meaning.

Booch invented, or at least popularized the terms, as far as I
know.  I understand his logic, which is a user-centric rather
than a provider-centric view.  Clearly the user is more "active"
with an active iterator.  With a passive iterator, the user's
code has to sit around and "wait" to be called.

But I admit I have trouble remembering which is which.
The choice at this point is to find new, more intuitive
terms, adopt some other set that everyone can understand
and remember, or use active and passive with highly visible,
up-front definitions of what they mean.  Using active and
passive opposite to their established meaning is *not*
an option, as far as I am concerned.

****************************************************************

From: Bob Duff
Date: Thursday, April 14, 2005  3:37 PM

> I didn't forget. Matt was wrong then and he's wrong now. His standard
> reply, "Because others got it wrong, Ada should get it wrong, too," is
> not convincing.

Fighting for sensible terminology is a worthy goal.  But the English
language (including technical jargon) is defined by how people use it,
whether or not it makes sense.  (Why do we drive on a parkway, and park
on a driveway?  Why is "sanction" its own opposite?)

Don't get me started, or I'll start ranting about how evil it is to call
a 32-bit 2's complement small finite subset of integers by the name
"Integer".  ;-)

> But I admit I have trouble remembering which is which.
> The choice at this point is to find new, more intuitive
> terms,...

I find "cursor" pretty intuitive for the one kind.  And I'm pretty happy
calling the other kind just "iterator" -- it iterates, unlike a cursor,
which just sits there waiting to be told what to do.

****************************************************************

From: Georg Bauhaus
Date: Thursday, April 14, 2005   4:05 PM

> But I admit I have trouble remembering which is which.
> The choice at this point is to find new, more intuitive
> terms, adopt some other set that everyone can understand
> and remember, or use active and passive with highly visible,
> up-front definitions of what they mean.  Using active and
> passive opposite to their established meaning is *not*
> an option, as far as I am concerned.

The word "Iterator" doesn't appear in the version 11 RM*.TXT
files as far as I can see. There is only one occurence of
"iterator" in a general remark in the NOTES section of
Section 3, about the Access attributes for subprograms
being appropriate for an iterator abstraction.
"Passive" or "active" do not occur together with iteration.

So perhaps trouble can be avoided by avoiding
"(active|passive) iterat.*" phrases altogether and instead
stick with phrases used in A.18 that either say
"write a loop" or alternatively "call Iterate"?

****************************************************************

From: Randy Brukardt
Date: Wednesday, April 13, 2005  8:15 PM

Sigh. That's about at the level of those minus signs. I don't need more of
that. Maybe next time I'll just keep "real briefs". :-)

****************************************************************

From: Matthew Heaney
Date: Wednesday, April 13, 2005  10:12 PM

> Well, you can easily implement this yourself using the
> container library we have now:
[snip]

> Hmmmm... I sense an ai302/example is brewing...

As promised, I have implemented said example:

<http://charles.tigris.org/source/browse/charles/src/ai302/examples/library/
>


The library type is implement as three separate sets (I omitted catalog
order in order to simplify the example):


package Libraries is

   type Library_Type is limited private;

   procedure Add
     (Library : in out Library_Type;
      Book    : not null access constant Book_Type);

   procedure Books_By_Title
     (Library : in Library_Type;
      Process : not null access procedure (Book : in Book_Type));
...
private

   package Book_Sets is
      new Ada.Containers.Ordered_Sets
     (Book_Constant_Access,
      "<" => Compare_Books);

   package Title_Sets is
      new Ada.Containers.Ordered_Sets
     (Book_Sets.Cursor,
      "<" => Compare_Titles);

   package Author_Sets is
      new Ada.Containers.Ordered_Sets
     (Book_Sets.Cursor,
      "<" => Compare_Authors);

   type Library_Type is limited record
      Book_Set  : Book_Sets.Set;
      Title_Set : Title_Sets.Set;
      Author_Set : Author_Sets.Set;
   end record;

end Libraries;


The actual book objects are stored in the Book_Set.  Whenever you add a book
to the library, it gets added to that set, and in addition its Book_Set
cursor gets inserted into the Title_Set and Author_Set.

(Actually, since Book_Type is always passed around by reference, I probably
could have used a Book_Constant_Access as the element type for those other
sets, too.  In fact, I probably didn't even need the Book_Set, since the key
(title, author) is already unique.)

Implementing the Library_Type using three sets allows me to list books in
both title order and author order, or perform membership tests.  I can even
list books by a specific author.

Run the example and see for yourself...

****************************************************************

From: Florian Weimer
Date: Thursday, April 14, 2005  5:50 AM

> But I prefer to include the component type:
>
>     for E: Element_Type in My_Container loop
>         ...
>     end loop;

Or even anonymous subprograms:

   for (Item : in out Element_Type; Stop : out Boolean)
     in My_Container.Iterate
   loop
      ...
   end loop;

Iterate would be defined as:

   procedure Iterate
     (Container : in out Containter_Type;
      Action : access procedure
        (Item : in out Element_Type; Stop : out Boolean))
   is
      Stop : Boolean := False;

   begin
      for J in Container.Data'Range loop -- or some other looping construct
         Action (Containter.Data (J), Stop);
         exit when Stop;
      end loop;
   end Iterate;

The compiler would translate the "for" idiom to something like this:

   declare
      procedure Action (Item : in out Element_Type; Stop : out Boolean) is
      begin
         ...
      end Action;

   begin
      My_Container.Iterate (Action'Access);
   end;

Overload resolution rules apply to the Iterate call.  It can even be
dispatching.

I think that iterators are so specific a construct that if you think
there's no reasonable way to express them, you should wonder if the
language lacks expressiveness (or, in the case of Ada, terseness).
Forcefully adding iterators only doesn't close the underlying gap, and
just adds yet another gazebo to the language.

Anonymous subprograms are quite useful in a variaty of contexts (look
at my transaction example), not just for iterators, and might actually
be worth the increase in complexity.

It might make sense to replace for/in/loop different keywords (perhaps
for/in/do or with/in/do).  I'm not sure if the anonymous subprogram
should be passed exlicitly, like in:

   with (J : Index) in Invoke_Something (Param_1, <>) do ...

This would reduce the behind-the-scenes magic even further.

****************************************************************

From: Bob Duff
Date: Thursday, April 14, 2005  8:36 AM

Florian Weimer wrote:

> Or even anonymous subprograms:

I like anonymous subprograms.

>    for (Item : in out Element_Type; Stop : out Boolean)
>      in My_Container.Iterate
>    loop
>       ...
>    end loop;
>
> Iterate would be defined as:
>
>    procedure Iterate
>      (Container : in out Containter_Type;
>       Action : access procedure
>         (Item : in out Element_Type; Stop : out Boolean))
>    is
>       Stop : Boolean := False;
>
>    begin
>       for J in Container.Data'Range loop -- or some other looping construct

or, in some cases, recursive calls.

>          Action (Containter.Data (J), Stop);
>          exit when Stop;
>       end loop;
>    end Iterate;

I find that Stop flag annoying.  I don't want to say "Stop := True;".
I want to say "exit when ...".

Even worse, Action must say "Stop := False" to *not* exit the loop,
since Stop is mode 'out'.  Making it mode 'in out' would alleviate
*that* problem.  But even declaring the Stop flag in Action is an
annoyance in the (usual) case where you don't want premature exit.

> The compiler would translate the "for" idiom to something like this:
>
>    declare
>       procedure Action (Item : in out Element_Type; Stop : out Boolean) is
>       begin
>          ...
>       end Action;
>
>    begin
>       My_Container.Iterate (Action'Access);
>    end;

I prefer this model (passing the Item as a parameter) to Randy's
proposal, because it allows by-reference passing when appropriate,
and it allows limited types and indefinite subtypes.

On the other hand, I'm having trouble finding the best way to deal with
premature loop exit.  The annoying Stop flag fits in well with the
existing language.

> Overload resolution rules apply to the Iterate call.  It can even be
> dispatching.
>
> I think that iterators are so specific a construct that if you think
> there's no reasonable way to express them, you should wonder if the
> language lacks expressiveness (or, in the case of Ada, terseness).
> Forcefully adding iterators only doesn't close the underlying gap, and
> just adds yet another gazebo to the language.

True.

> Anonymous subprograms are quite useful in a variaty of contexts (look
> at my transaction example), not just for iterators, and might actually
> be worth the increase in complexity.

True.  I would add anonymous subprograms, and then add a gazebo for the
common case of iterators.  The gazebo is less important.  I also want to
be able to do things that are common in functional languages (map, fold,
etc).  Conveniently.

> It might make sense to replace for/in/loop different keywords (perhaps
> for/in/do or with/in/do).  I'm not sure if the anonymous subprogram
> should be passed exlicitly, like in:
>
>    with (J : Index) in Invoke_Something (Param_1, <>) do ...

I don't understand what you want that to mean.

(If I had designed Ada 83, it would be "for ... do ... end for;".
No "loop".)

****************************************************************

From: Florian Weimer
Date: Thursday, April 14, 2005   1:20 PM

> I find that Stop flag annoying.  I don't want to say "Stop := True;".
> I want to say "exit when ...".

I didn't actually think about that, I added the Stop parameter just to
show that you can use two arguments. 8-(

Maybe anonymous functions should be permitted, too, so you could at
least use "return False;":

   with (Item : in out Element_Type) return Boolean
     in My_Container.Iterate
   do
      ...
   end with;

Or one could define a magic return type (Ada.Iterators.Iterator_Status,
for example).  This iterator type would be automatically used as a
return type if the for/loop variant is used.

   procedure Iterate
     (Container : in out Containter_Type;
      Action : access function
        (Item : in out Element_Type; Stop : out Boolean)
        return Ada.Iterators.Iterator_Status);

   for (Item : in out Element_Type) in My_Container.Iterate loop
      ...
   end loop;

Rather baroque, but I don't see a better way at the moment.

The rules which describe the legality and semantics of exit and return
statements in the anonymous subprogram body are a bit complex, too.
And I doubt there is a convenient way to permit "exit Some_Outer_Loop;".

>> It might make sense to replace for/in/loop different keywords (perhaps
>> for/in/do or with/in/do).  I'm not sure if the anonymous subprogram
>> should be passed exlicitly, like in:
>>
>>    with (J : Index) in Invoke_Something (Param_1, <>) do ...
>
> I don't understand what you want that to mean.

Invoke_Something would be declaed as

   procedure Invoke_Something
    (Param_1 : Object_Type;
     Action : access procedure (J : Index));

"<>" denotes the access-to-anonymous-subprogram value.  Without such a
feature, the possible parameter profiles for Invoke_Something are
rather limited.

****************************************************************

From: Bob Duff
Date: Thursday, April 14, 2005  3:24 PM

> > I find that Stop flag annoying.  I don't want to say "Stop := True;".
> > I want to say "exit when ...".
>
> I didn't actually think about that, I added the Stop parameter just to
> show that you can use two arguments. 8-(

Oh, I thought that was an integral part of your idea.
I guess I don't really understand what you're proposing.

>    procedure Iterate
>      (Container : in out Containter_Type;
>       Action : access function
>         (Item : in out Element_Type; Stop : out Boolean)
>         return Ada.Iterators.Iterator_Status);

Functions can't have 'out' params.  Maybe in Ada 1X they can?

> The rules which describe the legality and semantics of exit and return
> statements in the anonymous subprogram body are a bit complex, too.
> And I doubt there is a convenient way to permit "exit Some_Outer_Loop;".

Yeah.  I'm not sure what's the best way, here.

> >> It might make sense to replace for/in/loop different keywords (perhaps
> >> for/in/do or with/in/do).  I'm not sure if the anonymous subprogram
> >> should be passed exlicitly, like in:
> >>
> >>    with (J : Index) in Invoke_Something (Param_1, <>) do ...
> >
> > I don't understand what you want that to mean.
>
> Invoke_Something would be declaed as
>
>    procedure Invoke_Something
>     (Param_1 : Object_Type;
>      Action : access procedure (J : Index));
>
> "<>" denotes the access-to-anonymous-subprogram value.  Without such a
> feature, the possible parameter profiles for Invoke_Something are
> rather limited.

So you mean "<>" denotes a subprogram whose body is the "..." shown
above?

****************************************************************

From: Florian Weimer
Date: Thursday, April 14, 2005  5:38 PM

> Functions can't have 'out' params.  Maybe in Ada 1X they can?

perhaps giving us

  declare
     e: Element_Type;
     gen: Tree_Walker;
  begin
     while gen.yield(e) loop
        use_it(e);
     end loop;
  end;

:-)

****************************************************************

From: Adam Beneschan
Date: Thursday, April 14, 2005  11:51 AM

> Sigh. That's about at the level of those minus signs. I don't need more of
> that. Maybe next time I'll just keep "real briefs". :-)

BTW, has www.adaic.com/standards/ada05.html been made temporarily
unavailable while minus sign maintenance work is being done, or has it
moved?  (If the former, I hope the time period during which the manual
is unavailable is real brief.)

****************************************************************

From: Gary Dismukes
Date: Thursday, April 14, 2005  12:29 PM

It's moved -- you now need to look at www.adaic.com/standards/ada06.html

****************************************************************

From: Marius Amado Alves
Date: Thursday, April 14, 2005   1:21 PM

It's a pity they bumped the year with the move. I wonder why. Everybody
calls Ada 2005 Ada 2005.

****************************************************************

From: Dirk Craeynest
Date: Thursday, April 14, 2005   1:55 PM

Was a conscious decision taken (how/when?) that the language defined by
the new amendment will informally be called Ada 2006, instead of Ada
2005, the name that we all have been using for quite some time now?

If so, then this is really unfortunate, for various reasons:

- as the name is informal anyway (the "real" name of the language will
  be just "Ada"), the informal name doesn't have to be linked to the
  year that ISO will publish the standard, but can be linked to the
  year that the work on the standard was completed (as some other
  language communities do);

- the new Ada standard is, and has for quite some time been, announced
  widely as "Ada 2005", and changing this to 2006 may appear as a one
  year slip, enforcing the (wrong) idea some have that Ada evolves very
  slowly via a very heavy process;

- changing the 05 in 06 this late in the process will increase the
  confusion on the Internet/Web (existing references may point to
  non-existing pages, searches for "Ada 2005" will not show new
  information, etc.);

- this issue has been discussed in the past on several forums already
  (including this one), and each time there seemed to be a consensus
  that "Ada 2005" was much to be preferred;

- etc.

As this change is not widely known (yet), I propose to reconsider it.

****************************************************************

From: Randy Brukardt
Date: Thursday, April 14, 2005  2:14 PM

I was holding off on a public announcement until after the upcoming ARG
meeting, because by then we will have discussed and decided the nomenclature
issues. (Right now, it is very inconsistent as  to the names.) I *certainly*
did not want a public discussion about names until the ARG had an internal
discussion on the topic (perhaps my opinion is small minority). Now, we're
fated to thousands of messages on the name of the language...

****************************************************************

From: Pascal Obry
Date: Thursday, April 14, 2005  1:39 PM

 > It's a pity they bumped the year with the move. I wonder why. Everybody
 > calls Ada 2005 Ada 2005.

Why? Because it won't be out in 2005 I suppose. Also I find it nice. Less
confusion between Ada95 and Ada05.

****************************************************************

From: Dirk Craeynest
Date: Thursday, April 14, 2005   2:37 PM

= I was holding off on a public announcement until after the upcoming
= ARG meeting, because by then we will have discussed and decided the
= nomenclature issues.

That's a good idea, but will this mean that the .../ada05.html link
will remain dead until then?

= (Right now, it is very inconsistent as  to the names.)

Maybe, but to be honest: I do not remember having seen the name "Ada
2006" used on any web sites nor in any announcements.

A Google search I just did gave 16 results, none of them related to the
Ada language.

= I *certainly* did not want a public discussion about names until the
= ARG had an internal discussion on the topic

Changing the main web page about the new Ada standard on the ada-auth
site risks to spark such a public discussion, though...

= (perhaps my opinion is small minority). Now, we're
= fated to thousands of messages on the name of the language...

That's why I proposed in my previous message to reconsider this change
(at least until after the internal discussion in the ARG).

Randy, everything you listed above gives even more good reasons for not
changing the name now...

PS: Please keep in mind at the ARG meeting that the printed program
for the Ada-Europe'2005 conference is being finalized and goes to
the printers *very* soon.  And everything in there that is related
to the new standard (such as the special half day tutorial) uses the
name "Ada 2005"...

****************************************************************

From: Randy Brukardt
Date: Thursday, April 14, 2005  3:10 PM

Dirk Craeynest writes:

...
> = I *certainly* did not want a public discussion about names until the
> = ARG had an internal discussion on the topic
>
> Changing the main web page about the new Ada standard on the ada-auth
> site risks to spark such a public discussion, though...

Main web site? This is a private-use page that is not linked or referenced
anywhere in public. The public main page is:
   http://www.ada-auth.org/amendment.html

This page only exists to organize the incomplete documents for the ARG. No
public use was intended until the changes were fully inserted into the
documents. The only reason that the files were put on AdaIC was so that they
could be indexed for the search engine (so the "search button" in the pages
would work). I have no idea how that URL got out to the public in the first
place; certainly there was no public announcements or links.

We haven't been actively discouraging people from looking at those
documents, but there was little point in doing so unless you were a formal
reviewer, given the state of incompleteness. The Amendment document shows a
much more complete set of changes.

In any case, no one outside of the ARG was supposed to see that page until
after the ARG meeting, at which point it would reflect whatever decision was
made. Gary *certainly* wasn't supposed to give it out; if there was to be a
public announcement, I would have already made it.

> = (perhaps my opinion is small minority). Now, we're
> = fated to thousands of messages on the name of the language...
>
> That's why I proposed in my previous message to reconsider this change
> (at least until after the internal discussion in the ARG).

The ARG meeting starts Saturday. This won't be undecided for long.

> Randy, everything you listed above gives even more good reasons for not
> changing the name now...

The reason for changing the name now is simply so that we all don't have to
do it later when it is more expensive. We wasted several thousand dollars on
"Ada 94" brochures. It would be better to reflect reality and use Ada 2006.
That always was the name I've used internally, because there never was any
chance of it being approved this year. (And Ada has traditionally used the
standard year for its identifiers.) It will be known as Ada 2006 sooner or
later, it might as well be sooner.

I wanted to call it "Ada 200Y" everywhere, but some people thought that was
too ugly. Given we had no idea when or if we'd finish, that was silly IMHO.

If you mean "now" in today rather than Saturday, well, I don't see the
difference, especially on a private web page.

****************************************************************

From: Dirk Craeynest
Date: Thursday, April 14, 2005  3:47 PM

= Main web site? This is a private-use page that is not linked or
= referenced anywhere in public. The public main page is:
=    http://www.ada-auth.org/amendment.html

On that public main page, the first item under "Other documents" reads

   Drafts of consolidated standard (Ada 95+Corrigendum+Amendment 1)

   This is the home of a set of consolidated documents. Drafts of both
   the Ada Reference Manual and the Annotated Ada Reference Manual are
   available here.

and that title points to <http://www.adaic.com/standards/ada05.html>.

= This page only exists to organize the incomplete documents for the
= ARG. [...]  I have no idea how that URL got out to the public in the
= first place; certainly there was no public announcements or links.

As shown above, there is a prominent link on the amendment.html page,
and it has been found and used for quite some time by several people.

This "working documents" page was quite useful for non-ARG "outsiders"
as well, because it showed a lot of work had been and is being done,
plus showed a clear disclaimer that the page contained a draft which
wasn't fully updated yet.

The current (IMHO premature) name change means that people will wonder
what happened...

[...]
= > = (perhaps my opinion is small minority). Now, we're
= > = fated to thousands of messages on the name of the language...
= >
= > That's why I proposed in my previous message to reconsider this
= > change (at least until after the internal discussion in the ARG).
=
= The ARG meeting starts Saturday. This won't be undecided for long.

Understood.

If the decision will be too use "Ada 2006", I hope "everybody" will
try to get as many references (on the various web pages, wiki projects,
etc.) to "Ada 2005" updated as soon as possible...

****************************************************************

From: Randy Brukardt
Date: Thursday, April 14, 2005  4:17 PM

> and that title points to <http://www.adaic.com/standards/ada05.html>.

My brain must have turned to jelly. I have no idea what would have possessed
me to put that link there; we had decided to keep these documents private
for the time being. (That was supposed to end in February, but I didn't get
them done until a week or so ago.) I've long since forgotten about it -- the
links with it are very stale.

They'll all be gone in an hour or so. (I've got to update that page anyway.)

****************************************************************

From: Marius Amado Alves
Date: Thursday, April 14, 2005  4:56 PM

> ... I have no idea how that URL got out to the public in the first
> place... (Randy)

Maybe you forgot to set up a robots.txt file to block Google's
crawler...

****************************************************************

From: Randy Brukardt
Date: Thursday, April 14, 2005  5:20 PM

> Maybe you forgot to set up a robots.txt file to block Google's
> crawler...

Dirk seems to have answered that one. There wasn't supposed to be any link
to it, and I have no recollection of making one, but since it is there,
clear as day, I obviously did. Probably that was another one of those 2 am
postings that I forgot about as soon as I got a night's sleep (last night's
will probably fall into that category).

****************************************************************

From: Jeffrey Carter
Date: Friday, April 22, 2005  10:57 AM

>    I sympathize with your concern about active and passive,
> but if we use them at all, we have to stick with the established
> meaning for these terms.  It is one thing to invent your
> own terminology.  It is another to use existing terminology
> in exactly the opposite way as the established meaning.

I don't use them at all. The thing that is called an "active iterator"
isn't an iterator (something that iterates) at all. The term used by the
standard containers, Cursor, is much better than Iterator for this type.
Only the thing called a "passive iterator" is an iterator, so it's the
only thing I use the word "iterator" for, so I call it simply an
iterator. I tend to use "Location" or "Position" rather than "Cursor",
but Cursor is fine, too.

> Booch invented, or at least popularized the terms, as far as I
> know.  I understand his logic, which is a user-centric rather
> than a provider-centric view.  Clearly the user is more "active"
> with an active iterator.  With a passive iterator, the user's
> code has to sit around and "wait" to be called.

The Client has to do more with a Cursor. If that's being active, fine.
But it's a Cursor, not an iterator.

> But I admit I have trouble remembering which is which.
> The choice at this point is to find new, more intuitive
> terms, adopt some other set that everyone can understand
> and remember, or use active and passive with highly visible,
> up-front definitions of what they mean.  Using active and
> passive opposite to their established meaning is *not*
> an option, as far as I am concerned.

Pretty much what I said above. One's a Cursor, the other's an iterator.

****************************************************************

From: Jeffrey Carter
Date: Friday, April 22, 2005  10:58 PM

By the way, I only received a big bunch of Ada-Comment messages from Apr
14 on today, in case you're wondering why I'm only now replying.

****************************************************************

From: Matthew Heaney
Date: Saturday, April 23, 2005  6:58 AM

Hmmm.  Sounds like the mail iterator isn't working...

****************************************************************

From: Bob Duff
Date: Saturday, April 23, 2005  8:40 AM

> I don't use them at all. The thing that is called an "active iterator"
> isn't an iterator (something that iterates) at all. The term used by the
> standard containers, Cursor, is much better than Iterator for this type.
> Only the thing called a "passive iterator" is an iterator, so it's the
> only thing I use the word "iterator" for, so I call it simply an
> iterator. I tend to use "Location" or "Position" rather than "Cursor",
> but Cursor is fine, too.

I also am happy to call these things "cursor" and (just plain)
"iterator".  But you and I are not The Terminology Boss, so if
we say "iterator", we will have to put up with people who ask
"which kind of iterator?".  (Perhaps "the kind that iterates"
is a good answer.)  ;-)

****************************************************************

From: Tucker Taft
Date: Saturday, April 23, 2005  9:54 AM

For what it is worth, I don't consider the term "cursor"
equivalent to what other people call "active iterators."
In fact, we changed the name from iterator for this
reason.  The difference between a "cursor" and an
"active iterator" is that a cursor is like a pointer,
and you can reasonably save a cursor and reuse it later.
However, you generally need the container to produce a cursor to the
next or previous item.

By contrast, an iterator combines everything
you need to know, but usually all you can do is get the
current item, check for more items, and advance to the next item.
It makes little sense to "save" an iterator, or make a table of
iterators, whereas it makes sense to make a table of
cursors (i.e. pointers).  Note that both iterators and
cursors have trouble surviving changes to the underlying
containers that are made through other access paths.
If you know the details of how a container is implemented,
you can sometimes reuse cursors across container changes, but
the Ada.Containers packages make few if any promises in this regard.

****************************************************************

From: Bob Duff
Date: Saturday, April 23, 2005  12:04 PM

> For what it is worth, I don't consider the term "cursor"
> equivalent to what other people call "active iterators."
> In fact, we changed the name from iterator for this
> reason.  The difference between a "cursor" and an
> "active iterator" is that a cursor is like a pointer,
> and you can reasonably save a cursor and reuse it later.
> However, you generally need the container to produce a cursor to the
> next or previous item.
>
> By contrast, an iterator combines everything
> you need to know, but usually all you can do is get the
> current item, check for more items, and advance to the next item.
> It makes little sense to "save" an iterator, or make a table of
> iterators, whereas it makes sense to make a table of
> cursors (i.e. pointers).

I'm not sure what you mean.  Are you talking about the operation
that gets the item that the cursor/iterator points at -- whether this
operation takes the container as a parameter, versus having this
information embodied in the cursor itself?  That is:

    Get_Element(A_Cursor) --> element
    Get_Element(A_Container, An_Iterator) --> element

?  What do you mean by "everything you need to know"?

In C++ STL, an "iterator" is the former -- you can get the pointed-to
item without passing the container.  That is, it's like a pointer, as
you say.  So I don't understand how this explains the name change from
iterator to cursor -- they both have essentially the same semantics.

(I prefer the term "cursor", by the way, reserving the term "iterator"
for the sort of thing that actually iterates -- same as Jeff.)

I can't find the terms "active iterator" or "passive iterator" in my STL
book (by Musser and Saini).  They're not in the index.

I also don't understand what you mean by the saving and tables business.
These seem to make sense for both kinds.  It depends whether all the
cursors/iterators in your table must point at the same container,
and whether there is extra overhead to store the container reference in
the cursor, and so forth.

>...  Note that both iterators and
> cursors have trouble surviving changes to the underlying
> containers that are made through other access paths.
> If you know the details of how a container is implemented,
> you can sometimes reuse cursors across container changes, but
> the Ada.Containers packages make few if any promises in this regard.

Well, that problem seems unavoidable.  But I don't think it's a problem
in *most* cases, because usually, you build up a container, and then you
use cursors to access it in a read-only manner.  (Or, maybe you modify
the elements, but you don't usually want to change the "shape" of the
container.)

There are exceptions, of course.  Sometimes you want to iterate through
a queue while sticking new items onto the end.  But even there, it's
usually best to do something like remove-first-item, and then allow
processing of that item to modify the queue.

****************************************************************


Questions? Ask the ACAA Technical Agent