Posts Tagged ‘Policy-Based Design’

This post is basically a meditation on static design choices and code expressivity.

Some days ago I was writing a simple wrapper around std::map supporting a couple of elemental features:

  • succinct syntax for inserting/updating key-value elements, e.g.:

selector<string, int> sel;

sel.at("one") = 1; // insertion

sel.at("two") = 2; // insertion

sel.at("one") = 10; // update

sel.get("one"); // 10

  • mechanism to handle a possible default value if an inexistent key is looked up.

Note that possible means optional and the client should be able to choose either to provide a default value or not. If a default value is not provided, the get() method just throws. From an Object-Oriented standpoint, a simple way to deal with this requirement is to have an interface, say IDefaultValueProvider<T>, and two concrete classes, say ActiveDefaultValueProvider<T> and PassiveDefaultValueProvider<T> (sort of Null Object Pattern).

Our selector<K,T> will store a unique_ptr<IDefaultValueProvider<T>>, passed in the constructor. Something like:


selector<string, int> sel ( make_unique<ActiveDefaultValueProvider<int>(0) );

sel.at("one") = 1; // insertion

sel.get("one"); // 1

sel.get("foo"); // 0 (default)

selector<string, int> sel_nd ( make_unique<PassiveDefaultValueProvider<int>() );
// or just selector<string, int> sel_nd; // default-parameter

sel_nd.get("one"); // throws

Ok this works. How does this implementation cost?

  • we wrote an interface and two concrete classes
  • we need a dynamic allocation (unique_ptr)
  • the selector has to store a unique_ptr
  • defaulted-selector and non-defaulted-selector have the same type

The latter point leads to (probably) the most important issue: we don’t know what will happen when selector.get() is called. Will it throw? Will not? Should we flood our code with plenty of try/catch? To solve this problem we can, for example, change the return value of get(): instead of getting a T&, we can return a pair<bool, T&> where the first element is true if the key exists and the second is the value corresponding to that key (if the key does not exist, T& is binded to a global fake T).

Ugly.

We can do better, but does it make sense? I think no. This problem can be addressed from another perspective: the client must decide which type of selector she wants, if a defaulted one or not. This way the user will know exactly what will happen. When designing classes it is important to discern between static and dynamic abstractions. Think of “configurability”: does it make sense to configure a certain instance of a class at compile-time (e.g. using a template) or at run-time (e.g. reading from a file)? For my simple example, the answer is probably the first.

Ok, how to express this static choice? An idea is to use templates and this is the second part of my meditation: how to communicate our intentions effectively? In particular, what if the readers (e.g. maintainers) of our code are not very familiar with TMP? I’d like to find a middle way combining compactness and clarity.

The problem now is: a selector must be instantiated by providing a template parameter, say either enable_default or disable_default. What we expect:


selector<string, int, enable_default> sel1 (10); // default = 10

selector<string, int, enable_default> sel2; // compile-error (default not provided)

selector<string, int, disable_default> sel3; // ok

selector<string, int, disable_default> sel4 (20); // compile-error

Suppose enable_default and disable_default are boolean flags (respectively, true and false). We have at least two possibilities here:

  • write two specializations (verbose but quite clear)
  • use static_assert and a bit of metaprogramming:
#include <type_traits>

template<typename K, typename T, bool flag>
struct selector
{
  template<typename V>
  selector(V&& pDefault) : default_value(std::forward<V>(pDefault))
  {
    // if (flag == true) OK, else ERROR (and complain)
    static_assert(flag, "Default value unexpected");
  }

  selector() : default_value(1)
  {
    // if (flag == false) OK, else ERROR (and complain)
    static_assert(!flag, "Provide a default value");
  }

private:

   // if (flag == true) T, else char (a fake default)
   typename std::conditional<flag, T, char>::type default_value;

// ... implementation ...
};

This is more readable and clearer than lots of enable_if and other tricks. But we can do much better by using Policy-Based Design and   moving the (single) point of variation to real classes (our policies). We’ll get rid of static_asserts and std::conditional.

This is a possible draft:

template<typename T>
struct disable_default
{
  T& get_default()
  {
    throw 1;
  }

  const T& get_default() const
  {
    throw 1;
  }
};

template<typename T>
struct enable_default
{
  template<typename Value>
  enable_default(Value&& def_value) : default_value(std::forward<Value>(def_value))
  {
  }

  const T& get_default() const
  {
     return default_value;
  }

