Pass subarray by reference (not by value) in Common Lisp

Question

Let's suppose I have an array - which I will call *my-array* - that looks like this:

#2A((1 2 3)
    (4 5 6)
    (7 8 9))

and I wish to apply some function f on the subarray

#2A((5 6)
    (8 9))

I'd love to be able to write

(f (subarray *my-array* '(1 2) '(1 2))

where subarray takes as arguments:

• the original array
• a 2-element list with starting point and ending point on the 1st dimension
• another 2-element list with starting point and ending point on the 2nd dimension
• etc.

I am looking for some way to pass the subarray as argument to function f by reference (or by pointer?) instead of by value.

(The dumb way to address this would be to write a function that creates (in this specific case) a 2*2 array and loops over i and j copying values from the original array. However, if you are dealing relatively large arrays, this would be quite costly.)

I found there exists a cl-slice package but I do not get whether it copies values or accesses data by reference.

Answer 1

Common Lisp has Displaced Arrays which are exactly what you are asking about (see array-displacement &c).

However, in your case, displaces arrays are no help because:

Multidimensional arrays store their components in row-major order; that is, internally a multidimensional array is stored as a one-dimensional array, with the multidimensional index sets ordered lexicographically, last index varying fastest.

This means that your subarray is not a contiguous section of your main array, and, thus, you cannot create another array displaced to it.

PS. If you cannot figure out how cl-slice works, you can use time to see how much memory it uses and make your inference from that.

PPS. It is, in fact, not too hard to whip up something like what you want:

(defmacro slice (array &rest ranges)
  "Return an accessor into ARRAY randing in RANGES."
  (let ((args (loop for r in ranges collect (gensym "SLICE-ARG-")))
        (arr (gensym "SLICE-ARRAY-")))
    `(let ((,arr ,array))
       (lambda ,args
         (aref ,arr
               ,@(loop for arg in args and (lo hi) in ranges
                   for range = (- hi lo)
                   collect
                     `(progn
                        (unless (<= 0 ,arg ,range)
                          (error "~S is out of range [0;~S]" ,arg ,range))
                        (+ ,lo ,arg))))))))

(defparameter *my-array*
  #2A((1 2 3)
      (4 5 6)
      (7 8 9)))

(defparameter f (slice *my-array* (1 2) (1 2)))

(loop for i from 0 to 1 do
    (loop for j from 0 to 1 do
        (format t " ~S" (funcall f i j)))
    (terpri))
 5 6
 8 9

Answer 2

I don't think it is possible to do exactly what you want to do. In memory, multidimensional arrays are implemented as a single flat array with some metadata which is used to convert from the multidimensional interface to the flat one. In your case *my-array* would look like this:

#(1 2 3 4 5 6 7 8 9)

If you had the subarray you desired as a reference to the original array, it would look like this:

#(5 6 _ 8 9)

Which is impossible since you are trying to skip the 7 of the original array. If all of the desired elements were part of a contiguous sub-sequence, you would be able to use the :displaced-to argument of make-array in order to copy the sub-sequence by reference, but unfortunately, that is not the case.

Answer 3

As others pointed out, you cannot use displaced arrays for matrices (maybe you could with non-standard functions). But all you need is to change how you interact with the original array. Here are some possibilities.

Sequences of displaced arrays

(defun area (matrix tlx tly brx bry)
  ;; you may also want to check that all coordinates are valid
  ;; inside current matrix. You could generalize this function for
  ;; more dimensions.
  (assert (<= tlx tly))
  (assert (<= brx bry))
  (loop
     for y from tly upto bry
     collect (make-array (1+ (- brx tlx))
             :displaced-to matrix
             :displaced-index-offset
             (array-row-major-index matrix y tlx))))

(tl means top-left, br means bottom-right).

Then, assuming you define your matrix as follows:

(defparameter *matrix* #2A((1 2 3)
                           (4 5 6)
                           (7 8 9)))

... the sub-matrix is obtained as follows:

