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

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

!standard 4.5.9 (0)          17-12-28 AI12-0242-1/01
!class Amendment 14-06-20
!status work item 14-06-20
!status received 14-06-17
!priority Medium
!difficulty Hard
!subject Reduction Expressions
!summary
New syntax and semantics to facilitate reduction and parallelism via Reduction Expressions.
!problem
A common computing model is known as MapReduce, which is essentially a technique used to generate a summary result for a set of data. Such problems are often good candidates for parallelization using divide and conquer strategies to process the data set, where the partial results of each portion of the data can be combined in parallel to produce the final result. Generating such libraries from scratch is non-trivial, and writing programs that use such libraries can be difficult to debug and error-prone to create. A general facility to solve such problems with syntax, where the compiler can provide improved safety and analysis would be helpful.
!proposal
This proposal depends on the facilities for aspect Global (AI12-0079-1) and for aspect Nonblocking (AI12-0064-2). Those proposals allow the compiler to statically determine where parallelism may be introduced without introducing data races.
The goals of this proposal are to provide a mechanism for expressing solutions to MapReduce problems that;
- Is easy to understand - Is Easy to write - Allows parallelization - Provides safety by eliminating data races and logic errors. - Fits in well with existing Ada syntax
Note that in this model the compiler will identify any code where a potential data race occurs (following the rules for concurrent access to objects as specified in the Language Reference Manual RM 9.10(11)), and point out where objects cannot be guaranteed to be independently addressable. If not determinable at compile-time, the compiler may insert run-time checks to detect data overlap.
Reduction Expressions ---------------------
A Reduction Expression is a syntactic construct, similar to a quantified expression that can be used to combine a set of values into a single result. This mechanism is called reduction.
Indeed, 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.
A Reduction expression is a more general syntactic form where there is less constraint on the type of operation to be applied to the set of values, and the operation can produce result values of types other than Boolean values, or array creation.
Semantics: A Reduction Expression looks like a quantified expression, except that the quantifier keyword ("all" or "some") is not present, and the predicate expression is replaced with an expression that evaluates to a function call returning an object of a nonlimited type, that is called the combiner_expression.
The combiner expression must denote a function call that has at least one parameter of the same type as the type of the Reduction expression. The combiner expression is evaluated iteratively to accumulate a result, which ultimately becomes the result of the Reduction Expression. The accumulation of the result occurs as the result of each iteration is implicitly fed back as an input to the function denoted by the combiner expression. The implicit parameter substitution is identified syntactically based on the "<>" box notation syntax, except that the box notation in this case must enclose the initial value to be used for the first call to the function, since at that point there would otherwise be no existing value to pass into the function. The initial value also serves to be the result of the reduction expression for the case when there are no iterations performed (E.g. For the case when a when a loop_parameter_specification for a Reduction Expression specifies a null range).
If the reduction expression is executed in parallel, then each thread of control (i.e. tasklet, see AI12-0119-1), needs to accumulate its partial result into an implicit accumulator variable. This implicit variable is of the type associated with the reduction expression result, and it is initialized to a special value called the identity value. The identity value is specified by either applying an Identity aspect to the declaration of the function denoted by the combiner expression, or indirectly to another function called a reducer function that is similarly associated with the combiner expression via the use of a Reducer aspect applied to the function denoted by the combiner expression. The Identity aspect of a function identifies a value of the same type as the combiner expression. If a combiner expression does not have a corresponding Identity value, then the Reduction expression cannot be parallelized, and it is assumed to require sequential execution.
It is recommended that a compiler apply parallelism implicitly to a reduction expression if it can be determined that there are no data dependences, and the compiler can determine the reduction operations needed to initialize and combine partial results. Otherwise, a compiler would fall back to sequential execution for the construct.
Once each tasklet has generated its local partial result, it can combine these results with other tasklets using a reducer function. The Reducer function for a Reduction expression is a function that accepts two parameters where both parameters are of the same type, and returns a result of that same type, which is also the type of the Reduction expression.
For parallelization, the combiner expression must denote a function that has a Reducer aspect specified for its declaration if the function itself is not a Reducer function. The Reducer aspect identifies another function that is to be used to combine partial results from two tasklets into the final result of the Reduction expression. The multiple results are combined two at a time.
The Reducer function is expected to generate an associative result based on the input parameters. A Reducer function does not need to be commutative (e.g. vector concatenation), as it is expected that the implementation will ensure that the results are combined in a manner that is consistent with sequentially applying the Reducer function to the partial results in iteration order. The combiner expression does not need to have an associated Reducer function if the Reduction expression is to be computed sequentially.
For Reductions Expressions executed in parallel, it is important that the value of the Identity aspect associated with a function does not affect the result of the computation. For example, if the reduction result type is Integer and the reducer is addition, then the Identity value should be zero, since adding zero to any value does not affect the result value. Similarly, if the reducer is multiplication then the Identity value should be one, since multiplying any Integer value by 1 does not affect the result value. If the result type is a vector and the reducer is concatenation, then the Identity value should be an empty vector, since concatenating an empty vector to another vector does not affect the value of the other vector.
!wording
Modify 4.4(1/3)
"In this International Standard, the term "expression" refers to a construct of the syntactic category expression or of any of the following categories: choice_expression, choice_relation, relation, simple_expression, term, factor, primary, conditional_expression, quantified_expression {, reduction_expression}."
Modify 4.4(7/3)
"primary ::=
numeric_literal | null | string_literal | aggregate | name | allocator | (expression) {| <reduction_parameter>} | (conditional_expression) | (quantified_expression) {| (reduction_expression)}"
Add 4.4(15.h)
"Wording Changes from Ada 2012
Added reduction_expression and reduction_parameter to primary."
Replace 4.5.1(2-3) with
"The following logical operators are predefined for every boolean type T
function "and"(Left, Right : T) return T with Identity => True function "or" (Left, Right : T) return T with Identity => False function "xor"(Left, Right : T) return T with Identity => False"
The following logical operators are predefined for every modular type T
function "and"(Left, Right : T) return T function "or" (Left, Right : T) return T with Identity => 0 function "xor"(Left, Right : T) return T with Identity => 0"
The following logical operators are predefined for every one-dimensional array type T whose component type is a boolean type:
function "and"(Left, Right : T) return T function "or" (Left, Right : T) return T function "xor"(Left, Right : T) return T"
Add AARM note
"The Identity aspect for the "and" function for modular types is not specified
because it is difficult to statically specify a value that would work for all types. eg. type X is mod 97; We could say that it is T'Last for types where the modulus is a power of 2, for example, but that is not general enough, similarly, we could say that the Identity for the "and" function for a one-dimensional array is T'(others => True), but that only works if T is a constrained array type, so we dont bother trying to specify the Identity aspect for these operations."
Modify 4.5.3(2)
"function "+"(Left, Right : T) return T{ with Identity => 0}
function "-"(Left, Right : T) return T{ with Reducer => "+"}
"
Modify 4.5.5(2)
"function "*" (Left, Right : T) return T{ with Identity => 1}
function "/" (Left, Right : T) return T{ with Reducer => "*"} function "mod"(Left, Right : T) return T function "rem"(Left, Right : T) return T"
Modify 4.5.5(12) "function "*"(Left, Right : T) return T{ with Identity => 1.0}
function "/"(Left, Right : T) return T{ with Reducer => "*"}
"
Modify 4.5.5(14) "function ""(Left : T; Right : Integer) return T{ with Reducer => ""}
function ""(Left : Integer; Right : T) return T{ with Reducer => ""} function "/"(Left : T; Right : Integer) return T{ with Reducer => "*"}
"
Modify 4.5.5(19) "function "*"(Left, Right : universal_fixed) return universal_fixed{ with Identity => 1.0}
function "/"(Left, Right : universal_fixed) return universal_fixed{ with Reducer => "*"
"
Add Section 4.5.9
"Reduction Expressions"
Reduction expressions provide a way to write a reduction that combines a set of values into a single result.
Syntax
reduction_expression ::= for loop_parameter_specification => combiner_expression | for iterator_specification => combiner_expression
reduction_parameter ::= expression
Wherever the Syntax Rules allow an expression, a reduction_expression may be used in place of the expression, so long as it is immediately surrounded by parentheses.
Discussion: The syntactic category reduction_expression appears only as a primary that is parenthesized. The above rule allows it to additionally be used in other contexts where it would be directly surrounded by parentheses. This is the same rule that is used for conditional_expressions; see 4.5.7 for a detailed discussion of the meaning and effects of this rule.
Name Resolution Rules
The expected type of a reduction_expression is any nonlimited type. The expected type of a combiner_expression is the same type as the immediately enclosing reduction_expression.
The expected type of a reduction_parameter is the same type as the immediately enclosing reduction_expression.
A reducer_function is a function that has exactly two parameters where both formal parameters and the result are of the same type. A reducer_function is called implicitly to combine results from multiple executions of the combiner_expression of a reduction expression when the reduction expression has parallel execution. The function denoted by a combiner_expression can be associated with a reducer_function. If such an association exists, either the function is itself a reducer_function or its declaration has the Reducer aspect which specifies the associated reducer_function.
An identity_value is a value that can be used to initialize implicit declarations of variables that accumulate the results of a reduction_expression when the reduction expression has parallel execution. The identity_value for the function denoted by a combiner_expression is determined from either; the Identity aspect specified on the declaration of the denoted function, or by the Identity aspect specified on the declaration of another function named by the the Reducer aspect of the denoted function.
Legality Rules
A reduction_parameter shall only appear in a combiner_expression.
A reduction_parameter shall appear exactly once within the immediately enclosing combiner_expression of a reduction_expression.
AARM Ramification A reduction expression may consist of nested reduction expressions, each with a corresponding combiner_expression and reduction_expression.
The type of an identity_value associated with the reduction_expression and the type of the reduction_parameter shall be of the same type as the reduction_expression.
The result type and the type of both formal parameters of an associated reducer_function shall be of the same type as the reduction_expression.
Static Semantics
For parallel execution, the combiner_expression either needs to denote a function that is a reducer_function, or the denoted function needs to have the Reducer aspect specified on its declaration. Otherwise, the reduction expression is executed sequentially.
For parallel execution, the combiner_expression either needs to denote a function that has the Identity aspect specified on its declaration, or the denoted function nees to have the Reducer aspect specified on its declaration and the function named by the Reducer aspect needs to have the Identity aspect specified on its declaration. Otherwise, the reduction expression is executed sequentially.
For a function_specification, the following language-defined operational aspects may be specified with an aspect_specification (see 13.1.1):
Identity
The aspect Identity denotes a value that is to specified as the identity_value associated with a Reduction_Expression. The aspect shall be specified by a static expression, and that expression shall be explicit, even if the aspect has a boolean type.
Identity shall be specified only on a function_specification declaration.
Reason: The part about requiring an explicit expression is to disallow omitting the value for this aspect, which would otherwise be allowed by the rules of 13.1.1.
Aspect Description for Identity: Identity value for a function.
The expected type for the expression specified for the Identity aspect is the result type of the function_specification declaration on which it appears.
Only one Identity aspect may be applied to a single function declaration;
Reducer
The aspect Reducer shall denote a reducer_function that is to be associated with a declared function.
Reducer The aspect Reducer denotes a function with the following specification:
function reducer(L, R : in result_type) return result_type
where result_type statically matches the subtype of the result of the declared function.
Only one Reducer aspect may be applied to a single function declaration;
Aspect Description for Reducer: Reducer function associated with the combiner_function_call of a reduction expression.
Dynamic Semantics
For the evaluation of a reduction_expression, the loop_parameter_specification or iterator_specification is first elaborated, and accumulator variables of the type of the reduction_expression are implicitly declared. Each accumulator variable corresponds to a unique non-overlapping subset of the iterations to be performed where all accumulators together cover the full set of iterations to be executed. For the accumulator dedicated to the first iterations, the accumulator is initialized to the value of the reduction_parameter of the combiner_expression, otherwise the accumulators are initialized to the associated identity_value of the combiner_expression.
The evaluation of a reduction_expression then evaluates the combiner_expression for the values of the loop parameter in the order specified by the loop_parameter_specification (see 5.5) or iterator_specification (see 5.5.2) within each iteration subset. For each subsequent evaluation of the combiner_expression within an iteration subset, the result from the previous evaluation is substitued as the reduction_parameter of the current evaluation.
The value of the reduction_expression is determined as follows: As accumulator results are determined they are reduced into a single result two at a time by implicit calls to the reducer_function associated with the combiner_expression. The accumulator results passed to the reducer_function are always for two adjacent iteration subsets where the result for the lower iteration subset is passed as the first actual parameter to the reducer_function and the result for the higher iteration subset is passed as the second actual parameter to the reducer_function. If the Reduction_Expression does not evaluate any iterations, then the value of the Reduction_Expression is the value of the specified reduction_parameter expression.
Notes: The accumulator results must represent adjacent iteration subsets as described above to ensure that non-commutative reductions will produce consistent results for parallel execution.
Examples
A reduction expression to calculate the sum of elements of an array of integers
(for Element of A => <0> + Element) -- See 4.3.3(43)
A reduction expression to calculate the minimum value of an array of integers
(for X of A => Integer'Min(<Integer'Last>, X))
A reduction expression to create a string containing the alphabet
(for Letter in 'A' .. 'Z' => <""> & Letter)
A reduction expression to determine how many integers in an array are greater than 3
Four_Or_More : contant Natural := (for P of A => <0> + (if P > 3 then 1 else 0));
An expression function that returns its result as a Reduction Expression
function Factorial(N : Natural) return Natural is (for J in 1..N => <1> * J);
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 => <0.0> + (-1.0)**I * X**(2*I-1)/Float(Fact(2*I-1)));
A reduction expression that outputs the sum of squares
Put_Line ("Sum of Squares is" & Integer'Image(for I in 1 .. 10 => <0> + I**2));
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 => <0.0> + (4.0 / (1.0 + ((Real (I) - 0.5) * (1.0 / Number_Of_Steps))**2))));
Wording Changes from Ada 2012 Reduction expressions are new.
Modify A.1 (9.1)
-- function "and" (Left, Right : Boolean'Base) return Boolean'Base {with Identity => True}; -- function "or" (Left, Right : Boolean'Base) return Boolean'Base {with Identity => False}; -- function "xor" (Left, Right : Boolean'Base) return Boolean'Base {with Identity => False};
Modify A.1 (17)
-- function "+" (Left, Right : Integer'Base) return Integer'Base {with Identity => 0}; -- function "-" (Left, Right : Integer'Base) return Integer'Base {with Reducer => "+"}; -- function "*" (Left, Right : Integer'Base) return Integer'Base {with Identity => 1}; -- function "/" (Left, Right : Integer'Base) return Integer'Base {with Reducer => "*"};
Modify A.1 (25)
-- function "+" (Left, Right : Float) return Float {with Identity => 0.0}; -- function "-" (Left, Right : Float) return Float {with Reducer => "+"}; -- function "*" (Left, Right : Float) return Float {with Identity => 1.0}; -- function "/" (Left, Right : Float) return Float {with Reducer => "*"};
Modify A.1 (29-34)
function "*" (Left : root_integer; Right : root_real)
return root_real {with Identity => 1.0};
function "*" (Left : root_real; Right : root_integer)
return root_real {with Identity => 1.0};
function "/" (Left : root_real; Right : root_integer)
return root_real {with Reducer => "*"};
-- The type universal_fixed is predefined. -- The only multiplying operators defined between -- fixed point types are
function "*" (Left : universal_fixed; Right : universal_fixed)
return universal_fixed {with Identity => 1.0};
function "/" (Left : universal_fixed; Right : universal_fixed)
return universal_fixed {with Reducer => "*"};
Modify A.4.4 (13-17)
function Append (Left, Right : in Bounded_String; Drop : in Truncation := Error) return Bounded_String{ with Reducer => "&"};
function Append (Left : in Bounded_String; Right : in String; Drop : in Truncation := Error) return Bounded_String{ with Reducer => "&"};
function Append (Left : in String; Right : in Bounded_String; Drop : in Truncation := Error) return Bounded_String{ with Reducer => "&"};
function Append (Left : in Bounded_String; Right : in Character; Drop : in Truncation := Error) return Bounded_String{ with Reducer => "&"};
function Append (Left : in Character; Right : in Bounded_String; Drop : in Truncation := Error) return Bounded_String{ with Reducer => "&"};
Modify A.4.4 (21-26)
function "&" (Left, Right : in Bounded_String)
return Bounded_String{ with Identity => Null_Bounded_String};
function "&" (Left : in Bounded_String; Right : in String)
return Bounded_String{ with Reducer => "&"};
function "&" (Left : in String; Right : in Bounded_String)
return Bounded_String{ with Reducer => "&"};
function "&" (Left : in Bounded_String; Right : in Character)
return Bounded_String{ with Reducer => "&"};
function "&" (Left : in Character; Right : in Bounded_String)
return Bounded_String{ with Reducer => "&"};
Modify A.4.5 (15-19)
function "&" (Left, Right : in Unbounded_String)
return Unbounded_String{ with Identity => Null_Unbounded_String};
function "&" (Left : in Unbounded_String; Right : in String)
return Unbounded_String{ with Reducer => "&"};
function "&" (Left : in String; Right : in Unbounded_String)
return Unbounded_String{ with Reducer => "&"};
function "&" (Left : in Unbounded_String; Right : in Character)
return Unbounded_String{ with Reducer => "&"};
function "&" (Left : in Character; Right : in Unbounded_String)
return Unbounded_String{ with Reducer => "&"};
Modify A.18.2 (15/2-18/.2)
function "&" (Left, Right : Vector) return Vector
{ with Identity => Empty_Vector};
function "&" (Left : Vector;
Right : Element_Type) return Vector
{ with Reducer => "&"};
function "&" (Left : Element_Type;
Right : Vector) return Vector
{ with Reducer => "&"};
function "&" (Left, Right : Element_Type) return Vector
{ with Reducer => "&"};
Add after A.18.3 (32/2)
function "&" (Left, Right : List) return List
{ with Identity => Empty_List};
function "&" (Left : List;
Right : Element_Type) return List
{ with Reducer => "&"};
function "&" (Left : Element_Type;
Right : List) return List
{ with Reducer => "&"};
function "&" (Left, Right : Element_Type) return List
{ with Reducer => "&"};
Modify A.18.7(55/2)
function Union (Left, Right : Set) return Set { with Identity => Empty_Set};
Modify A.18.7(67/2)
function Symmetric_Difference (Left, Right : Set) return Set {with Identity => Empty_Set};
Modify A.18.8(27/2)
function Union (Left, Right : Set) return Set { with Identity => Empty_Set};
Modify A.18.8(35/2)
function Symmetric_Difference (Left, Right : Set) return Set { with Identity => Empty_Set};
Modify A.18.9(28/2)
function Union (Left, Right : Set) return Set { with Identity => Empty_Set};
Modify A.18.9(37/2)
function Symmetric_Difference (Left, Right : Set) return Set { with Identity => Empty_Set};
!discussion
There is a continuing trend of exponential growth of computational elements embedded on a single chip. This has led to significant challenges for software designers and implementers. Prior to 2005, the increase in transistor count corresponded to a similar increase in CPU clock speed, which boosted performance of sequential algorithms. Since then, CPU clock speeds have leveled off for reasons of practicality, and chip manufacturers have instead moved towards multicore technologies as a means of achieving performance increases.
As parallel technologies become more prevalent in the form of new emerging hardware platforms, safety concerns need to consider the paradigm shift from sequential to parallel behaviour. It is a paradigm that has been for a long time contained within a specialized domain of high-performance computing, but that is now required in all domains of computing systems.
This proposed model does not define syntax for the explicit parallelization of reduction expressions, since such parallelization can be performed implicitly by the compiler, when it knows that the expression is free of side-effects. This is facilitated by annotations identifying global variable usage on subprogram specifications (see AI12-0079-1).
A reduction expression provides a concise way to use iteration to combine a set of values into a single result.
We already have some special purpose reduction expressions in Ada in the form of quantified expressions and array aggregates of the form using an iterated_component_association.
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 the more generalized Reduction expression syntax.
All_Graduated : constant Boolean := (for Student of Class => <True> and Passed_Exam (Student));
Someone_Graduated : constant Boolean := (for Student of Class => <False> or Passed_Exam (Student));
Here we use "and" and "or" as the combiner_expression of the Reduction expression. The initial value plays an important role, since the Identity for "and" must be true, and false for "or".
Another concern might be whether parallel loops can generally be written as expressions.
Consider the calculation of Pi:
function Pi (Number_Of_Steps : Natural := 100_000) return Long_Float is (1.0 / Number_Of_Steps * (parallel for I in 1 .. Number_Of_Steps => <0.0> + (4.0 / (1.0 + ((Long_Float (I) - 0.5) * 1.0 / Number_Of_Steps)**2))));
One might feel that the readability of this example might be improved if temporary variable declarations were to be added for intermediate results. For instanced, it might be nice to replace the sub-expression;
(1 + ((Long_Float (I) - 0.5) * Step)**2)
with
(1.0 + X**2)
and
1.0 / Number_Of_Steps
with
Step
One ordinarily cannot declare variables in an expression, but one can always write a function which can be called from an expression.
We might instead decide to write:
function Pi (Number_Of_Steps : Natural := 100_000) return Long_Float is Step : constant Long_Float := 1.0 / Number_Of_Steps;
function Pi_Slicer (R : Long_Float; Index : Natural) return Float with Reducer => "+" is X : constant Long_Float := (Long_Float (Index) - 0.5) * Step; begin return R + 4.0 / (1.0 + X ** 2); end Pi_Slicer;
begin Pi : constant Long_Float := Step * (for I in 1 .. Number_Of_Steps => Pi_Slicer (<0.0>, I)); end Pi;
Which leaves a simpler looking Reduction Expression to do computation.
Another concern might be about the need to perform multiple reductions at the same time.
Consider:
Sum : Integer := (for X of Arr => <0> + X); Min : Integer := (for X of Arr => Integer'Min(<Integer'Last>, X)); Max : Integer := (for X of Arr => Integer'Max(<Integer'First>, X));
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 Identity => Identity is (Summary'(Sum => L + R, Min => Integer'Min (L, R), Max => Integer'Max (L, R)));
-- Combiner function for the Reduction expression function Process (L : Summary; X : Integer) return Summary with Reducer => Reduce is (Summary'(Sum => L.Sum + X, Min => Integer'Min (L.Min, X), Max => Integer'Max (L.Max, X)));
-- Reduction expression to compute all 3 results at once Result : constant Summary := (for X of Arr => Process (<Identity>, X));
!ASIS
** TBD.
!ACATS test
ACATS B-Test and C-Test are needed for these features.
!appendix

From: Brad Moore
Sent: Thursday, December 28, 2017 3:05 PM

Here is another chunk of my homework.

This is the new AI on Reduction Expressions which was split off from
AI12-0119-1. [This is version /01 of the AI. For previous discussion, see the
!appendix of AI12-0119-1, and versions /01 through /04 of that AI. - ED.]

I don't yet have a number for this AI, I presume Randy will work his magic and
assign a number.

The main differences in this version are that the reduction parameter (the
expression enclosed by angle brackets) is now mandatory. The parallel keyword
has been removed, as it is assumed the implementation will make the decision
whether to execute in parallel or sequentially. The Identity and Reducer aspects
are not mandatory for a reduction expression. If they are missing, the
implementation will choose sequential execution.

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

From: Randy Brukardt
Sent: Friday, December 29, 2017  1:07 AM

...
> The main differences in this version are that the reduction parameter
> (the expression enclosed by angle brackets) is now mandatory.

Haven't we yet come up with acceptable syntax for these things? Angle brackets
are not an acceptable syntax for a language like Ada. Even if they can be
unambiguously parsed (which I seriously doubt), they would be very confusing for
readers. (And especially for syntax error correctors.)

I'm interested in the proposed feature, but it has to have an acceptable syntax.
And to this point, it doesn't. If the syntax does not become acceptable soon,
then I will start having to oppose the entire feature (we're better off without
a feature than permanently damaging the Ada syntax).

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

From: Brad Moore
Sent: Friday, December 29, 2017 12:17 PM

The last time we discussed this was in Vienna.

At that time, we had narrowed it down to the set of choices;

(1)  <<  >> <<>>
(2)  <  >   <>
(3)  [  ]   []
(4)  {  }   {}

The results of the straw poll were:

Straw poll: Love-Hate-Neutral on the options given above
(1) 7-2-2
(2) 6-2-3
(3) 0-8-3
(4) 4-6-1

The straw poll favored 2 slightly over 1. (6 votes vs 5) Options 3 and 4 were
ruled out.

Though the meeting minutes say a choice was not made, it seemed clear that there
was a lot of love for angle brackets, since the two choices that survived both
had them.

I left it as single angle brackets, as it had the slight edge over double angle
brackets. I presumed people would otherwise be happy enough with either of those
two choices.

Presumably you were one of the 2 haters.

One thing I did in this version of the AI, that I now realize I need to undo is
that I changed the reduction_parameter syntax from a simple_expression to an
expression, as I was worried that it would disallow boolean expressions. I see
now from the Vienna meeting minutes that it was a simple expression, because
then it would force boolean expressions to be parenthesized, which eliminates
some ambiguity.

   eg < a > b >

would need to be:

  < (a > b) >

Does that help? Maybe we should say that it is a primary instead of a simple
expression, then in most cases it would need to be parenthesized.

Otherwise, does anyone have any better suggestions?

Any favourites out of these?

1. Sum := (for I of A => <0> + I);
2. Sum := (for I of A => use(0) + I);
3. Sum := (for I of A => with(0) + I);
4. Sum := (for I of A => $0 + I);
5. Sum := (for I of A => %0 + I);
6. Sum := (for I of A => :0: + I);
7. Sum := (for I of A => 0? + I);

Of these, I think I like 4 (followed by 5) as good if not better than 1.
$name is commonly used in scripting languages to indicate a parameter
substitution, so it might strike familiarity with a lot of users.

I tried searching for $ in the RM, I didn't find anything. Maybe adding $ to the
RM will increase Ada's fortunes. ;-)

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

From: Edmond Schonberg
Sent: Friday, December 29, 2017 12:35 PM

> Haven't we yet come up with acceptable syntax for these things? Angle
> brackets are not an acceptable syntax for a language like Ada. Even if
> they can be unambiguously parsed (which I seriously doubt), they would
> be very confusing for readers. (And especially for syntax error
> correctors.)
>
> I'm interested in the proposed feature, but it has to have an
> acceptable syntax. And to this point, it doesn't. If the syntax does
> not become acceptable soon, then I will start having to oppose the
> entire feature (we're better off without a feature than permanently
> damaging the Ada syntax).

This seems like an aesthetic argument: why is <init> unacceptable for Ada? There
is certainly no parsing problems with this syntax ( at least none in the
prototype developed in GNAT). The proposed syntax is compact and readable, so I
don’t understand your objection to the current proposal.

(on the other hand, its usage to build aggregates instead of
iterated_component_associations it harder to implement efficiently, and it seems
like a stretch to say that a Reduction produces a “bigger" value than its
operands).

Concerning the text of the AI, I think it would be simpler if the motivation for
it were not related to potential parallelism. A reduction operation is
interesting in its own right, and implementation in terms of (and interaction
with) tasklets should be presented elsewhere, in connection with other
parallelizable constructs.

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

From: Jeff Cousins
Sent: Friday, December 29, 2017 12:38 PM

Tuck previously said that Ed had implemented a form of reduction expressions -
what syntax does that use?

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

From: Brad Moore
Sent: Friday, December 29, 2017 1:38 PM

> Concerning the text of the AI, I think it would be simpler if the
> motivation for it were not related to potential parallelism. A
> reduction operation is interesting in its own right, and
> implementation in terms of (and interaction with)  tasklets should be
> presented elsewhere, in connection with other parallelizable
> constructs.

I agree that parallelism is only a subset of the potential usage. I had that in
mind when writing the motivation text, but could have gone further to
deemphasize the parallelism angle, even though parallel reduction was the
problem we were trying to solve when this solution presented itself. I think it
is worth at least noting though that the syntax can be parallelized, as that is
a common, if not one of the main problems that other parallization languages,
e.g. OpenMP and Cilk, deal with. And that is intended to be the Ada solution to
that problem, even if implementations choose to not support it.

But since the parallelism is implicit, and implementation advice, and that there
can be a lot of uses where parallelism isn't even needed, the motivation should
focus more on the non-parallelism benefits.

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

From: Tucker Taft
Sent: Friday, December 29, 2017 6:04 PM

> Haven't we yet come up with acceptable syntax for these things? Angle
> brackets are not an acceptable syntax for a language like Ada. Even if
> they can be unambiguously parsed (which I seriously doubt), they would
> be very confusing for readers. (And especially for syntax error
> correctors.)
>
> I'm interested in the proposed feature, but it has to have an
> acceptable syntax. And to this point, it doesn't. If the syntax does
> not become acceptable soon, then I will start having to oppose the
> entire feature (we're better off without a feature than permanently
> damaging the Ada syntax).

So long as the angle brackets are never empty, they are distinct from any other
use of angle brackets, and since they are effectively in the "unary" context
rather than the "binary" context, they are easy to distinguish from
less-than/greater-than.

Ed Schonberg implemented these with no problem, and so we can review a bunch of
examples that work to see what we think.

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

From: Randy Brukardt
Sent: Friday, December 29, 2017  6:36 PM

> So long as the angle brackets are never empty, they are distinct from
> any other use of angle brackets, and since they are effectively in the
> "unary" context rather than the "binary" context, they are easy to
> distinguish from less-than/greater-than.

Perhaps in your world of "easy", but I'm dubious that it is going to work well
in the context of a table-driven parser. And particularly in terms of error
correction: the handling of binary operators and of bracketing tokens
(particularly closing brackets) is wildly different, and the context of an
expression is the same for both.

> Ed Schonberg implemented these with no problem, and so we can review a
> bunch of examples that work to see what we think.

Having looked at Brad's suggestions, I am beginning to realize that my objection
is really to the actual concept and not so much toward are particular syntax.
Whatever syntax is adopted, it will only be usable in this one particular case
(initialization of reduction expressions), since it appears in the middle of an
unrestricted expression. Much like we couldn't reuse <> for assignment because
it was already used, the same thing will occur for whatever syntax we adopt
here. (While one probably won't see reduction expressions as the default
parameter of a subprogram or the like, the possibility will exist.) As such,
this elevates this syntax all out of proportion to its actual use (fairly rare),
as it affects every expression that could possibly be written.

Unless you think 20% of new Ada programs will be reduction expressions (I don't
:-), it would be better to find a syntax that doesn't require inserting some new
thingy into every kind of expression that could ever occur. And if there is no
sane way to avoid that, then we at least need to avoid using a syntax that looks
to have a general use for a very specialized one-time usage.

For instance, I'd rather use <> or @@ to mark the location, and put the actual
expression somewhere else. (But I'd rather avoid having to mark the location at
all.)

I don't want to see angle brackets in Ada at all, but if we were going to have
them, I'd rather see them used in a general feature (say, some sort of pattern
matching) than a one-time use in a rare kind of expression. Let's find some
alternative to messing around with expressions. Please.

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

From: Brad Moore
Sent: Sunday, December 31, 2017 3:14 PM

> For instance, I'd rather use <> or @@ to mark the location, and put
> the actual expression somewhere else. (But I'd rather avoid having to
> mark the location at all.)

This is actually what I was originally thinking of a while back, where the <>
would always be used, and initialized by the Identity_Value aspect associated
with the reduction expression.

I never quite saw why we were so insistent on having the initial value inside
the angle brackets, because if one wants to use a value other than the
Identify_Value, that can easily enough be added to the expression outside the
reduction expression.

eg.

   Sum :=  5 + (for I in 1 .. 10 => <> + I);

Seems as easy to write as;

   Sum := (for I in 1 .. 10 => <5> + I);

And maybe more easier to understand for the reader as well.

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

From: Bob Duff
Sent: Sunday, December 31, 2017 4:44 PM

> And maybe more easier to understand for the reader as well.

I tend to agree.

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

From: Tucker Taft
Sent: Sunday, December 31, 2017 5:48 PM

> Tuck previously said that Ed had implemented a form of reduction expressions - what syntax does that use?

Single angle brackets.

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

From: Brad Moore
Sent: Monday, January 1, 2018 12:10 PM

> Seems as easy to write as;
>
>   Sum := (for I in 1 .. 10 => <5> + I);
>
> And maybe more easier to understand for the reader as well.

I recall now the reason we went the way we did was because we were looking to
disambiguate the syntax more, as we were worried about confusion with the new
array aggregate syntax. (See 4.3.3 (5.1/5))

However, in my view, I see aggregate syntax as just another specialised form of
reduction expression, just as quantified expressions can be viewed as a
specialised form of reduction expression.

For array aggregate syntax, the combiner_function can be considered to be
concatenation.

for example the array aggregate;

A : constant Integer_Array := (for I in 1 .. 10 => I);

can be viewed as a shorthand for the reduction expression;

A : constant Integer_Array := (for I in 1 .. 10 => <> & I);

The concatenation can be optimized by the implementation to be an 'in-place'
form of concatenation, where each element as it is composed is stored in the
result, rather than building a temporary array and assigning that temporary to
the result.

The confusion might come when one tries to mix aggregates with box notation into
this, but I think aggregate syntax is the disambiguator. In the AI there is a
rule that says that only one reduction parameter (i.e. box) can appear in a
reduction expression, but we could clarify that a box that appears inside
something like a record_component_association for a record aggregate, is not a
reduction parameter.

eg.

B : constant Record_Array := (for I in 1 .. 10 => <> & My_Record'(X => I, Y => <>));

The first Box is a reduction parameter, the second one isn't, as it is a
record_component_association.

One would ordinarily write this using the Array aggregate shorthand anyways,

B : constant Record_Array := (for I in 1 .. 10 => My_Record'(X => I, Y => <>));


So I still think that using <> syntax for the reduction parameter would work.

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

From: Edmond Schonberg
Sent: Tuesday, January 2, 2018  8:05 AM

...
> One would ordinarily write this using the Array aggregate shorthand
> anyways,
>
> B : constant Record_Array := (for I in 1 .. 10 => My_Record'(X => I, Y
> => <>));
>
>
> So I still think that using <> syntax for the reduction parameter would work.

I agree, this works, and reuses the meaning of the box in a non-confusing way. I
also agree that being able to specify a different default in the expression is
very little gain for new syntax.  Using the box does require a new aspect for
functions and operators however.

Tucker (private communication :-)) indicated that at the previous ARG meeting
the <init> form was also allowed to appear WITHIN any of the arguments of the
combiner function, which cannot be done with the box alone.  The rule you
propose would prevent the nested usage, which is fine by me!

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

From: Jeff Cousins
Sent: Tuesday, January 2, 2018  10:26 AM

Just some typos (and a query):

!proposal 2nd para
; -> :
Easy -> easy

Add AARM note:
eg. -> e.g.

Static Semantics 2nd para
nees -> needs

Dynamic Semantics 2nd para
substitued -> substituted

Examples – what’s the name of this formula for Pi?

Add after A.18.3 (32/2)
As this is an add not a modify, {} not needed.

!discussion 12th (?) para
instanced -> instance
; -> :
1 -> 1.0

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

From: Tucker Taft
Sent: Tuesday, January 2, 2018  12:27 PM

>> So I still think that using <> syntax for the reduction parameter would work.
>
> I agree, this works, and reuses the meaning of the box in a
> non-confusing way. I also agree that being able to specify a different
> default in the expression is very little gain for new syntax.  Using the box does require a new aspect for functions and operators however.

And this presumes that you always start with the same initial value.  For string
concatenation, for example, it is quite reasonable to have something other than
"" as the initial string.  I have also had examples for counting, max/min, etc.,
where the initial value varies according to context.  Finally you are separating
the specification of the initial value from the point of usage, which could make
it that much harder to understand the code.

> Tucker (private communication :-)) indicated that at the previous ARG
> meeting the <init> form was also allowed to appear WITHIN any of the
> arguments of the combiner function, which cannot be done with the box alone.  The rule you propose would prevent the nested usage, which is fine by me!

I don't think we should start by using a syntax that implies unnecessary
restrictions.  We could impose arbitrary restrictions that we might later relax,
but if the syntax makes that impossible, that is very unwise in my view.

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

From: Brad Moore
Sent: Wednesday, January 3, 2018 12:02 AM

> And this presumes that you always start with the same initial value.
> For string concatenation, for example, it is quite reasonable to have
> something other than "" as the initial string.  I have also had
> examples for counting, max/min, etc., where the initial value varies
> according to context.  Finally you are separating the specification of
> the initial value from the point of usage, which could make it that much harder to understand the code.

I'm afraid I am not understanding this comment.

For string concatenation, why not use whichever initial string you want outside
of the expression?

eg.

   Message : constant String := "Alphabet:" & (for Letter in 'A' .. 'Z' => <> & Letter);

Which I think would be easier to understand than

   Message : constant String := (for Letter in 'A' .. 'Z' => <"Alphabet:"> & Letter);

for those not familiar with the syntax. Its clearer in the first case that
"Alphabet:" will be the first part of the result.

Similarly,

   Sum : constant Integer := 5 + (for I in 1 .. 10 => <> + A(I));

Seems easier to read and understand to me than;

   Sum : constant Integer := (for I in 1 .. 10 => <5> + A(I));


   Sales_Price : constant Integer := Integer'Max(100, (for Bid of Offers => Integer'Max(<>, Bid)));

   Sales_Price : constant Integer := (for Bid of Offers => Integer'Max(<100>, Bid));

  Here I think one could argue either way, but maybe the second is preferable
  since it is shorter.

Maybe we need to see more examples, but of the examples we have currently, most
(in fact I think all) dont even have an initial value, other than the
Identity_Value.

For something that appears as though it would be uncommonly used in a majority
of cases, I wonder if is it worth adding special syntax when existing familiar
syntax can be used to express the same thing?

>> Tucker (private communication :-)) indicated that at the previous ARG
>> meeting the <init> form was also allowed to appear WITHIN any of the
>> arguments of the combiner function, which cannot be done with the box
>> alone.  The rule you propose would prevent the nested usage, which is
>> fine by me!

I am not sure I am understanding this limitation. Could someone (Tucker, Ed)
show an example of what the previous syntax would allow, but the current one
wouldn't?

It would also help if this example were a practical one.

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

From: Tucker Taft
Sent: Wednesday, January 3, 2018  9:17 AM

I really thinks it creates an unnecessary burden to require that every operation
you want to use as the "primary" operation of the reduction expression has to
have an appropriate aspect specified.  Suppose you find this nice package that
has the operation you want to use?  Do you have to create a private copy to
specify the aspect.  Furthermore, there are operations where there may not be
any obvious "identity," and so the reader will have to  guess what it might be.
Putting it explicitly in the reduction expression reduces the cognitive overhead
of using the feature.

...
>> And this presumes that you always start with the same initial value.
>> For string concatenation, for example, it is quite reasonable to have
>> something other than "" as the initial string.  I have also had
>> examples for counting, max/min, etc., where the initial value varies
>> according to context.  Finally you are separating the specification
>> of the initial value from the point of usage, which could make it that much harder to understand the code.
>
> I'm afraid I am not understanding this comment.
>
> For string concatenation, why not use whichever initial string you want
> outside of the expression?

Seems like an unnecessary extra concatenation.  Not such a big burden for string
concatenation, but could be expensive in other cases, such as, say, merging a
series of maps.

> eg.
>
>   Message : constant String := "Alphabet:" & (for Letter in 'A' .. 'Z'
> => <> & Letter);
>
> Which I think would be easier to understand than
>
>   Message : constant String := (for Letter in 'A' .. 'Z' =>
> <"Alphabet:"> & Letter);
>
> for those not familiar with the syntax ...

If someone is not familiar with the syntax, I think it would be at least as hard
to guess what "<> & blah" means.

To me, it is more reasonable to expect that the reader is familiar with the
general syntax than with all of the details of the particular operation being
used to do the reduction.  That is a reason why having to go to the declaration
of the operation to learn what is the initial value seems unwise.

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

From: Randy Brukardt
Sent: Wednesday, January 3, 2018  7:43 PM

>  Putting it explicitly in the reduction expression reduces the
> cognitive overhead of using the feature.

It's precisely that cognitive overhead that worries me. This expression and its
special syntax can appear absolutely anywhere, associated with any kind of
expression. But it is likely to be very rare in Ada code -- and there is nothing
about the expression or its syntax that intuitively explains what it does. (I
still barely understand that.) Outside of parallel execution, I don't see much
to recommend anyone writing in this style, yet we're for some reason encouraging
everyone to do so even for things that can't reasonably be parallelized
(built-in-place function calls come to mind).

Perhaps I'm reaching the too-fossilized-to-be-open-to-new-things stage, but I
don't want to see these things in any code that I have to read or maintain.
Which makes me wonder why we want them in any Ada code (I doubt very much that
I'm alone in this feeling).

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

From: Tucker Taft
Sent: Wednesday, January 3, 2018  8:48 PM

My experience in a language that supports this is that it is used quite
frequently.  Of course it will take some time to get used to any new notation.
The ultimate goal would be that once you are used to it, you should be able to
see what you need to see without having to jump back and forth from the code to
various aspect specifications.

Below are various examples from some "real" programs written in ParaSail (e.g. a
compiler to LLVM and a static analysis tool).  I prefaced each example with a
block of comments to try to explain what it is doing.

--------------

--  Count the number of formal-params that are output parameters
-- The "{...}" is a filter that controls whether any action is taken
-- for a particular item in the container
--  (equivalent to the "when X =>")
const Num_Outputs :=
                      (for each P of Formal_Params
                        {P.Is_Operation_Output} => <0> + 1)


--  Create a bracketed list of the elements of DF.
--  Note that ParaSail allows two iterators that iterate together,
--  stopping when either reaches its end.
--  So in the case, we are iterating over the elements of "DF" while
--  also doing a simple "X := Y then Z"
--  iterator which sets X to Y initially and then sets it to Z on each
--  subsequent iteration.
const DF_Image :=
  (for (F in DF; Sep := "" then ", ") => <"["> | Sep | F) | "]"


--  This produces a string representation of a sequence of ranges
--  separated by spaces
return (for R in Rngs forward =>
   <"Countable::["> | R.First | ".." | R.Last | " ") | "]"


--  This prints out a bracketed, comma-separated string representation
--  of the inputs
--  It again uses two iterators being iterated together
Println((for (each Input of Inputs forward;
                    Sep := "" then ", ") =>
                 <"["> | Sep | "VN" | Input) | "]")


--  This counts the number of parameters that are outputs or variables
--  with the filter in "{...}" again
(for each P of Params
 {P.Is_Operation_Output or else P.Is_Var} => <0> + 1)


--  This determine the minimum index of a set of parameters that pass
--  the filter (i.e. are either outputs or variables).
--  Rather than using the most positive and most negative values as the
--  "identity" for Min and Max, in Parasail, null is used, meaning both
--  Min(null, X) = X and Max(null, X) = X
const First_Updated :=
  (for each [I => P] of Params
    {P.Is_Operation_Output or else P.Is_Var} => Min(<null>, I))


-- Count the number of non-inputs
const Num_Inputs :=
  (for each P of Params {not P.Is_Operation_Output} => <0> + 1)


--  Print the list of VNs in VNs_To_Prop
Println(
  (for VN in VNs_To_Prop forward => <"Recursive_Top_Down"> | " VN" | VN))


--  Create a set of the parent value numbers (VNs) of the VNs in
--  Changed_Operands
const Parents : VN_Set :=
   (for Opnd in Changed_Operands =>
     <[]> | Op_Ctx.VN_To_Parent_Set_Map[Opnd])


--  Print a list of [VNx => VNy] pairs representing the live-out set
Println(
  (for each [Loc => VN] of Live_Out_Set =>
    <" Live_Out_Set ="> | " [VN" | Loc | "=>VN" | VN | "]"))


--  Count the number of nodes that are found by following the
--  Parent chain.
--  This uses the general "X := Y then Z while W" iterator which
--  initializes X to Y, and then sets it to Z on each subsequent
--  iteration, as long as "W" remains true.
return (for N := Node_Id then Node_Tree.Parent[N]
           while N in Node_Tree.Parent => <0> + 1)


--  "{...}" by itself is an assertion
--  This asserts that the sum of the sizes in Bit_Field_Sizes should be <= 63
{(for each Size of Bit_Field_Sizes => <0> + |Size|) <= 63}


--  Build up an array mapping from Bit-Field Key to the
--  sum of the sizes of all bit-fields preceding this bitfield
const Bit_Field_Offsets : Array<Univ_Integer, Indexed_By => Key_Type> :=
  [for each [Key => Size] of Bit_Field_Sizes, Key =>
     (for K in Key_Type::First() .. Key-1 => <0> + Bit_Field_Sizes[K])]


--  Dump the sizes of the bit fields
Println(
  (for (each [Key => Size] of Bit_Field_Sizes; Sep := "" then ", ")
    forward => <"Bit_Field_Sizes:["> | Sep | Key | " => " | Size) | "]")


--  Hash the characters of a string to produce an integer
func Hash_Vec(Vec : Vector<Univ_Character>) -> Univ_Integer is
 return (for I in 1 .. |Vec| reverse =>
   (<0> * 127 + (Vec[I] - Char_First)) mod Hash_Modulus)
end func Hash_Vec

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

From: Randy Brukardt
Sent: Wednesday, January 3, 2018  10:54 PM

> Below are various examples from some "real" programs written in
> ParaSail (e.g. a compiler to LLVM and a static analysis tool).  I
> prefaced each example with a block of comments to try to explain what
> it is doing.

Having looked over the examples, I'm now even more certain that I don't want
this notation in the language. Ada is not a functional language, but this
feature can only be used functionally. Ada expressions are too large as it is,
and this feature seems mainly about writing large, clever expressions that you
need to analyze for hours to understand. Bah-humbug. (Staying in the season. ;-)

We've probably gone too far already in allowing stuff in expressions, and if we
really need to do this to support parallelism in Ada, then it's time to admit
that Ada is the wrong foundation and start over with a functional design.
Grafting on some functional features because some people find them clever is the
wrong direction.

Anyway, let's look at one of these examples in detail:

> --  Count the number of formal-params that are output parameters
> -- The "{...}" is a filter that controls whether any action is taken
> -- for a particular item in the container
> --  (equivalent to the "when X =>")
> const Num_Outputs :=
>                       (for each P of Formal_Params
>                         {P.Is_Operation_Output} => <0> + 1)

So, how would one do this in Ada 2012? Probably I would write (assuming that
Formal_Params has an appropriate container iterator):

    declare
       Num_Outputs : Natural := 0;
    begin
       for P of Formal_Params loop
           if P.Is_Operation_Output then
               Num_Outputs := Num_Outputs + 1;
           end if;
       end loop;
       ... -- Use Num_Outputs.
    end;

The only real loss here is the inability to use "constant". That's hardly worth
a new construct. I write this sort of code all of the time, and probably so does
every other Ada programmer. This takes more lines, but that's mainly because of
the conventional Ada formatting. One could get rid of two lines with a trick
(which I don't recommend, BTW):

      Num_Outputs := @ + Boolean'Pos (P.Is_Operation_Output);

or a junky conditional expression:

      Num_Outputs := @ + (if P.Is_Operation_Output then 1 else 0);

It strikes me that the right way to do this in Ada if one is insisting on an
expression format is to directly write it (using the proposed block expression
and an expression assignment):

     Num_Outputs : constant Natural :=
        (declare
            Accum : Natural := 0;
         begin
            (for P of Formal_Params => (if P.Is_Operation_Output then Accum := @ + 1; Accum else Accum)));

The main problem with this is that the quantified expression tends to muddle the
readability of the loop portion (also a problem with your proposal) -- as they
are virtually identical but have rather different semantics.

In any case, the more I see of this the less I like it.

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

From: Brad Moore
Sent: Thursday, January 4, 2018  1:41 AM

I have an idea that gets rid of the <> entirely, and also gets rid of the need
to specify aspects. I think this also reads better and quite a bit more
understandable. Basically, the idea is to move both the combiner function and
the initial value out of the expression, so the expression just provides a list
of values.

e.g.
Instead of:

   Sum := (for I in 1 .. 10 => <5> + I);


You'd write:

   Sum := (5 + (for I in 1 .. 10 => I));


The expression function generates a list of values, and the combiner function
"+" applies all these values to the other argument which is the initial value.
You can basically read this as we are adding a bunch of values to 5.

You would need two sets of parens normally, one set around the for loop
generator, and another around the whole expression including the combiner and
initial value.

I have applied this syntax idea to all the example in the AI, plus most of the
examples that Tuck provided, after converting them to Ada from Parasail, and I
find every single one of them easier to read and understand using this syntax.

I feel the level of cognitive processing is significantly lower. When I compare
to back and forth between the two syntaxes for any of these examples, I feel the
"head explode" needle jump when I look at the ones with <> syntax. Not enough to
cause an explosion, thank goodness, but I do feel the needle jump, when I turn
the sensitivity knob up....

Here are the examples.

Sum : constant Integer := (for all I in 1 .. 10 => <0> + I);

Sum : constant Integer := (0 + (for I in 1 .. 10 => I));

Sales_Price : constant Integer := (for I in I .. 10 => Integer'Min(<5>, I)); Sales_Price : constant Integer := Integer'Min(5, (for I in I .. 10 => I));

Message : constant String :=  (for Letter in 'A' .. 'Z' => <"Alphabet: "> & Letter) Message : constant String := ("Alphabet: " & (for Letter in 'A' .. 'Z' => Letter));

Four_Or_More : constant Natural := (for P of A => <0> + (if P > 3 then 1 else 0)); Four_Or_More : constant Natural := (0 + (for P of A => (if P > 3 then 1 else 0)));

function Factorial(N : Natural) return Natural is (for J in 1..N => <1> * J); function Factorial(N : Natural) return Natural is (1 * (for J in 1..N => J));

function Sin(X : Float; Num_Terms : Positive := 5) return Float is
  (for I in 1..Num_Terms => <0.0> + (-1.0)**I * X**(2*I-1)/Float(Fact(2*I-1)));

function Sin(X : Float; Num_Terms : Positive := 5) return Float is
  (0.0 + (for I in 1..Num_Terms => (-1.0)**I * X**(2*I-1)/Float(Fact(2*I-1))));

Put_Line ("Sum of Squares is" & Integer'Image(for I in 1 .. 10 => <0> + I**2)); Put_Line ("Sum of Squares is" & Integer'Image(0 + (for I in 1 .. 10 => I**2)));

function Pi (Number_Of_Steps : Natural := 10_000) return Real is
   (1.0 / Number_Of_Steps *
     (for I in 1 .. Number_Of_Steps =>
        <0.0> + (4.0 / (1.0 + ((Real (I) - 0.5) * (1.0 / Number_Of_Steps))**2))));

function Pi (Number_Of_Steps : Natural := 10_000) return Real is
   (1.0 / Number_Of_Steps *
     (0.0 + (for I in 1 .. Number_Of_Steps =>
             (4.0 / (1.0 + ((Real (I) - 0.5) * (1.0 / Number_Of_Steps))**2)))));


--  Count the number of formal-params that are output parameters

Num_Outputs : constant Integer:=
    (for P of Formal_Params => <0> + (if P.Is_Operation_Output then 1 else 0))

Num_Outputs : constant Integer :=
    (0 + (for P of Formal_Params => (if P.Is_Operation_Output then 1 else 0)));

--  Create a bracketed list of the elements of DF.

X : constant DF_Image :=
  (for F in DF => <"["> & (if F = DF.First then "" else ", ") & F) & "]";

X : constant DF_Image :=
  ("[" & (for F in DF => (if F = DF.First then "" else ", ") & F)) & "]";

--  This produces a string representation of a sequence of ranges
--  separated by spaces

return (for R in Rngs => <"Countable::["> & R.First & ".." & R.Last & " ") & "]";

return ("Countable::[" & (for R in Rngs => R.First & ".." & R.Last & " ")) & "]";


--  This prints out a bracketed, comma-separated string representation of the inputs

Put_Line((for Inp of Inputs => <"["> & (if Inp = Inputs'First then "" else ", ") & "VN" & Inp) & "]");

Put_Line(("[" & (for Inp of Inputs => (if Inp = Inputs'First then "" else ", ") & "VN" & Inp)) & "]");


--  This counts the number of parameters that are outputs or variables

(for P of Params => <0> + (if P.Is_Operation_Output or else P.Is_Var then 1 else 0))

(0 + (for P of Params => (if P.Is_Operation_Output or else P.Is_Var then 1 else 0)))

--  This determine the minimum index of a set of parameters that pass
--  the filter (i.e. are either outputs or variables).

First_Updated : constant Integer :=
  (for P of Params =>
    Integer'Min(<Integer'Last>, (if P.Is_Operation_Output or else P.Is_Var then P.I else Integer'Last)));

First_Updated : constant Integer :=
   Integer'Min(Integer'Last,
               (for P of Params =>
                  (if P.Is_Operation_Output or else P.Is_Var then P.I else Integer'Last)));

-- Count the number of non-inputs

Num_Inputs : constant Integer :=
  (for P of Params => <0> + (if not P.Is_Operation_Output then 1 else 0));

Num_Inputs : constant Integer :=
  (0 + (for P of Params => (if not P.Is_Operation_Output then 1 else 0)));

--  Print the list of VNs in VNs_To_Prop

Put_Line((for VN in VNs_To_Prop => <"Recursive_Top_Down"> & " VN" & VN));

Put_Line("Recursive_Top_Down" & (for VN in VNs_To_Prop => " VN" & VN));


--  Create a set of the parent value numbers (VNs) of the VNs in
--  Changed_Operands

Parents : constant VN_Set :=
   (for Opnd in Changed_Operands => <Op_Ctx.Empty_Set> & Op_Ctx.VN_To_Parent_Set_Map(Opnd));

Parents : constant VN_Set :=
   (Op_Ctx.Empty_Set & (for Opnd in Changed_Operands => Op_Ctx.VN_To_Parent_Set_Map(Opnd)));

--  Print a list of [VNx => VNy] pairs representing the live-out set

Put_Line(
  (for Loc of Live_Out_Set =>
      <" Live_Out_Set ="> & " [VN" & Loc & "=>VN" & Loc.VN & "]"));

Put_Line(
  (" Live_Out_Set =" &
     (for Loc of Live_Out_Set => " [VN" & Loc & "=>VN" & Loc.VN & "]")));


--  Count the number of nodes that are found by following the
--  Parent chain.

return (for N in Node_Tree.Parent_Iterate(Node_Id) => <0> + 1)

return (0 + (for N in Node_Tree.Parent_Iterate(Node_Id) => 1));


--  This asserts that the sum of the sizes in Bit_Field_Sizes should be <= 63

Assert((for Size of Bit_Field_Sizes => <0> + Size) <= 63);

Assert((0 + (for Size of Bit_Field_Sizes => Size)) <= 63);


Note, I see now what Ed and Tuck meant by nesting the <> inside the expression.
Tuck's last example has this.

--  Hash the characters of a string to produce an integer func Hash_Vec(Vec : Vector<Univ_Character>) -> Univ_Integer is  return (for I in 1 .. |Vec| reverse =>
   (<0> * 127 + (Vec[I] - Char_First)) mod Hash_Modulus) end func Hash_Vec


I don't believe this can be expressed using the syntax I am proposing either.
On the other hand, this was quite difficult to understand, and I agree with Ed,
I'd be completely fine with not allowing such functions to be written with
expression functions. This causes the head explode needle to move dangerously
close to the big bang!

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

From: Brad Moore
Sent: Thursday, January 4, 2018  1:48 AM

...
> We've probably gone too far already in allowing stuff in expressions,
> and if we really need to do this to support parallelism in Ada, then
> it's time to admit that Ada is the wrong foundation and start over
> with a functional design. Grafting on some functional features because
> some people find them clever is the wrong direction.

I'd be interested in hearing your take on the suggestion in my last email. After
eliminating the <> altogether, as well as the need for aspects, and pulling the
combiner and initial value out of the syntax, I think it helps quite a bit
towards looking more Ada like.

Quantified expressions and Array aggregates are pretty much reduction
expressions that we already have in the language, and quantified expressions are
particularly useful for contracts. I think reduction expressions will also be
useful in this area, as well as supporting parallelism.

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

From: Tucker Taft
Sent: Thursday, January 4, 2018  7:53 AM

Your suggestion is interesting, but it seems pretty ambiguous right now.  What
distinguishes these nested iterators from an array (or container) aggregate with
an iterated component association?

Also, didn't we agree to add the "when" clause to all iterators at the last ARG
meeting?

See below for a couple of other comments.

...
>> We've probably gone too far already in allowing stuff in expressions,
>> and if we really need to do this to support parallelism in Ada, then
>> it's time to admit that Ada is the wrong foundation and start over
>> with a functional design. Grafting on some functional features
>> because some people find them clever is the wrong direction.

Randy, this is about expressivity, not cleverness.  Once you start doing
contract-based programming, you really want the ability to express important
properties in postconditions.  It seems you are reacting this way mostly because
it is unfamiliar.  Yes, Ada is evolving to have more functional constructs, such
as delta aggregates, array aggregates with iterated component associations, etc.
But that is what happens when you want to write things that specify what is the
net effect of an operation.  You may not be used to it, but that doesn't mean it
isn't useful and important.

> I'd be interested in hearing your take on the suggestion in my last email.
> After eliminating the <> altogether, as well as the need for aspects,
> and pulling the combiner and initial value out of the syntax, I think
> it helps quite a bit towards looking more Ada like.

As mentioned above, I think this is an interesting direction, but first, I would
prefer to see the use of the "when" clause for filtering rather than an "if"
expression, and the semantics seems quite ambiguous as written, given that the
syntax is not distinguishable from array aggregates with iterated component
associations.

> Quantified expressions and Array aggregates are pretty much reduction
> expressions that we already have in the language, and quantified
> expressions are particularly useful for contracts. I think reduction
> expressions will also be useful in this area, as well as supporting parallelism.

These are both very important points.  The reduction expression was designed to
be a generalization of quantified expressions (where the combining operation is
"and then" for "for all" and "or else" for "for some") and for array/container
aggregates with iterated component associations (where the combining operation
is "&" for an array aggregate, and something like "insert" for a container).
Secondly, these are the kinds of constructs you will want in postconditions to
describe what is being done by a function, and in expression functions when that
is *all* that is being done.  Admittedly, postcondition specifications can get
large, but that is the nature of contract-based programming.  One of the points
of reduction expressions is that it allows you to concisely specify what is
happening.  And if that is *all* that is happening, you can use the reduction
expression itself to perform the computation, rather than just specify the
contract for the computation.

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

From: Tucker Taft
Sent: Thursday, January 4, 2018  8:17 AM

One possibility would be to use unique syntax, such as "<...>", around the
iterator to indicate that you are doing a reduction across the result of the
iterator.  E.g.:

    --  Find smallest square of any odd element of Con
    Min_Odd_Square : constant Integer :=
      Integer'Min(Integer'Last,
                         <for E of Con when E mod 2 = 1 => E**2>);

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

From: Brad Moore
Sent: Thursday, January 4, 2018  10:35 AM

> Your suggestion is interesting, but it seems pretty ambiguous right
> now.  What distinguishes these nested iterators from an array (or
> container) aggregate with an iterated component association?
>
> Also, didn't we agree to add the "when" clause to all iterators at the
> last ARG meeting?

An array aggregate such as;

A : constant Array_Of_Integers := (for I in 1 .. 10 => I);

can be considered a shorthand for

A : constant Array_Of_Integers := (Empty_Array & (for I in 1 .. 10 => I))

Where Empty_Array is some expression for an array that has 0 elements.

The long form is disambiguated by the outer set of parens. There is only one
combiner function allowed in a reduction expression, in this case "&". The array
aggregate doesn't have that, nor does it have the enclosing set of parens.

It's subtle, but I think it works. It is also further disambiguated by context
where the expression must be an array since that is the target of the
expression. The only way to get an array of integers from a set of integer
values would be to concatenate them together. I think while this further
disambiguation helps clarify to the reader, it is not necessary for the compiler
to parse. It already has enough just with the set of parents. At least that is
my hope.


I don't recall discussing the "when" clause at the ARG meeting, and when I
search for "when" in Randy's minutes, I dont find anything. It sounds
interesting though, as it could help readability for cases where if expressions
would otherwise be used.

Is this something we would have discussed at a different ARG meeting? I searched
the Vienna minutes also, but didn't find anything.

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

From: Randy Brukardt
Sent: Thursday, January 4, 2018  6:16 PM

> One possibility would be to use unique syntax, such as "<...>", around
> the iterator to indicate that you are doing a reduction across the
> result of the iterator.  E.g.:
>
>     --  Find smallest square of any odd element of Con
>     Min_Odd_Square : constant Integer :=
>       Integer'Min(Integer'Last,
>                          <for E of Con when E mod 2 = 1 => E**2>);

This thread started because I said that I didn't want to see angle brackets used
in Ada syntax. That didn't suddenly disappear because you put them somewhere
else... :-)

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

From: Randy Brukardt
Sent: Thursday, January 4, 2018  6:31 PM

...
> I don't recall discussing the "when" clause at the ARG meeting, and
> when I search for "when" in Randy's minutes, I dont find anything. It
> sounds interesting though, as it could help readability for cases
> where if expressions would otherwise be used.

It was in Vienna, and it was buried in some other proposal. Tucker suggested
that it get put out on its own, where either it was added to all iterators or
none. The person it was assigned to has never pursued it, and I haven't bothered
to remind them of it because I think it is a horrible and completely unnecessary
idea. (One can always put a conditional expression/statement inside of any
iterator.) As such, I was rather hoping that the proposer never actually gets it
on the agenda in time (June 15th).

Perhaps it is time to break out the gee-gaws speech; I just posted a form of it
on Ada-Comment. We all know that there is a cost to every feature added to Ada,
and the last thing I want to see is a language overloaded by clever gee-gaws of
every stripe. Ada started out its life with a design where pretty much
everything had a name, everything is written out explicitly, and shorthands are
rare ("elsif" being pretty much it). Now people want a shorthand for every
situation, make everything anonymous, and hope that the many possibilities occur
often enough that readers don't have to go to a book every time to figure out
what is going on. That doesn't seem to be the right direction for Ada -- we need
to limit the nice to haves to a minimum.

I'm willing to keep talking about reduction expressions ONLY because of the
parallism opportunities and would hope that no one use them otherwise. I don't
have any interest in anything that is only valuable for sequential cases,
because that's solely about making code harder to understand (especially the <>
in the middle cases -- no thanks).

P.S. I can't imagine how a "when clause" would work with case and aggregate
completeness checks; it would seem necessary to limit it to the form of a static
predicate and treat it effectively like such a predicate -- but then it would
have been better to define  such a predicate and iterator over that rather than
defining a "when clause". Sounds like a major complication with no actual new
expressive power.

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

From: Randy Brukardt
Sent: Thursday, January 4, 2018  7:04 PM

...
> >> We've probably gone too far already in allowing stuff in
> >> expressions, and if we really need to do this to support
> >> parallelism in Ada, then it's time to admit that Ada is the wrong
> >> foundation and start over with a functional design. Grafting on
> >> some functional features because some people find them clever is the wrong direction.
>
> Randy, this is about expressivity, not cleverness.  Once you start
> doing contract-based programming, you really want the ability to
> express important properties in postconditions.
> It seems you are reacting this way mostly because it is unfamiliar.
> Yes, Ada is evolving to have more functional constructs, such as delta
> aggregates, array aggregates with iterated component associations,
> etc.  But that is what happens when you want to write things that
> specify what is the net effect of an operation.  You may not be used
> to it, but that doesn't mean it isn't useful and important.

It's about cleverness, because there is ZERO problem writing a function to do
this. And it is precisely the sort of thing that is best put into a function
anyway, because it's complex and most likely occurs in multiple contracts. There
is far too little abstraction is many of the contracts I've seen, making them
ginormous.

(And I don't see delta aggregate or iterator aggregates as being functional at
all; they're just additional ways to specify an aggregate, ones that have been
missing forever.)

...
> > Quantified expressions and Array aggregates are pretty much reduction
> > expressions that we already have in the language, and quantified
> > expressions are particularly useful for contracts. I think reduction
> > expressions will also be useful in this area, as well as supporting
> > parallelism.
>
> These are both very important points.  The reduction expression was
> designed to be a generalization of quantified expressions (where the
> combining operation is "and then" for "for all" and "or else" for "for
> some") and for array/container aggregates with iterated component
> associations (where the combining operation is "&" for an array
> aggregate, and something like "insert" for a container).

AARRRGGGHHH!!!!

I was strongly opposed to quantified expressions in the beginning (I wanted if
expressions and nothing further), and I was eventually convinced that (A) some
others considered them important, and (B) I don't have to use them or worry
about reading them in normal code.

So now you want to turn essentially all Ada code into these nasty things.

AAARRRGGHHH!

Especially, trying to unify two completely unrelated things, a composite object
constructor (aggregates) and chains of expressions (values). Indeed, perhaps it
is my compiler-writer's viewpoint, but I can't even imagine treating these as
the same. An expression is (an elementary) value that lives in a machine
register while objects are memory that lives elsewhere. (Composite expressions
are pointers at objects.) A literal unification as described above would lead to
god-awful code (given that "&" can allocate as many as 4 temporary objects for
each one) -- the absoletely worst way to create an object (*any* object). No one
wants that.

This whole train is heading in the wrong direction, which is highly unfortunate.
It might make sense for some new language, but not for Ada.

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

From: Tucker Taft
Sent: Thursday, January 4, 2018  7:47 PM

...
> This thread started because I said that I didn't want to see angle
> brackets used in Ada syntax. That didn't suddenly disappear because
> you put them somewhere else... :-)

I am still unclear why you are so strongly against angle brackets.  Parsing is
straightforward so long as the rightmost construct is a "simple_expression."
They clearly look different from existing bracketing constructs, but in this
case, the whole point is that you want them to look different.   We could start
using "[]" or "{}" if you think those would be somehow better.  But trying to
overload "(...)" even more at this stage seems unwise.

As far as the "when" clause, it is quite important for cases when you are
building up something with the iterator, as you don't want to create a component
at all if the when clause returns False.  Container aggregates seem to be one
important use, but they are also useful for parallel iterators, where you don't
want the overhead of creating a "tasklet" if you are not going to be doing
anything with the element.

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

From: Edmond Schonberg
Sent: Thursday, January 4, 2018  7:48 PM

> Especially, trying to unify two completely unrelated things, a
> composite object constructor (aggregates) and chains of expressions
> (values). Indeed, perhaps it is my compiler-writer's viewpoint, but I
> can't even imagine treating these as the same. An expression is (an
> elementary) value that lives in a machine register while objects are memory that lives elsewhere.
> (Composite expressions are pointers at objects.) A literal unification
> as described above would lead to god-awful code (given that "&" can
> allocate as many as 4 temporary objects for each one) -- the
> absoletely worst way to create an object (*any* object). No one wants that.
>
> This whole train is heading in the wrong direction, which is highly
> unfortunate. It might make sense for some new language, but not for Ada.

At the risk of eliciting more gag reflexes, let me suggest another way of
looking at quantified expressions and reduction operations.  The original Ada
dealt mostly with scalars, arrays, and records, and had a very rich set of
constructs to build composite values, but few global operations on them.

The introduction of containers, with a large set of dedicated operations, made
these composite objects (almost) as easy to manipulate as scalars, and hid the
storage management of these complex objects from the programmer, with a great
increase in expressivity.

Quantified expressions are another construct intended to manipulate composite
objects, and they are widely used in logical formulae, and therefore in
predicates and invariants. Reduction operations are another useful way of
manipulating composite values, and are widely used in other languages. Now the
current syntax is still not ideal, and there is no way we will get the
compactness of the APL notation, where  +/V means the sum of the elements of V
:-)!  But the examples that Tuck proposed indicate that it is really a natural
notation for common computations. In fact, thinking about the APL notation, it
would be nice if the iterator was implicit and the argument was a container.
But even without that, there are good arguments to have reduction expressions in
the language, outside of possible parallelism.

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

From: Tucker Taft
Sent: Thursday, January 4, 2018  8:13 PM

I think we are approaching the APL view, but using an iterator rather than
directly using the container, to avoid having to "re-ify" the set of items to be
reduced, and dealing with the fact that many reducer operations in Ada are *not*
operators, unlike in APL.  Building on Brad's suggestion, but using "{...}"
instead of "(...)" to reduce further overloading the meaning of "(...)":

    So what in APL would be "op / vector" becomes in Ada:

        op (initial, {iterator over vector})
                    --  if "op" is *not* an Ada operator

or

        initial op {iterator over vector}
                    --  if "op" *is* an Ada operator

I am using "{...}" rather than "<...>" merely to avoid further inflaming
things... ;-)

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

From: Randy Brukardt
Sent: Thursday, January 4, 2018  8:14 PM

...
> > This thread started because I said that I didn't want to see angle
> > brackets used in Ada syntax. That didn't suddenly disappear because
> > you put them somewhere else... :-)
>
> I am still unclear why you are so strongly against angle brackets.
> Parsing is straightforward so long as the rightmost construct is a
> "simple_expression."  They clearly look different from existing
> bracketing constructs, but in this case, the whole point is that you
> want them to look
> different.   We could start using "[]" or "{}" if you think
> those would be somehow better.  But trying to overload "(...)" even
> more at this stage seems unwise.

My experience is that so-called angle brackets make code much harder to read.
The old Scribe syntax allows angle brackets as one of 5 sets of bracket
characters, and the angle bracket uses tend to be the hardest to read
(especially when other nearby text is using  < or > literally). There's also an
error correction concern (our table driven parser uses weights for each token to
determine error correction, but the weights for a bracketing token and for an
operator are nearly maximally different). I'd probably be less concerned if the
contents where limited to just an identifier or something else very simple, but
arbitrary expression text will lead to madness. (While a machine might be able
to parse it, a human would have trouble.)

I'd definitely be happier with {} or [], but I'd really rather not have to use
anything new at all. Maybe impossible, dunno.

> As far as the "when" clause, it is quite important for cases when you
> are building up something with the iterator, as you don't want to
> create a component at all if the when clause returns False.  Container
> aggregates seem to be one important use, but they are also useful for
> parallel iterators, where you don't want the overhead of creating a
> "tasklet" if you are not going to be doing anything with the element.

That seems abusive to me. Not creating components is precisely the problem case,
since other rules generally require completeness of components (certainly in the
array aggregate case, and this is a very valuable and important feature of Ada).
I'd rather that such containers are created using a loop and if structure, not
by a phony aggregate. Aggregates (and other expressions for that matter) are for
*simple* cases, not something that can (or should) handle *every* case.

As far as the parallel iterators go, that seems to be assuming that there is a
tasklet for every iteration, but that is unlikely. Much more likely there are
going to be chunks of iteration for each tasklet, and only the most simple
conditionals would allow dropping any tasklets (normally, you at least have to
evaluate the conditionals before knowing whether further processing is needed;
doing that outside of a tasklet is reducing parallelism for no reason).

As with every clever concept that has been proposed, I'm sure there are uses.
The problem is that we are starting to drown in clever concepts -- to the point
where I haven't even had the energy to come up with any of my own. ;-) We need
to draw the line lest we have a ton of gee-gaws and no one other than AdaCore
left in the Ada business.

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

From: Brad Moore
Sent: Friday, January 5, 2018  1:58 AM

> As mentioned above, I think this is an interesting direction, but
> first, I would prefer to see the use of the "when" clause for filtering rather than an "if"
> expression, and the semantics seems quite ambiguous as written, given
> that the syntax is not distinguishable from array aggregates with
> iterated component associations.

For reference...

Here are the examples again, using only the currently discussed form, but using
{...} instead of (...) for the iterator part, and using "when" clauses where it
makes sense.

For the cases where "When" clauses are used, I also show the version that uses
if expressions for comparison.


Sum : constant Integer := (0 + {for I in 1 .. 10 => I});

Sales_Price : constant Integer := Integer'Max(100, {for I in I .. 10 => I});

-- Appending to string
Message : constant String := ("Alphabet: " & {for Letter in 'A' .. 'Z' => Letter});

-- Prepending to string (Note: We might want to allow the combiner function to appear
-- on either side of the iterator
Message : constant String := ({for Letter in 'A' .. 'Z' => Letter} & " <-Alphabet");

-- Calculate ln(1 + X)
function Mercator (X : Float; Num_Steps : Integer) return Float is
  (0.0 + {for I in 1 .. Num_Steps => X**I / Float(I) * (if I mod 2 = 0 then -1.0 else 1.0)});

-- Number of Adults (18 years of age or older)

Adults : constant Natural := (0 + {for Age of People => (if Age >= 18 then 1 else 0)}); Adults : constant Natural := (0 + {for Age of People when Age >= 18 => 1});

function Factorial(N : Natural) return Natural is (1 * {for J in 1..N => J});

function Sin(X : Float; Num_Terms : Positive := 5) return Float is
  (0.0 + {for I in 1 .. Num_Terms => (-1.0)**I * X**(2*I-1)/Float(Fact(2*I-1))});

Put_Line ("Sum of Squares is" & Integer'Image(0 + {for I in 1 .. 10 => I**2}));

function Pi (Number_Of_Steps : Natural := 10_000) return Real is
   (1.0 / Number_Of_Steps *
     (0.0 + {for I in 1 .. Number_Of_Steps =>
             (4.0 / (1.0 + ((Real (I) - 0.5) * (1.0 / Number_Of_Steps))**2))}));

--  Count the number of formal-params that are output parameters

Num_Outputs : constant Integer :=
    (0 + {for P of Formal_Params => (if P.Is_Operation_Output then 1 else 0)});

Num_Outputs : constant Integer :=
    (0 + {for P of Formal_Params when P.Is_Operation_Output => 1});

--  Create a bracketed list of the elements of DF.

X : constant DF_Image :=
  ("[" & {for F in DF => (if F = DF.First then "" else ", ") & F}) & "]";

--  This produces a string representation of a sequence of ranges
--  separated by spaces

return ("Countable::[" & {for R in Rngs => R.First & ".." & R.Last & " "}) & "]";

--  This prints out a bracketed, comma-separated string representation of the inputs

Put_Line(("[" & {for Inp of Inputs => (if Inp = Inputs'First then "" else ", ") & "VN" & Inp}) & "]");


--  This counts the number of parameters that are outputs or variables

(0 + {for P of Params => (if P.Is_Operation_Output or else P.Is_Var then 1 else 0)}) (0 + {for P of Params when P.Is_Operation_Output or else P.Is_Var => 1})

--  This determine the minimum index of a set of parameters that pass
--  the filter (i.e. are either outputs or variables).

First_Updated : constant Integer :=
   Integer'Min(Integer'Last,
               {for P of Params =>
                  (if P.Is_Operation_Output or else P.Is_Var then P.I else Integer'Last)});

First_Updated : constant Integer :=
   Integer'Min(Integer'Last,
               {for P of Params when P.Is_Operation_Output or else P.Is_Var => P.I});

-- Count the number of non-inputs

Num_Inputs : constant Integer :=
  (0 + {for P of Params => (if not P.Is_Operation_Output then 1 else 0)});

Num_Inputs : constant Integer :=
  (0 + {for P of Params when not P.Is_Operation_Output => 1});

--  Print the list of VNs in VNs_To_Prop

Put_Line("Recursive_Top_Down" & {for VN in VNs_To_Prop => " VN" & VN});


--  Create a set of the parent value numbers (VNs) of the VNs in
--  Changed_Operands

Parents : constant VN_Set :=
   (Op_Ctx.Empty_Set & {for Opnd in Changed_Operands => Op_Ctx.VN_To_Parent_Set_Map(Opnd)});

--  Print a list of [VNx => VNy] pairs representing the live-out set

Put_Line(" Live_Out_Set =" &
         {for Loc of Live_Out_Set => " [VN" & Loc & "=>VN" & Loc.VN & "]"});

--  Count the number of nodes that are found by following the
--  Parent chain.

return (0 + {for N in Node_Tree.Parent_Iterate(Node_Id) => 1});


--  This asserts that the sum of the sizes in Bit_Field_Sizes should be <= 63

Assert((0 + {for Size of Bit_Field_Sizes => Size}) <= 63);


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

From: Tucker Taft
Sent: Friday, January 5, 2018  7:45 AM

...
> My experience is that so-called angle brackets make code much harder
> to read. The old Scribe syntax allows angle brackets as one of 5 sets
> of bracket characters, and the angle bracket uses tend to be the
> hardest to read (especially when other nearby text is using  < or >
> literally). There's also an error correction concern (our table driven
> parser uses weights for each token to determine error correction, but
> the weights for a bracketing token and for an operator are nearly
> maximally different). I'd probably be less concerned if the contents
> where limited to just an identifier or something else very simple, but
> arbitrary expression text will lead to madness. (While a machine might
> be able to parse it, a human would have
> trouble.)

This seems pretty subjective.  Scribe is notoriously dense with brackets, so I
can imagine making such distinctions is painful.  But many languages these days
use angle brackets as part of generic instantiation (e.g. Map<Key_Type,
Value_Type>) so it seems that much of the programming world has adopted angle
brackets as a useful alternative bracketing syntax.  But I could certainly live
with "{...}" instead.

> I'd definitely be happier with {} or [], but I'd really rather not
> have to use anything new at all. Maybe impossible, dunno.

I think having a distinct syntax for this is quite important.  Parentheses are
already everywhere in Ada, and trying to imbue levels of parentheses with
special semantics seems quite dangerous.

>> As far as the "when" clause, it is quite important for cases when you
>> are building up something with the iterator, as you don't want to
>> create a component at all if the when clause returns False.
>> Container aggregates seem to be one important use, but they are also
>> useful for parallel iterators, where you don't want the overhead of
>> creating a "tasklet" if you are not going to be doing anything with
>> the element.
>
> That seems abusive to me.

That's a new term for the ARG!

...
> Not creating components is precisely the problem case, since other
> rules generally require completeness of components (certainly in the
> array aggregate case, and this is a very valuable and important
> feature of Ada). I'd rather that such containers are created using a
> loop and if structure, not by a phony aggregate. Aggregates (and other
> expressions for that matter) are for *simple* cases, not something
> that can (or should) handle *every* case.

When it comes to creating a container aggregate for a map, there typically is no
notion of "completeness."  There might be some notion of no overlap, but
completeness doesn't really make sense for most maps.

> As far as the parallel iterators go, that seems to be assuming that
> there is a tasklet for every iteration, but that is unlikely. Much
> more likely there are going to be chunks of iteration for each
> tasklet, and only the most simple conditionals would allow dropping
> any tasklets (normally, you at least have to evaluate the conditionals
> before knowing whether further processing is needed; doing that
> outside of a tasklet is reducing parallelism for no reason).
>
> As with every clever concept that has been proposed, I'm sure there
> are uses. The problem is that we are starting to drown in clever
> concepts -- to the point where I haven't even had the energy to come up with any of my own.
> ;-) We need to draw the line lest we have a ton of gee-gaws and no one
> other than AdaCore left in the Ada business.

The notion of a "filter" is not just something "clever."  It is fundamental to
many notions of what an iterator does.  Having to use an explicit "if" statement
or "if" expression muddies the waters in my view, and forces an extra level of
nesting which makes it that much *harder* to read.  And neither an "if"
statement nor an "if" expression really works for something that is generating
values, which is what we are doing in the particular cases of a container
aggregate or a reduction expression.

Also, remember that we hope to use these notations as part of contracts.  It
doesn't work very well to bury the semantics of a contract inside a function,
because then you just have to write a contract for that function (unless that
function is an expression function -- which gets us back to using things like
reduction expressions).

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

From: Jean-Pierre Rosen
Sent: Friday, January 5, 2018  8:30 AM

>> I'd definitely be happier with {} or [], but I'd really rather not
>> have to use anything new at all. Maybe impossible, dunno.

> I think having a distinct syntax for this is quite important.  Parentheses are
> already everywhere in Ada, and trying to imbue levels of parentheses with
> special semantics seems quite dangerous.

Note that there is a precedent using parenthesis: in the body of an entry
family, where the body is "repeated" by the "for"

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

From: Brad Moore
Sent: Friday, January 5, 2018  11:07 AM

I'd like to try to simplify this further.
It feels like pulling the combiner_function and the initial value out of the
iteration part of the reduction expression was a step in the right direction.

It still is bothering me, that the construct feels complex enough that it seems
to need two types of bracketing. (parens and braces). It also bothers me that
the outer part of the construct involving the combiner looks too much like
existing syntax, but has quite different semantics of feeding multiple values
back into the expression.

It feels like we can decompose this construct further to make use of other syntax that either already exists, or we are considering adding.

Specifically, it feels like the set of values produced by the iteration part of
the reduction expression can be considered to be an array, and we already have
array aggregate syntax that can produce such arrays.

If we take the view that we can use array aggregate syntax to produce an array,
perhaps even an anonymous array, then that reduces the problem for reduction
expressions to just be;
   How to summarize an array.

We could use an attribute, say 'Reduce for that purpose, where the 'Reduce
attribute could enclose the combiner function and initial value.

I think we can then go back to using <> as the indicator where the feedback
occurs.

For example, to add all the elements of an array of integers (or a container of
integers);

Sum : constant Integer := A'Reduce(0 + <>);

Note here that unlike before, there is no need for Identity aspects or Reducer
aspects. Those are only needed if we want this to run in parallel. Here we are
just feeding every value of the array into the 'Reduce attribute to produce the
summary. Note that the initial value in this example is represented by 0.

If we can say that an array aggregate can produce an anonymous array, then we
can summarize a range of values inline.

Sum : constant Integer := (for I in 1 .. 10 => I)'Reduce(0 + <>);

Here we are just combining two separate syntax features together. (Array
aggregates + Reduction expression) Another nice feature of this is that you dont
need nested parens, which makes things more difficult to read. Nor do you need
to use different kinds of bracketing.

If the expression gets too complicated, you can then use declare expressions to
break it up for improved readability.

Sum : constant Integer := (Values : constant := (for I in 1 .. 10 => I)
                           begin Values'Reduce(0 + <>));


Note it could be optional (or mandatory) to explicitly mention the type of the
array in the Values declaration above. But we could have as above, where the
type of array is implicit or considered to be an anonymous array type.

With this in mind, here are all the current examples rewritten to use this
syntax idea.

-- Sum of an array of integers
A_Sum : constant Integer := (A'Reduce(<> + 0));

-- Sum of a range of values
Sum : constant Integer := (X : constant := (for I in 1 .. 10 => I)
                           begin X'Reduce(<> + 0));
-- or shorthand
Sum : constant Integer := ((for I in 1 .. 10 => I)'Reduce(<> + 0));

Sales_Price : constant Integer := Offers'Reduce(Integer'Max(100, <>));

-- Appending to string
Message : constant String := (for Letter in 'A' .. 'Z' => Letter)'Reduce("Alphabet: " & <>);

-- Prepending to string
Message : constant String := (for Letter in 'A' .. 'Z' => Letter)'Reduce(<> & " <- Alphabet");

-- Calculate ln(1 + X)
function Mercator (X : Float; Num_Steps : Integer) return Float is
  (Terms : constant := (for I in 1 .. Num_Steps =>
                          X**I / Float(I) * (if I mod 2 = 0 then -1.0 else 1.0))
   begin Terms'Reduce(0.0 + <>));

-- Number of Adults (18 years of age or older)

Adult_Count : constant Natural :=
  (Adults : constant := (for Age of People when Age >= 18 => 1)
   begin Adults'Reduce(0.0 + <>);

function Factorial(N : Natural) return Natural is ((for J in 1..N => J)'Reduce(1 * <>));

function Sin(X : Float; Num_Terms : Positive := 5) return Float is
  (Terms : constant := (for I in 1 .. Num_Terms =>
                          (-1.0)**I * X**(2*I-1)/Float(Fact(2*I-1)))
   begin Terms'Reduce(0.0 + <>));

Put_Line ("Sum of Squares is" & Integer'Image((for I in 1 .. 10 => I**2)'Reduce(0 + <>)));

function Pi (Number_Of_Steps : Natural := 10_000) return Real is
   (Terms : constant :=
      (for I in 1 .. Number_Of_Steps =>
         (4.0 / (1.0 + ((Real (I) - 0.5) * (1.0 / Number_Of_Steps))**2)))
    begin 1.0 / Number_Of_Steps * Terms'Reduce(0.0 + <>));

--  Count the number of formal-params that are output parameters

Num_Outputs : constant Integer :=
    ((for P of Formal_Params when P.Is_Operation_Output => 1)'Reduce(0 + <>));

--  Create a bracketed list of the elements of DF.

X : constant DF_Image :=
  DF'Reduce("[" & (if <> = DF.First_Element then "" else ", ") & <>) & "]";

--  This produces a string representation of a sequence of ranges
--  separated by spaces

return (for R in Rngs => R.First & ".." & R.Last & " ")'Reduce("Countable::[" & <>) & "]";

--  This prints out a bracketed, comma-separated string representation of the inputs

Put_Line(Terms : constant :=
           (for Inp of Inputs => (if Inp = Inputs'First then "" else ", ") & "VN" & Inp)
         begin Terms'Reduce("[" & <>) & "]");

--  This counts the number of parameters that are outputs or variables

(for P of Params when P.Is_Operation_Output or else P.Is_Var => 1)'Reduce(0 + <>)

--  This determines the minimum index of a set of parameters that pass
--  the filter (i.e. are either outputs or variables).

First_Updated : constant Integer :=
   (for P of Params when P.Is_Operation_Output or else P.Is_Var => P.I)'Reduce(Integer'Min(Integer'Last,<>));

-- Count the number of non-inputs

Num_Inputs : constant Integer :=
  (for P of Params when not P.Is_Operation_Output => 1)'Reduce(0 + <>);

--  Print the list of VNs in VNs_To_Prop

Put_Line("Recursive_Top_Down" & VNs_To_Prop'Reduce(" VN" & <>));


--  Create a set of the parent value numbers (VNs) of the VNs in
--  Changed_Operands

Parents : constant VN_Set :=
   Changed_Operands'Reduce(Op_Ctx.Empty_Set & <>.VN_To_Parent_Set_Map);


--  Print a list of [VNx => VNy] pairs representing the live-out set

Put_Line((for Loc of Live_Out_Set => " [VN" & Loc & "=>VN" & Loc.VN & "]")'Reduce(" Live_Out_Set =" & <>));

--  Count the number of nodes that are found by following the
--  Parent chain.

return (for N in Node_Tree.Parent_Iterate(Node_Id) => 1)'Reduce(0 + <>);


--  This asserts that the sum of the sizes in Bit_Field_Sizes should be <= 63

Assert(Bit_Field_Sizes'Reduce(0 + <>) <= 63);

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

From: Erhard Ploedereder
Sent: Friday, January 5, 2018  6:12 PM

> But I could certainly live with "{...}" instead.

Of all the offered options, I would prefer this one, because it does have the
Kleene connotations of something iterative and no previous association with Ada
semantics.

Having said that, I find all the syntax examples so far rather unintuitive.
Foremost, when I see one of these {..}, am I necessarily looking at a reduction?
Or am I looking at a generator? Why this attempt to mix the two notions?

is "(3 + {for i in 1..10 ..})" intuitively a reduction with 3 as an initial
value? Not to me, someone had to decipher the riddle for me explicitly.

"Integer*Min(5, {for I in 1..10 => I})" I am not sure I even understood.
Is this a strange way of spelling "1"? I presume that the I in the iteration
range of the example is a typo, no? If not, what does it mean?

> Sales_Price : constant Integer := Integer'Min(5, (for I in I .. 10 =>
> I));

Is "(3, {for i in 1..10 ..})" something meaningful? I would read this as a
vector of 10 pairs. Or maybe it is a vector of 11 entries, starting with a 3?

Note the short Hamming distance for 2 very different things.

Indeed, an intuitive Ada equivalent for +/{..} is needed for reductions and
similarly one for generators, if you want to get the functional folks to love
you.

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

From: Edmond Schonberg
Sent: Friday, January 5, 2018  7:12 PM

Maybe the introduction of an attribute ‘Reduce,  as suggested by Brad, is the
best way to make the construct immediately visible and intrusive. The prefix is
the iterator (really a generator) and the arguments are the operator or function
name and the initial value. Functional folks will love the presence of a real
functional!

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

From: Randy Brukardt
Sent: Friday, January 5, 2018  7:24 PM

...
> Indeed, an intuitive Ada equivalent for +/{..} is needed for
> reductions and similarly one for generators, if you want to get the
> functional folks to love you.

I, at least, explicitly don't give a rats a** about the "functional folks".
I would hope this is what's best for Ada going forward, and I'd also hope this
isn't trying to chase other consistencies with some vague hope that Ada might
appeal to them. That *never* works, and just ends up bastardizing the language.

The Introduction to the Ada Standard states that "Ada was originally designed
with three overriding concerns: program reliability and maintenance, programming
as a human activity, and efficiency." Typical "functional folks" don't care
about any of these. Most functional programs are conglomerations of clever
tricks without concern for efficiency or much else. They'll write a one-liner to
accurately predict tommorrow's stock market price, but no one including the
author will be able to figure out how it works and it will take 100 years to
run.

We need to stick to these original goals for Ada, and that means avoiding
loading up Ada with the gee-gaw de jour. Shortly afterward in the Introduction,
it says "Above all, an attempt was made to keep to a relatively small number of
underlying concepts integrated in a consistent and systematic way..." We have to
be careful that we are not completely forgetting the human element here -- no
one is going to be able to remember bunches of rarely used syntaxes.

I came to Ada in the first place because it was the only language at the time
that really got syntax right, with the appropriate balance between explicitness
and expressivity. Most language of the time (and that has not changed much in
the interim) go way too far in the direction of clever shorthands (like "++")
that programmers have to remember and understand.

Up to this point, we've done a good job (with a couple of exceptions) in keeping
the original goals (and the reasons I use Ada in the first place) intact. But
we're now starting toward "design-by-committee" where everybody's favorite
gadget is included, regardless of need or expressivity.


If there really is no way to write safe parallel-executing programs in a
conventional style, then so be it. But let's not use that as an excuse to
destroy all of Ada's positive attributes; it means that Ada has reached the end
of its useful life and a new language (without the baggage) needs to take over.
(And since I probably won't use that language, I don't care what it looks like.)

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

From: Randy Brukardt
Sent: Friday, January 5, 2018  7:50 PM

> ...
> > Not creating components is precisely the problem case, since other
> > rules generally require completeness of components
> (certainly in the
> > array aggregate case, and this is a very valuable and important
> > feature of Ada). I'd rather that such containers are
> created using a
> > loop and if structure, not by a phony aggregate. Aggregates
> (and other
> > expressions for that matter) are for *simple* cases, not something
> > that can (or should) handle *every* case.
>
> When it comes to creating a container aggregate for a map, there
> typically is no notion of "completeness."  There might be some notion
> of no overlap, but completeness doesn't really make sense for most
> maps.

The reason for having container aggregates at all (IMHO) is to allow the
array-like containers to be used even more like an array. One gets aggregates
for maps as a side-effect, but they don't fit into the model of aggregates at
all. (The whole reason for using aggregates is for the completeness checks,
otherwise a series of component assignments is easier and usually more
readable.)

One is not (I hope) building giant data structures with container aggregates;
those are almost always created by a program, and there's no reason for that
program to build a giant unoptimizable entity when a series of statements works
just as well (and can be optimized).

...
> > As with every clever concept that has been proposed, I'm sure there
> > are uses. The problem is that we are starting to drown in clever
> > concepts -- to the point where I haven't even had the energy to come
> > up with any of my own. ;-) We need to draw the line lest we have a
> > ton of gee-gaws and no one other than AdaCore left in the Ada business.
>
> The notion of a "filter" is not just something "clever."  It is
> fundamental to many notions of what an iterator does.

Not mine. :-)

> Having to use an explicit "if" statement or "if" expression muddies
> the waters in my view, and forces an extra level of nesting which
> makes it that much *harder* to read. And neither an "if" statement nor
> an "if" expression really works for something that is generating
> values, which is what we are doing in the particular cases of a
> container aggregate or a reduction expression.

That could be fixed, but it would require introducing another gee-gaw (we allow
omitting "else True", we could also allow omitting "else 0" and "else 0.0").

In any case, I jump back to the line in the RM Introduction I mentioned in the
reply to Erhard: "Above all, an attempt was made to keep to a relatively small
number of underlying concepts...". There are already at least two, and often
three, ways to write an iterator filter. Do we really need a fourth?

> Also, remember that we hope to use these notations as part of
> contracts.  It doesn't work very well to bury the semantics of a
> contract inside a function, because then you just have to write a
> contract for that function (unless that function is an expression
> function -- which gets us back to using things like reduction
> expressions).

Generally, these sorts of functions have to be extra-pure ("global in out null")
and they produce a simple answer ("Is_Open", "Mode", "Capacity", "Length"), so
there is no separate contract for them. And they should be able to reduced
algebraically at the call-site (assuming that appropriate stable properties have
been defined), meaning that looking in them for preconditions is unnecessary. So
we're mainly talking about being able to look in them for the purposes of
proving postconditions -- but that's almost never a problem since the function
and the postcondition are going to be in the same package (since they both need
to be primitives of the type). I suppose there might be some issues with
inherited functions and with postconditions for class-wide subprograms, but I
don't think this matters much: any static prover is going to have to look into
bodies -- at least for generic instantiations -- and if you have to do that in
some cases, why not all?

The more general answer is given in my reply to Erhard's message, but it
probably is even more critical. If we *really* need all of this stuff, then Ada
is done, because it will collapse of excessive weight. Ada does not need
everyone's pet feature (or pet five features ;-) and SOMEONE has to start being
the voice of reason on this topic.

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

From: Randy Brukardt
Sent: Friday, January 5, 2018  9:21 PM

...
> > My experience is that so-called angle brackets make code much harder
> > to read. The old Scribe syntax allows angle brackets as one of 5
> > sets of bracket characters, and the angle bracket uses tend to be
> > the hardest to read (especially when other nearby text is using  <
> > or > literally). There's also an error correction concern (our table
> > driven parser uses weights for each token to determine error
> > correction, but the weights for a bracketing token and for an
> > operator are nearly maximally different). I'd probably be less
> > concerned if the contents where limited to just an identifier or
> > something else very simple, but arbitrary expression text will lead
> > to madness. (While a machine might be able to parse it, a human
> > would have
> > trouble.)
>
> This seems pretty subjective.

Syntax always is!

> ... Scribe is notoriously dense
> with brackets, so I can imagine making such distinctions is painful.
> But many languages these days use angle brackets as part of generic
> instantiation (e.g. Map<Key_Type,
> Value_Type>) so it seems that much of the programming world has
> adopted angle brackets as a useful alternative bracketing syntax.

In that case, it seems to be a list of identifiers, which is quite restricted
and something I'd probably have grudgedly agreed to. Allowing arbitrary
expressions inside however, brings up reading ambiguity even if the compiler can
figure it out:

    <(lots + identifiers * operators > more + identifiers and operators)>

Hard to tell if the > is closing or an operator, especially if the expression is
long enough that it has to be written on multiple lines. And compare that to:

    <(lots + identifiers * operators >) + more + identifiers and operators > 1

which is the same problem with the other result.

> But I could certainly live with "{...}" instead.

Me too, so let's stay with that for now.

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

From: Brad Moore
Sent: Saturday, January 6, 2018  2:13 AM

> I find all the syntax examples so far rather unintuitive. Foremost,
> when I see one of these {..}, am I necessarily looking at a reduction?
> Or am I looking at a generator? Why this attempt to mix the two
> notions?

I strongly dislike introducing curly brace for this one purpose in Ada. It feels
too foreign to Ada, and too complex requiring two sets of braces of different
kinds in the same construct. That is what drove me to find a different solution
with the 'Reduce attribute.

> is "(3 + {for i in 1..10 ..})" intuitively a reduction with 3 as an
> initial value? Not to me, someone had to decipher the riddle for me
> explicitly.

How about?

(1..10)'Reduce(3 + <>);

To me, this appears more intuitive that we are reducing the range of values from
1 to 10. We have a descriptively named attribute that you could look up in the
RM, if you wonder how that attribute works, but the attribute syntax suggests to
me we are applying the reduction operation to the values on the left using the
formula on the right.

As Ed mentioned, the part on the left is the generator, but if you've already
got an array, there's no need to generate anything, and you can replace the left
side with the name of an array.

The idea of the 'Reduce attribute is that it is always just reducing an array of
values.

If you need to modify the values before you reduce them, then you could expand
the generator syntax to full array aggregate syntax to name the values and
modify them.

e.g.

-- Sum of squares
(for I in 1 .. 10 => I**2)'Reduce(0 + <>)

I'm not sure if we'd want to support the range shorthand, but it seems silly and
confusing to name loop variables if they are not used, which helps readability I
think when the shorthand can be used.

> "Integer*Min(5, {for I in 1..10 => I})" I am not sure I even understood.
> Is this a strange way of spelling "1"? I presume that the I in the
> iteration range of the example is a typo, no? If not, what does it
> mean?

The * between Integer and Min is a typo. It should be ' , since 'Min is the
attribute. The intent was to use array aggregate syntax to generate an array, as
you can currently do in Ada.

e.g.

-- Array Aggregate syntax example that is already in the RM
X : constant Integer_Array := (for I in 1 .. 10 => I);

I much prefer the following though than the curly brace syntax. See my previous
email for more examples and explanation.

(1 .. 10)'Reduce(Integer'Min(5, <>))

>> Sales_Price : constant Integer := Integer'Min(5, (for I in I .. 10 =>
>> I));
>
> Is "(3, {for i in 1..10 ..})" something meaningful? I would read this
> as a vector of 10 pairs. Or maybe it is a vector of 11 entries,
> starting with a 3?

The intent was that that wouldn't have been meaningful, as there is no combiner
function associated with the 3.

I see the confusion though, which hopefully is better remedied by the latest
syntax idea.

If you still find it confusing even with the 'Reduce attribute, then you at
least have the option of splitting this up to declare an array separately, and
then apply the reduction with just the 'Reduce attribute.

You don't have that option with the curly brace syntax.

Bids : constant Price_Array := (for C of Customers => C.Bid);

-- Get the best bid, but it has to be better than the minimum acceptable offer
Sales_Price : constant Integer :=
   Bids'Reduce(Integer'Max(<>,
                           Minimum_Acceptable_Offer));


Another advantage of the 'Reduce attribute syntax, is that it provides more
capability with simpler syntax.

With the previous curly brace syntax, to append the alphabet to a string you
could in theory write:

("Alphabet: " & {'A'..'Z'})

But if we want to instead prepend the alphabet to a string, we would need the
syntax to support having the combiner function and initial value on either side
of the generator, which is more complex syntax, and more complex to parse and
understand.

({'A'..'Z'} & "<- Alphabet")

With the Reduce attribute, you get the same capability, in a more uniform way.

('A'..'Z')'Reduce("Alphabet: " & <>)
vs.
('A'..'Z')'Reduce(<> & "Alphabet: ")

Another point to note is that though parens are not nested with 'Reduce
attribute syntax. The curly brace syntax you have braces nested inside of
parens. I was noticing that the nested parens can become difficult to read in
more complicated reduction expressions.

Lastly with the curly brace syntax, you always need to write a generator. With
the Reduce attribute, you dont need to write a generator if you already have an
array.

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

From: Erhard Ploedereder
Sent: Saturday, January 6, 2018  8:44 AM

>> "Integer*Min(5, {for I in 1..10 => I})" I am not sure I even understood.
>> Is this a strange way of spelling "1"? I presume that the I in the
>> iteration range of the example is a typo, no? If not, what does it
>> mean?
>> Sales_Price : constant Integer := Integer'Min(5, (for I in I .. 10 =>
>> I));

> The * between Integer and Min is a typo. It should be ' , since 'Min is the
> attribute.

Sorry, my typo. I understood that part. But you did not answer my question(s).
What is the outcome? and was the I in the range intentional and I simply did not
understand the idea?

> The intent was to use array aggregate syntax to generate an array, as
> you can currently do in Ada.

Where does an array play into Integer'Min and if so, what role does the 5 play?
To me, Min is typically a binary function that chooses among two values. By your
analogy, 'Min would have a signature of (Integer, Array of Integer); that looks
very strange.

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

From: Edmond Schonberg
Sent: Saturday, January 6, 2018  10:40 AM

I think that the introduction of an attribute 'Reduce is so far the clearest
choice: it makes the syntax clear without the need for a new keyword, and it
avoid the ambiguities /  obscuritiies that Randy has found in previous
proposals. Using an attribute also allows for a compact notation when applied to
a composite that supports iteration:   V'Reduce ("+", 0)  is clear and compact
(almost like +/V !).  But the prefix can be any iterated_component association :

   (for J in V'range => V (J) ** 2)'Reduce (F, V0)

       which can also be written as:

   (for E of V => E ** 2)'Reduce (F. 0).

The first argument of the attribute must be s combiner function or operator,
i.e. a binary operation with operands and result of the same type.  Being able
to have an expression on the prefix that yields an itterable construct is also a
natural generalization.  Randy, is this any more palatable?

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

From: Brad Moore
Sent: Saturday, January 6, 2018  11:45 AM

>>> "Integer*Min(5, {for I in 1..10 => I})" I am not sure I even understood.
>>> Is this a strange way of spelling "1"? I presume that the I in the
>>> iteration range of the example is a typo, no? If not, what does it
>>> mean?
>>> Sales_Price : constant Integer := Integer'Min(5, (for I in I .. 10
>>> => I));
>
>> The * between Integer and Min is a typo. It should be ' , since 'Min
>> is the attribute.
>
> Sorry, my typo. I understood that part. But you did not answer my
> question(s). What is the outcome? and was the I in the range
> intentional and I simply did not understand the idea?

The idea was that Integer'Min was to be treated as the combiner function, and
the curly braces indicated the values to be fed into the combiner function as
the second parameter.

As a combiner function, the other parameter shows the initial value (5) to be
passed into the first parameter, but for subsequent iterations, the result of
the previous calls to Integer'Min are passed back into Integer'Min for the first
parameter instead. The more I look at that example, the more I see your
confusion, and the more I dislike that whole proposal. Its way too subtle and
non-intuitive.

Integer'Min(5, {for I in 1 .. 10 => I});

Compare to;

(for I in 1 .. 10 => I)'Reduce(Integer'Min, 5)

As per Ed's latest suggested tweaks, which to me make it even clearer and
simpler. I agree with Ed and I think the 'Reduce attribute idea is a clear
winner over anything we've discussed before.

I will take a stab at updating the AI to reflect this latest idea.

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

From: Tucker Taft
Sent: Saturday, January 6, 2018  12:57 PM

I like Ed's refinement of Brad's 'Reduce proposal as well.

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

From: Brad Moore
Sent: Saturday, January 6, 2018  2:37 PM

> The first argument of the attribute must be s combiner function or
> operator, i.e. a binary operation with operands and result of the same
> type.

Can we relax this restriction a bit and say that that its a binary operation,
and the type of the 2nd argument of the attribute must match at least one of the
arguments of the binary operation as well as the result type of the binary
operation. The type of the values being reduced must match the type of the other
parameter of the binary operation.

This would then allow reductions such as concatenation where the result type can
be an array type, but the elements being concatentated are the elements of the
array.

e.g.

(for Letter in 'A' .. 'Z' => Letter)'Reduce("&", "")

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

From: Tucker Taft
Sent: Saturday, January 6, 2018  4:17 PM

Agreed, we should support the case where we have Vector op Component => Vector.

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

From: Erhard Ploederder
Sent: Saturday, January 6, 2018  4:08 PM

>    (for J in V’range => V (J) ** 2)’Reduce (F, V0)
>
>        which can also be written as:
>
>    (for E of V => E ** 2)’Reduce (F. 0).
>
> The first argument of the attribute must be s combiner function or
> operator, i.e. a binary operation with operands and result
> of the same type.  Being able to have an expression on the prefix that
> yields an itterable construct is also
> a natural generalization.  Randy, is this any more palatable?


I find this model and syntax a lot better.

Semantic question: In the case of
 (for E of V => g(E))'Reduce(f, 0)
where g has a side effect, what will the semantics say about the guaranteed
sequence of g and f calls?

1) all g calls before all f calls ?  Then you lost all ability to stream the
   values to and through the Reduce.

2) g, f, g, f, ... ?

3) (almost) anything goes

?
------------------------

1) is the semantics that you undoubtedly would be guaranteed to get if the
   prefix is to be treated as a normal array aggregate. (=> need for a different
   syntax, if you do not want that - and I sure do not want this canonical
   semantics)

3) is necessary if parallelization of g calls is supposed to play here.

2) maybe as a selectable option? It clearly makes implemention easier, since no
   buffer for results of g calls is needed, as is in case 3) and it still avoids
   storing the intermediate array.

--------------------

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

From: Edmond Schonberg
Sent: Saturday, January 6, 2018  4:40 PM

Given the interest in parallizability, I think the choice must be 3),  i.e.
unspecified order. If this is to be parallelizable, g better be side-effect free
anyway.

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

From: Edmond Schonberg
Sent: Saturday, January 6, 2018  4:47 PM

> Agreed, we should support the case where we have Vector op Component =>
> Vector.

I still think that this is an abuse of notation. It is amusing that it may fall
out of the proposed semantics of reduction, but a construct that builds an array
from scalar components does not look like its reducing anything:-)! We have
plenty of constructs for aggregates already, hiding this one in this new
notation is redundant (not to mention the awkward implementation it requires).
So I’d rather retain the consistent type requirement. (not a deal breaker
obviously, but also simpler to describe).

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

From: Brad Moore
Sent: Saturday, January 6, 2018  5:05 PM

A good point.

Another advantage of this restriction would be that we would not need the
'Reducer aspect for parallelism, since the combiner function would then always a
reducer function. (i.e. The function used to combine results from independent
tasklets).

We would still need the Identity aspect, but it would simplify the parallelism
part of this AI, and reduce the number of aspects needed to be placed on various
library calls in the RM.

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

From: Brad Moore
Sent: Saturday, January 6, 2018  8:44 PM

I have a few questions.

1) I presume we want 'Reduce to work on multidimensional arrays?

   Example from RM:

  G : constant Matrix :=
    (for I in 1 .. 4 =>
       (for J in 1 .. 4 =>
          (if I=J then 1.0 else 0.0))); -- Identity matrix

  Sum : constant Float := G'Reduce("+", 0.0);

  Reason, seems like a useful thing to be able to do, and easy enough to understand and implement.


2) I presume we are probably *not* interested in defining a version of 'Reduce
   that operates on a single dimension of a multidimentional array?

  e.g.
  Sum_1 : constant Float := G'Reduce(1, "+", 0.0);

  Where 1 represents the first dimension, similar to 'Length(1)

  Reason, while this could be implemented probably about as easy at the other
  version of 'Reduce, I suspect there might not be enough need for this to
  justify. We could always add this later, if needed.


3) Its not clear to me whether we'd want to be able to apply 'Reduce to
   aggregate expressions. I don't see a reason not to, and I suspect it would be
   allowed based on Ed's outline of the rules.

That is, I would think one would be able to write something like?

  Sum : constant Float :=
     Matrix'(for I in 1 .. 4 =>
               (for J in 1 .. 4 =>
                  (if I=J then 1.0 else 0.0)))'Reduce("+", 0.0);

4) And if the answer to 3 is yes, then I presume it would also work for other
   forms of array aggregates, not just ones involving
   iterated_component_associations?

eg

Sum : constant Float := Matrix'(1 => (1.1, 1.2, 1.3), 2 => (2.1, 2.2, 2.3))'Reduce("+", 0.0);

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

From: Jean-Pierre Rosen
Sent: Sunday, January 7, 2018  12:42 AM

I have been followin this thread with mixed feelings...

Although I see the benefit of the attribute, I don't like having:
(very_complicated_expression_spanning_several_lines)'Reduce()

I would suggest doing it the other way round:
For every function F with appropriate profile (TBD), there is a function
F'Reduce that operates on arrays of Elems, with the following semantics:
1) if the array is empty, Constraint_Error is raised
2) if the array has one element, the element is returned
3) otherwise, the result is the successive application of F to elements in an
   arbitrary order (needs better definition, it's just to give the idea).

This has the following benefits:
- Easy to read and understand
- No need for Identity
- For parallelism, easy to specify the reduction function as
  an aspect Reduction => F'Reduce

Some examples:

Old:
(for E of V => E ** 2)’Reduce (F. 0)

Proposed:
F'Reduce ((for E of V => E ** 2))

Old:
(for I in 1 .. 10 => I)'Reduce(Integer'Min, 5)

