Clever overloading

This post is intended to be a light introduction to certain C++ guru tricks. I want to introduce a couple of concepts that typically put normal people off. If you are an expert you will probably not learn anything new, except maybe for how to talk about such things to ordinary programmers. If you are an “ordinary programmer” with a happy family life, note that you really do not have to know these tricks to be a good, successful developer.

We are going to see a rather unusual problem connected to function overloading and explore the techniques of solving it.

The problem

Here is a suggestion from Vladimir Batov for extending library Optional. Both Optional from Library Fundamentals TS as well as Optional in Boost 1.56 have a member function value_or. This enables you an interesting way of accessing the potentially absent contained value: “either give me the value or give me the default”:

optional<int> convert(std::string s);

int i = convert(t).value_or(0);
// if conversion fails: i = 0; 

Function value_or() is declared more less like this:

template <typename T>
class optional
{
  // ...

  template <typename U>
  T value_or(U const& v) const
  {
    if (*this)              // initialized?
      return this->value(); // get contained value
    else
      return v;             // get v converted to T
  }
};

So, value_or() takes any argument of any type U implicitly convertible to T, not necessarily a T. It performs the conversion only when it is required, so that in the following code:

optional<std::string> get_text();
std::string s = get_text().value_or("n/a");

No std::string will be constructed from "n/a" when the returned optional contains a value.

It works pretty good. Now, here is an idea for a clever extension. Extend function value_or() so that it accepts any U that is either convertible to T or is callable (a functor or a function) with no arguments and a return type convertible to T:

int log_and_continue()
{
  clog << "conversion failed; using -1 instead" << endl;
  return -1;
}

int i = convert(t).value_or(&log_and_continue);
// if conversion fails: i = -1 and log; 

Can this be implemented? Consider the naïve case:

// WILL NOT WORK

template <typename U>
T value_or(U const& v) const
{
  if (*this)
    return this->value();
  else if (std::is_convertible<U, T>::value)
    return v;
  else
    return v();
}

This expression, std::is_convertible<U, T>::value is called a type trait, it is a sort of (meta)function that returns a compile-time boolean constant saying if U is convertible to T. It may not be obvious that this is a ‘function’ at first, given these angle brackets and colons, but it might be easier to think of it as a function if we wrapped it into a macro:

#define IS_CONVERTIBLE(U, T) std::is_convertible<U, T>::value

int main()
{
  assert (IS_CONVERTIBLE(int, double));
  assert (!IS_CONVERTIBLE(int, std::string));
}

Nonetheless, function value_or as defined above doesn’t work. In order for this function (any function instantiated from this template) to compile both instructions return v; and return v(); need to be valid; even if it can be proven at compile-time that the condition is always true (or false). This is how compilation rules in C++ work. The above code would work if we had something like “static if” from Language D. But we do not; for a good reason.

We could solve the problem by splitting this function into two overloads:

// WILL NOT WORK

template <typename U>
T value_or(U const& v) const
{
  if (*this)
    return this->value();
  else
    return v;
}

template <typename F>
T value_or(F const& f) const
{
  if (*this)
    return this->value();
  else
    return f();
}

Now each function contains only one required expression. It looks like it might work, but when we make a call like this:

int i = convert(t).value_or(def);

How is the compiler supposed to know which of the two overloads to pick? Compiler is good at picking the best function out of a number of competing overloads but here neither can be considered best. The two overloads match equally well: just some object passed by reference. This ambiguity results in a compiler error. So, is there a way to instruct the compiler which overload it should prefer and when?

Ideal solution: Concepts Lite

There is no direct way of doing it cleanly as of today. This is the problem that Concepts Lite aim at fixing. With Concepts Lite, this problem is solved like this:

// Concepts Lite, not C++ yet

template <typename U>
T value_or(U const& v) const
  requires is_convertible<U, T>::value
{
  if (*this)
    return this->value();
  else
    return v;
}

template <typename F>
T value_or(F const& f) const
{
  if (*this)
    return this->value();
  else
    return f();
}

This requires is a keyword and means “prefer this overload if is_convertible<U, T>::value is true.” If is_convertible<U, T>::value is false the first overload is not even considered, so the compiler can pick the second one. Concepts Lite are about far more than just solving our overload resolution problem, but this is another story, not in the scope of our post.

