The Archive of Formal Proofs

This is pretty kick-ass: machine-generated formal proofs in computer science. Let me say that I, for one, welcome our new generic theorem-proving overlords.

Messaging on one channel

For a simple application wanting to talk to itself, messaging on a single channel works well (or on two channels, input/output, to keep republishing from within an event handler from recursing). But to support class-hierarchy events instead of attribute-based ones calls for a decent data structure since you need reflection in both discovery and publishing.

The key code is:

public void publish(final Event event) { final Set<Receiver> receivers = new HashSet<Receiver>(); for (Class eventClass = event.getClass(); Event.class.isAssignableFrom(eventClass); eventClass = eventClass.getSuperclass()) for (final Pair<Receiver, Method> pair : getPairs(eventClass)) invokeOnce(receivers, pair.first, pair.second, event); }

Which looks up receiver/method pairs from an eventClass/pair map built from receiver subscriptions to the channel. InvokeOnce uses a set to remember if a receiver was already given the incoming event. Since publish starts with the most derived event class and works its way up towards the event base class, this ensures that only the receive method with the most derived event class argument is invoked.

You can have several receive methods, each with a different event class argument, and the best matching one is called. (For once, I am glad for single inheritance: this scheme would break with diamond inheritance.)

More on generics

Unfortunately, Sun's generics are not as similar to C++ templates as one might hope. For example, because of type erasure there is no difference between Foo<Bar> and Foo<Baz> in bytecode. That means that you cannot compile this appealing snippet:

