Sunday, September 21, 2008

Int-to-type idiom and infinite regress

A new writeup on Int-to-type idiom has been posted on More C++ Idioms wikibook. It is used to achieve static dispatching based on constant integral values. I'll finish the writeup of the idiom here with special attention to how int-to-type idiom can lead to infinite series of type instantiations and why. The idiomatic form of the Int-to-type idiom is given below.

template <int I>
struct Int2Type
{
enum { value = I };
typedef Int2Type<I> type;
typedef Int2Type<I+1> next;
};

The type typedef defined inside the template is the type itself. I.e, Int2Type<10>::type is same as Int2Type<10>. The next typedef gives the following type in order. However, compiler is not required to instantiate the next type unless and until two things happen: (1) an instance of the type is created or (2) an associated type is accessed at compile-time. For example, Int2Type<10> will be instantiated if one the following two things are written.

Int2Type<10> a; // a variable declaration.
typedef Int2Type<10>::type INT10; // accessing an associated type.

For kicks, lets see what happens if we add "::type" in the typedef of next.

template <int I>
struct Int2Type
{
enum { value = I };
typedef Int2Type<I> type;
typedef typename Int2Type<I+1>::type next; // Note change here.
};
int main (void)
{
Int2Type<10> i; // This instantiation will trigger an infinite chain.
}

For each instantiation of the Int2Type template, its "next" type is also instantiated because we are accessing the associated type defined inside the template. This leads to an infinite series of instantiations of the template with no end. Obviously, C++ compiler stops after predefined number of recursive instantiations with an error message. More formally, this problem is also known as infinite regress where the original problem reappears in the solution to the problem.

Tuesday, September 16, 2008

copy elision and copy-and-swap idiom

An updated writeup of the copy-and-swap idiom is now available on the More C++ Idioms wikibook. A comparison of two different styles of assignment operator is shown. First version accepts the parameter as pass-by-const-reference whereas the second version accepts it as pass-by-value. For some classes pass-by-value turns out to be more efficient as a copy of the object is elided when the right hand side is a rvalue.

Sunday, August 31, 2008

linked list using std::pair (infinite regression)

Defining a node of a linked-list using std::pair sounds as simple as drinking a Starbucks's white chocolate mocha. But it really isn't. Give it a try! The constraint is to use std::pair's first or second as a pointer to the structure itself, like in any linked-list's node. As far as I know, it is impossible unless you resort to ugly casts from void pointers. The problem is actually quite well known and gives rise to something known as infinite regress, where the problem you want to solve reappears in the solution to the problem.

typedef std::pair<int, /* Pointer to this pair!! */ > Node;

The closest thing I could come up with is something like the one below.

struct Node : std::pair <int, Node *>
{};

Node n;
n.second = &n; // A cyclic linked-list.

Wednesday, July 09, 2008

return void

I thought it would be interesting to discuss a subtle C/C++ interview question I learned recently. Question is deceptively simple: "Can you write a return statement in a function that returns void?" The answer is "Yes! You can return void!" The following program seems to be a valid C/C++ program.

static void foo (void) { }
static void bar (void) {
return foo(); // Note this return statement.
}
int main (void) {
bar();
return 0;
}

I tested it using gcc4 and VS9. With -ansi and -pedantic compiler options for gcc, it throws just a warning pointing at line #5.

return_void.c:5: warning: return with a value, in function returning void

Although use of such a feature is not clear in a C program, it is particularly useful while using templates. Consider,

template <class T>
T FOO (void) {
return T(); // Default construction
}

template <class T>
T BAR (void) {
return FOO<T>(); // Syntactic consistency. Same for int, void and everything else.
}

int main (void) {
BAR<void>();
}

It suddenly makes sense when templates are in picture. Take home point: Syntactic consistency is of paramount importance for supporting generic programming and writing generic libraries.

Saturday, June 14, 2008

Non-Virtual Interface and the Fragile Base Class Interface Problem

A new writeup on Non-Virtual Interface (NVI) idiom has been written on More C++ Idioms wikibook. In the writeup, I discuss the relationship of NVI with the Fragile Base Class (FBC) problem, which can silently break perfectly good derived classes because of some innocuous changes in the base class.

Monday, May 12, 2008

RSS Feed for More C++ Idioms Wikibook

