4.5.10 Reduction Expressions
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.
Syntax
Name Resolution Rules
A
reducer subprogram
is either subtype conformant with the following specification:
function Reducer(Accumulator : Accum_Type; Value : Value_Type) return Accum_Type;
or is subtype
conformant with the following specification:
procedure Reducer(Accumulator : in out Accum_Type; Value : in Value_Type);
Legality Rules
Static Semantics
Dynamic Semantics
For the evaluation of a
value_sequence,
the
iterated_element_association
is elaborated, then an iteration is performed, and for each value conditionally
produced by the iteration (see
5.5 and
5.5.2),
the associated
expression
is evaluated with the loop parameter having this value, to produce a
result that is converted to Value_Type, and used to define the next value
in the sequence.
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.
V'Reduce(Reducer,
Initial_Value)
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
(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.
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.
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. 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.
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.
If the evaluation of the
value_sequence
yields an empty sequence of values, the reduction expression yields the
initial value.
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.
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)
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)
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
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)). 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.
Examples
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 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));
A reduction expression
that outputs the sum of squares:
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 Pi:
--
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));
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 in parallel:
A'Parallel_Reduce(Integer'Min, Integer'Last)
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));
Ada 2005 and 2012 Editions sponsored in part by Ada-Europe