Ultra Strong Typing

Picture a library. QuantLib. Imagine it has an overloaded function

void f(unsigned int a) {}
void f(unsigned int a, unsigned int b) {}

which is used like this in client code

f(0);
f(0,0);

Now you want to extend the function adding an additional parameter. For backward compatibility you give it a default value.

void f(unsigned int a, double t = 0.0) {}
void f(unsigned int a, unsigned int b, double t = 0.0) {}

Compiling the client code above results in a compiler complaint, g++ for example says

testoverload.cpp:6:10: error: 
   call of overloaded ‘f(int, int)’ is ambiguous
     f(0,0);
          ^
testoverload.cpp:1:6: note: 
   candidate: void f(unsigned int, double)
 void f(unsigned int a, double t = 0.0) {}
      ^
testoverload.cpp:2:6: note: 
   candidate: void f(unsigned int, unsigned int, double)
 void f(unsigned int a, unsigned int b, double t = 0.0) {}
      ^

This is because the arguments 0 are int‘s, so not directly matching any signature exactly. Therefore the compiler tries to convert the arguments to match one of the signatures. However int can both be converted to unsigned int and double, which causes the ambiguity. One can resolve the error by changing the call to

f(0,0.0);

or

f(0u,0u);

or even

f(0.0,0.0)

or

f(0.0,0u)

all of which have one signature strictly better matching than the other, since only requiring conversion of at most one (instead of both) of the arguments while the other is already exactly matching.

Does that help ? No, since the new code should work with existing client code out of the box. That is the whole point of backward compatibility.

What we can do is to apply the SFINAE technique I wrote about in an earlier post. We make the second parameter a template parameter

template<class T>
void f(unsigned int a, T t = T(0.0)) {}

template<class T>
void f(unsigned int a, T b, double t = 0.0) {}

and then use meta programming to switch the function definition on and off depending on the type T

#include <boost/utility/enable_if.hpp>
#include <boost/type_traits/is_float.hpp>
#include <boost/type_traits/is_integral.hpp>

template<class T>
void f(unsigned int a, T t = T(0.0), 
 typename boost::enable_if<
                 boost::is_float<T> >::type* = 0 ) {}

template<class T>
void f(unsigned int a, T b, double t = 0.0, 
 typename boost::enable_if<
                 boost::is_integral<T> >::type* = 0) {}

Remember that boost::enable_if<b>::type is either void (when b is true, i.e. when T is a float or integral type respectively) or nothing. If it is nothing it causes a potential compiling error.

However since we are in the process of trying template substitutions here, the whole function definition is just silently discarded from the set of possible template incarnations (“substitution failure is not an error”, SFINAE). What is left is the one function definition we actually want depending on T.

The code then safely chooses the upper definition if we pass a float type like double or float as the second parameter and the lower one for an integral type like int, unsigned int, std::size_t and so on.

Quite heavy machinery to solve an easy problem.

Ultra Strong Typing

Interlude: SFINAE tricks

Hello again. This week I want to write about a point which remained open in a previous post . Jan Ladislav Dussek already gave a solution in response to the post. Thanks for that! However I believe the technology behind is quite fancy so worth a post in its own right.

What are the news apart from that? There is a second project adding AD capabilities to QuantLib following a different approach than described earlier in this blog. The idea is to just replace the Real datatype by active AD types at compile time and use them throughout all calculations. This only requires minimal code changes compared to the template approach.

The downside is that you can not mix AD and non-AD calculations during runtime which might have an impact on performance and / or memory footprint of your application.

My personal experiments show a 20 – 30 % slowdown in some simple examples but maybe this can be optimized. Or maybe this isn’t too bad and a small price to pay in comparison to the work needed to convert large parts of the codebase. Another question is whether the templated code can or should be merged into the official branch earlier or later. If not it would be quite cumbersome to keep an adjoint branch up to date with current developments. But not impossible.

Anyway it is interesting to note that the work on the new approach was initiated by Alexander Sokol and his company CompatibL. So quite a competitor. Like running a marathon with Dennis Kimetto (he ran a new world record in 2:02:57 last year in Berlin, a time in which I can safely run half the way, well a bit more but not much). Why not. We are still on track, aren’t we Cheng (whom I thank for his tireless contributions). 🙂

