Version 1.1 of ai05s/ai05-0139-2.txt

Using an iterator over one of the Ada 2005 containers libraries requires writing a subprogram which gets called repeatedly with each element of the container. That effectively requires writing the loop body out-of-line from the loop, making the code inside-out of its normal flow, requiring the writing of a lot of extra text, and thus making it much harder to read and understand.

A better mechanism is required.

In addition, using the notion of "accessors" or "references" as defined in AI05-0142 is syntactically awkward. Finally, it is often clearer to iterate over the elements of a container (or array) directly, rather than iterating over a cursor (or index) into the container (or array).

Using accessors for user-defined dereference (rather than simple access values as proposed in AI05-141) has the potential to provide a safer mechanism that might be used for persistence, relocating garbage collection, detection of dangling references, etc. However, using accessors would be syntactically painful compared to a simple ".all."

In all these cases, a modest amount of "syntactic sugar" might make the use of accessors, containers, and iterators more natural and easier to read.

Define a set of "magic" generic units which are linked to some appropriate syntactic sugar for accessors, containers, and iterators:

Note that the routines defined in the magic generic generally match those used in iteration for the Ada.Containers packages, and their meaning is the same. The only difference is that we've added an iterator object parameter to the Next and Previous functions (which is necessary to make them part of the interface).

The interface Basic_Iterator defines a user-defined iterator for the forward direction; the interface Reversible_Iterator defines a user-defined iterator for both the forward and reverse direction.

The function First is expected to deliver the first cursor value for the iterator iterating in the forward direction, or return No_Element if no cursor value is available. The function Next is expected to deliver the next cursor value for the iterator iterating in the forward direction given the previous cursor value returned from a call to First or Next, or return No_Element if no additional cursor values are available.

The function Last is expected to deliver the last cursor value for the iterator iterating in the reverse direction, or return No_Element if no cursor value is available. The function Previous is expected to deliver the next cursor value for the iterator iterating in the reverse direction given the previous cursor value returned from a call to Last or Previous, or return No_Element if no additional cursor values are available.

The generic package Element_References defines two tagged types which can be used for accessing elements of a container or similar structure:

A function that returns a result of a type descended from Element_Reference or Element_Constant_Reference has ".Data.all" implicitly applied to its result at the point of call, if necessary to satisfy overload resolution. This allows the convenient use of accessor functions both on the left-hand-side and right-hand-side of an assignment, and in other contexts. For example:

This last line is equivalent to:

Our final "magic" generic package, Container_Interfaces, defines an interface to be used in conjunction with the Reversible_Iterator defined in Interator_Interfaces, and the element reference types defined in Element_References, as the basis for a container that takes full advantage of our new syntactic sugar (which is further defined below):

Indexed_component syntax may be used with any object of a type descended from the Container interface, as though it were a single-dimensional array indexed by the Cursor type. It is equivalent to a call on Element_Ref in any context that requires a variable; otherwise it is equivalent to a call on Element_CRef. For example:

The last line is equivalent to:

These three generic packages would typically be instantiated as follows:

NEW ITERATOR SYNTAX

Given these three generic packages and their associated types, we then add two new kinds of "for" loop parameter specifications which provide for iteration over containers (and arrays) in a natural way:

The first requires an expression returning an object of a type descended from Basic_Iterator, or Reversible_Iterator if REVERSE appears. The defining_identifier is of the corresponding Cursor type, and can be used to index into the container.

The second requires an expression returning an array, or an object of a type descended from the Container interface defined above.

An example of the first iterator would be:

Some examples of the second iterator would be:

The "of" syntax, suggested by J.P. Rosen, seems to help identify X as an element of the array/container rather than as an index or cursor in the sequence defined by the discrete range or iterator.

USER DEFINED DEREFERENCE (AI05-141)

The generic package Element_References might also be relevant to the notion of a user-defined "dereference" operation suggested in AI05-141. One of the significant problems with AI05-141 as it stands is that there is no operation called when the dereference is "completed." If we presume that the purpose of a user-defined dereference might be to implement some kind of software paging or persistence, then the page on which the designated object resides needs to be "pinned" in memory until the dereference is complete. But there is no user-defined cleanup routine provided in AI05-141. The Element_Reference and Element_Constant_Reference could provide for that, because they are derived from Limited_Controlled.

