J3/14-211 To: J3 From: Malcolm Cohen Subject: REDUCE Date: 2014 June 26 1. Introduction The current definition of REDUCE is unclear and needs improvement. Furthermore, in light of discussion some changes to the specifications and syntax are warranted. 2. Deficiencies of the current definition That the initial order of the sequence is intended to be "array element order" is implied but not specified. That the application of the function (to adjacent elements of the sequence) should be with the argument order being the same as the sequence order is implied "OPERATION(x,y) for adjacent x and y in the sequence" but not rigorously specified. It might be thought useful to explain the consequences of a non-associative operation in slightly more detail than a simple recommendation. We could add something to Annex A, but since this already has the enormous catchall - the values returned by some intrinsic functions (13); and indeed hardly any processor-dependent functions are individually listed, that would appear to be unnecessary. 3. Discussion of ORDERED It has been proposed that there be an ORDERED argument that specifies that the operation "be applied to the elements of the sequence in order". Taken at face value, this would prohibit application of the associative law, i.e. for 4 elements a1 to a4 would require computation of ((a1 op a2) op a3) op a4) and not permit (a1 op a2) op (a3 op a4) However, the proposal states "The requirement for commutativity is removed when ORDERED is absent or present with the value FALSE." This is puzzling since there is no requirement for commutativity in the current REDUCE specification/syntax/text. Perhaps the intended meaning was that the requirement that *the processor* not "commute" the arguments be lifted. This provides little benefit since computing a3 op a4 is not more onerous than computing a4 op a3. Yes, there can potentially be some small benefit in a parallel execution environment [such as OpenMP] in the case where the cost of computing the operation is highly variable, but since enabling that involves higher overheads this only applies to a tiny minority of cases; this does not justify the extra complication to the standard. Furthermore, in discussion it was denied that ORDERED=.TRUE. was intended to prohibit re-associating the operations. If that is indeed the case, it would imply that ORDERED would be a spectacularly poor choice of keyword. To sum up: there are three cases (1) strict in-order evaluation: in this case the REDUCE intrinsic cannot run any faster than a trivial user function; the only benefit is that of clarity/convenience: no need to write a simple function. (2) evaluation applying the associative law; that is, re-associating the operand sequence is permitted. This is the model envisaged by the current text. It gains nearly all of the possible performance benefits. The operation "should" be associative otherwise the result will be indeterminate in some way. (3) evaluation applying both the associative and commutative laws: that is, both re-associating and argument swapping are permitted. This has little if any performance benefit over case (2). The operation "should" be both commutative and associative for this to work. It is clear that the default should be case (2), as this provides the maximum benefit for a very reasonable requirement: that the operation "should" be mathematically associative - in practice, what this means is that any non-associativity should be unimportant to the user. If the convenience factor of allowing case (1) is wanted, then indeed an ORDERED argument would be in order. There really does appear to be little point to case (3), which is unsafe for a default and unlikely to give any significant benefit. It could easily enough be provided by a compiler option such as "-Ounsafe" for the few people who might want to do it. If we really do want to add this mode, a separate COMMUTE argument (COMMUTE=.TRUE. to permit argument swapping) would be in order. Potential straw votes: sv Add ORDERED= argument for strict evaluation. Default ORDERED=.FALSE.. sv Add COMMUTE= argument for (3) above. Default COMMUTE=.FALSE.. 3. Revised Specifications (Changes marked with **) (Optional changes marked with ??) Add an intrinsic function that reduces an array by a user-defined operation. Similarly to the other reduction intrinsic functions, (a) reduction of a single dimension shall be provided, and (b) use of a logical mask array shall be supported. The array to be reduced may be of any intrinsic or derived type. The result for reduction of a single element shall be that element. The result for reduction of zero elements (the "identity" for the operation) shall be specifiable. ** Reduction of a zero-sized array with no identify specification shall ** cause error termination. The user-defined operation should be mathematically associative but need not be computationally associative. In order to facilitate reduction of arrays of such things as quaternions and matrices, commutativity will not be required. When more than two elements are being reduced, the operation may be associatively applied to elements and intermediate results in any order that does not commute (swap) operands. ?? It shall be possible to request strict in-order evaluation. ?? It shall be possible to permit argument swapping. 4. Syntax Same as before. ?? Optional ORDERED argument, default .FALSE., ?? for strict in-order evaluation. ?? Optional COMMUTE argument, default .FALSE., ?? for go-faster stripes. ??? If both ORDERED and COMMUTE, ORDERED before COMMUTE. 5. Edits to 14-007r1 [384:13] 13.7.140 REDUCE, p5 Result Value, Case (i), After "is the result of an iterative process." Insert "The initial order of the sequence is array element order." {Specify initial sequence precisely.} [384:14-15] Ditto, After "for adjacent x and y in the sequence," Insert "with x immediately preceding y,". {Specify the obvious.} [384:17] Ditto, Change "and is processor dependent otherwise" To "and otherwise, error termination is initiated". {Specify error termination on missing IDENTITY and zero-sized array.} [384:33+] 13.7.140 REDUCE, after p6 Examples, insert note "NOTE 13.nn If OPERATION is not computationally associative, REDUCE with the same argument values might not always produce the same result, as the processor can apply the associative law to the evaluation." 6. Additional edits to 14-007r1 for ORDERED argument [383:34] 13.7.140 REDUCE, heading, replace "IDENTITY" by "IDENTITY, ORDERED" twice. [384:15] Ditto, p5 Result Value, Case (i), After "x and y with r" insert "; if ORDERED is present with the value true, x and y shall be the first two elements of the sequence". {Strict left-to-right evaluation for ORDERED=.TRUE..} [384:33+] 13.7.140 REDUCE, after p6 Examples, insert note "NOTE 13.nn If OPERATION is not computationally associative, REDUCE without ORDERED=.TRUE. with the same argument values might not always produce the same result, as the processor can apply the associative law to the evaluation." {Replaces the edit in section 5.} 7. Additional edits to 14-007r1 for COMMUTE argument Left to an exercise to the reader. ===END===