Template Metaprogramming: Primitive Recursive?

Question

In this article, the writer asserts:

...the program did show that the template instantiation mechanism is a primitive recursive language that can perform nontrivial computations at compile time.

I found this rather interesting, as I help to teach a class in Theory of Computation which delves into the theory of primitive recursive functions. However, I was under the impression that Template Metaprogramming was Turing-complete, which is a strictly stronger statement than to say that it is primitive recursive...And after all, it is not very difficult to create a template metaprogram which fails to halt.

Am I missing something? Is Template Metaprogramming a strictly primitive recursive language, or am I correct in believing it to cover a wider range of programs?

Answer 1

I believe you just read too much into the text, and the "primitive" is not meant as "primitive recursive", but rather it is a "recursive language" (which sounds odd, I'd call describe that as a functional language, but never mind), which is primitive.

If you look at TMP as a functional language, it is not a very sophisticated one; thus, it is a primitive one.

But you are correct, TMP certainly is Turing-complete.

I doubt many people have heard of primitive recursive languages, and so this is just an unfortunate choice of words.

Answer 2

Unruh's program only demonstrated primitive recursion, that is, looping (I was actually present when this happened!). However it was immediately recognized that full recursion was supported (because indeed the implementation did not do tail rec optimisation).