[Matrix-SIG] Numpy in Viper

[skaller]

Konrad Hinsen wrote:
> 
> > FISh arrays are declared like:
> >
> >       {2,3 : 4, 7 : float_shape }
> >
> > which means 2 x 3 array of 4 x 7 arrays of
> > float shaped slots.  This is similar to a NumPy
> > shaped array _except_ that it is also possible to
> > have the type of an array element be another array.
> > [This is vital]
> 
> I don't see the essential difference; it looks like a matter of
> interpretation to me. 

	Sure. That's probably correct. But 'interpretation'
is the key.

>In NumPy you would create an array of shape (2,
> 3, 4, 7), and you could then interpret it as an array of shape (2, 3)
> with elements that are arrays of shape (4, 7). NumPy indexing allows
> you not to specify the last indices, so if a is an array with the
> shape shown above, then a[1, 0] is legal and returns an array of shape
> (4, 7).

	Functional operations, such as 'map' and 'reduce'
do not use indexing; that is, they represent loops, but
the loops are not written explicitly. Therefore, the 'indexing'
scheme must be embodied in the data structure they are applied to.
 
> The interpretation becomes important only in some of the more
> complicated structural operations. 

	I believe you have this backwards (technically):
it is important in the LEAST complicated, and most fundamental
operations.

	These 'operations' tend to be 'trivial' structural isomorphisms,
such as shape reinterpretation.

>In the early stages of NumPy
> design, I proposed to adopt the convention of J (an array language
> designed by Kenneth Iverson, who is also the inventor of APL), 

	.. and who wants to use the FISh engine to 
implement J better.

>in
> which each operation has a (modifiable) rank that indicates how it
> interprets its arguments' dimensions. For example, an operation of
> rank 2 applied to the array a would treat is as a (2,3) array of (4,
> 7) arrays, whereas an operation of rank 1 would treat it as a (2, 3,
> 4) array of (7,) arrays. If I understand your description of FISh
> correctly, it uses a similar approach but makes the interpretation
> part of the arrays instead of the operations. 

	Not quite: things that reinterpret the shape are also 'operations'.
In fact, the key to the design is that things like:

	map undim array # 'undim' removes a dimension

can be interpreter two ways:

	(map undim) array

and

	map (undim array)

That the 'map' and 'undim' operations commute with array like this
is the essential point: (map undim) is a new operation, and
(undim array) is a new data structure.

> Anyway, there was no
> majority for such a general scheme, and NumPy uses axis indices for
> structural operations. And I have to admit that I could not
> present any practical example for which the more general J-style
> approach would have been better. So I'd like to ask the same
> question about FISh: where does the difference matter?

	Polymorphism. In 'classic' functional programming
languages, 'map' is type polymorphic in the sense that in

	map f list

f is a function 

	f: 'a -> 'b

where list is a list  of 'a, and the result is a list of 'b,
the point being that 'map' will accept a pair of arguments
agreeing on 'a and 'b as indicated, for _any_ 'a and 'b.
So 'map' is 'polymorphic'.  But it is ONLY very weakly
polymorphic: it is type polymorphic. That 'map' function
on lists will ONLY work with lists. So in a typical
functional language, there is another function
'array_map' for mapping arrays, and 'btree_map' for
binary trees. And for arrays, there need to be multiple
versions of map -- hundreds of them. One for every 
pair of integers (rank, depth) where depth <= rank,
so that you can map the first 'depth' dimensions
of a matrix of some greater or equal rank.

	This is necessary, because map
need to know 'how deep' to go into the data structure.

	The point of FISh is that there is exactly
one version of map -- in FISh 1, it works on arrays
of arbitrary rank, for the whole array, and this is
enough, because of the rank transforming combinators.
[The same appies to all such functions like fold/reduce,etc]


	What does this mean? It means you can write a 
program which works on matrices of ANY rank: that is,
a rank polymorphic program. Just as
you can write programs for 2D matrices of any dimensions.
This CANNOT be done using indexing, because 
each extra rank requires another loop written in
the program.

	I hope my rather poor explanation is clear.
Have a look at FISh for the designers explanation.

-- 
John Skaller, mailto:skaller@maxtal.com.au
1/10 Toxteth Rd Glebe NSW 2037 Australia
homepage: http://www.maxtal.com.au/~skaller
downloads: http://www.triode.net.au/~skaller