macro for efficient array operations 
Author Message
 macro for efficient array operations

Hi,

I am trying to implement an array oriented sublanguage in Scheme.
I can't find a way (I am a little newbie) for building a macro which does
the following :

If A,B,C are vectors of vectors, I want to be able to express :
    C[i,j] = A[i,j] + B[i,j]     for all i,j (i,j being the indices)

In C/C++, this gives trivially:
for(int i=0;i<I;i++)
    for(int j=0;j<J;j++)
            C[i][j] = A[i][j] + B[i][j];

In Scheme, I would like to be able to write:
(tensor (i j) (assign-to (C i j) (+ (A i j) (B i j))))

Other examples for the notation is :
(tensor (i j) (assign-to (B i j) (A j i)))    will do B[i,j] = A[j,i]
(Transposition)
(tensor (i j k) (assign-to (C i j k) (+ (A i j) (B j k))))    will do
C[i,j,k] = A[i,j] + B[j,k]  (where C is a vector of vector of vector)

How can I implement the macro tensor to be able to deal with any number of
indices (i j ... ) and to do what I have described ?

Thank you for your help
Sebastien



Wed, 21 Jan 2004 00:17:14 GMT  
 macro for efficient array operations

Quote:
> If A,B,C are vectors of vectors, I want to be able to express :
>     C[i,j] = A[i,j] + B[i,j]     for all i,j (i,j being the indices)

> In C/C++, this gives trivially:
> for(int i=0;i<I;i++)
>     for(int j=0;j<J;j++)
>             C[i][j] = A[i][j] + B[i][j];

This doesn't look so trivial to me.  The I and J came out
of thin air.  Do you expect the computer to read your mind?

In Scheme you could tell the computer to assume that the
i and j range over the valid indices of the array on the
left hand side of the assignment, but this wouldn't have
worked in C/C++.

Quote:
> In Scheme, I would like to be able to write:
> (tensor (i j) (assign-to (C i j) (+ (A i j) (B i j))))

> Other examples for the notation is :
> (tensor (i j) (assign-to (B i j) (A j i)))    will do B[i,j] = A[j,i]
> (Transposition)
> (tensor (i j k) (assign-to (C i j k) (+ (A i j) (B j k))))    will do
> C[i,j,k] = A[i,j] + B[j,k]  (where C is a vector of vector of vector)

> How can I implement the macro tensor to be able to deal with any number of
> indices (i j ... ) and to do what I have described ?

I think this is a confusing syntax because (A i j) is the
standard syntax for a procedure call in Scheme.  By using
this syntax for array references, you make it impossible
to mix arbitrary procedure calls with arbitrary array
references within a tensor expression.

If you insist on doing this, however, and you are content
to support only a finite number of arithmetic operations
such as +, and to assume that all other expressions of
the form (A i j) represent array references, then the
following syntax definitions will do what you say you
want.

(define-syntax tensor
  (syntax-rules (assign-to)
    ((tensor (?i) (assign-to (?V ?ii) ?rhs))
     (let* ((v ?V)
            (n (vector-length v)))
       (do ((?i 0 (+ ?i 1)))
           ((= ?i n))
           (vector-set! v ?ii (tensor-auxiliary ?rhs)))))
    ((tensor (?i ?j ?k ...) (assign-to (?V ?ii ?jj ...) ?rhs))
     (let* ((v ?V)
            (n (vector-length v)))
       (do ((?i 0 (+ ?i 1)))
           ((= ?i n))
           (tensor (?j ?k ...)
             (assign-to ((vector-ref ?V ?ii) ?jj ...) ?rhs)))))))

(define-syntax tensor-auxiliary
  (syntax-rules (+ - *)
    ; one syntax clause for each of the recognized operations
    ((tensor-auxiliary (+ ?exp ...))
     (+ (tensor-auxiliary ?exp) ...))
    ((tensor-auxiliary (- ?exp ...))
     (- (tensor-auxiliary ?exp) ...))
    ((tensor-auxiliary (* ?exp ...))
     (* (tensor-auxiliary ?exp) ...))
    ; two syntax clauses for array references
    ((tensor-auxiliary (?A ?i))
     (vector-ref ?A ?i))
    ((tensor-auxiliary (?A ?i ?j ...))
     (tensor-auxiliary ((vector-ref ?A ?i) ?j ...)))))

Will



Wed, 21 Jan 2004 03:24:21 GMT  
 macro for efficient array operations



Quote:
> > If A,B,C are vectors of vectors, I want to be able to express :
> >     C[i,j] = A[i,j] + B[i,j]     for all i,j (i,j being the indices)

> > In C/C++, this gives trivially:
> > for(int i=0;i<I;i++)
> >     for(int j=0;j<J;j++)
> >             C[i][j] = A[i][j] + B[i][j];

