4.5.10 Reduction Expressions
{
AI12-0242-1}
{
AI12-0262-1}
Reduction expressions
provide a way to map or transform a collection of values into a new set
of values, and then summarize the values produced by applying an operation
to reduce the set to a single value result. A reduction expression is
represented as an attribute_reference
of the reduction attributes Reduce or Parallel_Reduce.Term entry: reduction
expression — expression that defines how to map or transform
a collection of values into a new set of values, and then summarize the
values by applying an operation to reduce the set to a single value
Syntax
Reason: The intent
is that the syntax matches as closely as possible array or container
aggregate notation. Syntax that matches a loop_parameter_specification
with the reverse reserved word would not be permitted in an array
aggregate, so we disallow that here.
Name Resolution Rules
Discussion: Accum_Type
represents the result of the reduction (the accumulator type),
and Value_Type represents the type of the input values to the
reduction.
{
AI12-0262-1}
A reducer subprogram
is subtype conformant with one of the following specifications: function Reducer(Accumulator : Accum_Type;
Value : Value_Type) return Accum_Type;
procedure Reducer(Accumulator : in out Accum_Type;
Value : in Value_Type);
Legality Rules
Static Semantics
Dynamic Semantics
{
AI12-0262-1}
If the value_sequence
does not have the reserved word parallel, it is produced as a
single sequence of values by a single logical thread of control. If the
reserved word parallel is present in the value_sequence,
the enclosing reduction_attribute_reference
is a parallel construct, and the sequence of values is generated by a
parallel iteration (as defined in 5.5, 5.5.1,
and 5.5.2), as a set of non-empty, non-overlapping
contiguous chunks (subsequences) with one
logical thread of control (see Clause 9) associated
with each subsequence. If there is a chunk_specification,
it determines the maximum number of chunks, as defined in 5.5;
otherwise the maximum number of chunks is implementation defined.Implementation defined:
The maximum number of chunks for a parallel
reduction expression without a chunk_specification.
V'Reduce(Reducer,
Initial_Value)
{
AI12-0262-1}
{
AI12-0348-1}
This attribute represents
a reduction expression, and is in the form of a reduction_attribute_reference.
{
AI12-0262-1}
{
AI12-0348-1}
The evaluation of a use of
this attribute begins by evaluating the parts of the reduction_attribute_designator
(the reducer_name
Reducer and the initial_value_expression
Initial_Value), in an arbitrary order. It then initializes
the accumulator of the reduction expression to the value of the
initial_value_expression
(the initial value).
The value_sequence
V is then evaluated.{
AI12-0262-1}
{
AI12-0348-1}
If the value_sequence
does not have the reserved word parallel, each value of the value_sequence
is passed, in order, as the second (Value) parameter to a call on Reducer,
with the first (Accumulator) parameter being the prior value of the accumulator,
saving the result as the new value of the accumulator. The reduction
expression yields the final value of the accumulator.{
AI12-0262-1}
If the reserved word parallel is present
in a value_sequence,
then the (parallel) reduction expression is a parallel construct and
the sequence has been partitioned into one or more subsequences (see
above) each with its own separate logical thread of control.{
AI12-0262-1}
{
AI12-0348-1}
Each logical thread of control creates a local
accumulator for processing its subsequence. The accumulator for a subsequence
is initialized to the first value of the subsequence, and calls on Reducer
start with the second value of the subsequence (if any). The result for
the subsequence is the final value of its local accumulator.{
AI12-0262-1}
{
AI12-0348-1}
After all logical threads of control of a parallel
reduction expression have completed, Reducer is called for each subsequence,
in the original sequence order, passing the local accumulator for that
subsequence as the second (Value) parameter, and the overall accumulator
[(initialized above to the initial value)] as the first (Accumulator)
parameter, with the result saved back in the overall accumulator. The
parallel reduction expression yields the final value of the overall accumulator.{
AI12-0262-1}
If the evaluation of the value_sequence
yields an empty sequence of values, the reduction expression yields the
initial value.{
AI12-0262-1}
{
AI12-0348-1}
If an exception is propagated by one of the calls
on Reducer, that exception is propagated from the reduction expression.
If different exceptions are propagated in different logical threads of
control, one is chosen arbitrarily to be propagated from the reduction
expression as a whole.Implementation Note:
{
AI12-0262-1}
For a reduction_attribute_reference
that has a value_sequence
without the reserved word parallel or a prefix
where the identifier
of the reduction_attribute_designator
is Reduce (see below), generally the compiler can still choose to execute
the reduction in parallel, presuming doing so would not change the results.
However sequential execution is necessary if the subtypes of the parameters
of Reducer do not statically match, since there is no subprogram identified
in the construct that could be used for combining the results in parallel.
Discussion: {
AI12-0262-1}
We say the calls to Reducer that combine the results
of parallel execution are sequentially ordered in increasing order because
certain reductions, such as vector concatenation, can be non-commutative
(but still associative) operations. In order to return a deterministic
result for parallel execution that is consistent with sequential execution,
we need to specify an order for the iteration, and for the combination
of results from the logical threads of control. It is also necessary
that combining calls to Reducer are issued sequentially with respect
to each other, which may require extra synchronization if the calls to
Reducer are being executed by different logical threads of control.
{
AI12-0242-1}
For a prefix
X of an array type[ (after any implicit dereference)], or that denotes
an iterable container object (see 5.5.1),
the following attributes are defined:X'Reduce(Reducer,
Initial_Value)
{
AI12-0242-1}
{
AI12-0348-1}
X'Reduce is a reduction
expression that yields a result equivalent to replacing the prefix
of the attribute with the value_sequence:
[for Item of X => Item]
X'Parallel_Reduce(Reducer,
Initial_Value)
{
AI12-0242-1}
{
AI12-0348-1}
X'Parallel_Reduce
is a reduction expression that yields a result equivalent to replacing
the attribute identifier
with Reduce and the prefix
of the attribute with the value_sequence:
[parallel for Item of X => Item]
Bounded (Run-Time) Errors
{
AI12-0262-1}
{
AI12-0348-1}
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)); it is a bounded error if
R does not. 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.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 and on the elements/components given
to each chunk. 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. Similarly, the split of elements has only weak requirements.
Thus, to get a consistent and portable result, an associative reducer
is required for a parallel reduction. 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.
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.
Examples
{
AI12-0262-1}
{
AI12-0429-1}
Example of 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));
{
AI12-0262-1}
{
AI12-0429-1}
Example of a reduction expression that computes
the Sine of X using a Taylor expansion:function Sine (X : Float; Num_Terms : Positive := 5) return Float is
([for I in 1..Num_Terms =>
(-1.0)**(I-1) * X**(2*I-1)/Float(Factorial(2*I-1))]
'Reduce("+", 0.0));
Put_Line ("Sum of Squares is" &
Integer'Image([for I in 1 .. 10 => I**2]'Reduce("+", 0)));
-- See 3.5.7.
function Pi (Number_Of_Steps : Natural := 10_000) return Real is
(1.0 / Real (Number_Of_Steps) *
[for I in 1 .. Number_Of_Steps =>
(4.0 / (1.0 + ((Real (I) - 0.5) *
(1.0 / Real (Number_Of_Steps)))**2))]
'Reduce("+", 0.0));
{
AI12-0242-1}
{
AI12-0429-1}
Example of a reduction expression used to calculate
the sum of elements of an array of integers:A'Reduce("+",0) -- See 4.3.3.
{
AI12-0242-1}
{
AI12-0429-1}
Example of a reduction expression used to determine
if all elements in a two-dimensional array of booleans are set to true:Grid'Reduce("and", True) -- See 3.6.
{
AI12-0242-1}
{
AI12-0429-1}
Example of a reduction expression used to calculate
the minimum value of an array of integers in parallel:A'Parallel_Reduce(Integer'Min, Integer'Last)
{
AI12-0312-1}
{
AI12-0429-1}
Example of a parallel reduction expression used
to calculate the mean of the elements of a two-dimensional array of subtype
Matrix (see 3.6) that are greater than 100.0:type Accumulator is record
Sum : Real; -- See 3.5.7.
Count : Integer;
end record;
function Accumulate (L, R : Accumulator) return Accumulator is
(Sum => L.Sum + R.Sum,
Count => L.Count + R.Count);
function Average_of_Values_Greater_Than_100 (M : Matrix) return Real is
(declare
Acc : constant Accumulator :=
[parallel for Val of M when Val > 100.0 => (Val, 1)]
'Reduce(Accumulate, (Sum => 0, Count => 0));
begin
Acc.Sum / Real(Acc.Count));
Extensions to Ada 2012
Ada 2005 and 2012 Editions sponsored in part by Ada-Europe
