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

Differences between 1.9 and version 1.10
Log of other versions for file ai12s/ai12-0242-1.txt

--- ai12s/ai12-0242-1.txt	2018/05/11 05:58:41	1.9
+++ ai12s/ai12-0242-1.txt	2018/10/16 00:46:15	1.10
@@ -1,4 +1,4 @@
-!standard 4.5.9 (0)                                18-03-01    AI12-0242-1/03
+!standard 4.5.9 (0)                                18-10-14    AI12-0242-1/04
 !class Amendment 14-06-20
 !status work item 14-06-20
 !status received 14-06-17
@@ -7,8 +7,9 @@
 !subject Reduction Expressions
 !summary
 
-Two New Attributes to facilitate reduction via a Reduce Attribute for
-sequential reduction and Parallel_Reduce Attribute for parallel reduction.
+Two New Attributes are introduced to facilitate reduction;
+A Reduce Attribute for sequential reduction and a Parallel_Reduce
+Attribute for parallel reduction.
 
 !problem
 
@@ -29,9 +30,9 @@
 specification.
 
 It would be useful if such summarizations could be expressed in a simpler, more
-concise manner, such as an expression, without always having to write another subprogram.
-The proposed solution is to allow an Attribute to be applied to an array object to provide
-the summarization.
+concise manner, such as an expression, without always having to write another
+subprogram. The proposed solution is to allow an Attribute to be applied to an
+array object or iterable container object to provide the summarization.
 
 Ada 83 was already a pretty good language for "hybrid" functional/imperative
 programming, because you can have a sequence of declarations that progressively
@@ -91,19 +92,26 @@
 to determine whether and where to insert parallelism. It is important in the
 context of Ada to have sufficient annotations to allow the compiler to both
 check the safety of explicit parallelism, and also safely insert implicit
-parallelism.  Hence the importance of the Global and Nonblocking annotations.
+parallelism. Hence the importance of the Global and Nonblocking annotations.
 
-One of the strengths of Ada is in the area of safety critical and high integrity
-systems. Ada has a unique opportunity to extend its offering in these areas by
-providing parallelism capabilities that can be statically checked by the
-compiler to help the programmer eliminate data races.
+It is also important to allow the programmer to indicate explicitly whether
+parallelism should be applied, as it documents to the reader that performance
+is important to the user, and makes it clear that parallelism is to be applied.
+For instance, a compiler might choose to conservatively apply parallelism,
+only in cases where it can statically determine that the performance would
+be guaranteed to benefit from the parallelism. A programmer might want to
+override the conservatism of the compiler and experiment with parallelism to
+measure the benefits, and then deploy the code in the form that provided the
+optimal performance. This is why the Parallel_Reduce attribute is included
+in this proposal.
 
 !proposal
 
 This proposal depends on the facilities for aspect Global (AI12-0079-1) and for
 aspect Nonblocking (AI12-0064-2). Those proposals allow the compiler to
 statically determine where parallelism may be introduced without introducing
-data races.
+data races. This proposal also depend on parallel iteration support for
+containers (AI12-0266-1).
 
 The goals of this proposal are to provide a mechanism for expressing a
 summarization of a set of values. Such a summarization is known as a reduction.
@@ -115,727 +123,206 @@
 - provides safety by eliminating data races and logic errors.
 - fits in well with existing Ada syntax
 
-Reduction Attributes
----------------------
-
 This model proposes two new attributes, 'Reduce, and 'Parallel_Reduce which can
-be used to combine the values of the prefix which denotes an array object into a
-single result. This mechanism is called reduction. The 'Reduce attribute is
+be used to combine the component values of an array or the element values
+of an iterable container object, into a single result value.
+
+This mechanism is called reduction. The 'Reduce attribute is
 intended to provide sequential reductions by default, unless the compiler can
 determine it is safe and beneficial to performance to implicitly introduce
 parallelism. The 'Parallel_Reduce attribute is intended to allow the programmer
 to explicitly request that a reduction be performed in parallel, which is useful
 because the compiler is not always able to make a correct assessment statically
-whether injecting parallelism with improve instead of detract from performance.
-When a compiler cannot make that determination, it is more apt to choose
+whether injecting parallelism will improve instead of detract from performance.
+Also, a compiler may not have the semantic knowledge to know how to combine
+the results of multiple logical threads of control when the subtype of the result
+is different than the subtype of the values being summarized.
+
+When a compiler cannot make the determination whether parallelism is worthwhile,
+or cannot determine how to apply the parallelism, it is likely to choose
 sequential processing because it is simpler, and more deterministic. By allowing
 the programmer to request parallelism explicitly, the compiler does not need to
 make the assessment, and the programmer can easily revert to sequential
-processing with by simply replacing the parallel version of the attribute with
+processing by simply replacing the parallel version of the attribute with
 the sequential one.
 
-The Parallel_Reduce attribute activates the necessary static checks by the
-compiler to ensure that the parallelism can safely be introduced, without
-necessarily requiring analysis to determine if there is a performance benefit to
-the parallelism. The two attributes are similarly named to make it easier for
-the programmer to switch between parallelism and sequential implementations,
-such that performance measurements and other similar techniques can be employed
-to help the programmer decide which attribute is the better choice for a
-particular problem.
+Both the Reduce and Parallel_Reduce attributes allow the programmer to
+name a user defined reducer subprogram to combine values from two iterations
+into a single value. The Parallel_Reduce attribute also allows the programmer
+to specify a user defined combiner subprogram to combine the results from
+multiple logical threads of control. This is needed in cases where the
+subtypes of the reducer subprogram parameters are not the same. If the subtypes
+of the reducer subprogram parameters are the same, then if the combiner subprogram
+is not specified, the reducer subprogram is also implicitly used as the
+combiner subprogram.
+
+The Parallel_Reduce attribute activates the necessary static checks (see
+AI12-0267-1) of the compiler to ensure that the parallelism can safely be
+introduced, without necessarily requiring analysis to determine if there is a
+performance benefit to the parallelism.
 
 The prefix of the 'Reduce and 'Parallel_Reduce attribute is either an array
-object or a container object. This includes objects created by array aggregates,
-or container aggregates.
+object or an iterable container object. This includes objects created by
+array aggregates, or iterable container object aggregates (see AI12-0212-1).
 
-The 'Reduce attribute and 'Parallel_Reduce attribute both accept two arguments.
-The first argument denotes a binary subprogram or operator. If the subprogram is
-a function, then the function is of the form;
-
-    function Combiner (L, R : S) return S;
-
-The type of the parameters and result are of the same type as the component or element
-objects associated with the attribute prefix.
-
-If the subprogram is a procedure, then the procedure is of the form;
-
-    procedure Combiner (L : in out S; R :  S);
-
-In either case, such a subprogram is called a *combiner_subprogram*. The
-combiner subprogram is called once for every value associated with the prefix of
-the attribute, where each value of the prefix is passed in as the second
-argument of the combiner subprogram, and results from previous calls are passed
-in as the first argument of the combiner subprogram.
-
-For the very first call to the combiner subprogram, the second argument of the
-attribute is passed as the first argument of the combiner subprogram, since
-there are no previous results yet determined. This second argument of the
-attribute is called the initial value.
-
-The initial value also serves to be the result of the attribute for the
-case when there are no iterations performed (E.g. For the case when the
-attribute prefix denotes a null array).
-
-In order for a 'Parallel_Reduce attribute reference to be legal, the combiner
-subprogram needs to have the Associative aspect. The Associative aspect is a
-Boolean aspect indicating that the subprogram can be applied to combine a set of
-values and provide equivalent results regardless of the grouping of the values,
-given that the order of the values is preserved. For instance, integer addition
-is considered to be an associative operation, since (A + B) + C = A + (B + C).
-The Associative aspect is more of a documentation artefact, since a compiler is
-unlikely to be able to determine if the result of an operation is in fact
-associative. We can define the aspect on language defined operations and
-libraries which can go a long way to catch errors. For user defined subprograms,
-we would require the programmer to apply the Associative aspect, which makes the
-programmer give consideration as to whether the operation is in fact associative
-or not.
-
-There is a thread of control associated with each value of the prefix. Each
-thread of control (i.e. tasklet, see AI12-0119-1), needs to accumulate its
-partial result into an implicit accumulator variable. This implicit variable is
-of the type of the combiner subprogram parameters, and is initialized to have
-the first value to be processed by the tasklet, unless the tasklet is assigned
-to process the first object or element of the prefix, in which case, the
-implicit variable is initialized to the value of the Initial_Value of the
-attribute reference.
-
-Once each tasklet has generated its local partial result, it can combine its
-result with other tasklets using the combiner subprogram. The multiple tasklet
-results are combined two at a time.
-
-For parallel execution, the 'Parallel_Reduce attribute is expected to generate
-an associative result based on the values of the prefix, but otherwise is not
-restricted. The combiner for 'Reduce does not need to have the Associative
-aspect. The combiner subprogram can be non-commutative (e.g. vector
-concatenation), as it is expected that the implementation will ensure that the
-tasklet results are combined while preserving the original ordering of the set
-of input values of the attribute prefix as would be consistent with sequential
-execution.
+For parallel execution, the user supplied reducer subprogram and combiner
+subprogram can be non-commutative (e.g. vector concatenation), as it is expected
+that the implementation will ensure that the results of the logical threads of
+control are combined while preserving the original ordering of the set of input
+values of the attribute prefix as would be consistent with sequential execution.
 
 !wording
 
-Add after 3.6.2(10)
+Add after 4.9(8)
 
-For a subtype S of a component of an array type A or element of a container type
-C, and a corresponding object O of the array or container type, which is denoted
-by the prefix of a Reduce or Parallel_Reduce attribute reference:
+"a reduction_expression whose prefix statically denotes a statically
+constrained array object or array subtype, and whose attribute_designator
+is Reduce, and whose reducer_subprogram denotes a static functions;"
 
-kA Combiner_Subprogram is a subprogram that accepts exactly two parameters and
-can be iteratively called to summarize the prefix object to produce a single
-result.
+Add New subclause
 
-A Combiner_subprobram either denotes a function with the following
-specification:
+4.5.9 Reduction Expressions
 
-   function Combiner(L, R : S) return S;
+A Reduction expression provides a way to write a value that denotes a
+combination of the component values of an array or of the
+element values stored in an /iterable container object/
+(see 5.5.1).
 
-or denotes a procedure with the following specification:
+Syntax
 
-   procedure Combiner(L : in out S; R : S);
+reduction_specification ::= /reducer_/name, /initial_value_/expression[, /combiner_/name]
 
