Common Lisp: Generic Function Specializing on Array Length

Question

I am just getting started with generic functions and am wondering if this is possible (I really hope so!).

I have made 3 packages for handling vectors of different lengths: vector2, vector3 and vector4.

Each package has functions that handle vectors of that length:

vector2:normalize - for normalizing *vector2s*
vector3:normalize - for normalizing *vector3s*
etc.

My vectors are typed arrays (for speed and memory use as this is for writing games) so a vector3 is:

(make-array 3 :element-type `single-float).

Now I am writing a package called vectors which will contain generic functions to handle any vector types.

So passing vector:normalize a vector3 should return a vector3 and so on.

I tried this:

(defmethod v+1 ((vec-a #.(class-of (make-array 3 
                       :element-type 
                       `single-float)))
        (vec-b #.(class-of (make-array 3 
                       :element-type 
                       `single-float))))
  (v3:v+1 vec-a vec-b))



(defmethod v+1 ((vec-a #.(class-of (make-array 4
                       :element-type 
                       `single-float)))
        (vec-b #.(class-of (make-array 4 
                       :element-type 
                       `single-float))))
  (v4:v+1 vec-a vec-b))

...based on what I saw in question 6083238, but obviously that only specialized on simple, single-float arrays as:

V> (class-of (make-array 4 :element-type  `single-float))
#<BUILT-IN-CLASS SB-KERNEL::SIMPLE-ARRAY-SINGLE-FLOAT>

What would be the best method of doing this, considering it needs to be fast and not memory hogging?

Cheers in advance!

Answer 1

Generic functions in CL can be specialized either with classes or EQL-specializer (see PCL chapter on GFs). Classes aren't types, although there's some relation. But in your case you have a single class and a single type. So, effectively, you want to specialize the methods on some arbitrary property. This can only be achieved with an EQL-specializer:

(defmethod v+1 ((size (eql 3)) vec-a vec-b)
  (v3:v+1 vec-a vec-b))
(defmethod v+1 ((size (eql 4)) vec-a vec-b) 
  (v4:v+1 vec-a vec-b))

They don't do any bounds checking, and also are somewhat more clumsy. The first problem can be solved by adding a check inside the method's body:

(defmethod v+1 ((size (eql 3)) vec-a vec-b)
  (assert (= 3 (length vec-a) (length vec-b))
    "Vector size mismtach")
  (v3:v+1 vec-a vec-b))

You can also define a macro to generate such methods for any size.

Another option is to use a macro at call site, that will present a simpler interface and can perform error checking as well:

(defmacro v+1* (vec-a vec-b)
  (once-only (vec-a vec-b)
    `(if (= (length ,vec-a) (length ,vec-b))
         (v+1 (length ,vec-a) ,vec-a ,vec-b)
         (error "Vector size mismatch"))))

For a discussion of ONCE-ONLY see PCL chapter on macros.

Answer 2

Essentially, there is no way to dispatch based on the size of a vector. As Vsevolod points out, generic functions in CLOS dispatch based on class, and the class of an array in Common Lisp is not altered by the number of elements it holds.

However, if performance is your main aim, then it might not be something you'd want to do either way; involving multiple dispatch in every operation at such a low level could potentially bog you down a bit.

Possible alternatives:

1. Think like an engineer. Convince yourself that operators on 2-, 3- and 4-vectors are fundamentally different things for your purposes and likely to appear in such different circumstances that it makes sense to have a distict notation for each, then tune those functions as much as possible. Eg: Just define and use +vector3, normalize-vector3 etc.

2. Think like a mathematician. Define the most general operators possible, ones that should work on any vector length. Worry about performance later, optimizing only those specific parts of the code that slow you down the most in the actual running program. Eg:

   (defun v+ (&rest vectors)
     (apply #'map 'vector #'+ vectors))
   
   (defun normalize (vector)
     (sqrt (reduce (lambda (acc x) (+ acc (* x x))) vector
                   :initial-value 0)))
   

   etc.

3. Think like people think Common Lisp programmers think and macro it all away. If you want efficiency but feel you need a consistant interface, then if generic functions can't do what you want, or can't do it fast enough, you might try something like this:

   (defvar *vector-op-table* '())   
   
   (defmacro defvectorops (dimensions &body mappings)   
       `(setf (getf *vector-op-table* ,dimensions) ',mappings))   
   
   (defun vector-op-reader (stream subchar numarg)   
     (declare (ignore subchar))   
     (let ((form (read stream))   
           (op-table (getf *vector-op-table* numarg)))   
       (sublis op-table form))) 
   
   (set-dispatch-macro-character
     #\# #\v #'vector-op-reader)
   

   Which would allow you to define mappings between the names in your standard vector interface (v+1, normalize etc.) and the names of any specialised functions for performing the associated operations (either named as in suggestion 1, or package-qualified). Eg:

   (defvectorops 2
     (v+1 . +vector2)                ; or vector2::v+1, if you want
     (normalize . normalize-vector2)
     ...)
   
   (defvectorops 3
     (v+1 . +vector3)
     ...)
   

   Which causes forms such as

   #2v(normalize (v+1 a b)) ; => (normalize-vector2 (+vector2 a b))
   #3v(normalize (v+1 a b)) ; => (normalize-vector3 (+vector3 a b))
   

   to read as a form using the specialized ops, letting you can define such mappings for any dimension of vector, changing only the digit in #v if you want any peice of code to work for different dimensions of vector.

   (You could have DEFVECTOROPS define these mappings for you if you use a standard naming convention, but sometimes it's best to keep things explicit).

Do bear in mind that any code above is untested (I'm at work and don't have a lisp system available), and the last solution especially is full of Starship Troopers level bugs that will seriously hurt you (there are saner ways to do it, but this was just for illustration), but I just thought it might be good to consider some possible alternate solutions. Which you choose depends on the best fit for the program / programmer. (I'd probably go for option 1 or 2, though.)