To: J3 J3/14-159r3
From: Dan Nagle
Subject: More reduce() (and co_reduce())
Date: 2014 June 24
Reference: 14-007r1, N2007, N1975, 13-392r2
This paper attempts to improve the specification
of the REDUCE work item. The N1975 specification follows:
*** begin 13-329r2 quote
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 shall be specifiable, and if not
specified this result shall be processor dependent.
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; in this, REDUCE will be different from CO_REDUCE. 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.
For users who require evaluation in strict array element order, we could
add an ORDERED=.TRUE. argument with that effect; to be most effective the
actual argument should be required to be constant. However, we do not
think that this case warrants the extra complication (and therefore it is
not part of the specifications).
*** end 13-329r2 quote
This specification does not state that the operations must be applied
in order, only that operands may not be swapped. This requirement does
not appear in the normative text. Indeed, the mapping from operands
to function arguments is not described in the text.
An attempt is made here to address these points.
Specification
-------------
As above, but with the following changes
Specify a default value to be returned when the array is
zero-sized and IDENTITY is absent.
Also add a ORDERED optional argument to specify that the operation
will be applied to the elements of the sequence in order.
The requirement for commutivity is removed when ORDERED is
absent or present with the value FALSE.
The discussion of associativity is moved to a Note, since the use
of non-associative operation functions may result in unforseen
consequences. These consequences may be explained in a Note.
Syntax
------
Add an ORDERED optional argument to REDUCE to specify that
the reduction is to preserve the order of the operands.
Edits
-----
To specify how reduction operations work add a new subclause
to Clause 13, perhaps after 13.2 [320:30+] or after 13.4 [322:16+]
and Note 13.5.
{edits against 14-007r1}
{define terms in Clause 1}
[14:3+] add a term
"1.3.108+
a sequence of data values subject to a reduction"
[15:29+] add some terms
"1.3.122+
a computation producing a data value from a sequence of data values
1.3.122+.1
a reduction where the data values are taken in a specified order
1.3.122+.2
a reduction where the data values are taken
in a processor-dependent order"
{add a new section after 13.2.4 - the location is arguable}
[318:30+] add a section: {this location sets x=2+}
"13.x Reduction Operations
13.x.1 Reduction Operands
A reduction operation applies a binary operation to all elements
of a sequence to produce a single result. The elements of this
sequence are operands and the sequence is the operand sequence.
All elements of the sequence shall have the same type
and type parameters.
13.x.2 Default Values of Reduction Operations
The value of the reduction in the case where the operand sequence has
zero elements may be specified as an optional default value, or if none
is specified it may be the default initialization value of the type and
kind of the operands. If there is no default initialization for the
type and kind of the operands, and if the type is an intrinsic type,
the default value is zero for numeric types, false for logical types,
and zero-length character values for character types. If the type
is a derived type, the above values are applied to the ultimate
components of the derived type.
13.x.4 Reduction Operators
A reduction operation is specified by a function. It is a pure function
taking two arguments of the same type and type parameters
as the elements of the operand sequence and returning a result
of the same type and type parameters.
13.x.4 Types of Reduction Operations
A reduction may be ordered or unordered.
13.x.4.1 Unordered Reductions
The operand sequence is considered to be unordered. The processor
selects two distinct operands of the operand sequence, associates one
chosen operand with the first argument of the operation function
and associates the second chosen operand with the second argument
of the operation function. The function is referenced and these operands
are removed from the operand sequence. The result of the function
reference is returned to the operand sequence as a new operand.
The number of operands in the operand sequence has thus been reduced
by one. When the operand sequence has only one operand, its value is
the result of the reduction.
13.x.4.2 Ordered Reductions
The operand sequence is considered to be ordered. In the case of REDUCE,
the order is the array element order. In the case of CO_REDUCE,
the order is the image index order. Each element is associated
with a unique integer index value in the range 1 through N, where N is
the number of operands, in order. The processor selects two adjacent
operands, with adjacent index values, from the operand sequence.
The chosen operand with the lower index value
is associated with the first argument of the operation function,
and the chosen operand with the higher index value is associated
with the second argument of the operation function. The function is
referenced and these chosen operands are removed from the operand
sequence. The function result is returned to the operand sequence
with an index value of either of the arguments. The number of operands
in the operand sequence has thus been reduced by one. When there is only
one operand remaining, its value is the result of the reduction.
Note 13.
An ordered reduction preserves the order of it operands,
and so is useful when the operation is not commutative.
An example of a useful non-commutative operation is a matrix
multiplication.
Note 13.+1
Some useful operations are mathematically associative
but not computationally associative. Some useful operations are
computationally associative but not mathematically associative.
Some useful operations are neither mathematically associative nor
computationally associative. The operation of a reduction
need not be associative. Therefore, the applications
programmer is cautioned that results may not be reproducible
unless care is taken when defining the function that provides
the operation. Non-associative operations are allowed because
some are useful, at the expense of allowing possibly non-reproducible
computations. Different compilers, different optimization options
of the same compiler, different revisions of the same compiler,
and different hardware may produce different values
if the chosen operation is not associative."
{update the reduce entry in Table 13.1}
[324:(about half way down the page)]
replace the REDUCE arguments with
"(ARRAY, OPERATION, DIM [, MASK, IDENTITY, ORDERED])" or
(ARRAY, OPERATION [, MASK, IDENTITY, ORDERED])"
{update the entries for reduce arguments in 13.7.140}
[383:34] replace "IDENTITY" by "IDENTITY, ORDERED" twice
[383:38] after "of any type." add a sentence
"The operand sequence consists of the elements of the array,
taken in array element order."
[384:1-4] replace the current OPERATION specification with
"OPERATION shall be a function meeting the requirements
of 13.x.4 Reduction Operators"
{describe the ORDERED argument}
[384:7+] add
ORDERED (optional) shall be a scalar logical constant. If present
with the value TRUE, the reduction is specified
to be an ordered reduction. Otherwise,
the reduction is unordered.
{update case-i}
[384:12-17] replace the current text with
"Case (i): The result of REDUCE( ARRAY, OPERATION [, IDENTITY =
IDENTITY, ORDERED = ORDERED] is the result
of a reduction operation where the operand sequence
consists of the elements of the array and the operation is
specified by the OPERATION function. If ORDERED is
present with the value TRUE, it is an ordered reduction
(13.x.4.2). Otherwise, it is an unordered reduction
(13.x.4.1). If present, IDENTITY provides the default value
when there are no elements in the operand sequence as
specified by (13.x.2)."
{update case-ii}
[384:18] replace "[, IDENTITY = IDENTITY]" with
"[, IDENTITY = IDENTITY, ORDERED = ORDERED]"
[384:19] replace "initial sequence is" with
"operand sequence consists of"
{update case-iii}
[384:21-25] replace "IDENTITY = IDENTITY" with
"IDENTITY = IDENTITY, ORDERED = ORDERED" four times
{remark upon the processor dependencies introduced by all this}
[483:10+] add a bullet item in the list:
"the order operands are selected from the operand sequence
and are associated with arguments of the operation function
when computing an unordered reduction"