Version 1.7 of ai12s/ai12-0326-2.txt

Unformatted version of ai12s/ai12-0326-2.txt version 1.7
Other versions for file ai12s/ai12-0326-2.txt

!standard 5.5(3/5)          19-07-15 AI12-0326-2/04
!standard 5.5.3(15/5)
!standard 5.5.3(17/5)
!standard 5.5.3(18/5)
!standard 5.5.3(19/5)
!standard 5.5.3(20/5)
!standard 5.5.3(21/5)
!class Amendment 19-04-05
!status work item 19-04-05
!status received 19-03-19
!priority Low
!difficulty Medium
!subject Bounded errors associated with procedural iterators
!summary
We define certain bounded errors associated with procedural iterators, and allow for parallel procedural iterators.
!problem
AI12-0189-1 introduced the Allows_Exit aspect to specify that a subprogram is designed to allow use with a procedural iterator where the loop body has an exit or other transfer of control out of the loop.
However, that AI did not explain what restrictions, if any, exist on a subprogram that specifies Allows_Exit. Issues might arise if the subprogram calls the loop body procedure in an abort-deferred region, or if it performs concurrent calls on the loop body procedure.
!proposal
We propose to define certain bounded errors associated with procedural iterators. In particular, we propose to make it a bounded error for an "Allows_Exit" subprogram to call the loop body procedure from an abort-deferred operation (unless the whole loop_statement was within this same abort-deferred operation), as this would interfere with implementing a transfer of control.
To handle the possibility that a procedural iterator subprogram might call the loop body procedure from a parallel (or tasking) construct, we propose to add the reserved word "parallel" to the syntax for procedural iterators, and specify that "parallel" be used only if the callable entity performing the iterator does not allow exit. We propose that it is a bounded error to call the loop-body procedure from multiple logical threads of control if "parallel" is not specified.
!wording
[Author's note: Paragraph numbers in this AI are from draft 20 of the Ada 2020 RM.]
Replace 5.5(3/5) with:
iteration_scheme ::= while condition | for loop_parameter_specification | for iterator_specification | [parallel] for procedural_iterator | parallel [(chunk_specification)] for loop_parameter_specification | parallel [(chunk_specification)] for iterator_specification
Modify 5.5.3(9/5):
The name or prefix given in an iterator_procedure_call shall resolve to denote a callable entity C {the /iterating procedure/} that is a procedure, or an entry renamed as (viewed as) a procedure. ...
Add at the end of 5.5.3(15/5):
{The procedure P is called the /loop body procedure/.}
Modify 5.5.3(16/5) as follows:
The following aspect{s} may be specified for a {callable entity}[subprogram or entry] S that has at least one formal parameter of an anonymous access-to-subprogram type:
Modify 5.5.3(17/5) as follows:
Allows_Exit
The Allows_Exit aspect is of type Boolean. The specified value shall be static. The Allows_Exit {aspect} of an inherited primitive subprogram is True if Allows_Exit is True either for the corresponding subprogram of the progenitor type or for any other inherited subprogram that it overrides. If not specified or inherited as True, the Allows_Exit aspect of a {callable entity}[subprogram or entry] is False. {For an entry, only a confirming specification of False is permitted for the Allows_Exit aspect.}
{AARM Reason: An entry does not allow exit, because implementing a transfer of control out of a task or protected entry creates unnecessarily complex dynamic semantics.}
Modify 5.5.3(18/5, 18.a/5, 18.b/5):
Specifying the Allows_Exit aspect {to be} True for a subprogram [asserts]{indicates} that the subprogram {/allows exit/, meaning that it} is prepared to be completed by arbitrary transfers of control from the [subprogram represented by the access-to-subprogram value]{loop body procedure}[Redundant:, including propagation of exceptions. A subprogram [for which Allows_Exit is True]{that allows exit} should use finalization [for any necessary cleanup, and in particular should not use exception handling to implement cleanup]{as appropriate rather than exception handling to recover resources and make any necessary final updates to data structures}].
Aspect Description for Allows_Exit: An [assertion that]{indication of whether} a subprogram will operate correctly for arbitrary transfers of control.
Ramification: A subprogram that does not need cleanup [meets the assertion]{satisfies the requirements}, and thus can specify Allows_Exit [to]{as} True. {If a subprogram S allows exit, it cannot expect to get control other than via finalization if the loop body procedure initiates a transfer of control as part of a procedural_iterator. In particular, exception handlers in S, even when others handlers, will not be executed when a transfer of control occurs. The mechanism that the implementation uses to implement such transfers of control needs to avoid triggering exception handlers.}
Add after 5.5.3(18/5):
Parallel_Iterator
The Parallel_Iterator aspect is of type Boolean. The specified value shall be static. The Parallel_Iterator aspect of an inherited primitive subprogram is True if Parallel_Iterator is True either for the corresponding subprogram of the progenitor type or for any other inherited subprogram that it overrides. If not specified or inherited as True, the Parallel_Iterator aspect of a callable entity is False.
Specifying the Parallel_Iterator aspect to be True for a callable entity indicates that the entity might invoke the loop body procedure from multiple distinct logical threads of control. The Parallel_Iterator aspect for a subprogram shall be statically False if the subprogram allows exit.
Aspect Description for Parallel_Iterator: An indication of whether a subprogram may use multiple threads of control to invoke the loop body procedure.
AARM Reason: Permitting exit from a parallel procedural iterator introduces additional semantic and implementation complexity.
Modify 5.5.3(19/5):
If a {callable entity}[subprogram or entry] overrides an inherited dispatching subprogram that [has a True Allows_Exit aspect]{allows exit}, {the overriding callable entity also shall allow exit}[only a confirming specification of True is permitted for the aspect on the overriding declaration].{ If a callable entity overrides an inherited dispatching subprogram that has a True Parallel_Iterator aspect, the overriding callable entity also shall have a True Parallel_Iterator aspect.}
Add after 5.5.3(19/5):
A loop_statement with a procedural_iterator as its iteration_scheme shall begin with the reserved word PARALLEL if and only if the callable entity identified in the iterator_procedure_call has a Parallel_iterator aspect of True.
Modify 5.5.3(20/5):
The sequence_of_statements of a loop_statement with a procedural_iterator as its iteration_scheme shall contain an exit_statement, return statement, goto_statement, or requeue_statement that leaves the loop only if the callable entity [C] associated with the procedural_iterator [has an Allows_Exit aspect specified True]{allows exit}.
Add after 5.5.3(21/5):
Dynamic Semantics
[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 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.]
AARM Proof: The stated dynamic semantics are implied by the static semantics given above and the bounded errors given below.
Bounded Errors
If the callable entity identified in the iterator_procedure_call allows exit, then it is a bounded error for a call of the loop body procedure to be performed from within an abort-deferred operation (see 9.8), unless the entire loop_statement was within the same abort-deferred operation. If detected, Program_Error is raised at the point of the call; otherwise, a transfer of control from the sequence_of_statements of the loop_statement might not terminate the loop_statement, and the loop body procedure might be called again.
If a loop_statement with the procedural_iterator as its iteration_scheme (see 5.5) does not begin with the reserved word PARALLEL, it is a bounded error if the loop body procedure is invoked from a different logical thread of control than the one that initiates the loop_statement. If detected, Program_Error is raised; otherwise, conflicts associated with concurrent executions of the loop body procedure can occur without being detected by the applicable conflict check policy (see 9.10.1). Furthermore, propagating an exception or making an attempt to exit in the presence of multiple threads of control might not terminate the loop_statement, deadlock might occur, or the loop body procedure might be called again.
AARM Discussion: Other Ada rules are still in effect for the allows exit subprogram A, of course. For instance, if a transfer of control causes finalization which raises an exception, Program_Error will be propagated by A (rather than the transfer of control). In such a case, the bounded error above would still apply. Another example is the case where an unrelated task is waiting on the normal completion of the loop body procedure call in A. Such a task might end up waiting forever if a transfer of control happens (this is a deadlock situation). This case does not require additional wording, as the same thing would happen if an exception is propagated from the loop body procedure or if A executed a transfer of control (a return statement).
!discussion
We define what happens when we use a procedural_iterator with a callable entity that allows exit, meaning that it does not rely on exception handling to do cleanup, but instead relies on finalization. We do not define the exact mechanism to implement this transfer of control, but we do make it a bounded error to invoke the loop body procedure (a new term introduced by this AI) from an abort- deferred operation (unless the whole loop is within this same operation), because an immediate exit from the calling procedure might be unsafe in that case. If the problem is not detected, we presume the transfer of control might be effectively ignored.
We disallow specifying the Allows_Exit aspect for an entry, and define entries to never allow exit. Supporting an exit from a loop body procedure invoked by a task or protected entry could be extremely complex, and seems to provide little or no added value.
We go further to allow the specification of "parallel" on a procedural iterator, with the semantics that the loop body procedure might be called from within multiple logical threads of control (including potentially multiple tasks). We do not allow exit in such a case, due to the added semantic and implementation complexity. If parallel is not specified, we make it a bounded error to invoke the loop body procedure from multiple logical threads of control (including possibly multiple tasks), because any potential conflicts due to concurrent executions of the loop body procedure would not have been considered by the applicable conflict check policy. The error is bounded rather than considered erroneous, since the presumed expansion would not be erroneous. Of course, erroneous execution might occur due to conflicts between concurrent actions, but that is already specified elsewhere.
!corrigendum 5.5(3/3)
Replace the paragraph:
iteration_scheme ::= while condition
  | for loop_parameter_specification
  | for iterator_specification
by:
iteration_scheme ::= while condition
  | for loop_parameter_specification
  | for iterator_specification
  | [parallel]
    for procedural_iterator
  | parallel [(chunk_specification)]
    for loop_parameter_specification
  | parallel [(chunk_specification)]
    for iterator_specification
chunk_specification ::= 
    integer_simple_expression
  | defining_identifier in discrete_subtype_definition
!corrigendum 5.5.3(0)
Insert new clause:
This is a new clause, so just force a conflict; the change is found in the conflict file.
!ASIS
None needed (anything needed would be part of the original mechanism).
!ACATS test
We should test that it correctly supports PARALLEL only if Allows_Exit is False, and does something sensible when multiple calls on the loop body procedure happen concurrently. Testing the bounded error cases would be difficult, though perhaps feasible given the limited possible consequences.
!appendix

From: Randy Brukardt
Sent: Thursday, May 9, 2019  1:12 PM

I forgot to mention during the that we have a minor problem with:

    The Allows_Exit aspect, if specified, shall be one of the
    identifiers specific to this aspect: No, Sequential, or Parallel.

because "parallel" is not an identifier in Ada 2020 (it's a reserved word).
It wouldn't be syntactically allowed in an aspect_specification. We either
need to allow it in an aspect_specification, or pick a different identifier.
(And I have no ideas for the latter.)

Since we didn't approve this one and dumped it back to Tucker, he can deal
with this in his update.

P.S. When we discussed this privately, we agreed that the container iterators ]
with Allows_Exit would be Sequential. If someone wants parallel execution,
they should use the iterator objects.

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

From: Tucker Taft
Sent: Thursday, May 9, 2019  1:45 PM

> I forgot to mention during the that we have a minor problem with:
>
>    The Allows_Exit aspect, if specified, shall be one of the
>    identifiers specific to this aspect: No, Sequential, or Parallel.
>
> because "parallel" is not an identifier in Ada 2020 (it's a reserved word).
> It wouldn't be syntactically allowed in an aspect_specification. We
> either need to allow it in an aspect_specification, or pick a different
> identifier. (And I have no ideas for the latter.)

We allow reserved words as attribute identifiers, so we could presumably allow
"Parallel" as an identifier specific to an aspect. But if we want to take
pity on the parser, we could follow the example of synchronization_kind and
use multiple words separated by "_".  Hence:

   Allows_Exit => No
   Allows_Exit => Sequential_Loop
   Allows_Exit => Parallel_Loop

...
> P.S. When we discussed this privately, we agreed that the container
> iterators with Allows_Exit would be Sequential. If someone wants
> parallel execution, they should use the iterator objects.

Agreed.  Specifying Allows_Exit => Parallel[_Loop] means that the procedure
normally invokes the loop body procedure from within a parallel construct,
which would be a big-time incompatibility for the container iterators.

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

From: Jean-Pierre Rosen
Sent: Friday, May 10, 2019  12:01 AM

> We either
> need to allow it in an aspect_specification, or pick a different identifier.
> (And I have no ideas for the latter.)

Concurrent ?

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

From: Tucker Taft
Sent: Friday, June 14, 2019  9:15 AM

Dynamic Semantics

  [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 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.]

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

From: Erhard Ploedereder
Sent: Friday, June 14, 2019  1:24 PM

> Hmm. And if "parallel" is not present, ?? .... "might" it not also?,
> can it call the body in arbitrary order but not concurrently?
>
> Seems to me
> that the words leave that entirely open.
>
> Is all this deriveable from previous text? I.e. is this really Redundant?

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

From: Tucker Taft
Sent: Friday, June 14, 2019  2:42 PM

> Hmm. And if "parallel" is not present, ?? .... "might" it not also?,
> can it call the body in arbitrary order but not concurrently?

There is only one loop body procedure, so not sure what you mean by "arbitrary
order."  It calls it zero or more times.  Later we learn it is a bounded error
if it invokes the loop body procedure from a logical thread of control other
than the one that initiated the loop.

> Seems to me
> that the words leave that entirely open.

The bounded error descriptions limit what can be done.

> Is all this deriveable from previous text? I.e. is this really Redundant?

It is derivable from text, if you include the bounded errors (which come
afterward).

Mostly I was trying to address your concern that we never made it clear what
was the purpose of the "parallel" keyword.  We can debate whether this is
redundant, but the important question for me is whether these words address
your question of what happens (in a positive sense) when the reserved word
"parallel" is present.  Do you think they address that concern?

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

From: Erhard Ploedereder
Sent: Friday, June 14, 2019  5:16 PM

Agreed that the intent of Parallel is now reflected.

I went on to discuss wording ....

The above (line 1) only applies if this text is not Redundant (or there is
text elsewhere about Parallel semantics, which apparently there isn't).

The other comments are addressing the user question "if my loop body proc.
has side-effects, can I rely on any order (the words right now say "no", you
can only rely on the body to be executed possibly many times - presumably
once for each iteration value, but even that isn't said) or at least on the
absence of races caused by concurrent execution? (the words right now are
mum on this question)"

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

From: Tucker Taft
Sent: Saturday, June 15, 2019  2:03 AM

> Agreed that the intent of Parallel is now reflected.

Good.

>
> I went on to discuss wording ....
>
> The above (line 1) only applies if this text is not Redundant (or
> there is text elsewhere about Parallel semantics, which apparently there isn't).
>
> The other comments are addressing the user question "if my loop body
> proc. has side-effects, can I rely on any order (the words right now
> say "no", you can only rely on the body to be executed possibly many
> times - presumably once for each iteration value, but even that isn't
> said) or at least on the absence of races caused by concurrent
> execution? (the words right now are mum on this question)"

Your questions don't particularly make sense to me because the "iterating
procedure" is an arbitrary Ada procedure, potentially one that is written by
the user.  So the notion that there is a well defined sequence of "iteration
values" is in the eye of the beholder.  The iterating procedure could flip a
coin, query the user, read a database, etc.  The language knows nothing about
the iterating procedure.  It is a "regular" Ada procedure that just happens
to have a parameter of an anonymous access-to-procedure type.  These dynamic
semantics are redundant because the static semantics establishes an
equivalence between the original loop_statement and a procedure call.

We define some bounded errors to limit a little bit what the iterating
procedure can do, but these errors can be detected only by looking at the
external behavior.  For example, if the loop body procedure is called on a
thread that is different from the one that called the iterating procedure,
we can presumably detect that and complain.  But we have no way of looking
"inside" the iterating procedure, from a language standard point of view.
Of course a smart compiler could look inside the iterating procedure, but
we don't presume that at all in this section.

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

From: Tucker Taft
Sent: Sunday, June 16, 2019  4:56 AM

This adds a new aspect Parallel_Iterator as proposed by JP for procedural
iterators. [This is version /03 of the AI - Editor.]

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

From: Randy Brukardt
Sent: Tuesday, July 16, 2019  7:14 PM

> This adds a new aspect Parallel_Iterator as proposed by JP for 
> procedural iterators.

Here is a bunch of "for the record" corrections (I've already discussed these
all with Tucker and he concurs with the changes):

(1) In many places, we say "subprogram or entry", and in other places, we say 
"callable entity". I've tried to consistently use "callable entity" in the 
wording changes (I didn't check other existing wording). [Note that if the 
wording just uses "subprogram", then I made no change.]

(2) There are missing parens in the insertion in the change for 5.5.3(9/5). 
This should be:

Modify 5.5.3(9/5):
 
   The name or prefix given in an iterator_procedure_call shall resolve  
   to denote a callable entity C {(the /iterating procedure/)} that is a  
   procedure, or an entry renamed as (viewed as) a procedure. ...

(3) The "allows exit" wording in 5.5.3(17/5) requires that entries only allow 
a "confirming specification of False". But there's nothing that says the value
is False for an entry if there is no specification, and it's weird to "confirm"
something undefined. Additionally, the entry wording never says what is being 
confirmed (it's sort of obvious, but it's better to be explicit). So I suggest
that the wording be more similar to the original, and a bit more explicit. Thus:

Modify 5.5.3(17/5) as follows:
 
  Allows_Exit
 
    The Allows_Exit aspect is of type Boolean. The specified value shall
    be static. The Allows_Exit {aspect} of an inherited primitive subprogram is
    True if Allows_Exit is True either for the corresponding subprogram
    of the progenitor type or for any other inherited subprogram that it
    overrides. If not specified or inherited as True, the Allows_Exit
    aspect of a {callable entity}[subprogram or entry] is False. {For an 
    entry, only a confirming specification of False is permitted for the 
    Allows_Exit aspect.}

(4) The wording change of 5.5.3(19/5) deleted "or entry", presumably because 
an entry can only be specified as False (as in the previous paragraph). 
However, an abstract subprogram that allows exit could be implemented by an 
entry, and we surely want such a thing to be illegal. It's also the case 
that this paragraph is weirdly written in terms of confirming specifications, 
whereas similar paragraphs for nonblocking (9.5(66/5)) and nonreturning 
subprograms (6.5.1(6/5)) are worded in terms of the aspect value (or its 
property name, if defined). So I think the entire paragraph should be 
reworded as:

Modify 5.5.3(19/5):
 
   If a [subprogram or entry]{callable entity} overrides an inherited  
   dispatching subprogram that [has a True Allows_Exit aspect]{allows 
   exit}, {the overriding callable entity also shall allow exit}[only a  
   confirming specification of True is permitted for the aspect on the  
   overriding declaration].{ If a callable entity overrides an  
   inherited dispatching subprogram that has a True Parallel_Iterator  
   aspect, the overriding callable entity also shall have a True  
   Parallel_Iterator aspect.}

(5) Lastly, the new paragraph following 5.5.3(19/5) says "parallel shall be 
used if Parallel_Iterator is True". However, this is intended to be 
exclusive -- this should say "if and only if" so that we don't have the 
weird situation of sequential things (and especially those that allow exit) 
being declared parallel. Thus:

Add after 5.5.3(19/5):
 
   A loop_statement with a procedural_iterator as its iteration_scheme  
   shall begin with the reserved word PARALLEL if and only if the 
   callable entity identified in the iterator_procedure_call has a 
   Parallel_iterator aspect of True.

Only this last item (5) makes any change to the semantics, and it's pretty 
clear that we intended the "if and only if" semantics here.

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

Questions? Ask the ACAA Technical Agent