The Policy Pattern

Previously I described some work I did to compare using three different sparse matrix libraries on a problem of interest to me. I wrote a complete and separate example for each library.

After I completed that post, I realized that the right way to organize my code was via the use of Policy classes to customize a single, templated main program with the three implementations. As long as each library was wrapped to present the same interface, I could use them generically via a template parameter.

For example, if I had access to three string libraries (say std::string, QString, and folly::String) I might write a function to capitalize a string like:

template<typename StringLibrary>
typename StringLibrary::string_t
allcaps(typename StringLibrary::string_t s) {
    return StringLibrary::toupper(s);
}

This code will work with any supplied StringLibrary class that has:

  • a nested type called string_t
  • a static method toupper that accepts a string_t and returns another

I might define a policy class that wraps std::string like this :

struct StandardString {
    using string_t = std::string;
    static string_t toupper(string_t s) {
        std::transform(
            s.begin(), s.end(), s.begin(),
            [](char c) { return std::toupper(c); });
        return s;
    }
};

I can now use StandardString as a template argument to allcaps and get the desired behavior:

int main() {
    std::cout << "foo is " << allcaps<StandardString>("foo") << "\n";
}

which prints foo is FOO.

I could wrap any other string type to make it usable with my function. As I write that code, I’d like the compiler to verify that I’ve satisfied the StringLibrary requirements. That’s where Concepts come in:

Concepts

A set of requirements on a data type has long been referred to (since the days of the STL) as a Concept. Dehnert and Stepanov is a good reference for the foundations. We are finally getting close to the point where we can express Concepts directly in the language with the advent of the Concepts TS, now landed in gcc 6.2. Using those language features, I might describe my above requirements this way:

template<typename L>
concept bool StringLibrary = requires(
        typename L::string_t s,              // temporaries used in expressions
        const char * cs
    ) {
    typename L::string_t;                    // required inner types

    // valid expressions
    { L::toupper( s ) } -> typename L::string_t;
    { typename L::string_t(cs) } -> typename L::string_t;

};

and then require that the concept be met in the using function with:

template<StringLibrary L>                    // just use the Concept name!
typename L::string_t
allcaps(typename L::string_t s) {            // as before
    return L::toupper(s);
}

If the embedded type is missing, cannot be constructed from a const char *, or has a toupper with the wrong signature, we get a compile error indicating that the StringLibrary Concept is not met, a vast improvement over the classic “template spew”.

Library-based Alternatives

There are a handful of versions of Concepts implemented as libraries. They lack the nice error messages of the TS but are available for most C++11 compilers. The ones I’m familiar with are:

  • The Boost Concept Checking Library. I managed to express all the constraints I had in the C++17 version with this; the final code actually #ifdef’s this in as an alternative to the TS for compilers that don’t support it. It’s been around long enough to support fairly old (C++03) compilers.
  • The author of the ranges-v3 library (the basis for the coming range support in C++17 and beyond) has a well-regarded Concept library which he describes here. This is probably a good choice for people with C++11 and later compilers.

Implementation Experience

Making the appropriate changes to work with Policies and Concepts was very instructive.

General Impressions

  • Doing this makes you think more clearly about program structure. I am becoming more and more convinced that the essence of good coding is choosing appropriate structure and interfaces. Concepts put a spotlight directly on those questions.
  • If you use the same code with more than one Policy you avoid some code duplication.
  • Concepts alert you to missing functionality. Much like with TDD, once a Concept is in place you can run your personal edit-compile-link loop until everything “passes”.
  • Failures can also point to areas where your chosen abstraction fails to match the available implementation.

Performance Issues

Having a fixed interface that wrapped libraries must conform to introduced some inefficiencies. In particular, requiring values passed between methods to always be the sparsemat_t type meant that sometimes extra conversions between dense and sparse were performed. It also meant that expression templates - a particular strength of Eigen - were not available. So this approach is best when interoperability, rather than performance, is your key goal.

One thing I couldn’t express

In constructing sparse matrices I want to be able to supply any sequence of “triplets” (row, column, value) so I would like to require that my sparse matrix library accept, e.g., a pair of ForwardIterators whose value type is a triplet. It is apparently impossible to express this constraint. Specifically, “constrained-type-specifiers are not permitted to declare parameters in requires expressions”, according to this bug report.

I ended up eliminating that constructor requirement from the SparseLibrary concept and adding one at the call site, for the actual iterators I was using.

Implementation Details that Affect the Interface

The SuiteSparse libraries had a funny usage requirement - a “common object” that contains settings and working storage for algorithms. Users are expected to supply a pointer to this object on every call. I had a few, mostly undesirable options:

  • Mimic this interface to the user so they have to supply a special object on every call. It would be empty for the other two libraries.
  • Have a “factory” in the interface that binds common objects to wrapped objects so they are implicitly supplied
  • Just create a static common object for the one library and let the wrappers use it.

I ended up choosing the third option, largely because this is an academic exercise.

Check out the Code

Source code for the Policy/Concept version of my sparse library examples can be found here. Feedback gladly accepted.