Can compilers identify recursion issues in Template Meta programming?

Question

In Template Meta Programming if a recursion is wrongly implemented with a resulting infinite loop, can the language compiler detect it? Or will the compiler just encounter an eventual stack overflow and crashe? My bet would be that compiler cannot detect this because doing so would violate the undecideability of the halting problem.

Am I right with the conclusion? Of course I could try this out with a piece of code, but I would like to hear more qualified thinking in this case.

Edit : Thanks guys, I get a general idea that my inference on the computation theory aspect of tmp was not wrong. I also understand that compiler implementations can have arbitrary recursion depth limits(Of course I reiterate that I could have tested this second part, but it was only my side-point).

Answer 1

You are correct. Detecting an infinite recursion without limiting the recursion stack frames on template meta programming would mean finding an alternative solution to the halting problem.

There are a few special cases which are, in theory, detectable. For example, if you can ensure referential transparency on the recursion and if the last function call receives the same parameters as the actual one, you are on an infinite recursive call. C++ offers no referential transparency warranty on template meta programming.

Answer 2

The standard states that implementations can (and effectively will) limit some quantities that among others include:

Annex B

• Recursively nested template instantiations, including substitution during template argument deduction (14.8.2)

The compiler will most probably bail out once its predefined limit for this quantity is reached, with an appropriate error message.

Answer 3

Of course, it IS POSSIBLE to detect infinite-loops due to referential transparency. That is trivial, but I didn't test which compiler does that.

On the other hand, it is either unlikely or impossible to detect, iff the recursion generates infinite DIFFERENT template instantiations (which do not loop on the instantiation level). This is due Turung completeness.

For each template instantiation the compiler will generate a finite tree graph where every node is a template instantiation. As soon as the compiler detects a back-edge/that the graph is no tree due to a loop, it should abort. Infinite graphs/trees (Halting problem) will probably be detected with timeouts / limited graph size.

Answer 4

Yes, it is usually detectable

Although the halting problem is undecidable in the general case, it is certainly decidable for many if not most specific cases.

And the easy, obvious, way to do that: limit the amount of recursion allowed.

So the answer, in general, is the first: it detects the infinite loop.

(It's easy to detect programs that don't stop if you can accept being wrong in certain cases. After all, unlimited recursion is not allowed by any compiler.)

Answer 5

Template metaprogramming is Turing complete, so yes, any compiler that is able to detect infinite loops in all cases (without mistakenly classifying terminating loops as infinite) would be able to solve the halting problem.

But just like regular code, some infinite loops could be detected. I don't think any compilers would check, though, and instead will just complain if you exceed some maximum recursion depth.

Answer 6

You can't in general detect such infinite recursion; template metaprogramming is Turing capable, and to such detection would amount to solving the halting problem. As is usual with Turing hard problems, that doesn't mean you can't detect certain cases.

I think the compilers tend to have a minimum number of levels that templates may nest established by the standard, and a maximum number at which point they'll diagnose a nesting-too-deep.