Back to the main point of this post. I first restate the problem in a bit more abtract way. We have the following classes on stage

template <class T> class BaseCouponPricer {};
template <class T> class DerivedCouponPricer : 
                      public BaseCouponPricer<T> {};

where the base class in QuantLib is really FloatingRateCouponPricer and the derived class something like CmsCouponPricer or IborCouponPricer or the like.

Now we have a utility function assigning coupon pricers to coupons

template <class T>
void setCouponPricer(const boost::shared_ptr<BaseCouponPricer<T> > &) {
    return;
}

taking a shared pointer to some pricer derived from our base class. Without the template stuff this is not a problem because there is an implicit conversion defined from a shared pointer to D to a shared point to B if D inherits from B. Although – and this is important to note – there is no inheritance relationship between the shared pointers themselves implied. And this is the whole source of the problem because user code like this

boost::shared_ptr<BaseCouponPricer<double> > basePricer;
boost::shared_ptr<DerivedCouponPricer<double> > derivedPricer;
setCouponPricer(basePricer);
setCouponPricer(derivedPricer);

will result in a compiler error like this

testTempl.cpp:35:34: error: no matching function for call to ‘setCouponPricer(boost::shared_ptr<DerivedCouponPricer<double> >&)’
     setCouponPricer(derivedPricer);
                                  ^
