Sign in to follow this  
Extrarius

C++ Template Metaprogramming Problem

Recommended Posts

I'm working on implementing a rather complicated metaprogramming system in C++ using a system quite a bit like that used in boost (with metafunction classes that have a templated Apply function that defines a Result type), but I'm not sure how to implement something using that methodology: Basically, I want a metafunction class BuildString which takes a character as a template parameter. This BuildString<char Character> then defines a templated Apply function which defines two things: It defines a Result type equil to it's template parameter ('identity function'), and it defines a static member of type std::string that is initialized to std::string(1, Character). So far, so good. I have exactly that:
template <char Character>
struct BuildString
{
	template<class Param1>
	struct Apply
	{
		typedef Param1 Result;
		static const std::string Output;
	};
};
template <char Character>
template <class Param1>
const std::string BuildString<Character>::Apply<Param1>::Output = std::string(1, Character);


It works perfect, as far as I can tell (BuildString<'A'>::Apply<void>::Output is "A"). Unfortunately, that's not all I need it do to. I also want to specialize the definition of Output such that if Apply's Param1 is a BuildString<NestedChar>::Apply<Anything>::Result, instead of being a single character, Output will be std::string(1, Character) + BuildString<NestedChar>::Apply<Anything>::OutputString so I can nest them to build up a string into the Output of the outermost BuildString. Is it at all possible to do this? I've tried quite a few different things and I can't get any of them to work (some compile but don't have expected result - it always just uses a single character for Output). If there is another way to build up strings a character at a time that will fit with this ::Apply<> metafunction framework, I wouldn't mind having to use something completely different (though something easy to use would be preferred), as long as I can build up strings a character at a time with the character being a template function. Also, just as an aside, does the standard allow limits on things like this? I know there can be a recursion limit, but what about when you're not actually iterating, such as BuildString<'A'>::Apply<BuildString<'B'>::Apply<BuildString<'C'>::Apply<Q>::Result>::Result>::Output etc replacing Q with more buildstring metacalls?

Share this post


Link to post
Share on other sites
Eh? You want to concatenate literals at compile-time and have the result behave like a std::string? You won't be able to avoid a run-time std::string ctor call as far as I can figure, anyway. Why not just do the usual things for concatenation and wrap the whole thing in the ctor call? I.e. const char * bar = "bar"; std::string("foo" bar "baz");

Share this post


Link to post
Share on other sites
The reason I need this is that I need to be able to integrate it with a rather large library I'm working on (for fun =-) to do a LOT of stuff using template metaprogramming. The library can already do lots of awesome stuff (well, theoretically), but there isn't a way to output the result all the processing it does. If I had this, I could make everything start with "" for output and 'bubble' output up through the whole system to the final result.

I don't care how it actually gets the result to the top (As long as it's not through a single global, because the library will need different instantiations to create different strings), but I have a whole system of classes fitting the pattern of BuildString (normal classes with a templated Apply that defines a type Result), and the idea is that putting a BuildString<'C'> into the chain somewhere it should add 'C' to the growing string so that at the end, the string will contain the proper characters in the proper order.

The only reason I'm using std::string is because I figured it'd be easiest to use it's simple operator+ to do the concatenation instead of defining some kind of crazy StringCat metafunction that would work with fixed-sized character arrays.

If you have any idea at all how to acomplish this goal (have a template metaprogram return a string that is modified by multiple metafunctions), feel free to mention any alternatives =-)

If you want to know more about the kind of model I'm using, you can look at Boost::MPL, especially the tutorial. Basically, the main difference is that instead of apply I use Apply and instead of ::type I use ::Result

Share this post


Link to post
Share on other sites
Quote:
Original post by Extrarius
I also want to specialize the definition of Output such that if Apply's Param1 is a BuildString<NestedChar>::Apply<Anything>::Result, instead of being a single character, Output will be std::string(1, Character) + BuildString<NestedChar>::Apply<Anything>::OutputString so I can nest them to build up a string into the Output of the outermost BuildString.

Don't use class-static const strings here, since the order of construction between them is not fully defined. Prefer static const objects in member functions or just locals returned by value. Even better, logically concatenate them at compile-time and put them into a char array of appropriate length, initialized with an initializer list.

As well, watch out for nested template instantiation depth. The standard recommends that compilers have at least a depth of 17, though most compilers do go much deeper than that. Still, keeping it low can have a noticeable impact on compile-times.

Really though, you're much better off using preprocessor metaprogramming to generate a variadic-style template parameter list and then pass all of your characters to that (i.e. instantiated like string< 'a', 'b', 'c', 'd' >). Then define metafunctions for concatenating two strings, etc. However, why build that from scratch when you can use a Boost.MPL vector_c of characters inside the implementation of your compile-time string type? Even if you are just doing it for the sake of learning, I really wouldn't recommend just working entirely from scratch as it's all pretty simple stuff, just tedious to implement, becoming more of a project in preprocessor metaprogramming if you want to do it correctly rather than template metaprogramming.