Proposed:
Integer'Min'Reduce ((5, for I in 1..10 => I))


Old:
(for Letter in 'A' .. 'Z' => Letter)'Reduce("&", "")

Proposed:
"&"'Reduce ((for Letter in 'A' .. 'Z' => Letter))

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

From: Peter Chapin
Sent: Sunday, January 7, 2018  9:17 AM

Hello!

I'm just an observer here, for now, so I feel some reluctance to jump in with
too many comments. I feel like I'm still gathering background information. ??
That said, I did want to say a few things about the debate regarding reduction
expressions...

I have extensive background with the functional language Scala and I've worked
with OCaml and Haskell as well. I can appreciate that Ada is not, at its core, a
functional language and that making it into one is fraught with potential
difficulties. On the other hand, there are two forces at work that are pushing
Ada to grow more functional features: contracts and now parallelism. Contracts
benefit from powerful expressions, and parallelism benefits from pure
expressions, both things that functional languages are good at. So it makes
sense to me to borrow ideas from the functional world to support these things in
Ada. The trick is doing so in a reasonable (for Ada) way!

In Scala, at least, there is a distinction between "reduce" and "fold." Folds
take an initial value, can be applied to an empty sequence, and use a combiner
function that might have parameters of different types (for example when folding
a sequence of characters into a string). In contrast, reductions can't be
applied (without exception) to an empty sequence and use a combiner function
taking parameters of the same type as the sequence elements. The AI talks about
"reducer functions" and "reduction expressions" which I found confusing at first
since the "reduction expression" is really a fold in the functional sense. I'm
not sure if this matters to anything, but speaking as someone coming from the
functional community I had to read the AI twice before I de-confused myself on
this point.

