Template Recursion Pickle

Originally Posted by phantomotap

O_o

You have used 'T1' as part of an argument to the 'c' template in the specification of the specialization. No 'T1' symbol is in scope.

You have not used 'T3' as part of an argument to the 'c' template in the specification of the specialization. You must use ever parameter as part of the specialization.

Your example is wrong on two places. I'm not sure what you may have intended. I can't say if you understood or not.

I'll write another example. (I'm writing inline so there may be a syntax bug.)

Soma

Code:

#include <iostream>

template
<
   unsigned int a_F,
   unsigned int b_F,
   unsigned int c_F,
   unsigned int d_F,
   unsigned int e_F,
   unsigned int f_F,
   unsigned int g_F
>
struct tester
{
};

template
<
   typename type1_F,
   typename type2_F
> // original template has two formal parameters
struct test
{
   test()
   {
      std::cout << "default" << '\n';
   }
};

template
<
   typename type_F
> // specialized template has one formal parameters
// specialization "passes" two arguments to the original
struct test<type_F, type_F>
{
   test()
   {
      std::cout << "small specialization" << '\n';
   }
};

template
<
   typename type_F,
   unsigned int a_F,
   unsigned int b_F,
   unsigned int c_F,
   unsigned int d_F,
   unsigned int e_F,
   unsigned int f_F,
   unsigned int g_F
> // specialized template has eight formal parameters
// specialization "passes" two arguments to the original
struct test<type_F, tester<a_F, b_F, c_F, d_F, e_F, f_F, g_F> >
{
   test()
   {
      std::cout << "big specialization" << '\n';
   }
};

int main()
{
   typedef unsigned long whatever;
   typedef whatever * not_whatever;
   test<whatever, not_whatever> a;
   test<whatever, whatever> b;
   test<whatever, tester<0, 1, 2, 3, 4, 5, 6> > c;
   return(0);
}

got it. yes, that is more or less the principle i was overly-succinctly trying to express.

thanks.

that is more or less the principle i was overly-succinctly trying to express.

Really?! O_o

Sorry for the confusion.

Soma

yep, and no worries about any confusion. as i continued to think about my example after i posted it, the principle started to become clear to me, as well as how woefully ambiguous the skeleton code (for lack of a better phrase) i posted was. i appreciate your help. i could have figured that out on my own with a little experimentation - my new motto should be 'code first, post second' or something. sometimes a bit of discussion really gets the gears turning tho'.

Originally Posted by phantomotap

Code:

// now consider the problem source (with corrected syntax)
template <int nrows, int ld> template <int uld>
inline void cmatrix<nrows,0,ld>::mgso( cupper<0,uld> &R){}
// the default template for 'cmatrix' doesn't have a declaration for such a function
// the parameter of 'cupper<0,?> &' doesn't match the parameter 'cupper<?,?> &'
// you've attempted to define a function of an enclosing class 'cmatrix<nrows,0,ld>'
// that is an expansion of a partial specialization of a template
// this is basically the same as the forth example above

Well there's the rub I suppose. The compiler can not infer that match, even though it may make sense to the programmer, since I can pick parameters for nrows, ncols and ld (the template parameters for cmatrix) that would enable such a match, namely ncols=0.

Alll I can say is that I'd hate to have to write a C++ compiler. Moreover I can easily imagine why templated code is not very portable across differing compilers. By the way, after debugging, it does appear that my code is working as it should.

OK this is still a bit arcane IMHO. Consider again the code that I got 'working'.

Code:

template <int nrows, int ncols, int ld = nrows>
class cmatrix {

public:
	float *val ; // pointer to the data on the device
/* a bunch of code */
/* template recursion to implement modified graham schmidt orthogonolization */
template <int uld, int ucols>
void mgso( cupper<ucols,uld> &R) 
{
/* code that always executes */

if (ucols > 1) { /* should be able to remove the if */
/* recurse over the remaining columns */

cmatrix<nrows,ucols-1,ld> X1(ptroff(0,1)) ;  /* remaining columns of this */

/* some more code ... */

/* recurse to get rest of mgso */
X1.mgso(rsub) ;

}
}

/* specialization case */
template <int uld>
void mgso( cupper<1,uld> &R)
{
/* same code that always executes as above */

}
} ; /* end class */

/* How mgso is actually called.  Probably should make mgso protected. */
cupper<ncols,ncols> qr()
{
cupper<ncols,ncols> R ;
mgso<ncols,ncols>(R) ;
return(R) ;

}

As phantamotap pointed out, it works not by template specialization per se, but via function overloading. There are in fact two versions of mgso

Code:

cmatrix<9,5> X ;
cupper<5> R ;
int uld=5 ;
cupper<1,uld>R1 ;
int ucols=5 ;

/* one version of mgso */
X.mgso<uld,ucols>(R) ;
/* the other version */
X.mgso<uld>(R1) ;

/* The compiler infers which form to pick based on the input parameter and.....????????? */
X.mgso(R) ; // picks X.mgso<uld,5>(R)
X.mgso(R1) ; // picks  X.mgso<uld>(R1) why?  why not X.mgso<uld,1>(R1) and then fail?