The open-content wikibook "More C++ Idioms" has grown quite a bit from it inception. Whenever I get time, I try to add more contents in the book. So I always wanted to track the changes happening in the book in a convenient manner. Today, I put together a RSS feed for the book, which publishes recent changes made to the book. Thanks to the excellent technical support provided by existing wikibookians (if that is a word). The feed is formatted like two column GUI-based diff utilities (kdiff3, Beyond-compare). Frankly, it is not as readable and enjoyable as regular blog entries but at least it will help interested readers to know what new content is being added to the book and how the book making progress towards completion.

Tuesday, April 22, 2008

Redirecting C++ Truths feed

Dear readers,

Thanks for your continued interest in the C++ Truths blog and a steady stream of feedback comments. For quite some time now, I'm interested in learning accurate statistics about the readers of this blog. Recently, I came across, FeedBurner, which seems to be a popular choice for centralized feed processing and maintaining feed analytics such as subscriber count, live hits and many more things. Therefore, I have decided to redirect all the future contents on C++ Truths blog to the CppTruths feed. Existing atom and rss feeds shall be discontinued soon. I encourage you to subscribe to the new feed source and help me find the real subscriber count. In return, I promise to be more regular and frequent in posting more C++ truths, which you love to read!!

- Sumant.

Friday, January 04, 2008

Function Template Overload Resolution and Specialization Anomaly

I recently realized that function template overloading and function template specialization can interact with each other in complex ways giving rise to quite surprising C++ programs. Consider,

template<class T> // (a) a base template
void f( T ) {
std::cout << "f(T)\n";
}

template<>
void f<>(int*) { // (b) an explicit specialization
std::cout << "f(int *) specilization\n";
}

template<class T> // (c) another, overloads (a)
void f( T* ) {
std::cout << "f(T *)\n";
}

int main (void) {
int *p = 0;
f(p);
}

Output of the above program is "f(T *)" (i.e. (c) is invoked in main). Now simply swap the order in which (b) and (c) are written. The output of the program changes! This time it invokes (b) giving output as "f(int *) specilization".

The reason behind it is that when the integer full specilization (b) of f is defined in the order shown above, it is a full specialization of (a). But (c) is a better match as it is an overloaded primary template defined afterwards and we get "f(T *)" as an output.

When (b) is defined after (c), (b) is an integer full specilization of (c) and hence the specilization is chosen as expected.

An excerpt from the book "C++ Templates - The Complete Guide" helps explain what is really happening here.

"Partial specialization doesn't introduce a completely new template: It is an extension of an existing template (the primary template). When a CLASS template is looked up, only primary templates are considered at first. If, after the selection of a primary template, it turns out that there is a partial specialization of that template with a template argument pattern that matches that of the instantiation, its definition (in other words, its body) is instantiated instead of the definition of the primary template. (Full template specializations work exactly the same way.)"

(Added this para on May-05-2008)
Note that the above paragraph applies to class templates only. But when full specializations are in consideration, the above paragraph applies to function templates as well. Full function template specialization is supported by C++98 standard but not partial function template specialization. A better alternative to partial function template specialization is to use plain old function overloading. Having said that, as far as I know, there are efforts begin made towards standardizing partial function template specialization for C++09 standard. (please see comments for more discussion on this.)

The program clearly shows that the order of definition of specilizations and overloads affects primary template lookup. As a result, interestingly enough, you can define the f<>(int *) full specialization twice in the program. One after (a) and another one after (c) and program compiles just fine!

template<class T> // (a) a base template
void f( T ) {
std::cout << "f(T)\n";
}

template<>
void f<>(int*) { // (b) an explicit specialization
std::cout << "f(int *) specilization\n";
}

template<class T> // (c) another, overloads (a)
void f( T* ) {
std::cout << "f(T *)\n";
}

template<>
void f<>(int*) { // (d) another identical explicit specialization
std::cout << "f(int *) another specilization\n";
}

int main (void) {
int *p = 0;
f(p);
}

What is the output here? Any guesses?

This program is an example of complexity that results due to orthogonality of C++ language. In simple terms, number of C++ features can co-exist and their interplay can baffle any uninitiated C++ programmer! I wonder how complex it would be once we have partial function template specialization support in standard C++ in 2009.