So the suggestion is that, at least conceptually, there is an element reference object created, where the access discriminant comes from the result of the user-defined dereference, and when the resulting element reference object goes away, a user-defined cleanup routine would be called, perhaps to "unpin" the page on which the designated object resides.

For practical reasons, rather than having the implementor of the storage pool provide extensions of Element_Reference and Element_Constant_Reference, they would instead just provide dereference operations similar to what is suggested in AI05-141, which takes in an "address" that might in fact not really be a machine address but rather an address-sized "locator" for the object that was returned by Allocate, and produces as a result a true machine address, suitable for use as the access discriminant of an element reference object. There would be two of these operations, one for dereferencing an access-to-variable value, and one for dereferencing an access-to-constant value, and the work to be done might be quite different in the two cases (presuming, for instance, that the underlying storage pool is doing software paging). In addition to the dereference operations, the implementor of the storage pool would provide two "cleanup" routines, which would be called when the hypothetical element reference object goes out of scope, again one for access-to-variable and one for access-to-constant.

The import and export operations suggested in AI05-141 might still be provided for conversion to/from longer-lived access values.

AI05-141 suggested that the dereference operation be accomplished through an IN-OUT parameter of type System.Address, allowing it to be the null procedure by default. Given the number of operations we are now talking about, we would suggest defining a distinct ("magic") descendant of Root_Storage_Pool that had these extra operations, two of which would more naturally be functions than procedures. The cleanup operations would ideally take three parameters, the storage pool, the original access value (which might not be a real machine address), and the "real" machine address produced by the dereference operation. Having both the original and the dereferenced value should simplify the cleanup operation.

Here is a possible package System.Managed_Storage_Pools:

Note that the use of element references is completely behind the scenes with this approach. These access values work just like "regular" access values, but behind the scenes:

This is based on the earlier proposal and discussion recorded in AC-0112.TXT. This proposal was modified to address the comments made on that one, and has been simplified considerably.

Note that the iterator interface can be directly applied to a container type (allowing it to be directly iterated) or it can be part of a separate function (which would allow adding additional parameters to the iterator and/or adding additional storage for the iterators). By using interfaces, we give maximum flexibility to the programmer that is using these iterators.

If the creator of the iterator needs extra storage to accomplish the iteration, they can include it in the type of the iterator.

If the creator of the iterator needs to get control when the loop is exited prematurely, they can define a controlled iterator type. In that case, (presuming that the iterator_expression was a function call) when the loop is exited, the Finalization routine for the iterator object will be called.

We provide a form for reverse iterators. Reverse iteration makes sense for many kinds of containers (vectors and lists, for instance). Given that the syntax already exists and every Ada programmer is familiar with it, not providing it would quickly become one of the most common frustrations of programming in Ada. That seems silly.

We could have simplified the proposal by requiring that all iterators support Last and Previous, but iterators where reverse iteration does not make sense would have to raise an exception when Last is called. The proposed features, in contrast, make a compile-time determination as to whether reverse is allowed. That will detect errors earlier; it generally is better to detect errors at compile-time if possible.

It might appear that this proposal would require some solution to the instantiation for private types problem, but as the examples below show, this is not true.

Note that the actual iterator type can be either limited or non-limited. The value of a limited iterator object is that an iterator implementation can assume (presuming that it only exports functions and not types) that the iterator object is created and destroyed with the loop. This allows safe cleanup operations when the loop is exited (as in the examples below). If that capability is not needed, an iterator implementation allow reuse of iterator objects (especially if no temporary storage is needed).

Note that if temporary storage or loop exit actions are needed, the iterator object must be separate from the container object that it is iterating on. Otherwise nested loops on the same container would not work.

The I and J loops need separate temporary storage, which must be provided by the iterator object (the loop can only provide the loop parameter cursor object).

This proposal requires some solution to the modify-in-place problem for the containers packages (see the family of AI05-0142 proposals). Without that, modifying an element in an iterator would require writing an extra subprogram, meaning the new syntax would not have gained anything.

The use of a controlled type for an iterator in this proposal would require bounded containers to be preelaborable units, rather than pure units. We add a prohibition on the actual container from being controlled, so that finalization adverse users could still use the bounded containers (but obviously not the iterators). This seems OK, given that the current accessor proposal (AI05-0142-4) has similar requirements.

It would be nice for an iterator implementation to be able to prevent the creation of iterator objects not associated with a loop. For instance, given the implementation of the example below:

