CVS difference for ai12s/ai12-0416-1.txt

Differences between 1.1 and version 1.2
Log of other versions for file ai12s/ai12-0416-1.txt

--- ai12s/ai12-0416-1.txt	2020/12/09 06:27:46	1.1
+++ ai12s/ai12-0416-1.txt	2021/01/09 08:02:16	1.2
@@ -1,4 +1,8 @@
-!standard A.18(2/5)                                  20-12-08  AI12-0416-1/01
+!standard 5.5(9/5)                                   21-01-08  AI12-0416-1/04
+!standard 6.4(9)
+!standard 6.4(10.1/2)
+!standard A.18(2/5)                            
+!standard A.18(5/3)
 !class Amendment 20-12-08
 !status Amendment 1-2012 20-12-08
 !status work item 20-12-08
@@ -11,12 +15,36 @@
 (1) We clarify the use of the term "container" in the introduction of
 the Containers child packages.
 
+(2) Define the term "smallest first".
+
+(3) Add a sentence explaining when a parallel construct with a 
+loop_parameter_specification is complete.
+
 !problem
 
 (1) The term "container type" is used in A.18(12/5). But the only definition
 is associated with aggregates (see 4.3.5) and that isn't really appropriate
 here.
 
+(2) Is_Sorted "Returns True if the elements are sorted smallest first as 
+determined by the generic formal "<" operator; otherwise, Is_Sorted returns 
+False." Smallest first implies that the "<" has to return true for the 
+elements, but that doesn't seem to account for equal elements.
+
+(3) Most parallel constructs have a definition of when the construct is
+complete. For instance, 5.5.2(10.2/5) ends with " In the absence of a transfer
+of control, the associated parallel construct of a parallel generalized
+iterator is complete when all of its logical threads of control are complete".
+There is similar wording in 5.6.1(3/5) for parallel blocks. But there is no
+such wording for parallel loops that iterates over a discrete range, formally
+one with a loop_parameter_specification.
+
+(4) 6.4(10.1/2) [a Dynamic Semantics paragraph] says that a prefixed view
+is equivalent to a call on the underlying subprogram. Equivalences defined
+in Dynamic Semantics only apply to runtime (not Legality). There are a number
+of Legality Rules that apply to calls. Two Legality Rules in 4.1.3 cover two
+important cases, but there don't appear to be any language that would, for
+instance, make calling an abstract subprogram via a prefixed view illegal.
 
 !proposal
 
@@ -24,6 +52,13 @@
 "container" by itself and mention that we can talk about more specific
 things as well.
 
