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

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

!standard 4.1.4(1)          19-01-14 AI12-0262-1/06
!standard 4.1.4(6)
!standard 4.1.4(11)
!standard 4.5.9(0)
!class Amendment 18-03-01
!status Amendment 1-2012 19-01-15
!status ARG Approved 9-0-2 19-01-14
!status work item 18-03-01
!status received 18-03-01
!priority Medium
!difficulty Hard
!subject Map-Reduce attribute
!summary
Reduction Expressions are defined to allow the programmer to apply the Map-Reduce paradigm to map/transform a set of values to a new set of values, and then summarize/reduce the transformed values into a single result value.
!problem
A common problem in computing is the Map-Reduce paradigm where a set of values possibly needs to be mapped or transformed to another set of values and the new values then need to be summarized or reduced to produce a single final result.
Currently in Ada, one generally has to write a subprogram to do this, which involves writing a loop to iterate through the set of values, and a global accumulator variable or set of variables that get updates through each iteration of the loop.
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.
To further illustrate the need, one of the most important additions to Ada 2012 is contract specifications for subprograms. However to write pre and post conditions that attempt to summarize inputs or outputs, one has to write a subprogram to express the summary result, which can add clutter to an API for an abstraction and injects a level of indirection. If a client then wants to understand the requirements of the pre condition or the effects of the post condition, one has to find and examine the body of the subprogram named in the contract specification.
It would be useful if such summarizations could be expressed in a simpler, more concise and localized manner, such as an expression, without always having to write another subprogram.
Ada 83 was already a pretty good language for "hybrid" functional/imperative programming, because you can have a sequence of declarations that progressively compute a desired result. Often it was only because you needed to enter a loop that you had to do any significant amount of computing after the "begin". In today's Ada, with conditional expressions, quantified expressions, the recently approved iterated component association, and our newly proposed container aggregates, the need for explicit ifs and loops after the "begin" is continuing to decrease. There appears to be a shift in the a balance between functional and imperative features, more towards the functional side. There is a resurgence of interest in functional programming these days, but going all the way to "pure functional" programming, with "monads" instead of assignment statements, and recursion only with no iteration, would be too going too far towards the functional side. Nonetheless, it is important to "complete" the functional primitives, if only to give the desired power to Ada's contract-based programming.
Some of the existing syntax in Ada already can provide forms of summarization. For example, a quantified expression can be viewed as being a special purpose Reduction Expression that applies an operation, the Predicate, to a set of values to reduce the predicate results to a single Boolean result. Similarly, an array aggregate in the form of an iterated_component_association can also be viewed as being a special purpose Reduction Expression that applies an operation, in-place concatenation, to a set of values to reduce into an array result. What is needed is a more general syntactic form where there is less constraint on the type of operation to be applied to summarize the set of values, and the operation can produce result values of types other than Boolean values, or array objects.
Such a reduction capability is the last remaining major component needed to complete the "iterated" operations. There are many applications of reduction capabilities, that apply to both sequential and parallelism use cases. It will often be the right way to define, in a postcondition, the final value of one output of the subprogram, even though the subprogram might have multiple outputs and might do many other things.
Such a capability can allow programmers to express algorithms more concisely, which tends to also make the algorithms easier to read, debug, understand, and maintain.
Another need is to be able to perform reductions in parallel. Modern computing platforms typically provide support for multicore computing, yet it can be considerably difficult to write algorithms that take advantage of these multicore platforms. Such algorithms tend to be very error prone, and are difficult to debug. Many of the divide and conquer algorithms involve reduction, commonly known as Map-Reduce, in the parallelism world.
The challenge with such algorithms when looping constructs are employed, is that a global accumulator value is typically needed, which normally would imply a data race if multiple threads of execution end up updating the global variable in parallel.
parallel reduction is in many ways a separate issue, when compared to sequential reduction, and where (and whether) it is best inserted depends heavily on the amount of computing done within a single iteration, the independence of those computations, and the number of iterations. The advantage of the notations like quantified expressions, and container aggregates, is that they are self-contained, and can often be analyzed holistically by the compiler to determine whether and where to insert parallelism.
It is important to also allow the programmer to indicate explicitly whether parallelism should be applied, as it documents to the reader that performance is important to the user, and makes it clear that parallel execution is likely to be worthwhile.
For instance, a compiler might choose to conservatively apply parallelism, only in cases where it can statically determine that the performance would be guaranteed to benefit from the parallelism. A programmer might want to override the conservatism of the compiler and experiment with parallelism to measure the benefits, and then deploy the code in the form that provided the optimal performance.
!proposal
This proposal depends on parallel iteration support for containers (AI12-0266-1) and support for container aggregates (AI12-0212-1).
The goals of this proposal are to provide a mechanism for expressing a summarization of a set of values. Such a summarization is known as a reduction. It is desired that such a mechanism;
- is easy to understand - is easy to write/express - allows parallelization - provides safety by eliminating data races and logic errors. - fits in well with existing Ada syntax
The proposal defines a new type of attribute reference called a reduction expression that allows a special form of iterated_component_association called a value_sequence to be specified as the left hand side of the "'", and where the attribute designator, Reduce, defines a reduction specification that indicates how the reduction is to be applied. The basic idea is that during the evaluation of the value_sequence, as each value is produced, it is reduced into the result by calling a reducer subprogram that is named by the reduction specification. Thus there is no need to create storage to hold all the values generated by the value_sequence prior to the reduction, since they are streamed into the result as they are produced.
A reducer subprogram is a subprogram that combines two input values into a single result value.
Another part of the reduction specification is the Initial_Value, which is a value of the result type of the reduction_attribute_reference. This value is used to initialize the result of the reduction expression prior to the iteration of the value_sequence. It also serves as the result value when the value_sequence does not produce any values.
If the parallel keyword is specified on the value sequence, then the reduction expression is a parallel construct and the iteration is divided among multiple logical threads of control. In this case, another subprogram may be specified as part of the reduction specification, called the combiner_subprogram, to combine the final results of the multiple logical threads of control. This may be necessary, if different parameter types are needed than specified in the profile of the reducer subprogram.
If the parallel keyword is not specified, then the combiner subprogram need not be specified, and likely will not be called even if specified, since only one logical thread of control is presumed, and so there is no need to combine multiple results.
!wording
Replace 4.1.4(2) with:
attribute_reference ::= prefix'attribute_designator | reduction_attribute_reference
Modify 4.1.4(6):
In an attribute_reference {that is not a reduction_attribute_reference}, if the attribute_designator is for an attribute defined for (at least some) objects of an access type, then the prefix is never interpreted as an implicit_dereference; otherwise (and for all range_attribute_references), if the type of the name within the prefix is of an access type, the prefix is interpreted as an implicit_dereference. Similarly, if the attribute_designator is for an attribute defined for (at least some) functions, then the prefix is never interpreted as a parameterless function_call; otherwise (and for all range_attribute_references), if the prefix consists of a name that denotes a function, it is interpreted as a parameterless function_call.
Replace 4.1.4(11) with:
The evaluation of a range_attribute_reference or an attribute_reference that is not a reduction_attribute_reference consists of the evaluation of the prefix. Redundant[The evaluation of a reduction_attribute_reference is defined in 4.5.9.]
New Section 4.5.9
4.5.9 Reduction Expressions
Reduction expressions provides 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 using the Reduce attribute.
Syntax
reduction_attribute_reference ::= value_sequence'reduction_attribute_designator
value_sequence ::= '[' [parallel] iterated_component_association ']'
reduction_attribute_designator ::= /reduction_/identifier(reduction_specification)
reduction_specification ::= /reducer_/name, /initial_value_/expression[, /combiner_/name]
Name Resolution Rules
The expected type for a reduction_attribute_reference shall be a single nonlimited type.
Given nonlimited subtypes I and R, where R is a subtype of the expected type of the reduction_attribute_reference:
A /reducer_/subprogram is either subtype conformant with the following specification:
function Reducer(Accumulator : R; Value : I) return R;
or is subtype conformant with the following specification:
procedure Reducer(Accumulator : in out R; Value : I);
A /combiner_/subprogram is a /reducer_/subprogram where subtypes I and R statically match.
The reducer_name of a reduction_specification denotes a reducer_subprogram.
The combiner_name of a reduction_specification denotes a combiner_subprogram.
The expected type of an initial_value_expression of a reduction_specification is that of subtype R.
The expected type of the expression of a value_sequence is that of subtype I.
The expected type of the index parameter of a value_sequence is that of the discrete_choice. The expected type of the loop parameter of a value_sequence is as defined for an iterator_specification (see 5.5.2).
The expected type for a value_sequence shall be a single one-dimensional array type. The component type of this array type is the expected type of the index parameter or loop parameter for the value_sequence.
Legality Rules
The combiner_name of a reduction_specification shall be specified if the subtypes of the parameters of the /reducer_/subprogram denoted by the reduction_specification do not statically match each other and the reduction_attribute reference has a value_sequence with the reserved work parallel.
AARM Reason: For a reduction_attribute_reference with a value_sequence that does not have the parallel keyword, the combiner_name of the reduction_specification is optional because only one logical thread of control is presumed so there is no need to provide a way to combine multiple results. End AARM Reason.
The discrete_choice_list of a value_sequence shall have a single discrete_choice and the discrete_choice shall not be the reserved word others.
AARM Ramification: The discrete_choice_list of a value_sequence may have a discrete_choice that is a nonstatic choice_expression or that is a subtype_indication or range that defines a nonstatic or null range. If the choice is a subtype_indication, the denoted subtype may have a static or dynamic predicate.
Static Semantics
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).
A reduction_attribute_reference denotes a value, with nominal subtype being the subtype of the first parameter of the reducer subprogram.
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_subprogram also implicitly denotes the combiner_subprogram.
Dynamic Semantics
For a reduction_attribute_reference, first the value_sequence is first evaluated. For a value_sequence with or without the reserved word parallel, the evaluation of a value_sequence is as defined for an array aggregate (see 4.3.3). The reduction_attribute_designator is then evaluated, and then the reduction is evaluated.
AARM Discussion: The presence of the parallel keyword does not effect the evaluation of the value_sequence. Conceptually, an array aggregate is produced, as though the parallel keyword were not present.
AARM Implementation Note: The intended implementation model is that a value_sequence generally avoids producing a temporary array aggregate object, and instead issue calls to the Reducer as values are produced by the evaluation of the value_sequence.
The following attribute is defined for a value_sequence V:
V'Reduce(Reducer, Initial_Value[, Combiner])
V'Reduce evaluates the Initial_Value, then initializes the result of the reduction expression to the value of the Initial_Value expression. If the value_sequence does not have the reserved word parallel, the value of each component of the array aggregate produced by the value_sequence is passed in ascending order as the second (Value) parameter to execute a call to Reducer, using the result of the previous iteration as the first (Accumulator) parameter of the call. The result of V'Reduce is the final result of the iteration. If the reserved word parallel is present in a value_sequence (a parallel reduction), then the reduction expression is a parallel construct and the iterations are partitioned into one or more chunks, each with its own separate logical thread of control (see clause 9). Each logical thread of control generates a local copy of the result of its iteration, which is initialized to the value of the expression produced by the first assigned iteration. 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, V'Reduce yields the result of the last call to Combiner. The calls to Combiner are executed 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.
If the value_sequence of the reduction_attribute reference produces an empty sequence, V'Reduce yields the value of the Initial_Value expression
AARM Implementation Note: For a reduction_attribute_reference that has a value_sequence without the parallel keyword, generally the compiler can still choose to execute the reduction in parallel, presuming doing so would not change the results. However, if the combiner_name is not specified, then sequential execution is necessary if the subtypes of the parameters of the reducer_subprogram denoted by the reduction_specification do not statically match, since there is no subprogram identified in the construct that could be used for combining the results in parallel.
AARM Discussion:
We say the calls to Combiner are sequentially ordered in increasing order because certain reductions, such as vector concatentation, can be non-commutative 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 calls to Combiner are issued sequentially with respect to each other, which may require extra synchronization if the calls to Combiner are being executed by different logical threads of control.
NOTES
The Initial_Value of a reduction expression is only evaluated once.
The /reducer_/subprogram and the /combiner_/subprogram /potentially conflict/ with other actions.
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-1) * 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)]'Reduce (Standard."&", "") -- This is a terrible way to copy a string. :-) String'[for I in My_String'range => My_String(I)]'Reduce (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".
We considered whether the syntax should be based on an iterated_element_association rather than an iterated_component_association. That would allow us to use the reverse keyword in the value_sequence. It was felt that the iterated_component_association and the model of an array aggregate is conceptually easier to understand than a container aggregate. Further, it was noted that the use of the order in reduction is rare, and only applies to certain reductions such as non-commutative reductions like concatenation. For such reductions, it is likely better to use an array aggregate rather than a reduction expression. Further the need for reverse ordering is even rarer and can be achieved easily enough using some simple math in the map applied in the value_sequence.
e.g.
Success := Rockets.Blastoff (Countdown_Sequence => [for I in 1 .. 10 => (11-I)]'Reduce("&", []));
We considered whether the combiner_subprogram should be disallowed if the parallel keyword is not present. We decided to allow it to be specified, even though it likely will not be called in this case, 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.
We considered defining an Associative aspect that could be specified on subprograms, and then having the compiler check that the reducer_subprogram and combiner_subprogram have that aspect specified as True when the parallel keyword is specified. Although it is true that the reducer_subprogram and combiner_subprogram need to be associative operations for parallelism to be applied, there are a number of problems with this. First of all, the compiler cannot verify if a particular call is truly associative, so the compiler would have to have faith in the programmer to get this right. Secondly, associativity can sometimes be in the eye of the beholder. For example, integer addition is normally considered an associative operation, but if integer overflow is a possibility, then technically the operation is not associative. That might be an important consideration for some users, and unimportant to others. Similarly, floating point math is not associative, due to the rounding errors that get introduced, but for many users, the results are good enough to consider as being associative. Thirdly, this added a lot of complexity and wording changes to the AI, which was deemed to not be worthwhile.
We considered whether the initial_value was always needed or not. We could alternatively overload the attribute names to provide versions that do not accept a second argument.
This however, means that there can be a question about what the expression should evaluate to, if the prefix of the attribute specifies a null range of values. Likely, an exception would need to be raised, but that can add complexity for uses such as contracts, since handling the exception case would need to be considered. We decided that for now at least, it is better to keep the interface simple. If an exception is needed for a null range, there are other ways to do that already in the language.
Another concern might be about the need to perform multiple reductions at the same time.
Consider:
Sum : Integer := [for Item of A => Item]'Reduce("+", 0): Min : Integer := [for Item of A => Item]'Reduce(Integer'Min, Integer'Last); Max : Integer := [for Item of A => Item]'Reduce(Integer'Max, Integer'First);
Here we have three calculations that might ideally occur in parallel, but here would normally be expected to execute sequentially with respect to each other.
One might want to calculate these three results iterating only once through the array.
This can be accomplished by creating a composite result type, and writing a user-defined reducer function.
type Summary is record Sum : Integer; Min : Integer; Max : Integer; end record;
-- Identity value for the Reduce function Identity : constant Summary := Summary'(Sum => 0, Min => Integer'Last, Max => Integer'First);
-- Reducer function for the Reduction expression function Reduce (L, R : Summary) return Summary with Nonblocking, Globals => null is (Summary'(Sum => L.Sum + R.Sum, Min => Integer'Min (L.Min, R.Min), Max => Integer'Max (L.Max, R.Max)));
-- Reduction expression to compute all 3 results at once Result : constant Summary := [for Item of A => Item]'Reduce(Reduce, Identity);
It was also noted here during performance testing that better times were collected by actually writting 3 separate reductions, however in other more complicated examples, it was found that writing a composite object as above provided better performance.
!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: Randy Brukardt
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.

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

From: Brad Moore
Sent: Thursday, October 18, 2018  10:16 PM

> 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.

Thanks for doing what I meant, and not what I said. :-)

> 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 change it on the fly.

I saw the square brackets in Tuckers latest version of his AI, which I think
makes perfect sense in his AI. But I intentionally did not incorporate them in
this AI. To me, the square brackets suggest an aggregate value for an array or
container object is being created, and it is beneficial to use them for that
purpose. In this AI, there is no aggregate, just an iterator/generator, so it
made sense to me to not have them, since semantically, the construct is very
different.

Maybe I need to have my view expanded, but at this point, having square brackets
in the value_generator syntax doesn't make sense to me. Basically, I dont see
the benefit for it here. Maybe someone could enlighten me about why this would
be a good thing?

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

From: Tucker Taft
Sent: Thursday, October 18, 2018  10:33 PM

In my mind, it is definitely a good thing to use [...] here, if we believe we
are generally going to be using [...] for constructs representing a homogeneous
collection, as opposed to (...) which is retained for a heterogeneous collection
like a record, where each element potentially has a different type.

Or more fundamentally, this notation is producing a sequence, just like an array
or a vector, but then it is immediately consuming the sequence.  It would be
weird in my view to shift the notation just because the sequence only exists
temporarily.

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

From: Randy Brukardt
Sent: Friday, October 19, 2018  12:13 AM

What he said.

Right now, the square brackets look weird to us 'cause we haven't been using
them for 40 years. But once we start using them, they'll quickly become natural,
and it would be bizarre to use () in one place and [] in another for what is
fundamentally the same thing. (The "oddity" is the language-defined arrays, they
should look like just another container. Little late for that, of course.)

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

From: Brad Moore
Sent: Friday, October 19, 2018  10:41 AM

OK, it makes sense to now when I think less of the underlying semantics, and
more of it being a set of values to be reduced.

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

From: Brad Moore
Sent: Wednesday, January  9, 2019  12:37 AM

Here is my homework update for AI12-0262-01 Map-Reduce attribute (Reduction
Expressions) [This is version /04 of the AI - Editor.]

There is a fair number of updates to the AI, but here is the main summary

- Renamed value_generator term to value_sequence
- Reworked the value_generator syntax to be based on
  iterated_component_association rather than iterated_element_association.

The main ramification of this change, is that we cannot use the reverse keyword
to iterate in reverse order.

For reductions, order is mostly unimportant, and only applies in certain types
of reductions such as non-commutative reductions like concatenation.

For concatenation, it is likely a better choice to use array aggregate syntax,
rather than as a reduction

If reverse order is needed, one can apply some simple math in the map function
of the expression to get that effect.

e.g.

 Success := Rockets.Blastoff (Countdown_Sequence => [for I in 1 .. 10 => (11-I)]'Reduce("&", []));

It was felt that basing the model on an array aggregate, rather than a container
aggregate would be conceptually simpler to understand, and possibly implement.

- More details on the dynamic semantics are provided.
The conceptual model is that the value_sequence first produces an array
aggregate object, then those values are passed in ascending order into
successive calls to the Reducer subprogram.

This is only the conceptual model. An AARM note recommends that the temporary
array object not be created, and instead, calls are streamed into calls to the
reducer subprogram as values are produced by the value sequence.

- Most of the wording was moved into the new section for Reduction Expressions

Thats pretty much it, other than numerous editorial changes.

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

From: Randy Brukardt
Sent: Thursday, January 10, 2019  11:55 PM

I've changed the wording instructions as I've commented on repeatedly tonight.

Shortened a bunch overlong lines.

----

Technical comment, only noticed because my name is on it:

>[For a reduction_attribute_reference for a value_sequence with the
>parallel keyword, the Nonblocking aspect of the /reducer_/subprogram
>shall be statically True, and the Global aspect of the
>/reducer_/subprogram shall be statically null.]
>
> [Author's note: Randy says this rule is unnecessary, as it is covered
> by  parallel constructs in AI12-0267-01, is it worth keeping here?]

That's only true if you have wording that says a parallel
reduction_attribute_reference is a parallel construct.  And you don't have that
(it appears in the !proposal and !discussion, but not the actual wording.

And here you are insisting on the strictest checks all of the time, whereas once
you say this is a parallel constrcut, the rules allow users to turn off these
checks (via a policy setting) if they think they know what they're doing.

So since this isn't our intent, it's just wrong. You probably ought to have
wording early on that says this is a parallel construct (in Static Semantics or
even the introduction, not Legality Rules).

I didn't make this change (maybe I should have).

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

From: Randy Brukardt
Sent: Friday, January 11, 2019  6:07 PM

At the start of the new section, you have grammar:

reduction_expression ::= reduction_attribute_reference

But there is no use of the non-terminal "reduction_expression" anywhere. And 
since this doesn't do anything at all (it just a "copy production"), I would 
just get rid of it.

Also, you have various wording changes in 4.1.4 that use 
reduction_attribute_reference. That's a forward reference, and should be 
marked as such with a (see 4.5.9) on it's first use.

However, it's usually the case that non-terminals at least appear in some 
syntax definition before it is used. Thus, I would be happier if 
"reduction_attribute_reference" was used somehow in the syntax of 4.1.4.

"range_attribute_reference" is defined separately because it's not an 
expression. That's not the case for a reduction_attribute_reference, so it 
would make sense to put "reduction_attribute_reference" under 
"attribute_reference".

Thus, I would suggest changing the syntax in 4.1.4 to:

    attribute_reference ::= prefix'attribute_designator
       | reduction_attribute_reference

That means that you don't have to make any of the 4.1.4 changes that you have 
(because reduction_attribute_reference would be automatically included), but 
some other wording would need to be changed to exclude 
reduction_attribute_reference. I saw 4.1.4(6) [which talks about 
"the attribute_designator"] and 4.1.4(11) [which talks about "the prefix"] 
would need to do that. For instance:

Replace 4.1.4(11) with:
The evaluation of a range_attribute_reference or an attribute_reference that
is not a reduction_attribute_reference consists of the evaluation of the 
prefix. Redundant[The evaluation of a reduction_attribute_reference is defined 
in 4.5.9.]

Probably the other would be:

In an attribute_reference {that is not a reduction_attribute_reference}, 
if the attribute_designator is for an attribute defined for (at least 
some) objects of an access type, then the prefix is never interpreted as
an implicit_dereference; otherwise (and for all 
range_attribute_references{ and reduction_attribute_references}), if {there 
is a prefix and }the type of the name within the prefix is of an access 
type, the prefix is interpreted as an implicit_dereference. Similarly, 
if the attribute_designator is for an attribute defined for (at least some) 
functions, then the prefix is never interpreted as a parameterless 
function_call; otherwise (and for all range_attribute_references{ and 
reduction_attribute_references}), if {there is a prefix and} the prefix 
consists of a name that denotes a function, it is interpreted as a 
parameterless function_call. 

[This subsumes the any change for AI12-0242-1 to this paragraph, and the 
other changes to 4.1.4 listed in that AI aren't needed, either. If we don't 
do AI12-0242-1, then we only need the first change, as no 
reduction_attribute_reference would have a prefix.]

----------

In the Name Resolution Rules:

Given nonlimited subtypes I and R, where R is a subtype of the expected
type:

Which expected type? Do you mean the expected type of the 
reduction_attribute_reference? If so, say that, don't make me guess.

-------

Typos:

Otherwise{,} the expected type of the loop parameter of a value_sequence is 
as defined for an iterator_specification ({s}[S]ee 5.5.2).

--------

As noted last night, if we say that the reduction is a parallel construct 
then we don't need anything else here as the checking policy of 9.10.1 
defines the rules. This is said in the Dynamic Semantics section, but that's 
rather too late (especially as it's primary effect is on Legality). So I'd 
suggest adding that to the start of the Static Semantics section:

A reduction_attribute_reference whose value_sequence includes the reserved 
word parallel is a parallel construct.

And delete the first paragraph of the Legality Rules, because it is dead 
wrong. (This change lets the checking policy control the rules in this 
construct, like every other parallel construct.)

We can also drop this phrase from the Dynamic Semantics for the attribute.

However, the parallel loop dis defined in Dynamic Semantics, so I suppose 
it would be OK to just delete the Legality Rule.

--------

The discrete_choice_list of a value_sequence is allowed to have a 
discrete_choice that is a nonstatic choice_expression or that is a 
subtype_indication or range that defines a nonstatic or null range.

This seems more like an AARM Ramification than a Legality Rule (because it 
doesn't prohibit anything). At most, it should be marked as redundant.

Related to that, you didn't say anything about predicates. Do you mean to 
allow discontiguous ranges via the use of a predicate? (I don't see a problem, 
but it does complicate the implementation.)

That is:

        subtype Odd is Natural
           with Static_Predicate => 1 | 3 | 5 | 7 | 9;

        [for I in Odd => I]'Reduce("+", 0)

??? (For more fun, imagine a Dynamic_Predicate being used.) Note that this 
wouldn't be substantially different than what would happen with a filter 
(AI12-0250-1), so maybe it's OK. I'd definitely add that to the 
note/redundant text if intended.

--------

The two AARM notes under Static Semantics seem to relate to parallel 
execution, which is Dynamic Semantics. Moreover, I don't see the point of 
the second one (it's an as-if optimization and implementations are always 
allowed to do those), and the first one is misleading. "sequential execution 
is presumed" seems to imply something else could happen. I'd at a minimum 
replace "presumed" by "necessary". And these seem in the wrong order. Maybe 
mention the possibility of parallel execution anyway at the start of the 
note with:

For a reduction_attribute_reference that has a value_sequence without the 
parallel keyword{, generally the compiler can still choose to execute the 
reduction in parallel, presuming that would not change the results.
However,} if the combiner ... 

Then the second note is unneeded. We surely don't need to go into detail about 
what is and is not allowed unless it is somehow different than the usual.

---------

AARM Suggested Implementation

No such thing. That's "AARM Implementation Note".

-----

Typo: Colon needed here:

The following attribute is defined for a value_sequence V{:}

-----

The AARM Note at the end of the Dynamic Semantics section appears to say 
essentially the same thing twice. Can these be combined??

-----

That's it for the !wording. Note that I didn't try to figure out if this does 
the right thing (I barely know what that is :-), but just that the wording 
organization made sense.

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

Questions? Ask the ACAA Technical Agent