45 votes

Le calcul basé sur constexpr est-il complet?

Nous savons que C++ modèle de la métaprogrammation est Turing complet, mais préprocesseur la métaprogrammation est pas.

C++11 nous donne une nouvelle forme de métaprogrammation: calcul de constexpr fonctions. Cette forme de calcul Turing-complet? Je pense que depuis la récursivité et l'opérateur conditionnel (?:) sont autorisés dans constexpr fonctions, il serait, mais j'aimerais que quelqu'un avec plus d'expertise pour confirmer.

62voto

Richard Smith Points 3935

TLDR: constexpr en C++11 n'était pas Turing-complet, en raison d'un bogue dans la spécification de la langue, mais ce bug a été résolu dans les projets ultérieurs de la norme, et clang implémente déjà le correctif.

constexpr, comme spécifié dans la norme ISO C++11 norme internationale, n'est pas Turing-complet. Esquisse de la preuve:

  • Chaque constexpr fonction fs'résultat (ou de non-résiliation) sur une séquence particulière d'arguments, a... est déterminé uniquement par les valeurs de a...
  • Chaque valeur de l'argument qui peut être construit à l'intérieur d'une expression constante doit être d'un type de littéral, qui en [basic.types]p10 est:
    • un type scalaire,
    • une référence,
    • un tableau de type de littéral, ou
    • un type de classe
  • Chacun des cas ci-dessus a un ensemble fini de valeurs.
    • Pour un scalaire non-type de pointeur, cela découle trivialement.
    • Pour un pointeur ou une référence à être utilisé dans une expression constante, elle doit être initialisée par une adresse ou une référence constante de l'expression, il doit en référer à un objet statique de la durée de stockage, de qui il y a seulement une quantité fixe dans n'importe quel programme.
    • Pour un tableau, la limite doit être une constante, et chaque membre doit être initialisé par une expression constante, à partir de laquelle le résultat suit.
    • Pour un type de classe, il existe un nombre fini de membres, chaque membre doit être de type de littéral et initialisé par une expression constante, à partir de laquelle le résultat suit.
  • Par conséquent, l'ensemble des entrées possibles a... qui f peut recevoir est limité, de sorte que toute finitely-décrite constexpr système est une machine à états finis, et donc n'est pas Turing-complet.

Toutefois, depuis la publication du C++11 standard, la situation a changé.

Le problème décrit dans Johannes Schaub, en réponse à std::max() et std::min() pas constexpr a été signalé à la normalisation de C++ comité question centrale 1454. En février 2012 WG21 réunion, nous avons décidé que c'était un défaut dans la norme, et de la résolution choisie inclus la possibilité de créer des valeurs de types de classe avec le pointeur ou de référence, les membres qui désignent temporaires. Cela permet à une quantité illimitée d'informations accumulées et traitées par un constexpr de la fonction, et est suffisante pour faire constexpr évaluation de Turing-complet (en supposant que la mise en œuvre prend en charge la récursivité à une surabondance de profondeur).

Afin de démontrer la Turing-complétude de l' constexpr pour un compilateur, qui met en œuvre le projet de résolution de l'enjeu fondamental 1454, j'ai écrit une Turing-simulateur machine pour clang la suite de tests:

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

Tronc versions de g++ et clang mettre en œuvre la résolution de cette question fondamentale, mais g++'s la mise en œuvre est actuellement impossible de traiter ce code.

8voto

Andrzej Points 1388

1voto

mihaild Points 44

Si nous prenons en compte les restrictions de l'ordinateur réel - comme la mémoire finie et finie valeur de MAX_INT - puis, bien sûr, constexpr (et également de l'ensemble de C++) n'est pas Turing-complet.

Mais si nous allons supprimer cette restriction - par exemple, si nous pensons à propos de int complètement arbitraire entier positif alors oui, constexpr partie de C++ sera Turing. Il est facile à exprimer toute partielle récursive de la fonction.

0, S(n) = n+1 et des sélecteurs I_n^m(x_1, ..., x_n) = x_m et superposition, évidemment, peut être exprimé à l'aide de constexpr.

La récursion Primitive peut se faire de manière droite:

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));
}

Et pour une partie de la récursivité nous avons besoin d'un truc simple:

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

Nous obtenons donc toute partielle de la récursivité de la fonction en tant que constexpr.

Prograide.com

Prograide est une communauté de développeurs qui cherche à élargir la connaissance de la programmation au-delà de l'anglais.
Pour cela nous avons les plus grands doutes résolus en français et vous pouvez aussi poser vos propres questions ou résoudre celles des autres.

Powered by:

X