4.5.10 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.
Glossary entry: An
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.
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
represents the result of the reduction (the accumulator type),
and Value_Type represents the type of the input values to the
A reducer subprogram
is either subtype conformant with the following specification:
function Reducer(Accumulator : Accum_Type; Value : Value_Type) return Accum_Type;
is subtype conformant with the following specification:
procedure Reducer(Accumulator : in out Accum_Type; Value : in Value_Type);
A combiner subprogram
is a reducer subprogram where the Value parameter is of subtype Accum_Type
rather than subtype Value_Type.
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.
The maximum number of chunks for a parallel
reduction expression without a chunk_specification.
This attribute represents
a reduction expression, and is in the form of a reduction_attribute_reference.
The evaluation of a use of
this attribute begins by evaluating the parts of the reduction_attribute_designator
Reducer, the initial_value_expression
Initial_Value, and the combiner_name
Combiner, if any), in an arbitrary order. It then
initializes the accumulator of the reduction expression to the
value of the initial_value_expression
(the initial value).
V is then evaluated.
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. Combiner, if specified,
is ignored for such a (sequential) reduction expression.
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.
Each logical thread of control creates a local
accumulator for processing its subsequence. If there is a separate Combiner
subprogram specified, then the accumulator for each subsequence is initialized
to the initial value, and Reducer is called in sequence order with each
value of the subsequence as the second (Value) parameter, and with this
local accumulator as the first (Accumulator) parameter, saving the result
back into this local accumulator. If there is no separate combiner specified,
then 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). In either case, the result for the subsequence
is the final value of its local accumulator.
After all logical threads of control of a parallel
reduction expression have completed, Combiner (or Reducer, if Combiner
is not specified) 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.
If the evaluation of the value_sequence
yields an empty sequence of values, the reduction expression yields the
If an exception is propagated by one of the calls
on Reducer or Combiner, 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.
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, if Combiner is not specified, then 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.
We say the calls to Combiner are sequentially ordered
in increasing order because certain reductions, such as vector concatentation,
can be non-commutative 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 calls to Combiner are issued sequentially with respect to each other,
which may require extra synchronization if the calls to Combiner are
being executed by different logical threads of control.
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 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]
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
If a parallel reduction expression
has a combiner subprogram specified, then it is a bounded error if the
initial value is not the (left) identity of the combiner subprogram.
That is, the result of calling the combiner subprogram with the Accumulator
being the initial value and the Value being any arbitrary value of subtype
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.
Reason: There is
no way to do the individual subsequence reductions when the Accum_Type
and the Value_Type are not the same, unless we can initialize
the local accumulator with an initial-value that is presumed to be the
identity. If the initial value is not the identity, and there is more
than one chunk, it will be included more than once in the overall reduction.
We associate this bounded error with there being a combiner subprogram
specified, since that is necessary only when Accum_Type and Value_Type
are different, and because the dynamic semantics above specify the use
of the initial value multiple times whenever a combiner is specified.
We chose to base the dynamic semantics rules on the presence of a separate
combiner, rather than on the matching between Accum_Type and Value_Type,
since the presence of the combiner is more visible in the source.
To be honest: In
this rule, “equal” means semantically equal. We don't care
if the bit patterns differ but 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.
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));
An expression function that computes the Sin of
X using Taylor expansion:
function Sin (X : Float; Num_Terms : Positive := 5) return Float is
([for I in 1..Num_Terms => (-1.0)**(I-1) * X**(2*I-1)/Float(Fact(2*I-1))]
A reduction expression that outputs the sum of
Put_Line ("Sum of Squares is" &
Integer'Image([for I in 1 .. 10 => I**2]'Reduce("+", 0));
An expression function to compute the value of
-- See 3.5.7.
function Pi (Number_Of_Steps : Natural := 10_000) return Real is
(1.0 / Number_Of_Steps *
[for I in 1 .. Number_Of_Steps =>
(4.0 / (1.0 + ((Real (I) - 0.5) * (1.0 / Number_Of_Steps))**2))]
Calculate the sum of elements of an array of integers:
A'Reduce("+",0) -- See 4.3.3.
Determine if all elements in a two dimensional
array of booleans are set to true:
Grid'Reduce("and", True) -- See 3.6.
Calculate the minimum value of an array of integers
Extensions to Ada 2012
Reduction expressions attributes
Ada 2005 and 2012 Editions sponsored in part by Ada-Europe