Version 1.10 of ai12s/ai12-0262-1.txt
!standard 4.1.4(1) 19-01-17 AI12-0262-1/08
!standard 4.1.4(6)
!standard 4.1.4(11)
!standard 4.5.10(0)
!class Amendment 18-03-01
!status Amendment 1-2012 19-01-15
!status work item 19-01-17
!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.10.]
New Section 4.5.10
4.5.10 Reduction Expressions
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 attribute Reduce.
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]
For the case of an iterated_component_association of a value_sequence
having a discrete_choice_list, there shall be exactly one
discrete_choice in the discrete_choice_list, which shall be
a discrete_subtype_indication or a range.
AARM Reason: If we allow multiple choices, we would have a new
overload resolution challenge, where you could have multiple
ranges requiring resolution across them. We disallow single values
because that would be useless, and we disallow "others" because there
is no applicable index constraint. The user can use a qualified
expression if they really need to use the full flexibility of
array-aggregate notation.
AARM Ramification: There is no rule against discrete_choice_list of a
value_sequence having a discrete_choice 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.
Name Resolution Rules
The expected type for a reduction_attribute_reference shall be a single
nonlimited type.
In the remainder of this subclause,
we will refer to nonlimited subtypes Val_Type and Acc_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:
AARM Discussion: Acc_Type is short for accumulator type (the result of the
reduction), and Val_Type is short for value type (the type of the input
values to the reduction).
* Acc_Type 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 : Acc_Type; Value : Val_Type) return Acc_Type;
or is subtype conformant with the following specification:
procedure Reducer(Accumulator : in out Acc_Type; Value : in Val_Type);
* A /combiner subprogram/ is a reducer subprogram where both parameters are
of subtype Acc_Type.
* 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 Acc_Type.
* The expected type of the expression of a value_sequence is that of
subtype Val_Type.
* For an iterated_component_association of a value_sequence that has a
discrete_choice_list comprising a single range, the range shall resolve to
some discrete type[Redundant:; which discrete type shall be determined without
using any context other than the bounds of the range itself (plus the
preference for root_integer — see 8.6).]. If the range resolves to
/root_integer/; the type of the index parameter of the
iterated_component_association (the /index type/ of the value_sequence) is
Integer; otherwise the index type is the resolved type of the
discrete_subtype_indication or range of the discrete_choice_list. For an
iterated_component_assocation of a value_sequence that has an
iterator_specification, the /index type/ of the value_sequence is Integer
[Redundant: and the type of the loop parameter of the iterator_specification
is as defined in 5.5.2].
Legality Rules
The combiner_name of a reduction_specification shall be specified
if the subtypes of the parameters of the subprogram denoted by the
reducer_Name of the reduction_specification do not statically match each
other and the reduction_attribute_reference has a value_sequence with
the reserved word parallel.
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.
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 the evaluation of a value_sequence, the evaluation proceeds as for a
single-dimensional array aggregate (see 4.3.3) with component type being
Val_Type and with index type as defined above, with the sequence of values
of the value_sequence corresponding to the components of the
notional array so defined, in increasing index order.
AARM Discussion:
The presence of the parallel keyword does not effect the evaluation of
the value_sequence. Conceptually, a sequential sequence of values 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 object, and instead issue calls to the Reducer as values
are produced by the evaluation of the value_sequence.
For a value_sequence V, the following attribute is defined:
V'Reduce(Reducer, Initial_Value[, Combiner])
This attribute represents a /reduction expression/, and is in the form of a
reduction_attribute_reference.
The evaluation of a use of this attribute
begins by evaluating the value_sequence V and the parts of the
reduction_attribute_designator (the /reducer_/name Reducer, the
/initial_value_/expression Initial_Value, and the /combiner_/name Combiner,
if any), in any order. It then initializes the /accumulator/ of the
reduction expression to the value of the /initial_value_/expression (the
/initial value/).
If the value_sequence does not have the reserved word parallel, each
value of the value_sequence is passed, in order, as the second
(Value) parameter to a call on Reducer, with the first
(Accumulator) parameter being the prior value of the accumulator,
saving the result as the new value of the accumulator. The reduction
expression yields the final value of the accumulator. Combiner, if
specified, is ignored for such a (sequential) reduction expression.
If the reserved word parallel is present in a value_sequence, then
the (parallel) reduction expression is a parallel construct and the
sequence of values is partitioned into one or more contiguous
non-empty chunks (/subsequences/), each with its own separate logical
thread of control (see clause 9). Each logical thread of control
creates a local accumulator for processing its subsequence. If there
is a separate Combiner subprogram specified, then the accumulator for
each subsequence is initialized to the initial value, and Reducer
is called in sequence order with each value of the subsequence as the
second (Value) parameter, and with this local accumulator as the
first (Accumulator) parameter, saving the result back into this local
accumulator. If there is no separate combiner specified, then the
accumulator for a subsequence is initialized to the first value of
the subsequence, and calls on Reducer start with the second value
of the subsequence (if any). In either case, the result for the
subsequence is the final value of its local accumulator.
After all logical threads of control of a parallel reduction
expression have completed, Combiner (or Reducer, if Combiner is
not specified) is called for each
subsequence, in the original sequence order, passing the local
accumulator for that subsequence as the second (Value) parameter, and
the overall accumulator [Redundant: (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.
If the evaluation of the value_sequence yields an empty sequence of
values, the reduction expression yields the initial value.
If an exception is propagated by one of the calls on Reducer or
Combiner, that exception is propagated from the
reduction expression. If different exceptions are propagated in
different logical threads of control, one is chosen arbitrarily to be
propagated from the reduction expression as a whole.
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 Combiner is not specified, then 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.
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.
Bounded Errors
If a parallel reduction expression has a combiner subprogram
specified, then it is a bounded error if the initial value is not the
(left) identity of the combiner subprogram. That is, the result of
calling the combiner subprogram with the Accumulator being the initial
value and the Value being any arbitrary value of subtype Acc_Type should
produce a result equal to the Value parameter. The possible consequences
are Program_Error, or a result that does not match the equivalent
sequential reduction expression due to multiple uses of the
non-identity initial value in the overall reduction.
AARM Reason: There is no way to do the individual subsequence
reductions when the Acc_Type and the Val_Type are not the same,
unless we can initialize the local accumulator with an initial-value
that is presumed to be the identity. If the initial value is not
the identity, and there is more than one chunk, it will be included
more than once in the overall reduction. We associate this bounded
error with there being a combiner subprogram specified, since that
is necessary only when Acc_Type and Val_Type are different, and
because the dynamic semantics above specify the use of the initial
value multiple times whenever a combiner is specified. We chose to
base the dynamic semantics rules on the presence of a separate
combiner, rather than on the matching between Acc_Type and Val_Type,
since the presence of the combiner is more visible in the source.
Examples
-- 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."&", "")
--
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 : constant Summary := Summary'(Sum => 0,
Min => Integer'Last,
Max => Integer'First);
--
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)));
--
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.
!corrigendum 4.1.4(2)
Replace the paragraph:
attribute_reference ::= prefix'attribute_designator
by:
attribute_reference ::=
prefix'attribute_designator
| reduction_attribute_reference
!corrigendum 4.1.4(6)
Replace the paragraph:
In an 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.
by:
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.
!corrigendum 4.1.4(11)
Replace the paragraph:
The evaluation of an attribute_reference (or
range_attribute_reference) consists of the evaluation of the prefix.
by:
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. The evaluation of a
reduction_attribute_reference is defined in 4.5.10.
!corrigendum 4.5.10(0)
Insert new clause:
Dummy to force a conflict.
!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.
****************************************************************
From: Randy Brukardt
Sent: Tuesday, January 15, 2019 10:22 PM
Under Name Resolution Rules for AI12-0262-1, we have the following rule:
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.
This cannot be what we want. As written, this requires an actual type
somewhere in the program's universe with these characteristics. Moreover,
we wanted to allow cases where an actual array could not be declared (the
component type being indefinite, such as T'Class). This rule doesn't allow
that.
Probably what Brad (or someone) was thinking is that we need a nominal array
type so that we can reuse the array aggregate dynamic semantics for describing
how a value_sequence is evaluated. But we don't want to describe that as a
"Name Resolution Rule".
(Side note: The description above is wrong, too: the component type needs to
be "I", the type of the value being reduced. It doesn't have anything to do
with the index/loop parameter.)
I think it probably would be best to simply define this imaginary array type
in the one place that it matters, and that is the Dynamic Semantics. The only
problem is the "I", the type of the component, is defined a long ways away. It
probably would be better if "I" and "R" had real names. Maybe "reduction
component type" and "reduction result type"???
Anyway, we need a rule at the top of the Dynamic Semantics section to give
this phony array definition:
For the purposes of evaluation of a reduction expression, a value_sequence
is presumed to be of a one-dimensional array type with a component type of
I (<better name here>). The index subtype is that of the discrete_range if
present, and Standard.Integer otherwise.
AARM Discussion: We use this type only for purposes of describing the
evaluation of the value_sequence. There does not need to be any type with
these characteristics available in the program. Indeed, if I is an indefinite
type, one cannot even declare such a type.
AARM To Be Honest: The index subtype is chosen to avoid any check failures.
But there is no intent to check that the aggregate determined would fit in
the index subtype; that might matter on a system with Integer'Last = 2**15-1.
We might want to consider splitting up the current the first paragraph to
include this information in the wording for evaluating the value_sequence,
rather than putting it before everything else.
Anyway, does this make sense? Are there any better ideas of how to define the
evaluation of the value_sequence? (doing that exclusively here seems
unappealing, as a number of rules would have to be copied).
P.S. I suggest fixing this in a clean-up AI. Have no interest in reopening
this AI. :-)
****************************************************************
From: Tucker Taft
Sent: Wednesday, January 16, 2019 1:01 PM
> Under Name Resolution Rules for AI12-0262-1, we have the following rule:
>
> 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.
>
> This cannot be what we want. As written, this requires an actual type
> somewhere in the program's universe with these characteristics.
> Moreover, we wanted to allow cases where an actual array could not be
> declared (the component type being indefinite, such as T'Class). This
> rule doesn't allow that.
Good point. One of the whole goals of the reduction expression is to do a
reduction without ever "actualizing" such an array, and without having to
declare such an array type. A value sequence doesn't have a type, or if it
does, it is an anonymous array type.
> Probably what Brad (or someone) was thinking is that we need a nominal
> array type so that we can reuse the array aggregate dynamic semantics
> for describing how a value_sequence is evaluated. But we don't want to
> describe that as a "Name Resolution Rule".
>
> (Side note: The description above is wrong, too: the component type
> needs to be "I", the type of the value being reduced. It doesn't have
> anything to do with the index/loop parameter.)
>
> I think it probably would be best to simply define this imaginary
> array type in the one place that it matters, and that is the Dynamic
> Semantics. The only problem is the "I", the type of the component, is
> defined a long ways away. It probably would be better if "I" and "R"
> had real names. Maybe "reduction component type" and "reduction result
> type"???
>
> Anyway, we need a rule at the top of the Dynamic Semantics section to
> give this phony array definition:
>
> For the purposes of evaluation of a reduction expression, a
> value_sequence is presumed to be of a one-dimensional array type with
> a component type of I (<better name here>). The index subtype is that
> of the discrete_range if present, and Standard.Integer otherwise.
>
> AARM Discussion: We use this type only for purposes of describing the
> evaluation of the value_sequence. There does not need to be any type
> with these characteristics available in the program. Indeed, if I is
> an indefinite type, one cannot even declare such a type.
>
> AARM To Be Honest: The index subtype is chosen to avoid any check failures.
> But there is no intent to check that the aggregate determined would
> fit in the index subtype; that might matter on a system with
> Integer'Last = 2**15-1.
>
> We might want to consider splitting up the current the first paragraph
> to include this information in the wording for evaluating the
> value_sequence, rather than putting it before everything else.
>
> Anyway, does this make sense? Are there any better ideas of how to
> define the evaluation of the value_sequence? (doing that exclusively
> here seems unappealing, as a number of rules would have to be copied).
This seems like a lot of horsing around for no clear reason. I suggest we
adjust the wording a bit so we don't need to talk about this array type at
all. Let me give it a shot. (I'll try to send something shortly.)
> P.S. I suggest fixing this in a clean-up AI. Have no interest in
> reopening this AI. :-)
Agreed.
I also noticed a problem with the "NOTES" at the bottom:
* The Initial_Value of a reduction expression is only evaluated once.
* The /reducer_/subprogram and the /combiner_/subprogram /potentially
conflict/ with other actions.
The first bullet has a number of problems, and might be best eliminated.
But if we wanted to get it exactly right:
* The evaluation of a reduction expression includes exactly one evaluation of
the Initial_Value expression.
The second bullet is very confusing, as it is "actions", not "subprograms,"
that potentially conflict. If it is non-normative, I suggest we remove it,
as it would be more confusing than clarifying for most users, I would guess.
If it is normative, it doesn't belong in a NOTE. But I hope it is implied by
the dynamic semantics, and so should probably just be dropped.
****************************************************************
From: Steve Baird
Sent: Wednesday, January 16, 2019 1:30 PM
> One of the whole goals of the reduction expression is to do a reduction
> without ever "actualizing" such an array, and without having to declare
> such an array type. A value sequence doesn't have a type, or if it does,
> it is an anonymous array type.
If we want to preserve the wording (and perhaps we don't) defining the
dynamic semantics of evaluating a sequence in terms of evaluation of an
array aggregate, then it seems like we need some notional anonymous array
type. In particular, the component subtype of this notional array type would
need to be defined and, unlike "real" array types, that subtype might be
indefinite (e.g., for the case where the value sequence is a sequence of
values of a class-wide type, or where it is a sequence of array values having
differing lengths).
****************************************************************
From: Randy Brukardt
Sent: Wednesday, January 16, 2019 1:57 PM
Right. Defining a notional array type is what I was trying to do with my
suggested wording. Otherwise, we'd have to define the semantics of evaluating
the value sequence here, and stop describing it as an array aggregate (which
happens in a variety of places). That in fact would be my preference if it
is short enough, but that's a large IF.
****************************************************************
From: Edmond Schonberg
Sent: Wednesday, January 16, 2019 2:08 PM
Now that we have container aggregates, it might be simpler to relate the
sequence to the construction of a list container, so the index is unrelated
to any index type of that notional anonymous array type.
****************************************************************
From: Tucker Taft
Sent: Wednesday, January 16, 2019 5:12 PM
The proposed dynamic semantics for parallel reduction don't seem to work if
the value type ("I") and the accumulator type ("R") are different:
"... 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."
Some of this terminology I believe could be improved, but in any case, the
"first assigned iteration" is the first value in the chunk of values assigned
to the logical thread of control, and that is of the "value" type ("I"). But
the final result of a reduction expression is supposed to be of the
"accumulator" type ("R"). So this doesn't work as written. I think we need
to use the value of the initial-value expression even in a parallel reduction,
since that has the right type (namely, the accumulator type). I realize there
are some down sides to that, since it means the initial value really needs to
be the identity of the reduction, so we need to make that very clear. For the
sequential reduction, the initial value can be arbitrary.
Note that if the two parameter subtypes to the reducer are the same, then the
above description works OK (i.e. accumulator and value types are the same).
We could say that if there is a combiner specified for a parallel reduction,
then the initial-value expression needs to be the identity of the reducer (and
the combiner, presumably!). If no combiner is specified, the initial-value
need not be an identity of the reducer, since we can use the "trick" used
above, where the first value of each chunk is the starting value for the
accumulator. But again, this only works if the values and the accumulator(s)
are of the same type.
Note that in this latter case, it is important that the initial-value
expression *is* used in the final sequence of calls combining all of the
individual chunk accumulators into the final result.
Unless someone objects, I'll go with this last idea in my "fixup" work on
this AI, where if there is a separate combiner specified, we make it a
bounded error if the initial-value is not an identity for both reducer and
combiner. If there is no combiner specified, then the initial-value will be
included in the overall reduction exactly once, just as it is in the
sequential reduction.
****************************************************************
From: Randy Brukardt
Sent: Wednesday, January 16, 2019 5:41 PM
> The proposed dynamic semantics for parallel reduction don't seem to
> work if the value type ("I") and the accumulator type
> ("R") are different:
I think I follow your argument, and it makes sense to me.
BTW, can we give these types real names? I and R don't make a lot of sense
in rules a page down from the definition. "Value type" and "accumulator
type" also help motivate what is going on.
****************************************************************
From: Brad Moore
Sent: Wednesday, January 16, 2019 8:04 PM
> Unless someone objects, I'll go with this last idea in my "fixup" work
> on this AI, where if there is a separate combiner specified, we make
> it a bounded error if the initial-value is not an identity for both
> reducer and combiner. If there is no combiner specified, then the
> initial-value will be included in the overall reduction exactly once,
> just as it is in the sequential reduction.
Agreed, with all you have said...
****************************************************************
From: Tucker Taft
Sent: Wednesday, January 16, 2019 7:39 PM
Here is an attempt to address the problems identified earlier, as well as
several others that Randy and others have noticed. I purposely did *not*
introduce the chunk-specification syntax into this, as I believe we agreed
that that will be a separate AI. I made the last-minute switch from "I" and
"R" to "Val_Type" and "Acc_Type" as suggested in this e-mail from Randy.
> BTW, can we give these types real names? I and R don't make a lot of
> sense in rules a page down from the definition. "Value type" and
> "accumulator type" also help motivate what is going on.
---------
Fixups for AI12-0262-1 on reduction expressions
[These were used to create version /08 of the AI - Editor.]
Modify the introduction, as follows:
Reduction expressions provide[s] 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 a reference to the reduction
attribute Reduce.}
-------
Add the following immediately after the BNF (within the Syntax Rules section):
For the case of an iterated_component_association of a value_sequence
having a discrete_choice_list, there shall be exactly one
discrete_choice in the discrete_choice_list, which shall be
a discrete_subtype_indication or a range.
AARM Reason: If we allow multiple choices, we would have a new
overload resolution challenge, where you could have multiple
ranges requiring resolution across them. We disallow single values
because that would be weird, and we disallow "others" because
there is no applicable index constraint. The user can use a
qualified expression if they really need to use the full flexibility
of array-aggregate notation.
---
Name Resolution
Change "R" and "I" to "Acc_Type" and "Val_Type" throughout (based on a
suggestion by Randy).
...
Modify the following paragraph, as follows:
A /combiner_/subprogram is a /reducer_/subprogram where [subtypes I and R
statically match] {both parameters are of subtype Acc_Type}.
...
Replace the last two paragraphs of Name Resolution, which are currently:
The expected type of the index parameter of a value_sequence is that of the
discrete_choice. Otherwise, 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.
with:
For an iterated_component_association of a value_sequence that has a
discrete_choice_list comprising a single range, the range shall resolve to
some discrete type[Redundant:; which discrete type shall be determined without
using any context other than the bounds of the range itself (plus the
preference for root_integer — see 8.6).]. If the range resolves to
/root_integer/; the type of the index parameter of the
iterated_component_association (the /index type/ of the value_sequence) is
Integer; otherwise the index type is the resolved type of the
discrete_subtype_indication or range of the discrete_choice_list. For an
iterated_component_assocation of a value_sequence that has an
iterator_specification, the /index type/ of the value_sequence is Integer
[Redundant: and the type of the loop parameter of the
iterator_specification is as defined in 5.2.2].
---
Dynamic Semantics
Replace the following:
Dynamic Semantics
For a reduction_attribute_reference, 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.
with:
Dynamic Semantics
For the evaluation of a value_sequence, the evaluation proceeds as for a
single-dimensional array aggregate (see 4.3.3) with component type being
Val_Type and with index type as defined above, with the sequence of values
of the value_sequence corresponding to the components of the notional array
so defined, in increasing index order.
---
Replace the paragraphs defining the V'Reduce attribute with the following:
The following attribute is defined for a value_sequence V:
V'Reduce (/reducer_/name, /initial_value_/expression[, /combiner_/name])
The evaluation of a use of this attribute (a /reduction expression/)
begins by evaluating the value_sequence V, the /reducer_/name, the
/initial_value_/expression, and the /combiner_/name (if any), in any
order. It then initializes the /accumulator/ of the reduction
expression to the value of the /initial_value_/expression (the
/initial value/).
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 the 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. The
/combiner_/name, if specified, is ignored for such a (sequential)
reduction expression.
If the reserved word parallel is present in a value_sequence, then
the (parallel) reduction expression is a parallel construct and the
sequence of values is partitioned into one or more contiguous
non-empty chunks (/subsequences/), each with its own separate logical
thread of control (see clause 9). Each logical thread of control
creates a local accumulator for processing its subsequence. If there
is a separate combiner subprogram specified, then the accumulator for
each subsequence is initialized to the initial value, and the reducer
is called in sequence order with each value of the subsequence as the
second (Value) parameter, and with this local accumulator as the
first (Accumulator) parameter, saving the result back into this local
accumulator. If there is no separate combiner specified, then the
accumulator for a subsequence is initialized to the first value of
the subsequence, and calls on the reducer start with the second value
of the subsequence (if any). In either case, the result for the
subsequence is the final value of its local accumulator.
After all logical threads of control of a parallel reduction
expression have completed, the combiner 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 [Redundant: (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.
For a parallel reduction expression, the /combiner_/name may be
omitted if the reducer is also a combiner_subprogram. In that case,
the reducer subprogram is implicitly used as the combiner.
If the evaluation of the value_sequence yields an empty sequence of
values, the reduction expression yields the initial value.
If an exception is propagated by one of the calls on the reducer or
combiner subprogram, 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.
---
Add the following:
Bounded Errors
If a parallel reduction expression has a combiner subprogram
specified, then it is a bounded error if the initial value is not the
(left) identity of the combiner subprogram. That is, the result of
calling the combiner subprogram with the Accumulator being the initial
value and the Value being any arbitrary value of subtype Acc_Type should
produce a result equal to the Value parameter. The possible consequences
are Program_Error, or a result that does not match the equivalent
sequential reduction expression due to multiple uses of the
non-identity initial value in the overall reduction.
AARM Reason: There is no way to do the individual subsequence
reductions when the Acc_Type and the Val_Type are not the same,
unless we can initialize the local accumulator with an initial-value
that is presumed to be the identity. If the initial value is not
the identity, and there is more than one chunk, it will be included
more than once in the overall reduction. We associate this bounded
error with there being a combiner subprogram specified, since that
is necessary only when Acc_Type and Val_Type are different, and
because the dynamic semantics above specify the use of the initial
value multiple times whenever a combiner is specified. We chose to
base the dynamic semantics rules on the presence of a separate
combiner, rather than on the matching between Acc_Type and Val_Type,
since the presence of the combiner is more visible in the source.
---
Delete the two NOTES as they have some wording issues, and are probably not
that helpful.
****************************************************************
From: Randy Brukardt
Sent: Thursday, January 17, 2019 12:15 AM
> Here is an attempt to address the problems ...
Thanks for doing this. When can I get your homework, similar wording changes
to AI12-0266-1? :-)
> Modify the introduction, as follows:
>
> Reduction expressions provide[s] 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 a reference
> to the reduction attribute Reduce.}
"reference" here strikes me as strange. Either is just a use of the attribute,
or it is an attribute_reference. I changed the text to use the latter, since
that was the change agreed upon during the meeting.
I also note that this wording needs to be changed further to take AI12-0242-1
into account, which defines a Parallel_Reduce attribute.
So, I ultimately used:
A reduction expression is represented as an attribute_reference of the
reduction attributes Reduce or Parallel_Reduce.
[For AI12-0262-1 individually, I dropped the Parallel_Reduce part.]
>Add the following immediately after the BNF (within the Syntax Rules section):
>
> For the case of an iterated_component_association of a value_sequence
> having a discrete_choice_list, there shall be exactly one
> discrete_choice in the discrete_choice_list, which shall be a
> discrete_subtype_indication or a range.
I presume you want to delete the Legality Rule that said essentially this.
There's no point in having both. That forced me to move the AARM Note about
dynamic choices to the Syntax section. It doesn't really belong there, but
it makes no sense floating in Legality Rules with no related text.
> AARM Reason: If we allow multiple choices, we would have a new
> overload resolution challenge, where you could have multiple
> ranges requiring resolution across them. We disallow single values
> because that would be weird, and we disallow "others" because
> there is no applicable index constraint. The user can use a
> qualified expression if they really need to use the full flexibility
> of array-aggregate notation.
We can do better than "weird". I used "useless". I wanted to use "only useful
for an obfuscated code contest", 'cause I was thinking about:
[for I in 1 => I]'Reduce ("+", A)
which is a really complicated way to add 1 to A. Of course, we still allow:
[for I in 0..1 => I]'Reduce ("+", A)
which is an even more complicated way to add 1 to A. So I just settled on
"useless". :-)
> ---
>
> Name Resolution
>
> Change "R" and "I" to "Acc_Type" and "Val_Type" throughout (based on a
> suggestion by Randy).
I added a short AARM note to this:
AARM Discussion: Acc_Type is short for accumulator type (the result of the
reduction), and Val_Type is short for value type (the type of the input
values to the reduction).
I could see making something like this NOTE, except that notes are all at the
bottom when its far too late for these to do any good.
> ---
>
> Dynamic Semantics
>
> Replace the following:
>
> Dynamic Semantics
>
> For a reduction_attribute_reference, 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.
>
> with:
>
> Dynamic Semantics
>
> For the evaluation of a value_sequence, the evaluation proceeds as for
> a single-dimensional array aggregate (see
> 4.3.3) with component type being Val_Type and with index type as
> defined above, with the sequence of values of the value_sequence
> corresponding to the components of the notional array so defined, in
> increasing index order.
You didn't edit the following AARM notes. I tried to scrub the discussion
of "array aggregate" from them while leaving the gist.
AARM Discussion:
The presence of the parallel keyword does not effect the evaluation of the
value_sequence. Conceptually, a sequential sequence of values 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 object, and instead issue calls to the Reducer as
values are produced by the evaluation of the value_sequence.
You might have intended to remove the first AARM note completely - I couldn't
tell since you didn't mention them at all. (I don't think the first one says
much interesting, and in some sense it is wrong, since the evaluation is
likely to be different, at least at the generated code level, if the reduction
is parallel. Esp. if we have a container iterator.) The second note definitely
has value, since we want to say that even though this evaluated roughly like
an aggregate, we're not expecting an object to be created by the evaluation.
> ---
>
> Replace the paragraphs defining the V'Reduce attribute with the
> following:
>
> The following attribute is defined for a value_sequence V:
>
> V'Reduce (/reducer_/name, /initial_value_/expression[,
> /combiner_/name])
...
I assumed that you were leaving the AARM notes alone. They still seem relevant
(although you might have simplified some of the wording had you edited them).
It goes without saying that I had to delete a bunch of extra spaces after periods. :-)
****************************************************************
From: Tucker Taft
Sent: Friday, January 18, 2019 9:41 AM
>> Here is an attempt to address the problems ...
>
> Thanks for doing this. When can I get your homework, similar wording
> changes to AI12-0266-1? :-)
I'll try to do this today.
>
>> Modify the introduction, as follows:
>>
>> Reduction expressions provide[s] 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 a
>> reference to the reduction attribute Reduce.}
>
> "reference" here strikes me as strange. Either is just a use of the
> attribute, or it is an attribute_reference. I changed the text to use
> the latter, since that was the change agreed upon during the meeting.
I presumed in an informal introduction, you could say "reference an attribute"
as equivalent to "make an attribute_reference," but I am fine if you want to
formalize the wording further.
> I also note that this wording needs to be changed further to take
> AI12-0242-1 into account, which defines a Parallel_Reduce attribute.
>
> So, I ultimately used:
> A reduction expression is represented as an attribute_reference of the
> reduction attributes Reduce or Parallel_Reduce.
OK.
> [For AI12-0262-1 individually, I dropped the Parallel_Reduce part.]
>
>> Add the following immediately after the BNF (within the Syntax Rules
> section):
>>
>> For the case of an iterated_component_association of a value_sequence
>> having a discrete_choice_list, there shall be exactly one
>> discrete_choice in the discrete_choice_list, which shall be a
>> discrete_subtype_indication or a range.
>
> I presume you want to delete the Legality Rule that said essentially this.
> There's no point in having both. That forced me to move the AARM Note
> about dynamic choices to the Syntax section. It doesn't really belong
> there, but it makes no sense floating in Legality Rules with no related text.
Sorry, I had not noticed the Legality Rule. The update began by just fixing
the Name Resolution rules, but then I realized that I had to restrict the
syntax to make Name Resolution straightforward, and never went back and
looked at the whole AI.
>> AARM Reason: If we allow multiple choices, we would have a new
>> overload resolution challenge, where you could have multiple
>> ranges requiring resolution across them. We disallow single values
>> because that would be weird, and we disallow "others" because
>> there is no applicable index constraint. The user can use a
>> qualified expression if they really need to use the full flexibility
>> of array-aggregate notation.
>
> We can do better than "weird". I used "useless". I wanted to use "only
> useful for an obfuscated code contest", 'cause I was thinking about:
>
> [for I in 1 => I]'Reduce ("+", A)
>
> which is a really complicated way to add 1 to A. Of course, we still allow:
>
> [for I in 0..1 => I]'Reduce ("+", A)
I presume you meant:
[for I in 1..1 => I]'Reduce ...
>
> which is an even more complicated way to add 1 to A. So I just settled
> on "useless". :-)
Fine.
>> ---
>>
>> Name Resolution
>>
>> Change "R" and "I" to "Acc_Type" and "Val_Type" throughout (based on
>> a suggestion by Randy).
>
> I added a short AARM note to this:
>
> AARM Discussion: Acc_Type is short for accumulator type (the result
> of the
> reduction), and Val_Type is short for value type (the type of the input
> values to the reduction).
Fine.
>
> I could see making something like this NOTE, except that notes are all
> at the bottom when its far too late for these to do any good.
Agreed.
>
>> ---
>>
>> Dynamic Semantics
>>
>> Replace the following:
>>
>> Dynamic Semantics
>>
>> For a reduction_attribute_reference, 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.
>>
>> with:
>>
>> Dynamic Semantics
>>
>> For the evaluation of a value_sequence, the evaluation proceeds as
>> for a single-dimensional array aggregate (see
>> 4.3.3) with component type being Val_Type and with index type as
>> defined above, with the sequence of values of the value_sequence
>> corresponding to the components of the notional array so defined, in
>> increasing index order.
>
> You didn't edit the following AARM notes. I tried to scrub the
> discussion of "array aggregate" from them while leaving the gist.
Again, I was sort of trying to do a minimal change. The notes that followed
didn't seem too bad as is, since we are talking about a "notional" array
aggregate.
> AARM Discussion:
> The presence of the parallel keyword does not effect the evaluation of
> the value_sequence. Conceptually, a sequential sequence of values 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 object, and instead issue calls to the
> Reducer as values are produced by the evaluation of the
> value_sequence.
>
> You might have intended to remove the first AARM note completely - I
> couldn't tell since you didn't mention them at all. (I don't think the
> first one says much interesting, and in some sense it is wrong, since
> the evaluation is likely to be different, at least at the generated
> code level, if the reduction is parallel. Esp. if we have a container
> iterator.) The second note definitely has value, since we want to say
> that even though this evaluated roughly like an aggregate, we're not
> expecting an object to be created by the evaluation.
I am fine with them, thought they are of course not normative, and that is
as it should be in my view.
>> ---
>>
>> Replace the paragraphs defining the V'Reduce attribute with the
>> following:
>>
>> The following attribute is defined for a value_sequence V:
>>
>> V'Reduce (/reducer_/name, /initial_value_/expression[,
>> /combiner_/name])
> ...
>
> I assumed that you were leaving the AARM notes alone. They still seem
> relevant (although you might have simplified some of the wording had
> you edited them).
Yes, again I was *trying* to make a minimal change.
> It goes without saying that I had to delete a bunch of extra spaces
> after periods. :-)
I hope I get some credit for being consistent... ;-)
****************************************************************
From: Randy Brukardt
Sent: Monday, January 21, 2019 7:57 PM
...
> > We can do better than "weird". I used "useless". I wanted to use
> > "only useful for an obfuscated code contest", 'cause I was thinking about:
> >
> > [for I in 1 => I]'Reduce ("+", A)
> >
> > which is a really complicated way to add 1 to A. Of course, we still
> > allow:
> >
> > [for I in 0..1 => I]'Reduce ("+", A)
>
> I presume you meant:
>
> [for I in 1..1 => I]'Reduce ...
That too. I did mean what I said, assuming that "+" is predefined or at least
acts like that, so that adding zero does nothing. I was trying to get the most
insane way of adding one, and more that it does, the better. That's the
"point" of such contests, after all.
...
> >> Dynamic Semantics
> >>
> >> For the evaluation of a value_sequence, the evaluation proceeds as
> >> for a single-dimensional array aggregate (see
> >> 4.3.3) with component type being Val_Type and with index type as
> >> defined above, with the sequence of values of the value_sequence
> >> corresponding to the components of the notional array so defined,
> >> in increasing index order.
> >
> > You didn't edit the following AARM notes. I tried to scrub the
> > discussion of "array aggregate" from them while leaving the gist.
>
> Again, I was sort of trying to do a minimal change. The notes that
> followed didn't seem too bad as is, since we are talking about a
> "notional" array aggregate.
This weekend, I started worrying about that array aggregate in the case of a
parallel reduce.
For a container iterator, an array aggregate always uses a forward
(sequential) iteration. (That would be more necessary, if such a thing is
possible, if we allow iteration filters.) And elements have to be evaluated in
iteration order. According to the above, adding "parallel" doesn't change this.
Thus, it would be necessary to materialize the "notional" array aggregate in
order to apply any parallelism to the resulting "notional" array aggregate.
Moreover, we're not using any of the parallel iteration mechanism here.
Note that the above wording works fine if (1) It is a sequential reduce; (2)
The iterator is the kind without an iterator_specification; (3) The iterator
doesn't support the parallel_iterator_interface. (2) might require a bit more
explanation: a regular iterator allows the expressions to be evaluated in an
arbitrary order, so there is no problem doing that in parallel without
materializing the aggregate. [Note that adding a filter will destroy this
property, it would have to be evaluated sequentially as with the other
iterators; it would require the two iteration model at a minimum, and I'd
expect that we'd share the wording.]
What we want, I think, is to use the parallel iterator if it is available
and this is a parallel reduction. Also, note that the "length-determining"
pass is pointless for a reduction. So we probably do want to duplicate at
least some of the array aggregate wording here, because it can be simplified
and made to execute in parallel.
Maybe something like:
For evaluation of a value_sequence that contains an
iterator_specification, an iteration is performed for that
iterator_specification (as described in 5.5.2), and for each value
produced, the associated expression is evaluated, its value is converted
to Val_Type, and used to define the next value produced by the
value_sequence. If the value_sequence includes the reserved word parallel,
a parallel iteration is performed; otherwise, a sequential iteration is
performed.
For the evaluation of some other value_sequence, the evaluation proceeds
as for a single-dimensional array aggregate (see 4.3.3) with component
type being Val_Type and with index type as defined above, with the
sequence of values of the value_sequence corresponding to the components
of the notional array so defined, in increasing index order.
I think I'm missing some of the needed wording here (I lifted the first part
from the wording for array aggregates, but I'm not sure if we need to say more
about the correspondence of the values with the nominal index values), but I
wanted to bring up this problem so we can consider fixes (or whether we want
to fix it).
****************************************************************
From: Randy Brukardt
Sent: Sunday, January 27, 2019 10:45 PM
The definition of Parallel_Reduce reads:
X'Parallel_Reduce(Reducer, Initial_Value[, Combiner])
X'Parallel_Reduce is a reduction expression that yields a result
equivalent to replacing the prefix of the attribute with the
value_sequence:
[parallel for Item of X => Item]
Let's try this:
X'Parallel_Reduce("+", 0)
would give us:
[parallel for Item of X => Item]'Parallel_Reduce("+", 0)
which is a bit of a problem, since there is no Parallel_Reduce attribute for a
value_sequence!
We have to say something about the attribute identifier as well:
X'Parallel_Reduce(Reducer, Initial_Value[, Combiner])
X'Parallel_Reduce is a reduction expression that yields a result
equivalent to replacing the attribute identifier with Reduce and
prefix of the attribute with the value_sequence:
[parallel for Item of X => Item]
---
None of these attributes ever say that they are in the form of
reduction_attribute_references. That seems kinda important, since the
resolution rules are based on that. I suppose that we can skip that
information for the object forms, since they are defined by equivalence,
but not for the value_sequence form.
---
Also, the value_sequence form starts:
For a value_sequence V, the following attribute is defined:
V'Reduce(/reducer_/name, /initial_value_/expression[, /combiner_/name])
This attribute name is far too long to fit into the existing attribute annex,
it would extend all the way across the page or beyond. Moreover, we want
these parts to come from the definition for a reduction_attribute_designator
and not from this description. Note that First is defined as
First(N)
and not
First(/static_/expression)
So, for these last two issues, I suggest redoing this as:
V'Reduce(Reducer, Initial_Value[, Combiner])
This attribute represents a /reduction expression/, and is in the form of a
reduction_attribute_reference.
The evaluation of a use of this attribute
begins by evaluating the value_sequence V and the parts of the
reduction_attribute_designator (the /reducer_/name Reducer, the
/initial_value_/expression Initial_Value, and the /combiner_/name Combiner,
if any), in any order. It then initializes the /accumulator/ of the
reduction expression to the value of the /initial_value_/expression (the
/initial value/).
...
---
The original wording for this AI had "reducer_subprogram" and
"combiner_subprogram" all over the place, but such syntax was not defined. We
don't want to use syntax terms that don't actually relate to the syntax.
Luckily, there isn't much use of those that can't be easily replace by
"subprogram denoted by the reducer_name" or just Reducer (in the attribute
definition).
Since this AI will be revoted at the next meeting (because of the extensive
wording changes), I won't try to record all of this in detail.
---
Attributes have to be introduced
For blah, the following attributes are defined:
Otherwise, the tools don't work (the attribute annex is created directly out
of the attribute text, I can't reorder anything).
****************************************************************
Questions? Ask the ACAA Technical Agent