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]

Ganesh wrote:

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.
Ganesh

[Ferdi Smit]

Ganesh wrote:

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: Fe********@cwi.nl
Room: C0.07 Phone: 4229
INS3 Visualization and 3D Interfaces
CWI Amsterdam, The Netherlands