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

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

--- ai12s/ai12-0242-1.txt	2018/10/16 00:46:15	1.10
+++ ai12s/ai12-0242-1.txt	2018/10/16 01:08:51	1.11
@@ -1,4 +1,4 @@
-!standard 4.5.9 (0)                                18-10-14    AI12-0242-1/04
+!standard 4.5.9 (0)                                18-10-15    AI12-0242-1/05
 !class Amendment 14-06-20
 !status work item 14-06-20
 !status received 14-06-17
@@ -206,7 +206,8 @@
 by the prefix of a reduction_expression, and a subtype R where R is the
 expected type of the reduction_expression;
 
-A /reducer_/subprogram either denotes a function with the following specification:
+A /reducer_/subprogram either denotes a function with the following
+specification:
 
    function Reducer(Accumulator : R; Value : S) return R with Non_Blocking, Global => null;
 
@@ -319,8 +320,50 @@
 
 !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 considered whether 'Reduce should allow reducer_subprograms without
+the Nonblocking aspect and Global=>null aspect specification, since
+strictly speaking that isn't necessary if the reduction does not execute
+in parallel. We could relax this in the future if it is needed, but typically
+most reducers are short simple functions, and typically will be nonblocking
+without global involving global variables. Since the aspects are needed
+for the reducer subprograms used with 'Parallel_Reduce, it was simpler
+to use the same specification for both attributes.
+
+We similarly considered whether the specification of the combiner_subprogram
+of 'Parallel_Reduce could be relaxed, since the calls to the
+combiner_subprogram need to be called sequentially since they update the
+final global result. However, while the calls to the combiner_subprogram
+need to be sequential with respect to each other, an implication could
+run these calls in parallel with other logical threads of control as
+part of the processing associated with calling the reducer_subprograms.
+This increases the parallelism of the overall processing which may
+provide performance benefits.
+
+For an example on how this can be accomplished while supporting non-commutative
+reduction, see the article Parallel Reduction Lists, in the June 2016 issue
+of the Ada User Journal at http://www.ada-europe.org/auj/archive/. Since
+calling the combiner_subprogram in parallel with other processing
+is a possibility, we need the global=>null and Nonblocking aspects for
+the combiner_subprogram associated with 'Parallel_Reduce to
+ensure this is safe to do without risking data races and deadlocking.
+
+We considered defining an Associative aspect that could be specified on
+subprograms, and then having the compiler check that the reducer_subprogram
+and combiner_subprogram have that aspect specified as True for the
+'Parallel_Reduce. Although it is true that the reducer_subprogram and
+combiner_subprogram need to be associative operations for parallelism
+to be applied, there are a number of problems with this. First of all,
+the compiler cannot verify if a particular call is truly associative,
+so the compiler would have to have faith in the programmer to get this right.
+Secondly, associativity can sometimes be in the eye of the beholder.
+For example, integer addition is normally considered an associative
+operation, but if integer overflow is a possibility, then technically
+the operation is not associative. That might be an important consideration
+for some users, and unimportant to others. Similarly, floating point math
+is not associative, due to the rounding errors that get introduced, but
+for many users, the results are good enough to consider as being associative.
+Thirdly, this added a lot of complexity and wording changes to the AI,
+which was deemed to not be worthwhile.
 
 We considered whether the initial_value was needed or not. We could
 alternatively overload the attribute names to provide versions that do not
@@ -349,8 +392,8 @@
 One might want to calculate these three results iterating only once through the
 array.
 
-This can be accomplished by creating a composite result type, and writing a user
-defined reducer function.
+This can be accomplished by creating a composite result type, and writing a
+user-defined reducer function.
 
    type Summary is
       record
@@ -365,10 +408,11 @@
                                            Max => Integer'First);
 
    -- Reducer function for the Reduction expression
-   function Reduce (L, R : Summary) return Summary with Associative is
-     (Summary'(Sum => L + R,
-               Min => Integer'Min (L, R),
-               Max => Integer'Max (L, R)));
+   function Reduce (L, R : Summary)
+       return Summary with Nonblocking, Globals => null is
+     (Summary'(Sum => L.Sum + R.Sum,
+               Min => Integer'Min (L.Min, R.Min),
+               Max => Integer'Max (L.Max, R.Max)));
 
    -- Reduction expression to compute all 3 results at once
    Result : constant Summary := A'Reduce(Reduce, Identity);
@@ -7733,5 +7777,143 @@
      the reducer_subprogram denotes a static function.
 
 [This was followed by version /04 of the AI - Editor.]
+
+****************************************************************
+
+From: Ed Schonberg
+Sent: Saturday, October 13, 2018  4:12 PM
+
+>  type Summary is
+>     record
+>        Sum : Integer;
+>        Min : Integer;
+>        Max : Integer;
+>     end record;
+>
+>  -- Identity value for the Reduce function
+>  Identity : constant Summary := Summary'(Sum => 0,
+>                                          Min => Integer'Last,
+>                                          Max => Integer'First);
+>
+>  -- Reducer function for the Reduction expression
+>  function Reduce (L, R : Summary) return Summary with Associative is
+>    (Summary'(Sum => L + R,
+>              Min => Integer'Min (L, R),
+>              Max => Integer'Max (L, R)));
+
+Should this be
+
+
+  Summary' (
+      Sum => L.Sum + R.Sum,
+      Min   => Integer'Min (L.Min. R.Min).
+      Max  =>  Integer'Max (L.Max. R.Max))
+
+or am I missing something basic?
+
+****************************************************************
+
+From: Brad Moore
+Sent: Saturday, October 13, 2018  5:00 PM
+
+You are correct. Thanks for catching that.
+
+Also, I should have mentioned that I removed the Associative aspect from this
+AI, as it added a lot of complexity for little value, particularly since the
+compiler could not prove its correctness.
+
+But I had neglected to remove the Associative aspect from this example also.
+
+****************************************************************
+
+From: Brad Moore
+Sent: Sunday, October 14, 2018  11:50 AM
+
+A minor update to the AI.
+
+I corrected the example that Ed pointed out, and added the Nonblocking,
+Global=>null aspect specification to that example.
+
+Also, I added notes in the discussion section about considering whether to relax
+the Nonblocking, Global=>null specification for use with the 'Reduce attribute,
+since that attribute doesn't strictly need these aspects if parallelism is not
+involved.
+
+I also added notes about considering the definition of an Associative aspect. We
+had that in an earlier version of the AI, but that was removed in the previous
+update.
+
+[Following is version /05 of the AI - Editor.]
+
+****************************************************************
+
+From: Randy Brukardt
+Sent: Monday, October 15, 2018  8:07 PM
+
+>    - Reduction expressions may be static expressions for the 'Reduce
+> case, if the reducer_subprogram denotes a static function.
+>
+and in the AI:
+>
+>Add after 4.9(8)
+>
+>"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;"
+
+Umm, this doesn't require the components of the prefix to be static. That seems
+rather fundamental to the definition of a static expression! Also, Ada currently
+doesn't have any static composite types other than strings; I have to wonder the
+wisdom of introducing them by a single special case, rather than some larger
+generalization of static expressions. (Static strings, after all are a hack to
+support interfacing.)
+
+This minutes say "Steve wonders if we would ever want a `Reduce to be static.
+We'll leave that for the AI author.". I think a better answer here would have
+been "no". :-)
+
+----
+
+>Syntax
+>
+>reduction_specification ::= /reducer_/name, /initial_value_/expression[, ...
+>
+>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.
+
+A reduction_specification is not an expression, so the above description is
+nonsense. You need to define this completely if you are going to do any of it
+this way:
+
+Replace 4.1.4(3/2):
+
+attribute_designator ::=
+    identifier[(static_expression)]
+  | identifier(reduction_specification)
+  | Access | Delta | Digits | Mod
+
+[Note: I just made Steve do that same thing with his AI12-0243-1.]
+
+----
+
+>The expected type of a reduction expression is any nonlimited type.
+
+This is fine, but then you say "R" is the expected type of the reduction
+expression -- but you just said that that is any nonlimited type. Can't have it
+both ways in a single set of Name Resolution Rules. Somewhere, "R" needs to be a
+single specific type (or whatever it is restricted to).
+
+-----
+
+In the most recent version of the AI, you have an "Implementation Advice" header
+without any text following it. I left that out.
+
+---
+
+I also added cross-references to other AIs the !proposal and !discussion,
+removed some extra spaces, added missing periods, broke up a couple of overlong
+lines.
 
 *****************************************************************

Questions? Ask the ACAA Technical Agent