Java: The programming tool of choice for discriminating hackers

In spite of all the Java bashing that's so in vogue this days, Team Smartass won the ICFP Programming Contest using Java, giving bragging rights to say that Java is "The programming tool of choice for discriminating hackers".
while(tongue in cheek){
take(this);
(lisp (snobs all))
fuctional_programing = Maybe[zealots]
ruby('fanboys')
}
Another proof of what matters is not the tool, is how you use it...

State machines using "Fluent interfaces/ DSL" in Java

I always found state machines very useful for describing particular aspects of object behavior. A classic example can be a shopping order: it can be "pending","in progress", "shipped", etc.
In my previous project, I started with a simple design using a transition matrix. I must confess it didn't work well. It was hard to explain and it grew more complex as new requirements were added. I though it would be simpler if I didn't use any "fancy OO stuff" and advanced idioms. I've should know better!
This time I wanted to try something different, and based in my previous experiments with internal DSLs with Scala and my (very limited) knowledge of the patters to achieve that in java, I just went ahead and tried to come up with something useful and understandable. This time seems to be working: although it has some "magic" behind curtains is only in the creation and is very easy to add or modify the configuration class for new or updated states and events. Other members of my project were able to add and remove states and transitions with only a brief explanation.

The basic classes are pretty simple: State and Event.

package statemachine;

public class Event {

final private String label;

public Event(String newLabel){

label=newLabel;

}

/**

* @return Returns the label.

*/

public String getLabel() {

return label;

}

public String toString(){

return label;

}

}

package statemachine;

import java.util.HashMap;

import java.util.Map;

public class State {

private final String label;

private final Map<Event,Transition> transitions= new HashMap<Event,Transition>();

//no public access to the constructor, must be in the same package

State(String newLabel){

this.label=newLabel;

}

void addTransition(Transition t){

transitions.put(t.getEvent(),t);

}

public State doEvent(Event e){

return (transitions.get(e)).getDestination();

}

/**

* @return Returns the label.

*/

public String getLabel() {

return label;

}

/**

* @return Returns the transitions.

*/

public Map<Event,Transition> getTransitions() {

return transitions;

}

}

You send a event to a sate and it returns the next state:
State newState=state.doEvent(event);
The State class holds a map of [event->state] (with the Transition class in the middle, for added effect :) )
As an extra safety measure, the State constructor and the addTransition method is accessible only to the package (well, unless you subclass it)
The "fluency" is provided by the Transition class (the useful methods return this to allow method chaining), so you can write:
new Transition(event).from(origin).to(destination)

package statemachine;

class Transition {

private State origin,destination;

private Event event;

public Transition(Event e){

event=e;

}

public Transition from(State orig){

origin=orig;

origin.addTransition(this);

return this;

}

public Transition to(State dest){

destination=dest;

return this;

}

/**

* @return Returns the destination.

*/

public State getDestination() {

return destination;

}

/**

* @return Returns the event.

*/

public Event getEvent() {

return event;

}

/**

* @return Returns the origin.

*/

public State getOrigin() {

return origin;

}

}

How this will look? Suppose you have a pretty simple FSM:















Using the previous pseudoDSL/Fluent interface will look like:

package statemachine;

public class FSMDef {

public final static State SUBMITTED=new State("Submitted");

public final static State OPEN= new State("Open");

public final static State CANCELLED= new State("Cancelled");

public final static State CLOSED= new State("Closed");

//Events

static class Events {

public final static Event OPEN = new Event("Open");

public final static Event CLOSE = new Event("Close");

public final static Event REOPEN = new Event("Re-Open");

public final static Event CANCEL = new Event("Cancel");

}

static {

new Transition(Events.OPEN).from(SUBMITTED).to(OPEN);

new Transition(Events.CLOSE).from(OPEN).to(CLOSED);

new Transition(Events.REOPEN).from(CLOSED).to(OPEN);

new Transition(Events.CANCEL).from(OPEN).to(CANCELLED);

}

}

Doesn't seems too complex, right?
I'm just starting with this, and probably barely skim the surface (sure it has some drawbacks), but so far it worked :)

