The Paradox of Software Complexity

A common principle in user interface design is the conservation of complexity. Every task has some fundamental, irreducible complexity. Designers can either hide this complexity behind a simple interface or expose it to the user through a richer, more complex interface. What if a designer adds useless widgets to the interface? Because complexity is added beyond what the user needs, the interface has been complicated. This same principle applies when designing abstractions in software; hiding complexity behind abstractions is one way our limited minds can build complex software! After all, it is much easier to reason about structures and functions than raw memory addresses and stack frames. Herein lies the paradox - partitioning software into abstractions is fundamentally a complication.

Complexity can be looked at as the "inter-connectedness" of the parts of a system. The more parts and connections between them, the more complex the system becomes. An abstraction takes some of these connected parts and hides them behind a new part. We have hidden the details, and the top-level is now (hopefully) simpler. The complexity from the details does not just go away; it is only hidden behind the abstraction. On top of this, we now have a new part and its new connections. The system is now complicated! If an abstraction is not worth the cost of this complication, then it is a bad abstraction.

For this reason, good abstractions are highly coherent and minimally coupled. A perfect example is a C compiler. A good compiler can abstract away the details of the machine code and free our minds to build higher-level abstractions. The programmer still has to worry about managing resources, but can have the convenience of functions and loops rather than the moves and jumps that are implemented by the CPU. In specific cases, a programmer will need to know these hidden details anyway. A C compiler is so decoupled that it does not need to be shipped with the binaries it produces. The C standard library, however, is supported by a platform-specific runtime library. This allows a lot of higher-level, platform-dependent parts to be abstracted away too. We can continue to hide complexity with virtual machines, network stacks and GUI toolkits. Every part hidden is another part we can afford to build.

In a perfect world, this article would have ended after the last sentence. As we covered earlier, there is a complication - all of these abstractions add unnecessary complexity. Their fundamental complexity does not just go away; somebody has to manage that complexity. To make matters worse, it is sometimes necessary to understand some of the abstracted details anyway. These leaky, complicated abstractions often result in performance, maintenance and security issues. Sometimes the complication pays off: the software components can be reused or divided more efficiently among a team. Other times, the cost of this complication will scale much faster than the software.

Improving on Tuples

In the previous article, we saw how a tuple is really just a struct disguised as an array. A tuple simply maps a struct's types to an index. Just as we can iterate over an array at run-time, we can iterate over a tuple's elements at compile-time. For example, we can implement a simple linear search and iterate over the tuple until an element of the given type parameter is selected. If no element of that type is found, then the code won't compile. Because all of this happens at compile-time, there is very little run-time overhead.

//------------------------------------------------------------------------------
// Recursively iterate over tuple
template <int N, typename A> 
struct TupleGetType {  
  typedef typename std::tuple_element<N, A>::type ElementN;
  template <typename T>
  typename std::enable_if<std::is_same<T, ElementN>::value, T&>::type
  static getType(A& tuple) {
    return std::get<N>(tuple);
  }

  template <typename T>
  typename std::enable_if<!std::is_same<T, ElementN>::value, T&>::type
  static getType(A& tuple) {
    return TupleGetType<N-1, A>::template getType<T>(tuple);
  }
};

//------------------------------------------------------------------------------
// Terminate at first element
template <typename A> 
struct TupleGetType<0, A> {
  typedef typename std::tuple_element<0, A>::type Element0;

  template <typename T>
  typename std::enable_if< std::is_same<T, Element0>::value, T&>::type
  static getType(A& tuple) {
    return std::get<0>(tuple);
  }

  template <typename T>
  typename std::enable_if<!std::is_same<T, Element0>::value, T&>::type
  static getType(A& tuple) {
    static_assert(std::is_same<T, Element0>::value, 
                  "No element of type T in std::tuple");
  }
};

//------------------------------------------------------------------------------
// Convenient wrapper
template <typename E, typename T> 
E& getType (T& tuple) {
  return TupleGetType<std::tuple_size<T>::value-1, T>::template getType<E>(tuple);
}

Now we don't have to worry about the positions of elements within the tuple. Although this isn't the prettiest or most readable code, the stink is safely encapsulated by the getType function. Of course, there is an obvious limitation: if the tuple has more than one element with the same type, only one will ever be returned by getType. We will explore the upside of this limitation in a moment.

We've already mentioned that tuples are basically equivalent to structs. More importantly, they allow us to define a collection of heterogeneous types using template parameters at compile-time. Because of this parameterization, tuples are incredibly useful when writing abstractions. A great example is a type-safe publish/subscribe mechanism:

//------------------------------------------------------------------------------
// Simple event handler interface
template <typename Event>
struct Handler {
  virtual void onEvent(Event event) = 0;
};

