Posts Tagged ‘Constraints’

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