Share this post


Link to post
Share on other sites
Quote:
Original post by Polymorphic OOP
[...]As well, watch out for nested template instantiation depth. The standard recommends that compilers have at least a depth of 17, though most compilers do go much deeper than that. Still, keeping it low can have a noticeable impact on compile-times.[...]

By this, do you mean that with a class like so:
struct I
{
template<class Param1>
struct Apply
{
typedef Param1 Result;
};
};
(a simple identity metafunction) that there is a maximum number of times I can do the following:

typedef X Type1;
typedef I::Apply<Type1>::Result Type2;
typedef I::Apply<Type3>::Result Type3;
typedef I::Apply<Type4>::Result Type4;
//... etc ... for TypeN
So that I couldn't (depending on the compiler) have a Type65536 declared in such a way (presuming the compiler doesn't 'optimize' the iteration out and just assign them all type X)? I know that a recursion limit is allowed, but I was really hoping I could do the above as many times as I want and still be assured that every standards compliant compiler will correctly compile the code.

Share this post


Link to post
Share on other sites
I wouldn't think you'd have much luck using std::string for compile time concatenation, unfortunately. It's hard to imagine any substitute for this either.

Though I probably don't know any more than you do in this area. There's my 2c anyway.

Edit: Wow believe it or not, I had this window open so long (behind others), that at the time I posted, no one else had. It's good to know that I was on the right track anyway.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
In case you're wondering what I'm trying to do, I'm trying to implement a turing complete language entirely via templates (which shouldn't be possible since the template language is supposedly not turing complete). The language I'm trying to implement is a minimalist version of Unlamda[1], leaving out the D and C functions since I'm not sure how to implement them via templates (or if it's possible). I do, however, have the SKI combinator trio implemented, and for the most part they work - I can construct an expression and get a (usually correct) result by using typeid().name() to output the final value. This is an unsatisfactory output method, though, because it is very difficult to read (end up with things like "struct S::Apply(struct I)::Result::Apply(struct I)::Result" for (S I I) because of currying) and also because it's entirely compiler-dependant (and might just return an empty string iirc) so it can't actually be used to calculate something at compile time that is later used at run time (the recursion limit eliminates the possibility of walking the answer like a tree/list to convert types into simple strings - I thought it didn't apply to the nested approach but I'm not sure now since Polymorphic OOP hasn't replied to my question).

If, however, I could get a build-string-char-by-char function working, then I could use it to build usable output in the same way that Unlambda[1]s dot-char function works (in fact, I could then translate many unlambda program straight to template metacode).

[1] http://en.wikipedia.org/wiki/Unlambda

-Extrarius

Share this post


Link to post
Share on other sites
Quote:
Original post by Extrarius
By this, do you mean that with a class like so:

It means that the standard recommends that compilers allow you to recursively instantiate a metafunction at least 17 times (only a recommendation, most go much beyond that, but still something to consider). Anyway, the main point is, don't rely on instantiating a template 50 times recursively just to make a 50 character long string, regardless of what your compiler can handle. You're just going to end up with an extremely complex instantiated type and, depending on how you further work with the type, you're probably going to have high complexity for many operations. If you just use preprocessor metaprogramming to generate a template parameter list of a fairly large size and use that, then make other intrinsic metafunctions for dealing with the string instantiations you'll get a much easier template to work with and one which will most-likely compile much faster.

But really, if you went that route, you might as well just use Boost.MPL.

Quote:
Original post by Extrarius
In case you're wondering what I'm trying to do, I'm trying to implement a turing complete language entirely via templates (which shouldn't be possible since the template language is supposedly not turing complete).

Actually, templates are turing complete.

Quote:
Original post by Extrarius
The language I'm trying to implement is a minimalist version of Unlamda

In that case have fun, and continue on with whatever choices are appropriate to reach the paradigm you want. Just keep in mind that template facilities aren't best suited for this style of programming so you'll probably encounter long compile-times and possibly reach compiler limits along the way.

Quote:
Original post by Extrarius
I can construct an expression and get a (usually correct) result by using typeid().name() to output the final value.

Yeah, definately don't do that. Perform everything logically at compile-time and then instantiate one type to represent the results of arbitrarily complex operations performed at compile-time when requested. Don't use, for instance, runtime string concatenation facilities as you described in your previous post, just build one single runtime string when requested, initialized strictly with data already concatenated at compile-time, as the information is all known at compile-time anyway.