In the recursion you have to call X1.mgso(rsub) and not X1.mgso<uld,1>(rsub), or it will not pick the overloaded specialization case, which makes sense, but I have no sense as to why it picks the correct overloaded mgso to complete the specialization case and terminate the recursion. Will this code even be portable? I especially will need to port this from MS Vis. Studio to gcc on linux.

*shrug*

I don't know of any compiler that fully supports template methods where this will not work.

This only relies on the compiler picking the correct overload. If a compiler doesn't pick the correct overload here it probably never does.

Without having a full example I can't be sure, but you probably do not need the 'if' statement at all because you do not need it to eliminate the recursion. The general case, the one overload, always recurses down and the terminating case, the other overload, doesn't.

In the interest of... the interesting, there are a few compilers around that do have problems with template methods that will not handle this situation. You will probably never run into them because the latest versions of all the popular compilers work correctly for this example. If supporting older or simply odd compilers is important, you can increase the portability by providing an interface that makes the choice of overloads explicit through reliance on non-template functions.

Just out of curiosity, do you want to allow any 'void cmatrix<?, ?, ?>::mgso(cupper<?, ?> &)' to be called with any 'cupper<?, ?>' reference? Or should the column size match? (Should the '$' representing 'ucols' and ncols' match in 'void cmatrix<?, $, ?>::mgso(cupper<$, ?> &)'.)

I've included some source which should explain virtually everything.

Soma

Code:

#include <iostream>

struct false_type{};
struct true_type{};

template
<
   unsigned int value_F
>
struct value_type{};

// the value is never used
// types distinguish the result
// everything matches the general case
const false_type * is_value_one(...){return(0);}
// but only a paramter convertble to a 'const value_type<1> &' matches here
const true_type * is_value_one(const value_type<1> &){return(0);}

template
<
   unsigned int a_F,
   unsigned int b_F
>
struct test1_p
{
   static const unsigned int a = a_F;
   static const unsigned int b = b_F;
};

template
<
   unsigned int a_F,
   unsigned int c_F,
   unsigned int d_F
>
struct tester1
{
   template
   <
      unsigned int a_FN,
      unsigned int b_FN
   >
   void test
   (
      const test1_p<a_FN, b_FN> & f
   ) // general case: always recurse
   {
      tester1<a_FN, c_F - 1, d_F> t1;
      test1_p<a_FN, b_FN - 1> t1p;
      std::cout
         << '(' << a_F << ':' << c_F << ':' << d_F << ')'
         << "::" << '(' << a_FN << ':' << b_FN << ')' << '\n'
      ;
      t1.test(t1p); // recurse
   }
   template
   <
      unsigned int a_FN
   >
   void test
   (
      const test1_p<a_FN, 1> & f
   )// terminating case: never recurse
   {
      std::cout
         << '(' << a_F << ':' << c_F << ':' << d_F << ')'
         << "::" << '(' << a_FN << ':' << 1 << ')' << '\n'
      ;
   }
};

template
<
   unsigned int a_F,
   unsigned int b_F
>
struct test2_p
{
   static const unsigned int a = a_F;
   static const unsigned int b = b_F;
};

template
<
   unsigned int a_F,
   unsigned int b_F,
   unsigned int c_F
>
struct tester2
{
   template
   <
      unsigned int d_FN
   >
   void test
   (
      const test2_p<b_F, d_FN> & f
   ) // interface guaranteeing b_F of parameter
   { // matches b_F of containing class
      // forward to the fucntion that does "work"
      // use overload resolution to determine recursion
      test(f, is_value_one(value_type<b_F>()));
   }
   template
   <
      unsigned int d_FN
   >
   void test
   (
      const test2_p<b_F, d_FN> & f,
      const false_type * false_f
   )// general case: always recurse
   {
      tester2<a_F, b_F - 1, c_F> t2;
      test2_p<b_F - 1, d_FN> t2p;
      std::cout
         << '(' << a_F << ':' << b_F << ':' << c_F << ')'
         << "::" << '(' << b_F << ':' << d_FN << ')' << '\n'
      ;
      // use overload resolution to determine recursion
      t2.test(t2p, is_value_one(value_type<b_F - 1>())); // recurse
   }
   template
   <
      unsigned int d_FN
   >
   void test
   (
      const test2_p<b_F, d_FN> & f,
      const true_type * true_f
   )// terminating case: never recurse
   {
      std::cout
         << '(' << a_F << ':' << b_F << ':' << c_F << ')'
         << "::" << '(' << b_F << ':' << d_FN << ')' << '\n'
      ;
   }
};

int main()
{
   tester1<10, 20, 30> t1;
   t1.test(test1_p<10, 5>()); // Success
   std::cout << '\n';
   t1.test(test1_p<20, 5>()); // Success
   std::cout << '\n';
   t1.test(test1_p<30, 5>()); // Success
   std::cout << '\n';
   t1.test(test1_p<1, 5>()); // Success
   std::cout << '\n';
   tester2<10, 20, 30> t2;
   //t2.test(test2_p<10, 5>()); // failure
   //std::cout << '\n';
   t2.test(test2_p<20, 5>()); // Success
   std::cout << '\n';
   //t2.test(test2_p<30, 5>()); // failure
   //std::cout << '\n';
   //t2.test(test2_p<1, 5>()); // failure
   //std::cout << '\n';
   return(0);
}