Casual Effects: Polymorphic vector operations for JavaScript

I wrote a small vector math (linear algebra/geometric) library codeheart.js because any kind of physical simulation for a game becomes awkward and redundant when implemented purely with scalar expressions. My current design is the result of several radically different experiments. I'm satisfied with the blend of special- and general-purpose code. It seems neither over-engineered nor too limited. The features that I sought were:

Support functional addition, subtraction, Haddamard/array multiplication and division, dot product, magnitude, and direction
To allow implementing polymorphic math routines, allow the same set of functions to operate on vectors:

of any number of components
with differently-named fields (e.g., xyz vs rgb vs. st)
implemented as Javascript arrays
from other libraries (especially box2d.js)
...and Javascript Numbers

Simple for me to maintain
Unlikely to exhibit hard to diagnose bugs (i.e., not too clever)

I originally wanted objects to be able to override the default behavior in order to provide their own definition of operations (e.g., for complex number multiplication), but backed off--this relied on prototypes and was fragile and sensitive to other library's conventions. For example, box2d's vector math has the same method names but mutates the argument, and that would have easily led to bugs in polymorphic code.

Javascript uses "protype" inheritance and has no (straightforward or trustworthy) method for determining the type of an object (although there are hacks). This makes dynamic dispatch tricky. I'm generally suspicious of templates, generics, overloading, inheritance, and alternative polymorphic mechanisms to first-class functions. They allow great code reuse but often open the door to subtle bugs and hard-to-understand error messages. I use prototype inheritance sometimes, but generally prefer invoking functions directly in Javascript because it is obvious to the caller what the code does and name conflicts can't interfere with semantics.

First-class functions are obviously the preferred method for implementing dynamic dispatch based on the Javascript language design. The question is how to use them. My solution was to implement a generic "apply" (really, a "map") operation that is hidden in the library, and then write small stub functions that use it to implement other operations. The apply operation has special cases for numbers, arrays, and objects (when these are mixed it promotes scalars to act like arrays or objects). The object rules are the only interesting ones. They create an object that has the same fields and prototype as its arguments, and then iterate over them. This is what ensures all of the listed properties above. The code looks like this:

/* 
   Applies arithmetic vector op to all elements of a and b.
   If one is an object, then the result is also an object
 */
function _ch_vecApply(opname, op, a, b) {
    var c, i, p;

    if (isNumber(a)) {
        if (isNumber(b)) {
            c = op(a, b);
        } else if (isArray(b)) {
            // scalar + array
            c = [];
            for (i = 0; i < b.length; ++i) c[i] = op(a, b[i]);
        } else {
            // scalar + object
            c = {};
            c.__proto__ = b.__proto__;
            for (p in b) if (b.hasOwnProperty(p)) c[p] = op(a, b[p]);
        }
    } else if (isNumber(b)) {
        if (isArray(a)) {
            c = [];
            for (i = 0; i < a.length; ++i) c[i] = op(a[i], b);
        } else {
            // object + scalar
            c = {};
            c.__proto__ = a.__proto__;
            for (p in a) if (a.hasOwnProperty(p)) c[p] = op(a[p], b);
        }
    } else if (isArray(a)) {
        // array + array
        if (! isArray(b)) _ch_error('Cannot apply ' + opname + ' an array and an object');
        if (a.length !== b.length) _ch_error('Cannot apply ' + opname + ' to arrays of different lengths');
        c = [];
        for (i = 0; i < a.length; ++i) c[i] = op(a[i], b[i]);
    } else {
        // object + object
        if (isArray(b)) _ch_error('Cannot apply ' + opname + ' an object and an array');
        if (a.__proto__ !== b.__proto__) _ch_error('Cannot apply ' + opname + ' to ' + a + ' and ' + b + ' because they have different prototypes');
        c = {};
        c.__proto__ = a.__proto__;
        for (p in a) if (a.hasOwnProperty(p)) c[p] = op(a[p], b[p]);
    }

    return c;
}

The individual functions revealed to the library user are implemented as:

function _ch_add(x, y) { return x + y; }
function add(a, b) {
    _ch_checkArgs(arguments, 2, 'add(a, b)');
    return _ch_vecApply('add', _ch_add, a, b);
}

It was easy to implement the pile of functions like this and the slightly-special case magnitude(), dot(), and direction(). I may generalize this into general-purpose map() and reduce(), but that would be overreaching for my current goals.

Note that Javascript doesn't have functions like isArray (in the versions currently deployed in browsers), so I give those helpers here as well:

function isNumber(x) {
    return (typeof(x) === "number");
}

function isBoolean(x) {
    return (typeof(x) === "boolean");
}

function isArray(x) {
    // First check for some array method before calling the potentially slow toString method
    return (x !== undefined) && (x.push !== undefined) && (Object.prototype.toString.call(x) === "[object Array]");
}

function isString(x) {
    return (typeof(x) === "string");
}

function isObject(x) {
    return (typeof(x) === "object") && ! isArray(x);
}

function isFunction(x) {
    return (typeof(x) === "function");
}

Morgan McGuire is a professor of Computer Science at Williams College and a professional game developer. He is the author of The Graphics Codex, an essential reference for computer graphics that runs on iPhone, iPad, and iPod Touch.

Friday, April 19, 2013

Polymorphic vector operations for JavaScript