Wednesday, June 24, 2009

Make Tricks

GNU Make represents lists as whitespace-delimited. So, if you have a list of JAR files, you might specify them like so:

JAR_FILES = \
/path/to/jar1.jar \
/path/to/jar2.jar
Of course, other programs, like javac, represent lists using different delimiters such as the colon (:). And unfortunately, GNU Make doesn't provide a convenient way to convert between the two representations. So you have to use a stupid trick:
EMPTY =
JOIN = $(subst $(EMPTY) $(EMPTY),$(2),$(1))
This declares a function, JOIN (but not the built-in join), that you can call when you need to construct the classpath. For example,
javac -cp $(call JOIN,$(JAR_FILES),:) $(JAVA_FILES)
Stuart Feldman first released make in 1977. Hmm.

Monday, February 9, 2009

Inheritance in JavaScript

JavaScript has some surprising strengths and weaknesses. Although I often wish it were more strongly-typed, it can be incredibly convenient to change the behavior of a class by reassigning a method, rather than defining an explicit subclass. Good JavaScript makes abundant use of anonymous functions and closure, and that part at least works quite well.

One serious weakness of the language, however, is that it is a bit too open-ended. We often want to use inheritance, defining a hierarchical structure of code-sharing. JavaScript doesn't have classes, but it does have prototypal inheritance, where multiple objects can share attributes (typically methods, which are simply function objects) via the prototype attribute. This attribute is assigned to the object's constructor before it is constructed, giving the object a semi-secret reference to the prototype (e.g., __proto__) that is used to query prototypal attributes when they are undefined on the instance.

Unfortunately, no one really agrees on the right way to use prototypal inheritance. The most common approach is:

function Graph() { ... }
function Tree() { ... }
Tree.prototype = new Graph();
This does mostly the right thing, because any attributes on the new Graph() instance will be available to any Tree instance via the prototype system. However, it shares too much; not only does it share any attributes assigned to Graph's prototype, it shares any attributes assigned in the Graph constructor. Worse yet, it shares them between all instances of Tree.

How can this go wrong? Well, imagine if the Graph constructor initializes an array:
function Graph() {
this.adjacency = [];
}
Now all of your Tree instances share the same adjacency array, and modifications to one will affect the others. Whoops.

One easy way to fix this is to call the superclass constructor in the subclass. JavaScript doesn't chain constructors for you automatically. However, it's very easy for you to do via the call method on all functions:
function Tree() {
Graph.call(this);
}
This assigns a new array to the adjacency attribute of all new trees, thus short-circuiting the lookup into the shared prototype.

And yet, as you may have noticed, there is still something irksome about this (the most common) approach: the Tree prototype has to construct a "default instance" of Graph to share. But what if there's no such thing as a "default instance"? Don't we just want to share Graph's prototype?
Tree.prototype = Graph.prototype;
From Tree's perspective, this does exactly the right thing. Trees will no longer share a single adjacency field through their prototype if you forget to chain the Graph constructor. However, any subsequent assignments to the Tree prototype will also be applied to Graph. Thus,
Tree.prototype.root = function() { ... };
assigns a root method not only to all Tree instances, but to all Graphs as well. Whoops!

An elegant, if cryptic, solution by Douglas Crockford is the beget object. This is a magic object that shares the same prototype as the superclass, but is not actually an instance of the superclass. This way, you avoid needing to construct a "default" instance of the superclass. I prefer a slight variant of his implementation, adding an extend method to all functions:
Function.prototype.extend = function() {
function f() {}
f.prototype = this.prototype;
return new f();
};
Now, when I'm defining Tree, I say:
Tree.prototype = Graph.extend();
Et voilà! The good news is that now your code works correctly. The bad news is that because this is not built-in to JavaScript, most frameworks define their own inheritance mechanisms, making interoperability difficult or impossible.

Friday, February 6, 2009

Sorting in JavaScript

JavaScript's Array.sort function has a nifty feature where it lets you pass in a sort function, much like a Comparator in Java. A naïve implementation might look like this:

var names = [ ... ];
names.sort(function(a, b) {
return a > b;
});
Looks right, right? I mean, the function is doing a comparison, which is what a comparator is supposed to do, right? Right?

