Joseph D. Darcy's Sun Weblog

Wednesday August 19, 2009

Generics and the Mandelbrot set

Elaborating on some slides from a JavaOne talk, the Mandelbrot set is defined recursively as the set of values in the complex plane C where the iterations z_n+1 = z_n² + c remain bounded, giving rise to a familiar and complex shape.

Determining whether a particular point is inside or outside the boundary of the Mandelbrot set can be difficult because of the fractal nature of the curve; however, good approximations are possible. First at a coarse level, if the absolute value of a point is greater than 1, it is definitely not part of the Mandelbrot set so all of the Mandelbrot set is contained within a circle of radius 2 centered at the origin. Second, there are two primary curves within the set:

• A circle of radius ¼ centered at (-1, 0)

• A heart-shaped cardiord whose boundary is c = e^it/2 - (e^it/2)²

The overall area of the Mandelbrot set is a bit over 1.5; the circle has area ≈0.1963, 13.0% of the total, and the cardiord has area ≈1.178, 78.1% of the total. Therefore, together the circle and cardiord contain over 90% of the area of the whole set and it is comparatively easy to determine if a point is inside or outside the union of the circle and the cardiord.

Using generics in Java has some similarities to the Mandelbrot set. Generics can be recursive, such as in the f-bound in the declaration of java.lang.Enum: public abstract class Enum<E extends Enum<E>>..., and it can be trickly to determine if a use of generics is reasonable. Fortunately, another similarity is that there are two primary use-cases for generics that cover the vast majority of sensible scenarios:

• Generic aggregates, List<T>, Set<T>, etc.

• Type tokens, Class<T> (or even super type tokens)

Aggregates like subtypes of java.util.Collection are the heart of generics usage and using generic collections is usually straightforward; Effective Java's PECS mnemonic (producer-extends, consumer super) provides guidance for some of the trickier cases. The second most common use of generics is for type tokens, Class<T>, which embody type information both at compile-time and at runtime. For example, type tokens are used to retrieve annotations.

Be wary of other uses of generics in Java. Java's generics have significantly technical differences from templates in C++; Java generics are by design not a Turing-complete meta-language! Attempting to use Java generics to simulate features in another languages, like Haskell's pattern matching, is unlikely to lead to pleasant or idiomatic Java code. In a Java program, using pervasive type parameters to pass along other information throughout a program, such as to address code evolution issues, is also not a pleasant fit. A warning sign in API design is a Java class having more than two type parameters; this likely signals generics are being used in an awkward way.