testTempl.cpp:35:34: note: candidate is:
testTempl.cpp:12:6: note: template<class T> void setCouponPricer(const boost::shared_ptr<BaseCouponPricer<T> >&)
 void setCouponPricer(const boost::shared_ptr<BaseCouponPricer<T> > &) {
      ^
testTempl.cpp:12:6: note:   template argument deduction/substitution failed:
testTempl.cpp:35:34: note:   mismatched types ‘BaseCouponPricer<T>’ and ‘DerivedCouponPricer<double>’
     setCouponPricer(derivedPricer);
                                  ^
testTempl.cpp:35:34: note:   ‘boost::shared_ptr<DerivedCouponPricer<double> >’ is not derived from ‘const boost::shared_ptr<BaseCouponPricer<T> >’

where the essential message is in the last line. This was produced with gcc, clang is a bit less chatty (which is a good quality in general)

testTempl.cpp:35:5: error: no matching function for call to 'setCouponPricer'
    setCouponPricer(derivedPricer);
    ^~~~~~~~~~~~~~~
testTempl.cpp:12:6: note: candidate template ignored: could not match 'BaseCouponPricer' against
      'DerivedCouponPricer'

The implicit conversion mentioned above does not help here because it is not taken into consideration by the compiler’s template substitution machinery.

The idea to solve this is to make the implementation more tolerant, like this

template <template<class> class S, class T>
void setCouponPricer(const boost::shared_ptr<S<T> > &) {
    return;
}

now taking a shared pointer to any type S which itself takes a template parameter T. This compiles without errors. But now the door is open for code that do not make sense because S could be something completely different from a pricer.

What we need is some check at compile time for class inheritance. The boost type traits library (or since C++11 the std library itself) has something for this, namely we can write

bool isBase = boost::is_base_of<BaseCouponPricer<double>, 
                                DerivedCouponPricer<double> >::type::value;

Here we use generic template programming which is something like programming with types instead of values and where the function evaluation is done during compilation, not at run time. The function we use here is boost::is_base_of which takes two arguments and the return value of this function is itself a type which we can retrieve by ::type.

Since there is no such thing like a function taking type arguments and returning a type in C++ (and which in addtion is evaluated at compile time), ordinary struct‘s are used for this purpose taking the input values as template parameters and providing the return value as a typedef within the struct assigning the label type to the actual return value which is, remember, a type.

In our specific case we are expecting a boolean as the return value so the return type has to represent true or false, and it does. Actually there is a wormhole from the meta programming to the regular C++ space, yielding an usual bool, and this is via ::value which unpacks a boolfrom its meta space wrapper which stores it just as a static constant.

If on the other hand we write

bool isBase = boost::is_base_of<BaseCouponPricer<double>, 
                                UnrelatedClass<double> >::type::value;

for an unrelated class (i.e. a class not derived from BaseCouponPricer) we get isBase = false.

But we are not done, the best part is yet to come. I just begin with the end result because I don’t have a clue how people come up with these kind of solutions and am reluctant to think of a motivating sentence

template <template <class> class S, class T>
void setCouponPricer(
    const boost::shared_ptr<S<T> > &,
    typename boost::enable_if<
        boost::is_base_of<BaseCouponPricer<T>, S<T> > >::type *dummy = 0) {
    return;
}

What I usually do when I see code like this for the first time is sit there for a few hours and just stare at it. And then after a while you see the light:

We add a second parameter to our function which is defaulted (to 0, doesn’t matter) so that we do not need to specify it. The only reason for this second parameter is to make sense or not to make sense, in the latter case just removing the function from the set of candidates the compiler considers as an template instantiation for the client code. What I mean by not ot make sense becomes clearer when looking at the implementation of boost::enable_if (I took this from the 1_57_0 distribution):

  template <bool B, class T = void>
  struct enable_if_c {
    typedef T type;
  };

  template <class T>
  struct enable_if_c<false, T> {};

  template <class Cond, class T = void> 
  struct enable_if : public enable_if_c<Cond::value, T> {};

The function (struct) enable_if takes one input parameter, namely Cond standing for condition. This parameter is a type since we are doing meta programming but the implementation derefences the value via ::value just as we did above for testing and passing it to the implementing function enable_if_c. Passing means inheritance here, we are programming with struct‘s (with difficult topics I tend to repeat myself, bear with me please).

The second parameter T defaulted to void does not play any important role, it could just be any type (at least in our application here). The return value from enable_if_c is this type if the input parameter is true or nothing if the input parameter is false. This is implemented by partial template specialization, returning (by declaring a typdef for) T = void in the general definition but nothing in the specialization for B = false.

Now if nothing is what we get as the return value ::type, i.e. there is no typedef at all for the return value, the expression for our second dummy parameter from above

typename boost::enable_if<
        boost::is_base_of<B,D> >::type *dummy = 0

does not make sense since without a ::type we can not declare a pointer to it. If type is void on the other hand the expression makes perfect sense. One could add that a non-existent ::type in the meta programming space is what void is in the regular programming space. Not very helpful and just to confuse everyone a bit.

The first case when ::type is void is clear now, the function is just taken by the compiler to instantiate the client code function. And this is the case if our earlier condition checking for the inheritance relationship is true.

If this is false on the other hand a senseless expression is born during the template substitution process and therefore discarded by the compiler for further use. This is also know as SFINAE which stands for substitution failure is not an error, you can read more about that here.

The test code for the whole thing is as follows

boost::shared_ptr<UnrelatedClass<double> > noPricer;
boost::shared_ptr<BaseCouponPricer<double> > basePricer;
boost::shared_ptr<DerivedCouponPricer<double> > derivedPricer;

setCouponPricer(noPricer); // compile error
setCouponPricer(basePricer); // ok
setCouponPricer(derivedPricer); // ok

This is all a bit crazy and sounds like exploiting undocumented language features, not meant for those purposes. And probably it was in the beginning when meta programming was discovered. But it’s obviously widely used nowadays and even necessary to comply with the already classic C++11 standard.

Which we just discussed yesterday when talking about C++11 – compliant random number generators. Here is an interesting one by Thijs van den Berg. In chapter 26.5.1.4 / table 117 of the C++11 standard n3242 it says that you must provide two seed methods, one taking an integer and an addtional one taking a sequence generator. Since the signature of both methods is overlapping the only way of telling whether you have an integer or a sequence generator is by using techniques like the ones above. And so did Thijs in his code. So better get used to it, I guess.

By the way compile time calculations are quite popular. There is even a template programming raytracer. I might port some QuantLib pricing engines to compile time versions if the adjoint project should die for some reason.

The final implementation of setCouponPricers in the real code now looks as follows

template <template <class> class S, class T>
void setCouponPricers(
    const typename Leg_t<T>::Type &leg,
    const std::vector<boost::shared_ptr<S<T> > > &pricers,
    typename boost::enable_if<boost::is_base_of<FloatingRateCouponPricer_t<T>,
                                                S<T> > >::type *dummy = 0) {
/* ... */
}

Again a good example that templated code together with some dirty generic programming tricks does not necessarily loose readability.

Interlude: SFINAE tricks