Re: APL-style array indexing in Kawa - a sketch

[Jamison Hope <jrh@theptrgroup.com>]

On Aug 13, 2015, at 9:59 PM, Per Bothner <per@bothner.com> wrote:

> 
> I recently changed the various vector classes to use an index mapper:
> Every vector has two fields: a raw Java array buffer, as well as
> an IntSequence mapper which maps vector indexes to buffer indexes.
> This allows slices, rotations, permutations, etc, using the
> same same buffer:
>  (VEC I) => index I in VEC ; function-call notation for indexeing
>  (set! (VEC i) VALUE) - update value
>  (VEC [i <: J]) => slice of VEC ; same buffer, new index mapper
>  (VEC [i0 i1 ... in]) ==> [(VEC i0) (VEC i1) ... (VEC in)]
>      - but re-using the VEC buffer with a new index mapper
>  (set! (VEC [i <: J]) VALUE) - replace elements (possible re-size)

In this last example, VALUE is a sequence and not an atom, right?  So:

(define v (make-vector 5 0)) ;; -> #(0 0 0 0 0)

(set! (v [2 <: 4]) 1) ;; error!

(set! (v [2 <: 4]) #(1 1)) ;; -> v is now #(0 0 1 1 0)

(set! (v [2 <: 4]) #(1)) ;; -> v is now #(0 0 1 0)

> Kawa also supports multi-dimensional arrays, based on SRFI-25, and you
> can use the same function-call notation:
>  (ARR X Y)
>  (set! (ARR X Y) VALUE)
> SRFI-25 (and Kawa) has functions for slices, transpose, rotations, etc.
> However, I'd like to have APL-style array-as-index for general arrays:
>  (ARR [A <: B] Y [c <: D])
>  (ARR [5 2 6] [2 3])

So the way to read this is that it constructs a new 3x2 2D array which
shares backing store with ARR, and its six elements in row-major order
are (ARR 5 2), (ARR 5 3), (ARR 2 2), (ARR 2 3), (ARR 6 2), and (ARR 6 3),
right?


Is there some clever notation for a range meaning "from here to the end,
wherever that is"?  (VEC [i <: ]) doesn't work;
(VEC [i <: (length VEC)]) works, but seems verbose.

Matlab (which uses 1-based indexing) lets you do things like A(2:end) to
extract all-but-the-first element.  Also, for dimensions for which you
want the whole thing, instead of writing "1:end" you can use ":" as
shorthand:  A(:,3) means the whole third column (regardless of the
number of rows), and A(3,:) means the whole third row (regardless of the
number of columns).


>  (ARR IARR1 IARR2 IARR3)
> 
> The bulk of this note shows (tersely) the types, classes, and
> basic representation of generalized arrays.  It focuses on the
> differences from the version of gnu.lists in the Kawa trunk.
> The actual Scheme API (in terms of functions) is a later discussion;
> initially we will prioritize array construction plus indexing.
> 
> * Is this a feature you'd find exciting and/or use it?

I can definitely think of math-ish things to do with something like this.

If I have a 4x4 matrix T representing a spatial transformation, then
(T [0 <: 3] [0 <: 3]) would be the upper-left 3x3 submatrix, which would
be a rotation matrix that magically stays in sync with the original
transform data.  That could be handy.

The values at [(T 0 3) (T 1 3) (T 2 3)] are the translation vector.
Using this new notation, that's *almost* the same as (T [0 <: 3] [3]),
except that the latter gives me a 3x1 2D matrix rather than a 3-element
1D vector.

Will there be some simple way to flatten the result to reduce its rank
so I can omit the index that would always be 0?

> * Would your friends or co-workers find it exciting and/or use it?

They may, if I tell them to.. most likely they would use it unknowingly
by using some program that I wrote (there aren't a lot of Schemers or
Lispers -- or Java-ers, really -- here).

> * I know computers and data structures.  I don't know matrixes or math, much.
>  Would this approach cause problems if trying to to do high-performace
>  array/matrix manipulations, or interfacing to other libraries?

It's kind of hard to say.  It depends whether the added indirection of
the index mapper introduces more overhead than the gain from not
allocating a new data store and copying over the values at array
creation time, right?  It certainly *seems* like it would be a win, at
least for arrays larger than some size N (wherever the size of the data
starts to outgrow the size of the index mapper object).

What would be the idiomatic way to do a deep(?) copy, to break the
connection with the original data buffer?  One situation I can think of
where the sharing could cause trouble would be passing the sub-vector to
something like an in-place sort function, where we might not actually
want to overwrite the parent array's data.


> * Would you be interested in helping out?


I'll certainly try it out and let you know if stuff doesn't work, but I
don't know how much help I would be with the actual implementation.

--
Jamison Hope
The PTR Group
www.theptrgroup.com