Trait

From APIDesign

Revision as of 19:57, 2 September 2012

Trait is a delta - a difference - that you can mix-in when using modern OOP languages when creating your own class. Traits are frequently present in Scala.

Is C better than C++?

Recently I've noticed an interesting article describing why C is more effective than C++ and in general most of OOP languages. The article is well written and for a while I was nodding in an agreement. The claim that by using OOP and insisting on encapsulation one cannot implement linked list as effectively as in C is very good one!

However later I realized that the take on OOP is really targeted to OOP languages of the past. In modern languages, like Scala one can keep encapsulation and still be as effective as the old plain good C. As Martin Odersky once put it: there used to be a time when people were arguing whether we need goto statement to effectively find a particular number in a matrix. Those days are gone - we can focus on new problems. The same applies to effective and encapsulated list problem. I am not a Scala expert, but I knew its type system is powerful enough. It took me few hours to re-learn Scala, but finally I created the code...

Encapsulated List

To create as effective list as presented in C in the article one needs an orchestration between the list class and its elements. Fine, let's achieve that with traits. First of all define the prev and next pointers each type willing to participate in a list needs to provide:

Code from Listable.scala:

trait Listable[T] {
  private[effectivelist] var prev : T = _
  private[effectivelist] var next : T = _
}
 

Then we can create a list that operates on top of such items:

Code from List.scala:

final class List[T <: Listable[T]] {
  private var item : T = _
  private final var EMPTY : T = _
 
  final def get(index : Int) : T = {
    var pos : T = item;
    for (i <- 1 to index) {
      pos = pos.next;
      if (pos == item) {
        throw new IndexOutOfBoundsException()
      }
    }
    return pos
  }
 
  final def size() : Int = {
    if (item == EMPTY) {
      return 0
    }
    var size = 0
    var pos : T = item
    do {
      size = size + 1
      pos = pos.next
    } while (pos != item)
    return size
  }
 
  final def add(toAdd : T) : Boolean = {
    if (toAdd.prev != EMPTY) {
      return false
    }
 
    if (item == null) {
      item = toAdd
      toAdd.next = toAdd
      toAdd.prev = toAdd
      return true
    } else {
      toAdd.prev = item.prev
      item.prev.next = toAdd
      item.prev = toAdd
      toAdd.next = item
      return true
    }
  }
  final def remove(toRemove : T) : Boolean = {
    if (toRemove.prev == EMPTY) {
      return false
    } else {
      toRemove.prev.next = toRemove.next
      toRemove.next.prev = toRemove.prev;
      if (item.next == item) {
        item = EMPTY
      }
      if (item == toRemove) {
        item = toRemove.next
      }
      toRemove.next = EMPTY
      toRemove.prev = EMPTY
      return true
    }
  }
}
 

Please note that the definition of item is using private access modifiers giving access only to the list implementation. So the encapsulation is guaranteed (so OOP principles are kept). Of course, given the implementation is a one-to-one copy of the C list, it is going to be as effective as the C one. Here is a sample usage:

Code from ListTest.scala:

case class Person(name : String, age : Int) extends Listable[Person]
 
var list : List[Person] = _
var p1, p2, p3, p4 : Person = _
 
@Before def initializeListAndValues: Unit = {
  list = new List[Person]
  p1 = new Person("Jarda", 39)
  p2 = new Person("Sona", 37)
  p3 = new Person("Anna", 7)
  p4 = new Person("Ondra", 6)
}
 
@Test def tryFewAdditions = {
  assertTrue(list.add(p1))
  assertTrue(list.add(p2))
  assertTrue(list.add(p3))
  assertTrue(list.add(p4))
 
  assertEquals("Jarda was inserted first", "Jarda", list.get(0).name)
  assertEquals("Sona was inserted 2nd", 37, list.get(1).age)
  assertEquals("Anna was inserted 3rd", "Anna", list.get(2).name)
  assertEquals("Anna was inserted 4th", 6, list.get(3).age)
}
 

Please note that there is no cast, everything is typed correctly, thanks to Scala's flexible type system. Good achievement, Scala guys! Of course some may say that it is ugly every class that one wants to use in the effective list needs to inherit from the Listable trait. What should one do when the type has been written by somebody else and does not inherit from Listable? Can one put following class into a list?

Code from ListMixinTest.scala:

class Point(val x: Int, val y : Int);
 

In fact, it is more than easy thanks to Scala's implicit conversion methods. One can create a subtype that mixes in the Point as well as Listable and define an implicit method that converts from Point to ListablePoint. Then one can basically store Points in a list:

Code from ListMixinTest.scala:

class ListablePoint(x: Int, y: Int)
extends Point(x,y) with Listable[ListablePoint] {
  def this(r : Point) = this(r.x, r.y)
}
implicit def toList(p : Point) : ListablePoint = new ListablePoint(p)
 
@Test def useThePlainOldPointInList : Unit = {
  val list = new List[ListablePoint]
  list.add(new Point(10, 20))
  assertEquals("One element", 1, list.size)
  assertEquals("X is 10", 10, list.get(0).x)
  assertEquals("y is 20", 20, list.get(0).y)
}
 

This is a nice example showing how much the OOP technology progressed during last two decades. Thanks Scala for moving the OOP further.

Can this be done in C++?

One question remains: Can this be emulated in C++? Mixins are inherently present in C++ as the language supports multiple inheritance. Implicit conversions are indeed there, so the only question is whether one can type this correctly without using casts. My early 90ties knowledge of C++ would suggest, one needs casts, but maybye the C++ changed meanwhile with a hope to keep with progress of OOP made meanwhile. Anyone knows?