Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C++ > Endless recursion in template instantiation

Reply
Thread Tools

Endless recursion in template instantiation

 
 
Carlo Milanesi
Guest
Posts: n/a
 
      03-06-2011
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++ 200 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)?

--

Carlo Milanesi
http://carlomilanesi.wordpress.com/
 
Reply With Quote
 
 
 
 
Alain Ketterlin
Guest
Posts: n/a
 
      03-06-2011
Carlo Milanesi <(E-Mail Removed)> writes:

[...]
> 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++ 200 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.
 
Reply With Quote
 
 
 
 
Carlo Milanesi
Guest
Posts: n/a
 
      03-06-2011
On 06/03/2011 14.12, Alain Ketterlin wrote:
> Carlo Milanesi<(E-Mail Removed)> writes:
>
> [...]
>> 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++ 200 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".

>> 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).


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
http://carlomilanesi.wordpress.com/
 
Reply With Quote
 
Carlo Milanesi
Guest
Posts: n/a
 
      03-08-2011
On 06/03/2011 17.49, Paavo Helde wrote:
> Carlo Milanesi<(E-Mail Removed)> wrote in news:4d7373ab$0
> $6842$(E-Mail Removed):
>
>> Consider the following program to convert between units of measurement:

>
> 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.

--

Carlo Milanesi
http://carlomilanesi.wordpress.com/
 
Reply With Quote
 
itaj sherman
Guest
Posts: n/a
 
      03-09-2011
On Mar 6, 1:44 pm, Carlo Milanesi <(E-Mail Removed)>
wrote:

>
> 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
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Explicit instantiation of non-template member of template class Noah Roberts C++ 6 02-02-2011 09:53 PM
Instantiation of template method in template class Ed C++ 1 08-27-2008 06:41 AM
Explicit instantiation of STL vector demands explicit instantiation of all the templates it using internally. krunalbauskar@gmail.com C++ 1 12-25-2006 03:51 PM
explicit instantiation of template methods of template classes Thomas Maier-Komor C++ 6 05-19-2005 08:00 AM
Explicit template instantiation from template function doesn't compile? Fernando Cuenca C++ 4 09-06-2004 04:06 PM



Advertisments