Wrong. The sort function should return one of three values (a negative number, zero, or a positive number). The implementation above returns one of only two values (true or false). This means the implementation above won't distinguish between a and b being equal, and a being less than b. The corrected implementation:
names.sort(function(a, b) {
return (a > b) ? 1 : ((a < b) ? -1 : 0);
};
Note that the original sort function could still work in theory, as long as the caller knew to invoke it twice per comparison, reversing the arguments. I'm not certain, but Firefox appears to support this implementation. Either that, or I was incredibly lucky in an unlucky way.

Sunday, February 1, 2009

Gradients in Java 2D

Java has some built-in support for gradients (such as GradientPaint), but it's fairly limited. The built-in support only allows you to construct linear or radial gradients, clipped to arbitrary shapes. If you, however, want your gradient to follow a particular path, you're out of luck. For example:

gradient-path

The above image is an open uniform b-spline, which starts opaque red and then fades smoothly to translucent blue. (I'll leave it as a separate topic on how to render b-splines in Java 2D; only cubic Bézier curves are built-in.) But it doesn't fade simply from left-to-right, as a linear gradient would do; it fades smoothly along the path of the spline.

My solution was to use a flattening PathIterator to convert the path into a polyline. Then, for each line segment, I compute the appropriate bounding polygon to fill with a static color. Unfortunately, Java's built-in support for stroking paths is not very helpful here, so you have to implement your own joins. Since I'm rendering each segment with a static color, I also subdivide some of the longer line segments to avoid color quantization.

I'm fairly satisfied with the result as shown above. However, I did notice some unusual artifacts with antialiasing enabled; even though my segment polygons tile exactly (in OpenGL terminology I create a quad strip), Java renders subpixel gaps between segments. This goes away with antialiasing turned off.

Wednesday, October 8, 2008

Emacs Considered Helpful

I know all the cool kids these days are using Eclipse or IntelliJ as their IDE, but for all the old people out there that are still trying to cobble a few lines of C++ together, I'd like to give a shout-out to Emacs: Emacs is glorious. Its capabilities are vast and seemingly endless.

In particular, I've discovered (well, remembered) I can do my entire development cycle in Emacs, rather than switching back and forth to that pesky shell. The main things I really like are:

M-x compile for running make.

M-x gdb for debugging my executable and finding all of the places where I didn't manage memory ownership correctly, or attempted to access arrays out-of-bounds. I'd become so used to stack traces on exceptions in Java that I rarely had to do serious debugging with JDB, but on the other hand I really enjoy debugging interactively using breakpoints and watching data.

M-x svn-status for hooking into my Subversion repository. Using = I can easily diff files (or run C-x v = from the file itself). Using m I can mark files and then type c to checkin. I can also type SHIFT-u to update the files from the repository. It even shows a little colored light in the status bar while I'm editing so I know the file's version control status!

The best thing is that these are built-in to Emacs, rather than some third-party extension. And there are pretty impressive third-party extensions, too. Then again, Emacs is older than I am, so like a fine Port, it's had many years to mature.

Factory Methods in C++

Consider this lesson 1 in C++ for Java programmers: how to write a factory method. The problem in C++ is that objects can either live on the stack, as temporary objects, or in the heap. It's easy to define a method that returns a new object, but what if I actually want that object on the stack?

The solution is that C++ has copy constructors, which let you take a temporary object and copy it into some space you allocated on the heap. So, this means I can now write a simple factory method:

MyObject MyFactory::object(...) {
return MyObject(...);
}
So, if I want an object on the stack, I simply say:
MyObject o = MyObject::object(...);
Whereas if I want an object in the heap, I say:
MyObject* o = new MyObject(MyObject::object(...));
I believe that "modern" compilers may even be smart enough to avoid the extra copy in this situation, by having the factory method initialize directly into the new memory on the heap. But I'm not so sure.

The upside of this approach is that you can now create objects either on the stack or the heap using the factory method. The downside is that this can't be done with polymorphism; polymorphic objects can only be created in the heap, because the compiler can't know the true type of the returned object from the factory method (because it may be determined at runtime).

So, in practice, you may want to create objects exclusively in the heap when using factory methods. And this is effectively what Java does; only primitives and references live in the stack. Of course, if you do this with C++, you then have to manage the new and delete operations explicitly, which can be cumbersome if the factory method is used to create short-lived objects. And then you could say, why not use smart pointers?

To which I say... why not use Java?

Thursday, October 2, 2008

Why C++ is Broken

... in two lines. The following statment constructs a new instance of MyClass using the default constructor:

MyClass myObj1;
However, if you add parens, as you often do while calling a constructor:
MyClass myObj1();
It changes the statement to a forward declaration for a function called "myObj1" that takes no arguments and returns an instance of MyClass. This is even true inside a function, since you can define local functions.