Ada Conformity Assessment Authority      Home Conformity Assessment   Test Suite ARGAda Standard
 
Ada Reference Manual (Ada 202x Draft 18)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_component_association ']'
4/5
reduction_attribute_designator ::= reduction_identifier(reduction_specification)
5/5
reduction_specification ::= reducer_nameinitial_value_expression[, combiner_name]
6/5
For the case of an iterated_component_association of a value_sequence having a discrete_choice_list, there shall be exactly one discrete_choice in the discrete_choice_list, which shall be a discrete_subtype_indication or a range.
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 both parameters are of subtype Accum_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 a value_sequence is that of subtype Value_Type.
20/5
For an iterated_component_association of a value_sequence that has a discrete_choice_list comprising a single range, the range shall resolve to some discrete type; which discrete type shall be determined without using any context other than the bounds of the range itself (plus the preference for root_integer - see 8.6). If the range resolves to root_integer; the type of the index parameter of the iterated_component_association (the index type of the value_sequence) is Integer; otherwise the index type is the resolved type of the discrete_subtype_indication or range of the discrete_choice_list. For an iterated_component_association of a value_sequence that has an iterator_specification, the index type of the value_sequence is Integer and the type of the loop parameter of the iterator_specification is as defined in 5.5.2

Legality Rules

21/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.
22/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

23/5
The nominal subtype of the index parameter of a value_sequence is that of the discrete_choice. The nominal subtype of the loop parameter of a value_sequence is as defined for an iterator_specification (see 5.5.2).
24/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.
25/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.
26/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

27/5
For the evaluation of a value_sequence:
28/5
if the iterated_component_association has an iterator_specification, an iteration is performed for that iterator_specification (as described in 5.5.2), and for each value produced by the iterator, 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;
29/5
otherwise, the discrete_choice_list of the iterated_component_association is evaluated, and for each value, in increasing order, of the discrete subtype or range defined by the discrete_choice_list, the associated expression is evaluated with the index parameter having this value, to produce a result that is converted to Value_Type, and used to define the next value in the sequence.
30/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.
31/5
For a value_sequence V, the following attribute is defined:
32/5
V'Reduce(Reducer, Initial_Value[, Combiner])

This attribute represents a reduction expression, and is in the form of a reduction_attribute_reference.
33/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.
34/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.
35/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.
36/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.
37/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.
38/5
If the evaluation of the value_sequence yields an empty sequence of values, the reduction expression yields the initial value.
39/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.
40/5
For a prefix X of an array type (after any implicit dereference), or denotes an iterable container object (see 5.5.1), the following attributes are defined:
41/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:
41.1/5
[for Item of X => Item]
42/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:
42.1/5
[parallel for Item of X => Item]

Bounded (Run-Time) Errors

43/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

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