Regarding syntax... I realize we aren't talking about adding general lambdas to
Ada, but does it make sense to choose a syntax that wouldn't prohibit such an
addition in the future?

I see a pretty similarity between:

(1 .. 10)'Reduce(3 + <>)

and the Scala equivalent:

(1 to 10).fold(3)(_ + _)

Scala allows methods with multiple parameter lists, and for obscure technical
reasons (not one of Scala's better features) related to type inference, the
initial value needs to be put into its own parameter list. So the syntax
logically is trying to be:

(1 to 10).fold(3, _ + _ )

where the weird looking "_ + _" is Scala's highly abbreviated way of writing a
lambda. The underscores are placeholders for the unnamed function arguments,
similar to the <> notation in the proposed 'Reduce syntax. Spelling out the
anonymous combiner function longhand gives:

(1 to 10).fold(3, (x: Int, y: Int) => x + y) )

I guess that's all I have to say for now. I don't have a specific suggestion or
feeling at the moment about what is best for Ada here. I'm still absorbing the
very interesting discussion. I did want to throw in my support for the idea of,
in some fashion, adding folds, er... reduction expressions, to Ada. Certainly
they are widely used in languages that currently have them and they would enrich
Ada's expression sublanguage considerably.

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

From: Tucker Taft
Sent: Sunday, January 7, 2018  10:30 AM