As a side note, if you are just using the string at runtime and are using runtime string concatenation facilities anyway, then there is no reason for you to be using template metaprogramming to begin with, as expression templates would generally provide a superior alternative. Use template metaprogramming if the result is needed at compile-time, such as to calculate a value needed to instantiate another template or to create a complex type from data which needs to be known at compile-time. Here it just sounds like you want all of the results at runtime.

Quote:
Original post by Extrarius
If, however, I could get a build-string-char-by-char function working, then I could use it to build usable output in the same way that Unlambda[1]s dot-char function works (in fact, I could then translate many unlambda program straight to template metacode).

You can do that, an by all means, don't let the recommended compiler limit stop you (again, most compilers go well beyond it). I wouldn't wory about the limit much as I doubt you'll be using it much for extremely complex data, but its still something to consider and shows that templates generalyl aren't best-suited for this particular type of metaprogramming. Anyway, it's more compile-times and ease of use that I'd worry about since the syntax is going to start looking hairy pretty quickly. It's not exactly a style of programming that I'd want to use with templates.

Share this post


Link to post
Share on other sites
Quote:
Original post by Polymorphic OOP
[...]Actually, templates are turing complete.[...]
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.

Quote:
[...]just build one single runtime string when requested, initialized strictly with data already concatenated at compile-time, as the information is all known at compile-time anyway.[...]
I'm not sure how to do it this way any more than any other way. I would greatly appreciate a more detailed explanation. Realize, though, that whatever method I use must be embeddable within a chain of combinators (and it should act like the Identity Combinator 'I' that I posted above, as far as how it defines it's Result type).

Quote:
[...]the syntax is going to start looking hairy pretty quickly. It's not exactly a style of programming that I'd want to use with templates.
Not really:
(S I I (S I I)) becomes:

#define Eval(F,A) F::Apply<A>::Result

typedef Eval(Eval(S, I), I) SII;
typedef Eval(SII, SII) SII_SII;
Not pretty, but not really that bad as far as template metaprogramming goes. Of course, it won't be pretty for functions that do any real computation, but neither is the actual combinator language or it's base, lambda calculus. It's not part of the specification to be pretty =-)

If it always gave the correct answer, it'd be pretty impressive (IMO anyways).
(S I I (S I I)) should evaluate to (S I I (S I I)) - it can't be simplified and after a few evaluations you end up with the same thing you started with - but for some reason it comes back as (S I I) despite the fact that many other test cases return the proper answers. I expected it to fail to compile (recursion limit), but the incorrect result is extremely puzzling:

(S I I (S I I)) => {(S x y z) means ((x z) (y z))}
(I (S I I) (I (S I I)) => Outer=(S I I), Inner=(S I I) {Verified up to here}
(Outer Inner) ?? => ?? (S I I)
I'm not sure what causes the last step to evaluate to (S I I)
Is this caused by a recursion limit? I thought that when the limit was reached, the compiler would emit an error of some kind. If incorrect behavior is allowed, it's quite puzzling.

Should I post my definition of metafunction classes S and K ('Combinator I' was posted earlier)? Anybody interested in helping me debug some very simple template code that would be turing complete without recursion limits?

[Edited by - Extrarius on November 4, 2005 5:12:57 PM]

Share this post


Link to post
Share on other sites
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.

Quote:
Original post by Extrarius
I'm not sure how to do it this way any more than any other way. I would greatly appreciate a more detailed explanation. Realize, though, that whatever method I use must be embeddable within a chain of combinators (and it should act like the Identity Combinator 'I' that I posted above, as far as how it defines it's Result type).

The most easily optimized way, but having limitation based on a size you would personally decide, would be to create a static const char array large enough to hold the entire string, and then just use an initializer list in the initialization of the char array, with each element being a compile-time constant taken from the template instantiations, thereby making the array initialized prior to any constructors for any types, therefore avoiding problems with construction order.

Short of that, I'd recommend using a static const char array reference inside of a function which is initialized to a static const char array created inside of another function. Inside of the function which directly has the static char array, use template metaprogramming to unravel a simple loop which just copies the elements of the compile-time string into the static char array. Since the local array reference in the other function is also static, the function doing the initialization is only called once, and since the initialization is based off of all compile-time constants and since you are just interfacing with it through a reference, there's going to be minimal overhead. As well, since you are using static arrays inside of functions, you also avoid any construction order problems.

If you want the result to be a ::std::string, just initialize the string with the char array in the above examples. Still, you shouldn't ever be resorting to fully runtime concatenations considering its based around template metaprogramming.

Quote:
Original post by Extrarius
I thought that when the limit was reached, the compiler would emit an error of some kind.

It will emit an error if it's reached. I didn't look through your logic, but if you are having problems it's most-likely do to a mistake in code.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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 parameter
struct 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 currying
struct 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).

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this