[Numpy-discussion] [help needed] associativity and precedence of '@'

[Dag Sverre Seljebotn]

On 03/20/2014 02:26 PM, Dag Sverre Seljebotn wrote:
> On 03/19/2014 08:45 PM, josef.pktd at gmail.com wrote:
>>
>>
>>
>> On Wed, Mar 19, 2014 at 2:24 PM, Nathaniel Smith <njs at pobox.com
>> <mailto:njs at pobox.com>> wrote:
>>
>>      On Tue, Mar 18, 2014 at 9:14 AM, Robert Kern <robert.kern at gmail.com
>>      <mailto:robert.kern at gmail.com>> wrote:
>>       > On Tue, Mar 18, 2014 at 12:54 AM, Nathaniel Smith <njs at pobox.com
>>      <mailto:njs at pobox.com>> wrote:
>>       >> On Sat, Mar 15, 2014 at 6:28 PM, Nathaniel Smith <njs at pobox.com
>>      <mailto:njs at pobox.com>> wrote:
>>       >>> Mathematica: instead of having an associativity, a @ b @ c gets
>>       >>> converted into mdot([a, b, c])
>>       >>
>>       >> So, I've been thinking about this (thanks to @rfateman for
>>      pointing it
>>       >> out), and wondering if Mathematica's approach is worth following up
>>       >> more. (It would need to make it past python-dev, of course, but
>>      worst
>>       >> case is just that they say no and we're back where we are now, so we
>>       >> might as well think it through.)
>>       >
>>       > I predict with near-certainty that this will be rejected,
>>
>>      I guess that's what everyone thought about @ too? ;-)
>>
>>       > but that
>>       > doesn't prevent it from derailing the discussion. This proposal is
>>       > unlike anything else in Python. Chained comparisons are *not* similar
>>       > to this proposal. The chaining only happens at the syntax level, not
>>       > the semantics. `a < b < c` gets compiled down to `a.__lt__(b) and
>>       > b.__lt__(c)`, not `do_comparison([a, b, c], [lt, lt])`.
>>
>>      Yes, the syntax is the same as chained comparisons, and the dispatch
>>      is a generalization of regular operators. It is unusual; OTOH, @ is
>>      unusual in that no other operators in Python have the property that
>>      evaluating in the wrong order can cost you seconds of time and
>>      gigabytes of memory. Perhaps.
>>
>>       > We have approval for a binary @ operator. Take the win.
>>
>>      We have approval, and we have a request: that we figure out how @
>>      should work in detail to be most useful to us. Maybe that's this
>>      proposal; maybe not. Ultimately rejected-or-not-rejected comes down to
>>      how strong the arguments for something are. And while we can make some
>>      guesses about that, it's impossible to know how strong an argument
>>      will be until one sits down and works it out. So I still would like to
>>      hear what people think, even if it just ends in the conclusion that
>>      it's a terrible idea ;-).
>>
>>
>>
>> What happens if you have 5 @ in a row?
>>
>> My head hurts if I had to think about what would actually be going on.
>> and don't forget, the sparse matrix is stuck in the middle.
>
> Order-of-matrix-multiplication is literally my textbook example of a
> dynamic programming problem with complexity O(n^2) where n is number of
> terms (as in, it's how dynamic programming is introduced in my textbook).
>
> I don't think adding sparse or diagonal matrices changes this as long as
> you only deal with chained @ and make some simple assumptions of the
> cost of a FLOP in sparse @ dense, sparse @ sparse, dense @ dense, and so on.
>
> Where you need anything more than very simple dynamic programming
> algorithms is when you add + into the mix ("whether to use the
> distributive rule or not" and so on).
>
> I'm positive to the chained @ idea, I think it's the answer to "what we
> really want".

Sorry, I totally misunderstood this. The question is of course how you 
dispatch technically (where the __matmul__ function lives and which one 
to use), not figuring out what you want done.

I think you'd need to keep this very simple; for instance, just require 
the leftmost matrix to implement __matmul__ that takes a list, ditch 
__rmatmul__, and then solve the rest on the library level.

In our case, everyone would delegate __matmul__ to something in NumPy 
that then supports hooks and solves this on the library level. That 
would work as I say above + hooks to plug in cost estimators and compute 
functions for various matrix products.

(I've thought too much about these things as I wasted at least a month 
of my PhD on the now abandoned "oomatrix" project to find the optimal 
way of computing a linear algebra expressions.)

Dag Sverre