Version 1.7 of 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