> This doesn't look so trivial to me.  The I and J came out
> of thin air.  Do you expect the computer to read your mind?

I agree, I gave the example in C/C++ to give a "feeling" of what I want (I
and J should have been defined before).

Quote:

> In Scheme you could tell the computer to assume that the
> i and j range over the valid indices of the array on the
> left hand side of the assignment, but this wouldn't have
> worked in C/C++.

> > In Scheme, I would like to be able to write:
> > (tensor (i j) (assign-to (C i j) (+ (A i j) (B i j))))

> > Other examples for the notation is :
> > (tensor (i j) (assign-to (B i j) (A j i)))    will do B[i,j] = A[j,i]
> > (Transposition)
> > (tensor (i j k) (assign-to (C i j k) (+ (A i j) (B j k))))    will do
> > C[i,j,k] = A[i,j] + B[j,k]  (where C is a vector of vector of vector)

> > How can I implement the macro tensor to be able to deal with any number
of
> > indices (i j ... ) and to do what I have described ?

> I think this is a confusing syntax because (A i j) is the
> standard syntax for a procedure call in Scheme.  By using
> this syntax for array references, you make it impossible
> to mix arbitrary procedure calls with arbitrary array
> references within a tensor expression.

That's true, if you have a better notation for that, maybe replacing some (A
i j) expressions with '(A i j), it is welcome.
Again, I am trying to give the global objective for the macro. It would also
be nice if it is possible to add conditions on the indices like ( (< i 4) j)
instead of (i j) to make the modifications only for the indicies (i,j) with
i<4.
The ability to mix arbitrary procedure calls with arbitrary array references
will be a really valuable feature.

Sebastien



Wed, 21 Jan 2004 20:36:42 GMT  
 macro for efficient array operations

Quote:
> That's true, if you have a better notation for that, maybe replacing some (A
> i j) expressions with '(A i j), it is welcome.
> Again, I am trying to give the global objective for the macro. It would also
> be nice if it is possible to add conditions on the indices like ( (< i 4) j)
> instead of (i j) to make the modifications only for the indicies (i,j) with
> i<4.
> The ability to mix arbitrary procedure calls with arbitrary array references
> will be a really valuable feature.

> Sebastien

