Wednesday, March 08, 2006

Abstraction in Software - Commonality and Variability (Part 2)

In Part 1 of this series, I had stated the definition of abstraction as studied by Dick Gabriel in Patterns of Software : Tales from the Software Community
Abstraction in programming is the process of identifying common patterns that have systematic variations; an abstraction represents the common pattern and provides a means for specifying which variation to use.

A good abstraction needs to capture the common aspects across the family while specifying the variabilities of individual items. Jim Coplien refers to commonality as the essence of an abstraction, while he mentions variability as the spice of life. Parnas defines a family of programs based on the common properties of the set and the special properties of the individual members :
We consider a set of programs to constitute a family, whenever it is worthwhile to study programs from the set by first studying the common properties of the set and then determining the special properties of the individual family members

Whatever be the implementation language, model of computation or programming paradigm, software abstraction is always based on this duality of commonality and variability. All design patterns which promise good abstractions, support this duality.

  • The Template Method pattern encapsulates the common operation flow with variable hotspots.

  • The Strategy pattern supports common interface with varying implementation of the algorithm.

  • The Bridge pattern allows varying abstraction and implementation hierarchies with a common interface.


In his book Multi-Paradigm Design for C++, Jim Coplien distinguishes between Positive Variability and Negative Variability in software abstractions. Positive variabilites add to the contracts exposed by the base class, without violating any of those specifications. OTOH negative variabilities contradict the assumptions that underlie the base contracts. However, he insists that not all negative variabilities are bad - in fact various programming languages offer specific constructs to design negative variabilites in a positive way. In C++, public inheritance with addition of contracts is an approach to address positive variability (the base class encapsulating the commonality of the abstraction), while features like template specialization may be used to implement negative variability. The following example, which illustrates the commonality and variability of an abstraction, is, once again from Coplien :

template <class T>
class Stack {
    StackRep<T>* rep;
    ....
};

template <class T>
class StackRep {
    friend class Stack<T>;
    StackRep<T>* next;
    T* rep;
};


The above example presents a generic implementation of a stack based around a completely general implementation - can handle polymorphic data types, can easily grow as large as needed and the stacked items need not have a default constructor. This is the commonality of the abstraction which all instantiations of the template are bound to.
But this implementation adds a lot of overhead to the memory consumed by the objects it manages, particularly if the managed objects are small. Users wanting to implement a stack of integers may like to go for a more efficient solution, since they don't need the generality of polymorphism support.
Enter template specialization !!

template<> class Stack<int> {
    int* rep;
    ....
};


In the above example, Stack<int> violates the commonality of the structure which the base template provides - we treat this as a negative variability !!
This post illustrates the features of a good data abstraction - a unification of the common properties of a family alongside managing the variations. In the next entry of this series, we will look at some of the control abstractions and how they have evolved in some of the modern programming languages.

Stay tuned !!

No comments: