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

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

--- ai12s/ai12-0262-1.txt	2018/03/02 06:20:05	1.1
+++ ai12s/ai12-0262-1.txt	2018/10/17 23:46:42	1.2
@@ -1,4 +1,4 @@
-!standard 5.5.2(2/3)                                  18-03-01  AI12-0262-1/01
+!standard 5.5.2(2/3)                                  18-10-16  AI12-0262-1/02
 !standard 5.5.2(5/4)
 !standard 5.5.2(7/3)
 !class Amendment 18-03-01
@@ -9,13 +9,22 @@
 !subject Map/Reduce attribute
 !summary
 
-** TBD.
+The capabilities of Reduction Expressions are expanded to allow the
+programmer to stream values into the reduction by writing the prefix of
+the reduction attribute as an iterated_element_association or
+iterated_component_association.
 
 !problem
 
+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. This proposal also depend on parallel iteration support for
+containers (AI12-0266-1), and reduction expressions (AI12-0242-1)
+
 AI12-0242-1 defines a reduction operation for existing objects. However,
 in cases where there is no existing type that matches the objects to reduce,
-this is less than convinient. Moreover, if the stream of objects to reduce
+this is less than convenient. Moreover, if the stream of objects to reduce
 is indefinite, it isn't possible in Ada to declare an array type that matches
 it. One could instantiate an indefinite container, but that would have to be
 materialized (since it is made up of calls to user-defined operations).
@@ -24,68 +33,166 @@
 declaring a type and without forcing the materialization of an object.
 
 !proposal
-
-[Author's note: I've just gathered a bunch of notes from public and private
-e-mail discussion. These aren't complete.
-
-One thing that is clear from discussions is that this "version" of the
-Reduction attribute needs a separate description, as the name resolution,
-legality rules, and dynamic semantics all have differences. Therefore, it
-makes sense to put this into a separate AI, one that does depend on some
-of the concepts defined in AI12-0242-1.]
-
-Syntax
-
-   (iterated_element_association)'Attribute_Designator (name, expression)
-
-[Notes: "iterated_element_association" comes from AI12-0212-1. We're only
-using the syntax here; the rest of the rules needs to be defined with this
-AI. As a practical matter, the prefix would have to be parsed as if it is
-an aggregate, and then checked that it has this form. (That's pretty common
-for Ada constructs -- "name" often has to be parsed as "expression", for
-instance.]
-
-The attribute designators are Reduce/Parallel_Reduce (or possibly
-Reduction/Parallel_Reduction). [Should be the same as AI12-0242-1's choice.]
-
-Name Resolution Rules
-
-Expand the syntax above into it's parts, since we are concerned about doing 
-overload resolution on the parts of the iterator:
 
- (for iterator => element_expr)'Reduction(combiner, initial-value)
+The proposal is to allow an iterated_component_association or an
+iterated_element_association as the prefix of a reduction expression
+attribute reference. The basic idea is that as during the evaluation
+of the prefix, as each value is produced during evaluation of the prefix,
+it is reduced into the result value. Thus there is no need to create
+storage to hold all the values prior to the reduction.
+If the parallel keyword is present in the prefix, then the
+reduction expression is a parallel construct and the iteration is
+divided among multiple logical threads of control as appropriate for
+array or container iteration depending on whether the prefix is an
+iterated_component_association (for arrays) or a iterated_element_association
+(for containers). In the parent AI, AI12-0242-1, two attributes are needed
+because there is otherwise no way for the programmer to explicitly specify
+whether parallelism should be applied for an array or container object.
+For this AI, the parallel keyword is allowed in the prefix, so only one
+attribute is needed. Reduce is chosen as the name of the attribute designator.
+
+To be more consistent with the Reduce attribute for an attribute prefix
+of an array object or container iterator object, we relax the rules to
+allow a combiner subprogram to be specified. For an array object or container
+iterator object prefix, the combiner_subprogram is not expected to be called,
+since only one logical thread of control is presumed. It does make it easier
+for the programmer to switch back and forth between sequential and parallel
+execution by simply removing or adding the parallel keyword if the prefix
+is an iterated_component_association or iterated_element_association.
+Similarly, for an array object or iterated container object, one merely
+needs to change the name of the attribute designator to select parallel or
+sequential execution.
 
-A 'Reduction attribute reference is required to have a single expected type.
-That then provides the expected type for the initial-value.  We require the
-first operand of the combiner (and the result if any) to have the type of
-the initial-value. The second operand of the combiner has to have the type
-of the element_expr.
-
-For a combiner function, this makes the resolution problem look like:
+!wording
 
-  X : expected_type := combiner(expected-type'(initial-value), element_expr);
+Modify 4.5.9 (1)
 
-...which is a pretty standard resolution problem. The iterator has to be
-resolved without any context, of course (that's the usual case for iterators).
+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 the values assigned to loop parameters during the evaluation of an
+iterated_component_association (see 4.3.3) or iterated_element_association
+(see 4.3.5)}.
+
+Modify 4.5.9 (?)
+
+[For a reduction_expression where the attribute_reference is Reduce,
+there shall not be a combiner_name specified]
+For a reduction_expression where the attribute_reference is Reduce,
+the combiner_name shall be specified if subtype S and subtype R do not
+statically match and the prefix of the attribute is an
+iterated_component_association or iterated_element_association with the
+parallel keyword.
+
+Modify 4.5.9 (?)
+
+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. {The prefix of the attribute shall denote either an
+object of an array type or an /iterated container object/.}
+
+Modify 4.5.9 (?)
+
+AARM Note
+
+The combiner_name is [always] optional for Reduce {if the attribute prefix
+does not have the parallel keyword}, because only one logical thread of
+control is presumed so there is no need to provide a way to combine multiple results.
 
 Static Semantics
+
+Modify 4.5.9 (?)
 
-Likely similar to the object version, but the elements come from a different
-place (logically).
+For a reduction_expression where the attribute_reference is Parallel_Reduce,
+{or if the attribute_reference is Reduce and the attribute prefix has the
+parallel keyword, }
+if the combiner_name is not specified[,] then the subprogram denoted by
+the reducer_subprogram also implicitly denotes the combiner_subprogram.
 
 Dynamic Semantics
 
-We need to describe the operation of the operation directly in terms of the
-iterator and interleaved invocations of the combiner. (And of course with
-parallelism possibilities.) (The object'Reduction version uses the iterator
-of the object for this task.)
+Add after 4.5.9 (?)
 
-!wording
+The following attributes are defined for a prefix I that is of an
+iterated_component_association or iterated_element_association
+
+I'Reduce(Reducer, Initial_Value[, Combiner])
 
-** TBD.
+   I'Reduce is a reduction expression that initializes the result of the
+   expression to the Initial_Value, and then evaluates the prefix of the
+   attribute. If the prefix does not have the parallel keyword, then
+   as each value of the prefix is produced, a call is made to the Reducer
+   passing the value as the second (Value) parameter to the call, and using
+   the result of the previous iteration as the first (Accumulator) parameter.
+   Yields the final result of the iteration.
+
+   If the prefix of the attribute does have the parallel key word, then
+   the reduction expression is a parallel construct and 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. As each value of the
+   prefix is produced, a call is made to the Reducer passing the value
+   as the second (Value) parameter to the call, and using the result of the
+   previous iteration as the first (Accumulator) parameter. As each logical thread
+   of control completes its assigned iterations, the Combiner is called
+   using the value of the local result as the second (Value) parameter of
+   the call,  and using the previous final result value, as the the first
+   (Accumulator) parameter for the call. Once all logical threads of control have
+   completed, yields the result of the last call to Combiner. 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.
+
+   I'Reduce yields the Initial_Value if the prefix of the attribute reference
+   denotes a null range of values.
+
+Add to 4.5.9 examples
+
+Examples
+
+  Determine how many integers in an array are prime numbers
+
+  Prime_Count : constant 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));
 
 !discussion
 
+This AI doesn't get into too much detail about how the presence of the parallel
+keyword in an iterated_component_association or an iterated_element_association
+maps to generating the parallelism. We already define this for arrays and
+iterated container objects, so it seems unnecessary to repeat that detail here.
+It also doesn't add the parallel keyword to the iterated_component_association
+or iterated_element_association syntax. It seems more appropriate that that
+should be done in AI12-0212-1 (Container aggregates; generalized array
+aggregates). Presumably there would be a benefit for adding parallelism for such
+aggregates as well.
+
 It's mildly annoying that qualifying the prefix changes the resolution a lot
 (as that turns the attribute into the object version (as in AI12-0242-1)).
 
@@ -114,6 +221,34 @@
 in general thinking of them as two views of the same construct will be fine
 for anyone but Ada lawyers.
 
+We already have some special purpose expressions in Ada in the form of
+quantified expressions and array aggregates of the form using an
+iterated_component_association, that are effectively a form of reduction.
+
+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".
+
 !ASIS
 
 ** Unknown.
@@ -126,5 +261,62 @@
 
 !appendix
 
+From: Brad Moore
+Sent: Tuesday, October 16, 2018  11:45 PM
+
+Here is my first attempt at this AI, which expands the 'Reduce attribute defined
+in AI12-0242-1 to allow the prefix to be an iterated_component_association or an
+iterated_element_association. [This is version /02 of this AI - Editor.]
+
+I chose to overload 'Reduce as the name of the attribute associated with this
+AI.
+
+'Reduce is used whether the parallel keyword is present in the prefix or not.
+
+I didn't add the parallel keyword to syntax of these associations in this AI. I
+presumed that that already existed in AI12-0212-1.
+
+My thought was that it was more appropriate to do that in AI12-0212-1 where
+iterated_component_association and iterated_element_association is defined. I
+think there may be similar benefits to adding parallelism to aggregates.
+
 ****************************************************************
 
+From: Randy Brukardt
+Sent: Wednesday, October 17, 2018   6:45 PM
+
+>The following attributes are defined for a prefix I that is of an
+>iterated_component_association or iterated_element_association
+>
+>I'Reduce(Reducer, Initial_Value[, Combiner])
+
+Several issues here:
+
+(1) There's only one attribute defined here, so use singular.
+(2) There's no parens or brackets surrounding the
+    iterated_component_association, they have to be given here.
+(3) An iterated_component_association is not syntactally a prefix, so you can't
+    talk about a prefix.
+
+The net effect is that you need new syntax for this construct, either here or in
+4.1.4. My original version had that part:
+
+Syntax
+
+reduction_expression ::=
+   (iterated_element_association)'Reduce(Reducer, Initial_Value[, Combiner])
+
+Although this obviously doesn't support the other options (square brackets,
+iterated_component_associations).
+
+You then have to have quite a bit of wording for the resolution of these
+expressions (they DO NOT resolve like attributes or like parts of aggregates,
+either -- all of that has to be done explicitly here). In particular, the
+determination of S is much harder than it is with the regular attribute form,
+where the prefix is resolved without context and has to resolve to an existing
+type. Here S comes from the iterator, which has to be resolved first, and by
+itself (without the context usually available when resolving in an aggregate).
+There was some discussion on this point in my old AI draft, and some more in the
+public e-mail (there was also a lot in private e-mail).
+
+****************************************************************

Questions? Ask the ACAA Technical Agent