would have the effect setting tampering on My_List and keeping it set until until the object is destroyed (potentially a long time in the future). But this is not the natural thing to do -- it requires a lot more typing than the intended usage -- and no major definitional problems are encountered in this case. We would need a lot more mechanism to prevent the creation of objects outside of the loop context, so we do not try to prevent this misuse.

Alternatives considered:

One option considered was including the name of the cursor type somewhere in the syntax. Something like:

That was not done mainly because differs from the existing syntax for no clear benefit. It would make the type of the identifier clearer, but it also would mean that switching from a discrete iterator to a container one would require some syntax changes that don't really fit into the model. (One solution to that problem would be to optionally add the type name to the discrete for loop as well, but that seems like a bunch of additional changes for little value.)

It should be noted that with this formulation, the existing discrete iterators could be considered just a predefined instantiation of this magic generic for discrete types. The analogy breaks down a bit for ranges (they don't look like a function call), but it isn't hard to imagine such a unification.

A more important consideration was allowing elements of a container to be directly iterated on. That is, the type of the loop parameter could be the element of a container (that is, anything at all) rather than the cursor to the item.

That would require the element type to be included in the generic somewhere, as well as an accessor function.

But the important consideration would be how the iterated element actually is handled. The programmer may only want read-only access to the elements, or they may want to change a copy of the element, or they my need to change the element in place. It is difficult to make these decisions for the programmer, and providing a large family of iterators quickly gets complicated.

Given all of this, and that existing Ada iteration is on read-only index values (which are can be considered a restricted form of cursors), we only provide iterator on cursors, which are treated as constants within the loop. This way the programmer can pick the most appropriate way to access the actual element: via Element, Update_Element, or (hopefully) some form of Modifiable_Element.

This feature could easily be used in the existing Ada.Containers packages. We give a suggested implementation for Ada.Containers.Doubly_Linked_Lists; the other containers could be similar.

The start of the visible part of Ada.Containers.Doubly_Linked_Lists would be modified as follows:

Note that the changes here are the addition of the nested package Cursors, the addition of the instantiation, and the subtype and renames to eliminate the effect of the nested package. The majority of the package is unchanged.

After the existing procedure Reverse_Iterate, we would add a new function:

This would be described as

This could be implemented by defining a controlled type in the private part of Ada.Containers.Doubly_Linked_Lists:

The implementation of these operations would be something like:

Note that we didn't add these interfaces to the actual container types. That was because we wanted these iterators to be a tampering context (thus ensuring that they terminate and do not lead to erroneous execution). Users would be very surprised if a "safe" construct like a for loop caused erroneous execution (which will happen if the node designated by the loop parameter is deleted).

The function Iterate would normally be used directly in a loop:

We could also define a partial list iterator:

where Start and Finish (if not No_Element) would have to be cursors for Container. In this case, the iteration would run from Start to Finish (or No_Element, if Finish is not on the list after/before Start) forward or in reverse. (This would also be a tampering context as above.)

We would use Partial_Iterator directly in a loop:

Some reviewers have said that they would prefer the iterator to work directly on the container object. This would only eliminate a single selected name, which does not seem worth the problems that would be introduced. The example above means that an iterator is written:

Only the truly lazy would find a significant difference from:

Moreover, we are planning (as of this writing) to use a similar mechanism to provide safe accessors. That mechanism also requires writing an extra selector; it would seem bizarre to work hard to eliminate that here, but still handle use it for accessors.

Finally, a direct syntax would not allow nested loops (as different termination code is needed for each loop) unless significant additional magic is defined. Essentially, something like function Iterate would have to be defined internally to the interface to provide the needed temporary space/termination object. This would require far more mechanism than the current proposal.

About the only thing going for the direct syntax is that it would be a bit easier to understand. However, usage of the current proposal is so easy that once a programmer sees an example, they will immediately understand how it works. Understanding the details would rarely be needed.

From: Tucker Taft
Sent: Tuesday, December  8, 2009  5:01 PM


Here is a new variant for AI05-139 on user-defined iterators, etc.  [This is
version /01 of this AI - ED.] It is based on all the earlier proposals,
and incorporates the notes on iterators I passed around at the last ARG meeting.

I removed the wording, and didn't update the discussion, so you will just
have to focus on the !proposal section, which includes some simple examples.

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