...
> I would suggest doing it the other way round:
> For every function F with appropriate profile (TBD), there is a
> function F'Reduce that operates on arrays of Elems, with the following
> semantics:

I believe it is a serious mistake to have to create an array to do a reduction.
There are many cases when you want to do a reduction over a series of values
that are produced in various ways.  Limiting it to arrays means you end up
having to figure out how to create the array, and furthermore, you need to know
in advance how big an array to allocate, or undergo the dynamic allocation
implicit in a growable vector.

Using a generalized iterator (including a filter of some sort) is significantly
more flexible and potentially hugely more time and space efficient.

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

From: Erhard Ploedereder
Sent: Sunday, January 7, 2018  12:02 PM

> I believe it is a serious mistake to have to create an array to do a
> reduction.

Indeed. Argument to the Reduction should be a Generator (which, as a very
special case, can be an array iterator).

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

From: Brad Moore
Sent: Sunday, January 7, 2018  12:05 PM

> I have been followin this thread with mixed feelings...
>
> Although I see the benefit of the attribute, I don't like having:
> (very_complicated_expression_spanning_several_lines)'Reduce()
>
> I would suggest doing it the other way round:
> For every function F with appropriate profile (TBD), there is a
> function F'Reduce that operates on arrays of Elems, with the following semantics:
> 1) if the array is empty, Constraint_Error is raised