+(2) Define "smallest first".
+
+(3) Add a definition of when a parallel construct with a 
+loop_parameter_specification is complete.
+
+(4) Move 6.4(10.1/2) to Static Semantics (after 6.4(9)).
+
 !wording
 
 [Editor's note: These changes were applied to Draft 28 of the Ada 202x RM, 
@@ -47,7 +82,36 @@
 primary types declared in the child packages of package COntainers, such as
 Vector, List, or Map.
 
+(2) Modify A.18(5/3):
 
+When a formal function is used to provide an ordering for a container, it is 
+generally required to define a strict weak ordering. A function "<" defines 
+a /strict weak ordering/ if it is irreflexive, asymmetric, transitive, and in 
+addition, if x < y for any values x and y, then for all other values z, 
+(x < z) or (z < y).{ Elements are in a /smallest first/ order using such an
+operator if, for every element y with a predecessor x in the order, (y < x) is
+false.}
+
+   AARM Reason: Given a "<" operator that provides a strict weak ordering, 
+   knowing that (y < x) is false is enough to know that (x <= y) is true.
+   For a strict weak ordering, (x = y) when both (x < y) and (y < x) are false.
+   Therefore, it is not necessary to use the "=" operator or test (x < y).
+   We only need to discuss adjacent elements since a strict weak ordering is
+   transitive.
+
+(3) Add to the end of 5.5(9/5):
+
+In the absence of a transfer of control, the associated parallel construct of
+a loop_parameter_specification is complete when all of its logical threads of
+control are complete.
+
+Add an AARM note:
+  Discussion: The rules for completing a parallel construct when there is 
+  a transfer of control are given in 5.1.
+
+(4) Move 6.4(10.1/2) after 6.4(9), under the heading "Static Semantics".
+
+
 !discussion
 
 (1) The term "container" appears to be used to mean whatever is convinient in
@@ -65,6 +129,145 @@
 We use the terms "container type" and "container package" in other wording,
 and it is best to introduce them early.
 
+(2) If elements A and B are equal, then A < B and B < A are both False.
+That means that the correct "smallest first" test isn't simply A < B (if A is
+the "first" element), but (A < B) or (not B < A). (This corresponds to less 
+than or equal.) Because of the requirements of a "strict weak ordering",
+if (A < B) is True, then B < A has to be False. So testing (not B < A) is 
+sufficient.
+
+We define "smallest first" accordingly. We use "predecessor" as that is the
+term used in defining the list containers, and it works as an English term
+when applied to the Vector containers and to arrays.
+
+(3) While 7.6.1(2/2) makes it clear that a sequential construct is "complete"
+when its execution ends, it is much less clear when the execution ends for a
+parallel construct made up of several threads, all of which will end at
+different times. We felt it necessary to explain this for other parallel
+constructs, and it seems necessary to do so for normal parallel loops as well.
+
+Note that we talk about the "associated parallel construct" so that this
+wording clearly applies to parallel reductions and any other parallel
+constructs using a loop_parameter_specification (as does the wording for
+other kinds of iterators). It's not just about parallel loops.
+
+(4) The rules that are needed for a call on a prefixed view include:
+  * Calling an abstract subprogram with a nondispatching call is illegal;
+  * An in out or out parameter shall be a variable;
+  * The anti-order-dependence rules of 6.4.1;
+  * The accessibility checks on an aliased parameter of a function.
+
+In particular, rules that apply to actual parameters have to apply to the
+prefix of a prefixed view. It isn't practical to copy all of those into
+4.1.3.
+
+Instead we change the equivalence to Static Semantics, which makes it apply
+to Legality Rules as well as runtime semantics.
+
+Note that the Legality Rules 4.1.3(13.1/5) and 4.1.3(13.2/2) are NOT
+redundant. They apply not just to calls, but also to uses of a prefixed view
+that are not a call (in particular, a renaming, use as an actual for
+a formal subprogram, or use as the prefix of 'Access [the last is only 
+possible for access-to-protected-procedures]).
+
+It's likely that there are still some rules that should fail for a prefixed
+view that is not a call (especially if prefixed views are extended to untagged 
+types in a future Ada). These cases seem unlikely enough that it isn't worth 
+worrying about them now. For instance, it seems that one could "hide" a local
+object in a renaming and evade the accessibility check on an aliased parameter
+of a function. But for that to happen, one needs a local renaming of a prefixed
+view of a function returning a composite type, with the prefix being a local, 
+AND the function being called in a library-level context (such as being used
+to initialize an allocator of a library-level access type). [Editor's note:
+No simple fix seems available for this particular issue, which is why we chose
+to ignore it at this point.]
+
+!corrigendum 5.5(9/4)
+
+@drepl
+For the execution of a @fa<loop_statement> with the @fa<iteration_scheme>
+being @b<for> @fa<loop_parameter_specification>,
+the @fa<loop_parameter_specification> is first elaborated. This
+elaboration creates the loop parameter and elaborates the
+@fa<discrete_subtype_definition>.
+If the @fa<discrete_subtype_definition> defines a subtype with a null range,
+the execution of the @fa<loop_statement> is complete. Otherwise, the
+@fa<sequence_of_statements> is executed once for each value of the
+discrete subtype defined by the @fa<discrete_subtype_definition> that
+satisfies the predicates of the subtype (or until
+the loop is left as a consequence of a transfer of control).
+Prior to each such iteration,
+the corresponding value of the discrete subtype is assigned to the
+loop parameter. These values are assigned in increasing order unless
+the reserved word @b<reverse> is present, in which case the values
+are assigned in decreasing order.
+@dby
+For the execution of a @fa<loop_statement> that has an @fa<iteration_scheme>
+including a @fa<loop_parameter_specification>, after elaborating the 
+@fa<chunk_specification> and @fa<aspect_specification>, if any, 
+the @fa<loop_parameter_specification> is
+elaborated. This elaborates the @fa<discrete_subtype_definition>,
+which defines the subtype of the loop parameter. If the 
+@fa<discrete_subtype_definition> defines a subtype
+with a null range, the execution of the @fa<loop_statement> is complete.
+Otherwise, the @fa<sequence_of_statements> is conditionally executed once for 
+each value of
+the discrete subtype defined by the @fa<discrete_subtype_definition> that
+satisfies the predicates of the subtype (or until the loop is left as a
+consequence of a transfer of control). Prior to each such iteration, the
+corresponding value of the discrete subtype is assigned to the loop
+parameter associated with the given iteration. If the loop is a parallel
+loop, each chunk has its own logical thread of control with its own copy
+of the loop parameter; otherwise (a @i<sequential loop>), a single logical
+thread of control performs the loop, and there is a single copy of the
+loop parameter. Each logical thread of control handles a distinct
+subrange of the values of the subtype of the loop parameter such that
+all values are covered with no overlaps. Within each logical thread of
+control, the values are assigned to the loop parameter in increasing
+order unless the reserved word @b<reverse> is present, in which case the
+values are assigned in decreasing order. In the absence of a transfer of
+control, the associated parallel construct of a @fa<loop_parameter_specification>
+is complete when all of its logical threads of control are complete.
+
+If a @fa<chunk_specification> with a @fa<discrete_subtype_definition> is 
+present, then the logical thread of control associated with a given chunk 
+has its own copy of the chunk parameter initialized with a distinct value from
+the discrete subtype defined by the @fa<discrete_subtype_definition>. The
+values of the chunk parameters are assigned such that they increase with
+increasing values of the ranges covered by the corresponding loop
+parameters.
+
+Whether or not a @fa<chunk_specification> is present in a parallel loop,
+the total number of iterations of the loop represents an upper bound
+on the number of logical threads of control devoted to the loop.
+
+!corrigendum 6.4(9)
+
+@dinsa
+A subprogram call shall contain at most one association for each formal 
+parameter. Each formal parameter without an association shall have a 
+@fa<default_expression> (in the profile of the view denoted by the @fa<name>
+or @fa<prefix>). This rule is an overloading rule (see 8.6).
+@dinst
+@s8<@i<Static Semantics>>
+
+If the @fa<name> or @fa<prefix> of a subprogram call denotes a prefixed view
+(see 4.1.3), the subprogram call is equivalent to a call on the underlying 
+subprogram, with the first actual parameter being provided by the @fa<prefix>
+of the prefixed view (or the Access attribute of this @fa<prefix> if the first 
+formal parameter is an access parameter), and the remaining actual parameters
+given by the @fa<actual_parameter_part>, if any.
+
+!corrigendum 6.4(10.1/2)
+
+@ddel
+If the @fa<name> or @fa<prefix> of a subprogram call denotes a prefixed view
+(see 4.1.3), the subprogram call is equivalent to a call on the underlying 
+subprogram, with the first actual parameter being provided by the @fa<prefix>
+of the prefixed view (or the Access attribute of this @fa<prefix> if the first 
+formal parameter is an access parameter), and the remaining actual parameters
+given by the @fa<actual_parameter_part>, if any.
+
 !corrigendum A.18(2/2)
 
 @drepl
