Ada Reference Manual (Ada 2022) — Legal Information
Contents   Index   References   Search   Previous   Next 

4.5.10 Reduction Expressions

1/5
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

2/5
reduction_attribute_reference ::= 
    value_sequence'reduction_attribute_designator
  | prefix'reduction_attribute_designator
3/5
value_sequence ::= 
    '[' [parallel[(chunk_specification)] [aspect_specification]]
        iterated_element_association ']'
4/5
reduction_attribute_designator ::= 
    reduction_identifier(reduction_specification)
5/5
reduction_specification ::= reducer_name, initial_value_expression
6/5
The iterated_element_association of a value_sequence shall not have a key_expression, nor shall it have a loop_parameter_specification that has the reserved word reverse.
7/5
The chunk_specification, if any, of a value_sequence shall be an integer_simple_expression.

Name Resolution Rules

8/5
The expected type for a reduction_attribute_reference shall be a single nonlimited type.
9/5
In the remainder of this subclause, we will refer to nonlimited subtypes Value_Type and Accum_Type of a reduction_attribute_reference. These subtypes and interpretations of the names and expressions of a reduction_attribute_reference are determined by the following rules:
10/5
Accum_Type is a subtype of the expected type of the reduction_attribute_reference.
11/5
A reducer subprogram is subtype conformant with one of the following specifications:
12/5
   function Reducer(Accumulator : Accum_Type;
                    Value : Value_Type) return Accum_Type;
13/5
   procedure Reducer(Accumulator : in out Accum_Type;
                     Value : in Value_Type);
14/5
The reducer_name of a reduction_specification denotes a reducer subprogram.
15/5
The expected type of an initial_value_expression of a reduction_specification is that of subtype Accum_Type.
16/5
The expected type of the expression of the iterated_element_association of a value_sequence is that of subtype Value_Type. 

Legality Rules

17/5
If the reduction_attribute_reference has a value_sequence with the reserved word parallel, the subtypes Accum_Type and Value_Type shall statically match.
18/5
If the identifier of a reduction_attribute_designator is Parallel_Reduce, the subtypes Accum_Type and Value_Type shall statically match.

Static Semantics

19/5
A reduction_attribute_reference denotes a value, with its nominal subtype being the subtype of the first parameter of the subprogram denoted by the reducer_name.

Dynamic Semantics

20/5
For the evaluation of a value_sequence, the iterated_element_association, the chunk_specification, and the aspect_specification, if any, are elaborated in an arbitrary order. Next 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, which produces a result that is converted to Value_Type and is used to define the next value in the sequence.
21/5
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.
22/5
For a value_sequence V, the following attribute is defined:
23/5
V'Reduce(Reducer, Initial_Value)

This attribute represents a reduction expression, and is in the form of a reduction_attribute_reference.
24/5
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.
25/5
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.
26/5
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.
27/5
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.
28/5
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.
29/5
If the evaluation of the value_sequence yields an empty sequence of values, the reduction expression yields the initial value.
30/5
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.
31/5
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:
32/5
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:
32.1/5
[for Item of X => Item]
33/5
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:
33.1/5
[parallel for Item of X => Item]

Bounded (Run-Time) Errors

34/5
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.

Examples

35/5
Example of an expression function that returns its result as a reduction expression:
36/5
function Factorial(N : Natural) return Natural is
   ([for J in 1..N => J]'Reduce("*", 1));
37/5
Example of a reduction expression that computes the Sine of X using a Taylor expansion:
38/5
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));
39/5
Example of a reduction expression that outputs the sum of squares:
40/5
Put_Line ("Sum of Squares is" &
          Integer'Image([for I in 1 .. 10 => I**2]'Reduce("+", 0)));
41/5
Example of a reduction expression used to compute the value of Pi:
42/5
--  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));
43/5
Example of a reduction expression used to calculate the sum of elements of an array of integers:
44/5
A'Reduce("+",0)  -- See 4.3.3.
45/5
Example of a reduction expression used to determine if all elements in a two-dimensional array of booleans are set to true:
46/5
Grid'Reduce("and", True)  -- See 3.6.
47/5
Example of a reduction expression used to calculate the minimum value of an array of integers in parallel:
48/5
A'Parallel_Reduce(Integer'Min, Integer'Last)
49/5
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:
50/5
type Accumulator is record
   Sum   : Real; -- See 3.5.7.
   Count : Integer;
end record;
51/5
function Accumulate (L, R : Accumulator) return Accumulator is
  (Sum   => L.Sum   + R.Sum,
   Count => L.Count + R.Count);
52/5
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));
Contents   Index   References   Search   Previous   Next 
Ada-Europe Ada 2005 and 2012 Editions sponsored in part by Ada-Europe