Working solution: tag dispatching

But we can solve our problem with some clever tricks. There are at least two ways of doing it. Here is one. We will add a second special function parameter to each function. This will be a “tag” that will make the functions look different. We will also change the name of the function slightly. You will see why in a second:

#include <type_traits>

template <typename U>
T value_or_(U const& v, std::true_type) const
{
  if (*this)
    return this->value();
  else
    return v;
}

template <typename F>
T value_or_(F const& f, std::false_type) const
{
  if (*this)
    return this->value();
  else
    return f();
}

These std::true_type and std::false_type are ‘tags’ defined in the Standard Library. A tag is an empty class. It contains no member and has no state: its purpose is to control (or “mess with”, if you will) the overload selection algorithm. You can use our functions like this:

int i = convert(t).value_or_(def, true_type{});

Are you familiar with brace-initialization syntax? While true_type is a type, true_type{} is an object. But this solution is silly. It is no better than having two different function names instead of two overloads. True; so let’s make it better:

template <typename U>
T value_or(U const& v) const
{
  return value_or_(v, std::is_convertible<U, T>{});
}

And that’s it. Let’s see what is going on here. You already know type trait std::is_convertible, but this time we are using it without referring to its static member value. This is how type traits work in the Standard Library. If the condition they represent for the given types (U being convertible to T in our case) holds, the trait is derived from true_type; if not, it is derived from false_type. This makes true_type and false_type represent boolean values — however, the values are not encoded as different bit patterns stored in memory, but as different types.

Thus, based on the value of std::is_convertible<U, T>{}, we dispatch the call to either of the two overloads. Everything works fine now:

int i = convert(t).value_or(def);
// picks the right overload

You can see the full working example here.

Working solution: enable_if

Tag dispatching is not the only clever solution to our problem. Let’s explore another possibility: enable_if. Our overloaded functions return T. We will change the return type a bit. Don’t get scared off. We will explain everything step by step.

#include <type_traits>

template <typename U>
typename std::enable_if<is_convertible<U, T>::value, T>::type
value_or_(U const& v) const
{
  if (*this)
    return this->value();
  else
    return v;
}

template <typename F>
typename std::enable_if<!is_convertible<F, T>::value, T>::type
value_or_(F const& f) const
{
  if (*this)
    return this->value();
  else
    return f();
}

Let’s focus on the first overload for now. Its return type is of the form:

typename std::enable_if<_ARGUMENTS_>::type

This is how in C++03 type meta-functions work. You pass some arguments into the class template, and get a type in return. Do you know why we need to type this typename? If you do not, just believe me that you have to type it. This is how templates work in C++: in certain cases you need to hint the compiler that type is a type rather than a static data member.

So, what are the two arguments that meta-function enable_if takes? The first one is a compile-time constant of type bool. Just some compile-time value. It represents a condition. The second argument is a type (rather than value). If the condition is true, the nested type type is same as this second template parameter. If the condition is false the nested type type is not defined. For example, the following construct:

typename std::enable_if<true, T>::type

really means “type T”. But the following one:

typename std::enable_if<false, T>::type

is just ill-formed: we are trying to access a type that doesn’t exist. But what is it good for? Let’s get back to our function signature:

template <typename U>
typename std::enable_if<is_convertible<U, T>::value, T>::type
value_or_(U const& v) const;

When the overload resolution mechanism tries to consider this function if it is a good match: when U is convertible to T, this signature is really equivalent to:

template <typename U>
T
value_or_(U const& v) const;

But when U is not convertible to T, the declaration is simply malformed. However, this is a special case of malformed-ness that happens during overload resolution for which special rules in the language apply. The gurus call it SFINAE. In our case it means that the compiler will pretend this overload just isn’t there and try to look for other ones. It will find the other overload, and because the other overload uses the opposite condition (note the usage of operator!), the compiler will have a good unambiguous match. Thus based on the result of the meta-function is_convertible compiler will always see only one overload: either the first or the second, and will never have an ambiguity. For a full example see here.

There is also another way to solve our problem with enable_if without having to spoil the return type. But while the two solutions described so far will work back in C++03 if you use Boost.TypeTraits and Boost.EnableIf instead of C++11 header <type_traits>, the third way will only work in C++11. You can see the example here. Even more, in C++11 we can do it without a single enable_if in our class, as suggested by Paweł Turkowski: see here. There is no room to discuss it in detail in this post.

