Thread: Template Recursion Pickle

  1. #1
    Registered User
    Join Date
    Apr 2007
    Posts
    141

    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?

  2. #2
    3735928559
    Join Date
    Mar 2008
    Location
    RTP
    Posts
    838
    why can't you specialize for the special cases of rows and vectors?

  3. #3
    Officially An Architect brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,396
    You need to create a specialization for the ncols == 0 case. I'd actually specialize on ncols == 1, since that's really your base.
    Code:
    //try
    //{
    	if (a) do { f( b); } while(1);
    	else   do { f(!b); } while(1);
    //}

  4. #4
    Registered User
    Join Date
    Apr 2007
    Posts
    141
    Quote Originally Posted by brewbuck View Post
    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.

  5. #5
    Registered User
    Join Date
    Apr 2007
    Posts
    141
    Quote Originally Posted by m37h0d View Post
    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.

  6. #6
    3735928559
    Join Date
    Mar 2008
    Location
    RTP
    Posts
    838
    you introduced uld in the specialization. i don't think you can do that.

  7. #7
    Registered User
    Join Date
    Apr 2007
    Posts
    141
    Quote Originally Posted by m37h0d View Post
    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?

  8. #8
    Master Apprentice phantomotap's Avatar
    Join Date
    Jan 2008
    Posts
    5,108
    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;
    }

  9. #9
    3735928559
    Join Date
    Mar 2008
    Location
    RTP
    Posts
    838
    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.

  10. #10
    3735928559
    Join Date
    Mar 2008
    Location
    RTP
    Posts
    838
    i take it back - i was/am just confused
    Last edited by m37h0d; 02-03-2009 at 06:08 PM.

  11. #11
    Master Apprentice phantomotap's Avatar
    Join Date
    Jan 2008
    Posts
    5,108
    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

  12. #12
    3735928559
    Join Date
    Mar 2008
    Location
    RTP
    Posts
    838
    Quote Originally Posted by phantomotap View Post
    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.

    Quote Originally Posted by phantomotap View Post
    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....
    Last edited by m37h0d; 02-03-2009 at 06:54 PM.

  13. #13
    Registered User
    Join Date
    Apr 2007
    Posts
    141
    Quote Originally Posted by phantomotap View Post
    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.

  14. #14
    Master Apprentice phantomotap's Avatar
    Join Date
    Jan 2008
    Posts
    5,108
    [...]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);
    }

  15. #15
    Master Apprentice phantomotap's Avatar
    Join Date
    Jan 2008
    Posts
    5,108
    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
    Last edited by phantomotap; 02-03-2009 at 07:31 PM.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Specialising a member function with a template template parameter
    By the4thamigo_uk in forum C++ Programming
    Replies: 10
    Last Post: 10-12-2007, 04:37 AM
  2. Screwy Linker Error - VC2005
    By Tonto in forum C++ Programming
    Replies: 5
    Last Post: 06-19-2007, 02:39 PM
  3. error: template with C linkage
    By michaels-r in forum C++ Programming
    Replies: 3
    Last Post: 05-17-2006, 08:11 AM
  4. Class Template Trouble
    By pliang in forum C++ Programming
    Replies: 4
    Last Post: 04-21-2005, 04:15 AM
  5. oh me oh my hash maps up the wazoo
    By DarkDays in forum C++ Programming
    Replies: 5
    Last Post: 11-30-2001, 12:54 PM