Wednesday, October 31, 2007

Immutable objects in Java

I just read a clever post from JP Moresmau on a functional language he is writing which translates to Java.

One idea which lept out at me was how to provide setters to immutable objects in Java: the setters are instance factory methods, thus:

class DontTreadOnMe {
    public final String species;
    public final int length;

    DontTreadOnMe(String species, int length) {
        this.species = species;
        this.length = length;
    }

    // Snakes can grow but cannot change species
    DontTreadOnMe setLength(int length) {
        return new DontTreadOnMe(length);
    }
}

This works rather nicely for code which uses the convention. Unfortunately, the getter/setter idea is so firmly embedded in the fingertips of Java coders, that I expect this bug frequently:

final DontTreadOnMe copperhead
        = new DontTreadOnMe("Copperhead", 1);
// Grow in length
copperhead.setLength(2);
// Oops! Does not work as expected but compiles

My preference is for the bean properties proposal. Make immutables with read-only properties; use copy-construction to make new objects with different field values (fortunately Java copy construction is vastly simpler than C++).

Saturday, October 27, 2007

Hamcrest matchers

I missed this post from Joe Walnes a while ago on using Hamcrest matchers for more than testing.

I appreciate their DSL-like quality and clever mixture of literate class names, static factory methods and Java generics.

In his post Joe Walnes references Håkan Råberg's nice idea for filtering collections with Hamcrest matchers, but unfortunately that post links to no code, usage examples. select and reject are trivial to code:

public static <T> List<T> select(
        final Collection<T> c,
        final Matcher<T> matcher) {
    final List<T> select = new ArrayList<T>();

    for (final T t : c)
        if (matcher.matches(t))
            select.add(t);

    return select;
}

public static <T> List<T> reject(
        final Collection<T> c,
        final Matcher<T> matcher) {
    return select(c, not(matcher));
}

The statically-typed query API is not so trivial to toss off early in the morning. Hopefully Håkan Råberg will release code at some point.

UPDATE: Nat Pryce was kind enough to point to Hamcrest Collections, itself inspired by Håkan Råberg's post. Thanks, Nat!

Tuesday, October 23, 2007

Feature request for JDK7: delegation

Some while back I wrote about delegation for Java. Delegation? By this I mean direct language support for constructor-based dependency injection of interface implementation, a.k.a. mixins.

Many interesting proposals for JDK7 are in the air: the smell of change is replacing the mustiness of an aging language and I want my chance to improve Java while there is a open window of opportunity.

About delegation

For more details follow my three-year old posting. In a nutshell, delegation is assignment to this in a constructor to inject an interface implementation without the need for manually coding boilerplate forwarding methods.

An example makes this more clear:

interface Blogger {
    boolean post(final String entry);
}

// Without delegation
class MessyCoder implements Blogger {
    private final Blogger bloggerDelegate;

    MessageCodeBlogger(Blogger bloggerDelegate) {
        this.bloggerDelegate = bloggerDelegate;
    }

    public boolean post(final String entry) {
        return bloggerDelegate.post(entry);
    }
}

// With delegation
class CleanCoder implements Blogger {
    CleanCoder(Blogger bloggerDelegate) {
        this = bloggerDelegate;
    }
}

In an example this small, the gain in clarity and bug-avoidance is limited, but for larger interfaces or for multiple interfaces, the gain is proportionately larger.

The bigger picture

Providing cleaner code is only a small benefit of delegates. A larger benefit is that of mixins: dynamic implementation inheritance without breaking the single-inheritance contract of Java. Extension by composition—rather than inheritance—becomes a first-class syntax citizen of the language.

Delegates solve the mixin problem raised by Bruce Eckels about Java generics, and do so without needing aspects. (Although, behind the scenes, the compiler very well may use aspects to implement delegates. But you the over-committed programmer need not spend your short time on this point.)

Of course, you could always just fake it or do it the hard way.