I don't think we want the user to have to worry about handling such constraint
errors. That's why we have the initial_value. You get that result if you are
trying to apply 'Reduce to a null array, or an empty
iterated_component_association. Having to deal with exceptions makes it more
difficult to use with contracts for example.

> 2) if the array has one element, the element is returned
> 3) otherwise, the result is the successive application of F to
> elements in an arbitrary order (needs better definition, it's just to give
> the idea).
>
> This has the following benefits:
> - Easy to read and understand
> - No need for Identity
> - For parallelism, easy to specify the reduction function as an
>   aspect Reduction => F'Reduce

I think we can (and probably should) get rid of the 'Identity aspect with either
proposal. I don't think it is needed. For tasklets where Initial_Value is not
being applied, the initial value can be the value of the first item. If there
are more than one item per tasklet, the Reducer function can be applied to
combine the first and subsequent results.

Another criticism of this idea is that it would significantly expand our concept
of what an attribute is.

With the previous 'Reduce, the arguments of the attribute translate to arguments
of a function call, which we have already with other attributes in the language.

With your suggestion, the contents of this attribute are an expression, which
needs to be parsed, which is something we don't have yet in the language.

> Some examples:
>
> Old:
> (for E of V => E ** 2)’Reduce (F. 0)
>
> Proposed:
> F'Reduce ((for E of V => E ** 2))
>
> Old:
> (for I in 1 .. 10 => I)'Reduce(Integer'Min, 5)
>
> Proposed:
> Integer'Min'Reduce ((5, for I in 1..10 => I))

