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

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

!standard 5.5.2(2/3)          18-10-18 AI12-0262-1/03
!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 attribute reference with a new syntactic construct called a value_generator, which is very similar to an iterated_component_association, except instead of associating values to components of an array, the values are streamed into the reduction.
!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 define a new syntactic construct called a value_generator, that is very similar to an iterated_component_association and allow that to be specified as the left hand side of the attribute reference for a reduction expression. The basic idea is that during the evaluation of the value_generator, as each value is produced during evaluation of the value_generator, it is reduced into the result. 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 the iterator of the value_generator. In the parent AI, AI12-0242-1, two attributes are needed because there is otherwise no way for the programmer to explicity specify whether parallelism should be applied for an array or container object. For this AI, the parallel keyword can be specified in the value_generator, so only one attribute is needed. Reduce is chosen as the Identifier of the attribute designator.
To be more consistent with the Reduce attribute for a reduction expression with a value_generator, we relax the rules to allow a combiner subprogram to be specified if the Reduce attribute has a prefix. In this case, 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.
!wording
attribute_reference ::= prefix'attribute_designator {| [value_generator]'attribute_designator}
[Editor's note: literal [] around value_generator.]
Modify 4.1.4(11)
The evaluation of an attribute_reference (or range_attribute_reference) consists of the evaluation of the prefix {or value_generator (see 4.5.9)}.
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 a value_generator}.
Syntax
Add just after Syntax in 4.5.9
value_generator ::= [parallel] for defining_identifier in discrete_choice_list => expression | [parallel] for iterator_specification => expression
Modify definition of Reduction Expression in 4.5.9 Syntax
A /Reduction Expression/ is an attribute reference where the identifier of the attribute_designator is Reduce or Parallel_Reduce and the [expression of the] attribute_designator [is]{has} a reduction_specification.
Name Resolution Rules
Modify 4.5.9 (?)
For a subtype S [of a component of an array type A or element of an iterable container object C and a corresponding object O of the array or iterable container object, which is denoted by the prefix of a reduction_expression]:
Add after Name Resolution Rules for reduction_specification
The defining_identifier of a value_generator declares one or more instances of a /loop parameter/ where the nominal subtype of each loop parameter is a subtype that shall statically matches S.
The loop parameters of the iterator_specification of a value_generator shall statically match S.
Legality Rules
Modify 4.5.9 (?)
For a reduction_expression where the {identifier of the attribute_designator} [attribute_reference] is Reduce, [there shall not be a combiner_name specified] {the combiner_name shall be specified if subtype S and subtype R do not statically match and the attribute reference has a value_generator with the parallel keyword.}
Modify 4.5.9 (?)
For a reduction_expression where the {identifier of the attribute_designator} [attribute_reference] is Parallel_Reduce, {the attribute reference shall have a prefix and} 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] {when the identifier of the attribute_designator is} [having an] Reduce {if the attribute reference has a value_generator without the parallel keyword or if the attribute reference has a prefix}, 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_designator is Parallel_Reduce, {or if the attribute_reference has a value_generator with 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 attribute is defined for a value_generator V
V'Reduce(Reducer, Initial_Value[, Combiner])
V'Reduce is a reduction expression that initializes the result of the expression to the Initial_Value, and then evaluates the value_generator of the attribute. If the value_generator does not have the parallel keyword, then as each value of the value_generatr 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 value_generator 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 value_generator 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.
V'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
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).

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

From: Brad Moore
Sent: Wednesday, October 17, 2018  10:57 PM

Ok, since I have already defined reduction_expression with syntax in AI12-0242,
would it not be OK to just define syntax for a reduction_prefix?

ie

 reduction_prefix ::=
   (iterated_element_association) | /object_/name

And then say that a reduction expression is an attribute_reference where the
prefix is a reduction_prefix, and the attribute_designator contains a
reduction_specification where the identifier of the attribute_designator is
either Reduce or Parallel_Reduce? Or does it make sense to try to show this with
syntax definitions?

I am now thinking I only need to have iterated_element_association in the
syntax, (not iterated_component_assocation), since the syntax of an
iterated_element_association seems to support iterating through both arrays and
containers.

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

From: Randy Brukardt
Sent: Wednesday, October 17, 2018  11:39 PM

At home, so a short response. Prefix is a syntax term, so you can't use it
informally. And you don't want to change the syntax term, because it is widely
used.

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

From: Brad Moore
Sent: Thursday, October 18, 2018  12:11 AM

I see, thanks!

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

From: Brad Moore
Sent: Thursday, October 18, 2018   5:18 PM

Here is an attempt to address the comments Randy raised a couple days ago for my
first submission.

Hopefully this version is a step in the right direction.

After realizing that Prefix is syntax that is a name, I changed the definition
of Attribute_Reference, to allow a new syntactic construct called a
value_generator (which is not a prefix).

A value_generator looks very much like an iterated_component_association, but it
allows the parallel keyword, and semantically it is not an "association" of
values to the components of an array, but rather a "generator" of values, so
calling it a value_generator seemed to help clarify the concept.

Another change is how name resolution occurs for reduction expressions.
Previously, the idea was to start from the "outside" and look in, resolving the
reduction_specification after resolving the prefix.

Now, the order is a bit different. First you determine the expected type of the
overall expression, which is a single type. Next you look into the
reduction_specification, to determine the subtype associated with the Initial
Value. That subtype is the subtype that must statically match all the values in
the value_generator, so the value_generator is resolved last.

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

From: Brad Moore
Sent: Thursday, October 18, 2018   5:28 PM

Sorry, I meant to say that I wrote the AI such that the subtype of the second
parameter to the reducer_subprogram in the reduction_specification must
statically match all the values in the value_generator.

That is, you first determine the subtype of the second parameter, then use that
to resolve the values of the value_generator.

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

From: Brad Moore
Sent: Thursday, October 18, 2018   9:35 PM

One minor issue:

>For a reduction_expression where the {identifier of the attribute_designator]
>{attribute_reference} is Parallel_Reduce,

This doesn't make any sense (3 curly brackets and one square bracket??); the
previous paragraph says

>For a reduction_expression where the {identifier of the attribute_designator}
>[attribute_reference] is Reduce,

which is what I expected here; so I changed it accordingly.

The other issue is that given the change to AI12-0212-1 to use square brackets,
this ought to use those as well. So I changed the syntax and examples to do
that. (Hope I got it right.) It should be easier to change it back (replace all
of the square brackets with parens) if we decide that than it would be to change
it on the fly to square brackets.

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

Questions? Ask the ACAA Technical Agent