Ada Conformity Assessment Authority      Home Conformity Assessment   Test Suite ARGAda Standard
 
Ada Reference Manual (Ada 202x Draft 20)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)]] iterated_element_association ']'
4/5
reduction_attribute_designator ::= reduction_identifier(reduction_specification)
5/5
reduction_specification ::= reducer_nameinitial_value_expression[, combiner_name]
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 either subtype conformant with the following specification:
12/5
   function Reducer(Accumulator : Accum_Type; Value : Value_Typereturn Accum_Type;
13/5
or is subtype conformant with the following specification:
14/5
   procedure Reducer(Accumulator : in out Accum_Type; Value : in Value_Type);
15/5
A combiner subprogram is a reducer subprogram where the Value parameter is of subtype Accum_Type rather than subtype Value_Type.
16/5
The reducer_name of a reduction_specification denotes a reducer subprogram.
17/5
The combiner_name, if any, of a reduction_specification denotes a combiner subprogram.
18/5
The expected type of an initial_value_expression of a reduction_specification is that of subtype Accum_Type.
19/5
The expected type of the expression of the iterated_element_association of a value_sequence is that of subtype Value_Type

Legality Rules

20/5
The combiner_name of a reduction_specification shall be specified if the subtypes of the parameters of the subprogram denoted by the reducer_name of the reduction_specification do not statically match each other and the reduction_attribute_reference has a value_sequence with the reserved word parallel.
21/5
If the identifier of a reduction_attribute_designator is Parallel_Reduce then the combiner_name of the reduction_specification shall be specified if the subtypes of all the parameters of the subprogram denoted by the reducer_name of the reduction_specification do not statically match.

Static Semantics

22/5
A reduction_attribute_reference denotes a value, with nominal subtype being the subtype of the first parameter of the subprogram denoted by the reducer_name.
23/5
For a reduction_attribute_reference that has a value_sequence with the reserved word parallel, if the combiner_name is not specified, then the subprogram denoted by the reducer_name also implicitly denotes the combiner subprogram.
24/5
For a reduction_attribute_reference where the identifier of the reduction_attribute_designator is Parallel_Reduce, if the combiner_name is not specified, then the subprogram denoted by the reducer_name also implicitly denotes the combiner subprogram.

Dynamic Semantics

25/5
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.
26/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.
27/5
For a value_sequence V, the following attribute is defined:
28/5
V'Reduce(Reducer, Initial_Value[, Combiner])

This attribute represents a reduction expression, and is in the form of a reduction_attribute_reference.
29/5
The evaluation of a use of this attribute begins by evaluating the parts of the reduction_attribute_designator (the reducer_name 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). The value_sequence V is then evaluated.
30/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. Combiner, if specified, is ignored for such a (sequential) reduction expression.
31/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.
32/5
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.
33/5
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.
34/5
If the evaluation of the value_sequence yields an empty sequence of values, the reduction expression yields the initial value.
35/5
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.
36/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:
37/5
X'Reduce(Reducer, Initial_Value[, Combiner])

X'Reduce is a reduction expression that yields a result equivalent to replacing the prefix of the attribute with the value_sequence:
37.1/5
[for Item of X => Item]
38/5
X'Parallel_Reduce(Reducer, Initial_Value[, Combiner])

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:
38.1/5
[parallel for Item of X => Item]

Bounded (Run-Time) Errors

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

Examples

40/5
An expression function that returns its result as a Reduction Expression:
41/5
function Factorial(N : Natural) return Natural is
   ([for J in 1..N => J]'Reduce("*", 1));
42/5
An expression function that computes the Sin of X using Taylor expansion:
43/5
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))]
      'Reduce("+", 0.0));
44/5
A reduction expression that outputs the sum of squares:
45/5
Put_Line ("Sum of Squares is" &
          Integer'Image([for I in 1 .. 10 => I**2]'Reduce("+", 0));
46/5
An expression function to compute the value of Pi:
47/5
--  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))]
           'Reduce("+", 0.0));
48/5
Calculate the sum of elements of an array of integers:
49/5
A'Reduce("+",0)  -- See 4.3.3.
50/5
Determine if all elements in a two dimensional array of booleans are set to true:
51/5
Grid'Reduce("and", True)  -- See 3.6.
52/5
Calculate the minimum value of an array of integers in parallel:
53/5
A'Parallel_Reduce(Integer'Min, Integer'Last)

Contents   Index   References   Search   Previous   Next 
Ada-Europe Ada 2005 and 2012 Editions sponsored in part by Ada-Europe