Template Recursion Pickle

I'm trying to implement an matrix algorithm via template recursion, but I've run into a problem with my compiler. I don't know the right syntax to end the recursion. It doesn't quite fit into the simple pattern of ending the recursion with template specialization.

Here is a synopsis of the code:

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 <int uld>
inline void mgso( cupper<ncols,uld> &R)
{
/* some code */

if (ncols > 1) {
/* recurse over the remaining columns */

cmatrix<nrows,ncols-1,ld> X1(ptroff(0,1)) ;
/* ... */

/* recursion starts here */
X1.mgso(rsub) ;
}
}

} ;

/* cupper is a derived class from cmatrix */
template<int nrows, int ld = nrows>
class cupper : public cmatrix<nrows,nrows,ld> {
public:
	inline float *subptr()
	{
		return(val+1+ld) ;
	}

	cupper<nrows-1,ld> sub()
	{
		return(subptr()) ;

	}

/* other stuff like constructors and destructors etc. */

} ;

The problem is that the compiler ends up trying to constuct a cmatrix<nrows,0,ld>
where ncols=0, resulting in all kinds of errors. My compiler (MS visual studio 2005) gives me the error,

c:\projects\s3000\cudageo\cmatrix.h(93) : error C2057: expected constant expression
1> c:\projects\s3000\cudageo\cmatrix.h(518) : see reference to class template instantiation 'cmatrix<nrows,ncols,ld>' being compiled
1> with
1> [
1> nrows=5,
1> ncols=0,
1> ld=7
1> ]

Note that the recursion occurs with X1.mgso(rsub) ; It recurses despite the
if (ncols > 1) { ... } statement and it in fact tries to create X1 with ncols=0, despite the if statement.

The variable that recurses is not uld in the template definition, so direct template specialization is not quite right. Am I going to have create a special instance of cmatrix to get the recursion to stop?

why can't you specialize for the special cases of rows and vectors?

You need to create a specialization for the ncols == 0 case. I'd actually specialize on ncols == 1, since that's really your base.

Originally Posted by brewbuck

You need to create a specialization for the ncols == 0 case. I'd actually specialize on ncols == 1, since that's really your base.

OK I agree, but let's take the ncols=0 case for a second. I'm just trying to get the darn syntax right. I tried this code after the cmatrix class template statement and failed,

Code:

template <int uld, int nrows,int ld>
inline void cmatrix<nrows,0,ld>::mgso( cupper<0,uld> &R)
{

}

This generates a matching failure, with the error,

Code:

c:\projects\s3000\cudageo\cmatrix.h(559) : error C2244: 'cmatrix<rows1,cols1,ld1>::mgso' : unable to match function definition to an existing declaration
1>        definition
1>        'void cmatrix<nrows,0,ld>::mgso(cupper<0,uld> &)'
1>        existing declarations
1>        'void cmatrix<rows1,cols1,ld1>::mgso(cupper<ncols,uld> &)'

It seems like it should match. Am I missing an additional declaration of some sort or am I just being stupid.

Originally Posted by m37h0d

why can't you specialize for the special cases of rows and vectors?

Well inside the class template, the template variable is uld, which is not my recursion variable. So it looks like I have to recurse over ncols, which is one template variable for cmatrix.

But the syntax for exactly how to do that is eluding me for some reason as you can see from my previous post.

you introduced uld in the specialization. i don't think you can do that.

Originally Posted by m37h0d

you introduced uld in the specialization. i don't think you can do that.

OK well then, suppose I have a template with two or more integer parameters, but I only want to recurse over one of those parameters. How do I do it?

Nested templates perhaps?

The first example below fixes a few problems with the original source and shows a way of specializing the behavior and interface of a nested template without specializing the enclosing class. (I just modified the source you posted. It hasn't been styled.)

The second example shows recursion on a second integer value. It is as strait forward as you probably think. It isn't, or at least shouldn't be, the recursion giving you a problem.

If you need more help, you'll have to post more source. We can't guess at the missing bits.

Soma

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 <int uld>
inline void mgso( cupper<ncols,uld> &R);

} ;

/* cupper is a derived class from cmatrix */
template<int nrows, int ld = nrows>
class cupper : public cmatrix<nrows,nrows,ld> {
public:
	inline float *subptr()
	{
		return((this->val)+1+ld) ;
	}

	cupper<nrows-1,ld> sub()
	{
		return(subptr()) ;

	}

/* other stuff like constructors and destructors etc. */

} ;

template <int nrows, int ncols, int ld, int uld>
struct cmatrix__mgso_implementation
{
static inline void execute( cupper<ncols,uld> &R)
{
if (ncols > 1) {
/* recurse over the remaining columns */

cmatrix<nrows,ncols-1,ld> X1(ptroff(0,1)) ;
/* ... */

/* recursion starts here */
X1.mgso(rsub) ;
}
}
};

template <int nrows, int ld, int uld>
struct cmatrix__mgso_implementation<nrows, 0, ld, uld>
{
static inline void execute( cupper<0,uld> &R)
{
// specialization for 'cmatrix<nrows, ncols, ld>::mgso' ncols = 0 here
}
};