It sounds like what you want can be achieved with array
comprehensions.  Take a look at Single Assignment C
(http://www.informatik.uni-kiel.de/~sacbase/) for examples of array
comprehensions (also Haskell and Clean).  An example (in a vaguely
Haskell/Clean-ish syntax):

(define (dot-product a b)
  ( x * y | x in a, y in b))

Which translates to: the dot-product of a and b is the product of each
element x in a and y in b.

Someday I'd like to write a similar array package for Scheme...

Noel



Fri, 23 Jan 2004 15:33:07 GMT  
 macro for efficient array operations

Quote:

> > > In Scheme, I would like to be able to write:
> > > (tensor (i j) (assign-to (C i j) (+ (A i j) (B i j))))

As Will noted, this is missing vital information and is also somewhat
restrictive of the operations permissible within the TENSOR special
form.

Something like:

(tensor-for-each (A B C) (i j)
   (tensor-set! C (+ (tensor-ref A i j)
                     (tensor-ref B i j))))

would be rather more Scheme-like. TENSOR-FOR-EACH is still a special
form here (because of the list notation for the list of tensors). A
fully procedural abstraction would look like:

(tensor-for-each
   (lambda (i j)
      (tensor-set! C (+ (tensor-ref A i j)
                        (tensor-ref B i j))))
   A B C)

The salient points of both forms being that TENSOR-FOR-EACH needs to
be able to look at each of the tensors to derive the correct shape of
the iteration. This also gives you an oppurtunity to detect various
type problems (mismatching dimensionalities, different basis sizes,
etc...) A very naive implementation (completely untested and essentially
pulled directly out of my arse) that uses SRFI-9 for the tedious
structure definition bits follows immediately:

(define-record-type tensor
   ; going to use a flattened data representation instead of
   ; a vector of vectors; just for grins
   (make-tensor dimension-vector data)
   tensor?
   (dimension-vector tensor-shape tensor-shape!)
   (data tensor-data tensor-data!))

(define (tensor-dimensionality tensor) (vector-length (tensor-shape tensor)))
(define (tensor-dimension tensor n) (vector-ref (tensor-shape tensor) n))

(define (tensor-validate-indices t . indices)
   (let ((requested-shape (length indices))
         (shape (tensor-shape t)))
      (if (= requested-shape (tensor-dimensionality t))
          (let build ((dim 0) (indices indices) (data-ref 0))
             (if (null? indices)
                 data-ref
                 (let ((index (car indices))
                       (dimension (tensor-dimension t dim)))
                    (and (< index dimension)
                         (build (+ dim 1)
                                (cdr indices)
                                (+ (* data-ref dimension)
                                   index))
                         )))))))

(define (tensor-ref tensor . indices)
   (let ((index (tensor-validate-indices tensor indices)))
      (if index
          (vector-ref (tensor-data tensor index))
          (error 'invalid-tensor-ref))))

(define (tensor-set! tensor val . indices)
   (let ((index (tensor-validate-indices tensor indices)))
      (if index
          (vector-set! (tensor-data tensor index) val)
          (error 'invalid-tensor-ref))))

(define-syntax tensor-for-each
   ; because I think that the special form is more readable
   ; and has slightly greater potential for robustness...
   (syntax-rules ()
      ((tensor-for-each (tensor0 tensor+ ...)
                        (index0 index+ ...)
                        exp0 exp+ ...)
       (%tensor-for-each (list tensor0 tensor+ ...)
                         (length '(index0 index+ ...))
                         (lambda (index0 index+ ...) exp0 exp+ ...)))
      ))

(define (%tensor-for-each ts iteration-depth f)
   (if (pair? ts)
       (let ((basic-shape (tensor-shape (car ts))))
          (if (fold (lambda (t valid?)
                       (and valid?
                            (< (- iteration-depth 1)
                               (tensor-dimensionality t))
                            (equal? basic-shape (tensor-shape t))
                            ))
                    #t
                    ts)
              (for-all-tuples-in (vector-take basic-shape iteration-depth) f)
              ))))

FOLD, FOR-ALL-TUPLES-IN, and VECTOR-TAKE are left as an exercise for the reader.

Quote:
> > > Other examples for the notation is :
> > > (tensor (i j) (assign-to (B i j) (A j i)))    will do B[i,j] = A[j,i]
> > > (Transposition)
> > > (tensor (i j k) (assign-to (C i j k) (+ (A i j) (B j k))))    will do
> > > C[i,j,k] = A[i,j] + B[j,k]  (where C is a vector of vector of vector)

recasting these with my definitions:

(tensor-for-each (A B) (i j) (tensor-set! B (tensor-ref A j i) i j))
(tensor-for-each (A B C) (i j k)
   (tensor-set! C (+ (tensor-ref A i j) (tensor-ref B j k))
                i j k))

OK, the fact that the variable-length indices must be last arguments
to the tensor mutator is annoying, but that could be macrologized,
too. e.g.

(define-syntax tensor
   (syntax-rules (set ref)
      ((tensor set t (ix0 ix+ ...) v) (tensor-set! t v ix0 ix+ ...))
      ((tensor ref t (ix0 ix+ ...) v) (tensor-ref t ix0 ix+ ...))
      ))

or somesuch (again *completely* untested).

Quote:
> > > How can I implement the macro tensor to be able to deal with any number
> > >  of indices (i j ... ) and to do what I have described ?

I hope that I have added some value to Will Clinger's observation. The
above, while not exactly providing the forms you wanted, captures the
fundamental abstractions which I think you were expressing in a more
flexible fashion. HTH.

david rush
--
The beginning of wisdom for a [software engineer] is to recognize the
difference between getting a program to work, and getting it right.
-- M A Jackson, 1975



Sun, 25 Jan 2004 17:24:45 GMT  
 macro for efficient array operations

Quote:
> I hope that I have added some value to Will Clinger's observation. The
> above, while not exactly providing the forms you wanted, captures the
> fundamental abstractions which I think you were expressing in a more
> flexible fashion. HTH.

> david rush
> --
> The beginning of wisdom for a [software engineer] is to recognize the
> difference between getting a program to work, and getting it right.
> -- M A Jackson, 1975

That is exactly the answer I was looking for  !!!
I will work on it as a basis for my personal project (write a pseudo-tensor
language to write algorithms and make Scheme produce efficient C/C++ code in
a bug-free way).

Thanks a lot.
Sebastien



Mon, 26 Jan 2004 15:35:54 GMT  
 
 [ 6 post ] 

 Relevant Pages 

1. efficient vector/matrix operations in Ada

2. Efficient nibble-operations

3. Space efficient sorting of arrays

4. Space efficient sorting of arrays

5. J/APL memory use [was Re: SV: Space efficient sorting of arrays]

6. re efficient sorting of arrays

7. Efficient Mutable Arrays

8. Is Ruby Array#shift/unshift Efficient?

9. An efficient way to pass 3-D arrays to functions

10. Efficient way to pass different shaped arrays?

11. most efficient placement of array declarations?

12. Efficient ways to pass arrays, contd.

 

 
Powered by phpBB® Forum Software