is the precedence of reduce correct?

[mppf]

The spec indicates in section 10.11 that reduce has higher precedence than *. I found this surprising, but I'm not sure I can explain why. (Something about them being multiple tokens makes me think they bind loosely).

This issue is just to note the issue in case anybody else runs into it / has run into it and wants to discuss.

For example, if we have

var A:[1..10] int;

writeln( + reduce 2*A );

is interpreted as

writeln( (+ reduce 2)*A );

rather than as

writeln( + reduce (2*A) );

The specification has rationale for it:

One final area of note is the precedence of reductions. Two common cases tend to argue for making reductions very low or very high in the precedence table:

max reduce A - min reduce A wants (max reduce A) - (min reduce A)
max reduce A * B wants max reduce (A * B)

The first statement would require reductions to have a higher precedence than the arithmetic operators while the second would require them to be lower. We opted to make reductions have high precedence due to the argument that they tend to resemble unary operators. Thus, to support our intuition:

max reduce A * B requires max reduce (A * B)

This choice also has the (arguably positive) effect of making the unparenthesized version of this statement result in an aggregate value if A and B are both aggregates—the reduction of A results in a scalar which promotes when being multiplied by B, resulting in an aggregate. Our intuition is that users who forget the parentheses will learn of their error at compilation time because the resulting expression is not a scalar as expected.

[ben-albrecht]

It might be useful to look at which pattern is more frequently used in code bases to determine which pattern we should prioritize through precedence rules.

(rip)grepping modules/ for reduce, I counted 8 instances of the following pattern:

op reduce A * B

and 0 instances of this pattern:

op reduce A - op reduce A

test/ may be more representative of typical user codes, but I'm not yet willing to sift through that output...

[vasslitvinov]

I ran the following patch through paratest:

--- a/compiler/parser/chapel.ypp
+++ b/compiler/parser/chapel.ypp
@@ -359,6 +359,7 @@
 %left TNOELSE
 %left TELSE
 %left TCOMMA
+%left TREDUCE TSCAN TDMAPPED
 %left TFOR TFORALL TIF TATOMIC TSYNC TSINGLE
 // %left TOWNED TUNMANAGED TSHARED
 %left TIN
@@ -376,7 +377,6 @@
 %right TUPLUS TUMINUS
 %left TSTAR TDIVIDE TMOD
 %right TBNOT TBANG
-%left TREDUCE TSCAN TDMAPPED
 %right TEXP
 %left TCOLON
 %left TBORROWED TOWNED TUNMANAGED TSHARED

14 tests failed including futures. Here is a summary:

[Error matching compiler output for arrays/vass/dmapped-int-error]
[Error matching program output for exercises/histogram1]
[Error matching program output for exercises/histogram2]
[Error matching program output for exercises/histogram3]
[Error matching compiler output for expressions/bradc/reduceVsMathPrec]
[Error matching .bad file for expressions/bradc/reduceVsMathPrec2]
[Error matching program output for puzzles/deitz/puzzle071004-v2]
[Error matching compiler output for reductions/deitz/test_neg_min_reduce]
[Error matching program output for studies/amr/advection/amr/AMR_AdvectionCTU_driver]
[Error matching compiler output for studies/hpcc/STREAMS/bradc/stream-fragmented]
[Error matching compiler output for studies/hpcc/STREAMS/diten/stream-fragmented-local]
[Error matching compiler output for trivial/deitz/expressions/all_precedence_levels_in_a_single_expression]
[Error matching .bad file for trivial/sungeun/bad_reduce_expr]
[Error matching compiler output for types/real/nan-minmax]

[test: arrays/vass/dmapped-int-error.chpl]
[Executing diff dmapped-int-error.good dmapped-int-error.comp.out.tmp]
1c1
< dmapped-int-error.chpl:3: error: cannot apply 'dmapped' to the non-domain type int(64)
---
> dmapped-int-error.chpl:2: error: cannot apply 'dmapped' to the non-domain type [domain(1,int(64),false)] domain(1,int(64),false)

var a1: [1..3] domain(1) dmapped Block({1..2});

But, this test is just checking what error occurs.

[test: exercises/histogram1.chpl]
[test: exercises/histogram2.chpl]
[test: exercises/histogram3.chpl]
[Executing diff histogram3.good histogram3.exec.out.tmp]
9,24c9
< ...
---
> histogram3.chpl:50: error: halt reached - Number of items in histogram does not match number of random numbers

if + reduce Y != numNumbers then

[test: expressions/bradc/reduceVsMathPrec.chpl]
[test: expressions/bradc/reduceVsMathPrec2.chpl]
[Executing diff reduceVsMathPrec.good reduceVsMathPrec.comp.out.tmp]
1,10c1
< ...
---
> reduceVsMathPrec.chpl:16: error: 'max' undeclared (first use this function)

Lots of examples since it's testing the precedence. E.g.

var total: int = + reduce A * B;

[test: puzzles/deitz/puzzle071004-v2.chpl]
[Executing diff puzzle071004-v2.good puzzle071004-v2.exec.out.tmp]
1c1
< 5 5 5
---
> 9

writeln(+ reduce ([1..3] 1) + [4..6] 2);

[test: reductions/deitz/test_neg_min_reduce.chpl]
[Executing diff test_neg_min_reduce.good test_neg_min_reduce.comp.out.tmp]
1c1
< -1
---
> test_neg_min_reduce.chpl:1: error: 'min' undeclared (first use this function)

writeln(- min reduce (1..3));

[test: studies/amr/advection/amr/AMR_AdvectionCTU_driver.chpl]
> Line 863, element 1: elements differ
>   _output/fort.q0015: 4.0740609322151691E-02
>   regression_data/fort.q0015: 4.0631121763156218E-02
> etc.....

AMR code has very many parethesized reductions (suggesting perhaps the other precedence would make the code nicer looking) but the one that changed behavior might be this:

return +reduce(signatures(1).array):real / D.numIndices:real;

[test: studies/hpcc/STREAMS/bradc/stream-fragmented.chpl]
[test: studies/hpcc/STREAMS/diten/stream-fragmented-local.chpl]
[Executing diff stream-fragmented-local.good stream-fragmented-local.1.comp.out.tmp]
1,12c1,2
< ...
---
> stream-fragmented-local.chpl:25: In function 'main':
> stream-fragmented-local.chpl:53: error: 't' undeclared (first use this function)

const execTime = [t in 1..numTrials] max reduce [loc in LocaleSpace] allExecTime(loc)(t);

[test: trivial/deitz/expressions/all_precedence_levels_in_a_single_expression.chpl]
[Executing diff all_precedence_levels_in_a_single_expression.good all_precedence_levels_in_a_single_expression.comp.out.tmp]
1,19c1
< ...
---
> all_precedence_levels_in_a_single_expression.chpl:32: error: cannot promote short-circuiting && operator

This is a test of operator precedence.

[test: trivial/sungeun/bad_reduce_expr.chpl]
[Executing diff bad_reduce_expr.bad bad_reduce_expr.exec.out.tmp]
1d0
< bad_reduce_expr.chpl:6: error: iterator or promoted expression iterator used in if or while condition

if (+ reduce A-B) == 11 then writeln("hi");

(test is expecting an error)

[test: types/real/nan-minmax.chpl]
[Executing diff nan-minmax.good nan-minmax.comp.out.tmp]
1,2c1
< nannannannan
< done
---
> nan-minmax.chpl:29: error: Cannot assign to bool from int(64)

e.g.

assert(min reduce ARR == -INFINITY);
assert(minloc reduce zip(ARR, ARR.domain) == (-INFINITY, n-1));

[vasslitvinov]

Looking at the last one - the test that I wrote recently: types/real/nan-minmax.chpl
the problematic cases are all like these:

assert(min reduce ARR == -INFINITY);
assert(minloc reduce zip(ARR, ARR.domain) == (-INFINITY, n-1));

To me, it is mostly a matter of a habit, whether to think of it as (min reduce ARR) == whatever or min reduce (ARR == whatever).

[mppf]

In the original case where I ran into this, I wanted to do something like + scan A - B and was surprised that I needed parentheses. However in some way's @vasslitvinov's experiment above takes it as far as possible:

• I don't think there's any reason to change the precedence of dmapped at this time. (Is there some reason it needs to have the same precedence of reduce and scan? AFAIK that was just how it ended up).
• I don't think it's a given that reduce would have lower precedence than the comparison operators, but it could. For example, it could have precedence between the comparison operators and +.

[mppf]

Only the following failing test cases cause me some concern with changing the precedence of reduce:

writeln(- min reduce (1..3));