Is this a valid goal?

Ok, so we explored a couple of clever tricks; now let’s get back to our original problem statement. An ‘intelligent’ function value_or that (upon the attempt to access a missing value) first tries to convert the argument to T, and if it doesn’t work it tries to check if the argument can be called as a function and use its result. Is is a good idea to have an intelligent function like this that tries to figure out what your intentions were? After all, you can have two functions that do these two different things:

int i = convert(t).value_or(0);
int j = convert(t).value_or_eval(&log_and_continue);

So far, I have avoided an important problem with how our task is formulated. There exist types U which are both convertible to T and callable with zero arguments — which way should our intelligent function pick then? Also, there are types that are neither callable nor convertible to T. What do we want to do for these? Fail with an error message, I guess, but what message? “U not convertible to T”? “U is not a funcction”? “U is neither convertible to T, nor is it a function”? “no function value_or found for this U”? Depending on what your answer to these two questions is, you might want a different design for your function overloads. If you are using tag dispatching, you will need a four-state tag or two boolean tags. If you are using enable_if, you may need to add more complicated conditions, like:

std::is_convertible<U, T>::value && !is_generator<U, T>::value

I use the name Generator after SGI’s STL Programmer’s Guide. It represents a zero-argument function returning a value of type T. But it is not even defined in the Standard Library. We would have to write it ourselves.

Tag dispatching vs enable_if

Our example above is rather controversial. But it served my goal well: to compare how the two techniques solve the same problem. Typically, however, the two techniques solve different kinds of problems.

Tags need not be true-or-false; they can form a hierarchy (in OO sense); this enables the rules of overloading similar to these when we pick between the derived and base class. STL uses this for overloading (e.g. function std::advance) based on iterator categories. Iterator categories are represented by tags:

struct input_iterator_tag{};
struct output_iterator_tag{};
struct forward_iterator_tag: input_iterator_tag{};
struct bidirectional_iterator_tag: forward_iterator_tag{};
struct random_access_iterator_tag: bidirectional_iterator_tag{};

These tags are embedded in the iterator traits. And now, if we implement two overloads for tags input_iterator_tag and random_access_iterator_tag, all iterators in between like BidirectionalIterator will be dispatched to the overload with input_iterator_tag tag. And in the case of STL algorithms, they are overloaded not in order to do different things (like in our task), but to do the very same thing more efficiently. For more details on this see here.

The enable_if technique is good when you want to disable some overload in certain cases and enable nothing instead. For instance, we used it to fix the “too perfect forwarding” problem.

Beware of your dark nature!

If you have read this far, it seams I got you interested in these techniques. Let me warn you then. I only showed you that such techniques exist. I really do not recommend employing them in your code (unless there is some really good reason to do so). I spent quite a while figuring out why one of the enable_if examples in this post didn’t compile. I solved the problem with value_or in Boost.Optional by adding a function with a different name: value_or_eval. Even if you accept the complexity you intend to add, consider your colleagues. You will put a burden of complicated, magical code not only on yourself, but also on everyone that ever has to read or fix your code. Have mercy. The noble goal of programming is to make the programs simple — not complicated.

Further reading

  1. Jaakko Järvi, Jeremiah Willcock, Andrew Lumsdaine, Matt Calabrese, Boost.EnableIf.
  2. John Maddock, Steve Cleary, et al, Boost.TypeTraits.
  3. David Abrahams, “Ceneric Programming Techniques”.
  4. David Abrahams, Douglas Gregor, “Generic Programming in C++: Techniques”.
  5. John Maddock, Steve Cleary, “C++ Type Traits”.
  6. Jaakko Järvi, Jeremiah Willcock, Howard Hinnant, Andrew Lumsdaine, “Function Overloading Based on Arbitrary Properties of Types”.
  7. Andrew Sutton, Bjarne Stroustrup, Gabriel Dos Reis, “Concepts Lite: Constraining Templates with Predicates”.
  8. Bjarne Stroustrup, Gabriel Dos Reis, Andrew Sutton, “«Static If» Considered”
  9. Andrew Sutton, Bjarne Stroustrup, Gabriel Dos Reis, “Concepts Lite”.
  10. Andrew Sutton, “Working Draft, C++ Extensions for Concepts”.
  11. R. Martinho Fernandes, “Remastered enable_if”.
  12. R. Martinho Fernandes, “To SFINAE or not to SFINAE”.
  13. Xeo, “Beating overload resolution into submission”.
  14. Andrzej Krzemieński, “Meta-functions in C++11”.