  T& get_default()
  {
     return default_value;
  }

private:
  T default_value;
};

template<typename K, typename T, template <typename> class default_policy = enable_default>
struct selector : public default_policy<T>
{

 using typename default_policy<T>::get_default;

 template<typename Value>
 selector(Value&& def_value) : default_policy<T>(std::forward<Value>(def_value))
 {
 }

 selector()
 {
 }

 T& select(const K& key)
 {
   return const_cast<T&>(static_cast<const selector*>(this)->select(key));
 }

 const T& select(const K& key) const
 {
   auto it = selector_map.find(key);
   if ( it != end(selector_map) )
   {
      return it->second;
   }
   else
   {
      return get_default();
   }
 }

//... other stuff omitted here ...

private:
   std::map<K,T> selector_map;
};

Let’s see how to instantiate selectors:

selector<string, int, enable_default> def_selector(0);

//...

selector<string, int, disable_default> ndef_selector;

A possible (and a bit different) code is on ideone.

A couple of notes:

  • the policy is a “template template parameter” to avoid redundancy
  • a constructor is not generated if not used (e.g. using enable_default, the empty ctor is not generated at all)

The mechanism is clear because it is sort of driven by design: enable_default wants to be constructed with an argument, then the host class (the selector) just forwards its constructor parameter to the base class. If the user does not provide a parameter, the code simply does not compile. If the code is not easy to read yet, put a static_assert (or a comment) to clarify our intentions, but I think it’s not needed.

My final note about this meditation is: template metaprogramming aims to be clear and helpful instead of tricky and painful. We have lots of possible solutions, more or less complicated. Policy-Based Design is not only a usage of templates, but also a tool for specifying constraints, class rules, and (static) abstractions. It helps to express choices by (static) design.

I conclude with a question for you about expressivity/clarity: given, for example, this code I wrote in a previous post to force the user to pass an rvalue-reference:


// [1] (does not compile on VC2010)
template<typename T>
auto make_move_on_copy(T&& aValue)
 -> typename enable_if<is_rvalue_reference<decltype(aValue)>::value, move_on_copy<T>>::type
{
    return move_on_copy<T>(move(aValue));
}

// [2]
template<typename T>
move_on_copy<T> make_move_on_copy(T&& aValue)
{
   static_assert(is_rvalue_reference<decltype(aValue)>::value, "parameter should be an rvalue");
   return move_on_copy<T>(move(aValue));
}

I think SFINAE here is overused, whereas static_assert is easier and more readable. Which do you prefer?

Advertisements

Designing software systems is hard because it constantly asks you to choose, and in program design, just as in life, choice is hard. Choices can be conbined, which confers on design an evil multiplicity. Writing generic code is about giving the user the capability to choose the combination she likes the most and, possibly, the faculty to expand/customize the initial codebase.

C++ vector is a good example: it lets you choose what type of objects you are going to store in and, in case, what allocator you want to use. The allocator is optional because vector provides a default parameter. Default choices are prominent when your component admits simplified/general usage.

This post deals with fighting against evil multiplicity using a flexible and generative approach. I’m going to build a step-by-step example to support the discussion.

Consider a trivial logger class:

class Logger
{
public:
     Logger(ostream& stream) : m_stream(stream) {}

     void Log(const string& message)
     {
          m_stream << message;
     }

private:
     ostream& m_stream;
};

I have already made some decisions: construction (provide a reference to an ostream), message type (string), what to log (log everything), how to log (just use operator<<). Improving genericity by logging every type supporting operator<< is quite simple:

template <typename MessageType>
void Log(const MessageType& message)
{
     m_stream << message;
}

Templates come to the rescue. Now, what if we want to choose what to log? Suppose we want to filter log entries depending on a certain severity (e.g. info, error, debug). Log method could look like this:

template <typename MessageType>
void Log(const MessageType& message, const Severity& severity)
{
     if (...severity...)
          m_stream << message;
}

How to choose what to log here? An approach could be injection:

class Logger
{
public:
     Logger(ostream& stream, Filter& filter) : m_stream(stream), m_filter(filter) {}

     template <typename MessageType>
     void Log(const MessageType& message, const Severity& severity)
     {
          if (m_filter.CanPrint(severity))
               m_stream << message;
     }
private:
     ostream& m_stream;
     Filer& m_filter;
};

Consider an example of usage:

ErrorFilter filter;
Logger logger = Logger (cout, filter);
logger.Log("Hello, this is an info and won't be logged!", Info());
logger.Log("This error will be logged!", Error());

What I dont’ like:

  • Creating severities every time I have to log,
  • Creating a filter and worrying about its ownership,
  • Making static decisions and using them “dynamically”.

Consider the first issue. To avoid creating severity objects every time Log method is called, we can employ templates, again:

template <typename SeverityType, typename MessageType>
void Log(const MessageType& message)
{
if (m_filter.CanPrint<SeverityType>())
          m_stream << message;
}

I swapped SeverityType and MessageType to omit the second template parameter and let the compiler to get by on its own:

logger.Log<Error>("this is an error!");

Second and third issues are strictly related: first I created a filter then I injected it into the Logger. I consider these operations dynamic, meaning that the binding between Logger and Filter is after the program starts. How can we improve this? How can we benefit from static binding here?

An elagant way to encapsulate “static” decisions is built on policies. The mechanics of policies consist of a combination of templates with multiple inheritance. This technique is purposely conceived to support flexible code generation by combining a small number of these “primitive devices”. It’s easier to apply a filter policy to our example than to bore you with abstract concepts:

template <typename FilterPolicy>
class Logger : public FilterPolicy
{
     // just for readablity (a sort of "specification")
     using FilterPolicy::Filter;
public:
     Logger(ostream& stream) : m_stream(stream) {}

     template <typename SeverityType, typename MessageType>
     void Log(const MessageType& message)
     {
          // inherited from FilterPolicy
          if (Filter<SeverityType>())
               m_stream << message;
     }
private:
     ostream& m_stream;
};

A class that uses policies — a host class — is a template with many template parameters, each parameter being a policy. The host class “indirects” parts of its functionality through its policies and acts as a receptacle that combines several policies in a coherent aggregate.

Now we can use our Logger class easily:

// typedef Logger<ErrorFilter> LoggerErrorFilter; -> use typedef if you need readability
Logger<ErrorFilter> logger(cout);
logger.Log<Error>("this will be logged!");
logger.Log<Info>("this won't be logged!");

Possibile implementations of filter policies:

// Severity types
struct Info {};

struct Error {};

struct Generic {};

struct ErrorFilter
{
     // pass nothing by default
     template<typename Severity>
     bool Filter() { return false; }
};

// Specialization -> Let pass errors
template<>
bool ErrorFilter::Filter<Error>() { return true; }

Relying on template specializations you can quickly create new filters. Play – mildly – with macros if you are lazy:

// Generate a Filter by Name
#define CREATE_FILTER(Name)\
 struct Name \
 {\
 template<typename Severity> bool Filter() {return false;}\
 };

// [SUPPORT] Create a specialization
#define ADD_SEVERITY(FilterName, Severity)\
 template<> bool FilterName::Filter<Severity>() { return true; }

// One-Severity Filter
#define CREATE_FILTER_1(Name, Severity)\
 CREATE_FILTER(Name)\
 ADD_SEVERITY(Name, Severity)

// Two-Severities Filter
#define CREATE_FILTER_2(Name, Severity1, Severity2)\
 CREATE_FILTER_1(Name, Severity1)\
 ADD_SEVERITY(Name, Severity2)

// ... add 3,4,... versions if you need

// User's code

CREATE_FILTER_2(ErrorInfoFilter, Error, Info)

...

Logger<ErrorInfoFilter> logger(cout);
logger.Log<Error>("this will be logged!");
logger.Log<Info>("this will be logged too!");

This is just a possible implementation. In a future post I’ll show you another code based on tuples, with no macros nor specializations. By the way, you can add new filters with complicated logic by creating new policies that observe FilterPolicy’s specification (just the Filter function). Think of the specification as the methods the host class expects to use. This differs from classical object-orientation where you need to observe a typed interface; here this constraint is blunt because a policy only need to observe a sort of “signature expectations”.

Another responsability we can confine in a policy regards outputting the message:

struct OStreamPolicy
{
   OStreamPolicy(ostream& stream) : m_stream(stream) {}

   template<typename Message>
   void Out(const Message& message)
   {
       m_stream << message << endl;
   }

private:
   ostream& m_stream;
};

// very fake class!
struct DBPolicy
{
   DBPolicy(const string& credentials) : m_db(credentials) {}

   template<typename Message>
   void Out(const Message& message)
   {
       m_db.Insert(message);
   }

private:
   LogDB m_db;
};

template <typename FilterPolicy, typename OutPolicy>
class Logger : public FilterPolicy, public OutPolicy
{
     using FilterPolicy::Filter;
     using OutPolicy::Out;
public:
     template<typename ARG1>
     Logger(ARG1&& arg1) : OutPolicy(forward<ARG1>(arg1)) {}

     template <typename SeverityType, typename MessageType>
     void Log(const MessageType& message)
     {
          // inherited from FilterPolicy
          if (Filter<SeverityType>())
               // inherited from OutPolicy
               Out(message);
     }
};

...

Logger<ErrorFilter, OStreamPolicy> logger(cout);

Logger<ErrorFilter, DBPolicy> db_logger("POLICY-BASED");

I used perfect forwarding to enforce genericity. To improve this design you can, for example, employ a variadic constructor (generic and variable number of arguments). A radical approach could completely eliminate construction parameters:

struct CoutPolicy
{
   template<typename Message>
   void Out(const Message& message)
   {
      cout << message << endl;
   }
};

Choose the design more convenient for you but don’t be too maniac about static decisions (for example you may need to read a log file from a network source and this can’t be determined at compile time!). Adding other out policies is easier than adding filter ones!

The power of policies comes from their ability to mix and match. A policy-based class can accommodate very many behaviors by combining the simpler behaviors that its policies implement. This effectively makes policies a good weapon for fighting against the evil multiplicity of design.

Using policy classes, you can customize not only behavior but also structure. This important feature takes policy-based design beyond the simple type genericity that’s specific to container classes.

The last thing I’m going to show you is about enriched behavior: a policy can provide supplemental functionality that propagates through the host class due to public inheritance. Furthermore, the host class can implement enriched functionality that uses the optional functionality of a policy. If the optional functionality is not present, the host class still compiles successfully, provided the enriched functionality is not used.

For example, consider an OutPolicy such as:

struct SpecialOutPolicy
{
   template<typename Message>
   void Out(const Message& message)
   {
      // not relevant
   }

   template<typename Message>
   void SpecialOut(const Message& message)
   {
      // another logging method, not "required" by the host class "specification"
   }
};

You inherit SpecialOut by instantiating a Logger templetized on SpecialOutPolicy. This feature can be particularly useful when you need to control what operations can be executed according to static (aka by design) constraints. Trivial example: suppose you have to interact with an I/O device through a certain wrapper, specifying an appropriate opening mode (e.g. text read, text write, binary read, binary write). An old-style implementation could be:

class IODeviceWrapper
{
     IODeviceWrapper(int mode) // lots of #defines to avoid numbers
     { ...  }
     <SomeType> Read(<SomeParameters>) { ... }
     <SomeType> Write(<SomeParameters>) { ... }
     ...
};

What if I instantiate the device using a read mode and then I attempt to write? It shouldn’t be permitted by design. We can enforce this constraint by employing policies:

template<typename Mode>
class IODeviceWrapper : public Mode
{
   ...
};

struct ReadMode
{
    <SomeType> Read(<SomeParameters>) { ... }
};

struct WriteMode
{
    <SomeType> Write(<SomeParameters>) { ... }
};

struct ReadWriteMode : public ReadMode, public WriteMode {};

...

IODeviceWrapper<OpenMode> wrapper;
wrapper.Read(...); // ok
wrapper.Write(...); // not compile

IODeviceWrapper<ReadWriteMode> anotherWrapper;
anotherWrapper.Read(...); // ok
anotherWrapper.Write(...); // now ok

Such techinques can enforce not only customization but also design constraints. Thanks to their flexibility, policies are great allies if you are writing a library or a set of APIs. Furthermore, policy-based design is open-ended that is the library should expose the specifications from which these policies are built, so the client can build her own.

If you want to study in deep this topic I recommend Modern C++ Design by Alexandrescu. In addition to an excellent introduction to policy-based design, you can find real examples of usage applied to design patterns (e.g. command, visitor). Although this book was written more than 10 years ago, you can learn:

  • non-trivial examples of policy-based classes,
  • template metaprogramming techniques,
  • C++ & modern implementations of Design Patterns,
  • implementation ideas of some C++11 concepts.

Policy-based design requires you to change point of view about software decisions. Consider not only dynamic binding but also static (or compile time) binding. A more powerful approach lies in mixing static binding with dynamic binding, but this is another story!