[EDIT: Fixed the generics declarations that were eaten by the HTML format. BTW, if anybody knows a good code formatter for blog posts, let me know ]

Scala: fold/reduce cheatsheet

My fold/reduce 'cheat sheet' is something like:

For the list (a,b,c,d) fold/reduce is:

reduceLeft(f) => f(f(f(a,b),c),d)

foldLeft(Z)(f) => f(f(f(f(Z,a),b),c),d)

("applies the function from the left")


reduceRight(f) => f(a,f(b,f(c,d)))

foldRight(Z)(f) => f(a,f(b,f(c,f(d,Z))))

("applies the function from the right")

[EDIT: as you see, fold and reduce are essentially the same, but fold starts with an outside element ]

Questions, only questions

Today I'm full of questions. Software development and programming is hard. Is a close encounter with layers and layers of complexity. Once we master one level, we open a whole new level. To tackle it one must employ multiple techniques. But they always involve trade-offs. How to balance programming using standard and maybe cumbersome idioms vs more elegant but more obscure idioms? What if the programming style is too personal and strange to others? Shall we settle for the lowest common denominator ? How do we balance the conflict between something harder to understand at first but easier to extend and maintain against something more familiar but with exponential complexity growth after each change? How do we maintain the "conceptual integrity" (F. Brooks) through the life of the system? As the project complexity grows, the need for sophisticated techniques increases. (I'm coming to the conclusion that if a developer can't comprehend some level of complexity, shouldn't be allowed to participate in the project without close mentoring). Refactoring is necessary because entropy. Every code base starts to degrade and loose integrity as evolves. I wonder if there's a code entropy metric... At what point a refactoring is good enough? When do you stop? At least your architecture should be stable, or you didn't validate it. I guess complexity is in the eye of the beholder. I found that a system composed of smaller simple pieces with complex interactions is easier to evolve than bigger pieces with simple interactions because each piece is internally complex and the limited interactions means its harder to combinate them in new ways. Of course, gratuitous complexity should be avoided at all costs. Sometimes I look for a "zen" approach to coding. At the end, I always take a pragmatic approach and find a trade-off that balances the forces. Isn't coding about that? Each line you write is a choice you need to make... At some point we need to use "introspection" and "metaprogramming" but not the programming techniques: introspection on how we approach problem solving and programming and metaprogramming on what we can do to program better.

Playing with Scala 4: Abstract types and Self-types

