[J3] Commutativity of co_reduce

[Malcolm Cohen]

Ok, maybe there won't be a paper...

The NOTE in the standard makes it clear that it was deliberate that commutativity was not required. As it happens, it was required in the original "advanced coarrays TS", but was deliberately removed on incorporation into F2018, see 16-187r2.

As I recall one subgroup discussion, one of the concerns was with derived types where the "main thing" being computed was indeed associative and commutative, but with additional components that were not commutative, e.g. tracking computational history or time or something else useful but parenthetical to the main result. I don't accurately recall the specific examples used, but I do remember that they were convincingly useful, the only question being whether those component operations were really "mathematical" (and thus subject to the commutativity rule); they certainly were not commutative.

So, it was decided to not throw out the bathwater, because we wanted to keep that baby. Or something.

(Also, it was felt desirable to keep the differences in capability between REDUCE and CO_REDUCE to a minimum; commutativity is not an issue with REDUCE, and so was never a requirement.)

Now, one may disagree with the reasoning, or even consider that the decision was the wrong one, but it was what it was, viz not an error, and thus not subject to revision by interpretation.

Changing that now would be a backwards incompatibility between F2018 and F2023 (if we did it via an interp) or F2018/F2023 and F2028 (if we change it in the next revision). Being an incompatibility means we really should not do it via interp unless it was very clearly an error. I do not think we have reached that bar - the issues were discussed (and one of the other papers involved actually mention matrix multiply!), and the committee made its decision with full knowledge of those issues.

I was not in favour of removing the commutativity requirement at the time, but that was then. Removal via interp now is out of the question. Quite apart from the lateness in the revision cycle, I am not in favour of removing it in the F202y revision, at least partly because it is so hard to detect.

I would not be opposed to insertion of a *recommendation* that the OPERATION be commutative, but I am 100% sure that the original proposers of permitting non-commutativity would be opposed (I imagine or recall a heated discussion to that effect). With that in mind, I cannot say that I would whole-heartedly support such a recommendation either; we already have the NOTE warning about the possibility of different results, that should be enough I think.

With the lack of effective detection technology for commutativity violation, reinstating the commutativity requirement would merely be a louder exhortation to the user to "not do that". Such a result does not seem worth the introduction of an incompatibility.

Cheers,
-- 
..............Malcolm Cohen, NAG Oxford/Tokyo.

-----Original Message-----
From: J3 <j3-bounces at mailman.j3-fortran.org> On Behalf Of Malcolm Cohen via J3
Sent: Thursday, October 24, 2024 11:22 AM
To: 'General J3 interest list' <j3 at mailman.j3-fortran.org>
Cc: Malcolm Cohen <malcolm at nag-j.co.jp>
Subject: Re: [J3] Commutativity of co_reduce

Hi Brad,

Bare string concatenation is not possible, as the character length of the OPERATION is the same as the length of the arguments, not the sum. I also don't think that string concatenation is a mathematical operation per se.

Bare matrix multiplication is likewise not possible, as the arguments of OPERATION are scalar, but you are right that the matrices could be wrapped in a derived type.

I seem to recall that commutativity was in an earlier draft, but that we took it out as all the intrinsic operations that are not commutative are also not associative. This was quite a while ago. Of course we deliberately took it out of REDUCE as there is an ordering available.

I will write a paper.

Cheers,
--
..............Malcolm Cohen, NAG Oxford/Tokyo.

-----Original Message-----
From: J3 <j3-bounces at mailman.j3-fortran.org> On Behalf Of Brad Richardson via J3
Sent: Wednesday, October 23, 2024 10:27 AM
To: General J3 interest list <j3 at mailman.j3-fortran.org>
Cc: Brad Richardson <everythingfunctional at protonmail.com>; Malcolm Cohen <malcolm at nag-j.co.jp>
Subject: Re: [J3] Commutativity of co_reduce

Hi Malcolm,

String concatenation is the easiest example to think of. Matrix multiplication is another. The possibility of encountering them gets much greater when you start considering user defined derived types.

Regards,
Brad

On Wed, 2024-10-23 at 10:17 +0900, Malcolm Cohen via J3 wrote:
> Hi Brad,
> 
> What operation is associative but not commutative?
> 
> Also, the answer is not deterministic anyway: the rule is 
> "mathematically associative" not "computationally associative".
> 
> Cheers,
> --
> ..............Malcolm Cohen, NAG Oxford/Tokyo.
> 
> -----Original Message-----
> From: J3 <j3-bounces at mailman.j3-fortran.org> On Behalf Of Brad 
> Richardson via J3
> Sent: Wednesday, October 23, 2024 9:47 AM
> To: General J3 interest list <j3 at mailman.j3-fortran.org>
> Cc: Brad Richardson <everythingfunctional at protonmail.com>;
> fortran at lbl.gov
> Subject: [J3] Commutativity of co_reduce
> 
> Hi all,
> 
> The LBL group has encountered another question, this time with respect 
> to co_reduce. At present the description of OPERATION argument states 
> "OPERATION shall implement a mathematically associative operation."
> The subsequent description of how OPERATION is applied:
> 
> The computed value of a reduction operation over a set of values is 
> the result of an iterative process. Each iteration involves the 
> evaluation of OPERATION (x, y) for x and y in the set, the removal of 
> x and y from the set, and the addition of the value of OPERATION (x,
> y) to the set.
> The process terminates when the set has only one element; this is the 
> computed value.
> 
> Of note is that the word "set" implies that there is no ordering of 
> the values. The description also does not imply an order in which the 
> values are combined nor does it specify what subsequent iteration 
> consumes the result of a given combination. Thus the reduction only 
> has a deterministic answer if OPERATION is both associative *and* 
> commutative. We believe that it would be clearer if this requirement 
> was stated explicitly. The edits for this would be quite simple. I.e.
> 
> [383:5] Add "and commutative" after "associative" so that the sentence
> reads:
> 
>     OPERATION shall implement a mathematically associative and
>     commutative operation.
> 
> [383:29+] Delete the NOTE
> 
> Do others have opinions? Would it be reasonable to submit this change 
> as an edits paper as just a clarifying change?
> 
> Regards,
> Brad Richardson
> 
>