This one is interesting, because it's fairly unambiguous (since -min doesn't make any sense). Right now, the parser handles reductions with expr TREDUCE expr. If we changed the precedence of reduce, we could change that to something more like ident TREDUCE expr | (expr) TREDUCE expr`.

const execTime = [t in 1..numTrials] max reduce [loc in LocaleSpace] allExecTime(loc)(t);

I think this is running into the same problem as the above.

return +reduce(signatures(1).array):real / D.numIndices:real;

Here, the parentheses after reduce make it look like it's specifying exactly what goes in to the reduction. It looks kindof like a function call. However that only works if the reduce has higher precedence than the following expressions. Note though that the above is actually already misleading with the current precedence rules - it is doing

+ reduce (array:real) / numIndices;

Another misleading example would be this:

+ reduce (A) ** 2;

which is interpreted (on master) as + reduce (A ** 2).

So, I think that if we had a goal of supporting this function-invocation-like pattern for reduce, we should handle that by making a specific parser rule for + reduce ( expr ) and that this pattern isn't a strong motivator for the current precedence.

[mppf]

The spec rationale claims that the error you get if you misunderstand the precedence is a motivator for the precedence choice. Would we still get a good error if we made the opposite choice?

Suppose we chose the opposite precedence and somebody wanted to write

max reduce A - min reduce A

but meant

(max reduce A) - (min reduce A)

The compiler would actually interpret it as

max reduce (A - min reduce A)

Which you might think would compile but have much worse performance (because the inner reduction might be computed once per array element). However that is not what happens today - the sub-expression is evaluated only once. This is an open question in #7904.

Hidden below is a benchmark showing that the performance is comparable. Anyway, the situation is that if #7904 is left working the way it works on master, the change in behavior from what was intended is probably harmless. If #7904 changes, it would become a performance problem without any indication from the compiler (Of course it is something we could add a warning specifically about if desired).

config const n = 1000000;
config const ntrials = 100000;

use Time;

proc main() {
  const A:[1..n] int = 1..n;
  var sum = 0;
  var t: Timer;
  t.start();
  for i in 1..ntrials {
    sum += (max reduce A) - (min reduce A);
  }
  t.stop();
  writeln("(max reduce A) - (min reduce A) ", t.elapsed(), " s");
  
  t.clear();
  t.start();
  for i in 1..ntrials {
    sum += max reduce (A - min reduce A);
  }
  t.stop();
  writeln("max reduce (A - (min reduce A) ", t.elapsed(), " s");
}

(max reduce A) - (min reduce A) 8.1839 s
max reduce (A - (min reduce A) 8.20486 s

The spec claims that max reduce A - min reduce A is a common case. However, there are relatively few occurrences of expressions containing two reduce expressions. Many of these do some kind of nested reduction that would be OK with either precedence choice, e.g. from programs/norm.chpl return max reduce [j in D.dim(2)] (+ reduce abs(x[D.dim(1), j]));.

Which tests actually use two or more reduce in the same expression in a way that is sensitive to precedence?

• reduceVsMathPrec.chpl (which tests the precedence itself)
• optimizations/bulkcomm/alberto/Block/PrintComms.chpl: var i= +reduce A.get + +reduce A.get_nb + +reduce A.put + +reduce A.put_nb;. As discussed above, due to the current behavior of promotion and sub-expressions (see Should promoted calls execute nested call expressions one or many times? #7904), this does about the same thing and at about the same performance in either precedence interpretation... but if we change Should promoted calls execute nested call expressions one or many times? #7904 it could become a performance issue.
• release/examples/benchmarks/shootout/spectralnorm.chpl writef("%.9dr\n", sqrt(+ reduce (u*v) / + reduce (v*v))); This one is similar in that if we change Should promoted calls execute nested call expressions one or many times? #7904 then it could have much worse performance.

Based on some grepping, I think there are many more cases of something like reduce (A + B) in the tests.

[bradcray]

There are plenty of decisions we've made in Chapel that have seemed increasingly wrong to me over time (most of which we've now corrected), but the precedence level of reduce and scan has never been one of them, personally. I'm not sure I can explain why any better than the original spec rationale, though. I think of them as being like unary operators; and I think of them as naturally taking an array as an argument, so if I want to reduce or scan an array-like expression, I tend to find that parenthesizing that expression seems natural as well (e.g., + reduce (A + b) visually parses more naturally for me than + reduce A + b which doesn't suggest the same thing). By that token, I'm also not convinced that counting the number of cases where parenthesis are used or not in practice is the right way to decide precedence. If I found that a * (b + c) was written far more often than (a * b) + c, it wouldn't cause me to conclude that it's incorrect to give * higher precedence than +.

[ben-albrecht]

As a data point, a user recently ran over the pitfall described in this issue: unexpected-result-for-inner-product-using-reduce

[vasslitvinov]

@mppf what do you think about closing this issue? How much room is here for more progress?

[mppf]

It doesn't sound to me like we're likely to change it but I would still be open to doing so if other people think it is worth changing. However, I'm not sure if this issue got much attention aside from those of us who commented on it.

Anyway, I think we could close the issue and say "we're not expecting to change it".