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