//------------------------------------------------------------------------------
// Our main event registrar
template <typename... Events>
struct EventRegistrar {
  // Publish an event of event type E
  template <typename E>
  void pub(E event) {
    for (Handler<E>* e : handlers_<E>()) {
      e->onEvent(event);
    }
  }

  // Subscribe to the event type E
  template <typename E>
  void sub(Handler<E>* pHandler) {
    handlers_<E>().push_back(pHandler);
  } 

private:
  // Get the list of Handler<E>s
  template <typename E>
  std::list<Handler<E>*>& 
  handlers_() {
    return getType<
      std::list<Handler<E>*>
    >(eventHandlers_);
  }

  // tuple of lists of handler<> pointers
  std::tuple<
    std::list<Handler<Events>*>...
  > eventHandlers_;
};

And its usage:

//------------------------------------------------------------------------------
// Some trivial event definitions.
struct EventA {};
struct EventB {};
struct EventC {};

//------------------------------------------------------------------------------
// Handler for EventA
struct HandlerA : public Handler<EventA> {
  void onEvent(EventA a) {
    std::cout << "EventA Fired!!!" << std::endl;
  }
};

//------------------------------------------------------------------------------
// This one handles two events
struct HandlerBC : public Handler<EventB>
                 , public Handler<EventC> {
  void onEvent(EventB b) {
    std::cout << "EventB Fired!!!" << std::endl;
  }

  void onEvent(EventC c) {
    std::cout << "EventC Fired!!!" << std::endl;
  }
};

//------------------------------------------------------------------------------

int main () {
  // Define an event registrar for events A, B and C
  EventRegistrar<
    EventA, 
    EventB, 
    EventC
  > reg;

  // Define two handlers, one for handlers event A, and one for events 
  // A and B.
  HandlerA  handlerA;
  HandlerBC handlerBC;

  // Subscribe to event types
  reg.sub(&handlerA);
  // We must tell the registrar which event we want to register
  // in this case because otherwise it is ambiguous
  reg.sub<EventB>(&handlerBC);

  // Publish some events
  reg.pub(EventA()); // triggers event
  reg.pub(EventB()); // triggers event
  reg.pub(EventC()); // no event triggered

  // Nothing was subscribed to EventC (our handlerBC had
  // only been added to the EventB registry).  Subscribe
  // to EventC
  reg.sub<EventC>(&handlerBC);

  // Publish another EventC  
  reg.pub(EventC()); // triggered event

  // The following should fail with compiler errors
  #ifdef FAIL_SUB
  reg.sub<EventC>(handlerA);
  #endif

  #ifdef FAIL_PUB
  struct EventZ {};
  reg.pub(EventZ());
  #endif
  
  return 0;
}

Everything is parameterized by type. As you can see, type parameters "flow" more easily between the different layers of our abstractions. There is little syntactic noise. Parameterizing by types also gives us type safety. The pieces of code guarded by FAIL_SUB and FAIL_PUB will actually provide compiler errors: handlerA can't possibly subscribe to EventC and the registrar has no clue what EventZ is.

What if we do want to store multiple elements of the same type in a tuple? We could revert and use tuple indices to address these elements; but as we saw previously, this is ugly and error-prone. Throwing away all of this context makes it far too easy to mix up variables when using the tuple. What if instead, we wrap the type in a struct and create an entirely distinct type? We can even provide some constructors and casts to make this new type more natural to use.

template <typename T, typename N>
struct NewType {
  NewType()
  :  value_() {
  }

  NewType(const T& value)
  :  value_(value) {
  }

  T& operator=(const T& value) {
    return value_;
  }

  operator T& () {
    return value_;
  }

  typedef T Type;  
  T         value_;
};

template <int N>
struct Tag;

Now we have a way to provide context other than with named variables. The Tag<> template just provides an easy way to define anonymous tags.

typedef NewType<float, Tag<0>> Position;
typedef NewType<float, Tag<1>> Velocity;

std::tuple<Position, Velocity> mv(0.0f, 10.0f);
getType<Position>(mv) += getType<Velocity>(mv) * 100.0f;

We can also use named tags if there is a concern of clashing types later on:

struct PosTag;
struct VelTag;
typedef NewType<float, PosTag> Position;
typedef NewType<float, VelTag> Velocity;

std::tuple<Position, Velocity> mv(0.0f, 10.0f);
getType<Position>(mv) += getType<Velocity>(mv) * 100.0f;

These type names can provide just as much context as variable name, but this obviously doesn't mean that every struct should be replaced with a tuple. Tuples really only have an advantage when building parameterized abstractions. In the next article, we will look at defining some key operations that can be used to create a basic type-safe relational algebra in C++11.

A Case for Tuples