I also find the expression (5, for I in 1..10 => I) strange. It doesn't seem to
mean anything by itself.

Only in the context of outside its enclosing parens as part of one particular
attribute.

With the 'old' syntax, there are no meaningless expressions.

Otherwise your suggestion appears to be mainly a cosmetic one, of just moving
things around. I can see your reasoning for doing so, but I don't think can be
justified given these criticisms.

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

From: Jean-Pierre Rosen
Sent: Sunday, January 7, 2018  12:20 PM

> I believe it is a serious mistake to have to create an array to do a
> reduction.  There are many cases when you want to do a reduction over
> a series of values that are produced in various ways.  Limiting it to
> arrays means you end up having to figure out how to create the array,
> and furthermore, you need to know in advance how big an array to
> allocate, or undergo the dynamic allocation implicit in a growable
> vector.
>
> Using a generalized iterator (including a filter of some sort) is
> significantly more flexible and potentially hugely more time and space
> efficient.

Indeed. This proposal does not intend to really create an array. It's 100% "as
if".

I was not explicit about this, but since F'Reduce would be 100% in the
compiler's realm, it could be defined as having convention => intrinsic and
aspect Inline. Since it deals only with elements, it could be considered an
optimization that F is simply called in line on all the elements without needing
to construct an actual array.

OTOH, a compiler would be /allowed/ to construct an array if it is more
convenient or efficient in some cases.

I think it would be easier to understand and explain with this model.

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

From: Tucker Taft
Sent: Sunday, January 7, 2018  1:00 PM

Your proposed syntax does not feel like an improvement from a readability point
of view, and seems to muddy the waters significantly semantically, in my view.

Personally, I prefer the order where the iterator comes first, so you know what
you are talking about, and then the reduction operation.  There are various
syntaxes that have been proposed that have that ordering.  I happen to still
prefer the one that ParaSail uses, but the one with:

   (iterator)'Reduce(func, params)

is second best, in my view.

I think we should not eliminate the 'Identity aspect, and in fact might want
additional aspects such as 'Commutative and 'Associative, but the basic
semantics of the reduction expression should not depend on having any of these
aspects specified.  Specifying them can provide more ways to optimize things,
but without them, I would argue the semantics should be very simple, and not
require the operation to be commutative, and perhaps not even associative
(though that is a bit more stringent).

The semantics of "(iterator)'Reduce(func, initial_val) would be simply:

    tmp := initial_val;
    while more in (iterator) loop
        tmp := func (tmp, <next-val-of-(iterator)>);
    end loop;
    return tmp;

Parallelization would be optional, and could use properties of "func" as defined
by various aspects (e.g. Identity, Reducer, Commutative, Associative, etc.), or
built-in knowledge in case of language-defined operators, to achieve maximum
speedup.

Overload resolution for "func" would expect a function with a profile of

    function func (Left : <initial_val'Type>; Right : <iterator-element'Type>) return <initial_val'Type>;

For the first version of this, we could require that <initial_val'Type> and
<iterator-element'Type> be the same, though that doesn't seem necessary, and
interferes with operations that are, for example, taking individual elements and
building up a set.  I agree it makes parallelization easier, if you presume func
has two operands of same type, and is associative, though having an aspect that
identifies a "Reducer" function that has those properties can provide the same
advantage.

You might also want to allow a second version of this, that could perhaps use
the identical syntax, and be chosen when the "Reduce" operation parameter is
actually a procedure rather than a function:

    (iterator)'Reduce(proc, initial_val)

would expand into

    tmp := initial_val
    while more in (iterator) loop
         proc(tmp, <next-val-of-(iterator)>);
    end loop;
    return tmp;

This could be significantly more efficient when the reduction is producing a
more complex data structure, such as a hashed set, or a large matrix.

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

From: Brad Moore
Sent: Sunday, January 7, 2018  1:57 PM

> I think we should not eliminate the 'Identity aspect, and in fact
> might want additional aspects such as 'Commutative and 'Associative,
> but the basic semantics of the reduction expression should not depend
> on having any of these aspects specified.  Specifying them can provide
> more ways to optimize things, but without them, I would argue the
> semantics should be very simple, and not require the operation to be
> commutative, and perhaps not even associative (though that is a bit more
> stringent).

I was actually thinking of writing the AI to replace the Identity aspect with an
Associative Boolean aspect. That seems more useful, since parallelism is not
possible if a reducer function is not associative.

If the reducer function does not have the associative aspect, then'Reduce
attribute would normally apply sequential processing. On the other hand, if the
reduction function does have it, then parallel execution can potentially be
applied by the implementation.

A problem with the Identity aspect is that it is difficult to apply everywhere.

For example, the language defined bitwise "and" of;

type Fingers is mod 5;

is hard to define. You could say it is Fingers'Last, but then "and"ing that with
3, wouldn't work. You could say it is 7, but then the value is outside the range
of values for the type, and its use could trigger constraint errors.

Using the logic that Jean-Pierre proposed, you don't have to define this, and
the 'Reduce attribute works.

I think the Associative aspect is a better replacement for 'Identity, because it
can easily defined on all subprograms that need it. (And its simpler, being a
boolean aspect)

I think we should not include the Identity aspect in this proposal unless
someone can show a valid need for it. I would want to see some sort of
explanation on how it can improve parallelism or understanding.

As it stands, it just appears to add complexity to the model in an inconsistent
manner without any real benefit. We can always add it later, if we can find a
valid use for it.

The associative aspect already seems to have validity. It can be used to prevent
errors, and help in the decision of whether to use parallelism or not.

A communitative aspect might be useful for future consideration, but my
experience with Paraffin is that having the implementation assume all reductions
are non-commutative does not add noticeable overhead to parallelism. So for now,
I would recommend we leave the Commutative aspect out of the AI.

> Overload resolution for "func" would expect a function with a profile
> of
>
>    function func (Left : <initial_val'Type>; Right : <iterator-element'Type>)
>    return <initial_val'Type>;
>
> For the first version of this, we could require that
> <initial_val'Type> and <iterator-element'Type> be the same, though
> that doesn't seem necessary, and interferes with operations that are,
> for example, taking individual elements and building up a set.  I
> agree it makes parallelization easier, if you presume func has two
> operands of same type, and is associative, though having an aspect
> that identifies a "Reducer" function that has those properties can provide the same advantage.

By first version, I assume you mean first version of this AI/feature.

I agree we can always consider later whether to add a 'Reducer aspect and
support reducer functions with differing types of parameters, based on feedback
from users. I think for now assuming all parameters are of the same type
probably covers a majority of the uses.

> You might also want to allow a second version of this, that could
> perhaps use the identical syntax, and be chosen when the "Reduce"
> operation parameter is actually a procedure rather than a function:
>
>    (iterator)'Reduce(proc, initial_val)
>
> would expand into
>
>    tmp := initial_val
>    while more in (iterator) loop
>         proc(tmp, <next-val-of-(iterator)>);
>    end loop;
>    return tmp;

I agree allowing a procedure for a reducer is useful, and probably worth
considering for this version of the AI. We could say that it can be a procedure
that accepts two parameters of the same type, where the first parameter is an in
out parameter.

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

From: Tucker Taft
Sent: Sunday, January 7, 2018  3:24 PM

...
> I was actually thinking of writing the AI to replace the Identity
> aspect with an Associative Boolean aspect. That seems more useful,
> since parallelism is not possible if a reducer function is not associative.

Both are relevant.  It is not an either/or.

> If the reducer function does not have the associative aspect,
> then'Reduce attribute would normally apply sequential processing. On
> the other hand, if the reduction function does have it, then parallel
> execution can potentially be applied by the implementation.
>
> A problem with the Identity aspect is that it is difficult to apply
> everywhere.

That's OK.  If there is no well-defined identity, then so be it.

> For example, the language defined bitwise "and" of;
>
> type Fingers is mod 5;
>
> is hard to define. You could say it is Fingers'Last, but then "and"ing
> that with 3, wouldn't work. You could say it is 7, but then the value
> is outside the range of values for the type, and its use could trigger
> constraint errors.

Right.  These non-power-of-2 modular types are weird in various ways, and
certainly don't have well-defined bit-wise boolean operators.  So these
operators wouldn't have a well-defined Identity aspect, which is fine, since
no-one in their right mind would use bit-wise boolean operators to reduce a
bunch of non-power-of-2 modular values.  But clearly addition and multiplication
have well-defined Identity aspects, even for such oddball modular types.  No
need to throw out the baby with the non-power-of-2 modular type bathwater!

> Using the logic that Jean-Pierre proposed, you don't have to define
> this, and the 'Reduce attribute works.
>
> I think the Associative aspect is a better replacement for 'Identity,
> because it can easily defined on all subprograms that need it. (And
> its simpler, being a boolean aspect)

There might still be reasons to define an Identity aspect, as it might be useful
for some purposes.  I don't see this as one "replaces" the other.  They should
all be optional, and only used for certain optimizations.

> I think we should not include the Identity aspect in this proposal
> unless someone can show a valid need for it. I would want to see some
> sort of explanation on how it can improve parallelism or understanding.

Well, "normal" reductions use identity quite a bit, but it seems fine to omit
it.  In general, I would try to separate this proposal into what is needed for
basic functionality, and what is useful for optimizations and parallelization.
The aspects should only be needed for optimizations, and never be required for
basic functionality.  And if we cannot agree on the aspects, or want to leave
them for a future AI, that seems fine.

>> ...
>> You might also want to allow a second version of this, that could
>> perhaps use the identical syntax, and be chosen when the "Reduce"
>> operation parameter is actually a procedure rather than a function:
>>
>>   (iterator)'Reduce(proc, initial_val)
>>
>> would expand into
>>
>>   tmp := initial_val
>>   while more in (iterator) loop
>>        proc(tmp, <next-val-of-(iterator)>);
>>   end loop;
>>   return tmp;
>
> I agree allowing a procedure for a reducer is useful, and probably
> worth considering for this version of the AI. We could say that it can
> be a procedure that accepts two parameters of the same type, where the first
> parameter is an in out parameter.

Right.  Though again, we could allow the second parameter to be of a different
type.

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

From: Tucker Taft
Sent: Monday, January 8, 2018  3:04 PM

...
> Regarding syntax... I realize we aren't talking about adding general
> lambdas to Ada, but does it make sense to choose a syntax that wouldn't
> prohibit such an addition in the future?

There is a separate AI on lambdas.  The latest syntax proposal for reduction
expressions (at least last time I checked!) is compatible with using a lambda
expression for the function name.  E.g.

    (for E of V => E**2)'Reduce("+", 0)  -- sum of squares

could have a lambda expression in place of the "+":

    (for E of V => E**2)'Reduce(<lambda-expression>, 0)

The proposed syntax for lambda expressions is currently defined in:

   http://www.ada-auth.org/cgi-bin/cvsweb.cgi/ai12s/ai12-0190-1.txt?rev=1.5

and uses a syntax like:

   (function (X, Y) return X + Y)

So the above example could be written as:

   (for E of V => E**2)'Reduce( (function (X, Y) return X+Y) , 0)

Obviously not a great example, but you could imagine more interesting functions.

As far as terminology, "fold" and "reduce" are clearly very similar in
semantics. The annoying thing about "fold" is that there are so many different
versions of it (foldl, foldl1, foldr, ...).  So we have chosen to use the term
"reduction" even though in some cases it might be closer to a "fold."

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

From: Peter Chapin
Sent: Monday, January 8, 2018  3:24 PM

Thanks! I'll take a look at that lambdas AI. As for the terminology, I don't
think it's a big deal. We have to call it something and "fold" is really
somewhat of an odd term in many ways. "Reduce" has the advantage of sounding
more like what is going on.

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

From: Brad Moore
Sent: Monday, January 8, 2018  7:17 PM

In private email, Jean-Pierre was questioning the need for an initial value as
an argument to the 'Reduce attribute, as it could be considered an error for
attempting to reduce 0 items.

This is something I've struggled with as well.

This got me to thinking that there probably are times when an exception is
wanted, and times when it is not.

For example,

-- Determine the maximum number of widgets that can be found at a particular
-- store brand near me. If the answer is 0, because there are no such stores,
-- or 0 because the stores that do exist are out of stock, I dont care, the
-- answer is still 0.
Max_Widgets : constant Integer :=
   (for Location in Stores when Location.City = Calgary)'Reduce(Integer'Max, 0);

-- On the other hand, there may not always be a clear value to use. Is it clear
-- that a result of Temperature'Min means that no cities were found, or that
-- is an actual value for the coldest settlement in Antartica?
Max_Temp : constant Temperature :=
   (for City of World
       when City.Continent = Antartica => City.Max_Temperature)'Reduce(Temperature'Max, Temperature'Min);

A nice feature of the 'Reduce attribute concept, is that we can have more than
one version of the attribute.

We could also have a version that only accepts one argument, the reducer
subprogram, and it raises constraint error if there are no items to be reduced.

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

From: Tucker Taft
Sent: Monday, January 8, 2018  7:41 PM

> In private email, Jean-Pierre was questioning the need for an initial
> value as an argument to the 'Reduce attribute, as it could be considered an
> error for attempting to reduce 0 items.
> ...
> A nice feature of the 'Reduce attribute concept, is that we can have more than
> one version of the attribute.
>
> We could also have a version that only accepts one argument, the
> reducer subprogram, and it raises constraint error if there are no items to be
> reduced.

I suppose, but I think you are over-thinking this.  It is very rare that you
really *want* an exception.  Let's keep this simple.  Yes there are a million
options imaginable, but to me that is where the foldl, foldl1, foldr, foldr1
madness arose.

A simple pragma Assert can always be inserted if you really want an exception
under certain conditions.

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

From: Randy Brukardt
Sent: Monday, January 8, 2018  9:28 PM

> I believe it is a serious mistake to have to create an array to do a
> reduction.  There are many cases when you want to do a reduction over
> a series of values that are produced in various ways.  Limiting it to
> arrays means you end up having to figure out how to create the array,
> and furthermore, you need to know in advance how big an array to
> allocate, or undergo the dynamic allocation implicit in a growable
> vector.

I don't think anyone was suggesting that the array would have to actually
be materialized. But the prefix of this attribute seems like it has to be
an array aggregate, as it has the syntax of an array aggregate. Saying that
the semantics of some construct is determined by 7 characters at the very
end -- many lines after the start -- seems like the wrong way to go.

So, my view was that the prefix was an object of some appropriate type, and
there would be a rule that the order of evaluation of the parts of the prefix
and the 'Reduce itself are unspecified (probably would take a notwithstanding
rule). I suppose that means that the attribute would have to be able to handle
an existing array object, but that doesn't seem like a problem.

> Using a generalized iterator (including a filter of some
> sort) is significantly more flexible and potentially hugely more time
> and space efficient.

Since container aggregates need to be able to contain generalized iterators, I
don't see a difference here. Certainly, as-if optimizations are always allowed,
and we'll have to make the order of evaluation unspecified if any parallelism is
going to be applied.

---

One note here is that an aggregate standing by itself isn't currently a legal
attribute prefix. But a qualified aggregate is legal, so I don't think there
would be any significant issue with allowing an aggregate as a prefix. Probably
would want to allow any expression so long as it was in parens. (Note that we
just rejected this idea in terms of Obj'Image, but I guess we're allowed to
change our mind.)

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

From: Randy Brukardt
Sent: Monday, January 8, 2018  10:34 PM

...
> The semantics of "(iterator)'Reduce(func, initial_val) would be
> simply:

There's a stray quote above that confused me for a while.

>     tmp := initial_val;
>     while more in (iterator) loop
>         tmp := func (tmp, <next-val-of-(iterator)>);
>     end loop;
>     return tmp;

Or more conventionally:

    declare
       tmp : <reducer type> := initial_val;
    begin
       for <id> <rest of iterator> loop
           tmp := func (tmp, <id>);
       end loop;
       Result := tmp; -- Or "return tmp" if this is a function.
    end;

