44

我们知道C++ 模板元编程是图灵完备的，但预处理器元编程不是。

C++11 为我们提供了一种新的元编程形式：constexpr 函数的计算。这种计算形式是图灵完备的吗？我在想，由于在 constexpr 函数中允许递归和条件运算符 (?:) ，它会是这样，但我希望有更多专业知识的人来确认。

4

3 回答 3

60

tl; dr：constexpr由于语言规范中的错误，C++11 中的图灵不完整，但该错误已在标准的后续草案中得到解决，并且 clang 已经实现了修复。

constexpr，按照 ISO C++11 国际标准的规定，不是图灵完备的。草图证明：

  • 每个constexpr函数f在特定参数序列上的结果（或非终止）a...仅由a...
  • 可以在常量表达式中构造的每个参数值都必须是文字类型，可以[basic.types]p10是：
    • 标量类型，
    • 一个参考，
    • 文字类型的数组，或
    • 类类型
  • 上述每种情况都有一组有限的值。
    • 对于标量、非指针类型，这很简单。
    • 常量表达式中使用的指针或引用，必须由地址或引用常量表达式初始化，因此必须引用具有静态存储持续时间的对象，在任何程序中该对象的数量都是有限的。
    • 对于一个数组，边界必须是一个常量，并且每个成员都必须由一个常量表达式初始化，结果来自该表达式。
    • 对于类类型，成员的数量是有限的，并且每个成员必须是字面量类型并由常量表达式初始化，结果来自该常量表达式。
  • a...因此，可以接收的可能输入的集合f是有限的，因此任何有限描述的constexpr系统都是有限状态机，因此不是图灵完备的。

然而，自从 C++11 标准发布后，情况发生了变化。

Johannes Schaub 对std::max() 和 std::min() not constexpr的回答中描述的问题已作为核心问题 1454 报告给 C++ 标准化委员会。在 2012 年 2 月的 WG21 会议上，我们决定这是一个缺陷标准和选择的解决方案包括使用指定临时对象的指针或引用成员创建类类型值的能力。这允许函数累积和处理无限量的信息constexpr，并且足以使constexpr评估图灵完备（假设实现支持递归到无限深度）。

为了演示constexpr实现核心问题 1454 建议解决方案的编译器的图灵完备性，我为 clang 的测试套件编写了一个图灵机模拟器：

http://llvm.org/svn/llvm-project/cfe/trunk/test/SemaCXX/constexpr-turing.cpp

g++和clang的trunk版本都实现了这个核心问题的解决，但是g++的实现目前无法处理这个代码。

于 2012-03-02T05:39:26.427 回答
8

看看这些。我编译了这些示例，它们在 GCC 4.6 中工作： 编译时计算，编译时解析字符串 - 第一部分，编译时解析字符串 - 第二部分

于 2012-02-08T22:48:35.333 回答
1

如果我们考虑到真实计算机的限制——例如有限内存和 MAX_INT 的有限值——那么，当然，constexpr（以及整个 C++）不是图灵完备的。

但是如果我们取消这个限制——例如，如果我们将 int 视为一个完全任意的正整数——那么是的，C++ 的 constexpr 部分将是图灵完备的。很容易表达任何部分递归函数。

0, S(n) = n+1 和选择器 I_n^m(x_1, ..., x_n) = x_m 和叠加显然可以用 constexpr 表示。

原始递归可以直接完成：

constexpr int h(int x1, ..., int xn, int y) {
  return (xn == 0) ? f(x1, ..., xn) : g(x1, ..., xn, y-1, h(x1, ..., xn, y-1));
}

对于部分递归，我们需要一个简单的技巧：

constexpr int h(int x1, ... int xn, int y = 0) {
  return (f(x1, ... xn, y) == 0) ? y : h(x1, ..., xn, y+1);
}

所以我们得到任何部分递归函数作为 constexpr。

于 2012-02-21T12:52:11.093 回答