One of the more exciting new features in C++11 is the std::tuple template. A tuple is a struct pretending to be an array; the variable names are replaced with anonymous tuple indices. By replacing identifiers with more abstract indices, we can create a more abstract object. For example, cartesian coordinates (x, y) and complex coordinates (phase, magnitude) could both be represented by tuple<float, float>. Unlike an array, the elements can have different types.

Consider any C-style struct. The struct's member variables can be mapped directly to tuple elements. The first variable and index zero could be paired, followed by the second variable and index one. This would continue until the last member variable was paired with index N, where N is one less than the number of variables in the struct. With this mapping, it just so happens that the tuple’s elements are in the same order as the struct’s records, though this need not be the case. Regardless of the chosen mapping, a tuple abstracts away the names of the members, so instead of “position” and “velocity”, we have element one and element two.

To demonstrate a tuple’s abstraction potential, here is a simple example:

struct Move {
  float velocity_;
  float position_;

  Move(float pos, float vel) 
    : velocity_ (vel)
    , position_ (pos) {
  }

  inline update(float dt) {
    position_ += velocity_ * dt; 
  }   
};

Let’s reimplement this class using a tuple instead of member variables:

template<typename T>
struct Integrate {
  std::tuple<T, T> tuple_;

  Integrate(T s, T ds) 
    : tuple_ (ds, s) {
  }

  inline update(float dt) {
    std::get<1>(tuple_) += std::get<0>(tuple_) * dt; 
  }   
};

We’ve successfully abstracted away all of the context about “moving”. Now this implementation can be used for other tasks such as calculating throughput for a network interface. Without this context, unfortunately, the abstraction is more difficult to use. A name is obviously better than an index, so it seems as if we’ve taken a step back. Lets instead focus on what we get by abstracting away this context. What if we wish to add another “order” to the integration? For example, we are developing a game and we want to allow acceleration of a game entity due to gravity. We can add another element to our tuple:

template<typename T> 
struct Integration2 {
  std::tuple<T, T, T> tuple_;

  Integration(T s, T ds, T ds2) 
    : tuple_ (ds2, ds, s) {
  }

  inline update(float dt) {
    std::get<1>(tuple_) += std::get<0>(tuple_) * dt;
    std::get<2>(tuple_) += std::get<1>(tuple_) * dt;
  }
};

Without the context, it is easy to see that this is a pattern that can be generalized. Why have two different definitions of this class when instead we could have a single template that can define any number of iterated integrals?

// "Recursive" Case
template <int N>
struct UpdateTupleImpl {
  template <typename...T>
  static void update(std::tuple<T...>& tuple, float dt) {
    UpdateTupleImpl<N-1>::template update<T...>(tuple, dt);
    std::get<N+1>(tuple) += std::get<N>(tuple) * dt;
  }
};

// Terminal Case
template <>
struct UpdateTupleImpl<1> {
  template <typename...T>
  static void update(std::tuple<T...>& tuple, float dt) {
    std::get<1>(tuple) += std::get<0>(tuple) * dt;
  } 
};

// Wrap it up in a helper - deduce template parameters 
template <typename...T>
inline void integrate(std::tuple<T...>& tuple, float dt) {
  UpdateTupleImpl<sizeof...(T)-1>::template update<T...>(tuple, dt);
}

// Example
std::tuple<float, float, float> vel(1.0f, 5.0f, 10.0f);
integrate(vel, 100.0f);
integrate(vel, 100.0f);
float position = std::get<1>(vel);

Along with demonstrating C++’s ability to define powerful abstractions, this example also shows how ugly and verbose the language can be. Our template parameters can be any mix of types (we can have floats, doubles and ints mixed for example), but all the types must support the += operator and float multiplication. This example isn't supposed to be useful or used in practice; it is just a simple demonstration of abstraction using tuples.

In the example above, the “recursive” case isn’t actually recursive. Because it is the template parameter that varies, it is actually calling a completely different function with each iteration. We also know the number of iterations at compile-time, so the functions are inlined and the implementation is as efficient as the more concrete example.

We’ve already covered one of the major disadvantages of a tuple: the loss of context caused by abstracting away identifiers. Not only do we have to know what a tuple’s elements’ values represent whenever we use it, we must also know the values’ types and their positions within the tuple. Something very interesting happens if every element of the tuple has a different type. It becomes possible to unambiguously address a tuple element by its type alone, thus abstracting both identifiers and tuple element positions away. Its even possible for the type names to contain enough context to make up for losing the identifiers.

typedef Integration<Velocity, Position> Mover;
// initial velocity, and initial position
Mover mv({0.0f}, {100.0f});
update(mv, 100.0f);
update(mv, 100.0f);
float position = getType<Position>(mv.tuple_);

Unfortunately std::tuple does not have a uniqueness constraint. Even if it did, we’d have to define the unique types for the tuple. The next article in this series will address these issues with an alternative to std::tuple.