Constrained Templates

June 12, 2010

written by Walter Bright

Templates have evolved from humble beginnings as “parameterized types” to a startlingly powerful abstraction tool. Naturally, this abstraction ability gets pushed hard, and gaps and weaknesses show up. Template constraints in the D programming language plug one of those gaps in a simple, intuitive way.

The gap comes from a template for a function being defined as having an argument `t` of type `T`, where type `T` is not specified. For a simple example, consider a function that computes the greatest common denominator using Euclid’s algorithm:

T gcd(T)(T a, T b) {
    while (b) {
        auto t = b;
        b = a % b;
        a = t;
    }
    return a;
}

The template is used like:

auto x = gcd!(int)(16, 4);

and is instantiated with `T` being replaced with the `int` type.

That looks easy enough. What could go wrong?

First off, from looking at the body, the type `T` must support the `%` operation. If it is instantiated like this:

int y;
auto x = gcd!(int*)(&y, &y);

The template is instantiated, and the expression in the template body:

b = a % b;

will fail with a message that looks like:

Error: incompatible types for ((a) % (b)): 'int*' and 'int*'

and a line number pointing into the template body. The error is being reported as occurring somewhere other than where the actual problem is, which is that gcd is being instantiated with a wrong type. While this example is trivial and hence easy to figure out, once templates get more complicated, with nested instantiations, the error messages can get increasingly removed from where the real problem is, and harder and harder to figure out.

What we’d really like to do is somehow constrain the template parameter type `T` so that it can only be types that are modulus-able. At first thought, this is a daunting requirement. How could this be expressed? At second thought, why not express the requirement the way one would use it?

T gcd(T)(T a, T b) if (is(typeof(a % b))) {
    ...
}

The if-clause following the template declaration is called a template constraint. If it isn’t satisfied, the template is not instantiated. If there is no other overload of `gcd` that is satisfied, the compiler emits an error message then and there that the type argument for `T` does not satisfy the constraint. Presumably this is far more direct and useful than the former method of some arbitrary message coming out from deep within the template body. Furthermore, one can have many overloads of `gcd` that accept different kinds of `T`, so it isn’t just for error messages.

But there are a couple oddities in the constraint, so let’s break it down. First off, everything in the if-clause is standard D expression stuff. Next:

What is the value of `a`? It doesn’t matter, it’s arbitrary. In an if-clause, the use of parameters makes for convenient stand-ins for instances of their corresponding types. If more are needed, the idiom:

T.init

may be used. Every type has a default initializer for it, and the idiom `T.init` represents that. In C++, one would equivalently represent it as `T()`. In this if-clause, it’s used as an arbitrary literal of type `T`.

a % b

This expression attempts to compute the remainder of two values of type `T` being divided. If the compiler successfully compiles it, we’re good to go. But if the compiler fails to compile it, shouldn’t it just issue an error message right then and there? Not exactly, I’ll explain in a moment.

typeof(a % b)

produces the type of the result of the modulus operation. (It works analogously to the `decltype(expr)` in C++.)

is(typeof(a % b))

This form of the is-expression takes a type as its argument, and returns a boolean of `true` if its argument is a valid type, and false if it is not. Here’s where the failure to compile `a % b` comes in. Failing to compile means the `typeof` fails to produce a valid type, and now the is-expression returns `false`. This then bubbles up to the if-clause, which is `false`, and the constraint is not satisfied.

There are more things our `gcd` template needs of its parameters; the result of the `%` must also be assignable to a type `T`, the type `T` must be usable as a boolean, and it must be assignable. So the constraint can express this by adding more constraints:

T gcd(T)(T a, T b) if (is(typeof(a = a % b)) &&
                       is(typeof(!b)) &&
                       is(typeof(a = b)))
{
    ...
}

The following capabilities:

arbitrary expressions can be in the if-clause, including function calls (that can be executed at compile time) and instantiations of other templates. These expressions follow the usual rules of D expressions.
the ability to test if an expression or type construct compiles successfully or not. Even statements can be used, if they are embedded inside a lambda function
the ability to execute functions at compile time

combine to bestow the ability to specify arbitrarily complex constraints using nearly the full power of the language. Best of all, the D programmer already knows how to do these things, so learning constraints is a simple extension of existing knowledge.

This isn’t just a theoretical exercise. Andrei Alexandrescu makes heavy and effective use of them in code like the D standard library’s algorithms implementation (see http://dsource.org/projects/phobos/browser/trunk/phobos/std/algorithm.d). For example, on line 342 we see:

void fill(Range, Value)(Range range, Value filler)
    if (isForwardRange!Range && is(typeof(range.front = filler)))
{
    ...
}

Here the template `fill()` takes a `Range` and sets all the elements in that range to `filler`. The constraints specify that:

the `Range` supports forward iteration
the `filler` can be assigned to members of the `Range`

All is not roses, though. More notable complaints against the constraint system:

The constraint is not checked against the template body to verify that all that is demanded of the template parameters is reflected in the constraint. This shouldn’t result in runtime bugs, though, because the worst case is one is left with the same situation as not having any constraints — an error message emanating from the template body as it fails to instantiate. While extra work, it is possible to unit test the constraint by writing a surrogage minimal type that satisfies only the constraint, and instantiating the template with it. Then, if the template body requires more of the type, the unit test will fail at compile time.
Because constraints are ad-hoc, there are no standard ways to communicate type information from authors to consumers. Thus, this information relies on idiom and convention, which may or may not become a scale problem in the future. In essence, they are duck typing.

Conclusion

Template constraints are a simple technique to solve one of the more vexing problems encountered when using complex templates. They are implemented, are used in real code, and work.

Acknowledgements

Thanks to Andrei Alexandrescu, Bartosz Milewski, and David Held for reviewing a draft of this.

Articles

Constrained Templates

Conclusion

Acknowledgements