Pourquoi est-il impossible de construire un compilateur qui permet de déterminer si une fonction C++ va changer la valeur d’une variable particulière ?

Question

J'ai lu cette ligne dans un livre:

Il ne devient impossible de construire un compilateur qui peut réellement déterminer si oui ou non une fonction C++ permet de changer la valeur d'un variable particulière.

Le paragraphe a été de parler de pourquoi le compilateur est conservatrice lors de la vérification de const-ness.

Pourquoi est-il impossible de construire un tel compilateur?

Le compilateur peut toujours vérifier si une variable est réaffecté, un non-const fonction est appelée sur elle, ou s'il est transmis sous la forme d'un non-const paramètre...

Answer 1

Pourquoi est-il impossible de construire un tel compilateur?

Pour la même raison que vous ne pouvez pas écrire un programme qui permettra de déterminer si le programme prendra fin. Ceci est connu comme le problème de l'arrêt, et c'est une de ces choses qui n'est pas calculable.

Pour être clair, vous pouvez écrire un compilateur qui permet de déterminer qu'une fonction n'modifier la variable dans certains cas, mais vous ne pouvez pas écrire une manière fiable que vous indique que la fonction va ou ne va pas changer la variable (ou arrêter) pour toutes les fonctions possibles.

Voici un exemple facile:

void foo() {
    if (bar() == 0) this->a = 1;
}

Comment un compilateur de déterminer, simplement en regardant le code, si foo ne changera jamais a? Si elle fait ou ne fait pas dépend des conditions externes à la fonction, à savoir la mise en œuvre de l' bar. Il n'y a plus que de la preuve que le problème de l'arrêt n'est pas calculable, mais c'est déjà bien expliqué liée à l'article de Wikipedia (et dans chaque calcul de la théorie des manuels scolaires), donc je vais pas tenter de l'expliquer correctement ici.

Answer 2

Imaginez que ce compiler existe. Supposons également que, pour des raisons pratiques, il fournit une fonction de bibliothèque qui renvoie 1 si la fonction passée modifie une variable donnée et 0 quand la fonction n’est pas. Alors que devrait imprimer ce programme ?

Answer 3

Ne pas confondre "sera ou ne sera jamais modifier une variable" pour "a un chemin d'exécution qui modifie une variable."

Le premier est appelé opaque prédicat de détermination, et il est carrément impossible de décider - en dehors de réduction à partir du problème de l'arrêt, vous pouvez simplement pointer la variable peut provenir d'une source inconnue (eg. l'utilisateur). Cela est vrai de toutes les langues, et pas seulement en C++.

La dernière déclaration, cependant, peut être déterminé en regardant l'arbre d'analyse, ce qui est quelque chose que tout optimiser les compilateurs n'. La raison n'est que pure fonctions (et referentially transparent fonctions, pour une définition de referentially transparent) ont toutes sortes de nice optimisations qui peuvent être appliquées, comme être facilement inlinable ou ayant leurs valeurs sont déterminées au moment de la compilation; mais de savoir si une fonction est pure, nous avons besoin de savoir si il peut toujours modifier une variable.

Donc, ce qui semble être une déclaration surprenante sur le C++ est en fait une simple déclaration au sujet de toutes les langues.

Answer 4

Je pense que le mot clé « si oui ou non une fonction C++ va changer la valeur d’une variable particulière » est « ». Il est certainement possible de construire un compilateur qui vérifie si oui ou non une fonction C++ n’est autorisé à modifier la valeur d’une variable particulière, vous ne pouvez pas dire avec certitude que le changement va se produire :

Answer 5

Je ne pense pas que c’est nécessaire appeler le problème de l’arrêt pour expliquer que vous ne pouvez pas algorithmiquement savent au moment de la compilation si une fonction donnée modifiera une certaine variable ou non.

Au lieu de cela, il suffit de faire remarquer que la comportement de la fonction dépend souvent de conditions d’exécution, que le compilateur ne peut pas connaître à l’avance. Par exemple

Comment le compilateur pourrait prédire avec certitude si `` sera modifiée ?