Skip to main content

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.

Comments

Bourgeois said…
You're missing a "typename" ;-)
flo said…
Unfortunately, there is no infinite series of instantiations at all, because the integer template parameter is fixed in size.
Sumant said…
It is arguable that way but for all practical purposes it is infinite. Using default settings there are 500 instantiations on g++, 1000 on Comeau, and 450 on VC8. From your argument an analogy can also be drawn as there can't be infinite recursion possible in any computer because the stack space is anyways limited by computer's main memory.
flo said…
The analogy does not hold as you are not using infinite recursion in your example: The number of different instantations of your class template is not infinite but actually limited by the number of different instantiatons of the int type. Your program compiles fine if this number is less than the maximum level of recursion your compiler is willing to traverse. For practical purposes: Try char instead of int.
An infinite series of instantiations of a class template is possible in general but unfortunately not with this one.
Sumant said…
Please use the *second* example in my original post including the main function. On three different compilers (mentioned before) it gives rise to an infinite series, which is terminated by the compiler with an error message. Your point about using char is well taken. It does not cross the limits of the compiler as there are only 256 possible values.
Sumant said…
The key point I want to bring out is that there is a possibility of a series of instantiations that almost always will overwhelm current compilers. In some cases such as using 'char' or 'unsigned char' the number of instantiations are limited to 256. However, for 'wchar_t', 'int', 'long', and their unsigned counterparts, there will be tremendous number of unnecessary instantiations breaking the compilation. I would still like to stick to the word 'infinite' because conceptually it really is infinite.
flo said…
My key point: It just isn't infinite. Neither conceptually nor practically. The recursion is not infinite because there is a well defined termination condition.
The fact that your compilers hit their limits before the condition was met is completely irrelevant: Given enough resources, this recursion will eventually always stop. This is not true for real infinite recursions.
flo said…
If it is really so important for you to show infinite regress with the help of a class template whose instantiation "leads to an infinite series of instantiations of the template with no end", you might consider this one which really causes an infinite recursion:

template <typename T>
struct Type : Type< Type<T> > {};
Sumant said…
This is an interesting example and obviously it creates an infinite series of instantiations. But again, the number of instantiations are limited by the maximum depth a compiler is willing to go. I do agree with your point that there is a well defined limit to the recursion in the example I showed (unlike yours), which is governed by the size of an integer. However, both the things have much much smaller and harder limits imposed by the compilers.
christian said…
Hey, will you continue with the blog?
it's really good :D
Sumant said…
Yes, I'm certainly going to continue this blog. For a long time now I'm totally swamped with my work at the university. I've learned a LOT of fresh C++ truths in the meanwhile. So I'll be back!
Dascandy said…
Given the new variadic templates, your errors can grow a bit large if you make this mistake:

http://www.atlantisos.org/errormsg

That was me not going down a level and ending up with a template instantiated with 500 std::strings, which was instantiated from one with 499 std::strings etc... completely written out by the compiler.
Sumant said…
@Dascandy - How does your source look like? and which compiler are you using?
Dascandy said…
That was in a mocking framework, where I was trying to get my tuple to invoke a function by recursively passing down its argument to the next layer of tuple implementation. I forgot to mention to it that it had to be the *next* layer. This was on gcc 4.3.1 or 4.3.0, I think the latter.
rmn said…
this post in my forum is quite similar: http://cpptalk.wordpress.com/2009/08/13/computations-at-compile-time/
you are more than welcome to have a look.
Thanks for the tips, can you check out my C++ Code Samples too?
Very useful, thanks! Will take a look at your other C++ articles
Its very glad to see your post because you added much aided information which will be very much useful to C++ programmers.I definitely agree with your conclusions ,It is used to achieve static dispatching based on constant integral values.So thanks for sharing your thoughts.
xander345 said…
if you like c++ you can compile it online here: http://codecompiler.info/

32, 64 - windows & Linux - and more programming languages

Popular posts from this blog

Multi-dimensional arrays in C++11

What new can be said about multi-dimensional arrays in C++? As it turns out, quite a bit! With the advent of C++11, we get new standard library class std::array. We also get new language features, such as template aliases and variadic templates. So I'll talk about interesting ways in which they come together.

It all started with a simple question of how to define a multi-dimensional std::array. It is a great example of deceptively simple things. Are the following the two arrays identical except that one is native and the other one is std::array?

int native[3][4];
std::array<std::array<int, 3>, 4> arr;

No! They are not. In fact, arr is more like an int[4][3]. Note the difference in the array subscripts. The native array is an array of 3 elements where every element is itself an array of 4 integers. 3 rows and 4 columns. If you want a std::array with the same layout, what you really need is:

std::array<std::array<int, 4>, 3> arr;

That's quite annoying for two r…

Folding Monadic Functions

In the previous two blog posts (Understanding Fold Expressions and Folding Functions) we looked at the basic usage of C++17 fold expressions and how simple functions can be folded to create a composite one. We’ll continue our stride and see how "embellished" functions may be composed in fold expressions.

First, let me define what I mean by embellished functions. Instead of just returning a simple value, these functions are going to return a generic container of the desired value. The choice of container is very broad but not arbitrary. There are some constraints on the container and once you select a generic container, all functions must return values of the same container. Let's begin with std::vector.
// Hide the allocator template argument of std::vector. // It causes problems and is irrelevant here. template <class T> struct Vector : std::vector<T> {}; struct Continent { }; struct Country { }; struct State { }; struct City { }; auto get_countries…

Covariance and Contravariance in C++ Standard Library

Covariance and Contravariance are concepts that come up often as you go deeper into generic programming. While designing a language that supports parametric polymorphism (e.g., templates in C++, generics in Java, C#), the language designer has a choice between Invariance, Covariance, and Contravariance when dealing with generic types. C++'s choice is "invariance". Let's look at an example.
struct Vehicle {}; struct Car : Vehicle {}; std::vector<Vehicle *> vehicles; std::vector<Car *> cars; vehicles = cars; // Does not compile The above program does not compile because C++ templates are invariant. Of course, each time a C++ template is instantiated, the compiler creates a brand new type that uniquely represents that instantiation. Any other type to the same template creates another unique type that has nothing to do with the earlier one. Any two unrelated user-defined types in C++ can't be assigned to each-other by default. You have to provide a c…