[J3] Commutativity of co_reduce

[Brad Richardson]

Hi Malcolm,

LBL would like to see your improvement included. I.e.

"The choice of x and y is processor dependent."

We also agree that the NOTE could be improved.

Regards,
Brad


On Fri, 2024-10-25 at 13:47 +0900, Malcolm Cohen via J3 wrote:
> Hi Brad,
> 
> I disagree. The note does not make commutativity "expected", in fact
> the reverse: it brings to the user's attention that commutativity is
> not required and that without commutativity the results are not fully
> determinate.
> 
> They are not fully determinate for floating-point anyway since that
> is computationally non-associative.
> 
> This is a feature. It is there for good reason. Please do not try to
> delete it. The users do not want CO_REDUCE_ORDERED, they want what is
> there now.
> 
> As far as I can tell, LBL should be completely unaffected by this.
> The standard as it currently is does not constrain LBL. LBL as a user
> is free to use commutative OPERATIONs, but is not required to. LBL as
> an implementor is free to use the most efficient ordering it can
> imagine, but is not required to.
> 
> Perhaps it would help to insert something like "The choice of x and y
> is processor dependent." into the second paragraph of the OPERATION
> argument. I don't think that is strictly necessary, but it would make
> it more explicit, which is probably a good thing, and avoids an
> accidental misreading of it being "undefined".
> 
> I note that we already say that the computed value of CO_REDUCE is
> processor dependent in Annex A. That covers both computational non-
> associativity (e.g. floating-point) and computational non-
> commutativity.
> 
> I note that although matrix multiply per se is not commutative in
> general, it is sometimes e.g. when one has matrices that describe
> rotations in N-space. Other properties of the result are also
> preserved with commutation, even when the exact value is not. So
> there can be value even in operations that appear to be non-
> commutative.
> 
> We could also expand the NOTE along the lines John was suggesting. I
> think it got cut back to the "bare essentials" to avoid being too
> specific, but we could certainly look at putting something similar to
> those words in, if it would help. (My view is that those words are
> implied by the text we have, but I know other people jump to
> different conclusions.)
> 
> > You absolutely could do string concatenation
> 
> That is not string concatenation. In general, A//B (i.e.
> concatenation) is not equal to TRIM(A)//B (what one might call
> "trimmed concatenation"). But like matrices, you could do something
> like string concatenation by wrapping it in a derived type, so not a
> big deal.
> 
> 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: Thursday, October 24, 2024 11:41 PM
> 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,
> 
> I do not think that this should be left as is. It's effectively
> contradictory. It does not say that commutativity is required, but
> describes an algorithm and includes a note that effectively makes it
> expected. Either it should just say that commutativity is required,
> confirming what has already been implied. This is LBL's preference,
> is the simplest change, there exist algorithms which require it that
> can have better performance characteristics than those that don't,
> and I've already written edits for it.
> 
> [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.
> 
> 
> If commutativity is not a requirement, then the description of the
> algorithm needs to be changed to define what the ordering of the
> values is. Right now the ordering is not defined, and the note
> effectively acknowledges this.
> 
> IMO the first option can be done as an edits paper that simply
> clarifies what the standard already implies, whereas the second
> option does require an interp to say "no, no, we didn't mean to imply
> commutativity was required". If there are users who want a CO_REDUCE
> that doesn't require commutativity for OPERATION, one should be
> introduced separately, i.e. CO_REDUCE_ORDERED.
> 
> I'm happy to write up either paper (in fact I've already written
> them), and can upload them for vote/discussion on Monday. I do not
> think this should be left as is, in this middle ground of "this isn't
> required, but if you don't follow it the behavior is undefined".
> 
> Regards,
> Brad
> 
> P.S. You absolutely could do string concatenation with the following
> for OPERATION.
> 
> function trim_concat(lhs, rhs) result(combined)
>   character(len=HUGE_STRING), intent(in) :: lhs, rhs
>   character(len=HUGE_STRING) :: combined
>   combined = trim(lhs) // trim(rhs)
> end function
> 
> On Thu, 2024-10-24 at 13:37 +0900, Malcolm Cohen via J3 wrote:
> > 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
> > > 
> > > 
> > 
> > 
> > 
> > 
> 
> 
>