This entry was posted in programming and tagged , , , , . Bookmark the permalink.

24 Responses to Clever overloading

  1. mvpete says:

    Just a quick question on this line.

    std::string get_text();
    std::string s = get_text().value_or("n/a");
    

    Is it supposed to be optional<std::string> get_text(); ?

  2. grisha says:

    Hi,
    in your examples if U is not convertiable to T, then it’s a callable object. Is it for simplifiing ?
    Or you do not want to explain about something like is_callable: http://stackoverflow.com/questions/15393938/find-out-if-a-c-object-is-callable ?

    Thanks

    • @grisha: Thanks for the link. Yes, I do it for making the problem simple enough. I even explain it at the end. And yes, I do not want to describe how to implement is_callable, as this is a subject for another post. More, I do not want U to just be callable, I want it to be callable with zero arguments and return a value convertible to T.

  3. I think decltype-based sfinae is also an option here.

  4. Marek says:

    Did not finished the article but what if F returns an U (convertible to T) and F is also convertible to T? Are then F and U interchangeable? Not sure if the code is correct, but consider this:

    class A {
    public:
    operator int(){return 1;}
    int operator()(){return 2;}
    };

    std::optional get_result(); // defined elsewhere
    std::optional result = get_result();
    int i = result.value_or(A{});
    // What contains i in case of result contains no value, 1 or 2?

  5. Paweł says:

    Bit simpler solution: http://ideone.com/iFnFJD

  6. ColonelSammy says:

    That’s a great article…in fact it’s so interesting that I wrote a follow up that does the same thing but in a different way. Hopefully this will be published in ACCU Overload soon…I’ll be referencing your article so please let me know if that’s a problem.

  7. Ophir says:

    Regarding the line from optional::value_or()

    if (*this)

    This makes sense only if the method may be called over a null pointer to an object of type optional, but isn’t doing so result in undefined behavior?

    • This notation is correct. The confusion stems from optional’s interface, which uses contextual conversion to bool to indicate if it contains a value. If optional had member function contains_value(), the example would read:

      if (this->contains_value())
      

      But because optional defines explicit operator bool() instead, the corresponding usage is:

      if (this->operator bool())
      

      or equivalent variants:

      if ((*this).operator bool())
      
      if (bool(*this))
      
      if (*this)
      

      In neither case is this null.

      • Ophir says:

        Thanks. Oddly (and embarrassingly…) I kept looking at
        if (*this)
        and seeing
        if (this)
        By the way, your blog is great.
        Ophir

  8. Aurelien says:

    Hello,
    What about an emplace like overload of value_or? I miss being able to write that :

    optional<tuple<int, double>> f();
    auto t = f().value_or(0, 0.0);
    
  9. viboes says:

    I like the value_or_eval interface. When we want a constant, we can pass

    o.value_or_eval(constant(0));
    

    But adding constant is a little burden.

    I know that this post is not promoting the use of SFINAE, but we could consider an alternatively interface based if we consider a value as a `Nullary` function.

    If value_or takes as parameter `X` those evaluation is convertible to `T`. The evaluation of a nullary function consists in calling the function, the evaluation of a value is he value itself.

    template <typename Nullary>
    T eval(Nullary const& f) 
    requires ...  // the result of evaluating f is convertible to T
    { return f(); };
    
    template <typename Value>
    requires ...  // v is convertible to T
    T eval(Value const& v) { return v; };
    

    With this eval the generic function value_or is a simple as

    // ...
      template <typename X>
      T value_or(X const& v) const
      {
        if (*this)              // initialized?
          return this->value(); // get contained value
        else
          return eval(v);
      }
    
  10. viboes says:

    @Aurelian You emplace value_or version can be achieved easily making it variadic and forwarding to a variadic eval function that just constructs a T with the forwarded arguments.

    @Andrzej I don’t know if you can edit my previous comment, the code needs some format changes.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s