template meta programming

[Ganesh]

I am not sure if the question is relevant to this group.

Is there a proof that template metaprogramming is Turing-complete? Is
the proof trivial - just replace all the template instantiaion with a
function call and since function calls are turing complete, template
metaprogramming is turing complete. I am not sure if this is a valid
proof. I may not even make sense, as I am not very confident when it
comes to theoritical computer science.

However, my main question is - template metaprograms can work only on a
given input input which are know statically at compile time (Correct me
if I am wrong). While a general C++ program can work on any input. If
this is the case, how can we conclude that template metaprograms have
the same computational power as a general C++ program? For eg, I tried
to write a quicksort using template metaprograms, but in vain. The way
one partitions the input set is highly input dependent and even for a
given input, the partition changes across the levels of recursion. How
can we make use of template meta programming, in a case like this?

Ganesh

 

[Mark P]

I am not sure if the question is relevant to this group.

Is there a proof that template metaprogramming is Turing-complete? Is
the proof trivial - just replace all the template instantiaion with a
function call and since function calls are turing complete, template
metaprogramming is turing complete. I am not sure if this is a valid
proof. I may not even make sense, as I am not very confident when it
comes to theoritical computer science.

It is Turing complete (and of course there is a proof) but your proof
does not work because your reduction goes the wrong way. You need to
provide a general transformation from a Turing complete program to a
template metaprogram, not the other way around.

However, my main question is - template metaprograms can work only on a
given input input which are know statically at compile time (Correct me
if I am wrong). While a general C++ program can work on any input. If
this is the case, how can we conclude that template metaprograms have
the same computational power as a general C++ program? For eg, I tried
to write a quicksort using template metaprograms, but in vain. The way
one partitions the input set is highly input dependent and even for a
given input, the partition changes across the levels of recursion. How
can we make use of template meta programming, in a case like this?

Just because template metaprograms are Turing complete doesn't mean they
are convenient to use. You can indeed write quicksort in a metaprogram
but you'll have to somehow supply the "input" to quicksort at compile
time. That is, it must somehow be embedded in the program that you give
to the compiler.

 

[Ferdi Smit]

I am not sure if the question is relevant to this group.

Is there a proof that template metaprogramming is Turing-complete? Is
the proof trivial - just replace all the template instantiaion with a
function call and since function calls are turing complete, template
metaprogramming is turing complete. I am not sure if this is a valid
proof. I may not even make sense, as I am not very confident when it
comes to theoritical computer science.

I think the simplest, most straight-forward way would be to implement a
turing machine in a template meta program. This shouldn't be too hard.
You have compile time multi-dimensional arrays, tmp lists, a tmp if-else
construct. In fact, after a google search, I just saw a paper by Todd
Veldhuizen doing the exact same thing. It requires some effort, but not
too much.

--
Regards,

Ferdi Smit (M.Sc.)
Email: (e-mail address removed)
Room: C0.07 Phone: 4229
INS3 Visualization and 3D Interfaces
CWI Amsterdam, The Netherlands