是基于constexpr的计算图灵完成吗？ [英] Is constexpr-based computation Turing complete?

问题描述

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

C + +11给了我们一种新的元编程形式：计算constexpr函数。这种形式的计算图灵完成吗？我认为，因为递归和条件运算符（？:)是允许在constexpr函数，这将是，但我想要有更多的专业知识的人来确认。

解决方案

tl; dr： constexpr 在C ++ 11中不是Turing完成，由于语言规范中的一个错误，但是该漏洞已在标准的后续草稿中得到解决，并且clang已经实现了修复。

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

• 每个 constexpr 函数 f 对特定参数序列的结果（或非终止） a ... 仅由 a ...


• 可以在常量表达式中构造的每个参数值必须是文字类型， [basic.types] p10 是：
  
  
  
  
  • 标量类型，
  
  
  • a
  
  
  • 一个类型
  
  
  
  • 
    
  • 上述每种情况都有一组有限的值。
    
    
    
    
    • 对于标量非指针类型，这是简单的。
    
    
    • 对于要使用的指针或引用在常量表达式中，它必须由地址或引用常量表达式初始化，因此必须引用具有静态存储持续时间的对象，在任何程序中只有一个有限数量的对象。
    
    
    • 对于数组，绑定必须是一个常量，并且每个成员都必须用一个常量表达式初始化，结果如下。
    
    
    • 对于类类型，有一个有限数
    
    
  
  
  • 因此，每个成员必须是文字类型，并由常量表达式初始化，可以接收的可能输入 a 其中 f 可以接收是有限的，因此任何有限描述的 constexpr system是一个有限状态机，因此不是Turing完成。
  
  
  
  
  

  自从C ++ 11标准发布以来，情况已经改变。

  
  
  

  约翰内斯·绍布对 std :: max（）和std :: min（）not constexpr 被报告给C ++标准化委员会作为核心问题1454.在2012年2月WG21会议上，我们决定这是标准中的缺陷，所选择的解决方案包括能够使用指针或指定临时表达式的引用成员创建类类型的值。这允许通过 constexpr 函数来累积和处理无限量的信息，并且足以使 constexpr 评估图灵完成（假设实现支持递归到无界深度）。

  
  
  

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

  
  
  

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

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

  
  

  We know that C++ template metaprogramming is Turing complete, but preprocessor metaprogramming is not.

  C++11 gives us a new form of metaprogramming: computation of constexpr functions. Is this form of computation Turing-complete? I am thinking that since recursion and the conditional operator (?:) are allowed in constexpr functions, it would be, but I would like someone with more expertise to confirm.

  解决方案

  tl;dr: constexpr in C++11 was not Turing-complete, due to a bug in the specification of the language, but that bug has been addressed in later drafts of the standard, and clang already implements the fix.

  constexpr, as specified in the ISO C++11 international standard, is not Turing-complete. Sketch proof:

  • Every constexpr function f's result (or non-termination) on a particular sequence of arguments, a..., is determined only by the values of a...
  • Every argument value that can be constructed inside a constant expression must be of a literal type, which by [basic.types]p10 is either:
    • a scalar type,
    • a reference,
    • an array of literal type, or
    • a class type
  • Each of the above cases has a finite set of values.
    • For a scalar, non-pointer type, this follows trivially.
    • For a pointer or reference to be used in a constant expression, it must be initialized by an address or reference constant expression, so must refer to an object with static storage duration, of which there are only a finite quantity in any program.
    • For an array, the bound must be a constant, and each member must be initialized by a constant expression, from which the result follows.
    • For a class type, there are a finite number of members, and each member must be of literal type and initialized by a constant expression, from which the result follows.
  • Therefore, the set of possible inputs a... which f can receive is finite, so any finitely-described constexpr system is a finite state machine, and thus is not Turing-complete.

  However, since the publication of the C++11 standard, the situation has changed.

  The problem described in Johannes Schaub's answer to std::max() and std::min() not constexpr was reported to the C++ standardization committee as core issue 1454. At the February 2012 WG21 meeting, we decided that this was a defect in the standard, and the chosen resolution included the ability to create values of class types with pointer or reference members that designate temporaries. This allows an unbounded quantity of information to be accumulated and processed by a constexpr function, and is sufficient to make constexpr evaluation Turing-complete (assuming that the implementation supports recursion to an unbounded depth).

  In order to demonstrate the Turing-completeness of constexpr for a compiler that implements the proposed resolution of core issue 1454, I wrote a Turing-machine simulator for clang's test suite:

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

  Trunk versions of both g++ and clang implement the resolution of this core issue, but g++'s implementation currently is unable to process this code.

  这篇关于是基于constexpr的计算图灵完成吗？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！