1/23/08

Playing with Scala 3: OO, Traits, and Views

OO

Look at graph classes my previous post:

class Node (val label:String) {
var transitions: List[Arc] = Nil
var previous: Node = _
var weight= Float.PositiveInfinity
var visited = false
...

and

class Arc(var start: Node, var end: Node) {
var weight: Float = _
...
Don't you feel that something doesn't really fit? What are previous, visited, and weight are doing in Node? And weight in Arc?

Those properties doesn't really belong to a generic Node or Arc, they're specific for our algorithm. So, why having them there? Let's put those attributes on special cases of Node and Arc: DfsNode and DfsArc. But wait! Putting weight in both doesn't seem right either... we're defining the same thing twice! Weight is some kind of "cross-cutting" attribute.

Traits

Luckily modern OO languages had a very elegant way of solving this kind of problems by means of traits (usually are described as "interfaces with implementation" but a very powerful concept), so let's define our weight as a trait:

trait Weighted {
var weight= Float.PositiveInfinity
}

So we can clean our Node and Arc classes:

class Node(val label:String) {
var transitions: List[Arc] = Nil

override def toString()= {
label
}

def --> (end: Node):Arc={
transitions = new Arc(this,end) :: transitions
transitions.head
}
}

class Arc(var start: Node, var end: Node) {

override def toString()= {
start.label+"-->"+end.label
}
}

Now they look useful for any graph application, and we can define our particular versions for the Dfs algorithm:

class DfsNode (label:String) extends Node(label) with Weighted {
var previous: DfsNode = _
var visited = false

override def toString()= {
super.toString+" w:"+weight+" p:"+previous
}
}

class Arc(var start: Node, var end: Node) {
override def toString()= {
start.label+"-->"+end.label
}
}

And I just need to change the signatures of the functions of the algorithm:

object Dijkstra {

def shortestPath(graph:Set[DfsNode], start: DfsNode, end: DfsNode) = {
var unvisited=graph
start.weight=0
while (!unvisited.isEmpty) {
val vertx=min(unvisited)
vertx.transitions.map(improveDistance(_))
unvisited=unvisited-vertx
}
}

def improveDistance(a:DfsArc) ={
if (a.start.weight+a.weight< a.end.weight) {
a.end.weight=a.start.weight+a.weight
a.end.previous=a.start
}
}

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

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

What? It doesn't compile! node.transitions returns a list of Nodes and not DfsNodes! Argh! We've been bitten by the static typing! ("Ha-ha" will shout the Dynamic typing Nelson). I could use a .asInstanceOf[type] everywhere (like a Java cast) but it looks like a kludge and you have to put everywhere! There must be a better solution, after all, Scala is supposed to look elegant, right?

Views (implicit conversions)

Scala has a very interesting way of dealing with that kind of problem: by creating views using implicit conversions, we can convert from one type to other, the compiler will insert the appropriate call when needed. So I defined a conversion from Arc to DfsArc and Node to DfsNode:

object Implicits {
implicit def node2DfsNode(node:Node):DfsNode={
if (node.isInstanceOf[DfsNode])
node.asInstanceOf[DfsNode]
else {
var dfsNode=new DfsNode(node.label)
dfsNode.transitions=node.transitions
dfsNode
}
}

implicit def arc2DfsArc(arc:Arc):DfsArc={
if (arc.isInstanceOf[DfsArc])
arc.asInstanceOf[DfsArc]
else {
new DfsArc(arc.start,arc.end)
}
}
}

And now, everything will happly compile. The only caveat is as I defined the method --> returning an Arc and arc2DfsArc creating a new instance if I pass an Arc, the use of n1-->n2 weight=2 sets the weight in a new object and not in the object in the transitions collection. I'm sure there's a better solution, but meanwhile if we overrride the --> method in DfsNode will work:
def --> (end: DfsNode):DfsArc={
transitions = new DfsArc(this,end) :: transitions
transitions.head.asInstanceOf[DfsArc]
}

(Let me know if you want the full code posted)

10 comments:

Eric said...

Hi Gabriel,

I don't know for sure but I think that you could avoid to define implicit defs by using type declarations like the ones described in this paper:

http://lamp.epfl.ch/~odersky/papers/ScalableComponent.pdf (look at the Observer case study for instance).

Please post your findings if you discover that there is a more elegant solution indeed.

I'll give it a try if I can find some time.

Eric.

yolio said...

i think you forgot the DfsArc class in your post

Unknown said...

@Eric
I'll take a look, I'm still not totally satisfied with my solution.

@Mr Carriata
Opss... you're right!
Here it is:

class DfsArc(start: DfsNode,end: DfsNode) extends Arc(start,end) with Weighted {
override def toString()= {
super.toString+" w:"+weight
}
}

Thanks a lot for noticing it!

Eric said...

Hi Gabriel,

I suffered a bit to find a working solution, though I'm not persuaded it's the best (at least it compiles):


// Graph is a Trait, defining Arc and Node abstractly as related with each other
trait Graph {
type A <: Arc
type N <: Node
abstract class Node {
def --> (end: N): A
}
class Arc(start: N, end: N)
}

// Here I extracted the creation of a new Arc from 2 Nodes as an abstract method
trait SimpleGraph extends Graph {
type N <: SNode
type A <: SArc
def newArc(start: N, end: N): A

// Note that SNode has to use the self-type N to be used in the newArc creation method
class SNode(val label:String) extends Node { self: N =>
var transitions: List[A] = Nil
override def toString()= label

def --> (end: N): A = {
transitions = newArc(this, end) :: transitions
transitions.head
}
}

class SArc(val start: N, val end: N) extends Arc(start, end) {
override def toString() = start.label + "-->" + end.label
}
}

// This object provides the simple implementation of Nodes and Arcs by "fixing" the types N and A
// and defining the newArc creation method
object SimpleGraph extends SimpleGraph {
type N = SNode
type A = SArc
def newArc(start: N, end: N) = new SArc(start, end)
}

// This is the weighted version of the graph
class DfsGraph extends SimpleGraph {
type N = DfsNode
type A = DfsArc
def newArc(start: N, end: N) = new DfsArc(start, end)
class DfsNode(override val label:String) extends SNode(label) with Weighted {
var previous: DfsNode = _
var visited = false
override def toString() = super.toString+" w:"+weight+" p:"+previous
}

class DfsArc(override val start: N, override val end: N) extends SArc(start, end) with Weighted

trait Weighted {
var weight= Float.PositiveInfinity
}
}

object Dijkstra extends DfsGraph {
def shortestPath(graph: Set[DfsNode], start: DfsNode, end: DfsNode) = {
var unvisited = graph
start.weight = 0
while (!unvisited.isEmpty) {
val vertx = min(unvisited)
vertx.transitions.map(improveDistance(_))
unvisited=unvisited-vertx
}
}

def improveDistance(a: DfsArc) = {
if (a.start.weight + a.weight < a.end.weight) {
a.end.weight = a.start.weight + a.weight
a.end.previous = a.start
}
}

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

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

Eric.

Unknown said...

Wow, thanks a lot, Eric. :)
I thought on overriding newArc(this, end), but I was trying to escape from adding flexibility from the begining :D.
But is a good application for type declarations, because the problem we're trying to solve is in fact a "family polymorphism" (and my OO side shouted "abstract factory!"). The good thing is the small extra step used for defining the type declarations pretty much guarantees the type safety of the extensions.
Later I'll take a closer look, this deserves another post :)
(I'm gladly surprised of how much I'm learning from the "simple" Dfs example)

Eric said...

Hi Gabriel,

Thanks to the Scala mailing list, I discovered a similar example on the Scala-lang
site


Eric.

Anonymous said...

Hi gabriel

Just read your blog ..i was wondering if i could get any help in developing php projects using eclipse. Or any source or references you can suggest me.

Unknown said...

Have you tried http://www.eclipse.org/pdt/ ?

Unknown said...
This comment has been removed by a blog administrator.
Anonymous said...
This comment has been removed by a blog administrator.