Version 1.4 of ai12s/ai12-0360-1.txt

Unformatted version of ai12s/ai12-0360-1.txt version 1.4
Other versions for file ai12s/ai12-0360-1.txt

!standard 5.5.2(2/3)          20-04-26 AI12-0360-1/02
!standard 5.5.2(5/4)
!standard 5.5.2(7/3)
!class Amendment 20-02-04
!status work item 20-02-04
!status received 19-12-03
!priority Low
!difficulty Medium
!subject Procedural iterators for generic procedures
!summary
generic procedural iterators are defined.
!problem
Procedural iterators are a powerful way to iterate without all of the complication of creating a single-use subprogram (and giving it a meaningful name and parameters and so on).
However, the anonymous access-to-subprogram parameter that it depends upon was added to Ada in Ada 2005. For libraries that originate in Ada 95, and for new libraries where the potentially easier analysis associated with generics is important, a generic procedure with a single formal subprogram is often used instead. These generics still need an explicitly declared procedure, and require a lot of housekeeping to declare and call, representing nonproductive work and producing harder-to-read code, and so would benefit from the same kind of syntactic sugar provided for acess-to-subprogram-based iterators. More generally, we don't want to "orphan" the use of generic formal subprograms in iterators.
!proposal
A procedural iterator can work with a generic procedure with a single formal procedure. This maps to an instantiation and a loop body procedure.
If one has the following generic procedure:
generic with procedure Action (Key : Key_Type; Value : Value_Type); procedure Iterate_Some_Structure (Obj : Structure_Type);
The following procedural iterator:
for (Key, Value) of Iterate_Some_Structure (My_Obj) loop
Do_Something_With (Key, Value);
end loop;
would map to:
declare procedure <loop_body> (Key : Key_Type; Value : Value_Type) is begin Do_Something_With (Key, Value); end <loop_body>;
procedure <inst> is new Iterate_Some_Structure (<loop_body>); begin <inst> (My_Obj); end;
Note that the procedural iterator syntax can make the code significantly easier to read and understand, without introducing any fundamentally new semantics.
As part of this proposal, we also simplify the original proposal to allow the iterating procedure to have only one parameter of an anonymous-access-to-subprogram type, thereby eliminating the need for the "<>" even when this parameter is not the last. Allowing only one such parameter had already been recognized as being necessary for the Allows_Exit and Parallel_Iterator aspects to be meaningful, but apparently no separate AI for that had ever been produced.
To simplify the description, we specify that the term "callable entity" within these rules also applies to the case where the name or prefix of the iterator_procedure_call denotes a generic procedure, where it effectively refers to the instance of the generic. The net effect is that most of the legality rules need no wording changes.
!wording
Modify 5.5.3 (1/5):
A procedural_iterator {transforms its loop body into a locally declared procedure, and then passes it to a user-defined iterating procedure as a (generic) actual parameter along with any other parameters specified in the iterator procedure call} [invokes a user-defined procedure, passing in the body of the enclosing loop_statement as a parameter of an anonymous access-to-procedure type], to allow the loop body to be executed repeatedly as part of the invocation of the user-defined procedure.
Replace 5.5.3 (4/5-8/5) with:
iterator_procedure_call ::= name | prefix actual_parameter_part
Modify 5.5.3 (9/5):
The name or prefix given in an iterator_procedure_call shall resolve to denote {either a generic procedure C, or} a callable entity C (the /iterating procedure/) that is a procedure, or an entry renamed as (viewed as) a procedure. {To simplify the description below, the term callable entity is used to refer to the entity denoted by the name or prefix, or the instance thereof if it is a generic procedure.} [Redundant:When there is an actual_parameter_part, the prefix can be an implicit_dereference of an access-to-subprogram value.]
Replace 5.5.3 (10/5-12/5) with:
If C is a generic procedure, the iterator_procedure_call is resolved as though it were a call on an instance of C (the /iterating procedure/); otherwise exactly one of the formal parameters of the callable entity C shall be of an anonymous access-to-procedure type A, and the iterator_procedure_call is resolved as a call on the callable entity C after omitting this formal access parameter.
Modify 5.5.3 (13/5):
{If C is a generic procedure, C shall have exactly one generic formal parameter, which shall be a formal procedure A, with at least one formal parameter in its parameter profile; if C is a callable entity, the} [The] anonymous access-to-procedure type A shall have at least one formal parameter in its parameter profile. {In either case, if} [If] the iterator_parameter_specification is a formal_part, then this formal_part shall be mode conformant with that of A. If the iterator_parameter_specification is a list of defining_identifiers, the number of formal parameters of A shall be the same as the length of this list.
Modify 5.5.3 (15/5):
A loop_statement with an iteration_scheme that has a procedural_iterator is equivalent to a local declaration of a procedure P followed by {:
* if C is a generic procedure, an instantiation of C with P as its only generic actual parameter, followed by a procedure_call_statement whose name or prefix denotes this instance of C (the /iterating procedure/), and whose actual_parameter_part, if any, is the same as that of the iterator_procedure_call;
* otherwise,} a procedure_call_statement that is formed from the iterator_procedure_call by [replacing the <> of the parameter_association_with_box with]{inserting (at an appropriate point) an additional parameter_association for the formal parameter of type A, with explicit_actual_parameter} P'Access.{
}The formal_part of the locally declared procedure P is formed from the [formal_part of the anonymous access-to-procedure type] {parameter profile} of A, by replacing the identifier of each formal parameter of [this] {its} formal_part with the identifier of the corresponding formal parameter or element of the list of defining_identifiers given in the iterator_parameter_specification. The body of P consists of the conditionally executed sequence_of_statements. The procedure P is called the /loop body procedure/.
Modify 5.5.3 (16/5):
The following aspects may be specified for {a generic subprogram S that has exactly one generic formal parameter that is a formal procedure, or for} a callable entity S that has [at least]{exactly} one formal parameter of an anonymous access-to-subprogram type{. In the case of a generic, each instance of the generic subprogram has the same aspect with the same value; the description below is given in terms of a subprogram that is such an instance}:
Modify 5.5.3 (25/5):
[Redundant: For the execution of a loop_statement with an iteration_scheme that has a procedural_iterator, [the procedure denoted by the name or prefix of the iterator_procedure_call (the iterating procedure) is invoked, passing an access value designating the loop body procedure as a parameter]{the iterating procedure (see above) is invoked, with the loop body procedure either specified in the instantiation defining the iterating procedure, or designated by an access-to-procedure parameter}. The iterating procedure then calls the loop body procedure zero or more times and returns, whereupon the loop_statement is complete. If the parallel reserved word is present, the iterating procedure might invoke the loop body procedure from multiple distinct logical threads of control.]
!discussion
Because the procedural iterator is new in Ada 202X, we believe it is appropriate to refine it if we believe it is missing an important use-case. The generic-formal-subprogram-based approach seems at least as common, if not more so, than the anonymous-access-to-subp-based approach to iteration in existing Ada code. We also believe that in systems where any kind of formal verification is important, the minimization of indirect calls is paramount. This refinement of the procedural iterator feature supports that important (and growing) constituency in the Ada community, and even for "everyday" programmers, making this very common paradigm of instantiate-and-call easier to read and understand could be of significant benefit.
There are further possible extensions:
1) We could allow multiple generic formal parameters. However, that would significantly add complexity to the proposed transformation, as we would somehow have to combine generic actuals with procedure call actuals, which sounds like a real headache.
2) We could allow the generic formal subprogram to be a function rather than a procedure, with some value returned by the function to mean "quit now." This would be difficult to standardize. Even if we could agree on a Boolean result, agreeing on whether True or False means "quit now" would be difficult.
We believe the current proposal hits the right balance, and leaves for future revisions possible extensions to the feature.
!example
(See Proposal.)
!ASIS
[Not sure. It seems like some new capabilities might be needed, but I didn't check - Editor.]
!ACATS test
ACATS B- and C-Tests are needed to check that the new capabilities are supported.
!appendix

From: Tucker Taft
Sent: Tuesday, December 3, 2019  5:19 PM

While putting together some slides about the "procedural iterator"
(http://www.ada-auth.org/standards/2xaarm/html/AA-5-5-3.html) I realized that
there is a very similar case which comes up very often, at least in my code,
which might also benefit from the procedural iterator syntactic sugar.  In
particular, I have many, many instances of generic (iterating) procedures
that have exactly one generic formal parameter, which is a formal procedure.
For example:

   generic
      with procedure Action (Key : Key_Type; Value : Value_Type);
   procedure Iterate_Some_Structure (Obj : Structure_Type);

A typical usage is as follows:

   declare
       procedure Process_One (Key : Key_Type; Value : Value_Type) is
       begin
            Do_Something_With (Key, Value);
       end Process_One;

       procedure Process_All is new Iterate_Some_Structure (Process_One);
   begin
       Process_All (My_Obj);
    end;

This is quite similar to the situation of calling an iterating procedure that
has a single access-to-procedure parameter, plus zero or more other parameters.
So perhaps the same syntactic sugar should apply.  That is:

   for (Key, Value) of Iterate_Some_Structure (My_Obj) loop
       Do_Something_With (Key, Value);
   end loop;

I would claim that the "sugared" version is much easier to read and understand
than the gobbledygook above it.  And at least from my experience, I have many
places where I could use this second sort of procedural iterator.  One
interesting aspect of this second sugaring is that the parameters are already
separated into the formal procedure and the other parameters, so there is no
need for a "<>" placeholder.

Comments?

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

From: Joshua Fletcher
Sent: Monday, December 9, 2019 11:07 AM

This proposal doesn't seem like a fair comparison:

It presents a new form of the 'for of' syntax that provides the key and the
value in the loop, and contrasts it with using a generic to manage the loop.

The more accurate contrast would be with a 'for in' loop - especially the
Ada 2012 kind, which can provide access to the iterator (or Cursor) in the
loop.

The existing syntax that someone might use to contrast that with is:

   for Cursor in My_Obj.Iterate loop
      Do_Something_With (Container_Pkg.Key (Cursor), Container_Pkg.Value (Cursor));
   end loop;

(You could also write Do_Something to take a Cursor, depending on its
relationship to the container type)

Note: Here, the Iterate procedure returns an Interator from
Ada.Iterator_Interfaces, and the Cursor type has a Key and Value function.
Not all Cursor types have both, since a key isn't relevant for all
iterate-able structures; Doubly linked lists don't have a meaningful key, and
Vectors have a "To_Index" function instead of a Key function.
A structure comparable two a multi-dimensional array could have multiple keys;
but that's not much different from a key with multiple elements.

I'm not saying it's a bad idea - it would give the 'best of both worlds' of a
"for in" and a "for of" loop in one. - "For in" gives the cursor (which
typically has accessors for key and value), "For of" just gives the value
without the key.)
I prefer "for of" loops for any case where I don't actually need the key
(or index).  If I need the key (or index), I use "for in"

Tucker's suggested new syntax would make it easier to get the key and value
inside the loop (eliminating the step of having to extract them from the
Cursor), but the existing cost of doing so is pretty small because of what was
added in Ada 2012, and doesn't typically require a generic.

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

From: Joshua Fletcher
Sent: Monday, December 9, 2019 12:50 PM

I'm following up on my previous response, as I hadn't fully grasped the power
of the procedural iterators. To me, they appear similar to lambda expressions
and closures in other languages.

I really like the power offered by the procedural iterators.

When we call, for example:
for (Name, Val) of Ada.Environment_Variables.Iterate(<>) loop
   Put_Line (Name & " => " & Val);
end loop;

It appears that we don't need guarantee that "Ada.Environment_Variables.Iterate"
actually does any iterating; We're just giving it the content of the procedure
that it may call in an iteration, or use however it likes.

In the Environment_Variables example, the fact that there's a conceptual
container involved where iterating may happen is completely encapsulated.
It uses the Allows_Exit aspect, but it doesn't need to.
There's a procedure that happens to be called iterate, that takes access to a
procedure, and we just build the procedure as though it were the body of a
loop.

That's really neat.  I like that.

Nothing in the Procedural Iterators section says anything about a "for in"
loop, though, because there's no real concept of a Key or index.
For environment variables, the name is effectively a key, but you can't
actually tell from the spec, aside from human interpretation.
That's an implementation detail.  In reality, Name and Value are just two
parameters of a procedure that the "Iterate" procedure may call zero to many
times. "For of" makes sense.  "For in" doesn't really apply.

I think I'm back to my original answer, though:

If we're at a place in code where we have access to the concept of a container
with keys and values, we can use "for in" to get a cursor that can give us the
key and the value.

We can write:
   for Cursor in My_Obj.Iterate loop
      Do_Something_With (Container_Pkg.Key (Cursor), Container_Pkg.Value (Cursor));
   end loop;

If we don't have access to the fact that we have a container, then we can't
magically manufacture cursors, keys, and values. For the environment variables
example, the Iterate procedure provides the name and the value to procedure it
calls. For Ordered_Maps, the Iterate function returns a
Reversible_Iterator'Class.

If we wanted to use a procedural iterator with, for example, an instance of
ordered maps, we can do so with the other existing "Iterate" procedure
profiled like this:

   procedure Iterate
     (Container : Map;
      Process   : not null access procedure (Position : Cursor));

for (Cursor) of My_Map.Iterate (<>) loop
      Do_Something_With (Container_Pkg.Key (Cursor), Container_Pkg.Value (Cursor));
end loop;

In fact, that's equivalent to the example that is already there:

for (C : Cursor) of My_Map.Iterate loop
   Put_Line (My_Key_Type'Image (Key (C)) & " => " & My_Element_Type'Image (Element (C)));
end loop;

if, for example, the ordered maps container had the following procedure (which
it doesn't, but could):

   procedure Iterate
     (Container : Map;
      Process   : not null access procedure (Key : Key_Type; Value : Element_Type));

Then we could do the following:

for (Key, Value) of My_Map.Iterate (<>) loop
      Do_Something_With (Key, Value);
end loop;

or equivalently:

for (Key, Value) of My_Map.Iterate loop
   Put_Line (My_Key_Type'Image (Key) & " => " & My_Element_Type'Image (Element));
end loop;

This doesn't seem all that different from the existing case with a cursor.

Given that ordered maps are a visible container with an iterator, and Key
Value functions provided, none of this seems necessary for that particular
case, However, being able to use procedural iterators on objects as
illustrated above, will be useful when the other mechanisms for iterating
are encapsulated.


Suppose, for example, someone defined a package like
Ada.Environment_Variables, called Environment_Objects.

The spec is identical, except that all the subprograms call into a tagged
object as their first parameter. You can query Value, and Exists, and call
Set and Clear on the object type defined in the package.
The object type could be implemented under-the-hood with an indefinite
ordered map of strings, but you can't tell from the spec.

From the spec, there's no iterator type or cursor defined, but there is an
iterate procedure:
procedure Iterate (Env : Object; Process : not null access procedure (Name, Value : String));

for such a package, I believe we could call the following:

for (Name, Val) of Environment_Objects.Iterate(My_Object, <>) loop
   Put_Line (Name & " => " & Val);
end loop;


That being the case, the procedural iterators definition seems to cover the
cases for what it is.

The ability to get both key and value in a loop from a publically iterable
type would be an extension to generalized loop iteration.
We have "for in" and "for of", this would give us another kind of "for of",
distinct from procedural iterators.

Unfortunately, that it is potentially confusing with the procedural iterators
also available with similar syntax.

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

From: Tucker Taft
Sent: Tuesday, December 10, 2019  7:39 AM

> I really like the power offered by the procedural iterators.
...

They have turned out to be useful in a number of contexts. 

Unfortunately, I was unable to determine from your responses what you thought
of generalizing this "syntactic sugar" to cover the case of a generic with a
single formal parameter that is a formal procedure.

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

From: Joshua Fletcher
Sent: Tuesday, December 10, 2019  11:17 AM

My thoughts:

You said yourself that this is "quite similar to the situation of calling an
iterating procedure that has a single access-to-procedure parameter, plus
zero or more other parameters."

If the following procedure was defined, you could already use a procedural
iterator, according to what is already written in 5.5.3 of Ada 202X Draft 23:

  procedure Iterate_Some_Structure (Obj : Structure_Type;
      Action : not null access procedure (Key : Key_Type; Value : Value_Type));

So... the idea, then, is that the language would effectively recognize the
generic signature as being equivalent to the access-to-procedure parameter.
(at least in this context)

This would be to make it easier to use existing libraries that chose to use
the generic approach rather than offering a procedure with a single
access-to-procedure parameter.

As it is, we could already wrap the generic if we want to use the procedural
iterator; The following code wraps such a generic and works for what it is in
GNAT, for example:

procedure Wrap_Iterate_Some_Structure (Obj : Structure_Type;
     Action : not null access procedure (Key : Key_Type; Value : Value_Type)) is
  procedure Call_It is new Iterate_Some_Structure (Action => Action.all);
begin
  Call_It (Obj => Obj);
end Wrap_Iterate_Some_Structure;

But your solution avoids having to explicitly instantiate the generic or add
any additional named procedures; it would be like generating and calling the
above procedure without the developer having to write it.

It is definitely a neat idea, but I don't see how it would generalize.


If this becomes part of the language, users might expect it to generalize, or
it just becomes an odd one-off special case;
I'd want to know how else I could use this seemingly powerful capability:
It's basically a light-weight way of using an anonymous ephemeral generic
instantiation... but it only works when there's a only single formal procedure
parameter. I think it is too much of a special case if it's limited to this,
but I'd be interested in other people weighing in.

If we could build on this to allow it to be more general, it could be really
interesting; possibly a part of how to bring generics into the 21st century.
... but right now this is only addressing a case that doesn't even need a
generic.

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

From: Tucker Taft
Sent: Tuesday, December 10, 2019  1:55 PM

OK, thanks for your feedback.

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

From: Randy Brukardt
Sent: Wednesday, February 19, 2020  4:46 PM

Some private discussion reminded me of a thought that I never wrote down on an older proposal...

Back in December, Tucker Taft wrote:

...
> While putting together some slides about the "procedural iterator"
> (http://www.ada-auth.org/standards/2xaarm/html/AA-5-5-3.html)
> I realized that there is a very similar case which comes up very
> often, at least in my code, which might also benefit from the
> procedural iterator syntactic sugar.  In particular, I have many, many
> instances of generic (iterating) procedures that have exactly one
> generic formal parameter, which is a formal procedure.
...
> This is quite similar to the situation of calling an iterating
> procedure that has a single access-to-procedure parameter, plus  zero
> or more other parameters.  So perhaps the same syntactic sugar should
> apply.

I think the basic idea is sound, but I'm rather dubious of letting it apply
*only* to generics with *exactly* one generic formal parameter. This seems more
like a hack than a considered feature.

I've seen iterator generics with other formal parameters, and it would be
annoying to prevent the use of the "sugar" just because someone decided to use
a generic formal parameter rather than a subprogram parameter for setting
bounds:

   generic
      Low, High : in Key_Type;
      with procedure Action (Key : Key_Type; Value : Value_Type);
   procedure Search_Key_Range (Obj : Structure_Type);

Here we have an iterator that returns all of the key, value pairs whose keys
are between the First and Last key values. But your proposed sugaring wouldn't
work.

Similarly, if the iterator was constructed outside of the structure's package,
one might have something like:

   generic
      with package Struct is new Structure_Generic (<>);
      with procedure Action (Key : Struct.Key_Type; Value : Struct.Value_Type);
   procedure Search_Key_Range (Obj : Struct.Structure_Type);

If we don't allow some other parameters, then such iterators would necessarily
have to be inside of the package defining the structure; end users couldn't
create their own. Note that the access-to-subprogram iterator can have
arbitrary other parameters so end users can create there own with some care.

So it seems to me that this sort of thing needs to (optionally) include a full
instance and <> parameter much like the existing form of this sort of iterator.

Of course, that sort of requirement complicates the definition, but it seems
too special case without that.

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

Questions? Ask the ACAA Technical Agent