Time-stamp: <2013-12-26 14:12:48 tony>

1Using this file

This README file is intended to be read by humans as well as processed by Emacs org-mode for publishing, for literate-programming of examples, for bug-tracking and task/issue management, etc.

1.1TODO[#A] Write up basic setup for using this file from org-mode

• State "TODO" from "" [2010-06-07 Mon 16:18]

leveraging ORG-MODE tools for mixing in TODO's within docs -- need to include incantation for this to do the right thing for the agenda view!

Right now there are issues with common-lisp support from within babel within org-mode. The configuration is not clear right out of the box and requires a bit of work to get working.

  ;; emacs-lisp snippet for linking in using this and the in-lined
  ;; commented TODOs of course, still must be written

1.2TODO[#B] Quick example of using this.

1.3Credits

Original Idea and majority (all?) work: Tamas K. Papp <tkpapp@gmail.com> Mucking, cleaning, simplifying, maintainance: AJ Rossini <blindglobe@gmail.com>

1.4Quick Start

1.4.1ASDF only, OBSOLETE!

  (asdf:oos 'asdf:load-op :xarray)
  (asdf:oos 'asdf:compile-op :xarray :force T)

1.4.2QUICKLISP

  (ql:quickload :xarray)

If you are a neanderthal, and want to go back to the roots, you can simply pull from github or similar:

  git clone http://github.com/blindglobe/xarray.git

2Overview

This package implements a generalized interface for array-like objects. An array-like object is any structure whose data (but not necessarily metadata) could be simply mappable to either a lisp array or a list-of-list structure.

This could be interpreted in that this forms either a rectangular or ragged-array (differential lengths of EITHER rows OR columns).

The idea is that we should be able to index an object's data, but might not be able to access specialized metadata. We provide a means of having views into convienently indexable rectangular substructures, which are view-by-reference, not copies, (TODO: need to create indexing tools for pulling various combinations out). In addition, there is a tool for taking a copy of the array into a lisp array (TODO: generalize to other array structures).

General design is that xref works out of the box on lisp arrays and list-of-list structures. Additional matrix packages could depend on xarray and extend the generics (i.e. lisp-matrix) or have patching-packages (think ASDF-SYSTEM-CONNECTIONS) register.

In a sense, we just rely on the default situation of CLOS -- it'll tell users which structures need xref-able methods, and the users will just have to tell us. But that means that XARRAY is their dependency, not that an XARRAY can look forward and load them (which might be worthwhile when using XCREATE or the conversion routines.

3API

3.1interface.lisp

(defgeneric xelttype (object) (defgeneric xdims (object) (defgeneric xdim (object dim) (defgeneric xrank (object) (defgeneric xsize (object) (defgeneric xref (object &rest subscripts) (defgeneric (setf xref) (value object &rest subscripts) (defgeneric xsetf (destination source &key map-function) (defgeneric xsimilar (rank object) (defgeneric xcreate (class dimensions &optional options) (defgeneric as* (class object copy-p options)

3.2operations.lisp

operations.lisp:29: `(defgeneric ,name (a b &key &allow-other-keys) operations.lisp:69:(defgeneric x= (a b &optional eps) operations.lisp:117: `(defgeneric ,name (a) operations.lisp:221:(defgeneric xdot (a b)

3.3view.lisp

(defgeneric permutation (object &rest permutation) (defgeneric transpose (object) (defgeneric xslice (object &rest index-specifications) (defgeneric (setf xslice) (value object &rest index-specifications) ; (defgeneric row-major-projection (object &rest dimensions) (defgeneric column-major-projection (object &rest dimensions) (defgeneric flat (object) (defgeneric ancestor-subscripts (object index)

3.4Core

3.4.1XREF

Access individual elements in an array.

  (xref object
        #| 1 2 3 or similar indexing sequence |# )
  (setf (xref object
              #| 1 2 3 or similar indexing sequence |# )
        value)

to retrieve or set an element. This would be easy to do with aref if aref was a generic function, but for various (sensible) reasons, it is not. I (here, this is Tamas) describe a simple interface with a few generic functions. Any objects that has these methods is called "xrefable". For a given datastructure, we must implement the following tools.

queries (sub)structure and returns views which can be accessed and set. The reference <ref> manages the indicies in the resulting view.

  (xref object <ref>)

3.4.2XDIMS

queries dimensions of structure. There is an open question[fn:1]whether an XDIM function should exist.

  (xdims object)  ;; returns list of all indicies
  (xdim object <dimindex eg 0, ..., n-1>)
  (nth 0 (xdims object))
  (nth 1 (xdims object))

3.4.3XELTTYPE

   (xelttype object &optional <ref>)

queries element and substructure types. If <ref> is given, it returns the substructure, if <ref> is nil, it returns the whole structure.

3.4.4XCOPY

   (xcopy object <ref>)

queries (sub)structure and returns copies. If one gets confused between a view and copy, dire consequences could entail, so we use separate generic functions for reference and copy, rather than a single "xaccess", which could result in:

   (defmacro xref  (&rest args) (xaccess :type 'reference @args))
   (defmacro xcopy (&rest args) (xaccess :type 'copy      @args))

3.4.5XNEW

creates a new structure. One could consider using a undefined object in order to implement this with setf, i.e.

   (setf (xref undef-object <refs>) object-with-right-structure)

and having it return undef-object with the right value. But thereare a few other possibilities.

3.5Extended

3.5.1XRANK

3.5.2XSIMILAR

3.5.3XSIZE

Return the number of elements in the array (product of dimensions,so a zero-dimensional array has size 1). Should be the analog ofARRAY-TOTAL-SIZE

3.5.4XCREATE

Creates a new xref-able object with a particular backing store(ARRAY, or LISTOFLIST, or MATRIX-LIKE, or DATAFRAME-LIKE).

3.5.5AS*

libraries specialize, so write for data store.

Users should leverage AS or COPY-AS

3.5.6AS

user function for as*

3.5.7COPY-AS

user function for as* which makes a deep copy

3.5.8TAKE

3.6Utility

these are currently related to arrays.

3.6.1CVECTOR

returns a simple array of the specified element type, which isvector-ish, filled by contents.

3.6.2CARRAY

returns a simple array of the specified element type, which isarray-ish (dimensioned), filled by contents.

3.6.3CVECTOR*

Same as cvector, but element-type is derived using NUMERIC-TYPE-CLASSIFIER.

3.6.4CARRAY*

Same as carray, but element-type is derived using NUMERIC-TYPE-CLASSIFIER.

4Approach in general

Both copies and views on an array should be XREF-able.

Array and vector construction for LISP ARRAYS (the default and base storage class) are shown as follows:

  (defparameter *b* (xarray:cvector* (list 0.0 1.0 2.0 3.0 4.0 5.0 6.0 7.0)))
  ,*b* ;; this is an array of 1 item, a list of 8 floats
  
  (defparameter *c* (xarray:cvector* 0.0 1.0 2.0 3.0 4.0 5.0 6.0 7.0))
  ,*c* ;; this is an array of 8 items, each a float
  
  (defparameter *a* (xarray:carray* (list 2 4)
                                    0.0 1.0 2.0 3.0 4.0 5.0 6.0 7.0))
  ,*a*
  
  
  
  (defparameter *d* (xarray:cvector 'double-float 0.0 1.0 2.0 3.0 4.0 5.0 6.0 7.0))
  ,*d* ;; this is an array of 1 item, a list of 8 floats
  
  (defparameter *e* (xarray:cvector 'fixnum 0 1 2 3 4 5 6 7))
  ,*e* ;; this is an array of 8 items, each a float
  
  (defparameter *f* (xarray:carray 'fixnum (list 2 4)
                                    0 1 2 3 4 5 6 7))
  ,*f*
  
  (defparameter *g* (xarray:carray 'double-float (list 2 4)
                                    0.0 1.0 2.0 3.0 4.0 5.0 6.0 7.0))
  *g*

This can be sliced and dices in a number of ways,

  (xarray:xslice *a* :all 2)  ; third column
  (xarray:xslice *a* 0 :all) ; first row

selects the 3th column of an array.[fn:2] , and then the first row. This view is also xrefable, so you can use

  (setf (xarray:xref (xarray:xslice *a* :all 2) 1) 9.0)

to set element 2 in the 3rd column, which has value 6, to the value 9. Changes will be made in the original array

  *a*

since this is a view. But for functions that just expect an array, they can use the interface (xref, xdims, etc) and not care where it is coming from.

I have also implemented permutations (generalized transpose), and row-major projections. If you want to collect the elements of a view in an array ("deep copy"), use

  (copy-as *a*)
  (copy-as (xarray:xslice *a* :all 2))

which delivers a CL array of the original and then sliced xrefable object.

There are convenience functions that for easy array/vector creation, inspired by R:

  (carray* '(2 3) 1 2 3 4d0 5 6)
  ;; => #2A((1.0d0 2.0d0 3.0d0) (4.0d0 5.0d0 6.0d0))

guess the type so that all of the elements would fit in. See also cvector and carray (manually specified type) and cvector*.

5Roadmap, tasks, bugs.

5.1TODO[#B] unit testing [0/5]

• State "TODO" from "" [2010-06-07 Mon 15:33]

5.1.1TODO[#B] XDIMS unittests

• State "TODO" from "" [2010-06-07 Mon 15:29]

5.1.2TODO[#B] XTYPE unittests

• State "TODO" from "" [2010-06-07 Mon 15:29]

5.1.3TODO[#B] XREF unittests

• State "TODO" from "" [2010-06-07 Mon 15:29]

5.1.4TODO[#B] XCOPY unittests

• State "TODO" from "" [2010-06-07 Mon 15:29]

5.1.5TODO[#B] XNEW unittests

• State "TODO" from "" [2010-06-07 Mon 15:29]

5.2TODO[#A] integrate linear algebra routines

• State "TODO" from "" [2010-06-07 Mon 15:33]

probably from GSLL? It shouldbe easy to rig an xrefable interface to GSLL arrays.

5.3TODO[#B] Specialized arrays [0/2]

• State "TODO" from "" [2010-06-07 Mon 15:33]

upper- and lower-triangular matrices, etc. xrefable elements canbe read-only, xref-writeable-p is an interface to test if anelement is writeable, it was included specifically for this.In addition, integrate sparse matrices from cl-sparsematrix.

5.3.1TODO[#B] Triangular matrices

• State "TODO" from "" [2010-06-07 Mon 15:33]

5.3.2TODO[#B] Sparse matrices

• State "TODO" from "" [2010-06-07 Mon 15:33]

5.4TODO[#B] specialized subclasses for certain cases and operations

• State "TODO" from "" [2010-06-07 Mon 15:34]

eg views on matrices, a transpose-view would be much simpler (andfaster, maybe?) than the generalized permute. Some operations (such asouter products, multiplication, addition) could be highly optimizedwhen we know more about the specific structure (e.g. triangular,only ones/zeros, etc...).

5.5TODO[#B] decent printing for xrefable objects,

• State "TODO" from "" [2010-06-07 Mon 15:34]

currently converted to array.

5.6TODO[#B] direct access from other systems

• State "TODO" from "" [2010-06-07 Mon 15:34]

certain views can be directly accommodated by LAPACK/GSLL (eg amatrix with a stride). Minor possibility for speedup/memorysavings. This is related to optimization based on substructure.

5.7TODO[#B] fix SLICE api between LISP-MATRIX and XARRAY

• State "TODO" from "" [2010-06-07 Mon 15:38]

5.8TODO[#B] implement equalp for XREF-able objects

• State "TODO" from "" [2010-06-07 Mon 15:40]

6Development in progress

To use this from within org-mode/org-babel, C-c ' will put intoslime / lisp editing mode

  (in-package :cl-user)
  (asdf:oos 'asdf:compile-op 'xarray :force t)
  (asdf:oos 'asdf:load-op 'xarray)
  (asdf:oos 'asdf:load-op 'xarray-test)

Tamas was thinking about this being a general interface, but then inmy (Tony's) opinion, included some specialized issues that needed tobe considered here but handled elsewhere. My limited understandinghad to do with practical considerations; I don't need to bepractical, and he does. THIS is precisely where I am deviating inmy further development of this.

What I (Tony) am currently thinking about is to pay a penalty initially (and maybe for a while!) on speed of access and write a general interface using a range of possible back-ends. So that we can get the interface clean: xref pulls out a value and puts it int an array of the same structure, xref* pulls out a value and sticks it into a lisp array or scalar and returns it. Speed can be handled later by doing a compile-time/run-time tradeoff, we will pay the compile-time penalty, in exchange for run-time advantages. This fits into the theme of rapid prototyping (slow exec) followed by rapid execution (post-proto...).

We'll optimize for version 2. Ha-ha.

Current thinking on the above, is to stick them into separate packages. In particular, I've factored out the listoflist infrastructure into its own package.

Checking current test state; but this is currently broken!

  (in-package :xarray-ut)
  (run-tests :suite 'xarray-ut)
  ;; => #<Results for XARRAY-UT 13 Tests, 0 Errors, 0 Failures>
  (describe (run-tests :suite 'xarray-ut))

6.1Development work and examples

Here are any current trials that are undergoing development.

(in-package :xarray-user)
;; and dev code goes here.

7Discussion

8Footnotes

[fn:1] this is aesthetic. Why write a simple list extract tool when it could suffice to use existing list extraction functions? This also leads to better programmer knowledge, as well as a single point of optimization for the overall system (the internal system list manipulation functions)

[fn:2] The slice interface is similar to Tamas' affi package, but now arbitrary index vectors are allowed, much like R.