Thanks to the scala mailing list, and to Eric, I have a satisfying enough model of a graph to be used by the Dijkstra's algorithm.
(well, there already was a generic graph and directed graph written in Scala... talking about reinventing the wheel!. The solution in Eric's comment works great too... is almost the same, but he was faster than me on coming up with it :D )
http://www.scala-lang.org/intro/abstracttypes.html
http://www.scala-lang.org/intro/selfrefs.html
I just used the same code, and changed the nodes and edges to use sets instead of lists (really, we don't care about the order)
The Scala example of Graph uses abstract types: it declares type Node and type Edge as type "parameters" to be defined by concrete implementation. Even more, by declaring type Node <: NodeIntf, we're restricting Node to be subtypes of NodeIntf. The declaration "self: Node =>" tells "I'll use self as Node type"
Then I declared the trait Weighted and extended the class DirectedGraph adding my extensions to NodeImpl and EdgeImpl to use weighted trait and add the node label and the previous property. I had to add a collection of the adjacent arcs, because they weren't in the original Graph and is easier for the algorithm. I overrode the connectWith method to keep track of the adjacent arcs as they're added, also I defined our --> operator to call the connectWith method.

class DfsNode extends NodeImpl with Weighted {

var previous: DfsNode = _
var label:String = _
var nodeEdges: Set[Edge] = Set()

override def connectWith(node: Node): Edge = {
val newEdge=super.connectWith(node)
nodeEdges = nodeEdges + newEdge
newEdge
}

def -->(n2:Node):DfsEdge =connectWith(n2)

override def toString()= label+ " w:"+weight

}

Edges are simpler, just add the weight and override toString:
class DfsEdge(origin:Node, dest:Node) extends EdgeImpl(origin, dest) with Weighted {
override def toString()= from.label+"-->"+to.label+" w:"+weight
}

All are enclosed in the DfsGraph class extending the DirectedGraph class, now I can assign the concrete types for Node and Edge:
type Node= DfsNode
type Edge= DfsEdge

The DirectedGraph class has a addNode method. To keep the DSL-ish quality of the construction of the graph, I added the method addNewNode to take the node label as parameter
def addNewNode(l:String):Node={
val newNode=super.addNode
newNode.label=l
newNode
}

So we can write: graph addNewNode "nodeLabel".

The example looks like this:

object Example extends Application {

val graph = new DfsGraph

val n1=graph addNewNode "start"
val n2=graph addNewNode "n2"
val n3=graph addNewNode "n3"
val n4=graph addNewNode "n4"
val n5=graph addNewNode "n5"
val n6=graph addNewNode "end"

n1-->n2 weight=2
n1-->n3 weight=1
n2-->n4 weight=1
n3-->n4 weight=3
n2-->n5 weight=1
n4-->n6 weight=1
n5-->n6 weight=3

graph.shortestPath(n1,n6)
println("Path")
graph.pathToStart(n6).reverse.map(println(_))

}

Pretty easy to read, don't you think?
In the next post, I'll show you how we can use this algorithm to solve the "Abbott's revenge" type of maze. Ideally, I want to create an interpreter for the input, exploring Scala's features for creating language interpreters.
Here is the complete code:

package dfs2;

abstract class Graph {
type Edge
type Node <: NodeIntf
abstract class NodeIntf {
def connectWith(node: Node): Edge
}
def nodes: Set[Node]
def edges: Set[Edge]
def addNode: Node
}

abstract class DirectedGraph extends Graph {
type Edge <: EdgeImpl
class EdgeImpl(origin: Node, dest: Node) {
def from = origin
def to = dest
}

class NodeImpl extends NodeIntf {
self: Node =>
def connectWith(node: Node): Edge = {
val edge = newEdge(this, node)
edges = edges + edge
edge
}
}

protected def newNode: Node
protected def newEdge(from: Node, to: Node): Edge

var nodes: Set[Node] =Set()
var edges: Set[Edge] =Set()
def addNode: Node = {
val node = newNode
nodes = nodes + node
node
}
}

trait Weighted {
var weight= Float.PositiveInfinity
}
class DfsGraph extends DirectedGraph {
class DfsNode extends NodeImpl with Weighted {
var previous: DfsNode = _
var label:String = _
var nodeEdges: Set[Edge] = Set()

override def connectWith(node: Node): Edge = {
val newEdge=super.connectWith(node)
nodeEdges = nodeEdges + newEdge
newEdge
}

def -->(n2:Node):DfsEdge =connectWith(n2)

override def toString()= label+ " w:"+weight
}

class DfsEdge(origin:Node, dest:Node) extends EdgeImpl(origin, dest) with Weighted {
override def toString()= from.label+"-->"+to.label+" w:"+weight
}

def addNewNode(l:String):Node={
val newNode=super.addNode
newNode.label=l
newNode
}

type Node= DfsNode
type Edge= DfsEdge

protected def newEdge(from: Node, to: Node): Edge = new DfsEdge(from,to)
protected def newNode: Node = new DfsNode

def shortestPath(start: DfsNode, end: DfsNode) = {
var unvisited=nodes
start.weight=0
while (!unvisited.isEmpty) {
val vertx=min(unvisited)
vertx.nodeEdges.map(improveDistance(_))
unvisited=unvisited-vertx
}
}

def improveDistance(a:Edge) ={
if (a.from.weight+a.weight< a.to.weight) {
a.to.weight=a.from.weight+a.weight
a.to.previous=a.from
}
}

def min(nodes: Set[DfsNode]): DfsNode = {
nodes.reduceLeft((a:DfsNode,b:DfsNode)=>if (a.weight<b.weight) a else b )
}

def pathToStart(end:DfsNode):List[DfsNode] = {
if (end == null)
Nil
else
end :: pathToStart(end.previous)
}
}