Common Lisp Package: SPARTNS

README:

FUNCTION

Private

CHAINED-DELETE (&KEY DATA REP-LIST INDEX-LIST ELEMENT-TYPE SPARSE-ELEMENT BLOCK-NAME TEST-EQUAL EMPTY-DIM-MAP)

This function will return the code necessary to delete one element from a sparse tensor, given the chained representation scheme. - data will be inserted as is in the code. It is the container where the tensor is stored. - rep-list MUST be a list of the representation schemes, and it CANNOT be a variable, because it will be used in macroexpansion time. - index-list is inserted as is, and will be later replaced by the list of indices. - element-type is inserted as is. It is the type of the stored elements. - sparse-element is inserted as is. It is the value of the sparse element. - block-name is just a name for the block of code. A wrapper function will use gensym for this.

CHAINED-GET (&KEY DATA REP-LIST INDEX-LIST ELEMENT-TYPE SPARSE-ELEMENT BLOCK-NAME TEST-EQUAL EMPTY-DIM-MAP)

This function will return the code necessary to access one element in a sparse tensor, given the chained representation scheme. - data will be inserted as is in the code. It is the container where the tensor is stored. - rep-list MUST be a list of the representation schemes, and it CANNOT be a variable, because it will be used in macroexpansion time. - index-list is inserted as is, and will be later replaced by the list of indices. - element-type is inserted as is. It is the type of the stored elements. - sparse-element is inserted as is. It is the value of the sparse element. - block-name is just a name for the block of code. A wrapper function will use gensym for this. This function should be used by a macro that creates the real function for accessing the tensor.

CHAINED-MAKE (&KEY REP-LIST NON-ZERO-LIST ELEMENT-TYPE SPARSE-ELEMENT EMPTY-DIM-MAP)

This function will return the code necessary to create the representation of one of the dimensions of the sparse tensor.

CHAINED-SET (&KEY DATA REP-LIST INDEX-LIST NEW-VALUE NON-ZERO-LIST ELEMENT-TYPE SPARSE-ELEMENT BLOCK-NAME TEST-EQUAL EMPTY-DIM-MAP RESIZE-FUNCTION)

This function will return the code necessary to store one element in a sparse tensor, given the chained representation scheme. - data will be inserted as is in the code. It is the container where the tensor is stored. - rep-list MUST be a list of the representation schemes, and it CANNOT be a variable, because it will be used in macroexpansion time. - index-list is inserted as is, and will be later replaced by the list of indices. - new-value will be inserted as is. It is the value to be stored in the tensor. - element-type is inserted as is. It is the type of the stored elements. - sparse-element is inserted as is. It is the value of the sparse element. - block-name is just a name for the block of code. A wrapper function will use gensym for this.

CHECK-DEFSPARTN-PARAMETERS (NAME REPRESENTATION NON-ZERO ELEMENT-TYPE SPARSE-ELEMENT TEST-EQUAL RESIZE-FUNCTION RESIZE-AMOUNT DEF DECLARE)

This function checks the types of some parameters to defspartn.

COLLECT-NON-ZEROS-INTO-FAST-TRAVERSAL (SYMBOL-LIST ARRAY-LIST TYPES-LIST POSITION)

Produces the code to SETF values in a fast traversal: (collect-non-zeros-into-fast-traversal '(i j k v w) '(II JJ KK VV WW) '(fixnum fixnum fixnum double-float double-float) 10) ==> ((SETF (AREF (THE (SIMPLE-ARRAY FIXNUM (*)) II) 10) I) (SETF (AREF (THE (SIMPLE-ARRAY FIXNUM (*)) JJ) 10) J) (SETF (AREF (THE (SIMPLE-ARRAY FIXNUM (*)) KK) 10) K) (SETF (AREF (THE (SIMPLE-ARRAY DOUBLE-FLOAT (*)) VV) 10) V) (SETF (AREF (THE (SIMPLE-ARRAY DOUBLE-FLOAT (*)) WW) 10) W))

COPY-ARRAY-STRUCTURE (SEQUENCE)

Return a copy of SEQUENCE which is EQUAL to SEQUENCE but not EQ.

COPY-CVECTOR (SEQUENCE)

Return a copy of SEQUENCE which is EQUAL to SEQUENCE but not EQ.

CREATE-AND-BIND-ARRAYS (NON-ZEROS SYMBOL-LIST TYPE-LIST)

Generates the code to create and bind arrays, and also the type declarations. For example: (multiple-value-bind (n b d) (create-and-bind-arrays 4 '(x y z w) '(fixnum character double-float fixnum)) (format t "=======n:~%~a~%=======b:~%~a~%=======d:~%~a~%" n b d)) The output is: (ARRAY-X-2960 ARRAY-Y-2961 ARRAY-Z-2962 ARRAY-W-2963) =======b: ((ARRAY-X-2960 (MAKE-ARRAY 4 ELEMENT-TYPE FIXNUM)) (ARRAY-Y-2961 (MAKE-ARRAY 4 ELEMENT-TYPE CHARACTER)) (ARRAY-Z-2962 (MAKE-ARRAY 4 ELEMENT-TYPE DOUBLE-FLOAT)) (ARRAY-W-2963 (MAKE-ARRAY 4 ELEMENT-TYPE FIXNUM))) =======d: ((TYPE (SIMPLE-ARRAY FIXNUM (*)) ARRAY-X-2960) (TYPE (SIMPLE-ARRAY CHARACTER (*)) ARRAY-Y-2961) (TYPE (SIMPLE-ARRAY DOUBLE-FLOAT (*)) ARRAY-Z-2962) (TYPE (SIMPLE-ARRAY FIXNUM (*)) ARRAY-W-2963))

CREATE-NEXT-DIM (VALUE DATA REP-LIST INDEX-LIST NON-ZERO-LIST ELEMENT-TYPE SPARSE-ELEMENT RESIZE-FUNCTION)

This function is used by chained-set to create a new structure when necessary.

DEF-SPARTN-COPY (FUN-NAME SCHEME-NAME &KEY (DECLARE (QUOTE (OPTIMIZE (SPEED 3) (SAFETY 1)))) (DEF NIL))

Creates a fuction that copies a spartn. Examples: (def-spartn-copy 'my-copy-function 'hash) ==> (MY-COPY-FUNCTION (#:DATA-817) "Copies a sparse tensor of type HASH" (DECLARE (OPTIMIZE (SPEED 3) (SAFETY 1))) (SPARTN-CONVERT #:DATA-817 :FROM HASH :TO HASH :DESTRUCTIVE NIL)) (def-spartn-copy 'my-copy-function 'hash :def t) ==> (DEFUN MY-COPY-FUNCTION (#:DATA-820) "Copies a sparse tensor of type HASH" (DECLARE (OPTIMIZE (SPEED 3) (SAFETY 1))) (SPARTN-CONVERT #:DATA-820 :FROM HASH :TO HASH :DESTRUCTIVE NIL))

DEF-SPARTN-DELETE (FUN-NAME REP-LIST TYPE SPARSE-ELEMENT TEST-EQUAL EMPTY-DIM-MAP &KEY (DECLARE (QUOTE (OPTIMIZE (SPEED 3) (SAFETY 1)))) (DEF NIL))

Creates a function to delete elements from a tensor.

DEF-SPARTN-GET (FUN-NAME REP-LIST TYPE SPARSE-ELEMENT TEST-EQUAL EMPTY-DIM-MAP &KEY (DECLARE (QUOTE (OPTIMIZE (SPEED 3) (SAFETY 1)))) (DEF NIL))

Creates a function to get elements in a tensor.

DEF-SPARTN-MAKE (FUN-NAME REP-LIST TYPE SPARSE NON-ZERO-LIST EMPTY-DIM-MAP &KEY (DECLARE (QUOTE (OPTIMIZE (SPEED 3) (SAFETY 1)))) (DEF NIL))

Creates a function to initialize a tensor.

DEF-SPARTN-PACK (FUN-NAME REP-LIST TYPE &KEY (DEF NIL))

Creates a function that packs a sparse tensor.

DEF-SPARTN-SET (FUN-NAME REP-LIST TYPE SPARSE-ELEMENT NON-ZERO-LIST TEST-EQUAL EMPTY-DIM-MAP RESIZE-FUNCTION &KEY (DECLARE (QUOTE (OPTIMIZE (SPEED 3) (SAFETY 1)))) (DEF NIL))

Creates a function to set elements in a tensor.

DEF-SPARTN-TRAVERSE (MAC-NAME REP-LIST TYPE SPARSE TEST-EQUAL &KEY (DEF NIL))

Creates a macro for traversing one type of spartn, given the representation scheme (as a list), the element type, the sparse element and the desired name for the new macro. For example: (def-spartn-traverse do-hhd (hash hash) double-float 0d0 #'=) This will create a macro DO-HHD which can be used like this: (do-hhd ((i j) val data) (format t "The value at (~a, ~a) is ~a" i j val))

DEFINE-SPARTN-FUNCTIONS (NAME SPARTN-SCHEME EMPTY-DIM-MAP EMPTY-DIM-DEFS &KEY (DEF NIL) (DECLARE NIL))

Returns the code for the functions used with a spartn scheme. This is used by defspartn and w/spartns. If DEF is T, then this function will generate top-level code to define the functions: (DEFUN get-X (tensor index) ...) If DEF is NIL, then only the names, lambda-lists and bodies are generated: (get-X (tensor index) ...) The first form is used by defspartn (which is supposed to be used as a top-leval form), and the second is used by w/spartns (which will use LABELS to create local functions).

DEFINE-SPARTN-MACROS (NAME SPARTN-SCHEME EMPTY-DIM-MAP &KEY (DEF NIL))

Returns the code for the macros used with a spartn scheme. This is used by defspartn and w/spartns. If DEF is T, then this function will generate top-level code to define the functions and macros: (DEFMACRO traverse-X (index-list value tensor &body body) ...) If DEF is NIL, then only the names, lambda-lists and bodies are generated: (traverse-X (index-list value tensor &body body) ...) The first form is used by defspartn (which is supposed to be used as a top-leval form), and the second is used by w/spartns (which will use MACROLET to create local macros).

DO-FAST-TRAVERSAL (SYMBOL-LIST ARRAY-LIST TYPES-LIST BODY)

Traverses a structure of the type spartn-fast-traversal, binding the symbols for indices and values. Example: (do-fast-traversal '(i j k) ; indices '(v1 v2 v3) ; arrays '(fixnum double-float double-float) ; types '((format t "i=~a j=~a k=~a~%" i j k)))) ; body ==> (SYMBOL-MACROLET ((I (AREF (THE (SIMPLE-ARRAY FIXNUM (*)) V1) #:INDEX-2309)) (J (AREF (THE (SIMPLE-ARRAY DOUBLE-FLOAT (*)) V2) #:INDEX-2309)) (K (AREF (THE (SIMPLE-ARRAY DOUBLE-FLOAT (*)) V3) #:INDEX-2309))) (LOOP FOR #:INDEX-2309 BELOW 4 DO (FORMAT T "i=~a j=~a k=~a~%" I J K))) The symbol used for the index variable (#:INDEX-2309 in this example) is created by gensym. *NOTE* that we used '(( body )) when calling do-fast-traversal, and ,@body inside it.

EXPAND-SCHEME (FUNCTION SCHEME SUBST-LIST)

Expands the code from a representation scheme, substituting parameters. For example, if a scheme with the name 'cvector has this function registered: 'spartns::get --> '(get-cvec data index sparse-element) Then expand-scheme will work like this: (expand-scheme 'spartns::get 'cvector '((data d) (index i) (sparse-element sp))) => '(get-cvec d i sp)

FLATTEN (LIST)

Flattens a list.

GET-CREATE (REP)

Returns the Lisp code to create an empty dimension, given its representation. Examples: (get-create 'hash) ==> (MAKE-HASH-TABLE :SIZE 0) (get-create 'cvector) ==> (MAKE-NEW-CVECTOR (THE FIXNUM 0) :ELEMENT-TYPE FIXNUM :SPARSE-ELEMENT 0)

GET-SCHEME (NAME)

Retrieves a representation scheme given its name, which should be a symbol. If the scheme is not registered, this function returns NIL. (spartns::get-scheme 'spartns:cvector) ==> #<HASH-TABLE :TEST EQ :COUNT 10 {10036CF001}> T The hashtable returned is the representation scheme (see the function DEFSCHEME).

MAKE-EMPTY-DIMENSIONS (REP-LIST)

Given arepresentation list, this function returns two values: the Lisp code for creating empty dimensions for those representations, and a hashtable that maps symbols like EMPTY-REP- to those empty structures. For example, (make-empty-dimensions '(cvector hash array) ==> (LET ((#:EMPTY-ARRAY-847 (MAKE-ARRAY-STRUCTURE :VALUES (MAKE-ARRAY 0 :ELEMENT-TYPE 'FIXNUM :INITIAL-ELEMENT (THE FIXNUM 0)) :ACTIVE (MAKE-ARRAY 0 :ELEMENT-TYPE '(MOD 2) :INITIAL-ELEMENT 0) :MAX-CAPACITY 0)) (#:EMPTY-HASH-846 (MAKE-HASH-TABLE :SIZE 0)))), #<HASHTABLE :TEST EQL :COUNT 2 {129910020}) The second value returned (the hashtable) maps: hash --> #:EMPTY-HASH-846 array --> #:EMPTY-ARRAY-847 The cvector scheme was not included because it is the first in the representation list.

MAKE-TYPES-LIST (TYPE-LIST INDEX-SYMBOL-LIST)

Make s alist of types: (make-types-list '(hash-float cvector-double) '(i j k l)) ==> '(single-float double-float fixnum fixnum fixnum fixnum) type-list is a list of spartn schemes.

REMOVE-SCHEME (NAME)

Removes a representation scheme from the database.

SPARSE-ELEMENT-FOR-NEXT-DIM (REP-LIST EMPTY-DIM-MAP SPARSE-ELEMENT)

Returns the sparse element to be used in the next dimension: either the sparse-element for the tensor (if this is the last dimension) or an empty map using next dimension's representation.

SPARTN-SCHEME-DECLARE (INSTANCE)

@arg[extid]{A @class{extid}} @return[sytemid]{puri:uri or nil} Returns the System ID part of this External ID.

SPARTN-SCHEME-ELEMENT-TYPE (INSTANCE)

@arg[extid]{A @class{extid}} @return[sytemid]{puri:uri or nil} Returns the System ID part of this External ID.

SPARTN-SCHEME-NON-ZERO (INSTANCE)

@arg[extid]{A @class{extid}} @return[sytemid]{puri:uri or nil} Returns the System ID part of this External ID.

SPARTN-SCHEME-REPRESENTATION (INSTANCE)

@arg[extid]{A @class{extid}} @return[sytemid]{puri:uri or nil} Returns the System ID part of this External ID.

SPARTN-SCHEME-RESIZE-FUNCTION (INSTANCE)

@arg[extid]{A @class{extid}} @return[sytemid]{puri:uri or nil} Returns the System ID part of this External ID.

SPARTN-SCHEME-SPARSE-ELEMENT (INSTANCE)

@arg[extid]{A @class{extid}} @return[sytemid]{puri:uri or nil} Returns the System ID part of this External ID.

SPARTN-SCHEME-TEST-EQUAL (INSTANCE)

@arg[extid]{A @class{extid}} @return[sytemid]{puri:uri or nil} Returns the System ID part of this External ID.

SPLIT-INDICES-VALUES-DONT-BIND (TRAV)

Returns index-list values dont-bind

SPLIT-TRAVERSAL-DESCRIPTIONS (TRAVERSAL-LIST)

Splits the descriptions of several traversals into several lists: one for spartn type, one for the data containers, one for the variable to bind for value and one for the lists of variables to bind for indices. For example, (split-traversal-descriptions '((A data-a i j k l val-a) (B data-b x y z val-b :dont-bind (x)) (C data-c a b c val-c))) ==> (values (A B C) (DATA-A DATA-B DATA-C) (VAL-A VAL-B VAL-C) ((I J K L) (X Y Z) (A B C)) (NIL (x) NIL)) This is used by the macro w/spartns.

TRAVERSE-SPARTN-AUX (INDEX-LIST VALUE DATA ELEMENT-TYPE SPARSE-ELEMENT REP-LIST TEST-EQUAL DONT-BIND EMPTY-DIM-MAP BODY)

This is an auxiliary function that is used by the spartn-generic-traverse macro. It will produce the code to traverse a sparse tensor, given the representation scheme. dont-bind is a list of indices not to bind.

WITH-SPARTN-TRAVERSALS-AUX (SPARTN-TYPE-LIST DATA-LIST INDEX-LIST-LIST VALUE-LIST DONT-BINDS USED-INDEX-LIST BODY)

Generates the code to traverse several spartns, possibly with shared indices. This function does the heavy work, while w/spartn-traversals is the macro that exposes the functionality. (with-spartn-traversals-aux '(number2d fixnum2d) '(A B) '((I J) (x y)) '(va vb) '(pprint)) ==> (TRAVERSE-NUMBER2D ((I J) VA A) (TRAVERSE-FIXNUM2D ((X Y) VB B) (PROGN PPRINT)) Now an example with an excluded index: (with-spartn-traversals-aux '(number-2d fixnum-2d) '(A B) '((I J) (x y)) '(va vb) '(x) ;; <======= HERE! '(progn (pprint x) (pprint y) (pprint va))) ==> (TRAVERSE-NUMBER-2D ((I J) VA A) (TRAVERSE-FIXNUM-2D ((#:B-X-803 Y) VB B) (WHEN (AND (EQL X #:B-X-803)) (PROGN PROGN (PPRINT X) (PPRINT Y) (PPRINT VA))))) Note that the X index was excluded from the variables over which we loop. The code will loop over #:B-X-803 (locally created), but the body will only be evaluated if it is equal to X, which should be set outside the loop. This is equivalent to using a fixed value for one index.

Undocumented

ARRAY-STRUCTURE-ACTIVE (STRUCTURE)

SETFARRAY-STRUCTURE-ACTIVE (NEW-VALUE STRUCTURE)

ARRAY-STRUCTURE-COUNT (STRUCTURE)

SETFARRAY-STRUCTURE-COUNT (NEW-VALUE STRUCTURE)

ARRAY-STRUCTURE-MAX-CAPACITY (STRUCTURE)

SETFARRAY-STRUCTURE-MAX-CAPACITY (NEW-VALUE STRUCTURE)

ARRAY-STRUCTURE-VALUES (STRUCTURE)

SETFARRAY-STRUCTURE-VALUES (NEW-VALUE STRUCTURE)

CHAINED-PACK (&KEY DATA REP-LIST ELEMENT-TYPE)

COPY-SPARTN-SCHEME (INSTANCE)

CVECTOR-COUNT (STRUCTURE)

SETFCVECTOR-COUNT (NEW-VALUE STRUCTURE)

CVECTOR-INDEX (STRUCTURE)

SETFCVECTOR-INDEX (NEW-VALUE STRUCTURE)

CVECTOR-MAX-CAPACITY (STRUCTURE)

SETFCVECTOR-MAX-CAPACITY (NEW-VALUE STRUCTURE)

CVECTOR-VALUES (STRUCTURE)

SETFCVECTOR-VALUES (NEW-VALUE STRUCTURE)

MAKE-ARRAY-STRUCTURE (&KEY ((VALUES DUM114) (MAKE-ARRAY 0)) ((ACTIVE DUM115) (MAKE-ARRAY 0 ELEMENT-TYPE '(MOD 2))) ((MAX-CAPACITY DUM116) 0) ((COUNT DUM117) 0))

MAKE-CVECTOR (&KEY ((VALUES DUM314) (MAKE-ARRAY 0)) ((INDEX DUM315) (MAKE-ARRAY 0 ELEMENT-TYPE 'FIXNUM)) ((MAX-CAPACITY DUM316) 0) ((COUNT DUM317) 0))

MAKE-SPARTN-SCHEME (&KEY ((REPRESENTATION DUM1834) NIL) ((NON-ZERO DUM1835) NIL) ((ELEMENT-TYPE DUM1836) NIL) ((SPARSE-ELEMENT DUM1837) NIL) ((DECLARE DUM1838) NIL) ((TEST-EQUAL DUM1839) NIL) ((RESIZE-FUNCTION DUM1840) NIL))

SETFSPARTN-SCHEME-DECLARE (NEW-VALUE INSTANCE)

SETFSPARTN-SCHEME-ELEMENT-TYPE (NEW-VALUE INSTANCE)

SETFSPARTN-SCHEME-NON-ZERO (NEW-VALUE INSTANCE)

SPARTN-SCHEME-P (OBJECT)

SETFSPARTN-SCHEME-REPRESENTATION (NEW-VALUE INSTANCE)

SETFSPARTN-SCHEME-RESIZE-FUNCTION (NEW-VALUE INSTANCE)

SETFSPARTN-SCHEME-SPARSE-ELEMENT (NEW-VALUE INSTANCE)

SETFSPARTN-SCHEME-TEST-EQUAL (NEW-VALUE INSTANCE)

MACRO

Public

DEFSCHEME (&KEY NAME TYPE MAKE GET SET DELETE TRAVERSE PACK CAPACITY COUNT)

Adds a new representation scheme. - name is the name of the scheme (a symbol) - type is the Common Lisp type of an instance of this scheme. For example, if your scheme represents the mapping as a hashtable, then type is HASH-TABLE. If it is represented as a Lisp list, then it is LIST All other parameters (make, get, set, delete, traverse, capacity, count) should contain the Lisp code necessary to perform these actions: - make: the code necessary to create an instance of this scheme. If your code contains the symbols SIZE and ELEMENT-TYPE, they will be substituted for the actual values; - get: code necessary to access one element. Symbols that are substituted: DATA, INDEX, SPARSE-ELEMENT. It should return TWO VALUES: + the retrieved element (the sparse element, if the index was not found); + either T or NIL, depending on wether the element was found or not. For example, (IF found (VALUES element T) (VALUES sparse NIL)); - set: code to set one position. Substituted symbols: DATA, INDEX, VALUE, ELEMENT-TYPE - delete: code to remove one element. Substituted symbols: DATA, INDEX, SPARSE-ELEMENT, ELEMENT-TYPE; - traverse: code to traverse the structure, binding variables to the index and value while executing a body of code. Substituted symbols: INDEX, VALUE, DATA, ELEMENT-TYPE, BODY; - pack: code that packs the container, releasing non-used memory; - capacity: code that returns the maximum number of elements that the instance can handle. Substituted symbols: DATA; - count: code to return the actual number of non-zero elements. Substituted symbols: DATA. The macro will return the name of the newly created scheme. For example: (defscheme :name hash :type HASH-TABLE :make (let () (declare (ignore element-type)) (make-hash-table :size size)) :get (gethash index data sparse-element) :set (setf (gethash index data) value) :delete (remhash index data) :traverse (do-traverse-hash (index value data) body) :pack (values) ; we don't write code for shrinking a hashtable! :capacity (let () (declare (ignore data)) most-positive-fixnum) :count (hash-table-count data)) In the example, the make function ignores ELEMENT-TYPE (because hashtables ignore them). However, you should NOT try to make the code ignore symbols by using, for example, (let () (declare (ignore element-type)) (make-hash-table :size size)) because the element-type inside DECLARE will be substituted. Since the make function returns an object of type HASH-TABLE, then this is the value passed to the type parameter. The capacity code always returns most-positive-fixnum, since hashtables can grow.

DEFSPARTN (NAME &KEY REPRESENTATION NON-ZERO ELEMENT-TYPE SPARSE-ELEMENT (TEST-EQUAL 'EQL) (RESIZE-FUNCTION '(LAMBDA (X) (DECLARE (IGNORE X)) 200)) (RESIZE-AMOUNT -1) (DEF T) (DECLARE NIL))

Defines a new spartn scheme. If the DEF parameter is not NIL, then functions and macros will be created to access the spartn scheme. If the name of the new scheme is X, then the following functions will be defined: - (MAKE-X) - (GET-X tensor index) - (SET-X tensor index value) - (DELETE-X tensor index) - (PACK-X tensor) - (COPY-X tensor) The macro (TRAVERSE-X index-list value tensor body) will also be defined. NON-ZERO is just a hint so that containers in each dimension will be created with approximately this size. It is not a hard limit, and there is no guarantee that this will actually be the size of the containers. RESIZE-FUNCTION is a function that tells the amount by which container sizes is increased. The default value is (lambda (x) 200). This may or may not be used, depending on the representation scheme. The default value of DEF is T. You can set it to NIL if you want to use w/spartns (which will create the same macros and functions locally anyway). The parameter DECLARE is used to include declarations inside the defined functions. By default it is (optimize (speed 3) (safety 1)).

SPARTN-CONVERT (OLD-DATA &KEY FROM TO (DESTRUCTIVE NIL))

Returns a new spartn using a different representation but with the same contents as the one given. from and to must be the names of the representation schemes (symbols, not strings). Example: (defspartn hashhash :representation '(hash hash) ...) (defspartn :representation '(hash cvector) ...) (let ((mat (make-hashash))) (let ((mat2 (spartn-convert mat :from hashash :to hashcvec))) (get-hashvec mat2 '(2 3)))) Here MAT uses spartn scheme HASHHASH, which represents the tensor as a hashtable of hashtables. MAT2 is obtained by converting MAT to scheme HASHCVEC, which represents the tensor as a hashtable of compressed vectors.

W/FAST-TRAVERSALS (TRAVERSAL-LIST &BODY BODY)

Builds a structure of the type SPARTN-FAST-TRAVERSAL and calls do-fast-traversal to actually run through it. (spartns:w/fast-traversals ((2d-matrix m1 i j val-1) (2d-matrix m2 x y val-2)) (set-2d-matrix prod (+ (* i 5) x) (+ (* j 5) y) (* val-1 val-2))) ==> (LET ((#:POSITION-830 0) (#:ARRAY-VAL-1-831 (MAKE-ARRAY 1000 :ELEMENT-TYPE 'NUMBER)) (#:ARRAY-VAL-2-832 (MAKE-ARRAY 1000 :ELEMENT-TYPE 'NUMBER)) (#:ARRAY-I-833 (MAKE-ARRAY 1000 :ELEMENT-TYPE 'FIXNUM)) (#:ARRAY-J-834 (MAKE-ARRAY 1000 :ELEMENT-TYPE 'FIXNUM)) (#:ARRAY-X-835 (MAKE-ARRAY 1000 :ELEMENT-TYPE 'FIXNUM)) (#:ARRAY-Y-836 (MAKE-ARRAY 1000 :ELEMENT-TYPE 'FIXNUM))) (DECLARE (TYPE FIXNUM #:POSITION-830) (TYPE (SIMPLE-ARRAY NUMBER (*)) #:ARRAY-VAL-1-831) (TYPE (SIMPLE-ARRAY NUMBER (*)) #:ARRAY-VAL-2-832) (TYPE (SIMPLE-ARRAY FIXNUM (*)) #:ARRAY-I-833) (TYPE (SIMPLE-ARRAY FIXNUM (*)) #:ARRAY-J-834) (TYPE (SIMPLE-ARRAY FIXNUM (*)) #:ARRAY-X-835) (TYPE (SIMPLE-ARRAY FIXNUM (*)) #:ARRAY-Y-836)) ;; w/spartn-traversals will go make the traversal we'd like to do ;; repeatedly; we'll store the indices AND values: (SPARTNS:W/SPARTN-TRAVERSALS ((2D-MATRIX M1 I J VAL-1) (2D-MATRIX M2 X Y VAL-2)) (SETF (AREF (THE (SIMPLE-ARRAY NUMBER (*)) #:ARRAY-VAL-1-831) #:POSITION-830) VAL-1) (SETF (AREF (THE (SIMPLE-ARRAY NUMBER (*)) #:ARRAY-VAL-2-832) #:POSITION-830) VAL-2) (SETF (AREF (THE (SIMPLE-ARRAY FIXNUM (*)) #:ARRAY-I-833) #:POSITION-830) I) (SETF (AREF (THE (SIMPLE-ARRAY FIXNUM (*)) #:ARRAY-J-834) #:POSITION-830) J) (SETF (AREF (THE (SIMPLE-ARRAY FIXNUM (*)) #:ARRAY-X-835) #:POSITION-830) X) (SETF (AREF (THE (SIMPLE-ARRAY FIXNUM (*)) #:ARRAY-Y-836) #:POSITION-830) Y) (INCF #:POSITION-830) ;; (car array-names): all ararys have the same size. If the first one is ;; full, increase the size of all of them: (WHEN (>= #:POSITION-830 (THE FIXNUM (LENGTH #:ARRAY-VAL-1-831))) (SETF #:ARRAY-VAL-1-831 (JP-UTILS:ROBUST-ADJUST-ARRAY #:ARRAY-VAL-1-831 (THE FIXNUM (+ 1000 #:POSITION-830)) :ELEMENT-TYPE (ARRAY-ELEMENT-TYPE #:ARRAY-VAL-1-831))) (SETF #:ARRAY-VAL-2-832 (JP-UTILS:ROBUST-ADJUST-ARRAY #:ARRAY-VAL-2-832 (THE FIXNUM (+ 1000 #:POSITION-830)) :ELEMENT-TYPE (ARRAY-ELEMENT-TYPE #:ARRAY-VAL-2-832))) (SETF #:ARRAY-I-833 (JP-UTILS:ROBUST-ADJUST-ARRAY #:ARRAY-I-833 (THE FIXNUM (+ 1000 #:POSITION-830)) :ELEMENT-TYPE (ARRAY-ELEMENT-TYPE #:ARRAY-I-833))) (SETF #:ARRAY-J-834 (JP-UTILS:ROBUST-ADJUST-ARRAY #:ARRAY-J-834 (THE FIXNUM (+ 1000 #:POSITION-830)) :ELEMENT-TYPE (ARRAY-ELEMENT-TYPE #:ARRAY-J-834))) (SETF #:ARRAY-X-835 (JP-UTILS:ROBUST-ADJUST-ARRAY #:ARRAY-X-835 (THE FIXNUM (+ 1000 #:POSITION-830)) :ELEMENT-TYPE (ARRAY-ELEMENT-TYPE #:ARRAY-X-835))) (SETF #:ARRAY-Y-836 (JP-UTILS:ROBUST-ADJUST-ARRAY #:ARRAY-Y-836 (THE FIXNUM (+ 1000 #:POSITION-830)) :ELEMENT-TYPE (ARRAY-ELEMENT-TYPE #:ARRAY-Y-836))))) ;; position now holds the size of the final traversal, so we adjust all arrays to that ;; size: (SETQ #:ARRAY-VAL-1-831 (JP-UTILS:ROBUST-ADJUST-ARRAY #:ARRAY-VAL-1-831 #:POSITION-830 :ELEMENT-TYPE (ARRAY-ELEMENT-TYPE #:ARRAY-VAL-1-831))) (SETQ #:ARRAY-VAL-2-832 (JP-UTILS:ROBUST-ADJUST-ARRAY #:ARRAY-VAL-2-832 #:POSITION-830 :ELEMENT-TYPE (ARRAY-ELEMENT-TYPE #:ARRAY-VAL-2-832))) (SETQ #:ARRAY-I-833 (JP-UTILS:ROBUST-ADJUST-ARRAY #:ARRAY-I-833 #:POSITION-830 :ELEMENT-TYPE (ARRAY-ELEMENT-TYPE #:ARRAY-I-833))) (SETQ #:ARRAY-J-834 (JP-UTILS:ROBUST-ADJUST-ARRAY #:ARRAY-J-834 #:POSITION-830 :ELEMENT-TYPE (ARRAY-ELEMENT-TYPE #:ARRAY-J-834))) (SETQ #:ARRAY-X-835 (JP-UTILS:ROBUST-ADJUST-ARRAY #:ARRAY-X-835 #:POSITION-830 :ELEMENT-TYPE (ARRAY-ELEMENT-TYPE #:ARRAY-X-835))) (SETQ #:ARRAY-Y-836 (JP-UTILS:ROBUST-ADJUST-ARRAY #:ARRAY-Y-836 #:POSITION-830 :ELEMENT-TYPE (ARRAY-ELEMENT-TYPE #:ARRAY-Y-836))) (SYMBOL-MACROLET ((VAL-1 (AREF (THE (SIMPLE-ARRAY NUMBER (*)) #:ARRAY-VAL-1-831) #:INDEX-837)) (VAL-2 (AREF (THE (SIMPLE-ARRAY NUMBER (*)) #:ARRAY-VAL-2-832) #:INDEX-837)) (I (AREF (THE (SIMPLE-ARRAY FIXNUM (*)) #:ARRAY-I-833) #:INDEX-837)) (J (AREF (THE (SIMPLE-ARRAY FIXNUM (*)) #:ARRAY-J-834) #:INDEX-837)) (X (AREF (THE (SIMPLE-ARRAY FIXNUM (*)) #:ARRAY-X-835) #:INDEX-837)) (Y (AREF (THE (SIMPLE-ARRAY FIXNUM (*)) #:ARRAY-Y-836) #:INDEX-837))) (LOOP FOR #:INDEX-837 BELOW (LENGTH #:ARRAY-VAL-1-831) DO (SET-2D-MATRIX PROD (+ (* I 5) X) (+ (* J 5) Y) (* VAL-1 VAL-2))))) *NOTE*: When you do a fast-traversal, you are NOT operating on the original structures anymore, but on a copy (see the code above).

W/SPARTN-TRAVERSALS (TRAVERSAL-LIST &BODY BODY)

Traverses several tensors, possibly synchronizing indices. For example: (w/spartn-traversals ((A data-a i j k l val-a) (B data-b i j k val-b) ...) Will traverse data-a and data-b (of type A and B respectively), looping over l. (w/spartn-traversals ((A data-a i j k l val-a) (B data-b a b i j val-b) (C data-c i a m n val-c :dont-bind (b m))) ...) Will traverse data-a, data-b and data-c, but the only entries will be those such that the first index on data-a and data-c are equal to that of the second index of data-b, and so on.

W/SPARTNS (SPARTN-LIST &BODY BODY)

Creates local definitions for functions and macros to access a spartn scheme. These are the same functions and macros that DEFSPARTN creates if you pass it DEF=T. This is useful if you don't want the overhead of function calls (including boxing and unboxing of numbers). This macro will use LABELS and MACROLET to create the functions and macros that access the spartns in spartn-list. Example: (defspartn xyz ... :def nil) (w/spartns (xyz) (let ((s (make-xyz))) (set-xyz s '(0 0 0) 0.5) ...)) The w/spartns S-expression will be expanded into: (labels ((make-xyz (...)) (get-xyz (...)) (set-xyz (...)) ...) (macrolet ((traverse-xyz ...)) (let ((s (make-xyz))) (set-xyz s '(0 0 0) 0.5) ...)))

Private

DO-TRAVERSE-CVECTOR ((INDEX VALUE CVEC &KEY (ELEMENT-TYPE T) (START 0) (END -1) (SETF T)) &BODY BODY)

Traverses a cvector, binding variables to the index and value. element-type is used in type declarations inside the code; start and end are used for indices; setf is a flag that makes the method use SYMBOL-MACROLET instead of LET for the value binding (it is on by default). Example: (macroexpand-1 '(spartns::do-traverse-cvector (i v d) b)) ==> (LET ((#:FIXED-END-775 (1- (SPARTNS::CVECTOR-COUNT D)))) (LOOP SPARTNS::FOR #:I-774 FIXNUM SPARTNS::FROM 0 SPARTNS::TO #:FIXED-END-775 DO (LET ((I (AREF (SPARTNS::CVECTOR-INDEX D) #:I-774))) (SYMBOL-MACROLET ((V (AREF (THE (SIMPLE-ARRAY T (*)) (SPARTNS::CVECTOR-VALUES D)) #:I-774))) (DECLARE (TYPE T V) (TYPE FIXNUM I)) B)))) T

GET-CVEC (CV INDEX SPARSE-ELEMENT ELEMENT-TYPE TEST-EQUAL)

Retrieves an element from a cvector, given its index. If the element is found, returns (values element T). If the element is not in the vector, returns (values sparse-element NIL) instead.

MAKE-NEW-CVECTOR (SIZE &KEY (ELEMENT-TYPE T) (SPARSE-ELEMENT 0))

Makes a new (empty) cvector with maximum capacity equal to size. The element-type parameter can be used to make the internal representation more efficient. The default element-type is T.

PACK-CVEC (CV ELEMENT-TYPE)

Packs a cvector so cvector-count will be the same as cvector-max-capacity.

RESIZE-CVEC (CV ELEMENT-TYPE NEW-SIZE)

Resizes a cvector, adjusting the arrays for values and indices

SET-CVEC (CV INDEX SPARSE-ELEMENT ELEMENT-TYPE VALUE RESIZE-FUNCTION)

Sets an element in a cvector, given its index. If the index is not in the vector, it is added, unless there is no more space left, in which case an error is signaled.

SPARTN-GENERIC-TRAVERSE ((INDEX-LIST VALUE DATA) REP-LIST ELEMENT-TYPE SPARSE-ELEMENT TEST-EQUAL DONT-BIND &BODY BODY)

Traverses a sparse tensor, given: - A list of symbols (that will be bound to the indices) - A symbol to be bound to the value - The data - The representation scheme - The body

VARIABLE

Private

*REPRESENTATION-SCHEMES*

This variable holds a hashtable that maps names (symbols) to representation schemes for sparse vectors. These are structures that map fixnums onto data of any type.

*SPARTN-SCHEMES*

This variable holds a hashtable which maps names onto spartn schemes.

CLASS

Public

Undocumented

ARRAY

Private

Undocumented

SPARTN-SCHEME