ACCU Home page ACCU Conference Page ACCU 2017 Conference Registration Page
Search Contact us ACCU at Flickr ACCU at GitHib ACCU at Google+ ACCU at Facebook ACCU at Linked-in ACCU at Twitter Skip Navigation

pinLetters to the Editor(s)

Overload Journal #60 - Apr 2004 + Letters to the Editor   Author: Simon Sebright

Testing Templated Code

I've just read Mark Radford's editorial in the recent edition of Overload, and felt some unease at the rather sweeping statement that having templated code means you only have to test it once. True, there is only one set of code rather than a lot of similar copies, any one of which could later be independently tweaked.

But, if a template algorithm works fine with one type, there's no guarantee it'll work fine with another type. Assuming it compiles, then the provided type conforms to the required interface, but the implementation of that interface is in the hands of its provider, and clearly affects the result of running the algorithm on that type. Now, a counter argument might be that there are well-defined requirements for some sorts of system, e.g. value types should be default constructable, etc., which would aim to help out, but there's no accounting for problems in the implementation of even relatively simple requirements.

I also thought of another category of potential problem. If the template algorithm uses named functions of a type, then it's going to be pretty clear what functions get called (leaving aside polymorphic behaviour), but if the algorithm is using operators, then it might not be running the same code for different types. For example, suppose there is a global operator+ in place, which most types are using and the algorithm is adding instances together. That's all fine, but what happens when the supplied type implements its own operator+? I don't actually know off the top of my head what'll get precedence (if there isn't an ambiguity), but you can see the problem.

Having used pre-template compilers in the past (a situation like the hypothetical management banning them), we occasionally resorted to macros (with all their inherent problems) to synthesise template behaviour on relatively simple functions which we wanted implemented for lots of types.

Mark Radford's Reply

Thanks to Simon for taking the time to write in. I'm flattered that my first attempt at writing the editorial prompted someone to write in! Now of course, it falls on me to respond.

Let me paraphrase Simon's first point: the fact that a template works with one type is no guarantee it'll work with another, and further, a specialisation may compile ok but the implementation could do anything. Now I agree, a misbehaving implementation would certainly throw a spanner in the works, but let us note in passing that the issue is not specific to templates. For example, a (non-template) function could take advantage of run-time polymorphic behaviour by taking, as a parameter, a pointer/reference to an abstract base class. The same issue applies here with regard to the overriding of a virtual member function.

In the case of implementation supplied by either a template argument or the overriding of a virtual function, there is a requirement for a kind of specification that cannot be enforced at compile-time. The compiler can check syntax, and it can to some extent check semantics, but it can only check the semantics that can be represented in the code. What is at issue here is the specification of run-time behaviour - and when run-time behaviour happens, the compiler is no longer watching.

We clearly need to look elsewhere for help, and it presents itself in the form of design by contract - a term coined because of an analogy with legal contracts: a software routine can have contractual obligations placed on its input that must be met in order for it to behave correctly. Now, there are static aspects to such contractual obligations in terms of the syntax and semantics of a types interface, but that's not the end of the story, for contractual obligations extend well into run-time behaviour. By way of an example, let's take a look at the sorting algorithms in the C++ standard library, and more specifically, at the comparison operation (which may be in the form of operator< or a predicate, depending on the algorithm overload selected) used to determine the sorting order.

The C++ standard states (in section 25.3) that in order for a sorting algorithm to work properly the comparison function must induce a strict weak ordering on the values compared. Note that code using the sorting algorithms will compile without error even if the strict weak ordering requirement is not met. The comparison function could return a hard coded value of true every time and compilation would be unaffected - but this would render all bets off at run-time. With this contract specification in place, sort algorithms can be tested using objects of a specimen type designed to test the algorithm - the order into which these objects should be sorted is known in advance (as part of their design), and they can be sorted from various random orders and the post sort sequence checked to see if it is what is expected. It is important here to note exactly what is being tested: the template! It is the logic encoded in the template itself that is tested, to demonstrate that it honours its (behavioural) contractual obligation, provided the supplied argument object honours the contractual obligations of the parameter type.

Simon also makes a point about operators: specifically, what happens if the template uses an operator and there are other, unexpected overloads of the same operator in scope? This issue isn't peculiar to operators - especially when argument dependent lookup (ADL) gets in on the act. Anyway, with regard to templates (actually it's not just templates, but here it is templates with which we are concerned), ADL and overloading combine to make up the compiletime polymorphic behaviour of the template parameter's types interface. Now I have already argued that for a template to work properly its argument objects must honour the contractual obligations placed on their respective parameter types - and that's exactly what I'm going to do again here! When I first brought design by contract into this response I mentioned that although contractual obligations extend well into run-time behaviour, they start with compile-time semantics. Compile-time polymorphism is part of the set of semantics that constitute the (compile-time) contractual obligations on template parameter types, and places responsibility for the correct overload selection firmly with the parameter type designer.

As Simon indicates, the correct behaviour of parameterised code is dependent on its argument types also behaving correctly. However, fundamental design principles such as separation of concerns, encapsulation and design by contract all form symmetry - that is, the presence of all of them forms something very robust but things become very fragile in the absence of any. The testing of components is a practice that relies on this symmetry to be intact, but as long as the symmetry is intact, components can be tested individually - the symmetry is comprised of the rules governing the interplay between components, and not the interplay between actual components themselves. Therefore, any particular component can be tested to verify it is fulfilling its part of the bargain, and if it is it can do no more and the rest is up to the other participants.

Overload Journal #60 - Apr 2004 + Letters to the Editor