2011-05-22

Specifications, part IV

In the previous post I talked about how to write specifications for virtual functions. This post is about second C++ mechanism which uses new code as a tuning for the old one: templates.

Templates are probably the most important C++ abstraction-building tool: they allow constructing amazingly powerful abstractions without incurring run-time and memory penalties, and don't lose type information along the way. I think they should be preferred over virtual functions whenever run-time dispatching is not necessary (choosing one or another is the topic of separate blog post in the future though).

Specify template parameters

Often class and function templates (and member-function templates, and member-functions of class templates) expect their template parameters to have some properties. As usual, it is better to be explicit in what is expected.

Consider following template:

    /// prints its argument
    template <class T>
    void f(T t)
    {
        t.print();
    }

The code doesn't make sense if type T has no member-function template print which can be called without arguments. So it's better to put it in the documentation of function template f:

    /// prints its argument
    /// \pre T has a member-function print which can be called without arguments
    template <class T>
    void f(T t)
    ...

(Note that it is wise specify absolute minimum -- I'm talking about function print that can be called without arguments, not about print that has no arguments.)

This example is somewhat contrived: if client programmer misuses f compilation error will occur.
Sometimes though deciphering compilation error get tricky as instantiation that causes error is deep burried in the call stack. With that kind of things template parameters constraints help: you can have your types checked by type system, and as close to source of violation as possible. Read this Bjarne Stroustrup's faq for that.

And what is more important, compiler cannot verify everything: it verifies syntax and basic things (like presence of print() with compatible signature). But it will not help you with semantics that is not expressed in C++ type system. Examples of these ones are complexity, exception guarantees, specific side effects, commutativity/associativity of operation etc.

Consider std::vector<>. It requires that type of elements it holds is CopyConstructible, and CopyConstructible means specific semantics besides mere presence of publicly available copy-constructor. If you violate this requirement while instantiating std::vector with std::auto_ptr<SomeType>, you don't get any compilation error. Instead, you get undefined behavior (which in this case can be crash at runtime).

Another example of "semantic requirements" is usual requirement imposed on any clean-up function, and on user-defined swap operation to not throw: otherwise generic transactional code is impossible to implement correctly.

Third example is user-defined template that operates on container and promises O(N) run-time in terms of number of elements in the container:

    /// \pre Container is STL-like container
    /// \pre Op is the class that provides context-aware operator() with parameters
    ///      of types convertible to Container and to the type held by Container
    /// \post run-time complexity is O(c.size())
    template <class Container, class Op>
    do_something(Container& c, Op f)
    {
        for (c::const_iterator it = c.begin(); it != c.end(); ++it)
           f(c, *it);
    }

Note, that for keeping its promise, it should in general require that Op::operator() itself has the run-time complexity of O(1)! If all you have is do_something declaration and comments, you should specify it as well.

As with virtual functions, specification of template is only one part for ensuring correctness. Another one is of course providing type parameters that satisfies the specification.

No comments:

Post a Comment