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

https://github.com/JuliaLang/julia/blob/4d9a3349170d9beea8584cc9a730d37609280ac3/base/operators.jl#L518-L522

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.