Personal tools
You are here: Home Members martin Martins Weblog Family Polymorphism in Scala
Document Actions
  • Print this page
  • Add Bookmarklet

Family Polymorphism in Scala

How to keep types together for a set of associated types.

Today I have experimented with abstract types in Scala. Abstract types are types references that will be defined by subclasses.

The example

As an interesting exercise I found the graph example in the "Family Polymorphism" paper by Erik Ernst (2001). He defines two kinds of graphs, one ordinary and one with edges that can be disabled. For those that are too lazy to dig through the paper, one of the problems discussed is how to define a polymorphic message on edges without drilling holes into type safety and without hurting reusability by introducing massive C++ templating.

I use abstract types to define a type structure for Graphs with Nodes and Edges. This structure is then refined in two concrete sets of implementations. The interesting point is, that Scala allows me to avoid mixing up the types from the different implementations.

abstract class Graph {
type Node <: AbstractNode
type Edge <: AbstractEdge

def mkNode() : Node
def connect(n1: Node, n2: Node) : Edge

abstract class AbstractEdge(val n1: Node, val n2: Node)

trait AbstractNode {
def touches(edge: Edge): Boolean = edge.n1 == this || edge.n2 == this
}
}

Graph is the abstract definition of the structure. It contains abstract types for the Nodes and Edges, and Node and Edge factory methods, as well as the method touches, which will be redefined polymorphically for the "disabled edges" kind of graph below.

  class BasicGraph extends Graph {
type Node = BasicNode
type Edge = BasicEdge
protected class BasicNode extends AbstractNode
protected class BasicEdge(n1:Node, n2:Node) extends AbstractEdge(n1, n2)

def mkNode() = new BasicNode
def connect(n1: Node, n2: Node) : BasicEdge = new BasicEdge(n1, n2)
}

Nothing special for BasicGraph: It just contains concrete classes for the Nodes and Edges and defines corresponding factory methods.

  class OnOffGraph extends Graph {
type Node = OnOffNode
type Edge = OnOffEdge
protected class OnOffNode extends AbstractNode {
override def touches(edge: Edge): Boolean = edge.enabled && super.touches(edge)
}
protected class OnOffEdge(n1:Node, n2:Node, var enabled: Boolean) extends AbstractEdge(n1, n2)
def mkNode() = new OnOffNode
def connect(n1: Node, n2: Node) : OnOffEdge = new OnOffEdge(n1, n2, true)

}

OnOffGraph has the extension to provide for disabled edges. Note that the method OnOffNode.touches can be defined without the need to downcast the edge, because the abstract type Edge is defined to be an OnOffEdge in OnOffGraphs. The type system ensures that you cannot have a BasicEdge connected to OnOffNodes, so we are safe here!

Following some testing code:

    val g = new BasicGraph
val n1 = g.mkNode()
val n2 = g.mkNode()
val e = g.connect(n1,n2)
assert(n1 touches e)
assert(n2 touches e)
val g2 = new BasicGraph
// g2.connect(n1,n2) // ERROR: can't link to node of other graph

The way BasicGraphs are defined also prevents edges across graphs (Node and Edge are "path-dependent types"). Whether this is desired depends on the context; one could define a super class and an OuterEdge parallel to BasicEdge that would allow to span different graphs.

    val og = new OnOffGraph
val on1 = og.mkNode()
val on2 = og.mkNode()
val oe = og.connect(on1, on2)
// val mixed = og.connect(n1, n2) // ERROR: og.connect not applicable to g.Node

assert(on1 touches oe)
assert(on2 touches oe)
// println(on2 touches e) // ERROR: on2.touches not applicable to g.Edge
oe.enabled = false;
assert (! (on2 touches oe), "After disabling, edge virtually has gone")
assert (! (on1 touches oe), "After disabling, edge virtually has gone")

As desired, edges can be disabled for OnOffGraphs and the different node types are not compatible such that attempts to disable BasicEdges or to access an "enabled" field via runtime type BasicEdge are statically prevented.

    def addSome(graph: Graph): Graph#Edge = {
val n1, n2 = graph.mkNode()
graph.connect(n1,n2)
}

val e2 = addSome(g)
val oe2 = addSome(og)
// oe2.enabled = false // type OnOffGraph not retained, graph.Edge not possible
()

It is still possible to write code in terms of unspecific Graphs. In the current Scala implementation it is not possible to refer to a path-dependent type starting at a method parameter. Therefore, when the addSome method is applied to an OnOffGraph, the information that the result is always an OnOffEdge, is not retained by the type system. But you can get near that by making addSome generic:

def addSome[G <: Graph](graph: G): G#Edge = {
val n1, n2 = graph.mkNode()
graph.connect(n1,n2)
}

val e2 = addSome(g)
val oe2 = addSome(og)
oe2.enabled = false // now OK.


Conclusion

The possibility to define related types in a way similar to the one above enables the programmer to retain more static type information and certainly reduces the number of required casts. This is most probably also applicable for product / customization scenarios where multiple related classes have to be extended in a compatible way.

_____
tags:
Tuesday, January 20, 2009 in Programming Languages  | Permalink |  Comments (0)

Powered by Plone CMS, the Open Source Content Management System

This site conforms to the following standards: