Back to General and Gameplay Programming

C++ Template Metaprogramming Problem

General and Gameplay Programming Programming

Started by Extrarius November 03, 2005 08:37 PM

17 comments, last by Extrarius 18 years, 5 months ago

Extrarius

1,412

Author

November 04, 2005 10:27 PM

Quote:Original post by Polymorphic OOP
Quote:Original post by Extrarius
Since a recursion limit is allowed, templates CAN be turing complete (if your specific compiler has no recursion limit), but they don't HAVE to be. Thus, by the standard, you can't count on templates being turing complete.

Not at all. By standard you can consider the turing complete. There are always going to be limits for tons of features in any language implementation, not just templates in C++; that doesn't make them any less turing complete, acknowledging them is just being realistic. The C++ standard, for instance, has dozens of recommendations for minimum compiler limits in other areas of the language -- that doesn't mean that going beyond them is nonstandard code, they are just recommendations and don't imply compliance on any level.

Templates are turing complete, it's just that a compiler is generally going to have limits, just like there are often limits for many other features of any language. They can still theoretically be recursively instantiated forever, whether your compiler can handle it or not is another story. The standard merely acknowledges that fact and provides reasonable guidelines for an implementor to follow as recommendations.

A compiler for any functional language may have a limit to how deep recursion goes, that doesn't make the language any less turing complete, again, it's just being realistic.[...]

A recursion limit would be fine if there were some other form of iteration, but a language without a way to iterate (or recurse) indefinitely cannot define a program that will not halt. Thus, the halting problem does not apply to such a language. The halting problem does not apply to templates, because it's valid for the compiler to force them to halt. The halting function for templates can thus be defined to be:
Halt(Template MetaProgram) = true
in an entirely standards-compliant compiler. If templates were turing complete, this fact would prove that many things with 'proven undecidability' are actually decidable and would make many very famous people quite unhappy.

In C (and, provably, any turing complete language), it is possible to create a program that will iterate indefinitely.

"Walk not the trodden path, for it has borne it's burden." -John, Flying Monk

Polymorphic OOP

954

November 04, 2005 10:45 PM

Quote:Original post by Extrarius
A recursion limit would be fine if there were some other form of iteration, but a language without a way to iterate (or recurse) indefinitely cannot define a program that will not halt.

You are missing the point. As I said, these are just recommended guidelines and don't determine compliance in any way, shape, or form. If your compiler has a limit of 17 and you go 18 deep, your code is still completely compliant code. Even if your code recursively instantiates templates to a depth of 10 billion, your code is still compliant, just like if you have runtime code which uses function recursion to a depth of 10 billion it is still compliant (note that neither will probably work).

The recommended limits provided in the standard are just there to be realistic -- if you want to say "well, the compiler can have limitations, therefore it can't be turing complete", then that means that many other languages can't be considered turing complete as nearly any compiler is going to have limitations in some form, either ones which it explicitly sets internally, or ones based on how much memory you have, or any number of different variables. The fact that the standard helps implementors by giving a recommendation on minimum limits doesn't change that, they just provide guidelines. Had the standard not mentioned them at all, we wouldn't even be having this conversation. That wouldn't change that the limits exist, you have to be realistic. There are limits in practice for nearly any language facility in any language implementation whether explicitly stated or not.

Extrarius

1,412

Author

November 04, 2005 10:49 PM

The fact that limitations are neccessary does not escape me. The fact is that most languages are turing complete despite the allowed compiler limitations while C++ templates are not.

"Walk not the trodden path, for it has borne it's burden." -John, Flying Monk

Cocalus

554

November 04, 2005 11:02 PM

By your rules no language is turring complete if you can solve the halting problem on a limited system. But mathematically you can determine if any program will halt on any machine without infinite memory. The amount of time and space needed may be way beyond astonomically huge, but still finite.

The system is simple just have a computer that can store and compare all possible states of your program running on the more limited machine. Then you emulate your program on this huge system, storing all the machine states it goes through. If a current state ever matches a previous state you have an infinite loop. Now you just emulate until the program terminates or until you've gone through more cycles than possible program states. And there I've solved the halting problem for ALL languages, but that's because of a practical limit on the langauge, in this case storage size.

Extrarius

1,412

Author

November 04, 2005 11:36 PM

Cocalus: There is a difference between hardware limitations and language limitations. Only the latter will affect a language's status as turing complete or not. Hardware sets practical bounds, while languages set theoretical bounds - a language that is not turing complete will have computational limits independant of hardware, just as C++ templates do.

"Walk not the trodden path, for it has borne it's burden." -John, Flying Monk

Polymorphic OOP

954

November 05, 2005 12:09 AM

Quote:Original post by Extrarius
Cocalus: There is a difference between hardware limitations and language limitations.

As was already said several times, there is no language limitation. Templates are entirely turing complete and have no limits, it's just the compilers you use and computers you run which may have limits -- which is exactly the same with any language. The standard only acknowledges that fact and provides guidelines which do not affect compliance of code.

Aside from that, even if you wanted to try and look at compiler limits and "harware limits" separately, a C compiler is realistically going to have limits to what it can compile as well, only that limit is going to be comparatively high so you don't really even think about it. The only difference with recursive template instantiations is that it's most-likely going to be a more restrictive limit for what you are currently trying to do.

Limits are always going to exist in some form for a compiler for any number of facilities in a given language. That doesn't make the languages themselves not turing complete. Again, the languages do not have limits.

Extrarius

1,412

Author

November 05, 2005 03:10 AM

Hrmm, after some reflection I've found that you're technically correct - every language has limitations to allow for the fact that they don't run on turing computers.

The difference is that in most languages, the allowances are still part of the runtime behavior of the program - for example, malloc can return NULL if the memory cannot be obtained (a condition that could not happen on a turing machine since it has unlimited memory), but the program itself can deal with this condition.

In templates, if there is a limitation on recursion depth, the (meta)program does not get a chance to handle this condition and is instead terminated instantly. There is no way (if violation of the limit is a compile error) to make a (meta)program that can deal with such 'error conditions'. Thus, in practice template (meta)programs are severely limited, while other types of programs are allowed to at least attempt to deal with 'error conditions'.

Also, limitations in most languages allow much more room to maneuver than do the template recursion limit.

I now change my argument to the completely nonsensical statement that 'in practice, template metaprograms are less turing complete than normal languages such as C'.

Oh, also, I still have NO idea how to implement a 'dot[char] combinator' that "outputs [char]" and returns it's argument. Every method mentioned so far sounds far too static and doesn't sound as if it fits into my framework of unary metafunctions at all.
Oh, and following is the definition of S and I:

//I (1) - returns it's parameterstruct I{  template<class Param1>  struct Apply  {    typedef Param1 Result;  };};//S Combinator (3) - returns a function that does//1) (Param1 Param3) => Outer//2) (Param2 Param3) => Inner//3) (Outer Inner) => Result//(((S x) y) z) is ((x z) (y z))//Turned into the required unary function using curryingstruct S{  template<class Param1>  struct Apply  {    struct Result    {      template<class Param2>      struct Apply      {        struct Result        {          template<class Param3>          struct Apply          {            typedef Param1 P1;            typedef Param2 P2;            typedef Param3 P3;            //(x z) is x::Apply<z>::Result            typedef typename Param1::Apply<Param3>::Result OuterExpr;            //(y z) is y::Apply<z>::Result            typedef typename Param2::Apply<Param3>::Result InnerExpr;            //((x z) (y z)) is OuterExpr::Apply<InnerExpr>::Result            typedef typename OuterExpr::Apply<InnerExpr> Applied;            typedef typename Applied::Result Result;          };        };      };    };  };};typedef S:Apply<I>::Result::Apply<I>::Result SII;typedef SII::Apply<SII>::Result SII_SII;

Both of these are correct as far as I can tell, but the expression (S I I (S I I)) (SII_SII in the above) evaluates to (S I I) somehow when it should evaluate to itself. I'd appreciate any help in tracking this bug down (especially any tips on how to debug template metaprograms in general).

"Walk not the trodden path, for it has borne it's burden." -John, Flying Monk

Polymorphic OOP

954

November 05, 2005 11:32 AM

Quote:Original post by Extrarius
Oh, also, I still have NO idea how to implement a 'dot[char] combinator' that "outputs [char]" and returns it's argument. Every method mentioned so far sounds far too static and doesn't sound as if it fits into my framework of unary metafunctions at all.

It fits your framework as best as it can since you decided to use template metaprogramming. If it's "too static," that's because you chose to use this entirely compile-time facility, not a runtime one. Everything with strictly template metaprogramming is going to be "far too static" for your needs because everything has to be done strictly at compile-time. Ouputting a char in template metaprogramming is not possible since it is a compile-time facility, unless you output an error message.

As I said earlier, if you want runtime output of data in the middle of execution, such as for the dot operator, then strictly template metaprogramming is not the tool you should be using. Instead, use expression templates such that the function types are all created at compile-time but evaluated at runtime. Right now you have to have them both created and evaluated at compile-time.

Quote:Original post by Extrarius
I'd appreciate any help in tracking this bug down (especially any tips on how to debug template metaprograms in general).

You actually have a couple of problems. Firstly, your code is not standards compliant since you aren't using template for disambiguation, I.E.

typedef typename Param1::Apply<Param3>::Result OuterExpr;

should be

typedef typename Param1::template Apply<Param3>::Result OuterExpr;

and the same for the others.

Aside from that, and asuming the single colon at the bottom is a typo, the reason you aren't getting the proper results you want is because when you instantiate that last template (SII's apply template instantiated with SII), the outer->inner evaluation is equivalent to SII's apply template being instantiated with SII. Basically, upon instantiation, it's similar to saying

template< typename B >struct apply{  typedef typename apply< B >::type type;};

which can't be evaluated. The difference is that the mistake in your case only happens with particular arguments, whereas here it happens with any argument and is diagnosable prior to any instantiations taking place.

Extrarius

1,412

Author

November 05, 2005 12:08 PM

Quote:Original post by Polymorphic OOP
[...]Basically, upon instantiation, it's similar to saying
template< typename B >struct apply{  typedef typename apply< B >::type type;};
which can't be evaluated. The difference is that the mistake in your case only happens with particular arguments, whereas here it happens with any argument and is diagnosable prior to any instantiations taking place.

I understand that it can't be evaluated, but somehow it IS being evaluated which of course results in an incorrect result. When I try to compile your example class, VS gives several errors that together say essential "this can't be evaluated" but the same does not happen for my example.

"Walk not the trodden path, for it has borne it's burden." -John, Flying Monk

C++ Template Metaprogramming Problem

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

C++ Template Metaprogramming Problem

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Reticulating splines