[J3] Commutativity of co_reduce
Malcolm Cohen
malcolm at nag-j.co.jp
Fri Oct 25 04:47:47 UTC 2024
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
> >
> >
>
>
>
>
More information about the J3
mailing list