Parse 1 + 2 + 3 as +(1, +(2, 3))

[vchuravy]

@ChrisRackauckas and I was just talking and we were wondering why we are parsing 1 + 2 + 3 as Expr(:+, 1, 2, 3).
While I can see how that makes the parsers job easier it seems to make it harder for type-inference since instead of just
having on + method for integers we now have ~16, added to that is Chris infamous tendencies to create very long expressions
which causes things to break down one you reach a limit. (and as demonstrated before no matter how large N at some point it will be to small).

Is there a strong reason that I am missing for why we keep parsing it as a single expression? Macro-writers already need to program defensively
against both forms and it seems to me normalizing earlier would be better.

[JeffBezanson]

While I can see how that makes the parsers job easier

It doesn't :)

instead of just
having on + method for integers we now have ~16

What are the 16? How do you get that number?

I agree this is more trouble than it's worth though, and I'd rather it parse 2 arguments at a time like most infix operators. What about * and ++?

[ChrisRackauckas]

At 16 + starts splatting, at 32 the function no longer inlines and then the tuple is allocated and performance takes a 1000x or so drop. It seems if people don't like the current setup in the parser, and it causes user level issues, it might be good to just nix it.

[StefanKarpinski]

This doesn't seem like something we could change before 2.0 without breaking quite a bit.

[MasonProtter]

One potential reason to prefer parsing as +(1, +(2, 3)) is that it doesn't imply associativity of + and *, though admittedly I've never heard of a good definition of + that's not associative and also isn't a pun, but I think it can maybe hold for * due to the octonians.

I guess one can just make *(::Vararg{Octonian}) an error though and only define the the two argument version.

[tkf]

A cute thing you can do with the current parsing is to change the associativity of *:

julia> module RightAssociative
       *(a) = Base.:*(a)
       *(a, b) = Base.:*(a, b)
       *(args...) = *(args[1:end-2]..., *(args[end-1], args[end]))
       end
Main.RightAssociative

julia> using .RightAssociative: *

julia> Base.:*(x::Symbol, y) = Symbol("($x * $y)")

julia> :a * :b * :c
Symbol("(a * (b * c))")

Ref: https://discourse.julialang.org/t/why-is-multiplication-a-b-c-left-associative-foldl-not-right-associative-foldr/17552

Something like static arrays probably can do more advanced things by looking at exact sizes and picking up a good grouping.

BTW, I suppose 16 is just a heuristics to optimize the compile time:

julia/base/operators.jl

Lines 518 to 522 in 4d9a334

	function afoldl(op,a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,qs...)
	y = op(op(op(op(op(op(op(op(op(op(op(op(op(op(op(a,b),c),d),e),f),g),h),i),j),k),l),m),n),o),p)
	for x in qs; y = op(y,x); end
	y
	end

Is it possible to increase this threshold?

[elextr]

Surely parsing does not imply implementation, nothing prevents a macro or optimizer from following the spine of a (:+, 1, (:+, 2, 3)) and implementing it in any order it deems suitable.

[Sacha0]

The existing parsing exposes potential optimization opportunities for operations over collections. For example, with the present parsing and for matrix A and vectors u and v, u' * A * v can readily be made to hit an efficient bilinear form implementation. If I remember the last discussion of this parsing correctly, the preceding was the motivation for the present state :). Best!

[StefanKarpinski]

Yes, directly optimizing chained operations was the motivation for this current parsing. For chains of matrix and vector multiplications, this can be a major optimizations. Of course, we don't currently do such optimizations for chains of matrix multiplication.

[ChrisRackauckas]

https://discourse.julialang.org/t/speeding-up-solution-to-the-large-system-of-non-linear-complex-valued-odes/39075/2 is where this is showing up in practice.

[bkamins]

If this is change should it not be that 1+2+3 gets parsed as ((1+2)+3), as this is the current operation order? So at least the change would be breaking only on how it is parsed but the resulting value would not be affected.

[KristofferC]

A trick is to use const ⊕ = + and do a ⊕ b ⊕ c ⊕ ... to get rid of the n-arg parsing and not have code suddenly become order of magnitudes slower when you have too many terms.

[mikmoore]

I definitely support such a change. Situations where N-ary uses of +/++/* are significantly and uncontroversially better are so few that requiring an explicit non-infix N-ary call seems reasonable.

The status quo can occasionally cause nontrivial ugliness like JuliaLang/LinearAlgebra.jl#1043. And even in that situation of chained matrix multiplication, it's not a better implementation than can be achieved with the proper choice of binary reduction order. Dynamic reassociation seems like it should be the domain of packages anyway (although MatrixChainMultiply.jl appears abandoned at present).

---

should it not be that 1+2+3 gets parsed as ((1+2)+3)

Maybe I overstep, but had I assumed the title's suggestion of right-to-left associativity was merely a typo and that focus was on defaulting to purely binary reductions. Left-to-right is much more common and also is the documented behavior, with some caveats. I also interpreted this discussion to apply to the other N-ary-parsing operators * and ++.