README.org

* TALK
I just gave a talk about this at [[https://www.socallinuxexpo.org/scale/18x][SCaLE 18x]]. Here are the [[https://www.youtube.com/watch?v=YOOapXNtUWw][video of the talk]] and
the [[https://github.com/dkogan/talk-numpysane-gnuplotlib/raw/master/numpysane-gnuplotlib.pdf]["slides"]].

* NAME
numpysane: more-reasonable core functionality for numpy

* SYNOPSIS
#+BEGIN_EXAMPLE
>>> import numpy as np
>>> import numpysane as nps

>>> a   = np.arange(6).reshape(2,3)
>>> b   = a + 100
>>> row = a[0,:] + 1000

>>> a
array([[0, 1, 2],
       [3, 4, 5]])

>>> b
array([[100, 101, 102],
       [103, 104, 105]])

>>> row
array([1000, 1001, 1002])

>>> nps.glue(a,b, axis=-1)
array([[  0,   1,   2, 100, 101, 102],
       [  3,   4,   5, 103, 104, 105]])

>>> nps.glue(a,b,row, axis=-2)
array([[   0,    1,    2],
       [   3,    4,    5],
       [ 100,  101,  102],
       [ 103,  104,  105],
       [1000, 1001, 1002]])

>>> nps.cat(a,b)
array([[[  0,   1,   2],
        [  3,   4,   5]],

       [[100, 101, 102],
        [103, 104, 105]]])

>>> @nps.broadcast_define( (('n',), ('n',)) )
... def inner_product(a, b):
...     return a.dot(b)

>>> inner_product(a,b)
array([ 305, 1250])
#+END_EXAMPLE

* DESCRIPTION

Numpy is a very widely used toolkit for numerical computation in Python. Despite
its popularity, some of its core functionality is mysterious and/or incomplete.
The numpysane library seeks to fill those gaps by providing its own replacement
routines. Many of the replacement functions are direct translations from PDL
(http://pdl.perl.org), a numerical computation library for perl. The functions
provided by this module fall into three broad categories:

- Broadcasting support
- Nicer array manipulation
- Basic linear algebra

** Broadcasting
Numpy has a limited support for broadcasting
(http://docs.scipy.org/doc/numpy/user/basics.broadcasting.html), a generic way
to vectorize functions. A broadcasting-aware function knows the dimensionality
of its inputs, and any extra dimensions in the input are automatically used for
vectorization.

*** Broadcasting rules
A basic example is an inner product: a function that takes in two
identically-sized 1-dimensional arrays (input prototype (('n',), ('n',)) ) and
returns a scalar (output prototype () ). If one calls a broadcasting-aware inner
product with two arrays of shape (2,3,4) as input, it would compute 6 inner
products of length-4 each, and report the output in an array of shape (2,3).

In short:

- The most significant dimension in a numpy array is the LAST one, so the
  prototype of an input argument must exactly match a given input's trailing
  shape. So a prototype shape of (a,b,c) accepts an argument shape of (......,
  a,b,c), with as many or as few leading dimensions as desired.
- The extra leading dimensions must be compatible across all the inputs. This
  means that each leading dimension must either
  - equal 1
  - be missing (thus assumed to equal 1)
  - equal to some positive integer >1, consistent across all arguments
- The output is collected into an array that's sized as a superset of the
  above-prototype shape of each argument

More involved example: A function with input prototype ( (3,), ('n',3), ('n',),
('m',) ) given inputs of shape

#+BEGIN_EXAMPLE
(1,5,    3)
(2,1,  8,3)
(        8)
(  5,    9)
#+END_EXAMPLE

will return an output array of shape (2,5, ...), where ... is the shape of each
output slice. Note again that the prototype dictates the TRAILING shape of the
inputs.

*** What about the stock broadcasting support?

The numpy documentation dedicates a whole page explaining the broadcasting
rules, but only a small number of numpy functions provide any broadcasting
support. It's fairly inconsistent, and most functions have no broadcasting
support and no mention of it in the documentation. And as a result, this is not
a prominent part of the numpy ecosystem and there's little user awareness that
it exists.

*** What this module provides
This module contains functionality to make any arbitrary function broadcastable,
in either C or Python. In both cases, the input and output prototypes are
declared, and these are used for shape-checking and vectorization each time the
function is called.

The functions can have either

- A single output, returned as a numpy array. The output specification in the
  prototype is a single shape tuple
- Multiple outputs, returned as a tuple of numpy arrays. The output
  specification in the prototype is a tuple of shape tuples

*** Broadcasting in python
This is invoked as a decorator, applied to any function. An example:

#+BEGIN_EXAMPLE
>>> import numpysane as nps

>>> @nps.broadcast_define( (('n',), ('n',)) )
... def inner_product(a, b):
...     return a.dot(b)
#+END_EXAMPLE

Here we have a simple inner product function to compute ONE inner product. The
'broadcast_define' decorator adds broadcasting-awareness: 'inner_product()'
expects two 1D vectors of length 'n' each (same 'n' for the two inputs),
vectorizing extra dimensions, as needed. The inputs are shape-checked, and
incompatible dimensions will trigger an exception. Example:

#+BEGIN_EXAMPLE
>>> import numpy as np

>>> a = np.arange(6).reshape(2,3)
>>> b = a + 100

>>> a
array([[0, 1, 2],
       [3, 4, 5]])

>>> b
array([[100, 101, 102],
       [103, 104, 105]])

>>> inner_product(a,b)
array([ 305, 1250])
#+END_EXAMPLE

Another related function in this module broadcast_generate(). It's similar to
broadcast_define(), but instead of adding broadcasting-awareness to an existing
function, it returns a generator that produces tuples from a set of arguments
according to a given prototype. Similarly, broadcast_extra_dims() is available
to report the outer shape of a potential broadcasting operation.

Stock numpy has some rudimentary support for all this with its vectorize()
function, but it assumes only scalar inputs and outputs, which severely limits
its usefulness. See the docstrings for 'broadcast_define' and
'broadcast_generate' in the INTERFACE section below for usage details.

*** Broadcasting in C
The python broadcasting is useful, but it is a python loop, so the loop itself
is computationally expensive if we have many iterations. If the function being
wrapped is available in C, we can apply broadcasting awareness in C, which makes
a much faster loop.

The "numpysane_pywrap" module generates code to wrap arbitrary C code in a
broadcasting-aware wrapper callable from python. This is an analogue of PDL::PP
(http://pdl.perl.org/PDLdocs/PP.html). This generated code is compiled and
linked into a python extension module, as usual. This functionality documented
separately: https://github.com/dkogan/numpysane/blob/master/README-pywrap.org

After I wrote this, I realized there is some support for this in stock numpy:

https://docs.scipy.org/doc/numpy-1.13.0/reference/c-api.ufunc.html

Note: I have not tried using these APIs.

** Nicer array manipulation
Numpy functions that move dimensions around and concatenate matrices are
unintuitive. For instance, a simple concatenation of a row-vector or a
column-vector to a matrix requires arcane knowledge to accomplish reliably. This
module provides new functions that can be used for these basic operations. These
new functions do have well-defined and sensible behavior, and they largely come
from the interfaces in PDL (http://pdl.perl.org). These all respect the core
rules of numpy broadcasting:

- LEADING length-1 dimensions don't affect the meaning of an array, so the
  routines handle missing or extra length-1 dimensions at the front

- The inner-most dimensions of an array are the TRAILING ones, so whenever an
  axis specification is used, it is strongly recommended (sometimes required) to
  count the axes from the back by passing in axis<0

A high level description of the functionality is given here, and each function
is described in detail in the INTERFACE section below. In the following
examples, I use a function "arr" that returns a numpy array with given
dimensions:

#+BEGIN_EXAMPLE
>>> def arr(*shape):
...     product = reduce( lambda x,y: x*y, shape)
...     return numpy.arange(product).reshape(*shape)

>>> arr(1,2,3)
array([[[0, 1, 2],
        [3, 4, 5]]])

>>> arr(1,2,3).shape
(1, 2, 3)
#+END_EXAMPLE

*** Concatenation
This module provides two functions to do this

**** glue
Concatenates some number of arrays along a given axis ('axis' must be given in a
kwarg). Implicit length-1 dimensions are added at the start as needed.
Dimensions other than the glueing axis must match exactly. Basic usage:

#+BEGIN_EXAMPLE
>>> row_vector = arr(  3,)
>>> col_vector = arr(5,1,)
>>> matrix     = arr(5,3,)

>>> numpysane.glue(matrix, row_vector, axis = -2).shape
(6,3)

>>> numpysane.glue(matrix, col_vector, axis = -1).shape
(5,4)
#+END_EXAMPLE

**** cat
Concatenate some number of arrays along a new leading axis. Implicit length-1
dimensions are added, and the logical shapes of the inputs must match. This
function is a logical inverse of numpy array iteration: iteration splits an
array over its leading dimension, while cat joins a number of arrays via a new
leading dimension. Basic usage:

#+BEGIN_EXAMPLE
>>> numpysane.cat(arr(5,), arr(5,)).shape
(2,5)

>>> numpysane.cat(arr(5,), arr(1,1,5,)).shape
(2,1,1,5)
#+END_EXAMPLE

*** Manipulation of dimensions
Several functions are available, all being fairly direct ports of their PDL
(http://pdl.perl.org) equivalents
**** clump
Reshapes the array by grouping together 'n' dimensions, where 'n' is given in a
kwarg. If 'n' > 0, then n leading dimensions are clumped; if 'n' < 0, then -n
trailing dimensions are clumped. Basic usage:

#+BEGIN_EXAMPLE
>>> numpysane.clump( arr(2,3,4), n = -2).shape
(2, 12)

>>> numpysane.clump( arr(2,3,4), n =  2).shape
(6, 4)
#+END_EXAMPLE

**** atleast_dims
Adds length-1 dimensions at the front of an array so that all the given
dimensions are in-bounds. Any axis<0 may expand the shape. Adding new leading
dimensions (axis>=0) is never useful, since numpy broadcasts from the end, so
clump() treats axis>0 as a check only: the requested axis MUST already be
in-bounds, or an exception is thrown. This function always preserves the meaning
of all the axes in the array: axis=-1 is the same axis before and after the
call. Basic usage:

#+BEGIN_EXAMPLE
>>> numpysane.atleast_dims(arr(2,3), -1).shape
(2, 3)

>>> numpysane.atleast_dims(arr(2,3), -2).shape
(2, 3)

>>> numpysane.atleast_dims(arr(2,3), -3).shape
(1, 2, 3)

>>> numpysane.atleast_dims(arr(2,3), 0).shape
(2, 3)

>>> numpysane.atleast_dims(arr(2,3), 1).shape
(2, 3)

>>> numpysane.atleast_dims(arr(2,3), 2).shape
[exception]
#+END_EXAMPLE

**** mv
Moves a dimension from one position to another. Basic usage to move the last
dimension (-1) to the front (0)

#+BEGIN_EXAMPLE
>>> numpysane.mv(arr(2,3,4), -1, 0).shape
(4, 2, 3)
#+END_EXAMPLE

Or to move a dimension -5 (added implicitly) to the end

#+BEGIN_EXAMPLE
>>> numpysane.mv(arr(2,3,4), -5, -1).shape
(1, 2, 3, 4, 1)
#+END_EXAMPLE

**** xchg
Exchanges the positions of two dimensions. Basic usage to move the last
dimension (-1) to the front (0), and the front to the back.

#+BEGIN_EXAMPLE
>>> numpysane.xchg(arr(2,3,4), -1, 0).shape
(4, 3, 2)
#+END_EXAMPLE

Or to swap a dimension -5 (added implicitly) with dimension -2

#+BEGIN_EXAMPLE
>>> numpysane.xchg(arr(2,3,4), -5, -2).shape
(3, 1, 2, 1, 4)
#+END_EXAMPLE

**** transpose
Reverses the order of the two trailing dimensions in an array. The whole array
is seen as being an array of 2D matrices, each matrix living in the 2 most
significant dimensions, which implies this definition. Basic usage:

#+BEGIN_EXAMPLE
>>> numpysane.transpose( arr(2,3) ).shape
(3,2)

>>> numpysane.transpose( arr(5,2,3) ).shape
(5,3,2)

>>> numpysane.transpose( arr(3,) ).shape
(3,1)
#+END_EXAMPLE

Note that in the second example we had 5 matrices, and we transposed each one.
And in the last example we turned a row vector into a column vector by adding an
implicit leading length-1 dimension before transposing.

**** dummy
Adds a single length-1 dimension at the given position. Basic usage:

#+BEGIN_EXAMPLE
>>> numpysane.dummy(arr(2,3,4), -1).shape
(2, 3, 4, 1)
#+END_EXAMPLE

**** reorder
Reorders the dimensions in an array using the given order. Basic usage:

#+BEGIN_EXAMPLE
>>> numpysane.reorder( arr(2,3,4), -1, -2, -3 ).shape
(4, 3, 2)

>>> numpysane.reorder( arr(2,3,4), 0, -1, 1 ).shape
(2, 4, 3)

>>> numpysane.reorder( arr(2,3,4), -2 , -1, 0 ).shape
(3, 4, 2)

>>> numpysane.reorder( arr(2,3,4), -4 , -2, -5, -1, 0 ).shape
(1, 3, 1, 4, 2)
#+END_EXAMPLE

** Basic linear algebra
*** inner
Broadcast-aware inner product. Identical to numpysane.dot(). Basic usage to
compute 4 inner products of length 3 each:

#+BEGIN_EXAMPLE
>>> numpysane.inner(arr(  3,),
                    arr(4,3,)).shape
(4,)

>>> numpysane.inner(arr(  3,),
                    arr(4,3,))
array([5, 14, 23, 32])
#+END_EXAMPLE

*** dot
Broadcast-aware non-conjugating dot product. Identical to numpysane.inner().

*** vdot
Broadcast-aware conjugating dot product. Same as numpysane.dot(), except this
one conjugates complex input, which numpysane.dot() does not

*** outer
Broadcast-aware outer product. Basic usage to compute 4 outer products of length
3 each:

#+BEGIN_EXAMPLE
>>> numpysane.outer(arr(  3,),
                    arr(4,3,)).shape
array(4, 3, 3)
#+END_EXAMPLE

*** norm2
Broadcast-aware 2-norm. numpysane.norm2(x) is identical to numpysane.inner(x,x):

#+BEGIN_EXAMPLE
>>> numpysane.norm2(arr(4,3))
array([5, 50, 149, 302])
#+END_EXAMPLE

*** mag
Broadcast-aware vector magnitude. mag(x) is functionally identical to
sqrt(numpysane.norm2(x)) and sqrt(numpysane.inner(x,x))

#+BEGIN_EXAMPLE
>>> numpysane.mag(arr(4,3))
array([ 2.23606798,  7.07106781, 12.20655562, 17.3781472 ])
#+END_EXAMPLE

*** trace
Broadcast-aware matrix trace.

#+BEGIN_EXAMPLE
>>> numpysane.trace(arr(4,3,3))
array([12., 39., 66., 93.])
#+END_EXAMPLE

*** matmult
Broadcast-aware matrix multiplication. This accepts an arbitrary number of
inputs, and adds leading length-1 dimensions as needed. Multiplying a row-vector
by a matrix

#+BEGIN_EXAMPLE
>>> numpysane.matmult( arr(3,), arr(3,2) ).shape
(2,)
#+END_EXAMPLE

Multiplying a row-vector by 5 different matrices:

#+BEGIN_EXAMPLE
>>> numpysane.matmult( arr(3,), arr(5,3,2) ).shape
(5, 2)
#+END_EXAMPLE

Multiplying a matrix by a col-vector:

#+BEGIN_EXAMPLE
>>> numpysane.matmult( arr(3,2), arr(2,1) ).shape
(3, 1)
#+END_EXAMPLE

Multiplying a row-vector by a matrix by a col-vector:

#+BEGIN_EXAMPLE
>>> numpysane.matmult( arr(3,), arr(3,2), arr(2,1) ).shape
(1,)
#+END_EXAMPLE

** What's wrong with existing numpy functions?
Why did I go through all the trouble to reimplement all this? Doesn't numpy
already do all these things? Yes, it does. But in a very nonintuitive way.

*** Concatenation
**** hstack()
hstack() performs a "horizontal" concatenation. When numpy prints an array, this
is the last dimension (the most significant dimensions in numpy are at the end).
So one would expect that this function concatenates arrays along this last
dimension. In the special case of 1D and 2D arrays, one would be right:

#+BEGIN_EXAMPLE
>>> numpy.hstack( (arr(3), arr(3))).shape
(6,)

>>> numpy.hstack( (arr(2,3), arr(2,3))).shape
(2, 6)
#+END_EXAMPLE

but in any other case, one would be wrong:

#+BEGIN_EXAMPLE
>>> numpy.hstack( (arr(1,2,3), arr(1,2,3))).shape
(1, 4, 3)     <------ I expect (1, 2, 6)

>>> numpy.hstack( (arr(1,2,3), arr(1,2,4))).shape
[exception]   <------ I expect (1, 2, 7)

>>> numpy.hstack( (arr(3), arr(1,3))).shape
[exception]   <------ I expect (1, 6)

>>> numpy.hstack( (arr(1,3), arr(3))).shape
[exception]   <------ I expect (1, 6)
#+END_EXAMPLE

The above should all succeed, and should produce the shapes as indicated. Cases
such as "numpy.hstack( (arr(3), arr(1,3)))" are maybe up for debate, but
broadcasting rules allow adding as many extra length-1 dimensions as we want
without changing the meaning of the object, so I claim this should work. Either
way, if you print out the operands for any of the above, you too would expect a
"horizontal" stack() to work as stated above.

It turns out that normally hstack() concatenates along axis=1, unless the first
argument only has one dimension, in which case axis=0 is used. In a system where
the most significant dimension is the last one, this is only correct if everyone
has only 2D arrays. The correct way to do this is to concatenate along axis=-1.
It works for n-dimensionsal objects, and doesn't require the special case logic
for 1-dimensional objects.

**** vstack()
Similarly, vstack() performs a "vertical" concatenation. When numpy prints an
array, this is the second-to-last dimension (remember, the most significant
dimensions in numpy are at the end). So one would expect that this function
concatenates arrays along this second-to-last dimension. Again, in the special
case of 1D and 2D arrays, one would be right:

#+BEGIN_EXAMPLE
>>> numpy.vstack( (arr(2,3), arr(2,3))).shape
(4, 3)

>>> numpy.vstack( (arr(3), arr(3))).shape
(2, 3)

>>> numpy.vstack( (arr(1,3), arr(3))).shape
(2, 3)

>>> numpy.vstack( (arr(3), arr(1,3))).shape
(2, 3)

>>> numpy.vstack( (arr(2,3), arr(3))).shape
(3, 3)
#+END_EXAMPLE

Note that this function appears to tolerate some amount of shape mismatches. It
does it in a form one would expect, but given the state of the rest of this
system, I found it surprising. For instance "numpy.hstack( (arr(1,3), arr(3)))"
fails, so one would think that "numpy.vstack( (arr(1,3), arr(3)))" would fail
too.

And once again, adding more dimensions make it confused, for the same reason:

#+BEGIN_EXAMPLE
>>> numpy.vstack( (arr(1,2,3), arr(2,3))).shape
[exception]   <------ I expect (1, 4, 3)

>>> numpy.vstack( (arr(1,2,3), arr(1,2,3))).shape
(2, 2, 3)     <------ I expect (1, 4, 3)
#+END_EXAMPLE

Similarly to hstack(), vstack() concatenates along axis=0, which is "vertical"
only for 2D arrays, but not for any others. And similarly to hstack(), the 1D
case has special-cased logic to make it work properly.

The correct way to do this is to concatenate along axis=-2. It works for
n-dimensionsal objects, and doesn't require the special case for 1-dimensional
objects.

**** dstack()
I'll skip the detailed description, since this is similar to hstack() and
vstack(). The intent was to concatenate across axis=-3, but the implementation
takes axis=2 instead. This is wrong, as before. And I find it strange that these
3 functions even exist, since they are all special-cases: the concatenation axis
should be an argument, and at most, the edge special case (hstack()) should
exist. This brings us to the next function

**** concatenate()
This is a more general function, and unlike hstack(), vstack() and dstack(), it
takes as input a list of arrays AND the concatenation dimension. It accepts
negative concatenation dimensions to allow us to count from the end, so things
should work better. And in many cases that failed previously, they do:

#+BEGIN_EXAMPLE
>>> numpy.concatenate( (arr(1,2,3), arr(1,2,3)), axis=-1).shape
(1, 2, 6)

>>> numpy.concatenate( (arr(1,2,3), arr(1,2,4)), axis=-1).shape
(1, 2, 7)

>>> numpy.concatenate( (arr(1,2,3), arr(1,2,3)), axis=-2).shape
(1, 4, 3)
#+END_EXAMPLE

But many things still don't work as I would expect:

#+BEGIN_EXAMPLE
>>> numpy.concatenate( (arr(1,3), arr(3)), axis=-1).shape
[exception]   <------ I expect (1, 6)

>>> numpy.concatenate( (arr(3), arr(1,3)), axis=-1).shape
[exception]   <------ I expect (1, 6)

>>> numpy.concatenate( (arr(1,3), arr(3)), axis=-2).shape
[exception]   <------ I expect (3, 3)

>>> numpy.concatenate( (arr(3), arr(1,3)), axis=-2).shape
[exception]   <------ I expect (2, 3)

>>> numpy.concatenate( (arr(2,3), arr(2,3)), axis=-3).shape
[exception]   <------ I expect (2, 2, 3)
#+END_EXAMPLE

This function works as expected only if

- All inputs have the same number of dimensions
- All inputs have a matching shape, except for the dimension along which we're
  concatenating
- All inputs HAVE the dimension along which we're concatenating

A common use case that violates these conditions: I have an object that contains
N 3D vectors, and I want to add another 3D vector to it. This is essentially the
first failing example above.

**** stack()
The name makes it sound exactly like concatenate(), and it takes the same
arguments, but it is very different. stack() requires that all inputs have
EXACTLY the same shape. It then concatenates all the inputs along a new
dimension, and places that dimension in the location given by the 'axis' input.
If this is the exact type of concatenation you want, this function works fine.
But it's one of many things a user may want to do.

**** Thoughts on concatenation
This module introduces numpysane.glue() and numpysane.cat() to replace all the
above functions. These do not refer to anything being "horizontal" or
"vertical", nor do they talk about "rows" or "columns": these concepts simply
don't apply in a generic N-dimensional system. These functions are very explicit
about the dimensionality of the inputs/outputs, and fit well into a
broadcasting-aware system.

Since these functions assume that broadcasting is an important concept in the
system, the given axis indices should be counted from the most significant
dimension: the last dimension in numpy. This means that where an axis index is
specified, negative indices are encouraged. glue() forbids axis>=0 outright.

***** Example for further justification
An array containing N 3D vectors would have shape (N,3). Another array
containing a single 3D vector would have shape (3,). Counting the dimensions
from the end, each vector is indexed in dimension -1. However, counting from the
front, the vector is indexed in dimension 0 or 1, depending on which of the two
arrays we're looking at. If we want to add the single vector to the array
containing the N vectors, and we mistakenly try to concatenate along the first
dimension, it would fail if N != 3. But if we're unlucky, and N=3, then we'd get
a nonsensical output array of shape (3,4). Why would an array of N 3D vectors
have shape (N,3) and not (3,N)? Because if we apply python iteration to it, we'd
expect to get N iterates of arrays with shape (3,) each, and numpy iterates from
the first dimension:

#+BEGIN_EXAMPLE
>>> a = numpy.arange(2*3).reshape(2,3)

>>> a
array([[0, 1, 2],
       [3, 4, 5]])

>>> [x for x in a]
[array([0, 1, 2]), array([3, 4, 5])]
#+END_EXAMPLE

*** Manipulation of dimensions
**** atleast_xd()
Numpy has 3 special-case functions atleast_1d(), atleast_2d() and atleast_3d().
For 4d and higher, you need to do something else. These do surprising things:

#+BEGIN_EXAMPLE
>>> numpy.atleast_3d(arr(3)).shape
(1, 3, 1)
#+END_EXAMPLE

**** transpose()
Given a matrix (a 2D array), numpy.transpose() swaps the two dimensions, as
expected. Given anything else, it does not do what is expected:

#+BEGIN_EXAMPLE
>>> numpy.transpose(arr(3,      )).shape
(3,)

>>> numpy.transpose(arr(3,4,    )).shape
(4, 3)

>>> numpy.transpose(arr(3,4,5,6,)).shape
(6, 5, 4, 3)
#+END_EXAMPLE

I.e. numpy.transpose() reverses the order of ALL dimensions in the array. So if
we have N 2D matrices in a single array, numpy.transpose() doesn't transpose
each matrix.

*** Basic linear algebra
**** inner() and dot()
numpy.inner() and numpy.dot() are strange. In a real-valued n-dimensional
Euclidean space, a "dot product" is just another name for an "inner product".
Numpy disagrees.

It looks like numpy.dot() is matrix multiplication, with some wonky behaviors
when given higher-dimension objects, and with some special-case behaviors for
1-dimensional and 0-dimensional objects:

#+BEGIN_EXAMPLE
>>> numpy.dot( arr(4,5,2,3), arr(3,5)).shape
(4, 5, 2, 5) <--- expected result for a broadcasted matrix multiplication

>>> numpy.dot( arr(3,5), arr(4,5,2,3)).shape
[exception] <--- numpy.dot() is not commutative.
                 Expected for matrix multiplication, but not for a dot
                 product

>>> numpy.dot( arr(4,5,2,3), arr(1,3,5)).shape
(4, 5, 2, 1, 5) <--- don't know where this came from at all

>>> numpy.dot( arr(4,5,2,3), arr(3)).shape
(4, 5, 2) <--- 1D special case. This is a dot product.

>>> numpy.dot( arr(4,5,2,3), 3).shape
(4, 5, 2, 3) <--- 0D special case. This is a scaling.
#+END_EXAMPLE

It looks like numpy.inner() is some sort of quasi-broadcastable inner product, also
with some funny dimensioning rules. In many cases it looks like numpy.dot(a,b) is
the same as numpy.inner(a, transpose(b)) where transpose() swaps the last two
dimensions:


#+BEGIN_EXAMPLE
>>> numpy.inner( arr(4,5,2,3), arr(5,3)).shape
(4, 5, 2, 5) <--- All the length-3 inner products collected into a shape
                  with not-quite-broadcasting rules

>>> numpy.inner( arr(5,3), arr(4,5,2,3)).shape
(5, 4, 5, 2) <--- numpy.inner() is not commutative. Unexpected
                  for an inner product

>>> numpy.inner( arr(4,5,2,3), arr(1,5,3)).shape
(4, 5, 2, 1, 5) <--- No idea

>>> numpy.inner( arr(4,5,2,3), arr(3)).shape
(4, 5, 2) <--- 1D special case. This is a dot product.

>>> numpy.inner( arr(4,5,2,3), 3).shape
(4, 5, 2, 3) <--- 0D special case. This is a scaling.
#+END_EXAMPLE

* INTERFACE
** broadcast_define()
Vectorizes an arbitrary function, expecting input as in the given prototype.

SYNOPSIS

#+BEGIN_EXAMPLE
>>> import numpy as np
>>> import numpysane as nps

>>> @nps.broadcast_define( (('n',), ('n',)) )
... def inner_product(a, b):
...     return a.dot(b)

>>> a = np.arange(6).reshape(2,3)
>>> b = a + 100

>>> a
array([[0, 1, 2],
       [3, 4, 5]])

>>> b
array([[100, 101, 102],
       [103, 104, 105]])

>>> inner_product(a,b)
array([ 305, 1250])
#+END_EXAMPLE

The prototype defines the dimensionality of the inputs. In the inner product
example above, the input is two 1D n-dimensional vectors. In particular, the
'n' is the same for the two inputs. This function is intended to be used as
a decorator, applied to a function defining the operation to be vectorized.
Each element in the prototype list refers to each input, in order. In turn,
each such element is a list that describes the shape of that input. Each of
these shape descriptors can be any of

- a positive integer, indicating an input dimension of exactly that length
- a string, indicating an arbitrary, but internally consistent dimension

The normal numpy broadcasting rules (as described elsewhere) apply. In
summary:

- Dimensions are aligned at the end of the shape list, and must match the
  prototype

- Extra dimensions left over at the front must be consistent for all the
  input arguments, meaning:

  - All dimensions of length != 1 must match
  - Dimensions of length 1 match corresponding dimensions of any length in
    other arrays
  - Missing leading dimensions are implicitly set to length 1

- The output(s) have a shape where
  - The trailing dimensions are whatever the function being broadcasted
    returns
  - The leading dimensions come from the extra dimensions in the inputs

Calling a function wrapped with broadcast_define() with extra arguments
(either positional or keyword), passes these verbatim to the inner function.
Only the arguments declared in the prototype are broadcast.

Scalars are represented as 0-dimensional numpy arrays: arrays with shape (),
and these broadcast as one would expect:

#+BEGIN_EXAMPLE
>>> @nps.broadcast_define( (('n',), ('n',), ()))
... def scaled_inner_product(a, b, scale):
...     return a.dot(b)*scale

>>> a = np.arange(6).reshape(2,3)
>>> b = a + 100
>>> scale = np.array((10,100))

>>> a
array([[0, 1, 2],
       [3, 4, 5]])

>>> b
array([[100, 101, 102],
       [103, 104, 105]])

>>> scale
array([ 10, 100])

>>> scaled_inner_product(a,b,scale)
array([[  3050],
       [125000]])
#+END_EXAMPLE

Let's look at a more involved example. Let's say we have a function that
takes a set of points in R^2 and a single center point in R^2, and finds a
best-fit least-squares line that passes through the given center point. Let
it return a 3D vector containing the slope, y-intercept and the RMS residual
of the fit. This broadcasting-enabled function can be defined like this:

#+BEGIN_EXAMPLE
import numpy as np
import numpysane as nps

@nps.broadcast_define( (('n',2), (2,)) )
def fit(xy, c):
    # line-through-origin-model: y = m*x
    # E = sum( (m*x - y)**2 )
    # dE/dm = 2*sum( (m*x-y)*x ) = 0
    # ----> m = sum(x*y)/sum(x*x)
    x,y = (xy - c).transpose()
    m = np.sum(x*y) / np.sum(x*x)
    err = m*x - y
    err **= 2
    rms = np.sqrt(err.mean())
    # I return m,b because I need to translate the line back
    b = c[1] - m*c[0]

    return np.array((m,b,rms))
#+END_EXAMPLE

And I can use broadcasting to compute a number of these fits at once. Let's
say I want to compute 4 different fits of 5 points each. I can do this:

#+BEGIN_EXAMPLE
n = 5
m = 4
c = np.array((20,300))
xy = np.arange(m*n*2, dtype=np.float64).reshape(m,n,2) + c
xy += np.random.rand(*xy.shape)*5

res = fit( xy, c )
mb  = res[..., 0:2]
rms = res[..., 2]
print "RMS residuals: {}".format(rms)
#+END_EXAMPLE

Here I had 4 different sets of points, but a single center point c. If I
wanted 4 different center points, I could pass c as an array of shape (4,2).
I can use broadcasting to plot all the results (the points and the fitted
lines):

#+BEGIN_EXAMPLE
import gnuplotlib as gp

gp.plot( *nps.mv(xy,-1,0), _with='linespoints',
         equation=['{}*x + {}'.format(mb_single[0],
                                      mb_single[1]) for mb_single in mb],
         unset='grid', square=1)
#+END_EXAMPLE

The examples above all create a separate output array for each broadcasted
slice, and copy the contents from each such slice into the larger output
array that contains all the results. This is inefficient, and it is possible
to pre-allocate an array to forgo these extra allocation and copy
operations. There are several settings to control this. If the function
being broadcasted can write its output to a given array instead of creating
a new one, most of the inefficiency goes away. broadcast_define() supports
the case where this function takes this array in a kwarg: the name of this
kwarg can be given to broadcast_define() like so:

#+BEGIN_EXAMPLE
@nps.broadcast_define( ....., out_kwarg = "out" )
def func( ....., *, out):
    .....
    out[:] = result
#+END_EXAMPLE

When used this way, the return value of the broadcasted function is ignored.
In order for broadcast_define() to pass such an output array to the inner
function, this output array must be available, which means that it must be
given to us somehow, or we must create it.

The most efficient way to make a broadcasted call is to create the full
output array beforehand, and to pass that to the broadcasted function. In
this case, nothing extra will be allocated, and no unnecessary copies will
be made. This can be done like this:

#+BEGIN_EXAMPLE
@nps.broadcast_define( (('n',), ('n',)), ....., out_kwarg = "out" )
def inner_product(a, b, *, out):
    .....
    out.setfield(a.dot(b), out.dtype)

out = np.empty((2,4), np.float)
inner_product( np.arange(3), np.arange(2*4*3).reshape(2,4,3), out=out)
#+END_EXAMPLE

In this example, the caller knows that it's calling an inner_product
function, and that the shape of each output slice would be (). The caller
also knows the input dimensions and that we have an extra broadcasting
dimension (2,4), so the output array will have shape (2,4) + () = (2,4).
With this knowledge, the caller preallocates the array, and passes it to the
broadcasted function call. Furthermore, in this case the inner function will
be called with an output array EVERY time, and this is the only mode the
inner function needs to support.

If the caller doesn't know (or doesn't want to pre-compute) the shape of the
output, it can let the broadcasting machinery create this array for them. In
order for this to be possible, the shape of the output should be
pre-declared, and the dtype of the output should be known:

#+BEGIN_EXAMPLE
@nps.broadcast_define( (('n',), ('n',)),
                       (),
                       out_kwarg = "out" )
def inner_product(a, b, *, out, dtype):
    .....
    out.setfield(a.dot(b), out.dtype)

out = inner_product( np.arange(3), np.arange(2*4*3).reshape(2,4,3), dtype=int)
#+END_EXAMPLE

Note that the caller didn't need to specify the prototype of the output or
the extra broadcasting dimensions (output prototype is in the
broadcast_define() call, but not the inner_product() call). Specifying the
dtype here is optional: it defaults to float if omitted. If the dtype IS
given, the inner function must take a "dtype" argument; to use in cases
where out_kwarg isn't given, and the output array must be created by the
inner function.

If we want the
output array to be pre-allocated, the output prototype (it is () in this
example) is required: we must know the shape of the output array in order to
create it.

Without a declared output prototype, we can still make mostly- efficient
calls: the broadcasting mechanism can call the inner function for the first
slice as we showed earlier, by creating a new array for the slice. This new
array required an extra allocation and copy, but it contains the required
shape information. This infomation will be used to allocate the output, and
the subsequent calls to the inner function will be efficient:

#+BEGIN_EXAMPLE
@nps.broadcast_define( (('n',), ('n',)),
                       out_kwarg = "out" )
def inner_product(a, b, *, out=None):
    .....
    if out is None:
        return a.dot(b)
    out.setfield(a.dot(b), out.dtype)
    return out

out = inner_product( np.arange(3), np.arange(2*4*3).reshape(2,4,3))
#+END_EXAMPLE

Here we were slighly inefficient, but the ONLY required extra specification
was out_kwarg: that's all you need. Also it is important to note that in
this case the inner function is called both with passing it an output array
to fill in, and with asking it to create a new one (by passing out=None to