Iteration and subprogram calls are in some sense the twin cornerstones of programming. We are all familiar with the ubiquitous nature of statements such as

which in one form or another exist in all (normal) programming languages.

The detail of giving the precise description of the iteration and the indexing is really a violation of abstraction by revealing unnecessary detail. All we want to say is "assign zero to each element of the set A".

However, although it's not too much of a hassle with arrays, the introduction of containers revealed that detailed iteration could be very heavy-handed. Thus, as mentioned in the Introduction (see 1.3.5), suppose we are dealing with a list, perhaps a list of the type Twin declared as

To manipulate every element of the list in Ada 2005, we have to write something like

This reveals the gory details of the iterative process whereas all we want to say is "add X to the component Q for all members of the list whose component P is prime".

There is another way in Ada 2005 and that is to use the procedure Iterate. In that case the details of what we are doing have to be placed in a distinct subprogram called perhaps Do_It. Thus we can write

This avoids the fine detail of calling First and Next but uses what some consider to be a heavy infrastructure.

However, in Ada 2012 we can simply say

Not only is this just five lines of text rather than nine or eleven, the key point is that the possibility of making various errors of detail is completely removed.

The mechanisms by which this magic abstraction is achieved are somewhat laborious and it is anticipated that users will take a cookbook approach (show us how to do it, but please don't explain why – after all, this is the approach taken with boiling an egg, we can do it without deep knowledge of the theory of coagulation of protein material).

We will start by looking at the process using arrays. Rather than

we can write

In the case of a two-dimensional array, instead of

we can write

In Ada 2005 (and indeed in Ada 95 and Ada 83), the syntax for a loop is given by

This is all quite familiar. In Ada 2012, the syntax for loop_statement remains the same but iteration_scheme is extended to give

Thus the new form iterator_specification is introduced which is

The first production defines a generalized iterator whereas the second defines an array component iterator or a container element iterator. For the moment we will just consider the second production which has of rather than in. The iterable_name can refer to an array or a container. Suppose it is an array such as A or AA in the examples above.

We note that we can optionally give the subtype of the loop parameter. Suppose that the type A is given as

then the subtype of the loop parameter (E in the example) if not given will just be that of the component which in this case is simply Integer. If we do give the subtype of the loop parameter then it must cover that of the component. This could be useful with tagged types.

Note carefully that the loop parameter does not have the type of the index of the array as in the traditional loop but has the type of the component of the array. So on each iteration it denotes a component of the array. It iterates over all the components of the array as expected. If reverse is not specified then the components are traversed in ascending index order whereas if reverse is specified then the order is descending. In the case of a multidimensional array then the index of the last dimension varies fastest matching the behaviour of AA in the expanded traditional version as shown (and which incidentally is the order used in streaming). However, if the array has convention Fortran then it is the index of the first dimension that varies fastest both in the case of the loop and in streaming.

There are other obvious rules. If the array A or AA is constant then the loop parameter E or EE is also constant. So it all works much as expected. But do note carefully the use of the reserved word of (rather than in) which distinguishes this kind of iteration from the traditional form using an index.

As another array example suppose we have the following

which is similar to the list example above. In the traditional way we might write

Using the new notation this can be simplified to

where we have added the subtype Twin to clarify the situation. Similarly, in the simple list example we could write 

Note the beautiful similarity between these two examples. The only lexical difference is that The_Array is replaced by The_List showing that arrays and containers can be treated equivalently.

We now have to consider how the above can be considered as behaving like the original text which involves C of type Cursor, and subprograms First, No_Element, Element, Replace_Element and Next.

This magic is performed by several new features. One is a generic package whose specification is

This generic package is used by the container packages such as Ada.Containers.Doubly_Linked_Lists. Its actual parameters corresponding to the formal parameters Cursor and Has_Element come from the container which includes an instantiation of Ada.Iterator_Interfaces. The instantiation then exports the various required types and functions. Thus in outline the relevant part of the list container now looks like

The entities exported from the generic package Ada.Iterator_Interfaces are the two interfaces Forward_Iterator and Reversible_Iterator. The interface Forward_Iterator has functions First and Next whereas the Reversible_Iterator (which is itself descended from Forward_Iterator) has functions First and Next inherited from Forward_Iterator plus additional functions Last and Previous.

Note carefully that a Forward_Iterator can only go forward but a Reversible_Iterator can go both forward and backward. Hence it is reversible and not Reverse_Iterator.

The container packages also contain some new functions which return objects of the type Reversible_Iterator'Class or Forward_Iterator'Class. In the case of the list container they are

These are new functions and are not to be confused with the existing procedures Iterate and Reverse_Iterate which enable a subprogram to be applied to every element of the list but are somewhat cumbersome to use as shown earlier. The function Iterate with only one parameter is used for iterating over the whole list whereas that with two parameters iterates starting with the cursor value equal to Start.

Now suppose that the list container is instantiated with the type Twin followed by the declaration of a list

So we have now declared The_List which is a list of elements of the type Twin. Suppose we want to do something to every element of the list. As we have seen we might write

However, it might be wise at this point to introduce the other from of iterator_specification which is

This defines a generalized iterator and uses the traditional in rather than of used in the new array component and container element iterators. Using this generalized form we can write

In the body of the loop we manipulate the elements using cursors in a familiar way. The reader might wonder why there are these two styles, one using in and the other using of. The answer is that the generalized iterator is more flexible; for example it does not need to iterate over the whole structure. If we write

then the loop starts with the cursor value equal to S; this is using the version of the function Iterate with two parameters. On the other hand, the new array component and container element iterators using of are more succinct where applicable.

The generalized iterators for the list container use reversible iterators because the functions Iterate return a value of the type Reversible_Iterator'Class. The equivalent code generated uses the functions First and Next exported from List_Iterator_Interfaces created by the instantiation of Ada.Iterator_Interfaces with the actual parameters The_List.Cursor and The_List.Has_Element. The code then behaves much as if it were (see paragraph 13/3 of subclause 5.5.2 of the RM)

Of course, the user does not need to know all this in order to use the construction. Note that the functions First and Next used here (which operate on the class Forward_Iterator and are inherited by the class Reversible_Iterator) are not to be confused with the existing functions First and Next which act on the List and Cursor respectively. The existing functions are retained for compatibility and for use in complex situations.

It should also be noted that the initialization of F is legal since the result returned by Iterate is a value of Reversible_Iterator'Class and this is a subclass of Forward_Iterator'Class.

If we had written

then the notional code would have been similar but have used the functions Last and Previous rather than First and Next.

Another point is that the function call F.First will deliver the very first cursor value if we had written The_List.Iterate but the value S if we had written The_List.Iterate(S). Remember that we are dealing with interfaces so there is nothing weird here; the two functions Iterate return different types in the class and these have different functions First so the notional generated code calls different functions.

If we use the form

then the generated code is essentially the same. However, since we have not explicitly mentioned an iterator, a default one has to be used. This is given by one of several new aspects of the type List which actually now is

The aspect we need at the moment is the one called Default_Iterator which as we see has the value Iterate (this is the one without the extra parameter). So the iterator F is initialized with this default value and once more we get

The use of the other aspects will be explained in a moment.

Lists, vectors and ordered maps and sets can be iterated in both directions. They all have procedures Reverse_Iterate as well as Iterate and the two new functions Iterate return a value of Reversible_Iterator'Class.

However, it might be recalled that the notion of iterating in either direction makes no sense in the case of hashed maps and hashed sets. Consequently, there is no procedure Reverse_Iterate for hashed maps and hashed sets and there is only one new function Iterate which (in the case of hashed maps) is

and we note that this function returns a value of Forward_Iterator'Class rather than Reversible_Iterator'Class in the case of lists, vectors, ordered maps, and ordered sets.

Naturally, we cannot put reverse in an iterator over hashed maps and hashed sets nor can we give a starting value. So the following are both illegal

The above should have given the reader a fair understanding of the mechanisms involved in setting up the loops using the new iterator forms. We now turn to considering the bodies of the loops, that is the code marked "do something via cursor C" or "do something to E".

In the Ada 2005 example we wrote

It is somewhat tedious having to write Replace_Element when using a container whereas in the case of an array we might directly write

The trouble is that Replace_Element copies the whole new element whereas in the array example we just update the one component. This doesn't matter too much in a case where the components are small such as Twin but if they were giant records it would clearly be a problem. To overcome this Ada 2005 includes a procedure Update_Element thus

To use this we have to write a procedure Do_It say thus

and then

This works fine because E is passed by reference and no giant copying occurs. However, the downside is that the distinct procedure Do_It has to be written so that the overall text is something like

which is a bit tedious.

But of course, the text in the body of Do_It is precisely what we want to say. Using the historic concepts of left and right hand values, the problem is that The_List(C).Element cannot be used as a left hand value by writing for example

The problem is overcome in Ada 2012 using a little more magic by the introduction of generalized reference types and various aspects. In particular we find that the containers now include a type Reference_Type and a function Reference which in the case of the list containers are

Note the aspect Implicit_Dereference applied to the type Reference_Type with discriminant Element.

There is also a type Constant_Reference_Type and a function Constant_Reference for use when the context demands read-only access.

The alert reader will note the inclusion of aliased for the parameter Container of the function Reference. As discussed in Section 4.2 on subprogram parameters, this ensures that the parameter is passed by reference (it always is for tagged types anyway); it also permits us to apply 'Access to the parameter Container within the function and to return that access value.

It might be helpful to say a few words about the possible implementation of Reference and Reference_Type although these need not really concern the user.

The important part of the type Reference_Type is its access discriminant. The private part might contain housekeeping stuff but we can ignore that. So in essence it is simply a record with just one component being the access discriminant

and the body of the function might be

The rules regarding parameters with aliased (which we gloss over) ensure that no accessibility problems should arise. Note also that it is important that the discriminant of Reference_Type is an access discriminant since the lifetime of the discriminant is then just that of the return object.

Various aspects are given with the type List which as shown earlier now is

The important aspect here is Variable_Indexing. If this aspect is supplied then in essence an object of the type can be used in a left hand context by invoking the function given as the value of the aspect. In the case of The_List this is the function Reference which returns a value of type Reference_Type. Moreover, this reference type has a discriminant which is of access Element_Type and the aspect Implicit_Dereference with value Element and so gives direct access to the value of type Element.

We can now by stages transform the raw text. So using the cursor form we can start with

This is the full blooded version even down to using all.

Using the dereferencing with the aspect Implicit_Dereference we can omit the mention of the discriminant Element and the all to give

Remember that Reference is a function with two parameters. It might be clearer to write this without prefix notation which gives

Now because the aspect Variable_Indexing for the type List has value Reference, the explicit calls of Reference can be omitted to give

It should now be clear that the cursor C is simply acting as an index into The_List. We can compare this text with

which shows that 'Range is analogous to .Iterator.

Finally, to convert to the element form using E we just replace The_List(C) by E to give

The reader might like to consider the transformations in the reverse direction to see how the final succinct form transforms to the expanded form using the various aspects. This is indeed what the compiler has to do.

This underlying technique which transforms the sequence of statements of the container element iterator can be used quite generally. For example, we might not want to iterate over the whole container but just manipulate a particular element given by a cursor C. Rather than calling Update_Element with another subprogram Do_Something, we can write

or simply

Moreover, although the various aspects were introduced into Ada 2012 primarily to simplify the use of containers they can be used quite generally.

The reader may feel that these new features violate the general ideas of a language with simple building blocks. However, it should be remembered that even the traditional form of loop such as

is really simply a shorthand for

Without such shorthand, programming would be very tedious and very prone to errors. The features described in this section are simply a further step to make programming safer and simpler.

Further examples of the use of these new features with containers will be given in Section 8.3.

The mechanisms discussed above rely on a number of new aspects, a summary of which follows and might be found useful. It is largely based on extracts from the RM.

An important difference between Constant_Indexing and Variable_Indexing is that the functions for variable indexing must return a reference type so that it can be used in left hand contexts such as the destination of an assignment. Note that, in both cases, the name can denote several overloaded functions; this is useful, for example, with maps to allow indexing both with cursors and with keys.

Both Constant_Indexing and Variable_Indexing can be provided since the constant one might be more efficient whereas the variable one is necessary in left hand contexts. But we are not obliged to give both, just Variable_Indexing might be enough for some applications.

The reader might care to check that the aspects used in the examples above match these definitions and are used correctly. Note for example that the Default_Iterator and Iterator_Element aspects are only needed if we use the of form of iteration (and both are needed in that case, giving one without the other would be foolish).

This section has largely been about the use of iterators with loop statements. However, there is one other use of them and that is with quantified expressions which are also new to Ada 2012. Quantified expressions were discussed in some detail in Section 3.4 of the chapter on Expressions so all we need here is to consider a few examples which should clarify the use of iterators.

Instead of

which assigns true to B if every component of the array A has value 0, we can instead write

Similarly, instead of

which assigns true to B if some component of the array A has value 0, we can instead write

In the case of a multidimensional array, instead of

we can write

which iterates over all elements of the array AA however many dimensions it has.

We can also use these forms with the list example. Suppose we are interested in checking whether some element of the list has a prime component P. We can write

or perhaps

which uses the explicit iterator form.

© 2011, 2012, 2013 John Barnes Informatics.

Sponsored in part by: