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

--- ai12s/ai12-0348-1.txt	2020/01/18 05:06:35	1.3
+++ ai12s/ai12-0348-1.txt	2020/01/29 02:54:25	1.4
@@ -1,4 +1,4 @@
-!standard 4.5.10(0)                                  20-01-16  AI12-0348-1/02
+!standard 4.5.10(0)                                  20-01-28  AI12-0348-1/03
 !class Amendment 20-01-08
 !status Amendment 1-2012 20-01-15
 !status ARG Approved 9-0-4  20-01-15
@@ -199,15 +199,16 @@
 
 @s8<@i<Bounded (Run-Time) Errors>>
 
-For a parallel reduction expression, it is a bounded error if the initial 
-value is not the (left) identity of the reducer subprogram. That is, the result
-of calling the reducer subprogram with the Accumulator being the initial
-value and the Value being any arbitrary value of subtype @i<Accum_Type> should
-produce a result equal to the Value parameter. The possible consequences
-are Program_Error, or a result that does not match the equivalent
-sequential reduction expression due to multiple uses of the
-non-identity initial value in the overall reduction.
-  
+For a parallel reduction expression, it is a bounded error if the reducer 
+subprogram is not associative. That is, for any arbitrary values of subtype 
+@i<Value_Type> @i<A>, @i<B>, @i<C> and a reducer function @i<R>, the result of 
+@i<R> (@i<A>, @i<R> (@i<B>, @i<C>)) should produce a result equal to 
+@i<R> (@i<R> (@i<A>, @i<B>), @i<C>)). The possible consequences 
+are Program_Error, or a result that does not match the equivalent sequential 
+reduction expression due to the order of calls on the reducer subprogram being 
+unspecified in the overall reduction. Analogous rules apply in the case of a 
+reduction procedure.
+
 @s8<@i<Examples>>
 
 An expression function that returns its result as a Reduction Expression:
@@ -278,6 +279,39 @@
 parallel execution (see AI12-0349-1), so combiners are almost completely
 redundant and we can eliminate them without losing significant functionality.
 
+---
+
+Once all of the rules specific to combiners are removed, it became apparent
+that there was no rule requiring an associative reducer subprogram for 
+parallel reduction. That is necessary in order to get a consistent and
+portable result from a reduction, as the actual number of chunks used and
+the split of elements/components are both unspecified. (The maximum number 
+of chunks can be specified, but the implementation doesn't have to use that 
+number. There are restrictions on allowed splits, but not enough to determine
+the number of elements in each chunk.)
+
+We do that with a Bounded Error similar to the original error.
+
+For example, the following reduction is well-defined:
+
+      Str : String := ...
+      type Hash_Type is mod <some-prime-number>;
+
+      function Hash (Accum, Value : in Hash_Type) return Hash_Type is
+          (2*Accum + Value);
+
+      ... := [for I in Str'range => Character'Pos(Str(I))]'Reduce (Hash, 0);
+
+The reduction here creates a hash value for Str. But the similar parallel
+reduction triggers the Bounded Error:
+
+      ... := [parallel for I in Str'range => Character'Pos(Str(I))]'Reduce (Hash, 0);
+
+This makes the result (ahem) hash, since Hash is not associative:
+ 
+     Hash (A, Hash (B, C)) = 2*A + 2*B + C -- Unintended result!
+     Hash (Hash (A, B), C) = 4*A + 2*B + C -- Intended result.
+
 !ASIS
 
 Whatever is needed is covered by the original AIs; if anything, a combiner
@@ -813,5 +847,103 @@
 That seems fine.  So we get rid of the "combiner" parameter and all mention 
 of it, and in the presence of "parallel" we require the types of the 
 parameters of the "reducer" be the same.
+
+****************************************************************
+
+From: Randy Brukardt
+Sent: Tuesday, January 28, 2020  8:41 PM
+
+In updating the AARM notes for this AI, I discovered that the revised Bounded 
+Error in the AI has no relationship to any remaining semantics. Thus it could 
+be dropped.
+
+However, that made it clear that there was no mention of the fact that a 
+non-associative reducer in a parallel reduction generates unspecified results. 
+(I had thought that the existing Bounded Error covered that case, but it 
+obviously did not.)
+
+After discussion with Steve and Tucker, we agreed that we still need a Bounded 
+Error for a non-associative reducer. We then crafted the following text:
+
+For a parallel reduction expression, it is a bounded error if the reducer 
+subprogram is not associative. That is, for any arbitrary values of subtype 
+Value_Type A, B, C and a reducer function R, the result of R (A, R (B, C)) 
+should produce a result equal to R (R (A, B), C)). The possible consequences 
+are Program_Error, or a result that does not match the equivalent sequential 
+reduction expression due to the order of calls on the reducer subprogram being 
+unspecified in the overall reduction. Analogous rules apply in the case of a 
+reduction procedure.
+
+AARM Reason: In a sequential reduction expression, the reducer subprogram is 
+called in a left-to-right order, whereas in a parallel reduction expression, 
+the reducer subprogram is called in an order that depends on the number of 
+logical threads of control that execute the reduction. If the reducer is 
+associative, this order does not matter, but in other cases, very different 
+results are possible. While one can specify the maximum number of chunks, the 
+actual number of chunks is unspecified. Thus, to get a consistent and portable
+result, an associative reducer is required. We define this as a Bounded 
+(Run-Time) Errors to provide a stern warning about the required nature of the 
+reducer subprogram and to let compilers detect the problem when possible. 
+
+AARM To be honest: In this rule, “equal” means semantically equal. We don't 
+care if the bit patterns differ but that the results mean the same thing. In 
+particular, if the primitive equal is user-defined, that equality would be the
+one used to determine if this rule is violated. 
+
+[Randy's note: This last AARM note is carried over from the previous Bounded 
+Error, it still seems relevant.]
+
+I also added the following to the !discussion of the AI:
+
+Once all of the rules specific to combiners are removed, it became apparent 
+that there was no rule requiring an associative reducer subprogram for 
+parallel reduction. That is necessary in order to get a consistent and 
+portable result from a reduction, as the actual number of chunks used and the 
+split of elements/components are both unspecified. (The maximum number of 
+chunks can be specified, but the implementation doesn't have to use that 
+number. There are restrictions on allowed splits, but not enough to determine 
+the number of elements in each chunk.)
+
+We do that with a Bounded Error similar to the original error.
+
+For example, the following reduction is well-defined:
+
+      Str : String := ...
+      type Hash_Type is mod <some-prime-number>;
+
+      function Hash (Accum, Value : in Hash_Type) return Hash_Type is
+          (2*Accum + Value);
+
+      ... := [for I in Str'range => Character'Pos(Str(I))]'Reduce (Hash, 0);
+
+The reduction here creates a hash value for Str. But the similar parallel 
+reduction triggers the Bounded Error:
+
+      ... := [parallel for I in Str'range => Character'Pos(Str(I))]'Reduce (Hash, 0);
+
+This makes the result (ahem) hash, since Hash is not associative:
+ 
+     Hash (A, Hash (B, C)) = 2*A + 2*B + C -- Unintended result!
+     Hash (Hash (A, B), C) = 4*A + 2*B + C -- Intended result.
+
+------------------
+
+We're considering this as part of the editorial review of the AI. Since this 
+is unrelated to the purpose of this AI (it's fixing a bug in the underlying 
+AIs), if anyone wants to discuss it properly, we would make it into a separate 
+AI for discussion.
+
+It should be noted that we considered just using a user Note for this purpose. 
+The Dynamic Semantics defines the order of calls on Reduce (and that it is 
+different than the sequential case), so we could just note that the result 
+depends on two properties that are mostly unspecified if the Reducer is 
+non-associative.
+
+Tucker and Steve both felt this was a new case unlike existing order 
+dependencies and that it therefore needs greater visibility than just a 
+user note.
+
+Again, if anyone wants a full discussion on this point, please speak up. (And 
+feel free to wack me with any typos I managed to add to the above.)
 
 ****************************************************************