Introducting Index-Mapped-Arrays

I was writing a blog post regarding my release of a library I have been using for a while now but have recently cleaned up, but it got too wordy. I will post it as well (perhaps already have), but I wanted to have a short post showing the capabilities of this library. That way people might actually be interested enough to download the library or read the other post. So without further ado, I present Index-Mapped-Arrays:

Index-Mapped-Arrays provides a generic interface, imref, to Common Lisp types.

(imref '(a b c d e f) 2)
;; C

(imref '(((a b) (c d)) ((e f) (g h))) 1 1 1)
;; H

(imref '((1 2 3) (4 5 6) (7 8 9)) 1 1)
;; 5

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

;;; As well as setting

(let ((ima '((1 2 3) (4 5 6) (7 8 9))))
  (setf (imref ima 1 1) 'set)
  ima )
;; ((1 2 3) (4 SET 6) (7 8 9))

(let ((ima #2A((1 2 3) (4 5 6) (7 8 9))))
  (setf (imref ima 1 1) 'set)
  ima )
;; #2A((1 2 3) (4 SET 6) (7 8 9))

As the name implies, you can map indices. Mapping indices allows you to do things like pull vectors out of matrices and grab sub-regions of arrays.

(defparameter *arr* '((1 2 3) (4 5 6) (7 8 9)))

;; Note, it returns a list
(row-vector *arr* 1)
;; (4 5 6)

;; We can't easily get a column vector, so we return an IMA object.
(column-vector *arr* 1)
;; #1D-IMA(2 5 8)

;; Print readably
(let ((*print-readably* t))
  (print (column-vector *arr* 1)) )
;; #(2 5 8) ; Printed as a normal array
;; #1D-IMA(2 5 8)

;; Same sort of thing with a submatrix
(submatrix *arr* 0 1 3 2)
;; #2D-IMA((2 3) (5 6) (8 9))

(row-vector (submatrix *arr* 0 1 3 2) 1)
;; #1D-IMA(5 6)

Note that IMA tries its best to give you a native data structure back, but if it can't, it gives to an instance of class index-mapped-array which emulates the proper mapping.

But that's not all. Index maps are themselves setfable places.

(setf (column-vector *arr* 0) '(a b c))
;; (A B C)

*arr*
;; ((A 2 3) (B 5 6) (C 8 9))

(defparameter *subarr* (submatrix *arr* 1 1 2 2))
;; *SUBARR*

(setf (row-vector *subarr* 0) '(d e))
;; (D E)

*subarr*
;; #2D-IMA((D E) (8 9))

*arr*
;; ((A 2 3) (B D E) (C 8 9))

And to get all of this for any data structure that can be accessed via a list of integer indices, all you have to do is specialize the methods, ima-dimensions, ima-dimension, imref, and (setf imref) (or if your data structure is immutable immod). Do this, and everything above just works, and it's portable so it should work everywhere the spec is obeyed (I test on SBCL, CMUCL, CCL, CLISP, ECL, and ABCL. All but ABCL work).

And don't think that this is only useful for blocks of data. It's a bit more flexible than that. Observe:

(defclass point () ((x-value :initarg :x-value :initform 0 :accessor x-of)
                    (y-value :initarg :y-value :initform 0 :accessor y-of)
                    (z-value :initarg :z-value :initform 0 :accessor z-of) ))

(defmethod print-object ((point point) str)
  (format str
          "#<Point: x=~A y=~A z=~A>"
          (x-of point)
          (y-of point)
          (z-of point) ))

(make-instance 'point :x-value 1 :y-value 2 :z-value 3)
;; #<Point: x=1 y=2 z=3>

;; Define the IMA interface
(defmethod ima-dimensions ((ima point))
  (list 3) )
(defmethod ima-dimension ((ima point) n)
  3 )

(defmethod imref ((point point) &rest i)
  (case (first i)
    (0 (x-of point))
    (1 (y-of point))
    (2 (z-of point))
    (otherwise (error "Index ~S out of bounds" i)) ))
(defmethod (setf imref) (new-value (point point) &rest i)
  (case (first i)
    (0 (setf (x-of point) new-value))
    (1 (setf (y-of point) new-value))
    (2 (setf (z-of point) new-value))
    (otherwise (error "Index ~S out of bounds" i)) )
  new-value )

(let ((point (make-instance 'point :x-value 1 :y-value 2 :z-value 3)))
  (iter (for i below 3)
    (collect (imref point i)) ))
;; (1 2 3)

For extra functionality, and you do want it, you can use the def-unmapper macro and specialize the make-ima-like method which will tell IMA how to change other IMAs into this kind of IMA, and how to make an another IMA like this one so we can fill it with data, respectively.

(defmethod make-ima-like ((point point) &key &allow-other-keys)
  (make-instance 'point) )

(def-unmapper point (ima)
  (when (or (< 1 (length (ima-dimensions ima)))
            (< 3 (ima-dimension ima 0)) )
    (error "Can only map a vector with 3 or fewer elements to a point") )
  (let ((point (make-instance 'point)))
    (setf (a-of point) (imref ima 0)
          (b-of point) (imref ima 1)
          (c-of point) (imref ima 2) )
    point ))

;; Or, more interestingly
(let ((point1 (make-instance 'point :x-value 1 :y-value 2 :z-value 3))
      (point2 (make-instance 'point :x-value 3 :y-value 2 :z-value 1)) )
  (list (v:dot point1 point2)
        (v:cross point1 point2)
        (v:+ point1 point2)
        (v:- point1 point2) ))
(10 #<Point: x=-4 y=8 z=-4> #<Point: x=4 y=4 z=4> #<Point: x=-2 y=0 z=2>)

This works because my vector arithmetic library uses IMA to access the elements of its arguments, and uses make-ima-like to make the structures that it returns to the caller. The unmapper is used if you need to get some mapped data into a equivalent form but without any of the index mappings.

And if you thought that was all, I just added a new feature, a map simplifier. This means that in certain simple cases, multiple levels of mappings are reduced to a single map. For instance, taking a transpose of a transpose will return the original array. This means there is less to fear when it comes to using a mapping as part of long recursion or iteration.

(let ((ima '((1 2) (3 4))))
  (iter (for i below 1000)
    (setf ima (transpose ima)) )
  ima )
;; ((1 2) (3 4)) <- the original list

(let ((ima '((1 2) (3 4))))
  (iter (for i below 1001)
    (setf ima (transpose ima)) )
  ima )
;; #2D-IMA((1 3) (2 4)) <- Only one mapping here

;; Let's really test the simplifier
(defun count-items (item-to-count ima)
  (cond ((= 0 (ima-dimension ima 0))
         0 )
        ((eql item-to-count (imref ima 0))
         (+ 1 (count-items item-to-count (subvector ima 1))) )
        (t (count-items item-to-count (subvector ima 1)) )))

;; We have to make a kind of complicated vector structure because if the vector
;; is of type list or array, there are quick, native ways of getting at the
;; subvector we need, so the simplifier isn't used at all.
(let ((ima (column-vector
            (iter (for i below 10000)
              (collect (list 1 (alexandria:random-elt '(not-it it)))) )
            1 )))
  (time (count-items 'it ima)) )
;; Evaluation took:
;;   0.192 seconds of real time
;;   0.190000 seconds of total run time (0.190000 user, 0.000000 system)
;;   98.96% CPU
;;   458,864,121 processor cycles
;;   4,484,640 bytes consed
;; 4900

;; Compare to without the simplifier
(let ((ima (column-vector
            (iter (for i below 10000)
              (collect (list 1 (alexandria:random-elt '(not-it it)))))
            1 ))
      ;; *simplify* controls whether IMA attempts to simplify or not.  Don't try
      ;; *this at home.
      (ima::*simplify* nil) )
  (time (count-items 'it ima)) )
;; Evaluation took:
;;   20.112 seconds of real time
;;   20.030000 seconds of total run time (19.720000 user, 0.310000 system)
;;   [ Run times consist of 1.030 seconds GC time, and 19.0000 seconds non-GC time. ]
;;   99.59% CPU
;;   48,151,308,831 processor cycles
;;   8 page faults
;;   1,602,561,216 bytes consed
;; 5026

Also, if you want to exploit your data structures capabilities, you can by specializing the mapping methods. But you only need bother if you want to try and eke out some extra performance for your particular case.

It's even integrated with Iterate (although more can be done here).

;; One way to "flatten" an IMA
(iter (for el in-ima '((1 2) (3 4)))
  (collect el) )
;; (1 2 3 4)

;; These are pretty self explanatory
(iter
  (for col in-column-vectors-of '((1 2 3) (4 5 6) (7 8 9)))
  (for row in-row-vectors-of '((1 2 3) (4 5 6) (7 8 9)))
  (collect (v:dot col row)) )
;; (30 81 150)

Basically, I wanted to share this with the community. I've been using it for a couple years and I really like it. Maybe others out there will as well. The code is on my github page and is released under the Lesser Lisp GPL.