基于constexpr的计算图灵完成了吗？

Question

我们知道C++模板元编程是Turing完整的,但预处理器元编程却不是.

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

Answer 1

tl; dr:constexpr在C++ 11中没有图灵完备,由于语言规范中存在错误,但该错误已经在标准的后续草案中得到解决,而clang已经实现了修复.

constexpr,如ISO C++ 11国际标准中所规定的,不是图灵完备的.草图证明:

• 每个constexpr函数f对特定参数序列的结果(或非终止)a...仅由值确定a...
• 可以在常量表达式中构造的每个参数值必须是文字类型,其中[basic.types]p10:
  • 标量类型,
  • 参考,
  • 一个文字类型的数组,或
  • 类类型
• 上述每种情况都有一组有限的值.
  • 对于标量,非指针类型,这通常是简单的.
  • 对于要在常量表达式中使用的指针或引用,必须通过地址或引用常量表达式对其进行初始化,因此必须引用具有静态存储持续时间的对象,其中任何程序中只有一个有限的数量.
  • 对于数组,bound必须是常量,并且每个成员必须由常量表达式初始化,结果如下.
  • 对于类类型,存在有限数量的成员,并且每个成员必须是文字类型并且由常量表达式初始化,结果如下.
• 因此,所述一组可能的输入a...,其f可以接收是有限的,所以任何有限描述的constexpr系统是一个有限状态机,并因此不是图灵完整.

但是,自从C++ 11标准发布以来,情况发生了变化.

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

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

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

g ++和clang的中继版本实现了这个核心问题的解决方案,但是g ++的实现目前无法处理这个代码.

Answer 2

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