Version 1.2 of ai12s/ai12-0262-1.txt

Unformatted version of ai12s/ai12-0262-1.txt version 1.2
Other versions for file ai12s/ai12-0262-1.txt

!standard 5.5.2(2/3)          18-10-16 AI12-0262-1/02
!standard 5.5.2(5/4)
!standard 5.5.2(7/3)
!class Amendment 18-03-01
!status work item 18-03-01
!status received 18-03-01
!priority Medium
!difficulty Hard
!subject Map/Reduce attribute
!summary
The capabilities of Reduction Expressions are expanded to allow the programmer to stream values into the reduction by writing the prefix of the reduction attribute as an iterated_element_association or iterated_component_association.
!problem
This proposal depends on the facilities for aspect Global (AI12-0079-1) and for aspect Nonblocking (AI12-0064-2). Those proposals allow the compiler to statically determine where parallelism may be introduced without introducing data races. This proposal also depend on parallel iteration support for containers (AI12-0266-1), and reduction expressions (AI12-0242-1)
AI12-0242-1 defines a reduction operation for existing objects. However, in cases where there is no existing type that matches the objects to reduce, this is less than convenient. Moreover, if the stream of objects to reduce is indefinite, it isn't possible in Ada to declare an array type that matches it. One could instantiate an indefinite container, but that would have to be materialized (since it is made up of calls to user-defined operations).
What is needed is a way to directly process a stream of objects without declaring a type and without forcing the materialization of an object.
!proposal
The proposal is to allow an iterated_component_association or an iterated_element_association as the prefix of a reduction expression attribute reference. The basic idea is that as during the evaluation of the prefix, as each value is produced during evaluation of the prefix, it is reduced into the result value. Thus there is no need to create storage to hold all the values prior to the reduction. If the parallel keyword is present in the prefix, then the reduction expression is a parallel construct and the iteration is divided among multiple logical threads of control as appropriate for array or container iteration depending on whether the prefix is an iterated_component_association (for arrays) or a iterated_element_association (for containers). In the parent AI, AI12-0242-1, two attributes are needed because there is otherwise no way for the programmer to explicitly specify whether parallelism should be applied for an array or container object. For this AI, the parallel keyword is allowed in the prefix, so only one attribute is needed. Reduce is chosen as the name of the attribute designator.
To be more consistent with the Reduce attribute for an attribute prefix of an array object or container iterator object, we relax the rules to allow a combiner subprogram to be specified. For an array object or container iterator object prefix, the combiner_subprogram is not expected to be called, since only one logical thread of control is presumed. It does make it easier for the programmer to switch back and forth between sequential and parallel execution by simply removing or adding the parallel keyword if the prefix is an iterated_component_association or iterated_element_association. Similarly, for an array object or iterated container object, one merely needs to change the name of the attribute designator to select parallel or sequential execution.
!wording
Modify 4.5.9 (1)
A Reduction expression provides a way to write a value that denotes a combination of the component values of an array or of the element values stored in an /iterable container object/ (see 5.5.1) {or the values assigned to loop parameters during the evaluation of an iterated_component_association (see 4.3.3) or iterated_element_association (see 4.3.5)}.
Modify 4.5.9 (?)
[For a reduction_expression where the attribute_reference is Reduce, there shall not be a combiner_name specified] For a reduction_expression where the attribute_reference is Reduce, the combiner_name shall be specified if subtype S and subtype R do not statically match and the prefix of the attribute is an iterated_component_association or iterated_element_association with the parallel keyword.
Modify 4.5.9 (?)
For a reduction_expression where the attribute_reference is Parallel_Reduce, the combiner_name shall be specified if subtype S and subtype R do not statically match. {The prefix of the attribute shall denote either an object of an array type or an /iterated container object/.}
Modify 4.5.9 (?)
AARM Note
The combiner_name is [always] optional for Reduce {if the attribute prefix does not have the parallel keyword}, because only one logical thread of control is presumed so there is no need to provide a way to combine multiple results.
Static Semantics
Modify 4.5.9 (?)
For a reduction_expression where the attribute_reference is Parallel_Reduce, {or if the attribute_reference is Reduce and the attribute prefix has the parallel keyword, } if the combiner_name is not specified[,] then the subprogram denoted by the reducer_subprogram also implicitly denotes the combiner_subprogram.
Dynamic Semantics
Add after 4.5.9 (?)
The following attributes are defined for a prefix I that is of an iterated_component_association or iterated_element_association
I'Reduce(Reducer, Initial_Value[, Combiner])
I'Reduce is a reduction expression that initializes the result of the expression to the Initial_Value, and then evaluates the prefix of the attribute. If the prefix does not have the parallel keyword, then as each value of the prefix is produced, a call is made to the Reducer passing the value as the second (Value) parameter to the call, and using the result of the previous iteration as the first (Accumulator) parameter. Yields the final result of the iteration.
If the prefix of the attribute does have the parallel key word, then the reduction expression is a parallel construct and the iterations are divided among multiple logical threads of control. Each logical thread of control generates a local copy of the result of its iteration, which is initialized to the value of the loop parameter or loop cursor associated with the first assigned iteration. As each value of the prefix is produced, a call is made to the Reducer passing the value as the second (Value) parameter to the call, and using the result of the previous iteration as the first (Accumulator) parameter. As each logical thread of control completes its assigned iterations, the Combiner is called using the value of the local result as the second (Value) parameter of the call, and using the previous final result value, as the the first (Accumulator) parameter for the call. Once all logical threads of control have completed, yields the result of the last call to Combiner. The calls to Combiner are issued sequentially in increasing iteration order. The Combiner may be omitted if the Reducer is also a combiner_subprogram. In that case, the Reducer is implicitly used also as the Combiner argument.
I'Reduce yields the Initial_Value if the prefix of the attribute reference denotes a null range of values.
Add to 4.5.9 examples
Examples
Determine how many integers in an array are prime numbers
Prime_Count : constant Natural := (for P of A when Is_Prime(P) => 1)'Reduce("+",0);
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 Sin of X using Taylor expansion
function Sin(X : Float; Num_Terms : Positive := 5) return Float is
((for I in 1..Num_Terms => (-1.0)**I * X**(2*I-1)/Float(Fact(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(21) 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));
!discussion
This AI doesn't get into too much detail about how the presence of the parallel keyword in an iterated_component_association or an iterated_element_association maps to generating the parallelism. We already define this for arrays and iterated container objects, so it seems unnecessary to repeat that detail here. It also doesn't add the parallel keyword to the iterated_component_association or iterated_element_association syntax. It seems more appropriate that that should be done in AI12-0212-1 (Container aggregates; generalized array aggregates). Presumably there would be a benefit for adding parallelism for such aggregates as well.
It's mildly annoying that qualifying the prefix changes the resolution a lot (as that turns the attribute into the object version (as in AI12-0242-1)).
Specifically:
My_String : String(1..10);
(for I in My_String'range => My_String(I))'Reduction (Standard'"&", "") -- This is a terrible way to copy a string. :-) String'(for I in My_String'range => My_String(I))'Reduction (Standard'"&", "")
The first reduction overall requires a single expected type; it can't be used in a type conversion, for instance. The type provided allows the rest of the reduction to resolve. The second reduction requires the prefix to have a single expected type; that type provides enough information to let the rest of reduction to resolve, and allow any sort of use that can resolve.
Ultimately, however, these should do the same thing on a reasonable compiler; there are permissions for the second to not materialize the prefix and allow interleaving. The iterator that drives the first is the one explicitly given, while the second is driven by the built-in iterator for array types. But these ultimately are the same.
We can imagine cases where one would be legal and the other not legal, and possibly cases where the semantics would be different in some subtle way, but in general thinking of them as two views of the same construct will be fine for anyone but Ada lawyers.
We already have some special purpose expressions in Ada in the form of quantified expressions and array aggregates of the form using an iterated_component_association, that are effectively a form of reduction.
Consider:
All_Graduated : constant Boolean := (for all Student of Class => Passed_Exam (Student));
Someone_Graduated : constant Boolean := (for some Student of Class => Passed_Exam (Student));
Here we are in both cases effectively reducing a set of Boolean values into a single result using quantified expressions.
A similar effect can be written using a more generalized 'Reduce attribute expression, in combination with an array aggregate.
All_Graduated : constant Boolean := (for Student of Class => Passed_Exam (Student))'Reduce("And", True);
Someone_Graduated : constant Boolean := (for Student of Class => Passed_Exam (Student))'Reduce("Or", False);
Here we use "and" and "or" as the combiner_subprogram of the Reduction expression. The initial value plays an important role, since the Identity for "and" must be true, and false for "or".
!ASIS
** Unknown.
!ACATS test
ACATS B- and C-Tests are needed to check that the new capabilities are supported.
!appendix

From: Brad Moore
Sent: Tuesday, October 16, 2018  11:45 PM

Here is my first attempt at this AI, which expands the 'Reduce attribute defined
in AI12-0242-1 to allow the prefix to be an iterated_component_association or an
iterated_element_association. [This is version /02 of this AI - Editor.]

I chose to overload 'Reduce as the name of the attribute associated with this
AI.

'Reduce is used whether the parallel keyword is present in the prefix or not.

I didn't add the parallel keyword to syntax of these associations in this AI. I
presumed that that already existed in AI12-0212-1.

My thought was that it was more appropriate to do that in AI12-0212-1 where
iterated_component_association and iterated_element_association is defined. I
think there may be similar benefits to adding parallelism to aggregates.

****************************************************************

From: Randy Brukardt
Sent: Wednesday, October 17, 2018   6:45 PM

>The following attributes are defined for a prefix I that is of an
>iterated_component_association or iterated_element_association
>
>I'Reduce(Reducer, Initial_Value[, Combiner])

Several issues here:

(1) There's only one attribute defined here, so use singular.
(2) There's no parens or brackets surrounding the
    iterated_component_association, they have to be given here.
(3) An iterated_component_association is not syntactally a prefix, so you can't
    talk about a prefix.

The net effect is that you need new syntax for this construct, either here or in
4.1.4. My original version had that part:

Syntax

reduction_expression ::=
   (iterated_element_association)'Reduce(Reducer, Initial_Value[, Combiner])

Although this obviously doesn't support the other options (square brackets,
iterated_component_associations).

You then have to have quite a bit of wording for the resolution of these
expressions (they DO NOT resolve like attributes or like parts of aggregates,
either -- all of that has to be done explicitly here). In particular, the
determination of S is much harder than it is with the regular attribute form,
where the prefix is resolved without context and has to resolve to an existing
type. Here S comes from the iterator, which has to be resolved first, and by
itself (without the context usually available when resolving in an aggregate).
There was some discussion on this point in my old AI draft, and some more in the
public e-mail (there was also a lot in private e-mail).

****************************************************************

Questions? Ask the ACAA Technical Agent