(Here, Tucker's "(iterator)" is expanded a bit to be clearer.)

And this illustrates the problem I have with this whole idea. My goal for the
Ada 2020 is to have safe-by-construction parallelism features that can be added
to improve the performance of *existing* Ada code.

Thus, my hope would be that one could add parallelism to a loop simply by adding
"parallel" to the iterator specification (with possibly a small amount of change
to that specification). That assumes, of course, that the operations in the body
can be operated in parallel.

The problem is, of course, that that isn't quite possible for loops that involve
some sort of result. Just adding "parallel" to the  ought to get a error because
the use of "tmp" is not task-safe.

The solution to that problem that we're proposing is to completely abandon
conventional loops and switch to a functional notation. That's going to be hard
to do for existing code; discovering the reduction function and variable is
going to be hard in real loops (which are a lot more complex than the above, and
often have a number of variables to construct a result). It requires turning the
entire loop inside-out (and often creating helper types and functions, if there
is more than a single result object).

New code won't be much better; users will be required to think functionally
about reductions, but Ada is nowhere near a complete functional language (and it
would be impractical to allow things like general closures, so that isn't likely
to change), so one will then have to switch mental gears halfway through. It
sounds like the worst of both worlds to me.

At one point (Pittsburgh), we had a reasonable but unfinished solution that
looked a whole lot more like standard Ada. My recollection was that the main
problem was that the accumulator objects could be used as arrays, but I don't
know why we would make that property visible. (No one needs to access these
explicitly as arrays).

That would give something like:

    declare
       tmp : parallel <reducer type> := initial_val;
    begin
       parallel for <id> <rest of iterator> loop
           tmp := func (tmp, <id>);
       end loop;
       Result := tmp; -- Or "return tmp" if this is a function.
    end;

The idea being that "tmp" acts like a set of objects, one per tasklet, inside of
a parallel construct, but as a single object outside of such constructs. To get
from the set to the single object, the reducer/identity for the reducer type
would be used by default, or one could specify them with aspects as needed.

This looks a lot more like conventional Ada code, and certainly would be easier
to apply to existing loops than a reduction expression. And much less likely to
require frequent gear-switching in new code.

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

From: Jean-Pierre Rosen
Sent: Monday, January 8, 2018  11:42 PM

> In private email, Jean-Pierre was questioning the need for an initial
> value as an argument to the 'Reduce attribute, as it could be considered
> an error for attempting to reduce 0 items.

Oops, I didn't want to make it private. Thunderbird changed its UI recently, and
I keep hitting "Reply" instead of "Reply to all"...

For the record, here it is:
-------------------------------------------
Le 07/01/2018 à 19:04, Brad Moore a écrit :
> I don't think we want the user to have to worry about handling such
> constraint errors. That's why we have the initial_value. You get that
> result if you are trying to apply 'Reduce to a null array, or an empty
> iterated_component_association. Having to deal with exceptions makes
> it more difficult to use with contracts for example.

But isn't reducing 0 values an error? The maximum of 0 elements is certainly not
Integer'First!

[...]
> I think we can (and probably should) get rid of the 'Identity aspect
> with either proposal. I don't think it is needed. For tasklets where
> Initial_Value is not being applied, the initial value can be the value
> of the first item. If there are more than one item per tasklet, the
> Reducer function can be applied to combine the first and subsequent
> results.

Agreed, that's what I propose.

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

From: Brad Moore
Sent: Thursday, January 11, 2018  1:56 AM

> ...
>> The semantics of "(iterator)'Reduce(func, initial_val) would be
>> simply:
>
> There's a stray quote above that confused me for a while.
>
>>     tmp := initial_val;
>>     while more in (iterator) loop
>>         tmp := func (tmp, <next-val-of-(iterator)>);
>>     end loop;
>>     return tmp;
>
> Or more conventionally:
>
>    declare
>       tmp : <reducer type> := initial_val;
>    begin
>       for <id> <rest of iterator> loop
>           tmp := func (tmp, <id>);
>       end loop;
>       Result := tmp; -- Or "return tmp" if this is a function.
>    end;
>
> (Here, Tucker's "(iterator)" is expanded a bit to be clearer.)
>
> And this illustrates the problem I have with this whole idea. My goal
> for the Ada 2020 is to have safe-by-construction parallelism features
> that can be added to improve the performance of *existing* Ada code.
>
> Thus, my hope would be that one could add parallelism to a loop simply
> by adding "parallel" to the iterator specification (with possibly a
> small amount of change to that specification). That assumes, of
> course, that the operations in the body can be operated in parallel.
>
> The problem is, of course, that that isn't quite possible for loops
> that involve some sort of result. Just adding "parallel" to the  ought
> to get a error because the use of "tmp" is not task-safe.
>
> The solution to that problem that we're proposing is to completely
> abandon conventional loops and switch to a functional notation. That's
> going to be hard to do for existing code; discovering the reduction
> function and variable is going to be hard in real loops (which are a
> lot more complex than the above, and often have a number of variables to
> construct a result). It requires turning the entire loop inside-out (and
> often creating helper types and functions, if there is more than a single
> result object).

I really think in some cases users wont mind deleting an existing loop such as;

declare
   Sum : Integer := 0;
begin

   for I in 1 .. 1000 loop
      Sum := Sum + A(I);
   end loop

   Put_Line ("Sum of A=" & Integer'Image(Sum); end

and replacing with;

Put_Line ("Sum of A=" & Integer'Image(A'Reduce("+", 0)));

> New code won't be much better; users will be required to think
> functionally about reductions, but Ada is nowhere near a complete
> functional language (and it would be impractical to allow things like
> general closures, so that isn't likely to change), so one will then
> have to switch mental gears halfway through. It sounds like the worst of
> both worlds to me.
>
> At one point (Pittsburgh), we had a reasonable but unfinished solution
> that looked a whole lot more like standard Ada. My recollection was
> that the main problem was that the accumulator objects could be used
> as arrays, but I don't know why we would make that property visible.
> (No one needs to access these explicitly as arrays).
>
> That would give something like:
>
>    declare
>       tmp : parallel <reducer type> := initial_val;
>    begin
>       parallel for <id> <rest of iterator> loop
>           tmp := func (tmp, <id>);
>       end loop;
>       Result := tmp; -- Or "return tmp" if this is a function.
>    end;
>
> The idea being that "tmp" acts like a set of objects, one per tasklet,
> inside of a parallel construct, but as a single object outside of such
> constructs. To get from the set to the single object, the
> reducer/identity for the reducer type would be used by default, or one
> could specify them with aspects as needed.
>
> This looks a lot more like conventional Ada code, and certainly would
> be easier to apply to existing loops than a reduction expression. And
> much less likely to require frequent gear-switching in new code.

I can see that having both 'Reduce and parallel loop with reduction capabilities
would be appreciated by users.

I think there will be times when one or the other is a better choice for a
particular usage, and a 'Reduce attribute I believe will also have utility
beyond just parallelism.

What I am finding is that both forms need common support for parallelism.

I think both need subprograms to be annotated with an Associated aspect, as well
as the Reducer aspect that we had in earlier versions of the AI.

What I'd like to do, is carve out another AI from AI12-00119 that just has
wording for describing tasklets, executors, the Associated aspect, and Reducer
aspect. This would also have the changes to the containers and libraries to have
these attributes added.


It looks to me like this will be the most work to nail down in the RM. I think
the Associated aspect can borrow much of the wording that we currently have for
the NonBlocking aspect, except change occurrences of NonBlocking for Associated.

Then the Parallel Operations AI can be a lot better focused. The 'Reduce AI I
think will also be quite a lot simpler to write up, as both can reference the
tasklet AI.

Sound OK?

By having these in separate AI's we can discuss the pros and cons of each
feature based on their own merits, without having to look at the common support
as much, since that is needed for either solution anyways.

And yes, Randy, I will be sure to take your latest version of AI12-00119 as a
starting point. Thanks for your input.


On an aside, I did an experiment today where I wrote a parallel loop that
calculates 3 results, a sum of a set of values, the min of a set of values, and
the max of a set of values.

I was curious to see if writing this as three separate loops would be better or
worse than creating a composite object and writing a reducer function that can
combine results of this record type.

I found that writing as 3 separate loops was significantly faster than 1 loop.

For a loop that involves 4_000_000_000 iterations, the 3 loop solution took
11.17 seconds. The single loop took 18.29 seconds. Why bring this up?

The 'Reduce approach encourages users to write 3 separate 'Reduce expressions,
whereas the parallel loop approach encourages users to write a single loop with
3 results, which I found is easiest to implement in Paraffin if the 3 results
are combined into a single result type.

So it may be that using 'Reduce can result in significantly better performance
results than a parallel loop approach, for certain problems at least.

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

From: Randy Brukardt
Sent: Thursday, January 11, 2018  3:23 AM

...
> I really think in some cases users wont mind deleting an existing loop
> such as;
>
> declare
>    Sum : Integer := 0;
> begin
>
>    for I in 1 .. 1000 loop
>       Sum := Sum + A(I);
>    end loop
>
>    Put_Line ("Sum of A=" & Integer'Image(Sum); end
>
> and replacing with;
>
> Put_Line ("Sum of A=" & Integer'Image(A'Reduce("+", 0)));

Actually, they probably will, because the latter might very well run 10 times
slower. (It certainly will if the compiler tries to parallelize it, since
setup/teardown of a tasklet probably will take a lot more than 250 integer adds;
it might even if left sequential, as compilers have been optimizing the former
for 40 years and probably will generate only 4 or 5 x86 machine instructions for
the former -- but the patterns are likely to be very specific to the existing
format and won't work on the slightly different organization of a reduction.)

Indeed, some hardware has instructions specifically for loops like this. It
might end up running in microcode and there's no way that any other feature
could beat that.

Besides, real loops that need to run faster don't look like this. They look
like:

	-- Now, calculate the various running totals:
	for I in 1 .. Actual_Len loop
	    if Sample_Data(I).Check_Item then
		-- Note: We used to calculate Sample_Count,
		-- Actual_Sum, and Actual_Sqr_Sum here, but we've
		-- removed these as this is likely the innermost loop
		-- for the program.
		if Sample_Data(I).Score <= 0.0 then
		    Negative_Count := Negative_Count + 1;
		end if;
		Sample_Sum := Sample_Sum + Sample_Data(I).Score;
		Sample_Sqr_Sum := Sample_Sqr_Sum + (Sample_Data(I).Score*Sample_Data(I).Score);
		Product_Sum := Product_Sum +
	            (Actual_Data(I).Weighted_Worse_Ratio*Sample_Data(I).Score);
		Diff_Sum := Diff_Sum +
		    (Actual_Data(I).Weighted_Worse_Ratio - Sample_Data(I).Score);
		Diff_Sqr_Sum := Diff_Sqr_Sum +
		    (Actual_Data(I).Weighted_Worse_Ratio - Sample_Data(I).Score)**2;
	        if Result_Debug or else (Limited_Calc_Debug and then (I <= Debug_Calc_Limit or else I >= Actual_Len - Debug_Calc_Limit)) then
		    Ada.Text_IO.Put_Line ("Item " & Actual_Data(I).Item_Name & "; cnt="
			    & Natural'Image(Actual_Count));
		    Ada.Text_IO.Put("Sample Score="); LFlt_IO.Put (Sample_Data(I).Score, 10,6,0);
		    Ada.Text_IO.Put("; Actual Score="); LFlt_IO.Put (Actual_Data(I).Weighted_Worse_Ratio, 10,6,0);
	            Ada.Text_IO.New_Line;
		    --Ada.Text_IO.Put("Sample Sum="); LFlt_IO.Put (Sample_Sum, 10,6,0);
		    --Ada.Text_IO.Put("; Sample Sum**2="); LFlt_IO.Put (Sample_Sqr_Sum, 10,6,0);
	            --Ada.Text_IO.New_Line;
		    --Ada.Text_IO.Put("Actual Sum="); LFlt_IO.Put (Actual_Sum, 10,6,0);
		    --Ada.Text_IO.Put("; Actual Sum**2="); LFlt_IO.Put (Actual_Sqr_Sum, 10,6,0);
	            --Ada.Text_IO.New_Line;
		    --Ada.Text_IO.Put("Product Sum="); LFlt_IO.Put (Product_Sum, 10,6,0);
		    --Ada.Text_IO.Put("; Diff Sum="); LFlt_IO.Put (Diff_Sum, 10,6,0);
		    --Ada.Text_IO.Put("; Diff Sum**2="); LFlt_IO.Put (Diff_Sqr_Sum, 10,6,0);
	            --Ada.Text_IO.New_Line;
		-- else no trace
		end if;
	    -- else do not score this pair.
	    end if;
	end loop;

This is the operative loop of a correlation calculator, comparing an array of
actual values to an array of (proposed) estimated values. The array length is
tends to be as much as 4000 items. (Note that the two values that only depend on
Actual_Data are precalculated, since Actual_Data never changes for a particular
run, while the Sample_Data is regenerated for each trial.)

Among other things, one wonders where the debugging would go in a reduction. If
the reduction gives dubious results, you'll have to end up writing a
conventional loop to figure out why (no I/O is allowed in parallel operations,
since it allows blocking, and even when it is, you can't trace the intermediate
results).

Another thing about this code is that common subexpression elimination means
that many of the memory reads are eliminated (or should be, anyway). For
instance, Sample_Data(I).Score should be loaded into a register and only read
once. The reduced memory traffic provides a substantial speed-up to the code.

...
> It looks to me like this will be the most work to nail down in the RM.
> I think the Associated aspect can borrow much of the wording that we
> currently have for the NonBlocking aspect, except change occurrences
> of NonBlocking for Associated.

Why? I though "associated" just specified that an operation is associative; that
doesn't change the semantics of an operation that calls it. All of the
(substantial) complication of nonblocking comes because one can't allow a call
(anywhere) of an operation that allows blocking, so the property has to
propagate. Don't see why "associative" would have to propagate.

Or is "associated" supposed to be something completely different? I don't
remember seeing anything about it previously...

> Then the Parallel Operations AI can be a lot better focused.
> The 'Reduce AI I think
> will also be quite a lot simpler to write up, as both can
> reference the tasklet AI.
>
> Sound OK?

I don't really see the point, since 'Reducer is trivial (it's a Boolean and
isn't transitive), the same should be true for 'Associative, and the basic
parallel loop proposal (which doesn't support any reductions) can provide all of
the tasklet stuff (there isn't much).

I'd expect that any reduction proposal would be in a separate AI (or perhaps
alternative AIs). If we decided to adopt multiple proposals, we could worry
about eliminating duplication, but I do that sort of thing all of the time.

...
> On an aside, I did an experiment today where I wrote a parallel loop
> that calculates 3 results, a sum of a set of values, the min of a set
> of values, and the max of a set of values.
>
> I was curious to see if writing this as three separate loops would be
> better or worse than creating a composite object and writing a reducer
> function that can combine results of this record type.
>
> I found that writing as 3 separate loops was significantly faster than
> 1 loop.
>
> For a loop that involves 4_000_000_000 iterations, the 3 loop solution
> took 11.17 seconds. The single loop took
> 18.29 seconds. Why bring this up?

Because you're testing the wrong thing?

All you've proved here is that Ada has lousy support for tuple-based
programming. I'd be very surprised of any formulation that uses functions
returning composite types would have decent performance doing anything.

If you *really* wanted to test this, you would have used a Reducer *procedure*
to combine the records. The overhead of a single in out parameter is likely to
be many times less than a function return (which is creating an object for each
iteration).

But you'd also have to test whether the approach of writing a single
conventional loop is faster or slower than any parallelism. The overhead of a
loop, especially a parallel loop, can be substantial.

> The 'Reduce approach encourages users to write 3 separate 'Reduce
> expressions, whereas the parallel loop approach encourages users to
> write a single loop with 3 results, which I found is easiest to
> implement in Paraffin if the
> 3 results are combined into a single result type.
>
> So it may be that using 'Reduce can result in significantly better
> performance results than a parallel loop approach, for certain
> problems at least.

Comparing one insane solution (writing a function returning a record, requiring
extra type and function declarations) to a second insane solution (writing the
iterator part repeatedly, with all of the possibilities of error with that)
hardly seems valuable. Both solutions require writing a lot of extra text
compared to the sequential loop, and both seem to require turning the loop
inside out.

The big thing this demostrates is that Ada is a long way from really supporting
functional programming, and it probably never will be able to do that AND have
performance. (Ada doesn't handle tuples easily, and IMHO it shouldn't.)

In any case, a parallel loop is not going to fix every performance problem. Any
problem made up of reducers that are simple machine instructions (like "+" or
"Min") are probably going to be fastest without any parallelism at all. (And
will take the least text if there is only one loop!) You'd need 100s of
thousands of iterations for those to matter, and there aren't that many real
problems with that many iterations.

But there are a lot of problems with expensive iterations that might be helped.
And with expensive setups that would be costly to repeat. (And note the above
comments about common subexpression elimination. If you converted my example
into 5 loops, you'd have to redo all of the memory reads of .Score 5 times,
while the original loop only would do each read once. That would add a lot of
slowdown.

Perhaps you'd like to retry your experiment with my example above? I suspect the
results would be somewhat (or maybe a lot) different.

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

From: Brad Moore
Sent: Thursday, January 11, 2018  3:59 PM

> ...
>> I really think in some cases users wont mind deleting an existing
>> loop such as;
>>
>> declare
>>    Sum : Integer := 0;
>> begin
>>
>>    for I in 1 .. 1000 loop
>>       Sum := Sum + A(I);
>>    end loop
>>
>>    Put_Line ("Sum of A=" & Integer'Image(Sum); end
>>
>> and replacing with;
>>
>> Put_Line ("Sum of A=" & Integer'Image(A'Reduce("+", 0)));
>
> Actually, they probably will, because the latter might very well run
> 10 times slower. (It certainly will if the compiler tries to
> parallelize it, since setup/teardown of a tasklet probably will take a
> lot more than 250 integer adds; it might even if left sequential, as
> compilers have been optimizing the former for 40 years and probably
> will generate only 4 or 5
> x86 machine instructions for the former -- but the patterns are likely
> to be very specific to the existing format and won't work on the
> slightly different organization of a reduction.)

I disagree with this assessment. I would expect that a 'Reduce implementation
would generate the same code as a corresponding parallel loop, under the covers,
assuming only a single reduction result is needed.

For instance if a Paraffin like library was being called under the covers, the
same calls could be applied.

...
> Among other things, one wonders where the debugging would go in a reduction.
> If the reduction gives dubious results, you'll have to end up writing
> a conventional loop to figure out why (no I/O is allowed in parallel
> operations, since it allows blocking, and even when it is, you can't
> trace the intermediate results).

'Reduce is simple enough that there's nothing much to debug typically.

Reducers like Integer'Min, or "+", etc doesn't need debugging, and the rest of
the parallelism is provided by the implementation. There's a lot less to go
wrong.

I think if a loop is complex, then you are better off using a parallel loop,
then you can also insert debugging code more easily.

> Another thing about this code is that common subexpression elimination
> means that many of the memory reads are eliminated (or should be,
> anyway). For instance, Sample_Data(I).Score should be loaded into a
> register and only read once. The reduced memory traffic provides a
> substantial speed-up to the code.
>
> ...
>> It looks to me like this will be the most work to nail down in the RM.
>> I think the Associated aspect can borrow much of the wording that we
>> currently have for the NonBlocking aspect, except change occurrences
>> of NonBlocking for Associated.
>
> Why? I though "associated" just specified that an operation is
> associative; that doesn't change the semantics of an operation that
> calls it. All of the
> (substantial) complication of nonblocking comes because one can't
> allow a call (anywhere) of an operation that allows blocking, so the
> property has to propagate. Don't see why "associative" would have to
> propagate.

I think we'd also want to something similar where the compiler might warn the
user that a 'Reduce cannot be done in parallel. Similarly, you might want to
allow 'Associative on generic formals, then you would need to disallow an actual
that isn't associative. You might also want to query an attribute, like you can
for NonBlocking.

> Or is "associated" supposed to be something completely different? I
> don't remember seeing anything about it previously...

The idea is that it is a boolean aspect that can be applied to a binary function
where both parameters and result are of the same type. , or to a binary
procedure where both parameters are the same type, and one of the parameters is
an in out.

All it says is that semantically, you get the same result, regardless which
actual gets passed in which parameter. (e.g  A + B = B + A) for Integer "+"

>> Then the Parallel Operations AI can be a lot better focused.
>> The 'Reduce AI I think
>> will also be quite a lot simpler to write up, as both can reference
>> the tasklet AI.
>>
>> Sound OK?
>
> I don't really see the point, since 'Reducer is trivial (it's a
> Boolean and isn't transitive), the same should be true for
> 'Associative, and the basic parallel loop proposal (which doesn't
> support any reductions) can provide all of the tasklet stuff (there isn't
> much).

The Reducer aspect I am talking about is an aspect that can be applied to a
binary function or procedure where the two parameters are not of the same type.
It identifies another subprogram that has the Associative aspect, to be used
when combining results from a subprogram that has the Reducer aspect.

eg.

In Ada.Containers.Vectors...

   function "&" (Left, Right : Vector) return Vector with Associative;

   function "&" (Left : Vector; Right : Element_Type) return Vector with Reducer => "&";

The Reducer aspect names another function that has the Associative aspect.

You can then, for instance, append Characters to a Vector in parallel.
Otherwise, you could only concatenate vectors together in parallel.

> I'd expect that any reduction proposal would be in a separate AI (or
> perhaps alternative AIs). If we decided to adopt multiple proposals,
> we could worry about eliminating duplication, but I do that sort of thing all of the time.
>
> ...
>> On an aside, I did an experiment today where I wrote a parallel loop
>> that calculates 3 results, a sum of a set of values, the min of a set
>> of values, and the max of a set of values.
>>
>> I was curious to see if writing this as three separate loops would be
>> better or worse than creating a composite object and writing a
>> reducer function that can combine results of this record type.
>>
>> I found that writing as 3 separate loops was significantly faster
>> than 1 loop.
>>
>> For a loop that involves 4_000_000_000 iterations, the 3 loop
>> solution took 11.17 seconds. The single loop took
>> 18.29 seconds. Why bring this up?
>
> Because you're testing the wrong thing?
>
> All you've proved here is that Ada has lousy support for tuple-based
> programming. I'd be very surprised of any formulation that uses
> functions returning composite types would have decent performance doing anything.

Actually this works surprisingly well even for composites. I have updated my
program to produce a more information, and I think the results are quite
interesting.

I have also implemented Randy's test program from his previous email, and yes
that does also provide some interesting results that are quite different. See
even farther below.


With Optimization turned off in GNAT with 4 cores I ran the following tests on
my program which produced the following results.

1. Calculation of Sum of adding 1, 8_000_000_000 times using a sequential loop
2. Doing the same, but with a parallel loop
3. Calculate the sum as before, but also calculate min and max of the loop
   index, in 3 separate sequential loops
4. Do 3 again, but using 3 separate parallel loops.
5. Do all 3 calculations on a composite result in a single parallel loop using
   functional reduction. The calculation of results in each tasklet is done
   using a procedure, but the reduction between tasklets is done using a
   function, which is also used to provide the final result.
6. Do 5, except use a procedural reduction library. All reduction calls and
   final result are via a procedure in out parameter
7. Do 2, except instead of using my own Paraffin library, use Ada code passed
   to OpenMP library
8. Do 4, except use my OpenMP bindings from Ada.
9. Do 6, except use my OpenMP bindings from Ada.

We see here that using 3 separate parallelism loops ends up being twice as fast
as sequential. However, using composite record types, the performance is not
even worthwhile, as it is worse or at least roughly equivalent as sequential.

My suspicion is that having to use record types in comparison with elementary
types can add a significant amount of overhead. Probably the elementary types
can be processed more using hardware registers, etc.

Interesting things happen when I turn on optimization though. Skip down to see
those results.


************* Parallel Framework Test *************
  Physical Processors= 4

Single operation in a sequential Loop

{Elapsed = 00:00:19.25
Sum= 8000000000


Single Operation Parallelism Loop

{Elapsed = 00:00:05.30
Sum= 8000000000


3 operations in a sequential Loop

{Elapsed = 00:00:28.14
Sum= 8000000000, Min= 1, Max= 8000000000


3 Separate Parallelism Loops

{Elapsed = 00:00:15.64
Sum= 8000000000, Min= 1, Max= 8000000000


Single Functional Parallelism Loops

{Elapsed = 00:00:29.70
Sum= 8000000000, Min= 1, Max= 8000000000


Single Procedural Parallelism Loops

{Elapsed = 00:00:30.28
Sum= 8000000000, Min= 1, Max= 8000000000


Single Operation OpenMP Parallelism Loop

{Elapsed = 00:00:04.66
Sum= 8000000000


3 Separate OpenMP Parallelism Loops

{Elapsed = 00:00:15.55
Sum= 8000000000, Min= 1, Max= 8000000000


Single OpenMP Parallelism Loops

{Elapsed = 00:02:39.06
Sum= 8000000000, Min= 1, Max= 8000000000


----------------

Now after turning on full optimization in GNAT, I get the following results for
the same tests.


************* Parallel Framework Test *************
  Physical Processors= 4

Single operation in a sequential Loop

{Elapsed = 00:00:00.00
Sum= 8000000000


Single Operation Parallelism Loop

{Elapsed = 00:00:02.07
Sum= 8000000000


3 operations in a sequential Loop

{Elapsed = 00:00:08.24
Sum= 8000000000, Min= 1, Max= 8000000000


3 Separate Parallelism Loops

{Elapsed = 00:00:04.14
Sum= 8000000000, Min= 1, Max= 8000000000


Single Functional Parallelism Loops

{Elapsed = 00:00:05.30
Sum= 8000000000, Min= 1, Max= 8000000000


Single Procedural Parallelism Loops

{Elapsed = 00:00:05.31
Sum= 8000000000, Min= 1, Max= 8000000000


Single Operation OpenMP Parallelism Loop

{Elapsed = 00:00:02.09
Sum= 8000000000


3 Separate OpenMP Parallelism Loops

{Elapsed = 00:00:04.19
Sum= 8000000000, Min= 1, Max= 8000000000


Single OpenMP Parallelism Loops

{Elapsed = 00:00:17.29
Sum= 8000000000, Min= 1, Max= 8000000000

Interesting that a single operation, (sum) doesn't even register a time.
But when you try to do more than one, then there can be parallelism benefits.

But even with optimization turned on, you get better performance using 3
separate loops, although now at least there is at least some benefit to using a
single loop.

> If you *really* wanted to test this, you would have used a Reducer
> *procedure* to combine the records. The overhead of a single in out
> parameter is likely to be many times less than a function return
> (which is creating an object for each iteration).

In all my testing with Paraffin, I have found surprisingly that there never is
much of a difference between using a function vs a procedure. You can see that
in the results above.

> But you'd also have to test whether the approach of writing a single
> conventional loop is faster or slower than any parallelism. The
> overhead of a loop, especially a parallel loop, can be substantial.

I show that above in the results also. You can see the speedup vs sequential
code.

>> The 'Reduce approach encourages users to write 3 separate 'Reduce
>> expressions, whereas the parallel loop approach encourages users to
>> write a single loop with 3 results, which I found is easiest to
>> implement in Paraffin if the
>> 3 results are combined into a single result type.
>>
>> So it may be that using 'Reduce can result in significantly better
>> performance results than a parallel loop approach, for certain
>> problems at least.
>
> Comparing one insane solution (writing a function returning a record,
> requiring extra type and function declarations) to a second insane
> solution (writing the iterator part repeatedly, with all of the
> possibilities of error with that) hardly seems valuable. Both
> solutions require writing a lot of extra text compared to the
> sequential loop, and both seem to require turning the loop inside out.
>
> The big thing this demostrates is that Ada is a long way from really
> supporting functional programming, and it probably never will be able
> to do that AND have performance. (Ada doesn't handle tuples easily,
> and IMHO it
> shouldn't.)

I think the results above show that it actually does handle tuples pretty well.

> In any case, a parallel loop is not going to fix every performance problem.
> Any problem made up of reducers that are simple machine instructions
> (like "+" or "Min") are probably going to be fastest without any
> parallelism at all. (And will take the least text if there is only one
> loop!) You'd need 100s of thousands of iterations for those to matter,
> and there aren't that many real problems with that many iterations.

I see benefits to parallelism with both optimization turned off or on, even for
these simple operations.

> But there are a lot of problems with expensive iterations that might
> be helped. And with expensive setups that would be costly to repeat.
> (And note the above comments about common subexpression elimination.
> If you converted my example into 5 loops, you'd have to redo all of
> the memory reads of .Score 5 times, while the original loop only would
> do each read once. That would add a lot of slowdown.
>
> Perhaps you'd like to retry your experiment with my example above? I
> suspect the results would be somewhat (or maybe a lot) different.

I did just that, and created another test program.

This program runs the code sequentially, then as separate parallel loops one for
each result, then a single loop using a composite result type.

First are the results with optimization turned off.

************* Parallel Framework Test *************
  Physical Processors= 4

Multiple operations in a sequential Loop

{Elapsed = 00:00:01.45
Negative_Count= 0
Sample_Sum= 1.99965350799589E+07
Sample_Sqr_Sum= 1.33299985832170E+07
Product_Sum= 1.99965350799589E+07
Diff_Sum= 2.00046739200409E+07
Diff_Sqr_Sum= 1.33381374236478E+07


Multiple parallel loops

{Elapsed = 00:00:01.38
Negative_Count= 0
Sample_Sum= 1.99965350797953E+07
Sample_Sqr_Sum= 1.33299985832053E+07
Product_Sum= 1.99965350797953E+07
Diff_Sum= 2.00046739202047E+07
Diff_Sqr_Sum= 1.33381374236362E+07


Single parallel loop

{Elapsed = 00:00:00.42
Negative_Count= 0
Sample_Sum= 1.99965350797952E+07
Sample_Sqr_Sum= 1.33299985832053E+07
Product_Sum= 1.99965350797952E+07
Diff_Sum= 2.00046739202047E+07
Diff_Sqr_Sum= 1.33381374236363E+07

---------------------------------

Then I run it again with optimization turned on....

************* Parallel Framework Test *************
  Physical Processors= 4

Multiple operations in a sequential Loop

{Elapsed = 00:00:00.62
Negative_Count= 0
Sample_Sum= 1.99965350799589E+07
Sample_Sqr_Sum= 1.33299985832170E+07
Product_Sum= 1.99965350799589E+07
Diff_Sum= 2.00046739200409E+07
Diff_Sqr_Sum= 1.33381374236478E+07


Multiple parallel loops

{Elapsed = 00:00:00.94
Negative_Count= 0
Sample_Sum= 1.99965350797953E+07
Sample_Sqr_Sum= 1.33299985832053E+07
Product_Sum= 1.99965350797952E+07
Diff_Sum= 2.00046739202048E+07
Diff_Sqr_Sum= 1.33381374236362E+07


Single parallel loops

{Elapsed = 00:00:00.20
Negative_Count= 0
Sample_Sum= 1.99965350797950E+07
Sample_Sqr_Sum= 1.33299985832052E+07
Product_Sum= 1.99965350797950E+07
Diff_Sum= 2.00046739202050E+07
Diff_Sqr_Sum= 1.33381374236362E+07


With optimization turned off, there is only a slight benefit to using separate
loops, but there is a big advantage to using a single loop.

With optimization turned on, using parallelism with separate loops is quite a
bit worse than sequential.

However, using a single loop is about 3 times faster. So the results from this
program are pretty much the reverse of what you get with my program.

So to summarize all this,

I'd say that as the complexity of a loop increases, it is better and easier to
use a parallel loop.

As the complexity of a loop decreases, it is likely better and easier to use a
'Reduce call.

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

From: Randy Brukardt
Sent: Thursday, January 11, 2018  10:40 PM

...
> > Actually, they probably will, because the latter might very well run
> > 10 times slower. (It certainly will if the compiler tries to
> > parallelize it, since setup/teardown of a tasklet probably will take
> > a lot more than 250 integer adds; it might even if left sequential,
> > as compilers have been optimizing the former for 40 years and
> > probably will generate only 4 or 5
> > x86 machine instructions for the former -- but the patterns are
> > likely to be very specific to the existing format and won't work on
> > the slightly different organization of a reduction.)
>
> I disagree with this assessment. I would expect that a 'Reduce
> implementation would generate the same code as a corresponding
> parallel loop, under the covers, assuming only a single reduction
> result is needed.

I think you missed my point. For the 1000 iterations in the original example,
highly optimized sequential loop code probably would clobber any attempt at a
parallel loop, as creation/ending synch on the tasklets would far outweigh the
cost of doing 1000 iterations (most likely with all of the critical stuff in
registers).

You saw an extreme case of this in your simple test program with optimization
on, as GNAT recognized that the loop didn't do anything very interesting other
than waste time and replaced the entire thing with the result of 8_000_000. Not
doing a loop is going to beat doing a loop any time. ;-)

The other part of my point is that a *sequential* reduce expression might not
get the benefit of those optimizations, because the setup and organization would
be somewhat different. Some of these optimizations tend to be pattern matching,
where a known pattern is recognized and replaced with something much simpler; if
the code is slightly different, the pattern doesn't match and the optimization
doesn't get done. Obviously, that would be very implementation-specific, so it's
hard to say much more about that.

...
> I think if a loop is complex, then you are better off using a parallel
> loop, then you can also insert debugging code more easily.

Other than that we don't have a way to do reductions currently in a parallel
loop. :-)

Note that I'd be happy to finish the current version of the parallel loop AI
without worrying about reducers, and deal with the reducer issues separately.
(That would at least let us make some progress.)

> > ...
> >> It looks to me like this will be the most work to nail down in the RM.
> >> I think the Associated aspect can borrow much of the wording that
> >> we currently have for the NonBlocking aspect, except change
> >> occurrences of NonBlocking for Associated.
> >
> > Why? I though "associated" just specified that an operation is
> > associative; that doesn't change the semantics of an operation that
> > calls it. All of the (substantial) complication of nonblocking comes
> > because one can't allow a call (anywhere) of an operation that
> > allows blocking, so the property has to propagate. Don't see why "associative"
> > would have to propagate.
>
> I think we'd also want to something similar where the compiler might
> warn the user that a 'Reduce cannot be done in parallel.

Warnings are not the Standard's concern. OTOH, I would like to have a way to
tell the compiler whether to parallelize (or not) a reduction expression, since
it doesn't in general have the information needed to make that choice. It can't
find out the number of iterations nor how expensive the reduction function is
(in special cases it can, like statically bounded iterations with a predefined
operator as a reduction function). Having to make a runtime choice would mean
essentially generating all of the code twice (once for a parallel reduction, and
once for a sequential reduction), and always choosing parallel would make most
reductions pretty slow (you need a significant amount of work - either
iterations or in the function body - before parallelizing will help anything).

> Similarly, you might want to allow 'Associative on generic formals,
> then you would need to disallow an actual that isn't associative. You
> might also want to query an attribute, like you can for NonBlocking.

That's still many times simpler than Nonblocking. Because Nonblocking controls
legality rules in bodies for which it is true, but we have cases where you don't
know the value until the generic is instantiated. You don't need any of that.

> > Or is "associated" supposed to be something completely different? I
> > don't remember seeing anything about it previously...
>
> The idea is that it is a boolean aspect that can be applied to a
> binary function where both parameters and result are of the same type.
> , or to a binary procedure where both parameters are the same type,
> and one of the parameters is an in out.
>
> All it says is that semantically, you get the same result, regardless
> which actual gets passed in which parameter. (e.g A + B = B + A) for
> Integer "+"

Um, that's "commutative". :-)

An associative operator is one for which (A + B) + C = A + (B + C). My
understanding is that was the only requirement needed to allow parallel
reduction (because we don't know which one we'd want to do first, but it is easy
enough to keep Left things on the left and Right things on the right).

> >> Then the Parallel Operations AI can be a lot better focused.
> >> The 'Reduce AI I think
> >> will also be quite a lot simpler to write up, as both can reference
> >> the tasklet AI.
> >>
> >> Sound OK?
> >
> > I don't really see the point, since 'Reducer is trivial (it's a
> > Boolean and isn't transitive), the same should be true for
> > 'Associative, and the basic parallel loop proposal (which doesn't
> > support any reductions) can provide all of the tasklet stuff (there
> > isn't much).
>
> The Reducer aspect I am talking about is an aspect that can be applied
> to a binary function or procedure where the two parameters are not of
> the same type. It identifies another subprogram that has the
> Associative aspect, to be used when combining results from a
> subprogram that has the Reducer aspect.
>
> eg.
>
> In Ada.Containers.Vectors...
>
>    function "&" (Left, Right : Vector) return Vector with Associative;
>
>    function "&" (Left : Vector; Right : Element_Type) return Vector
> with Reducer => "&";
>
> The Reducer aspect names another function that has the Associative
> aspect.
>
> You can then, for instance, append Characters to a Vector in parallel.
> Otherwise, you could only concatenate vectors together in parallel.

Yes, but this is still trivial (perhaps fairly large, but that is different than
hard). In any case, I don't want these aspects stuff mixed in with the basic
parallel loop proposal (which actually is nearing completion, I think -- it just
needs wording polishing).

Reduction stuff is its own thing, regardless of what context it appears in.

...
> So to summarize all this,
>
> I'd say that as the complexity of a loop increases, it is better and
> easier to use a parallel loop.

...assuming that we have a way to write a reduction in such a loop. :-)

> As the complexity of a loop decreases, it is likely better and easier
> to use a 'Reduce call.

Makes sense, but I at least rarely write such loops (outside of string processing, which wouldn't have enough iterations to be worth parallelizing, and which generally aren't reductions anyway). YMMV.

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

From: Jean-Pierre Rosen
Sent: Thursday, January 11, 2018  11:35 PM

>> All it says is that semantically, you get the same result, regardless
>> which actual gets passed in which parameter. (e.g A + B = B + A) for
>> Integer "+"
> Um, that's "commutative". :-)
>
> An associative operator is one for which (A + B) + C = A + (B + C). My
> understanding is that was the only requirement needed to allow
> parallel reduction (because we don't know which one we'd want to do
> first, but it is easy enough to keep Left things on the left and Right things
> on the right).

And especially, note that "&" is NOT commutative...

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

From: Brad Moore
Sent: Friday, January 12, 2018  1:13 PM

...
> I think you missed my point. ...

OK

> ...
>> I think if a loop is complex, then you are better off using a
>> parallel loop, then you can also insert debugging code more easily.
>
> Other than that we don't have a way to do reductions currently in a
> parallel loop. :-)
>
> Note that I'd be happy to finish the current version of the parallel
> loop AI without worrying about reducers, and deal with the reducer
> issues separately. (That would at least let us make some progress.)

I think thats a good idea for now, for that AI.
I'd probably still try to create a separate AI on Associative, Reducer aspects, as that would be needed for the 'Reduce AI, but would be better to separate that part out.

> I would like to have a way to
> tell the compiler whether to parallelize (or not) a reduction
> expression, since it doesn't in general have the information needed to make that choice.
> It can't find out the number of iterations nor how expensive the
> reduction function is (in special cases it can, like statically
> bounded iterations with a predefined operator as a reduction
> function). Having to make a runtime choice would mean essentially
> generating all of the code twice (once for a parallel reduction, and
> once for a sequential reduction), and always choosing parallel would
> make most reductions pretty slow (you need a significant amount of
> work - either iterations or in the function body - before parallelizing will
> help anything).

Maybe we could allow a parallel do block for this purpose. It indicates that
parallelism is desired, and we could also say that the "and" is optional.

parallel
do
    Foo := A'Reduce(F,0);
end do;

If the "and" is present, then parallelism is first applied to the separate
blocks, and then optionally applied internally to each block, if more cores are
available.

e.g.

parallel
do
    Foo := A'Reduce(F,0);
and
    Bar := A'Reduce(G,0);
end do;

Though if the compiler was unsure about reducing via the F reducer, it would
probably fall back to the default as would be applied if the enclosing parallel
do wasn't there.

If one really wanted the F reducer to be done in parallel for this example, one
could write:

parallel
do
    parallel do
       Foo := A'Reduce(F,0);
    end do;
and
    Bar := A'Reduce(G,0);
end do;

...
>> > Or is "associated" supposed to be something completely different? I
>> > don't remember seeing anything about it previously...
>>
>> The idea is that it is a boolean aspect that can be applied to a
>> binary function where both parameters and result are of the same
>> type.
>> , or to a binary procedure where both parameters are the same type,
>> and one of the parameters is an in out.
>>
>> All it says is that semantically, you get the same result, regardless
>> which actual gets passed in which parameter. (e.g A + B = B + A) for
>> Integer "+"
>
> Um, that's "commutative". :-)

Yes, sorry my mistake for trying to type out this email too fast without
thinking. The intent was to write the formula
    (A + B) + C = A + (B + C)

And so my description of associative is also incorrect. It is not about being
able to switch the order of parameters to the function, but rather being
flexible in applying the function to a series of values without concern for
order in how the function is applied.

> In any case, I don't want these aspects stuff mixed in with the basic
> parallel loop proposal (which actually is nearing completion, I think
> -- it just needs wording polishing).
>
> Reduction stuff is its own thing, regardless of what context it appears in.

Agreed.

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

From: Brad Moore
Sent: Friday, January 12, 2018  1:17 PM

...
> And especially, note that "&" is NOT commutative...

Yes, sorry for the confusion of typing the wrong formula for associativity,

but note that while this is not commutative, it is associative, and thus is a
candidate for parallelisation. The intent of the proposal is to support both
commutative and non-commutative reducer functions.

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


Questions? Ask the ACAA Technical Agent