template <int nrows, int ncols, int ld> template <int uld>
inline void cmatrix<nrows, ncols, ld>::mgso( cupper<ncols,uld> &R)
{
cmatrix__mgso_implementation<nrows, ncols, ld, uld>::execute(R);
}

Code:

#include <iostream>

template
<
   unsigned int x_F,
   unsigned int y_F
>
struct test: test<x_F, y_F - 1>
{
   test()
   {
      std::cout << '(' << x_F << ',' << y_F << ')' << '\n';
   }
};

template
<
   unsigned int x_F
>
struct test<x_F, 0>
{
   test()
   {
      std::cout << '(' << x_F << ',' << 0 << ')' << '\n';
   }
};

int main()
{
   test<5, 5> a;
}

what i mean is i think your specialized template argument list has to be smaller than your unspecialized one - if i'm reading your code correctly, it looks like essentially what you've done is implicitly introduce a 4th template parameter.

i am far from a template guru tho & i am having a hard time telling exactly what you're doing.

i take it back - i was/am just confused

what i mean is i think your specialized template argument list has to be smaller than your unspecialized one - if i'm reading your code correctly, it looks like essentially what you've done is implicitly introduce a 4th template parameter.

This is simply wrong. You do have to pass the required number of arguments to the original template in the specification of the specialization, but the template of a specialization or partial specialization can have as few or as many formal parameters as may be required.

Besides, in this instance, he is, from the perspective of the compiler, attempting to define a method that hasn't been declared in the class definition.

Soma

Originally Posted by phantomotap

Besides, in this instance, he is, from the perspective of the compiler, attempting to define a method that hasn't been declared in the class definition

yes, i realized that after a second look at it.

Originally Posted by phantomotap

This is simply wrong. You do have to pass the required number of arguments to the original template in the specification of the specialization, but the template of a specialization or partial specialization can have as few or as many formal parameters as may be required.

ok. indulge me with a comprehension check, if you don't mind:

Code:

template<typename T1,typename T2>class c
{
};
template<typename T3>class c<int,T1>
{

};

^ this is valid, and the compiler can differentiate the two? edit - since it is more specialized, anything with int as the first parameter will deduce to that second case....

Originally Posted by phantomotap

Besides, in this instance, he is, from the perspective of the compiler, attempting to define a method that hasn't been declared in the class definition.

Soma

Yes and that's what I am struggling to understand in this example. Superficially it seems like the template arguments should match the declaration. However it seems that it has trouble matching the nested ncols variable. I can only guess this is because it would have to infer ncols through the class definition or something.

However I came up with a 'fix' that at least compiles. I'm still debugging though so I'm not sure if it's correct. The fix is similar to what you had proposed, but all definitions are now inside the class.

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

}

The key differences are that ncols, a template paramater for the whole class has become ucols a template parameter for the mgso method, and that I add the specialization for ucols=1 by dropping the argument from the template argument list. So I think this device allows me to include the specialization right inside the class.

Now I just have to debug it to see if my syntax is correct.

By the way, thanks for your answer, it is quite helpful.

[...]indulge me with a [...] anything with int[...]

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);
}

Yes and that's what [...] class definition or something.

A few small source examples should correct your misunderstanding and explain the error you get.

The key differences are [...] the template argument list.

Yes. You have declared two overloads of the method named 'mgso': one with a 'cupper<?,?> &' parameter; the other with a 'cupper<1,?> &' parameter.

So I think this device allows me to include the specialization right inside the class.

You have not specialized anything. You have overloaded a template function with another template function. Now that both declarations exist you can define the functions inline, inside the class definition, or as you would normally.

The key thing to take away from this: you are overloading functions. The rules still apply even though you are using class templates and template methods.

Soma

Code:

// define struct A
struct A
{
void test(int); //declare void A::test(int)
};
//define void A::test(int)
void A::test(int){}

Code:

// define struct A
struct A
{
void test(int); //declare void A::test(int)
};
//define void A::test(float)
void A::test(float){} //error: there is no such function to define

Code:

// define struct A
struct A
{
void test(int); //declare void A::test(int)
};
//define void B::test(int)
void B::test(int){} //error: there is no such class and no such function to define

Code:

// define struct A
struct A
{
void test(int); //declare void A::test(int)
};
//define void B::test(int)
void B::test(float){} //error: again there is no such class and no such function to define

Code:

// here you have defined 'struct A' with the name 'matrix<?, ?, ?>'.
template <int nrows, int ncols, int ld> class cmatrix
{
// here you have declared 'void A::test(int)' with the name 'void msgo(cupper<?,?>&)'
template <int uld> inline void mgso( cupper<ncols,uld> &);
};
// here you have defined  'void A::test(int)' with the name 'void msgo(cupper<?,?>&)'
template <int nrows, int ncols, int ld> template <int uld>
inline void cmatrix<nrows,ncols,ld>::mgso( cupper<ncols,uld> &R){}

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