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)
}
}