Sunday, January 10, 2010

A Case for Orthogonality in Design

In Learning, using and designing command paradigms, John M Carroll introduces the notion of lexical congruence. When you design a language, one of the things that you do is lexicalization of the domain. If we extrapolate the concept to software designs in general, we go through the same process with our domain model. We identify artifacts or lexemes and choose to name them appropriately so that the names are congruent with the semantics of the domain. This notion of lexical congruence is the essence of having a good mnemonics for your domain language. I found the reference to Carroll's work in Testing the principle of orthogonality in language design, which discusses the same issue of organizing your language around an optimal set of orthogonal semantic concepts. This blog post tries to relate the same concepts of orthogonality in designing domain models using the power that the newer languages of today offers.

The complexity of a modeling language depends on the number of lexemes, their congruence with the domain concepts being modeled and the number of ways you can combine them to form higher order lexemes. The more decoupled each of these lower level lexemes are, the easier they are to compose. When you have overlapping concepts being modeled as part of lexemes, the mixing is not easy. You need to squeeze in some special boundary conditions as part of composition logic. Making your concepts independent yet composable makes your design orthogonal.

The first time I came across the concept of orthogonality in design and consciously appreciated the power of unification that it brings on to your model, is through Andrei Alexandrescu's idea of policy based design that he evangelized in his book Modern C++ Design and in the making of the Loki library. You have orthogonal policies that are themselves reusable as independent abstractions. And at the same time you can use the language infrastructure to combine them when composing your higher order model. Consider this C++ example from Andrei's book ..

template<  class T,  template <class> class CheckingPolicy,  template <class> class ThreadingModel>class SmartPtr;
CheckingPolicy enforces constraints that need to be satisfied by the pointee object. The ThreadingModel abstraction defines the concurrency semantics. These two concerns are not related in any way between themselves. But you can use the power of C++ templates to plug in appropriate behaviors of these concerns when composing your own custom type of SmartPtr ..

template SmartPtr<Widget, NoChecking, SingleThreaded>  WidgetPtr;
This is orthogonal design where you have a minimal set of lexemes to model otherwise unrelated concerns. And use the power of C++ templates to evolve a larger abstraction by composing them together. The policies themselves are independent and can be applied to construct arbitrary families of abstraction.

The crux of the idea is that you have m concepts that you can use with n types. There's no static relationship between the concepts and the types - that's what makes orthogonality an extensible concept. Consider Haskell typeclasses ..

class Eq a where   (==) :: a -> a -> Bool
The above typeclass defines the concept of equality. It's parameterized on the type and defines the constraint that the type as to define an equality operator in order to qualify itself as an instance of the Eq typeclass. The actual type is left open which gives the typeclass an unbounded extensibility.

For integers, we can do

instance Eq Integer where   x == y =  x integerEq y
For floats we can have ..

instance Eq Float where   x == y =  x floatEq y
We can define Eq even for any custom data type, even recursive types like Tree ..

instance (Eq a) => Eq (Tree a) where   Leaf a         == Leaf b          =  a == b  (Branch l1 r1) == (Branch l2 r2)  =  (l1==l2) && (r1==r2)  _              == _               =  False
Haskell typeclasses, like C++ templates help implement orthogonality in abstractions through a form of parametric polymorphism. Programming languages offer facilities to promote orthogonal modeling of abstractions. Of course the power varies depending on the power of abstraction that the language itself offers.

Let's consider a real world scenario. We have an abstraction named Address and modeled as a case class in Scala ..

case class Address(no: Int, street: String,                    city: String, state: String, zip: String)
There can be many contexts in which you would like to use the Address abstraction. Consider printing of labels for shipping that needs your address to be printed in some specific label format, as per the following trait ..

trait LabelMaker {  def toLabel: String}
Note that printing addresses in the form of labels is not one of the primary concerns of your Address abstraction. Hence it makes no sense to model it as one of the methods of the class. It's only required that in some situations we may need to use the Address to print itself in the form of a label as per the specification mandated by LabelMaker.

One other concern is sorting. You may need to have your addresses sorted based on zip code before submitting them to your Printer module for shpping. Sorting may be required in combination with label printing or as well as on its own - these two are orthogonal concerns that should never have any dependence amongst themselves within your abstraction.

Depending on your use case, you can decide to compose your Address abstraction as

case class Address(houseNo: Int, street: String,   city: String, state: String, zip: String)  extends Ordered[Address] with LabelMaker {  //..}
which makes your Address abstraction statically coupled with the other two.

Or you may like to make the composition based on individual objects which would keep the base abstraction independent of any static coupling.

val a = new Address(..) with LabelMaker {  override def toLabel = {    //..  }}
As an alternative you can also choose to implement implicit conversions from Address using Scala views ..

object Address {  implicit def AddressToLabelMaker(addr: Address) = new LabelMaker {    def toLabel =      "%d-%s, %s, %s-%s".format(        addr.houseNo, addr.street, addr.city, addr.state, addr.zip)  }}
Whatever be the implementation, take note of the fact that we are not polluting the basic Address abstraction with the concerns that are orthogonal to it. Our model, which is the design language treats orthogonal concerns as separate lexemes and encourages ways to compose them non invasively by the user.

Eric said...

Very good article, thanks. Do you know if anyone tried to define a metric for orthogonality? Is that something you can measure or is it more like an aesthetic quality?

BTW, one typo:

static LabelMaker {
def toLabel: String
}

should be:

trait LabelMaker {
def toLabel: String
}

Eric.

Debasish said...

oops .. fixed the typo .. Thanks for the kind words ..

- Debasish

Gilles said...

I've been reading you for a while now, always very interesting articles!
I think orthogonality would only be better if you could add traits to existing objects. This way, you wouldn't need to decide at class level or instance level what orthogonal behaviour you would like to add to your object; you could add it at the point of use. I know there are the implicits, but they are called at each call, and cannot hold any state. I especially dislike having to repete myself as in:
def createPerson(name:String,age:Int)= {
if (mustLog) {
new Person(name,age) with Logging
} else {
new Person(name,age)
}
}

But maybe there is an alternative?

Debasish said...

Maybe I don't understand your concerns fully. But if you don't want to do it during invocation time, you can always define a trait as :

trait LoggablePerson extends Person with Logging {
//..
}

and use it. That way you don;t pollute your core abstraction and also you don't have to repeat for each instantiation.

Anonymous said...

This reminds me of Qi4j and composite-oriented programming where objects are built up from fragments (in the form of mixins, concerns, constraints, and side effects). Fragments allow the encapsulation of orthogonal concerns. It looks like this follows the orthogonal design philosophy.