A colleague of mine told me how he'd measured the time to calculate the square root of 10 million numbers as part of the evaluation of a product. One of the suprising things is just how fast this is on a modern average specification PC. Have a guess how long this would take in Java doing a simple loop implementation. Answer at the end - it might suprise you.
It seemed to me that this "problem" would be just the sort of thing you could do in the language J very simply; here's some code that works (whether this is how a J master would do it is quite another question):
%: ?10000000#10000000
Yes - that's all!
to explain:
10000000#10000000
gives you a list of 10000000 numbers, each of value 10000000
?10000000#10000000
gives you a list of 10000000 random numbers, each bewteen 0-10000000 (it applies the ? function to every element in the list, ? being a function that gives you a random number from 0 - it's parameter)
%: is the square root function, so %: ?10000000#10000000 gives you a list which is the square root of each number in the list.
So - to answer the speed question, on a desktop machine, the Java version took about half a second. (The speed of the J version will have to wait until I find out how to time things in J, probably really easy but I just haven't bothered to look yet; I was more interested in the neatness of the code rather than the performance).
One of the main activities of the the Design Patterns Revisited workshop, lead by Brian Foote, James Noble, Kyle Brown, and Dirk Riehle, was voting about which patterns from the GOF book (now 10 years old) should be included, removed or revised for a (at this point theoretical) second edition. I won't repeat Martin Fowler's write-up, but rather I'm writing up my reasons for wanting to remove some of the patterns. I should make it clear - I'd like a GOF style book in two volumes, one without these patterns (that I could happily recommend to anyone) and a second volume with these, and other, patterns for people with sufficient experience not to misuse them.
The intent of Singleton is to "Ensure a class only has one instance, and provide a global point of access to it". Martin Fowler pointed out that it is most often used for the "global point of access" rather than the "only has one instance" part. There are at least two problems with having global access to things. One is that it hides dependencies so that it is more difficult to understand how some piece of code works and how different pieces of code affect each other. Another is that it makes it more difficult to substitute the global thing with something else for testing purposes. Rather than have hidden dependencies using globals, the dependency injection approach makes dependencies explicit and easy to substitute for testing. If you really want a "global point of access" type thing, have a look at the Registry pattern.
The problem with a pattern like Singleton being in the GOF book is that people will, and do, use those patterns as a guide to best practice, and the "global point of access" part of Singleton is not (IMHO) good practice.
The intent of Mediator is to "Define an object that encapsulates how a set of objects interact". I don't have a problem with the intent, but rather with how I've seen Mediator used in practice. People use it as an excuse to not think about the responsibilities of objects, and just dump code in something they call a Mediator, resulting in very non object-oriented code. You may think it's unfair of me to object to a pattern because of it's misuse rather than correct use, but as with Singleton, I'd like a book that I can recommend to people where I don't see them use it as an excuse to create a mess. "We didn't know what to do with this code, so we applied the Mediator pattern, which must be good because it's in the GOF book".
(ooohhh - I can almost hear the gasps of disbelief; why could anyone want to remove this beautiful pattern?) The intent of Visitor is to "Represent an operation to be performed on the elements of an object structure". Many people confuse Visitor with "internal iterators". I'll try to explain using an example based on that in the GOF book, implemented in Java. Consider abstract syntax tree sort of thing, with an interface Node, and classes implementing that OperatorNode, NumberNode and ExpressionNode. The tree representing (3*2)+5 (here called "theTree") would be:
Node threeTimesTwo = new ExpressionNode(new NumberNode(3), new OperatorNode("*"), new NumberNode(2));
Node theTree = new ExpressionNode(threeTimesTwo, new OperatorNode("+"), new NumberNode(5));
(Full code provided at the end)
Let's say you want to pretty print this as "((3*2)+5)". Here are four different ways of implementing that:
You could ignore object-oriented programming and hack it together something like:
private static String theLeastOOPrettyPrint(Node root) {
StringBuffer result = new StringBuffer();
if (root instanceof ExpressionNode) {
result.append("(");
result.append(theLeastOOPrettyPrint(((ExpressionNode) root).getLeft()));
result.append(((ExpressionNode) root).getOperator().getOperator());
result.append(theLeastOOPrettyPrint(((ExpressionNode) root).getRight()));
result.append(")");
}
if (root instanceof NumberNode) {
result.append(Integer.toString(((NumberNode) root).getSomeNumber()));
}
if (root instanceof OperatorNode) {
result.append(((OperatorNode) root).getOperator());
}
return result.toString();
}
You could implement it using object-oriented programming as:
private static String theMostOOPrettyPrint(Node root) {
StringBuffer result = new StringBuffer();
root.prettyPrintOnto(result);
return result.toString();
}
and a method on OperatorNode (where operator is the string representation of the operator):
public void prettyPrintOnto(StringBuffer buffer){
buffer.append(operator);
}
and a method on NumberNode (where someNumber is the int represented by this Node):
public void prettyPrintOnto(StringBuffer buffer){
buffer.append(Integer.toString(someNumber));
}
and a method on ExpressionNode (where left, right and operator are the nodes representing the left, right and operator parts of the expression represented by this node. For example, for the ExpressionNode "theTree" defined earlier, left is the ExpressionNode "threeTimesTwo", operator is the OperatorNode representing "+" and right is the NumberNode representing "5"):
public void prettyPrintOnto(StringBuffer buffer){
buffer.append("(");
left.prettyPrintOnto(buffer);
operator.prettyPrintOnto(buffer);
right.prettyPrintOnto(buffer);
buffer.append(")");
}
Another alternative is using an "internal iterator" :
private static String iteratorPrettyPrint(Node root) {
final StringBuffer result = new StringBuffer();
root.each(new NodeInternalIterator(){
public void each(Node node){
node.prettyPrintOnlyYourself(result);
}
});
return result.toString();
}
where the "each" method on the "root" Node takes an instance of NodeInternalIterator and calls it's "each" method with each node in the tree as a parameter. The implementations of the iterating infrastructor are in the code included at the end. The "prettyPrintOnlyYourself" method implementations are the same as the "prettyPrintOnto" except for the case of the ExpressionNode, which becomes slightly trickier because it is now only responsible for it's own representation and not it's composite representation, and because it gets asked for it's representation after it's "children" :
public void prettyPrintOnlyYourself(StringBuffer buffer) {
buffer.insert(0,"(");
buffer.append(")");
}
That is, it now surrounds whatever is already on the buffer with braces.
In the "visitor" implementation, the logic is in the Visitor rather than the Node classes (again, the supporting infrastructor is in the code included at the end). In this case, the "accept" method on the "root" Node takes an instance of NodeVisitor and calls the appropriate "visitXXX" method with each node in the tree as a parameter, i.e. it calls visitOperatorNode for every OperatorNode, visitNumberNode for every NumberNode and visitExpressionNode for every ExpressionNode:
private static String visitorPrettyPrint(Node root) {
final StringBuffer result = new StringBuffer();
root.accept(new NodeVisitor(){
public void visitOperatorNode(OperatorNode node){
result.append(node.getOperator());
}
public void visitNumberNode(NumberNode node){
result.append(Integer.toString(node.getSomeNumber()));
}
public void visitExpressionNode(ExpressionNode node){
result.insert(0,"(");
result.append(")");
}
});
return result.toString();
}
People often call the "internal iterator" a "Visitor", but it isn't really a Visitor according to the GOF definition. A Visitor uses "double dispatch" to call a different method according to the type of node in the tree, in comparison to the "internal iterator" which calls the same method on every node in the tree.
The reason I'd like Visitor to be relegated to a "volume 2" of the GOF book is because it's not very object-oriented and is rather specialised. The logic is in the Visitor rather than the Node classes. I have seen Visitor used when the simple "object-oriented" solution would have been fine. That's not to say I don't see value in Visitor - it's a really neat pattern. There are cases where Visitor is the best choice of implementation, but it really is quite a specialised pattern that I don't think belongs in a "volume 1" of the GOF book. James Noble suggested that "double dispatch" should be included instead of Visitor, as Visitor is just an application of "double dispatch".
I'd like to thank Adewale Oshineye and Stacy Curl for their help with this article.
The full code used in this follows:
Interface Node:
package com.oocode.visitor;
public interface Node {
void prettyPrintOnto(StringBuffer buffer);
void each(NodeInternalIterator nodeIterator);
void accept(NodeVisitor nodeVisitor);
void prettyPrintOnlyYourself(StringBuffer result);
}
Class OperatorNode:
package com.oocode.visitor;
public class OperatorNode implements Node {
private String operator;
public OperatorNode(String operator) {
this.operator = operator;
}
public String getOperator() {
return operator;
}
public void prettyPrintOnto(StringBuffer buffer){
buffer.append(operator);
}
public void prettyPrintOnlyYourself(StringBuffer buffer) {
prettyPrintOnto(buffer);
}
public void each(NodeInternalIterator nodeIterator){
nodeIterator.each(this);
}
public void accept(NodeVisitor nodeVisitor){
nodeVisitor.visitOperatorNode(this);
}
}
Class NumberNode:
package com.oocode.visitor;
public class NumberNode implements Node {
private int someNumber;
public NumberNode(int someNumber) {
this.someNumber = someNumber;
}
public int getSomeNumber() {
return someNumber;
}
public void prettyPrintOnto(StringBuffer buffer){
buffer.append(Integer.toString(someNumber));
}
public void prettyPrintOnlyYourself(StringBuffer buffer) {
prettyPrintOnto(buffer);
}
public void each(NodeInternalIterator nodeIterator){
nodeIterator.each(this);
}
public void accept(NodeVisitor nodeVisitor){
nodeVisitor.visitNumberNode(this);
}
}
Class ExpressionNode:
package com.oocode.visitor;
public class ExpressionNode implements Node {
private Node left;
private OperatorNode operator;
private Node right;
public ExpressionNode(Node left, OperatorNode operator, Node right) {
this.left = left;
this.operator = operator;
this.right = right;
}
public Node getLeft() {
return left;
}
public OperatorNode getOperator() {
return operator;
}
public Node getRight() {
return right;
}
public void prettyPrintOnto(StringBuffer buffer){
buffer.append("(");
left.prettyPrintOnto(buffer);
operator.prettyPrintOnto(buffer);
right.prettyPrintOnto(buffer);
buffer.append(")");
}
public void prettyPrintOnlyYourself(StringBuffer buffer) {
buffer.insert(0,"(");
buffer.append(")");
}
public void each(NodeInternalIterator nodeIterator){
left.each(nodeIterator);
operator.each(nodeIterator);
right.each(nodeIterator);
nodeIterator.each(this);
}
public void accept(NodeVisitor nodeVisitor){
left.accept(nodeVisitor);
operator.accept(nodeVisitor);
right.accept(nodeVisitor);
nodeVisitor.visitExpressionNode(this);
}
}
Interface NodeInternalIterator:
package com.oocode.visitor;
public interface NodeInternalIterator {
void each(Node node);
}
Interface NodeVisitor:
package com.oocode.visitor;
public interface NodeVisitor {
void visitOperatorNode(OperatorNode node);
void visitNumberNode(NumberNode node);
void visitExpressionNode(ExpressionNode node);
}
Class PrettyPrint, which is where the different implementation techniques are used (a bit ugly, but adequate for my purposes):
package com.oocode.visitor;
public class PrettyPrint {
public static void main(String args[]) {
Node threeTimesTwo = new ExpressionNode(new NumberNode(3), new OperatorNode("*"), new NumberNode(2));
//the root node represents (3*2)+5
Node root = new ExpressionNode(threeTimesTwo, new OperatorNode("+"), new NumberNode(5));
// should produce ((3*2)+5)
System.out.println(theLeastOOPrettyPrint(root));
System.out.println(theMostOOPrettyPrint(root));
System.out.println(iteratorPrettyPrint(root));
System.out.println(visitorPrettyPrint(root));
}
private static String theLeastOOPrettyPrint(Node root) {
StringBuffer result = new StringBuffer();
if (root instanceof ExpressionNode) {
result.append("(");
result.append(theLeastOOPrettyPrint(((ExpressionNode) root).getLeft()));
result.append(((ExpressionNode) root).getOperator().getOperator());
result.append(theLeastOOPrettyPrint(((ExpressionNode) root).getRight()));
result.append(")");
}
if (root instanceof NumberNode) {
result.append(Integer.toString(((NumberNode) root).getSomeNumber()));
}
if (root instanceof OperatorNode) {
result.append(((OperatorNode) root).getOperator());
}
return result.toString();
}
private static String theMostOOPrettyPrint(Node root) {
StringBuffer result = new StringBuffer();
root.prettyPrintOnto(result);
return result.toString();
}
private static String iteratorPrettyPrint(Node root) {
final StringBuffer result = new StringBuffer();
root.each(new NodeInternalIterator(){
public void each(Node node){
node.prettyPrintOnlyYourself(result);
}
});
return result.toString();
}
private static String visitorPrettyPrint(Node root) {
final StringBuffer result = new StringBuffer();
root.accept(new NodeVisitor(){
public void visitOperatorNode(OperatorNode node){
result.append(node.getOperator());
}
public void visitNumberNode(NumberNode node){
result.append(Integer.toString(node.getSomeNumber()));
}
public void visitExpressionNode(ExpressionNode node){
result.insert(0,"(");
result.append(")");
}
});
return result.toString();
}
}
I enjoyed the talk on Find Bugs at OOPSLA 2004. Find Bugs is a useful, practical and pragmatic tool produced by David Hovemeyer, Bill Pugh and others at the University of Maryland.
It is much like a style checker but with rules that find things that are probably bugs. It's a very pragmatic, and simple, approach. It is somewhat reminiscent of SmallLint (for Smalltalk). The bug patterns that Find Bugs looks for are based on bugs that the Find Bugs developers have found in real code. In their talk, they presented figures of using Find Bugs on the JDK1.5 code base - it identified many potential bugs.
I tried Find Bugs on one of my open source projects, Jester. Mostly, the things it found weren't things that worry me too much - it identified my sloppy coding where streams won't be closed if an exception is thrown, which I'll probably fix some time. What pleased me most was that it found a couple of fields that I can delete (not bugs), and I do love deleting code.