Channels ▼

Walter Bright

Dr. Dobb's Bloggers

Constrained Templates

June 12, 2010

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:

a

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:

1. 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.

2. 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

3. 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 std.algorithm). 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:

1. the Range supports forward iteration

2. the filler can be assigned to members of the Range

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

1. 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.

2. 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.

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

Related Reading


More Insights






Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

 
Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.
 


Video