class Peter implements Receiver<PaulMessage>, Receiver<MaryMessage> { // ... public void onEvent(final PaulMessage paulsCalling) { } public void onEvent(final MaryMessage marysKnocking) { } }

Why not? Because Receiver<PaulMessage> and Receiver<MaryMessage> both compile down to just Receiver JDK5 does not permit duplicate declarations in the implements list. This greatly lessens the usefulness of my previous post.

Messaging with generics

Talking to my programming pairmate, Gregor Hohpe, we discussed a Java project using messaging that distinguished messages by type rather than by id or topic. A drawback is that with JDK1.4 you need reflection or extra coding to make it work nicely. Generics in JDK5 take care of this:

public interface Receiver<E extends Event> { void receive(final E event); } public interface Channel<E extends Event> extends Receiver<E> { void subscribe(final Receiver<E> receiver); void unsubscribe(final Receiver<E> receiver); }

Here, receivers and channels are typed by event. By making events into a hierarchy—consider the advantages and disadvantages of the Exception hierarchy—, ipso facto receivers and channels mirror that hierarchy. (In this fragment channels are multiplexed receivers, one of many choices.)

One could also type receivers by channel:

public interface Receiver<E extends Event, C extends Channel<E>> { void receive(final E event); }

But this seems too tightly coupled.

Partial continuations

This is a clever idea: partial continuations. My language geek sense is tingling.

Good physics books

I recently acquired some good physics books. Best among them:

Mathematical Methods for Physicists, Arfken and Weber

An outstanding text for undergraduate and early graduate physics math. Particularly useful are the problem sets and the emphasis on physics applications.

A Modern Introduction to Particle Physics, Fayyazuddin and Riazuddin

Putting the use of articles aside (Pakistani English isn't exactly the same as American), the writing is direct, very clear and to the point. This is a great text to read through and research interesting points on the side as you go along.

I really enjoy summer reading.

Value objects with JDK1.5

Trying out generics, I made a generic value object with JDK 1.5:

/** * <code>ObjectValueBase</code> is the abstract base for simple comparable, * value types. * * @author <a href="mailto:binkley@alumni.rice.edu">B. K. Oxley (binkley)</a> * @version $Revision$ * @since 1.0 */ abstract class ObjectValueBase <T extends Comparable<T>, V extends ObjectValueBase<T, V>> implements Cloneable, Comparable<V> { private T value; /** * Constructs a new <code>ObjectValueBase</code> with the given * <var>value</var>. * * @param value the value * * @throws IllegalArgumentException if <var>value</var> is invalid */ protected ObjectValueBase(final T value) { if (!valid(value)) throw new IllegalArgumentException(); this.value = value; } /** * Gets the value of this value object. * * @return the value */ public T getValue() { return value; } /** * Validates that the given <var>value</var> is permitted for this * <code>ObjectValueBase</code>. Constructors validate input this way. By * default, all inputs are valid; subclasses should override to restrict * input. * * @param value the value */ protected abstract boolean valid(final T value); // Cloneable /** * {@inheritDoc} * * A typical implementation for class <code>Foo</code> which extends * <code>ObjectValueBase</code> is: <pre> public Foo clone() { * return new Foo(getValue()); * }</pre> */ @Override public abstract V clone(); // Comparable /** * {@inheritDoc} */ public int compareTo(final V that) { if (null == that) return -1; else if (null == getValue()) return null == that.getValue() ? 0 : -1; else return getValue().compareTo(that.getValue()); } // Object /** * After self and nullity tests, passes check for equality to the held * value. * * {@inheritDoc} */ @Override public boolean equals(final Object o) { if (this == o) return true; else if (!(o instanceof ObjectValueBase)) return false; else // pass equality test on to value, even for different types return equals((V) o); } private boolean equals(final V that) { if (null == that) return false; else if (null == getValue()) return null == that.getValue(); else return getValue().equals(that.getValue()); } /** * {@inheritDoc} */ @Override public int hashCode() { if (null == getValue()) return 0; else return getValue().hashCode(); } /** * {@inheritDoc} */ @Override public String toString() { if (null == getValue()) return null; else return getValue().toString(); } }

The chief drawback, however, is that Java generics do not support native primitives, unlike templates in C++ or generics in all-object languages such as Scheme. And most value objects I use wrap primitives such as int (any sort of small-scale numeric) or float (often money). So I copy the class, take out the generics, and fix the wrapped type to be the needed primitive. A lot like JDK 1.4, then, but at least I get covariant return types for clone().

UPDATED: I added the C++-trick of including a class as a template parameter of its base class. In this case, by including the class as a generic parameter to ObjectValueBase, I can specify that clone() returns the correct type, no casts required. Neato!

Magic fields in Enum

A little experiment:

public class Scratch { private static enum Fred { A; public void setOrdinal(final int ordinal) { try { final Field field = getClass().getDeclaredField("ordinal"); field.setAccessible(true); field.set(this, new Integer(ordinal)); } catch (IllegalAccessException e) { throw new Error(e); } catch (NoSuchFieldException e) { throw new Error(e); } } } public static void main(final String[] args) { final Fred fred = Fred.A; System.out.println(fred.getClass()); final Field[] fields = fred.getClass().getDeclaredFields(); for (int i = 0; i < fields.length; i++) { System.out.println(fields[i]); } System.out.println(fred.ordinal()); System.out.println(fred); fred.setOrdinal(3); System.out.println(fred); System.out.println(fred.ordinal()); } }

The result?

class Scratch$Fred public static final Scratch$Fred Scratch$Fred.A private static final Scratch$Fred[] Scratch$Fred.$VALUES 0 A Exception in thread "main" java.lang.Error: java.lang.NoSuchFieldException: ordinal at Scratch$Fred.setOrdinal(Scratch.java:29) at Scratch.main(Scratch.java:47) at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method) at sun.reflect.NativeMethodAccessorImpl.invoke(Unknown Source) at sun.reflect.DelegatingMethodAccessorImpl.invoke(Unknown Source) at java.lang.reflect.Method.invoke(Unknown Source) at com.intellij.rt.execution.application.AppMain.main(AppMain.java:78) Caused by: java.lang.NoSuchFieldException: ordinal at java.lang.Class.getDeclaredField(Unknown Source) at Scratch$Fred.setOrdinal(Scratch.java:20) ... 6 more

So the fields in java.lang.Enum are not real but are synthesized by the JVM. Too bad. I wanted to write a runtime-extensible enum, but it looks like I am out of luck.

Also, it looks like there is no reasonable way to do this and support switch. Either I have to do something like:

switch (fred) { case A: doA(); break; default: if (fred.ordinal() == 3) do3(); else dieDieDie(); }

Or it gets really messy:

private static final int ZERO = 0; private static final int THREE = 3; public static enum Fred { A(ZERO) } public static void play(final Fred fred) { switch (fred.ordinal()) { case ZERO: doA(); break; case THREE: do3(); break; default: dieDieDie(); } }

Not nice at all.

The C++ Source

The C++ Source is a new, online C++ journal. More is better (usually).

A page about call/cc

An excellent page on call/cc. If I spent all my time reading about Java I'd quit programming and go back to writing classical music.

Audit history with Hibernate

Christian Bauer at Hibernate posts a very interesting technique for object auditing with Hiberate in combination with database triggers. How useful is this?

Interruptible queries with Java

ONJava.com has a nice article with clean examples of several techniques, Interruptible Database Queries. The clean code includes:

public synchronized ResultSet executeQuery(Statement statement, String query) throws SQLException, InterruptedException { // Set query parameters synchronized (params) { params.statement = statement; params.query = query; params.pending = true; params.notify(); } synchronized (results) { try { // Wait for the query to complete while (!results.serviced) results.wait(); if (results.exception != null) throw results.exception; } catch (InterruptedException e) { cancel(); throw e; } finally { results.serviced = false; } return results.rs; } }

Read the whole article for the worker thread, cancel() and how to put it all together.

APIs

Norman Walsh has an intelligent, interesting post on APIs (in spite of the lame title).

Cellular automata and music from IBM

Big Blue is so much cooler now than when I was a kid. For starters, there's the whole Linux shop a few miles from me here in Austin. And there's stuff like this, Cellular automata and music, a fascinating article featuring the Automatous Monk.

And see the beautiful presentation, Things Computer Science Tells Us About Philosophy. Too bad the darn thing is some sort of PowerPoint presentation!

First-class threads in C++

A library package to provice threads in C++ as first-class objects. From the introduction:

The main goal of RT++ however is to provide a programming interface which is considerably higher-level than that of comparable packages. RT++ considers threads as an abstract datatype with a functional interface i.e. threads communicate only via arguments (which are provided when the thread is defined) and results (which are delivered when the thread has terminated). Threads can be used like objects of any other type i.e. they can be stored in data structures, passed as thread arguments, and returned as thread results. Functional programming languages are called higher-order if they treat functions as first-order objects; we call RT++ higher-order because it treats threads in this way.

And:

RT++ provides a thread/memory management system where programmers need not care about these low-level issues. Thread resources are implicitly allocated as late as possible and implicitly freed as early as possible regardless whether or how often the thread result is retrieved. Threads are subject to garbage collection and automatically reclaimed when not referenced any more. RT++ also provides type constructors for arrays, lists, and general pointer structures whose objects can be passed by reference among threads and that are subject to automatic garbage collection. A high-level notion of non-determinism is supported via thread bags which retrieve their result in the order in which they become available and thus allow to write more abstract (and sometimes more efficient) parallel programs.

This is one reason I prefer C++ to Java for some of my programming — choice. Try replacing java.lang.Thread.

See your garbage, smell your garbage

Moazam Raja points out an interesting tool for watching garbage collection in a running program in his post, Visualizing Garbage Collection. What a pretty picture:

Excellent C++ refresher

Once, Weakly is an excellent C++ refresher blog by Stephen Dewhurst. The only minus is that the posts are PDF files! Still, it is worth the nuisance.

More on delegation

Of course the word I was searching for yesterday was delegation. But there are three flavors of implementation inheritance given:

public interface Bob { void dodeedo(); }

Your basic class inheritance

public class Fred extends BobImpl { }

Typical delegation

public class Fred implements Bob { private Bob bob = new BobImpl(); public void dobeedo() { bob.dobeedo(); } }

Returning the interface

public class Fred { private Bob bob = new BobImpl(); public Bob bob() { return bob; } }

Only in C++ is the first very flexible by using a template parameter to vary the implementing base class. Most code I see does the second, but this falls down when you provide several interfaces, especially when they are poorly designed to fit together such as List and Map. The third is the most flexible and resembles interface discovery. One could code it that way:

public class Fred { private Bob bob = new BobImpl(); public Object discover(Class itf) { if (itf.isAssignableFrom(Bob.class)) return bob; else return null; // alternatively throw something like ClassCastException } }

But that is way overkill most of the time.

Faking implementation inheritance in Java

I am a lazy programmer, and generate far too many typos. What to do when I want my objects to provide more than one interface and share the implementation amongst themselves? I could write a slew of forwarding methods, but that's sloppy and ugly and blows up the classes. I need mixins but Java doesn't have mixins. (However see here and here.) In C++ I could use implementation inheritance in the standard fashion. But what about Java?

The best I have is forwarding methods:

public interface Interface1 { void dobeedo(); } public class Bob implements Interface1 { private Interface1 mixin1; public Bob(Interface1 mixin1) { this.mixin1 = mixin1; } public void dobeedo() { mixin1.dobeedo(); } }

Sure it works, but do you really want to do this for several large interfaces? Poor Bob gets rather cluttered rather quickly.

(NB — What pattern is this? I can't quite put my finger on it. I don't mean the dependency injection, but the forwarding.)

Closures to the rescue

Simon Willison makes excellent use of closures in JavaScript to insert code for page load without interfering with other scripts trying to do the same thing:

function addLoadEvent(func) { var oldonload = window.onload; if (typeof window.onload != 'function') { window.onload = func; } else { window.onload = function() { oldonload(); func(); } } } addLoadEvent(nameOfSomeFunctionToRunOnPageLoad); addLoadEvent(function() { /* more code to run on page load */ });

This is very excellent.

A beautiful language-theoretic post

Maneability has a beautiful post on recombinant computing (yet another buzzwordy phrase) with a good grounding in the classics. The paper reference gets good style points. Enjoy as pleasure reading.

Clever use of Package

This is a class I wish I'd known about earlier: java.lang.Package. Euxx points out that is has the information you need to describe software's version: title, vendor and version for both software specification and the particular implementation. Yummy.

Propagating web exceptions to the test environment

Rather than use in-container testing such as Cactus, our project elected to run the tests separately and communicate with the web using httpunit and jwebunit. For the most part this has worked well but one lingering issue was that exceptions thrown in the container are hidden from the tests, and only show up as the exception handling page (our "red screen").

But, that is different now. We had passed the web session back and forth (a clever trick from Andrew McCormick using a helper servlet) using standard object serialization, but flattened it to a string on the trip back because of serial id mismatches. Then last night I realized that I could use XML serialization from the JDK (XMLEncoder) to serialize the session without worrying about mismatch issues. Once this worked, it was a small step to see to serialize web exceptions and rethrow them in unit tests. A rather neat solution, I think.

Very excellent NKS lecture

Cluey (if that's his real name, Danil) pointed me to to Wolfram's excellent lecture, A New Kind of Science and the Future of Mathematics. Did you buy his book? I did. Wow, is it heavy. It's one of the few books I have to read in pieces — all in one go and I wind up skimming too much. And the pretty pictures... oh so many pretty pictures. Here's just one, but is it a doosie:

To be 20 again, and a new kind of programmer.