Re: propose deprecation of generalized-vector-*

[Daniel Llorens <daniel.llorens@bluewin.ch>]

[-- Attachment #1: Type: text/plain, Size: 5809 bytes --]


On Feb 18, 2013, at 16:55, Andy Wingo wrote:

> It could make sense, yes.  What do others think?  What happens for
> array-set!?  Care to propose a patch?

Patch is attached. It looks a bit unwieldy because I am duplicating scm_array_handle_pos(), and I also had to fix the recent array_ref_1 optimization, but it shouldn't be slower for the old use. 

array-set! does what you would expect, obj must be an array of rank = the number of indices missing.

(define A #2((0 1) (2 3)))
(array-set! A #(7 8) 0)
A => #2((7 8) (2 3))

When all the indices are given, it works exactly as before, so one can still do stupid things like

(define A #2((0 1) (2 3)))
(array-set! A #0(9) 0 0)

and get

A => #2((#0(9) 1) (2 3))

and not

A => #2((9 1) (2 3)).

The lesson is to avoid rank-0 arrays except in the deep of libraries.

arrays.test fails in three places. Twice because I don't fail with the right exception 'wrong-num-indices', I don't know how to do that. Once because (array-set! rank-2 one index) doesn't fail on the missing index, but on the attempted copy. I haven't fixed these tests and I haven't added more.

---

It was interesting to read the other replies, thank you (plural). It was disappointing that nobody seems to be using arrays, but not very surprising. I use them a fair amount, but mostly for interfacing with C/C++. I do little with them in Guile since 1) the facilities are really not there or they are inconvenient to use, 2) when I need arrays I need speed and Guile isn't there either (yet!).

More than getting this patch accepted (as it is or with different function names), my concern is that what this patch does cannot be done on the user side except through make-shared-array, which is too slow. So I think there's a good argument that scm_i_make_array(), SCM_I_ARRAY_V(), SCM_I_ARRAY_BASE() and SCM_I_ARRAY_DIMS() should be published.

Now some optional motivation:

In other languages that have arrays, rank-0 arrays are not differentiated from the scalar inside. This is the right approach if you want to treat arrays of any rank as values. Then you can say that a rank-n array is

-------------------
a rank-n array of rank-0 cells
a rank-(n-1) array of rank-1 cells
...
a rank-1 array of rank-(n-1) cells
a rank-0 array of rank-n cells = a rank-n cell.

Figure 1.
-------------------

The extended versions of array-ref and array-set! allow you to use a rank-n array as any of these.

Old Guile used to have something called ‘enclosed arrays’, they are described in the 1.6 manual. This is a mechanism inspired by APL that allows one to split an array as in Figure 1, so that if you have a function that operates on rank-k arrays, you can array-map! it on arrays of any rank >= k.

Example:

(define A #((1 2) (3 4) (5 6))
(define (sqr x) (* x x))
(define (norm v) (+ (sqr (array-ref v 0)) (sqr (array-ref v 1))))
(define out #(0 0 0))
(array-map! out norm (enclosed-array A 1))

out => #(5 25 61), hopefully (I don't have Guile 1.6 here to try).

In later versions of APL (and most obviously in J) people realized that this is a bad way to go about things, since the reason you want to split A in rank-1 cells is ‘norm’. That is, rank-1 is a property of the function ‘norm’. And you don't need to do any conversions to iterate over the rank-1 cells of A; you only need to move a pointer on each iteration, but to do this array-map! should be aware of the rank of the procedure in each of its arguments.

I didn't want to mess with the C implementation of array-map! for what is only a proof of concept. One can do something passable in Guile by using the version of array-ref in the patch, since

(array-ref A 0) -> #(1 2), apply norm to this
(array-ref A 1) -> #(3 4), apply norm to this, etc.

I have a module that does this, not much more. I'll see if I can upload it somewhere, it could use a review.

Finally, to fuel the discussion of what kind of array operations Guile should provide, here is a list similar things that I have read about. I imagine there are many more. The software is all open source.

Scheme (!)
http://trac.sacrideo.us/wg/wiki/ArraysCowan
This is a proposal for R7RS large, very early-stages.

Python
http://www.scipy.org/Tentative_NumPy_Tutorial

Haskell
http://research.microsoft.com/en-us/um/people/simonpj/papers/ndp/rarrays.pdf
http://www.haskell.org/haskellwiki/Numeric_Haskell:_A_Repa_Tutorial

Perl
http://pdl.perl.org/

J
http://www.jsoftware.com/
http://www.jsoftware.com/help/jforc/contents.htm — I like this one a lot. There're also many classic articles on APL on the jsoftware site.

C++
http://blitz.sourceforge.net/
This one is dying for somebody to port it to C++11, but it does general rank (although compile-time only) and has clever features, e.g. TensorIndex.

There's also Matlab/Octave (bad language, I'm not a fan).

There's Fortran, for which I don't have a good link, but a lot of the array-compiler literature is about Fortran. There's SAC (http://www.sac-home.org/) as an example of a very ‘static’ array language. There're array languages targeting supercomputers, e.g. ZPL (http://www.cs.washington.edu/research/zpl/home/). 

Myself I have used Matlab way too much and numpy some. I have played with the J interpreter.

> Uniform vectors are just bytevectors.  The only difference between the
> different kinds of uniform vectors is a "type" field indicating the
> "natural" type of the object.  The type field is set when a bytevector
> is created, and is used in the generic array-ref functionality, and in
> the printer.
> 
> One consequence is that you can (s8vector-ref #u8(#xff) 0) => -1.

c64 <-> f64 is something that I have found useful myself.

Regards,

	Daniel

------------------


[-- Attachment #2: 0001-Extend-array-ref-array-set-to-work-with-cells-of-ran.patch --]
[-- Type: application/octet-stream, Size: 6874 bytes --]

From f85aaa7dec597b1d45830a3d346b55f3d3cefbff Mon Sep 17 00:00:00 2001
From: Daniel Llorens <daniel.llorens@bluewin.ch>
Date: Wed, 20 Feb 2013 22:44:06 +0100
Subject: [PATCH] Extend array-ref, array-set! to work with cells of rank > 0

* libguile/generalized-arrays.c
  - scm_array_ref: if the index list comes up short, return the cell at the
    position computed up to then.
  - scm_array_set_x: if the index list comes up short, use the cell at the
    position computed up to then as destination for o.
  - s_scm_i_array_ref: branch to the optimization only if rank of v matches.
  - s_scm_i_array_set_x: idem.
---
 libguile/generalized-arrays.c | 127 ++++++++++++++++++++++++++++++++++--------
 1 file changed, 103 insertions(+), 24 deletions(-)

diff --git a/libguile/generalized-arrays.c b/libguile/generalized-arrays.c
index 9382e81..086019f 100644
--- a/libguile/generalized-arrays.c
+++ b/libguile/generalized-arrays.c
@@ -256,17 +256,49 @@ scm_c_array_ref_2 (SCM array, ssize_t idx0, ssize_t idx1)
   return res;
 }
 
-
 SCM
-scm_array_ref (SCM v, SCM args)
+scm_array_ref (SCM a, SCM args)
 {
-  scm_t_array_handle handle;
-  SCM res;
-
-  scm_array_get_handle (v, &handle);
-  res = scm_array_handle_ref (&handle, scm_array_handle_pos (&handle, args));
-  scm_array_handle_release (&handle);
-  return res;
+  int k, arank;
+  ssize_t pos = 0;
+  SCM i = args;
+  SCM o;
+  scm_t_array_handle ah;
+  scm_t_array_dim * as;
+  scm_array_get_handle (a, &ah);
+  as = scm_array_handle_dims (&ah);
+  k = arank = scm_array_handle_rank (&ah);
+  for (; k>0 && scm_is_pair (i); --k, ++as, i=scm_cdr (i)) {
+    ssize_t ik = scm_to_ssize_t (scm_car (i));
+    if (ik<as->lbnd || ik>as->ubnd) {
+      scm_array_handle_release (&ah);
+      scm_out_of_range (NULL, scm_list_2 (a, args));
+    }
+    pos += (ik-as->lbnd)*as->inc;
+  }
+  if (k>0) {
+    if (k==arank) {
+      o = a;
+    } else {
+      scm_t_array_dim * os;
+      o = scm_i_make_array (k);
+      SCM_I_ARRAY_V (o) = SCM_I_ARRAY_V (a);
+      SCM_I_ARRAY_BASE (o) = pos + SCM_I_ARRAY_BASE (a); /* since arank>1. */
+      os = SCM_I_ARRAY_DIMS (o);
+      for (; k>0; --k, ++as, ++os) {
+        os->ubnd = as->ubnd;
+        os->lbnd = as->lbnd;
+        os->inc = as->inc;
+      }
+    }
+  } else if (scm_is_null (i)) {
+    o = scm_array_handle_ref (&ah, pos); /* these may be non-arrays. */
+  } else {
+    scm_array_handle_release (&ah);
+    scm_misc_error (NULL, "too many indices", scm_list_2 (a, args));
+  }
+  scm_array_handle_release (&ah);
+  return o;
 }
 
 
@@ -295,29 +327,70 @@ scm_c_array_set_2_x (SCM array, SCM obj, ssize_t idx0, ssize_t idx1)
 
 
 SCM
-scm_array_set_x (SCM v, SCM obj, SCM args)
+scm_array_set_x (SCM a, SCM o, SCM args)
 {
-  scm_t_array_handle handle;
-
-  scm_array_get_handle (v, &handle);
-  scm_array_handle_set (&handle, scm_array_handle_pos (&handle, args), obj);
-  scm_array_handle_release (&handle);
+  int k, arank;
+  ssize_t pos = 0;
+  SCM i = args;
+  scm_t_array_handle ah;
+  scm_t_array_dim * as;
+  scm_array_get_handle (a, &ah);
+  as = scm_array_handle_dims (&ah);
+  k = arank = scm_array_handle_rank (&ah);
+  for (; k>0 && scm_is_pair (i); --k, ++as, i=scm_cdr (i)) {
+    ssize_t ik = scm_to_ssize_t (scm_car (i));
+    if (ik<as->lbnd || ik>as->ubnd) {
+      scm_array_handle_release (&ah);
+      scm_misc_error (NULL, "out of range", scm_list_2 (a, args));
+    }
+    pos += (ik-as->lbnd)*as->inc;
+  }
+  if (k>0) {
+    SCM ai;
+    if (k==arank) {
+      ai = a;
+    } else {
+      scm_t_array_dim * ais;
+      ai = scm_i_make_array (k);
+      SCM_I_ARRAY_V (ai) = SCM_I_ARRAY_V (a);
+      SCM_I_ARRAY_BASE (ai) = pos + SCM_I_ARRAY_BASE (a); /* since arank>1. */
+      ais = SCM_I_ARRAY_DIMS (ai);
+      for (; k>0; --k, ++as, ++ais) {
+        ais->ubnd = as->ubnd;
+        ais->lbnd = as->lbnd;
+        ais->inc = as->inc;
+      }
+    }
+    /* an error is still possible here if o and ai don't match. */
+    scm_array_copy_x (o, ai);
+  } else if (scm_is_null(i)) {
+    scm_array_handle_set (&ah, pos, o);
+  } else {
+    scm_array_handle_release (&ah);
+    scm_misc_error (NULL, "too many indices", scm_list_2 (a, args));
+  }
   return SCM_UNSPECIFIED;
 }
 
 
 SCM_DEFINE (scm_i_array_ref, "array-ref", 1, 2, 1,
             (SCM v, SCM idx0, SCM idx1, SCM idxN),
-	    "Return the element at the @code{(idx0, idx1, idxN...)}\n"
-            "position in array @var{v}.")
+	    "Return the rank-(n-k) cell at the @code{(idx0 idx1 .. idx(k-1))}\n"
+            "position in n-rank array @var{v}.")
 #define FUNC_NAME s_scm_i_array_ref
 {
   if (SCM_UNBNDP (idx0))
     return scm_array_ref (v, SCM_EOL);
   else if (SCM_UNBNDP (idx1))
-    return scm_c_array_ref_1 (v, scm_to_ssize_t (idx0));
+    if (scm_c_array_rank (v)==1)
+      return scm_c_array_ref_1 (v, scm_to_ssize_t (idx0));
+    else
+      return scm_array_ref (v, scm_cons (idx0, SCM_EOL));
   else if (scm_is_null (idxN))
-    return scm_c_array_ref_2 (v, scm_to_ssize_t (idx0), scm_to_ssize_t (idx1));
+    if (scm_c_array_rank (v)==2)
+      return scm_c_array_ref_2 (v, scm_to_ssize_t (idx0), scm_to_ssize_t (idx1));
+    else
+      return scm_array_ref (v, scm_cons (idx0, scm_cons (idx1, SCM_EOL)));
   else
     return scm_array_ref (v, scm_cons (idx0, scm_cons (idx1, idxN)));
 }
@@ -326,17 +399,23 @@ SCM_DEFINE (scm_i_array_ref, "array-ref", 1, 2, 1,
 
 SCM_DEFINE (scm_i_array_set_x, "array-set!", 2, 2, 1,
             (SCM v, SCM obj, SCM idx0, SCM idx1, SCM idxN),
-	    "Set the element at the @code{(idx0, idx1, idxN...)} position\n"
-	    "in the array @var{v} to @var{obj}.  The value returned by\n"
-            "@code{array-set!} is unspecified.")
+	    "Set the rank-(n-k) cell at the @code{(idx0 idx1 .. idx(k-1))}\n"
+            "position in the n-rank array @var{v} to the k-rank array\n"
+            "@var{obj}.  The value returned is unspecified.")
 #define FUNC_NAME s_scm_i_array_set_x
 {
   if (SCM_UNBNDP (idx0))
     scm_array_set_x (v, obj, SCM_EOL);
   else if (SCM_UNBNDP (idx1))
-    scm_c_array_set_1_x (v, obj, scm_to_ssize_t (idx0));
+    if (scm_c_array_rank (v)==1)
+      scm_c_array_set_1_x (v, obj, scm_to_ssize_t (idx0));
+    else
+      scm_array_set_x (v, obj, scm_cons (idx0, SCM_EOL));
   else if (scm_is_null (idxN))
-    scm_c_array_set_2_x (v, obj, scm_to_ssize_t (idx0), scm_to_ssize_t (idx1));
+    if (scm_c_array_rank (v)==2)
+      scm_c_array_set_2_x (v, obj, scm_to_ssize_t (idx0), scm_to_ssize_t (idx1));
+    else
+      scm_array_set_x (v, obj, scm_cons (idx0, scm_cons (idx1, SCM_EOL)));
   else
     scm_array_set_x (v, obj, scm_cons (idx0, scm_cons (idx1, idxN)));
 
-- 
1.8.1.1


[-- Attachment #3: Type: text/plain, Size: 2 bytes --]