Annotated Ada Reference Manual (Ada 202y Draft 1)Legal Information
Contents   Index   References   Search   Previous   Next 

4.5.10 Reduction Expressions

1/5
{AI12-0242-1} {AI12-0262-1} 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.
1.a/5
Term entry: reduction expression — 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

Syntax

2/5
{AI12-0242-1} {AI12-0262-1} reduction_attribute_reference ::= 
    value_sequence'reduction_attribute_designator
  | prefix'reduction_attribute_designator
3/5
{AI12-0262-1} {AI12-0355-2} value_sequence ::= 
    '[' [parallel[(chunk_specification)] [aspect_specification]]
        iterated_element_association ']'
4/5
{AI12-0262-1} reduction_attribute_designator ::= 
    reduction_identifier(reduction_specification)
5/5
{AI12-0262-1} {AI12-0348-1} reduction_specification ::= reducer_nameinitial_value_expression
6/5
{AI12-0250-1} {AI12-0262-1} 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.
6.a/5
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. 
7/5
{AI12-0262-1} The chunk_specification, if any, of a value_sequence shall be an integer_simple_expression.

Name Resolution Rules

8/5
{AI12-0262-1} The expected type for a reduction_attribute_reference shall be a single nonlimited type.
9/5
{AI12-0262-1} 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:
9.a/5
Discussion: Accum_Type represents the result of the reduction (the accumulator type), and Value_Type represents the type of the input values to the reduction. 
10/5
{AI12-0262-1} Accum_Type is a subtype of the expected type of the reduction_attribute_reference.
11/5
{AI12-0262-1} A reducer subprogram is subtype conformant with one of the following specifications:
12/5
   function Reducer(Accumulator : Accum_Type;
                    Value : Value_Typereturn Accum_Type;
13/5
   procedure Reducer(Accumulator : in out Accum_Type;
                     Value : in Value_Type);
14/5
{AI12-0262-1} The reducer_name of a reduction_specification denotes a reducer subprogram.
15/5
{AI12-0262-1} The expected type of an initial_value_expression of a reduction_specification is that of subtype Accum_Type.
16/5
{AI12-0250-1} {AI12-0262-1} 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
{AI12-0262-1} {AI12-0348-1} 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
{AI12-0262-1} {AI12-0348-1} If the identifier of a reduction_attribute_designator is Parallel_Reduce, the subtypes Accum_Type and Value_Type shall statically match.
18.a/5
Reason: For a reduction_attribute_reference with a value_sequence that does not have the reserved word parallel or has a prefix and the identifier of the reduction_attribute_designator is Reduce, the subtypes Accum_Type and Value_Type can be different because only one logical thread of control is presumed so there is no need to combine multiple results. 

Static Semantics

19/5
{AI12-0262-1} 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
{AI12-0250-1} {AI12-0262-1} {AI12-0327-1} {AI12-0355-2} 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
{AI12-0262-1} 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.
21.a/5
Implementation defined: The maximum number of chunks for a parallel reduction expression without a chunk_specification.
22/5
{AI12-0262-1} For a value_sequence V, the following attribute is defined:
23/5
V'Reduce(Reducer, Initial_Value)

{AI12-0262-1} {AI12-0348-1} This attribute represents a reduction expression, and is in the form of a reduction_attribute_reference.
24/5
{AI12-0262-1} {AI12-0348-1} 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
{AI12-0262-1} {AI12-0348-1} 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
{AI12-0262-1} 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
{AI12-0262-1} {AI12-0348-1} 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
{AI12-0262-1} {AI12-0348-1} 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
{AI12-0262-1} If the evaluation of the value_sequence yields an empty sequence of values, the reduction expression yields the initial value.
30/5
{AI12-0262-1} {AI12-0348-1} 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.
30.a/5
Implementation Note: {AI12-0262-1} 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 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.
30.b/5
Discussion: {AI12-0262-1} We say the calls to Reducer that combine the results of parallel execution are sequentially ordered in increasing order because certain reductions, such as vector concatenation, can be non-commutative (but still associative) 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 combining calls to Reducer are issued sequentially with respect to each other, which may require extra synchronization if the calls to Reducer are being executed by different logical threads of control. 
31/5
{AI12-0242-1} 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)

{AI12-0242-1} {AI12-0348-1} 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)

{AI12-0242-1} {AI12-0348-1} 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
{AI12-0262-1} {AI12-0348-1} 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.
34.a/5
Reason: In a sequential reduction expression, the reducer subprogram is called in a left-to-right order, whereas in a parallel reduction expression, the reducer subprogram is called in an order that depends on the number of logical threads of control that execute the reduction and on the elements/components given to each chunk. If the reducer is associative, this order does not matter, but in other cases, very different results are possible. While one can specify the maximum number of chunks, the actual number of chunks is unspecified. Similarly, the split of elements has only weak requirements. Thus, to get a consistent and portable result, an associative reducer is required for a parallel reduction. We define this as a Bounded (Run-Time) Errors to provide a stern warning about the required nature of the reducer subprogram and to let compilers detect the problem when possible. 
34.b/5
To be honest: In this rule, “equal” means semantically equal. We don't care if the bit patterns differ but that 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. 

Examples

35/5
{AI12-0262-1} {AI12-0429-1} 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
{AI12-0262-1} {AI12-0429-1} 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
{AI12-0262-1} {AI12-0379-1} {AI12-0429-1} 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
{AI12-0262-1} {AI12-0379-1} {AI12-0429-1} 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
{AI12-0242-1} {AI12-0429-1} 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
{AI12-0242-1} {AI12-0429-1} 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
{AI12-0242-1} {AI12-0429-1} 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
{AI12-0312-1} {AI12-0429-1} 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));

Extensions to Ada 2012

52.a/5
{AI12-0005-1} {AI12-0242-1} {AI12-0262-1} {AI12-0348-1} Reduction expressions and the associated attributes are new. 

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