Endless recursion in template instantiation

[Carlo Milanesi]

Consider the following program to convert between units of measurement:

struct MilesPerHour { };

struct KilometersPerHour { };

// Clause 1
template <class FromUnit, class ToUnit>
double ConversionFactor();

// Clause 2
template <>
double ConversionFactor<MilesPerHour, KilometersPerHour>()
{ return 1.609; }

// Clause 3
template <>
double ConversionFactor<KilometersPerHour, MilesPerHour>()
{ return 1 / 1.609; }

#include <iostream>

int main ()
{
std::cout << ConversionFactor<KilometersPerHour, MilesPerHour>()
<< " " << ConversionFactor<MilesPerHour, KilometersPerHour>();
}

It works well, but clause 2 and clause 3 are somewhat redundant.
Therefore I replaced clause 1 with the following:
template <class FromUnit, class ToUnit>
double ConversionFactor()
{ return 1 / ConversionFactor<ToUnit, FromUnit>(); }

Then I could eliminate clause 2 OR clause 3 and the program kept working
well.
But if accidentally I eliminate both clause 2 AND clause 3, every
compiler I tried (gcc, VC++ 2005, VC++ 2008) completed the compilation
with no error messages. When running the (wrong) executable, in two
cases the program terminated silently, and in one case it crashed.
Of course such an executable program had never to be generated.
There is a way to force a compilation error in such a case (of endless
recursion in template instantiation)?

 

[Alain Ketterlin]

[...]

int main ()
{
std::cout << ConversionFactor<KilometersPerHour, MilesPerHour>()
<< " " << ConversionFactor<MilesPerHour, KilometersPerHour>();
} [...]
template <class FromUnit, class ToUnit>
double ConversionFactor()
{ return 1 / ConversionFactor<ToUnit, FromUnit>(); }

Then I could eliminate clause 2 OR clause 3 and the program kept
working well.
But if accidentally I eliminate both clause 2 AND clause 3, every
compiler I tried (gcc, VC++ 2005, VC++ 2008) completed the compilation
with no error messages. When running the (wrong) executable, in two
cases the program terminated silently, and in one case it crashed.

Terminated silently? That's strange

Of course such an executable program had never to be generated.

I don't understand your reasoning here.

There is a way to force a compilation error in such a case (of endless
recursion in template instantiation)?

The recursion in template instantiation is handled fine by the compiler,
and it's not endless. Mutual recursion of template instances is
certainly not an error, and it's actually crucial in certain
applications (e.g., parsers).

What would be endless recursion in template instantiation is:

template< int N >
int f()
{
return f<N-1>();
}

My compiler stops instantiating after a certain depth has been reached.
That's as good as can be.

What is endless in your case is the sequence of recursive calls
performed by your program, and this has nothing to do with templates.
Detecting this at compile time in the general case is out of reach of
any passed, present, and future compiler, so I guess it's not even
attempted in simple cases.

-- Alain.

 

[Carlo Milanesi]

[...]

int main ()
{
std::cout<< ConversionFactor<KilometersPerHour, MilesPerHour>()
<< " "<< ConversionFactor<MilesPerHour, KilometersPerHour>();
} [...]
template<class FromUnit, class ToUnit>
double ConversionFactor()
{ return 1 / ConversionFactor<ToUnit, FromUnit>(); }

Then I could eliminate clause 2 OR clause 3 and the program kept
working well.
But if accidentally I eliminate both clause 2 AND clause 3, every
compiler I tried (gcc, VC++ 2005, VC++ 2008) completed the compilation
with no error messages. When running the (wrong) executable, in two
cases the program terminated silently, and in one case it crashed.

Of course such an executable program had never to be generated.

I don't understand your reasoning here.

I meant: "Of course, as the application programmer forgot a necessary
clause, we would like that such an error would be detected by the
compiler, by halting the compilation process and emitting a diagnostic
message, instead of generating a program containing an endless recursion".

The recursion in template instantiation is handled fine by the compiler,
and it's not endless. Mutual recursion of template instances is
certainly not an error, and it's actually crucial in certain
applications (e.g., parsers).

You are right, I am sorry.
It not a case of endless recursion in template instantiation, but more
precisely a case of template instantiation generating an endless mutual
recursion of function calls.

I tried also to solve my problem using templates of structs instead of
templates of functions.
I could do it using integer values, but I need floating-point values,
and I couldn't do that.
Here is my solution using integer values:

struct Miles { };

struct Kilometers { };

template <class FromUnit, class ToUnit>
struct ConversionFactor
{
static const int value = 1000
/ ConversionFactor<ToUnit,FromUnit>::value;
};

template <>
struct ConversionFactor<Miles,Kilometers>
{
static const int value = 20;
};

#include <iostream>
using namespace std;

int main ()
{
std::cout << ConversionFactor<Kilometers,Miles>::value
<< " " << ConversionFactor<Miles,Kilometers>::value;
}

Of course, the meaning of "miles" and "kilometers" is not kept.
If the template specialization is removed, a compilation error is emitted.
I would like to do the same using "double" instead of "int".

 

[Carlo Milanesi]

I'm not very familiar with template metaprogramming, this is the best I
could come up in 15 minutes. If you comment out clause 2 you get the
desired compile error, but the error messages are quite cryptic. This can
be probably enhanced by some kind of static assert feature.

You look quite smart and competent!
Thank you very much.

 

[itaj sherman]

It works well, but clause 2 and clause 3 are somewhat redundant.
Therefore I replaced clause 1 with the following:
template <class FromUnit, class ToUnit>
double ConversionFactor()
{ return 1 / ConversionFactor<ToUnit, FromUnit>(); }

If you only want that, it's possible to add a static_assert that won't
compile.
But what if you have defined convert<A,B>, convert<B,C> and
convert<C,D>, then convert<A,D> is also redundant.
If you can afford to hold in memory a singleton 2-dimensional array
for all required conversions, then you can put some static data
members in your templates that would initialize the conversions matrix
when your program starts. But then also, conversions that are used in
the code but have no existing path will only be verified during static
initialization (when the program starts), not compile time. However
during runtime, any possible conversion is still O(1).

itaj