@@ -80,6 +283,26 @@
 common to all of the containers. A cursor referencing an element in a container
 is considered to be overlapping only with the element itself.
 
+!corrigendum A.18(5/3)
+
+@drepl
+When a formal function is used to provide an ordering for a container,
+it is generally required to define a strict weak ordering. A function "<"
+defines a @i<strict weak ordering> if it is irreflexive,
+asymmetric, transitive, and in addition, if @i<x> < @i<y> for
+any values @i<x> and @i<y>, then for all other values @i<z>,
+(@i<x> < @i<z>) or (@i<z> < @i<y>).
+@dby
+When a formal function is used to provide an ordering for a container,
+it is generally required to define a strict weak ordering. A function "<"
+defines a @i<strict weak ordering> if it is irreflexive,
+asymmetric, transitive, and in addition, if @i<x> < @i<y> for
+any values @i<x> and @i<y>, then for all other values @i<z>,
+(@i<x> < @i<z>) or (@i<z> < @i<y>). Elements are in a @i<smallest first> order
+using such an operator if, for every element @i<y> with a predecessor @i<x> in
+the order, (@i<y> < @i<x>) is false.
+
+
 !ASIS
 
 No ASIS effect.
@@ -108,3 +331,78 @@
 
 ****************************************************************
 
