Re: Not quite enough abstraction

[Noel Welsh <noelwelsh@xxxxxxxxx>]

Scheme typically allows both imperative and
functional manipulation of data.  E.g. we have
fold and set-car!  This isn't the case with
vectors because, I'm guessing, nobody knew how to
do efficient functional manipulation of vectors in
1993 (or whenever R5RS was completed).  So we only
have the imperative style avaiable.  Many moons
later the situation has changed somewhat.
Languages like Sisal and SAC have shown how to
compile fast functional matrix code.

Neither Sisal nor SAC allow higher order functions
so they both define their array manipulation in
terms of a modified for loop.  An example of the
SAC version is:

  with (0 <= i <= 4)
    genarray([1 10], i * 2);

This generates the array [0 2 4 6 8 0 0 0 0 0]

There is additional syntax to the with loop that
allows you to specify a step in the index.  There
are additional array constructors that draw values
from an existing array, modifying the values
according to an expression:

  A = [1 3 5 7 9 11 13 15 17 19];
  with (0 <= i <= 4)
     modarray(A, 9, i * 2);

=> [0 2 4 6 8 19 19 19 19 19]

Note that these expressions are declarative.
There is no guaranteed order to the iteration over
i.  In fact the compiler will merge loops and
rearrange the iteration order to achieve the best
memory locality.

Two things we can get from this:

Firstly I think we all want a higher level way to
express array manipulation.  We should steal ideas
from SAC.  We can do away with the explicit index
variable (i in the examples above) by using
higher-order functions.

Secondly, this is an attractive way to create
arrays.  It allows you to allocate arrays and
initialise them with useful values in one step.
Using different constructors to modarray/genarray
above allows you to create different types of
arrays.  I.e. imagine gen-sparse-array,
gen-nested-array etc.

If the focus of this SRFI is just a basic matrix
data type then it's pretty much ok as stands.
However I think we'd all like to see some
higher-level operations.  Note that the SAC with
loop is complete - they can express all array
manipulations using it.

A array processing function similar to the SAC
with loop is:

(array-fold start end [step] [width] seed constructor)

start, end, step and width are vectors of length n
seed is an array
constructor has type (vector array) -> array

The 1st argument to constructor takes successive
values from the set

{idx | for-each i in {0 ... n-1} : start[i] <=
idx[i] <= end[i] and (idx[i] - start[i]) mod step[i] <
width[i])

(copied from the SAC paper "On Defining
Application Specific High Level Array Operations
By Means of Shape Invariant Programming Facilities")

The 2nd argument to constructor is the result of
the previous call, or seed if there has been no
previous call.

The result of array-fold is the last result of
constructor.  By allowing constructor to
destructively modify seed we allow efficient
implementations.  The alternative is to implement
array-fold as a macro and use predefined
constructors as in the SAC case.  This way we can
avoid (explicit) destructive updates at the loss
of a bit of flexibility.

Finally, has the SRFI web page been updated yet?

Noel


__________________________________________________
Do You Yahoo!?
Great stuff seeking new owners in Yahoo! Auctions! 
http://auctions.yahoo.com