[J3] Commutativity of co_reduce

[Brad Richardson]

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
> > 
> > 
> 
> 
> 
>