[Matrix-SIG] Numpy in Viper

[skaller]

Hi. I have reached that stage of development of Viper,
my python interpreter/compiler, that I'm considering
a built-in array type. I've been looking at NumPy,
which seems pretty good, and now have some questions.

First, my idea was to add FISh 1 style arrays to Viper.
FISh is the most advanced array processing language available,
it uses shape analysis to generate optimal code, and is
suited to parallelization. I happened to write the FORTRAN
back end for FISh 1, and the experience using ocaml,
the implementation language, is partly responsible for
trying my hand at an ocaml based python compiler.

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]

FISh uses combinators to manipulate
the shape, based on category theory, so that
a new higher power kind of polymorphism is made
available. To illustrate, consider the 'map'
function. When you map a 2 x 3 array of
floats, the argument function is a function
from floats to something, the result is a 2 x 3
array of somethings.

Suppose you want to map the 2 x 3 array, to an
array of 2 elements, each being the sum of the
three row elements. (or is that columns? Anyhow ..)

We need to 'reshape' the array so we can use
the accumulation function. We can do this by
changing the shape from

	{ 2,3 : float_shape }

to

	{ 2 : 3 : float_shape }

and now we can map accumulate over the array,
which is ONE dimensional array with 2 elements,
to get a ONE dimensional array with 2 elements.

This mechanism applies to all array functions
like reduce (fold_left), etc. It allows to
write functions (like map) which work on any
kind of array at 'any level'.

I hope I have explained the idea well enough.
The fundamental difference to NumPy is that

	a) array elements are arrays
	b) shapes require a tuple of tuples to represent them


Now, the reason I am posting is that compatibility
and utility are, as usual, in conflict. My plan for Viper,
for example, is that arrays be built-in, and standard
No module: arrays become fundamental types. The reason is
that the compiler can then do optimisations.

I do not think I can achieve FISh quality optimisation
because of the non-statically typed nature of Python,
however, some good optimisations should be possible.

Any comments will be appreciated. you can check out
FISh 1 at:

	http://www-staff.mcs.uts.edu.au/~cbj/FISh/

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