!standard 4.1.4(1) 20-01-06 AI12-0262-1/12 !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 WG9 Approved 22-06-22 !status ARG Approved 10-0-1 19-02-11 !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 postconditions 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 precondition or the effects of the postcondition, 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 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[(chunk_specification)]] 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 might have a static or dynamic predicate. The chunk_specification, if any, of a value_sequence shall be an /integer_/simple_expression. 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 Value_Type and Accum_Type of a reduction_attribute_reference. These subtypes and interpretations of the names and expressions of a reduction_attribute_reference are determined by the following rules: AARM Discussion: Accum_Type represents the result of the reduction (the accumulator type), and Value_Type represents the type of the input values to the reduction. * Accum_Type is a subtype of the expected type of the reduction_attribute_reference. * A /reducer subprogram/ is subtype conformant with one of the following specifications: function Reducer(Accumulator : Accum_Type; Value : Value_Type) return Accum_Type; procedure Reducer(Accumulator : in out Accum_Type; Value : in Value_Type); * A /combiner subprogram/ is a reducer subprogram where the Value parameter is of subtype Accum_Type rather than subtype Value_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 Accum_Type. * The expected type of the expression of a value_sequence is that of subtype Value_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 its 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 evaluation of a value_sequence: * if the iterated_component_association has an iterator_specification, an iteration is performed for that iterator_specification (as described in 5.5.2), and for each value produced by the iterator, the associated expression is evaluated with the loop parameter having this value, to produce a result that is converted to Value_Type, and used to define the next value in the sequence; * otherwise, the discrete_choice_list of the iterated_component_association is evaluated, and for each value, in increasing order, of the discrete subtype or range defined by the discrete_choice_list, the associated expression is evaluated with the index parameter having this value, to produce a result that is converted to Value_Type, and used to define the next value in the sequence. If the value_sequence does not have the reserved word parallel, it is produced as a single sequence of values by a single logical thread of control. If the reserved word parallel is present in the value_sequence, the enclosing reduction_attribute_reference is a parallel construct, and the sequence of values is generated by a parallel iteration (as defined in 5.5, 5.5.1, and 5.5.2), as a set of non-empty, non-overlapping contiguous chunks (/subsequences/) with one logical thread of control (see clause 9) associated with each subsequence. If there is a chunk_specification, it determines the maximum number of chunks, as defined in 5.5; otherwise the maximum number of chunks is implementation defined. 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 parts of the reduction_attribute_designator (the /reducer_/name Reducer, the /initial_value_/expression Initial_Value, and the /combiner_/name Combiner, if any), in an arbitrary order. It then initializes the /accumulator/ of the reduction expression to the value of the /initial_value_/expression (the /initial value/). The value_sequence V is then evaluated. 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 has been partitioned into one or more subsequences (see above) each with its own separate logical thread of control. 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 Accum_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 Accum_Type and the Value_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 Accum_Type and Value_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 Accum_Type and Value_Type, since the presence of the combiner is more visible in the source. AARM To Be Honest: In this rule, "equal" means semantically equal. We don't care if the bit patterns differ but the results mean the same thing. In particular, if the primitive equal is user-defined, that equality would be the one used to determine if this rule is violated. Examples -- 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. !corrigendum 4.1.4(2) @drepl @xindent<@fa@fa<@ ::=@ >@fa'@fa> @dby @xindent<@fa@fa<@ ::=@ >@hr @ @ @ @ @fa'@fa@hr @ @ |@ @fa> !corrigendum 4.1.4(6) @drepl In an @fa, if the @fa is for an attribute defined for (at least some) objects of an access type, then the @fa is never interpreted as an @fa; otherwise (and for all @fas), if the type of the @fa within the @fa is of an access type, the @fa is interpreted as an @fa. Similarly, if the @fa is for an attribute defined for (at least some) functions, then the @fa is never interpreted as a parameterless @fa; otherwise (and for all @fas), if the @fa consists of a @fa that denotes a function, it is interpreted as a parameterless @fa. @dby In an @fa that is not a @fa, if the @fa is for an attribute defined for (at least some) objects of an access type, then the @fa is never interpreted as an @fa; otherwise (and for all @fas), if the type of the @fa within the @fa is of an access type, the @fa is interpreted as an @fa. Similarly, if the @fa is for an attribute defined for (at least some) functions, then the @fa is never interpreted as a parameterless @fa; otherwise (and for all @fas), if the @fa consists of a @fa that denotes a function, it is interpreted as a parameterless @fa. !corrigendum 4.1.4(11) @drepl The evaluation of an @fa (or @fa) consists of the evaluation of the @fa. @dby The evaluation of a @fa or an @fa that is not a @fa consists of the evaluation of the @fa. The evaluation of a @fa is defined in 4.5.10. !corrigendum 4.5.10(0) @dinsc 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 (). 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 (). 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: Tucker Taft Sent: Monday, January 21, 2019 9:34 PM ... > 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. I guess we also still need to add the maximum-chunks specification to the parallel reduce. > 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). I'd be happy to take another shot at it if you would like. What you have suggested seems pretty close already. **************************************************************** From: Randy Brukardt Sent: Monday, January 21, 2019 10:09 PM Please do. I promised to get seven large AIs into the draft Standard this week, which seemed doable. But I didn't count on two snow days, nor the number of notes about errors in the wording. (Perhaps I should have predicted the latter, the former is rather hard to predict.) **************************************************************** From: Randy Brukardt Sent: Sunday, January 27, 2019 10:45 PM **************************************************************** From: Randy Brukardt Sent: Sunday, January 27, 2019 10:45 PM **************************************************************** 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). **************************************************************** From: Tucker Taft Sent: Tuesday, January 29, 2019 3:58 PM All of your proposed edits make sense to me. **************************************************************** From: Brad Moore Sent: Saturday, February 2, 2019 3:10 PM All of your proposed edits make sense to me. **************************************************************** From: Tucker Taft Sent: Wednesday, January 30, 2019 10:00 PM OK, here is yet another update to AI12-0262-1. Since we are going to re-vote it, I went ahead and added the chunk_specification. I also abandoned any use of the array aggregate -- it just didn't buy enough, and it interfered with evaluating the value_sequence in parallel for the case of: [for I in 1..N => F(I)]'Reduce(...) [This was merged with version /08 to produce version /09 - Editor.] **************************************************************** From: Tucker Taft Sent: Thursday, January 31, 2019 7:58 AM I found one typo: "reserved work parallel" should be "reserved word parallel" in the Legality Rules. Also, the !discussion still mentions array aggregates, but that is probably OK since it is explaining the choice to use iterated_component_association rather than iterated_element_association with its more general loop_parameter_specification. **************************************************************** From: Randy Brukardt Sent: Thursday, January 31, 2019 3:09 PM I had found and fixed a number of typos (including that one) in my working version of that AI. I wasn't expecting a complete redo from you or I would have sent you that working version to start with. I guess I'll have to merge that. Grumble. **************************************************************** From: Tucker Taft Sent: Thursday, January 31, 2019 4:16 PM Sorry. When I started it became clear that some serious re-wording of the Dynamic Semantics was necessary. I didn't change that much else. **************************************************************** From: Randy Brukardt Sent: Friday, February 1, 2019 9:10 PM .. > > I had found and fixed a number of typos (including that one) in my > > working version of that AI. I wasn't expecting a complete redo from > > you or I would have sent you that working version to start with. I > > guess I'll have to merge that. Grumble. > > Sorry. When I started it became clear that some serious > re-wording of the Dynamic Semantics was necessary. I didn't > change that much else. I'll live. Just venting. --- Anyway, I didn't see anything in your wording about either banning the "in" form of chunk_specification or giving it a meaning (and there doesn't seem to be any meaning for that). Did you forget to do that, or were you intending to just ignore it, figuring that no one would use it?? --- You also never described where the chunk_specification is elaborated. Your wording just says: ... If there is a chunk_specification, it determines the maximum number of chunks, as defined in 5.5; otherwise the maximum number of chunks is implementation defined. Clearly, it has to be elaborated before you do any of the iteration mentioned in the previous bullets. I'd probably suggest that it be elaborated first in the value_sequence. Maybe start the bullets with: For evaluation of a value_sequence{, the chunk_specification (if any) is elaborated as described in 5.5, then}: (Note that 5.5 doesn't separately define the elaboration of a chunk_specification, rather it is described only as part of a loop statement. Perhaps we ought to slightly rewrite that so it can stand alone? OTOH, that's pretty much true for all of the iteration text, so maybe fixing the one isn't worth it. I doubt anyone is volunteering to rewrite the whole thing so it truly can stand alone - 'twas hard enough to get it right as it is.) --- One thing that we both missed is that the wording says the reduction arguments are evaluated "in any order". But the magic words in Ada are "in an arbitrary order"; that's indexed when it occurs as it triggers the anti-order-dependence rules and various 11.6 rules. We probably mean that here and need to use those words (at least something with "arbitrary order". --- You didn't see any of the obvious/necessary simplifications to the wording that I had, but at least that made it easier for me to merge. :-) --- I didn't make any changes (other than the merge) to your wording yet, pending finding out if there is a Legality Rule missing or something else. (The two chunk_specification issues that start this message are open.) **************************************************************** From: Tucker Taft Sent: Friday, February 1, 2019 10:03 PM ... > Anyway, I didn't see anything in your wording about either banning the "in" > form of chunk_specification or giving it a meaning (and there doesn't > seem to be any meaning for that). Did you forget to do that, or were > you intending to just ignore it, figuring that no one would use it?? I believe there was a syntax rule saying that the chunk_specification must be an /integer_/simple_expression. It comes just before the Name_Resolution rules. > --- > > You also never described where the chunk_specification is elaborated. > Your wording just says: > > ... If there is a chunk_specification, it determines the maximum > number of chunks, as defined in 5.5; otherwise the maximum number of > chunks is implementation defined. > > Clearly, it has to be elaborated before you do any of the iteration > mentioned in the previous bullets. I'd probably suggest that it be > elaborated first in the value_sequence. Maybe start the bullets with: I presumed we could rely on the fact that "determining the maximum number of chunks" already implies doing the elaboration, etc. > For evaluation of a value_sequence{, the chunk_specification (if any) > is elaborated as described in 5.5, then}: > > (Note that 5.5 doesn't separately define the elaboration of a > chunk_specification, rather it is described only as part of a loop > statement. Perhaps we ought to slightly rewrite that so it can stand alone? > OTOH, that's pretty much true for all of the iteration text, so maybe > fixing the one isn't worth it. I doubt anyone is volunteering to > rewrite the whole thing so it truly can stand alone - 'twas hard > enough to get it right as it > is.) I don't see a compelling need to pull it out, as long as we agree that we are using the "same" dynamic semantics for chunk_specification as defined in 5.5. If you believe that is too much hand-waving, I'll am happy to adopt the additional wording you suggested above. > --- > > One thing that we both missed is that the wording says the reduction > arguments are evaluated "in any order". But the magic words in Ada are > "in an arbitrary order"; that's indexed when it occurs as it triggers > the anti-order-dependence rules and various 11.6 rules. We probably > mean that here and need to use those words (at least something with > "arbitrary order". Agreed. > --- > > You didn't see any of the obvious/necessary simplifications to the > wording that I had, but at least that made it easier for me to merge. > :-) ... OK, glad to hear it was too much of a pain to merge. **************************************************************** From: Randy Brukardt Sent: Monday, February 4, 2019 9:41 PM ... > > Anyway, I didn't see anything in your wording about either banning > > the "in" > > form of chunk_specification or giving it a meaning (and there > > doesn't seem to be any meaning for that). Did you forget to do that, > > or were you intending to just ignore it, figuring that no one would use it?? > > I believe there was a syntax rule saying that the chunk_specification > must be an /integer_/simple_expression. > It comes just before the Name_Resolution rules. Missed that (twice). Not sure how I missed it in the file compare, but I probably only looked at Legality Rules when I missed it. (Aside: that happens a lot; I don't think of the Syntax heading as a place for Legality Rules. I realize there are a bunch of them there, but I often miss those. Grump.) > > You also never described where the chunk_specification is elaborated. > > Your wording just says: > > > > ... If there is a chunk_specification, it determines the maximum > > number of chunks, as defined in 5.5; otherwise the maximum number of > > chunks is implementation defined. > > > > Clearly, it has to be elaborated before you do any of the iteration > > mentioned in the previous bullets. I'd probably suggest that it be > > elaborated first in the value_sequence. Maybe start the bullets with: > > I presumed we could rely on the fact that "determining the maximum > number of chunks" already implies doing the elaboration, etc. > > > > For evaluation of a value_sequence{, the chunk_specification (if > > any) is elaborated as described in 5.5, then}: > > > > (Note that 5.5 doesn't separately define the elaboration of a > > chunk_specification, rather it is described only as part of a loop > > statement. Perhaps we ought to slightly rewrite that so it can stand alone? > > OTOH, that's pretty much true for all of the iteration text, so > > maybe fixing the one isn't worth it. I doubt anyone is volunteering > > to rewrite the whole thing so it truly can stand alone - 'twas hard > > enough to get it right as it > > is.) > > I don't see a compelling need to pull it out, as long as we agree that > we are using the "same" dynamic semantics for chunk_specification as > defined in 5.5. If you believe that is too much hand-waving, I'll am > happy to adopt the additional wording you suggested above. The semantics in 5.5 start by saying that it applies to a loop_statement "For the execution of a loop_statement...". The semantics of elaborating a chunk_specification starts "If a chunk_specification is present in a parallel loop...". We're not talking about any sort of statement here at all, nor any sort of explicit loop, so using this wording is a stretch. Now, given the lack of any other wording, one can apply the Dewar rule to come to the conclusion that you are supposed to copy this semantics even though you aren't dealing with any sort of loop or statement, but that's the sort of leap that we'd hope to avoid. There probably ought to be a paragraph in 5.5 simply dedicated to the elaboration and meaning of a chunk_specification, without referring to any particular parallel construct. For instance, we could rewrite 5.5(8.1/5) as follows: If the reserved word parallel is present in the iteration_scheme of a loop_statement (a parallel loop), the loop is a parallel construct which directly contains the iteration. For an iteration that is directly part of a parallel construct, the iterations are partitioned into one or more chunks, each with its own separate logical thread of control (see clause 9). If a chunk_specification is present in such a construct, it is elaborated first, and the result of the elaboration determines the maximum number of chunks used for the parallel construct. If the chunk_specification is an integer_simple_expression, the elaboration evaluates the expression, and the value of the expression determines the maximum number of chunks. If a discrete_subtype_definition is present, the elaboration elaborates the discrete_subtype_definition, which defines the subtype of the chunk parameter, and the number of values in this subtype determines the maximum number of chunks. After elaborating the chunk_specification, a check is made that the determined maximum number of chunks is greater than zero. If this check fails, Program_Error is raised. If there is no chunk_specification, the number of chunks is implementation defined. Now, we can reference the entire chunk thing by just saying that whatever is a parallel construct that directly contains the iteration. That is, replace the parallel part of 4.5.10(29/5) by something like: If the reserved word parallel is present in the value_sequence, the enclosing reduction_attribute_reference is a parallel construct directly containing a parallel iteration that generates the sequence of values is generated by a parallel iteration (as defined in 5.5, 5.5.1, and 5.5.2), as a set of non-empty, non-overlapping contiguous chunks (subsequences) with one logical thread of control (see clause 9) associated with each subsequence. The maximum number of chunks is determined as defined in 5.5. In an ideal world, the entirety of 5.5 and 5.5.2 should be rewritten similarly so that referencing how iteration works from aggregates and quantified expressions and reductions aren't somehow leaping from loop statements to some sort of expression. But I don't have the energy to do that... Aside: 5.5 defines parallel iteration for "normal" discrete iteration, so the 4.5.10(29/5) wording needs to reference that when talking about parallel iteration, at a minimum. ... > > You didn't see any of the obvious/necessary simplifications to the > > wording that I had, but at least that made it easier for me > to merge. > > :-) ... > > OK, glad to hear it was too much of a pain to merge. Freudian slip?? :-) :-) **************************************************************** From: Tucker Taft Sent: Monday, February 11, 2019 2:33 PM [Part of another thread:] Randy or anyone else, do you have notes on any other term(s) we wanted to give a (better) name to? **************************************************************** From: Randy Brukardt Sent: Monday, February 11, 2019 2:50 PM The term for whatever happens to a value_sequence before the actual reduction happens. It currently says "evaluate", but that implies the values are determined, when we're only talking about determining the iterator to execute. The best suggestion there was "prepared". Didn't see any others in my notes, but I didn't look ultra-carefully. **************************************************************** From: Tucker Taft Sent: Monday, February 11, 2019 3:00 PM Ah yes, prepared, initiated, hazed, ... **************************************************************** From: Tucker Taft Sent: Monday, February 11, 2019 3:04 PM Slightly more seriously, perhaps a value_sequence is "deployed." For the deployment of a value_sequence: ... **************************************************************** From: Tullio Vardanega Sent: Monday, February 11, 2019 3:26 PM In my preference list, "prepared" is first, and "deployed" is second. **************************************************************** From: Randy Brukardt Sent: Monday, February 11, 2019 8:15 PM What he said. I'm going to use "prepared" unless some obviously better idea is proffered. (It was left to me and Steve to figure out, and I'm guessing that Steve has had enough of inventing terms for a while. :-) **************************************************************** From: Randy Brukardt Sent: Monday, February 11, 2019 9:45 PM > I'm going to use "prepared" unless some obviously better idea is > proffered. (It was left to me and Steve to figure out, and I'm > guessing that Steve has had enough of inventing terms for a while. :-) It turns out that the "evaluation" of a value_sequence is that needed to generate the values. We don't have anything about separately setting up (evaluating the names) of the sequence anywhere. I looked into the possibility of separately defining the preparation of the sequence, (or, even better, just elaborating it), but that wouldn't do anything other than elaborate a subtype name or range (the actual iterator name is evaluated as part of the dynamic semantics of iteration; we certainly don't want to duplicate the dynamic semantics of container iteration). So, I conclude that the problem here is evaluating the value sequence first. It should simply be the last thing evaluated before we talk about what to do with the values. This changes the offending paragraph to the following: The evaluation of a use of this attribute begins by evaluating 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 an arbitrary order. It then initializes the /accumulator/ of the reduction expression to the value of the /initial_value_/expression (the /initial value/). The value_sequence V is then evaluated. It's a bit weird to evaluate the rightmost parts of the attribute first, but we've already determined that the alternative doesn't make a lot of sense. And splitting out elaboration of an iterator_specification looks to be a lot of wording change in 5.5.2; it hardly seems worth it. This change is a lot simpler than trying to invent a new term (or reuse an old term). Any complaints?? **************************************************************** From: Tucker Taft Sent: Monday, February 11, 2019 9:51 PM No complaints from me. **************************************************************** From Justin Squirek's AARM review (October 2020): ------------ -- 4.5.10 -- ------------ 11/5: The listing of reducer subprogram specifications reads a bit awkward since the phrase "subtype conformant with the following specification" is repeated for each specification. Perhaps it would be better to say: "A reducer subprogram is subtype conformant with one of the following specifications:" [Editor's response: And presumably delete 4.5.10(13/5). This makes sense to me; I'll process it as an editorial review change on AI12-0262-1 (unless someone objects when reading this message).] 20/5: This wording seems strange "A reduction_attribute_reference denotes a value, with nominal subtype being the subtype of the..." Should this not be corrected to something more like? "A reduction_attribute_reference denotes a value, with [a or its] nominal subtype being the subtype of the..." [Editor's response: Clearly, there is word missing here. ;-) "Its" appears best; it is a bit ambigious as to whether it is refering to the value or the attribute_reference. But I don't think that matters since either interpretation would serve to define the nominal subtype of such an expression - which is the point. Saying exactly the right thing seems overly wordy: "...with the nominal subtype of the attribute_reference being ..." (I don't think values have nominal subtypes; if I'm wrong about that we could have said "value" rather than "attribute_reference", but that is only a small improvement.) Again, I'll process it as an editorial review change on AI12-0262-1 (unless someone objects when reading this message).] ****************************************************************