UPDATE: More thoughts here and another solution.

Thursday, October 11, 2007

Java data validation trick with bit-twiddling

I have a specialized value object with the property that fields can be null but only in a particular order:

class Data {
    private final String field1;
    private final String field2;
    private final String field3;

    public Data(String field1, String field2,
            String field3) {
        if (!valid(field1, field2, field3))
            throw new IllegalArgumentException();

        this.field1 = field1;
        this.field2 = field2;
        this.field3 = field3;
    }

    // ...
}

The rule is simple: Given the order of the fields 1-4, any later field may be null provided that no earlier field is null. That is, "abc", "def", null is ok but "abc", null, "ghi" is invalid.

So the question becomes, How to code up valid?.

The straight-forward approach of nested if-else blocks becomes particularly unwieldy as more fields are added. But it turns out there is a clever solution using bit-twiddling:

private static boolean valid(String... fields) {
    byte flag = 0; // Fails after 8 fields

    // Sets the i-th bit for each non-null field
    for (int i = 0; i < fields.length; ++i)
        if (null != fields[i])
            flag |= (1 << i);

    // Math trick: 2n ∧ 2n-1 = 0
    return 0 == (flag & flag + 1);
}

In words: the flag has a 1-bit for each non-null field in argument order. The validation condition only holds when the 1 bits are in sequence starting at the 0-th position with no gaps, e.g., 00000111. That particular bit pattern is the same as one less than some power of two. Use the math fact that in bit arithmetic, 2n ∧ 2n-1 = 0 to check the condition.

Thanks to this powers-of-two problem for pointing the way.

Wednesday, October 10, 2007

Dethreading a chicken

Anyone who has tried knows what messy task deboning a chicken is (unless you are Morou Ouattara.) Likewise I face the messy task of protecting multi-threaded legacy code from itself.

I face a complex graph with an elaborate API. It is thread-safe in that individual nodes are locked, but it is not thread-consistent: changes traversing the graph are not isolated from each other.

What to do?

One approach which is of general application is to dethread the data structure. That is, turn it from multi-threaded access to single-threaded.

The task is made much simpler by the JDK5 concurrency library. First, create a facade for the original API:

interface Complexity {
    void methodOne(int argOne);
    int methodTwo();
    // ... ad nauseum
}

Next create command classes for each method call in the API:

class MethodOne
        extends Runnable {
    private final Complexity realGraph;
    private final int argOne;

    MethodOne(Complexity realGraph, int argOne) {
        this.realGraph = realGraph;
        this.argOne = argOne;
    }

    void run() {
        realGraph.methodOne(argOne);
    }
}

class MethodTwo
        extends Callable<Integer> {
    private final Complexity realGraphy;

    MethodTwo(final Complexity realGraph) {
        this.realGraph = realGraph;
    }

    Integer call() {
        return realGraph.methodTwo();
    }
}

// ... ad nauseum

Finally, wire the facade to forward calls to a queue for replay into the real graph with a dedicated single thread:

class SingleThreadComplexity implements Complexity {
    private final ExecutorService commands
            = Executors.newSingleThreadExecutor();
    private final Complexity realGraph
            = new OriginalMultiThreadComplexity();

    public void methodOne(int argOne) {
        commands.submit(new MethodOne(realGraph, argOne);
    }

    public int methodTwo() {
        try {
            return commands.submit(new MethodTwo(realGraph)).get();
        } catch (InterruptedException e) {
            throw new RuntimeException(e);
        } catch (ExecutionException e) {
            throw new RuntimeException(e);
        }
    }

    // ... ad nauseum
}

Finishing up

Unless the caller has special latency needs violated by the queueing of commands, the facade is a drop-in replacement for the original complex graph but with the new property that the original is always accessed sequentially from the same thread. Goetz calls this property thread confinement.

The complex, messy graph—a fowl thing indeed—is now dethreaded.