!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; <> 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 { boolean hasNext(); T next(); void remove(); } interface Iterable { 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. The foreach loop, I believe, translates into: { Iterator 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; > <> 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: <> 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: 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: 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 . = 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 . 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. ****************************************************************