Monday, September 20, 2004

Just how stupid do you think we are?

Seen on #prolog on freenode:

--> Initial_KK ( has joined #prolog
<Initial_KK> hi All
<Initial_KK> what's this program do?
<Initial_KK> member(X,[X|_]).
<Initial_KK> member(X,[_|T]) :- member(X,T).
My guess? Your Homework you lazy slob.

Friday, September 17, 2004

Orthogonality == Flexible ?

As a core developer of Kowari I am regularly faced with both the good and the unfortunate aspects of RDF. One thing I continually run up against is the seemingly arbitary distinctions between subject, predicate, and object nodes. In this particular case, I still can't find out why RDF won't permit blank nodes as predicates. The same goes for Literals as subjects and predicates. Having a string literal as a predicate or subject is a little strange, and almost certainly bad style, but a typed literal most certainly makes sense. If I want to make statements about the number 5 (LT 6, GT 4, isPrime, isOdd, etc) currently we either have to use bnodes, or fake URIs, so we get:

_:bnA <owl:sameAs> '5'^^<xmls:decimal>
_:bnB <owl:sameAs> '4'^^<xmls:decimal>
_:bnC <owl:sameAs> '6'^^<xmls:decimal>
_:bnA <lessThan> _:bnC
_:bnA <greaterThan> _:bnB
'5'^^<xmls:decimal> <lessThan> '6'^^<xmls:decimal>
'5'^^<xmls:decimal> <greaterThan> '4'^^<xmls:decimal>
This is particularly important when you consider what's involved in merging two such documents. Consider trying to insert a document containing primes, with a document containing prime-factors. As we are currently forced to use bnodes, and bnode-refid's are only valid within a single document we are going to have to stuff around doing bnode unification.

Finally the fact that a URI is itself perfectly fine as a typed literal, suggests that all we really need is bnodes and typed literals (and a fair bit of syntactic sugar, but that's a serialisation issue, so we can ignore that for semantics). At the end of the day, RDF is very cool, but I suspect a fully orthogonal triple-store is even cooler. I suppose it's just fortunate that Kowari is an RDF-store built on top of a generic triple-store ;)

Friday, September 10, 2004


Sometimes life throws you a curve ball. The past week I have been scrambling to help my parents respond to their landlords reasonable, yet highly inconvenient, desire to sell their house vacant possession. Consequently my blog has been neglected of late.

I enjoy reading essays, and I have definately enjoyed reading some of Malcolm Gladwell's contributions to the New Yorker (Gladwell also wrote The Tipping Point, a book I am going to have to read that discusses the effects of non-linearity in social systems). I particularly enjoyed Blowing Up, a look at non-linearity applied to the stock-market; The Mosquito Killer, a facinating look at the anti-malaria campaigns of the 20th century, and DDT in particular; The Dead Zone, the hunt for the Spanish Flu; The Coolhunt, a curious look into the 'cool hunters', a profession I never realised existed. Finally The Tipping Point, an article written four years before the publication of Gladwell's book, a reminder that non-linearity is a fact of life, and humans are particularly bad at anticipating the ramifications.

Thursday, September 02, 2004

Scheme Cookbook.

A few of my friends are also in the process of learning scheme. Stumbled across this interesting site which will not doubt be useful: The Scheme Cookbook. Greg, with his habit of implementing cat will likely be particularly interested in the chapter on Files and Directories.

Paul Graham is at it again.

Paul Graham has published yet another essay. This time the topic is, not inappropriately, essays. As expected, the essay is worth the time to read --- if nothing else his essays are entertaining. Graham presents the essay as a form of exploratory reasoning, attempting to differentiate it from the dissertation which he presents as far more rhetorical in nature. To illustrate this he draws an analogy between the relationship between thought and essay and between conversation and dialogue.

Fundamentally an essay is a train of thought-- but a cleaned-up train of thought, as dialogue is cleaned-up conversation. Real thought, like real conversation, is full of false starts. It would be exhausting to read. You need to cut and fill to emphasize the central thread, like an illustrator inking over a pencil drawing. But don't change so much that you lose the spontaneity of the original.
I couldn't help wondering if a better analogy would be the relationship between blog and essay. I certainly don't take the time to polish my blog posts Paul takes to polish his essays.

I personally found it thought provoking, and if that is a common experience, I guess that would make it a successful essay. I certainly wasn't surprised to see it dwell on Graham's other bug-bear, the shocking state of the modern high-school curricula. Still I find some irony in my main response: pondering the possibility that the internet may trigger a resurgence in the importance placed on rhetoric and the essayist in our society; this would certainly be no bad thing.

Wednesday, September 01, 2004

Equality and Equivalence.

My previous entry on the implementation of Object.equals() has attracted some comment, but the principle response was from Adrian Sutton, who objected to my example of a buggy equals implementation.

In one respect his criticism is valid; in general a subclass should delegate to its superclass for inheritited state equality. To do otherwise is to break encapsulation, and duplicate code. On the otherhand his complaint misses the point:

Class B is incorrectly assuming that it knows how to compare class A's data, and more importantly class B is changing the behavior of A in a way that is not compatible with the original model. Essentially, class A defines equality as having the same n1 values and class B is in the wrong for changing that. [emph added]
What Adrian misses is that if B is unable to meaningfully extend A's definition of equality then A should indicate that by declaring its implementation final, in the absence of a final declaration, B is entitled to extend it. I give an example of a meaningful use of final/instanceof in the Shape/Circle/Ellipse example at the end of the post, which I chose as it conveniently demonstrates all three cases associated with appropriate use of instanceof:
  1. Abstract class implementing equals using instanceof to allow proper delegation of equality in subclasses.
  2. Extensible concrete class, uses instanceof to allow subclassing; equals declared final to enforce contract
  3. Subclassing the concrete class, overriding accessors permitting inherited (unoverridable) equals method to operate correctly (besides meeting the superclass contract ;).
On the other hand Adrian is mistaken when he suggests that the use of getClass() in equals is a bug. There are two flaws with his reasoning. The first arises from a confusion between syntax and semantics. Adrian offers a code fragment, suggesting that it would need A to use instanceof for correctness:
class C extends A {
  public getValue() {
    return n1;
The confusion is in thinking this defines a new class. This is a discussion of semantics, hence any class offered as a counter example must needs be a new class semantically, while the above is strictly syntax. The easiest way to approach the semantics of a class is as a function constructing independent, concurrent, finite automata. Now C doesn't define any new states, and doesn't define any new behaviour (state transitions), semantically then it doesn't define a new class --- mathmatically, C is still isomorphic up to congruence with A, so in a very real sense they are the same class. What C actually defines is a function. A new, if rather clumsy, projection on A returning n1. I had better make it clear that I'm not suggesting there is a non-clumsy way of doing this, rather that the reason why it is valid to want an C to be equivalent to a A is that C doesn't define a new class, just a new function. Hence it is a completely different case to B, which is a non-congruent class. If you have a concrete class that must support subclassing, instanceof is a bug.

Moreover this is exactly what we would expect when we consider what it actually means for two objects to be equivalent. Remember, an object is an FA, and as such there is a well established body of work on the meaning of equivalence, anyone interested should read up on simulation and bisimulation. Informally however the key is recognising that the bundling of state and behaviour provided by an object is not just something we get to ignore when it becomes inconvenient, at least not without losing correctness. That if we are serious about OO, we are not just answering the question "are we currently in the same state?", but "are we in the same state, and will we remain in the same state in response to the same stimula?". In other words, it doesn't matter that B.n1 == A.n1, if A and B have different behaviours they aren't the same object.

It becomes particularly important to recognise this when you face the prospect of also implementing Comparable. The problem here is that the contract for compareTo is that of a Total Order. The best you can manage on A U B is a Pre-order, and once again you are left with the prospect of subtle and obscure bugs. From the javadoc for Comparable:

This interface imposes a total ordering on the objects of each class that implements it. This ordering is referred to as the class's natural ordering, and the class's compareTo method is referred to as its natural comparison method. ... For the mathematically inclined, the relation that defines the natural ordering on a given class C is:
       {(x, y) such that x.compareTo((Object)y) <= 0}.
The quotient for this total order is:
       {(x, y) such that x.compareTo((Object)y) == 0}.
It follows immediately from the contract for compareTo that the quotient is an equivalence relation on C, and that the natural ordering is a total order on C. When we say that a class's natural ordering is consistent with equals, we mean that the quotient for the natural ordering is the equivalence relation defined by the class's equals(Object) method:
     {(x, y) such that x.equals((Object)y)}.
Yet after all this, I do share Adrian's pain in this. The unfortunate fact is that if the author implemented A.equals properly, but forgot to include an accessor to A.n1, there is no clean way of gaining access to it. If you do find yourself in this fix, you are left with either direct bytecode hacking (the JVM doesn't know about the access permissions, so you can just access n1 directly), or package injection (if n1 doesn't have private scope). Alternatively, if the author has followed Adrian's advice, it becomes impossible to implement B correctly, and as Adrian's use of instanceof is wrong at a semantic level, no amount of bytecode hackery will save you.

So yet again we come back to my original point. Either you are implementing an abstract class; or you are writing a concrete class and can support either subclass equivalence, or polymorphic equality. "But I need both"!? Tough; Java doesn't support both, and a good engineer knows to work within the limitations of their tools. That a sizable segment of the java community continues to ignore the limitations of their language by presenting incorrect code, pretending that both are achievable, is a sad indictment on the state of that community.