Explain C++ SFINAE to a Python Guy

Question

What is SFINAE in C++? Can you please explain it in words understandable to a Python programmer? Also, what concept in Python does SFINAE in C++ correspond to?

Answer 1

If you have some overloaded template functions, some of the possible candidates for use may fail to be compilable when template substitution is performed, because the thing being substituted may not have the correct behaviour. This is not considered to be a programming error, the failed templates are simply removed from the set available for that particular parameter.

I have no idea if Python has a similar feature, and don't really see why a non-C++ programmer should care about this feature. But if you want to learn more about templates, the best book on them is C++ Templates: The Complete Guide.

Answer 2

There is nothing in Python that remotely resembles SFINAE. Python has no templates, and certainly no parameter-based function resolution as occurs when resolving template specialisations. Function lookup is done purely by name in Python.

Answer 3

Python won't help you at all. But you do say you're already basically familiar with templates.

The most fundamental SFINAE construct is usage of enable_if. The only tricky part is that class enable_if does not encapsulate SFINAE, it merely exposes it.

template< bool enable >
class enable_if { }; // enable_if contains nothing…

template<>
class enable_if< true > { // … unless argument is true…
public:
    typedef void type; // … in which case there is a dummy definition
};

template< bool b > // if "b" is true,
typename enable_if< b >::type function() {} //the dummy exists: success

template< bool b >
typename enable_if< ! b >::type function() {} // dummy does not exist: failure
    /* But Substitution Failure Is Not An Error!
     So, first definition is used and second, although redundant and
     nonsensical, is quietly ignored. */

int main() {
    function< true >();
}

In SFINAE, there is some structure which sets up an error condition (class enable_if here) and a number of parallel, otherwise conflicting definitions. Some error occurs in all but one definition, which the compiler picks and uses without complaining about the others.

What kinds of errors are acceptable is a major detail which has only recently been standardized, but you don't seem to be asking about that.

Answer 4

Warning: this is a really long explanation, but hopefully it really explains not only what SFINAE does, but gives some idea of when and why you might use it.

Okay, to explain this we probably need to back up and explain templates a bit. As we all know, Python uses what's commonly referred to as duck typing -- for example, when you invoke a function, you can pass an object X to that function as long as X provides all the operations used by the function.

In C++, a normal (non-template) function requires that you specify the type of a parameter. If you defined a function like:

int plus1(int x) { return x + 1; }

You can only apply that function to an int. The fact that it uses x in a way that could just as well apply to other types like long or float makes no difference -- it only applies to an int anyway.

To get something closer to Python's duck typing, you can create a template instead:

template <class T>
T plus1(T x) { return x + 1; }

Now our plus1 is a lot more like it would be in Python -- in particular, we can invoke it equally well to an object x of any type for which x + 1 is defined.

Now, consider, for example, that we want to write some objects out to a stream. Unfortunately, some of those objects get written to a stream using stream << object, but others use object.write(stream); instead. We want to be able to handle either one without the user having to specify which. Now, template specialization allows us to write the specialized template, so if it was one type that used the object.write(stream) syntax, we could do something like:

template <class T>
std::ostream &write_object(T object, std::ostream &os) {
    return os << object;
}

template <>
std::ostream &write_object(special_object object, std::ostream &os) { 
    return object.write(os);
}

That's fine for one type, and if we wanted to badly enough we could add more specializations for all the types that don't support stream << object -- but as soon as (for example) the user adds a new type that doesn't support stream << object, things break again.

What we want is a way to use the first specialization for any object that supports stream << object;, but the second for anything else (though we might sometime want to add a third for objects that use x.print(stream); instead).

We can use SFINAE to make that determination. To do that, we typically rely on a couple of other oddball details of C++. One is to use the sizeof operator. sizeof determines the size of a type or an expression, but it does so entirely at compile time by looking at the types involved, without evaluating the expression itself. For example, if I have something like:

int func() { return -1; }

I can use sizeof(func()). In this case, func() returns an int, so sizeof(func()) is equivalent to sizeof(int).

The second interesting item that's frequently used is the fact that the size of an array must to be positive, not zero.

Now, putting those together, we can do something like this:

// stolen, more or less intact from: 
//     http://stackoverflow.com/questions/2127693/sfinae-sizeof-detect-if-expression-compiles
template<class T> T& ref();
template<class T> T  val();

template<class T>
struct has_inserter
{
    template<class U> 
    static char test(char(*)[sizeof(ref<std::ostream>() << val<U>())]);

    template<class U> 
    static long test(...);

    enum { value = 1 == sizeof test<T>(0) };
    typedef boost::integral_constant<bool, value> type;
};

Here we have two overloads of test. The second of these takes a variable argument list (the ...) which means it can match any type -- but it's also the last choice the compiler will make in selecting an overload, so it'll only match if the first one does not. The other overload of test is a bit more interesting: it defines a function that takes one parameter: an array of pointers to functions that return char, where the size of the array is (in essence) sizeof(stream << object). If stream << object isn't a valid expression, the sizeof will yield 0, which means we've created an array of size zero, which isn't allowed. This is where the SFINAE itself comes into the picture. Attempting to substitute the type that doesn't support operator<< for U would fail, because it would produce a zero-sized array. But, that's not an error -- it just means that function is eliminated from the overload set. Therefore, the other function is the only one that can be used in such a case.

That then gets used in the enum expression below -- it looks at the return value from the selected overload of test and checks whether it's equal to 1 (if it is, it means the function returning char was selected, but otherwise, the function returning long was selected).

The result is that has_inserter<type>::value will be l if we could use some_ostream << object; would compile, and 0 if it wouldn't. We can then use that value to control template specialization to pick the right way to write out the value for a particular type.

Answer 5

SFINAE is a principle a C++ compiler uses to filter out some templated function overloads during overload resolution (1)

When the compiler resolves a particular function call, it considers a set of available function and function template declarations to find out which one will be used. Basically, there are two mechanisms to do it. One can be described as syntactic. Given declarations:

template <class T> void f(T);                 //1
template <class T> void f(T*);                //2
template <class T> void f(std::complex<T>);   //3

resolving f((int)1) will remove versions 2 and three, because int is not equal to complex<T> or T* for some T. Similarly, f(std::complex<float>(1)) would remove the second variant and f((int*)&x) would remove the third. The compiler does this by trying to deduce the template parameters from the function arguments. If deduction fails (as in T* against int), the overload is discarded.

The reason we want this is obvious - we may want to do slightly different things for different types (eg. an absolute value of a complex is computed by x*conj(x) and yields a real number, not a complex number, which is different from the computation for floats).

If you have done some declarative programming before, this mechanism is similar to (Haskell):

f Complex x y = ...
f _           = ...

The way C++ takes this further is that the deduction may fail even when the deduced types are OK, but back substitution into the other yield some "nonsensical" result (more on that later). For example:

template <class T> void f(T t, int(*)[sizeof(T)-sizeof(int)] = 0);

when deducing f('c') (we call with a single argument, because the second argument is implicit):

1. the compiler matches T against char which yields trivially T as char
2. the compiler substitutes all the Ts in the declaration as chars. This yields void f(char t, int(*)[sizeof(char)-sizeof(int)] = 0).
3. The type of the second argument is pointer to array int [sizeof(char)-sizeof(int)]. The size of this array may be eg. -3 (depending on your platform).
4. Arrays of length <= 0 are invalid, so the compiler discards the overload. Substitution Failure Is Not An Error, the compiler won't reject the program.

In the end, if more than one function overload remains, the compiler uses conversion sequences comparison and partial ordering of templates to select one that is the "best".

There are more such "nonsensical" results that work like this, they are enumerated in a list in the standard (C++03). In C++0x, the realm of SFINAE is extended to almost any type error.

I won't write an extensive list of SFINAE errors, but some of the most popular are:

• selecting a nested type of a type that doesn't have it. eg. typename T::type for T = int or T = A where A is a class without a nested type called type.
• creating an array type of nonpositive size. For an example, see this litb's answer
• creating a member pointer to a type that's not a class. eg. int C::* for C = int

This mechanism is not similar to anything in other programming languages I know of. If you were to do a similar thing in Haskell, you'd use guards which are more powerful, but impossible in C++.

---

1: or partial template specializations when talking about class templates