-[RLB: Examples have shown that an asymetric combiner is very useful. The second
-operand should be allowed to be any type, and that matches the element type
-of the iterator of the prefix type; the other operand specifies the type
-of the result of the attribute.]
-
-O'Reduce(Combiner, Initial_Value)
-
-   For a prefix denoting an object of an array or container, O'Reduce is an
-   expression that summarises the components or elements of O by applying the
-   named Combiner_Subprogram and initial value to all the values associated with
-   the attribute prefix.
-
-[RLB: A "container" is not a technical term, and even if it was, it's the wrong
-thing. What we need here is a full object iterator, essentially an "of" form. The
-resolution requirement should probably be an object of any composite type, and
-then have a Legality Rule of the form that the attribute is illegal if
-the type of the prefix does not have an "of" iterator (need technical terms, of
-course). The element type involved comes from that iterator, so this has an
-effect on the resolution of the combiner.]
-
-O'Parallel_Reduce(Combiner, Initial_Value)
-
-   For a prefix denoting an object of an array or container, O'Reduce is an
-   expression that summarises the components or elements of O by applying the
-   named Combiner_Subprogram and initial value to all the values associated with
-   the attribute prefix, using parallel execution. The Combiner_Subprogram shall
-   have the Associative aspect with the value True. See (9.12). The
-   Combiner_Subprogram shall have the Non_Blocking aspect with the value True.
-   See (9.5). The Combiner_Subprogram shall have the Global aspect and the
-   Global aspect shall not identify any global variables that are not
-   synchronized.
+A /Reduction Expression/ is an attribute reference where the identifier
+of the attribute_reference is Reduce or Parallel_Reduce and the expression
+of the attribute_designator is a reduction_specification.
 
 Name Resolution Rules
-
-The expected type of a Reduce or Parallel_Reduce attribute reference is any
-nonlimited type.
-
-AARM Note
-The prefix can be a (qualified) array or container aggregate. The prefix can
-denote an object of a multi-dimensional array.
-
-
-   Dynamic Semantics
-
-For a Reduce attribute reference, the combiner subprogram denoted by the
-attribute reference is first called passing the Initial_Value of the attribute
-reference as the first parameter, and the first value associated with the
-attribute prefix as the second parameter. The Combiner_Subprogram is then called
-repeatedly for each subsequent value associated with the attribute prefix where
-the result output by the previous call is passed as the first parameter to the
-Combiner_Subprogram, and the subsequent value of the prefix is passed as the
-second parameter. This continues until all values of the prefix have been
-processed. The result of the last call to the Combiner_Subprogram is the result
-of the expression. If the prefix of the attribute reference denotes a null range
-of values, then the Initial_Value is the result of the expression.
-
-[RLB: "repeatedly" doesn't explain what really happens. This needs to be worded
-in terms of the "of" iterator for the type of the prefix (especially important
-for the container case).]
-
-For a Parallel_Reduce attribute reference, each component or element of the
-prefix is assigned to an executor. (See 9.12). The executor associated with the
-first value of the prefix calls the Combiner_Subprogram using the Initial_Value
-of the attribute reference as the first parameter of the call, and using the
-first value as the second parameter. Any other consecutive values assigned to
-the same executor involve repeated calls to the Combiner_Subprogram, where the
-result output by the previous call is passed as the first parameter to the
-Combiner_Subprogram, and the subsequent value of the prefix is passed as the
-second parameter. For executors assigned to other components or elements of the
-prefix, the result for that executor is initially assigned the value from the
-lowest indexed value assigned to that executor. Any other consecutive values
-assigned to the same executor, involve repeated calls to the
-Combiner_Subprogram, where the result output by the previous call is passed as
-the first parameter to the Combiner_Subprogram, and the subsequent value of the
-prefix is passed as the second parameter. The results from the executors are
-combined similarly, by calling the Combiner_Subprogram to combine the results
-from two Executors whose results corresond to consecutive ranges of value of the
-attribute prefix. This process repeats until all Executors have combined all
-intermediate results into a final value. This result is the result of the
-expression. If the prefix of the attribute reference denotes a null range of
-values, then the Initial_Value is the result of the expression.
-
-AARM Note:
-
-It is important to specify which argument of the reducer function is used as for
-feeding back prior results, because certain reductions, such as vector
-concatentation, can be non-commutative operations. In order to return a
-deterministic result for parallel execution, it is necessary to specify which
-parameter is used for feedback of prior results. When combining results from two
-tasklets, the results associated with the array components with the lower index
-value are passed as argument L of the reducer function. This is also necessary
-for non-commutative reductions to work properly.
-
-
-Examples
-
-  Calculate the sum of elements of an array of integers
-
-  A'Reduce("+",0)  -- See 4.3.3(43)
-
-  Determine if all elements in a two dimensional array of booleans are set to
-  true
-
-  Grid'Reduce("and", true);  -- See 3.6(30)
-
-  Calculate the minimum value of an array of integers in parallel
-
-  A'Parallel_Reduce(Integer'Min, Integer'Last)
-
-  Determine how many integers in an array are prime numbers
-
-  Prime_Count : contant Natural := (for P of A when Is_Prime(P) => 1)'Reduce("+",0);
-
-  An expression function that returns its result as a Reduction Expression
-
-  function Factorial(N : Natural) return Natural is
-     ((for J in 1..N => J)'Reduce("*", 1));
-
-  An expression function that computes the Sin of X using Taylor expansion
-
-  function Sin(X : Float; Num_Terms : Positive := 5) return Float is
-     ((for I in 1..Num_Terms => (-1.0)**I * X**(2*I-1)/Float(Fact(2*I-1)))
-        'Reduce("+", 0.0));
-
-   A reduction expression that outputs the sum of squares
-
-   Put_Line ("Sum of Squares is" &
-             Integer'Image((for I in 1 .. 10 => I**2)'Reduce("+", 0));
-
-   An expression function to compute the value of Pi
-
-   --  See 3.5.7(21)
-   function Pi (Number_Of_Steps : Natural := 10_000) return Real is
-     (1.0 / Number_Of_Steps *
-       (for I in 1 .. Number_Of_Steps =>
-           (4.0 / (1.0 + ((Real (I) - 0.5) * (1.0 / Number_Of_Steps))**2)))
-              'Reduce("+", 0.0));
-
-AARM Implementation Advice
-
-For a prefix of a Reduce or Parallel_Reduce attribute reference that is an
-aggregate, the creation of a temporary object is not necessary if each value
-of the aggregate object that would have been created is iteratively applied to
-the Combiner_Suprogram of the attribute reference.
-
-[RLB: We need more than this; we also need a permission to interleave the
-evaluation of the aggregate choices and the reduction. That has to be
-normative as it overrides the canonical semantics. That probably ought to
-be a "Notwithstanding" rule.
-
-Wording Changes from Ada 2012
-Reduce attribute is new.
-Parallel_Reduce attribute is new.
-
-Modify 4.5.1(3) with
-
- function "and"(Left, Right : T) return T {with Associative}
- function "or" (Left, Right : T) return T {with Associative}
- function "xor"(Left, Right : T) return T {with Associative}"
-
-Modify 4.5.3(2)
-
-"function "+"(Left, Right : T) return T{ with Associative}
- function "-"(Left, Right : T) return T
-"
-
-Modify 4.5.3(4)
-
-"function "&"(Left : T; Right : T) return T {with Associative}
-function "&"(Left : T; Right : C) return T  {with Associative}
-function "&"(Left : C; Right : T) return T  {with Associative}
-function "&"(Left : C; Right : C) return T  {with Associative}"
 
-Modify 4.5.5(2)
-function "*"  (Left, Right : T) return T {with Associative}
-function "/"  (Left, Right : T) return T
-function "mod"(Left, Right : T) return T
-function "rem"(Left, Right : T) return T
+The expected type of a reduction expression is any nonlimited type.
 
-Modify 4.5.5(12)
+For a subtype S of a component of an array type A or element of an
+iterable container object C and a corresponding object O of the
+array or iterable container object, which is denoted
+by the prefix of a reduction_expression, and a subtype R where R is the
+expected type of the reduction_expression;
 
-function "*"(Left, Right : T) return T {with Associative}
-function "/"(Left, Right : T) return T
+A /reducer_/subprogram either denotes a function with the following specification:
 
-Modify 4.5.5(14)
+   function Reducer(Accumulator : R; Value : S) return R with Non_Blocking, Global => null;
 
-function "*"(Left : T; Right : Integer) return T {with Associative}
-function "*"(Left : Integer; Right : T) return T {with Associative}
-function "/"(Left : T; Right : Integer) return T
-
-Modify 4.5.5(16-17)
-
-function "*"(Left, Right : root_real) return root_real {with Associative}
-function "/"(Left, Right : root_real) return root_real
-
-function "*"(Left : root_real; Right : root_integer) return root_real {with Associative}
-function "*"(Left : root_integer; Right : root_real) return root_real {with Associative}
-function "/"(Left : root_real; Right : root_integer) return root_real
-
-Modify 4.5.5(19)
-function "*"(Left, Right : universal_fixed) return universal_fixed {with Associative}
-function "/"(Left, Right : universal_fixed) return universal_fixed
-
-Add AARM To Be Honest after 4.5.5(19)
-
-Addition and Multiplication operators for discrete and floating point types are
-not truly associative, even though the differences may not be important for
-typical use. Discrete additions might overflow when different groupings are
-applied, and floating point rounding errors can produce different results when
-different groupings are applied. We say these are associative though, because
-for typical use, the non-associativity is subtle enough to not be a concern.
-
-Add to new section 9.12 (See AI12-0119-1)
-
-[Reader Note: I somewhat modelled the Associative aspect after the nonblocking
- aspect. There may be content that is not needed, but I figure it makes sense to
- start with something that already has pretty good wording, rather than try to
- invent new wording]
-
-[RLB: There's much more wording here than needed, since Associative doesn't
-have any Legality Rules on the contents of the subprogram (it's more of an
-assertion). As such, most the generic rules are unneeded.]
-
-For a noninstance subprogram, predefined operator, generic subprogram, formal
-subprogram, formal object of a named or anonymous access-to-subprogram type
-(including a formal type) the following language-defined operational aspect is
-defined.
-
-AARM Ramification: "Noninstance subprogram" excludes a subprogram that is an
-instance of a generic subprogram. In that case, the aspect should be specified
-on the generic subprogram. If the Associative aspect needs to be added to an
-instance of a generic subprogram, it can be accomplished by creating a separate
-subprogram specification and then completing that specification with a
-renames-as-body of the instance.
-
-Associative
-The type of aspect Associative is Boolean.
-This aspect specifies the associative restriction for the entity;
-
-Aspect Description for Associative: Specifies that a subprogram or operator
-produces an associative result, that is, the operation produces the same
-semantic results when applied to a sequence of values, regardless how the values
-in the sequence are grouped, so long as the order of the sequence is maintained.
-
-Note: For example, addition is associative since (A + B) + C = A + (B + C)
-
-The Associative aspect may be specified for all entities for which it is
-defined. In particular, Associative may be specified for generic formal
-parameters.
-
-Ramification: The Associative aspect cannot be specified for enumeration literals
-but we don't need to mention that above. One would have to declare a subprogram in
-order specify the aspect in that case, but that defines a user-defined subprogram
-which is itself not a an enumeration literal.
-
-The subprogram or operator associated with the aspect shall have two or more
-parameters if the Associative aspect is True.
-
-For a dereference of an access-to-subprogram type, the Associative aspect of the
-designated subprogram is that of the access-to-subprogram type.
-
-[For a full type declaration that has a partial view, the aspect is the same as
-that of the partial view.]
-
-AARM Proof: Type aspects are never view-specific; they always have the same
-value for all views. This is formally stated in 13.1.
-
-For any inherited subprogram, it is asociative if and only if the corresponding
-subprogram of the parent is associative.
+or denotes a procedure with the following specification:
 
-Overridings of dispatching operations do not inherit this aspect.
+   procedure Reducer(Accumulator : in out R; Value : S) with Non_Blocking, Global => null;
 
-Unless directly specified, for a formal type, or formal subprogram,
-the aspect is that of the actual type, or subprogram.
+A /combiner_/subprogram is a /reducer_/subprogram where subtypes S and R
+statically match.
 
-AAARM Reason: This means that Associative legality checking for the actual
-parameters of the instance is only necessary when the aspect is explicitly
-specified for the formal type.
+The reducer_name of a reduction_specification denotes the name of a
+reducer_subprogram.
 
-Unless directly specified, for a derived type the Associative aspect is False.
+The expected type of an initial_value_expression of a reduction_specification
+is of subtype R.
 
-AARM Discussion: The expressions that can be specified for a derived type are
-limited by a Legality Rule, see below.
+The combiner_name of a reduction_specification denotes the name of a
+combiner_subprogram.
 
 Legality Rules
-
-If aspect Associative is specified for an entity that is not a generic unit or
-declared inside of a generic unit, the aspect_definition shall be a static
-expression.
-
- If the prefix of an Associative attribute_reference denotes a generic unit G,
- the reference shall occur within the declarative region of G.
-
-AARM Reason: We want the value of Associative attributes to be static so long as
-they occur outside of any generic unit. The Associative aspect of a generic unit
-will often depend on the actual parameters of the unit, so it cannot be static
-(or have any well-defined value). We need this latter rule in case the attribute
-of a generic is used outside of the generic. Note that the previous rule makes
-it illegal to use such an attribute to specify aspect Associative outside of a
-generic, but we don't want to allow any other uses since it does not have a
-known value until instantiated.
-
-AARM Ramification: This rule does not apply to instances of generic units and
-entities declared within them.
-
-In a generic instantiation (after replacement in the associative expressions by
-values of the actuals as described previously):
-
-the actual subprogram corresponding to an associative formal subprogram shall be
-associative [(an actual that is an entry is not permitted in this case)];
-
-the actual type corresponding to an associative formal access-to-subprogram type
-shall be associative;
-
-the actual object corresponding to a formal object of an associative
-access-to-subprogram type shall be of an associative access-to-subprogram type;
-
-In addition to the places where Legality Rules normally apply (see 12.3), the
-above rules also apply in the private part of an instance of a generic unit.
-
-AARM Ramification: For a generic formal parameter to be associative (thus, for
-these rules to apply), it has to explicitly specify aspect Associative to be
-True. In particular, these rules do not apply when it specifies aspect
-Associative to be an expression involving attribute Associative of a generic
-formal parameter. However, in such a case, these rules do apply in the instance
-of the specification of the generic unit (the normal re-checking is needed). For
-instance, the body of an expression function might make a prohibited call.
-
-A program unit P declared inside of a generic unit but not in a generic body or
-that is a generic specification not declared in a generic unit is considered
-associative for the purposes of checking the restrictions on an associative only
-if the value of its Associative aspect is statically True. For the purposes of
-checks in P, a call to a subprogram is considered associative unless the value
-of its Associative aspect is statically False.
-
-AARM Reason: This is a typical “assume-the-best” rule. We only make checks if we
-know the associative status of both P and the called subprogram. All other
-checks will be performed when the generic unit is instantiated. We used the
-awkward “inside of a generic unit but not in a generic body” so that a generic
-specification declared inside of a generic body uses the following
-“assume-the-worst” rule.
-
-A program unit P declared inside of a generic body or that is a generic body is
-considered associative for the purposes of checking the restrictions on an
-associative unit unless the value of its Associative aspect is statically False.
-For the purposes of checks in P, a call to a subprogram is considered to be
-non-associative unless:
-
-the value of its Associative aspect is statically True, or
-
-its associative expression (that is, Associative aspect) conforms exactly to
-that of P, or conforms to some part of the associative expression of P that is
-combined with the remainder of the associative expression of P by one or more
-and or and then operations.
-
-AARM Ramification: That is, if the aspect of the program unit is specified
-(directly or via inheritance) with any non-static Associative aspects, it is
-considered to be an associative program unit for the purposes of making checks.
-This is a typical “assume-the-worst” rule.
-
-Extensions to Ada 2012
-
-Aspect Associative is new; it allows compile-time checks to assist
-in determining if 'Reduce attribute evaluations can be performed with parallel
-execution.
-
-Modify A.1 (9.1)
-
-   -- function "and" (Left, Right : Boolean'Base) return Boolean'Base {with Associative};
-   -- function "or"  (Left, Right : Boolean'Base) return Boolean'Base {with Associative};
-   -- function "xor" (Left, Right : Boolean'Base) return Boolean'Base {with Associative};
-
-Modify A.1 (17)
-
-   -- function "+"   (Left, Right : Integer'Base) return Integer'Base {with Associative};
-   -- function "-"   (Left, Right : Integer'Base) return Integer'Base;
-   -- function "*"   (Left, Right : Integer'Base) return Integer'Base {with Associtive};
-   -- function "/"   (Left, Right : Integer'Base) return Integer'Base;
-
-Modify A.1 (25)
-
-   -- function "+"   (Left, Right : Float) return Float {with Associative};
-   -- function "-"   (Left, Right : Float) return Float;
-   -- function "*"   (Left, Right : Float) return Float {with Associative};
-   -- function "/"   (Left, Right : Float) return Float;
-
-Modify A.1 (29-34)
 
-function "*" (Left : root_integer; Right : root_real)
-     return root_real {with Associative};
+For a reduction_expression where the attribute_reference is Reduce,
+there shall not be a combiner_name specified.
 
-   function "*" (Left : root_real;    Right : root_integer)
-     return root_real {with Associative};
+For a reduction_expression where the attribute_reference is Parallel_Reduce,
+the combiner_name shall be specified if subtype S and subtype R do not
+statically match.
 
-   function "/" (Left : root_real;    Right : root_integer)
-     return root_real;
-
-   -- The type universal_fixed is predefined.
-   -- The only multiplying operators defined between
-   -- fixed point types are
-
-   function "*" (Left : universal_fixed; Right : universal_fixed)
-     return universal_fixed {with Associative};
-
-   function "/" (Left : universal_fixed; Right : universal_fixed)
-     return universal_fixed;
-
-Modify A.4.4 (13-17)
-
- function Append (Left, Right : in Bounded_String;
-                       Drop        : in Truncation  := Error)
-         return Bounded_String {with Associative};
-
-      function Append (Left  : in Bounded_String;
-                       Right : in String;
-                       Drop  : in Truncation := Error)
-         return Bounded_String  {with Associative};
-
-      function Append (Left  : in String;
-                       Right : in Bounded_String;
-                       Drop  : in Truncation := Error)
-         return Bounded_String {with Associative};
-
-      function Append (Left  : in Bounded_String;
-                       Right : in Character;
-                       Drop  : in Truncation := Error)
-         return Bounded_String {with Associative};
-
-      function Append (Left  : in Character;
-                       Right : in Bounded_String;
-                       Drop  : in Truncation := Error)
-         return Bounded_String {with Associative};
-
-
-Modify A.4.4 (21-26)
-
-      function "&" (Left, Right : in Bounded_String)
-         return Bounded_String {with Associative};
-
-      function "&" (Left : in Bounded_String; Right : in String)
-         return Bounded_String {with Associative};
-
-      function "&" (Left : in String; Right : in Bounded_String)
-         return Bounded_String {with Associative};
-
-      function "&" (Left : in Bounded_String; Right : in Character)
-         return Bounded_String {with Associative};
-
-      function "&" (Left : in Character; Right : in Bounded_String)
-         return Bounded_String {with Associative};
-
-Modify A.4.5 (15-19)
-
-   function "&" (Left, Right : in Unbounded_String)
-      return Unbounded_String {with Associative};
-
-   function "&" (Left : in Unbounded_String; Right : in String)
-      return Unbounded_String {with Associative};
-
-   function "&" (Left : in String; Right : in Unbounded_String)
-      return Unbounded_String {with Associative};
-
-   function "&" (Left : in Unbounded_String; Right : in Character)
-      return Unbounded_String {with Associative};
-
-   function "&" (Left : in Character; Right : in Unbounded_String)
-      return Unbounded_String {with Associative};
-
-Modify A.18.2 (15/2-18/.2)
-
-   function "&" (Left, Right : Vector) return Vector {with Associative};
-
-   function "&" (Left  : Vector;
-                 Right : Element_Type) return Vector {with Associative};
-
-   function "&" (Left  : Element_Type;
-                 Right : Vector) return Vector {with Associative};
-
-   function "&" (Left, Right  : Element_Type) return Vector {with Associative};
-
-Add after A.18.3 (32/2)
-
-   function "&" (Left, Right : List) return List {with Associative};
-
-   function "&" (Left  : List;
-                 Right : Element_Type) return List {with Associative};
-
-   function "&" (Left  : Element_Type;
-                 Right : List) return List {with Associative};
-
-   function "&" (Left, Right  : Element_Type) return List {with Associative};
-
-Modify A.18.7(53/2)
-
-procedure Union (Target : in out Set;
-                 Source : in     Set) {with Associative};
-
-Modify A.18.7(55/2)
-
-    function Union (Left, Right : Set) return Set {with Associative};
-
-Modify A.18.7(57/2)
-
-procedure Intersection (Target : in out Set;
-                        Source : in     Set) {With Associative};
-
-Modify A.18.7(59/2)
-
-function Intersection (Left, Right : Set) return Set {With Associative};
-
-Modify A.18.7(67/2)
-
-    function Symmetric_Difference (Left, Right : Set) return Set {with Associative};
-
-Modify A.18.8(26/2)
-   procedure Union (Target : in out Set;
-                    Source : in     Set) {with Associative};
-
-Modify A.18.8(27/2)
-
-   function Union (Left, Right : Set) return Set { with Associative};
-
-Modify A.18.8(29/2-31/2)
-
-procedure Intersection (Target : in out Set;
-                           Source : in     Set) {with Associative};
+AARM Note
+The combiner_name is always optional for Reduce, because only one
+logical thread of control is presumed so there is no need to provide a
+way to combine multiple results.
+
+Static Semantics
+
+For a reduction_expression where the attribute_reference is Parallel_Reduce,
+if the combiner_name is not specified, then
+the subprogram denoted by the reducer_subprogram also implicitly denotes the
+combiner_subprogram.
+
+Dynamic Semantics
+
+The following attributes are defined for a prefix O that is of an
+array type (after any implicit dereference), or denotes a constrained array subtype,
+or denotes an /iterable container object/:
+
+O'Reduce(Reducer, Initial_Value)
+
+   O'Reduce is a reduction expression that initializes the result of the
+   expression to the Initial_Value, and then uses an array component iterator
+   or a component element iterator to iterate in increasing order
+   through the values associated with the attribute prefix and issues calls
+   to Reducer using the value of the loop parameter or loop cursor as the
+   Value parameter for each iteration, and using the result of the previous
+   iteration as the Accumulator parameter. Yields the final result after
+   the iteration is complete. If the prefix of the attribute reference
+   denotes a null range of values, then yields the Initial_Value.
+
+O'Parallel_Reduce(Reducer, Initial_Value[, Combiner])
+
+   O'Parallel_Reduce is identical to O'Reduce except that O'Parallel_Reduce
+   is a parallel construct where the iterations are divided among multiple
+   logical threads of control. Each logical thread of control
+   generates a local copy of the result of its iteration, which is initialized
+   to the value of the loop parameter or loop cursor associated with the first assigned
+   iteration. The Reducer is called for subsequent iterations when multiple
+   iterations have been assigned to the same logical thread of control.
+   As each logical thread of control completes its assigned
+   iterations, the Combiner is called using the value of the local
+   result as the Value parameter of the call, and using the previous
+   final result value, as the the Accumulator parameter for the call.
+   Once all logical threads of control have completed, yields the result
+   of the last call to Combiner. If the prefix of the attribute reference
+   denotes a null range of values, then yields the Initial_Value.
+   The calls to Combiner are issued sequentially in increasing iteration order.
+   The Combiner may be omitted if the Reducer is also a combiner_subprogram.
+   In that case, the Reducer is implicitly used also as the Combiner
+   argument.
 
-   function Intersection (Left, Right : Set) return Set {with Associative};
+AARM Note
+The prefix can be a (qualified) array or aggregate for an
+/iterable container object/. The prefix can denote an object of a
+multi-dimensional array.
 
+AARM Note:
 
-Modify A.18.8(35/2)
-    function Symmetric_Difference (Left, Right : Set) return Set {with Associative};
+We say the calls to Combiner are sequentially ordered in increasing order
+because certain reductions, such as vector concatentation,
+can be non-commutative operations. In order to return a
+deterministic result for parallel execution that is consistent with
+sequential execution of the 'Reduce attribute, we need to specify an order
+for the iteration in both the 'Reduce and 'Parallel_Reduce cases,
+and for the combination of results from the logical threads of control
+for the 'Paralell_Reduce case.
 
-Modify A.18.9(27/2)
+Examples
 
-   procedure Union (Target : in out Set;
-                    Source : in     Set) {with Associative};
+  Calculate the sum of elements of an array of integers
 
-   function Union (Left, Right : Set) return Set { with Associative};
+  A'Reduce("+",0)  -- See 4.3.3(43)
 
-procedure Intersection (Target : in out Set;
-                           Source : in     Set) {with Associative};
+  Determine if all elements in a two dimensional array of booleans are set to
+  true
 
-   function Intersection (Left, Right : Set) return Set {with Associative};
+  Grid'Reduce("and", true);  -- See 3.6(30)
 
-Modify A.18.9(37/2)
-    function Symmetric_Difference (Left, Right : Set) return Set {with Associative};
+  Calculate the minimum value of an array of integers in parallel
 
+  A'Parallel_Reduce(Integer'Min, Integer'Last)
 
 !discussion
 
 A 'Reduce or 'Parallel_Reduce attribute reference provides a concise way to use
 iteration to combine a set of values into a single result.
-
-We already have some special purpose reduction expressions in Ada in the form of
-quantified expressions and array aggregates of the form using an
-iterated_component_association.
 
-Consider:
-
-   All_Graduated : constant Boolean :=
-     (for all Student of Class => Passed_Exam (Student));
-
-   Someone_Graduated : constant Boolean :=
-     (for some Student of Class => Passed_Exam (Student));
-
-Here we are in both cases effectively reducing a set of Boolean values into a
-single result using quantified expressions.
-
-A similar effect can be written using a more generalized 'Reduce attribute
-expression, in combination with an array aggregate.
-
-   All_Graduated : constant Boolean :=
-     (for Student of Class => Passed_Exam (Student))'Reduce("And", True);
-
-   Someone_Graduated : constant Boolean :=
-     (for Student of Class => Passed_Exam (Student))'Reduce("Or", False);
-
-Here we use "and" and "or" as the combiner_subprogram of the Reduction
-expression. The initial value plays an important role, since the Identity for
-"and" must be true, and false for "or".
-
-We considered whether to allow reductions for combiner_functions where the two
-parameters are not of the same type. For example, one might want to have a
-combiner that appends characters to an array of characters. It was decided that
-this would be left out for now. We could decide to add support for it later, but
-doing so would add a fair bit more complexity. For instance, it would then be
-necessary to define an Identity_Value aspect, because the compiler would not
-know how to initialize local accumulators for different tasklets. We currently
-only allow combiners where both parameters are of the same type. This allows us
-to use the first value associated each tasklet as the initial value, which works
-because the result and inputs are of the same type. If the types were different,
-we'd also need to define a Reducer aspect that names another subprogram that can
-be used to combine results from different tasklets. Such a Reducer subprogram
-would necessarily have the same types for both input parameters. Since we are
-currently restricting combiner_functions to have that form, there is no need to
-define a Reducer aspect.
-
-Such reducers tend to be concatentation reductions, which Ada already has
-concise syntax for, in the form of array aggregate notation, and possibly
-container aggregate as they are currently being proposed. There otherwise seems
-to be little need for such capability.
-
-We also considered whether the initial_value was needed or not. We could
+We considered whether the initial_value was needed or not. We could
 alternatively overload the attribute names to provide versions that do not
 accept a second argument.
 
@@ -846,98 +333,8 @@
 need to be considered. We decided that for now at least, it is better to keep
 the interface simple. If an exception is needed for a null range, there are
 other ways to do that already in the language.
-
-Another concern might be whether parallel loops can generally be written as
-expressions, and still have a similar performance benefit.
-
-Consider the calculation of Pi:
-
-   function Pi (Number_Of_Steps : Natural := 100_000) return Long_Float is
-     (1.0 / Number_Of_Steps *
-        (parallel for I in 1 .. Number_Of_Steps =>
-           (4.0 / (1.0 + ((Long_Float (I) - 0.5) * 1.0 / Number_Of_Steps)**2)))
-             'Reduce("+", 0.0));
-
-One might feel that the readability of this example might be improved if
-temporary variable declarations were to be added for intermediate results.
-For instanced, it might be nice to replace the sub-expression;
-   (1 + ((Long_Float (I) - 0.5) * Step)**2)
-with
-   (1.0 + X**2)
-and
-   1.0 / Number_Of_Steps
-with
-   Step
-
-One ordinarily cannot declare variables in an expression, but one can always
-write a function which can be called from an expression.
-
-We might instead decide to write:
-
-function Pi (Number_Of_Steps : Natural := 100_000) return Long_Float
-is
-   Step : constant Long_Float := 1.0 / Number_Of_Steps;
-
-   function Pi_Slicer (Index : Natural) return Float
-   is
-      X : constant Long_Float := (Long_Float (Index) - 0.5) * Step;
-   begin
-      return 4.0 / (1.0 + X ** 2);
-   end Pi_Slicer;
-
-   Temp : constant Long_Float :=
-      (for I in 1 .. Number_Of_Steps =>
-          Pi_Slicer (I))'Parallel_Reduce("+", 0.0);
-begin
-   return Step * Temp;
-end Pi;
-
-Which leaves a simpler looking Reduction Expression to do computation.
-
-For performance testing, two versions of this code were created using the
-Paraffin libraries, and tested using GNAT on a quadcore Linux machine.
-
-One version of the code has the parallelism code written inline as in the first
-version above, and the second calls a local subprogram idential to the Pi_Slicer
-routine above.
-
-For 10_000_000 steps of iteration, the following results were collected with
-optimization turned off.
-
-Sequential Pi
-Elapsed = 00:00:00.65
-Pi = 3.141592653590E+00
-
-Work Seeking Pi
-Elapsed = 00:00:00.16
-Pi = 3.141592653590E+00
-
-'Parallel_Reduce Pi
-Elapsed = 00:00:00.19
-Pi = 3.141592653590E+00
-
-Both versons of the code produced comparable results compared to the sequential
-version of the code.
-
-After turning on full optimization, and rerunning the same code, the following
-results were collected.
-
-Sequential Pi
-Elapsed = 00:00:00.57
-Pi = 3.141592653590E+00
 
-Work Seeking Pi
-Elapsed = 00:00:00.15
-Pi = 3.141592653590E+00
-
-'Parallel_Reduce Pi
-Elapsed = 00:00:00.14
-Pi = 3.141592653590E+00
-
-In this case, the results were even more comparable, and in fact the better
-time was found with the version of code that had the extra function call.
-
-Another  concern might be about the need to perform multiple reductions at the
+Another concern might be about the need to perform multiple reductions at the
 same time.
 
 Consider:
@@ -8303,5 +7700,38 @@
 provide some basic parallelism capabilities that cover a broad set of the
 parallelism spectrum, and then look at more esoteric (but potentially very
 useful) features or capabilities further down the road.
+
+****************************************************************
+
+From: Brad Moore
+Sent: Saturday, October 13, 2018  3:15 PM
+
+Here is a new version of AI12-0242-1, Reduction Expressions
+
+It is quite a lot more concise than the previous version, and a fair bit has
+changed, but the underlying semantics and syntax are mostly the same.
+
+Some of the highlighted changes are;
+
+   - Parts related to a map/reduce attribute prefix were carved out of this AI
+     as that will now appear in AI12-0262-1.
+   - Most of the wording moved into a new subclause dedicated to reduction
+     expressions, rather than being under the Array Operations clause
+   - The reductions now supports having differing subtypes for the accumulator
+     type, and the values being accumulated.
+   - To support differing subtypes and parallel execution with 'Parallel_Reduce,
+     a third parameter was added, which is called the combiner_subprogram. What
+     was previously called the combiner_subprogram is now called the
+     reducer_subprogram. If the subtypes of both parameters of the
+     reducer_subprogram statically match, then the combiner_subprogram can be
+     left unspecified for 'Parallel_Reduce, which is likely the most common
+     case. The 'Reduce attribute does not allow a combiner_subprogram to be
+     specified, as it is presumed that there will only be one logical thread of
+     control so there is no need to combine results from multiple logical
+     threads of control.
+   - Reduction expressions may be static expressions for the 'Reduce case, if
+     the reducer_subprogram denotes a static function.
+
+[This was followed by version /04 of the AI - Editor.]
 
 *****************************************************************

Questions? Ask the ACAA Technical Agent