(area *matrix* 1 1 2 2)
=> (#(5 6) #(8 9))

... and accessed like this:

(aref (nth ROW *) COL)

Any changes to *matrix* is reflected in one of the two displaced arrays, and inversely. But if you coerce the resulting list as a vector, then you'll have a vector of arrays. This is different from multi-dimensional arrays, but gives you constant time access for rows:

(aref (aref area ROW) COL)

Wrapper closure

Another way to provide a restricted view of the original matrix is to create an accessor function that works only for the ranges of interest:

(defun sub-matrix (matrix tlx tly brx bry)
  ;; again, you should do more checks
  (assert (<= tlx tly))
  (assert (<= brx bry))
  (lambda (x y &optional (value nil valuep))
    (incf x tlx)
    (incf y tly)
    (assert (<= tlx x brx))
    (assert (<= tly y bry))
    (if valuep
        (setf (aref matrix y x) value)
        (aref matrix y x))))

This returns a closure which takes 2 or 3 arguments. The first two arguments are x and y coordinates relative to the inner matrix. When given a third argument, the closure sets the value. Otherwise, it gets the value.

This can be made more generic. I was partly inspired by sds's answer but tried to do things a little differently; here I can generate either a setter or a getter function. I also add some checks before creating the function and during the execution of the created function:

(defun slice-accessor (array ranges mode)
  (let* ((dimensions (array-dimensions array))
         (max-length (length dimensions)))
    (check-type array array)
    (loop
       with r = (copy-list ranges)
       for range = (pop r)
       for (lo hi) = range
       for d in dimensions
       for x from 0
       for $index = (gensym x)
       collect $index into $indices
       when range
       do (assert (<= 0 lo hi d))
       and collect `(check-type ,$index (integer 0 ,(- hi lo))) into checks
       and collect `(incf ,$index ,lo) into increments
       finally (let ((body `(apply #'aref ,array ,@$indices ())))
                 (return
                   (compile nil
                    (ecase mode
                      (:read `(lambda ,$indices
                                ,@checks
                                ,@increments
                                ,body))

                      (:write (let (($v (make-symbol "VALUE")))
                                `(lambda (,$v ,@$indices)
                                   (check-type ,$v ,(array-element-type array))
                                   ,@checks
                                   ,@increments
                                   (setf ,body ,$v)))))))))))

CLOS

Once you have the above, you can provide a nice interface through objects. The setter and getter functions are updated whenever we change the ranges or the array being sliced:

(defclass array-slice ()
  ((array :initarg :array :accessor reference-array)
   (ranges :initarg :ranges :accessor slice-ranges :initform nil)
   (%fast-getter :accessor %fast-getter)
   (%fast-setter :accessor %fast-setter)))

(flet ((update-fast-calls (o)
         (setf (%fast-setter o)
               (slice-accessor (reference-array o) (slice-ranges o) :write)

               (%fast-getter o)
               (slice-accessor (reference-array o) (slice-ranges o) :read))))

  (defmethod initialize-instance :after ((o array-slice) &rest k)
             (declare (ignore k))
             (update-fast-calls o))

  (defmethod (setf reference-array) :after (new-array (o array-slice))
             (declare (ignore new-array))
             (update-fast-calls o))

  (defmethod (setf slice-ranges) :after (new-ranges (o array-slice))
             (declare (ignore new-ranges))
             (update-fast-calls o)))  

(defgeneric slice-aref (slice &rest indices)
  (:method ((o array-slice) &rest indices)
    (apply (%fast-getter o) indices)))

(defgeneric (setf slice-aref) (new-value slice &rest indices)
  (:method (new-value (o array-slice) &rest indices)
    (apply (%fast-setter o) new-value indices)))

Examples

(defparameter *slice*
  (make-instance 'array-slice :array *matrix*))

;; no range by default
(slice-aref *slice* 0 0)
=> 1

;; update ranges
(setf (slice-ranges *slice*) '((1 2) (1 2)))

(slice-aref *slice* 0 0)
=> 5

(incf (slice-aref *slice* 0 0) 10)
=> 15

*matrix*
=> #2A((1 2 3) (4 15 6) (7 8 9))

;; change array
(setf (reference-array *slice*) (make-array '(3 3) :initial-element -1))

(slice-aref *slice* 0 0)
=> -1