+From: Randy Brukardt
+Sent: Tuesday, December 8, 2020  1:37 AM
+
+In Jean-Pierre's review, he comments on the definition of Is_Sorted:
+
+   The case of equal elements is not addressed. Shouldn't it be:
+
+   Returns True if the elements are sorted smallest first as determined
+   by the generic formal "<" operator {and the generic formal "="
+   operator}
+
+The direct answer here is clear: No, we don't use the formal "=" for sorting. 
+Doing so would greatly complicate the rules for "<" as one would need to worry
+about interactions with "=" as well as defining a strict weak ordering. 
+Moreover, we want the vector sort and the array sort to work the same way, and
+there is no "=" passed into the array sort. And we want to support multiple 
+sorts for each container (or array), just using different "<" operations, the
+equality of elements might even be different for each ordering operation.
+
+But there still seems to be a problem here, in that the wording doesn't take 
+into account the possibility of equal elements. Elements are "equal" if 
+neither A < B nor B < A are True. "Smallest first" seems to imply that A < B
+for all adjacent A and B, but that's not right. The actual requirement has to
+be 
+     (A < B) or (not B < A)
+
+I'm not sure of the best way to fix this. The pedantic solution would be to 
+formally define "smallest first" (that's never done in the RM). We could put 
+that directly below the "strict weak ordering" paragraph in A.18. That would 
+be something like:
+
+     Elements are in a /smallest first/ order using an operator "<" if for an 
+     element A that precedes an element B, (A < B) or (not B < A) is True.
+
+     AARM Reason: For elements that are considered equal for a particular "<" 
+     operator, neither A < B nor B < A are true.
+
+Or we could add a To Be Honest AARM note somewhere that says something similar.
+
+Or we could somehow try to handle equal elements explicitly in the wording.
+(I don't have an idea for this.)
+
+I do think we need to say something somewhere, as we certainly mean to allow 
+sorting equal elements and for Is_Sorted to give a meaningful answer if there 
+are equal elements. And it's not obvious, as J-P's comment shows.
+
+Thoughts?
+
+****************************************************************
+
+From: Randy Brukardt
+Sent: Tuesday, December 8, 2020  9:11 PM
+
+...
+> Or we could somehow try to handle equal elements explicitly in the 
+> wording.
+> (I don't have an idea for this.)
+
+Another idea would be to write Is_Sorted as an expression function, in which
+case no wording would be needed. The sort operation can then be defined in 
+terms of Is_Sorted, again eliminating the English wording. But that wouldn't 
+help the array sorts, which don't have an Is_Sorted operation.
+
+> I do think we need to say something somewhere, as we certainly mean to 
+> allow sorting equal elements and for Is_Sorted to give a meaningful 
+> answer if there are equal elements. And it's not obvious, as J-P's 
+> comment shows.
+> 
+> Thoughts?
+
+Still waiting for thoughts. :-)
+
+I haven't written this up yet, as I don't know the solution to use.
+
+****************************************************************

Questions? Ask the ACAA Technical Agent