c++ - 编译器可以识别模板元编程中的递归问题吗？

Question

在模板元编程中，如果递归被错误地实现并导致无限循环，语言编译器可以检测到它吗？还是编译器会遇到最终的堆栈溢出和崩溃？我敢打赌，编译器无法检测到这一点，因为这样做会违反停止问题的不可判定性。

我的结论正确吗？当然我可以用一段代码来试试这个，但我想在这种情况下听到更多合格的想法。

编辑：谢谢大家，我大致知道我对 tmp 计算理论方面的推断没有错。我也明白编译器实现可以有任意的递归深度限制（当然我重申我可以测试第二部分，但这只是我的观点）。

Answer 1

您通常无法检测到这种无限递归；模板元编程具有图灵能力，并且这种检测将相当于解决停机问题。与图灵难题一样，这并不意味着您无法检测到某些情况。

我认为编译器倾向于具有标准建立的模板可以嵌套的最小级别数，以及他们将诊断嵌套太深的最大数量。

Answer 2

该标准规定，实施可以（并且有效地将）限制一些数量，其中包括：

附件 B

• 递归嵌套模板实例化，包括模板参数推导期间的替换 (14.8.2)

一旦达到此数量的预定义限制，编译器很可能会退出，并带有适当的错误消息。

Answer 3

模板元编程是图灵完备的，所以是的，任何能够在所有情况下检测到无限循环（不会错误地将终止循环分类为无限）的编译器都能够解决停止问题。

但就像常规代码一样，可以检测到一些无限循环。不过，我认为任何编译器都不会检查，而是会在超过某个最大递归深度时抱怨。

Answer 4

是的，通常可以检测到

尽管停机问题在一般情况下是不可判定的，但对于许多（如果不是最具体的情况）来说，它肯定是可判定的。

还有一个简单明了的方法：限制允许的递归量。

因此，一般来说，答案是第一个：它检测到无限循环。

（如果您可以接受在某些情况下出错，则很容易检测到不会停止的程序。毕竟，任何编译器都不允许无限递归。）

Answer 5

你是正确的。在不限制模板元编程的递归堆栈帧的情况下检测无限递归将意味着找到停止问题的替代解决方案。

有一些特殊情况在理论上是可以检测到的。例如，如果您可以确保递归的引用透明性，并且如果最后一个函数调用接收到与实际参数相同的参数，那么您将处于无限递归调用中。C++ 对模板元编程不提供参考透明度保证。

Answer 6

当然，由于引用透明性，检测无限循环是可能的。这是微不足道的，但我没有测试哪个编译器可以做到这一点。

另一方面，如果递归生成无限的不同模板实例化（不在实例化级别上循环），则不太可能或不可能检测到。这是由于 Turung 的完整性。

对于每个模板实例化，编译器将生成一个有限树图，其中每个节点都是一个模板实例化。一旦编译器检测到后边/由于循环而导致图不是树，它应该中止。无限图/树（停止问题）可能会被检测到超时/有限的图大小。