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

[Nathaniel Smith]

On Thu, Mar 20, 2014 at 1:36 PM, Dag Sverre Seljebotn
<d.s.seljebotn at astro.uio.no> wrote:
> On 03/20/2014 02:26 PM, Dag Sverre Seljebotn wrote:
>> 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.

Or even more specifically, the question is whether getting the chance
to use dynamic programming on chains of @'s (and only @'s!) is so
valuable that we want to have a special parsing+dispatch rule to allow
it.

I have to say that after glancing at a few hundred 'dot' calls, I'm
not as convinced that this is useful in practice. There are lots of
complex expressions out there involving 'dot', and relatively few of
them involve long chains of 'dot' calls [1][2]. There are strategies
for doing whole-expression optimization that work for more general
expressions, not just @ -- e.g. numexpr, numba, theano -- at the cost
of a bit more intrusiveness. And as numpy gets better at supporting
non-ndarray types, then it'll be easier to seamlessly support
low-impact deferred computation APIs like:

     a, b, c = defer(a, b, c)
     d = np.sin(a) + a @ b @ c
     e = d / (a + b + c + d)
     return force(e)

Having a special dispatch for @ would only help with one of the
computations here.

-n

[1] http://mail.scipy.org/pipermail/numpy-discussion/2014-March/069565.html
[2] http://mail.scipy.org/pipermail/numpy-discussion/2014-March/069578.html

-- 
Nathaniel J. Smith
Postdoctoral researcher - Informatics - University of Edinburgh
http://vorpus.org