Les compilateurs que j'ai utilisés en C ou en Java ont une fonction de prévention du code mort (alerte lorsqu'une ligne ne sera jamais exécutée). Mon professeur dit que ce problème ne pourra jamais être entièrement résolu par les compilateurs. Je me demande pourquoi. Je ne suis pas trop familier avec le codage réel des compilateurs car il s'agit d'un cours théorique. Mais je me demandais ce qu'ils vérifient (comme les chaînes d'entrée possibles par rapport aux entrées acceptables, etc.), et pourquoi c'est insuffisant.
Réponses
Trop de publicités?
Le problème du code mort est lié à la Problème d'arrêt .
Alan Turing a prouvé qu'il est impossible d'écrire un algorithme général qui, étant donné un programme, sera capable de décider si ce programme s'arrête pour toutes les entrées. Il est possible d'écrire un tel algorithme pour des types spécifiques de programmes, mais pas pour tous les programmes.
Quel est le rapport avec le code mort ?
Le problème de Halting est réductible au problème de la recherche de code mort. C'est à dire, si vous trouvez un algorithme qui peut détecter le code mort en cualquier alors vous pouvez utiliser cet algorithme pour tester si cualquier le programme s'arrêtera. Puisqu'il a été prouvé que c'est impossible, il s'ensuit que l'écriture d'un algorithme pour un code mort est également impossible.
Comment transférer un algorithme pour le code mort en un algorithme pour le problème de Halting ?
C'est simple : vous ajoutez une ligne de code après la fin du programme dont vous voulez vérifier l'arrêt. Si votre détecteur de code mort détecte que cette ligne est morte, alors vous savez que le programme ne s'arrête pas. Si ce n'est pas le cas, vous savez que votre programme s'arrête (jusqu'à la dernière ligne, puis jusqu'à votre ligne de code ajoutée).
Les compilateurs vérifient généralement les choses dont on peut prouver la mort au moment de la compilation. Par exemple, les blocs qui dépendent de conditions dont on peut déterminer qu'elles sont fausses au moment de la compilation. Ou toute déclaration après un return (dans le même périmètre).
Ce sont des cas spécifiques, et il est donc possible d'écrire un algorithme pour eux. Il est peut-être possible d'écrire des algorithmes pour des cas plus compliqués (comme un algorithme qui vérifie si une condition est syntaxiquement une contradiction et renvoie donc toujours faux), mais cela ne couvrirait pas tous les cas possibles.
Joker_vD
Points
2313
Prenons la preuve classique de l'indécidabilité du problème de l'arrêt et changeons le détecteur d'arrêt en un détecteur de code mort !
Programme C#
using System;
using YourVendor.Compiler;
class Program
{
static void Main(string[] args)
{
string quine_text = @"using System;
using YourVendor.Compiler;
class Program
{{
static void Main(string[] args)
{{
string quine_text = @{0}{1}{0};
quine_text = string.Format(quine_text, (char)34, quine_text);
if (YourVendor.Compiler.HasDeadCode(quine_text))
{{
System.Console.WriteLine({0}Dead code!{0});
}}
}}
}}";
quine_text = string.Format(quine_text, (char)34, quine_text);
if (YourVendor.Compiler.HasDeadCode(quine_text))
{
System.Console.WriteLine("Dead code!");
}
}
}Si YourVendor.Compiler.HasDeadCode(quine_text) renvoie à false puis la ligne System.Console.WriteLn("Dead code!"); ne sera jamais exécuté, donc ce programme en fait hace ont un code mort, et le détecteur était faux.
Mais s'il retourne true puis la ligne System.Console.WriteLn("Dead code!"); sera exécuté, et puisqu'il n'y a plus de code dans le programme, il n'y a plus de code mort du tout, donc encore une fois, le détecteur avait tort.
Ainsi, un détecteur de codes morts qui ne renvoie que "Il y a un code mort" ou "Il n'y a pas de code mort" doit parfois donner de mauvaises réponses.
abligh
Points
15586
Si le problème de l'arrêt est trop obscur, pensez-y de la manière suivante.
Prenons un problème mathématique que l'on pense être vrai pour tous les nombres entiers positifs. n mais il n'a pas été prouvé que c'était le cas pour tous. n . Un bon exemple serait La conjecture de Goldbach que tout nombre entier pair positif supérieur à deux peut être représenté par la somme de deux nombres premiers. Ensuite (avec une bibliothèque bigint appropriée), exécutez ce programme (le pseudocode suit) :
for (BigInt n = 4; ; n+=2) {
if (!isGoldbachsConjectureTrueFor(n)) {
print("Conjecture is false for at least one value of n\n");
exit(0);
}
}Mise en œuvre de isGoldbachsConjectureTrueFor() est laissée comme un exercice pour le lecteur, mais dans ce but, elle pourrait être une simple itération sur tous les nombres premiers inférieurs à n
Maintenant, logiquement, ce qui précède doit être soit l'équivalent de :
for (; ;) {
}(c'est-à-dire une boucle infinie) ou
print("Conjecture is false for at least one value of n\n");car la conjecture de Goldbach doit être soit vraie, soit fausse. Si un compilateur pouvait toujours éliminer le code mort, il y aurait certainement du code mort à éliminer ici dans les deux cas. Cependant, ce faisant, votre compilateur devrait au moins résoudre des problèmes arbitrairement difficiles. Nous pourrions fournir des problèmes de manière prouvée difficile qu'il devrait résoudre (par exemple, des problèmes NP-complets) pour déterminer quel morceau de code éliminer. Par exemple, si nous prenons ce programme :
String target = "f3c5ac5a63d50099f3b5147cabbbd81e89211513a92e3dcd2565d8c7d302ba9c";
for (BigInt n = 0; n < 2**2048; n++) {
String s = n.toString();
if (sha256(s).equals(target)) {
print("Found SHA value\n");
exit(0);
}
}
print("Not found SHA value\n");nous savons que le programme imprimera soit "Valeur SHA trouvée", soit "Valeur SHA non trouvée" (points bonus si vous pouvez me dire laquelle est vraie). Cependant, pour qu'un compilateur soit capable d'optimiser raisonnablement cela prendrait de l'ordre de 2^2048 itérations. Il s'agirait en fait d'une excellente optimisation car je prédis que le programme ci-dessus fonctionnerait (ou pourrait fonctionner) jusqu'à la mort thermique de l'univers plutôt que d'imprimer quoi que ce soit sans optimisation.
ckuhn203
Points
1236
Je ne sais pas si le C++ ou le Java ont une Eval mais de nombreux langages permettent d'appeler des méthodes de type par nom . Prenons l'exemple VBA (artificiel) suivant.
Dim methodName As String
If foo Then
methodName = "Bar"
Else
methodName = "Qux"
End If
Application.Run(methodName)Le nom de la méthode à appeler est impossible à connaître avant l'exécution. Par définition, le compilateur ne peut donc pas savoir avec une certitude absolue qu'une méthode particulière ne sera jamais appelée.
En fait, dans l'exemple de l'appel d'une méthode par son nom, la logique de branchement n'est même pas nécessaire. Il suffit de dire
Application.Run("Bar")est plus que ce que le compilateur peut déterminer. Lorsque le code est compilé, tout ce que le compilateur sait est qu'une certaine valeur de chaîne est passée à cette méthode. Il ne vérifie pas si cette méthode existe avant l'exécution. Si la méthode n'est pas appelée ailleurs, par des méthodes plus normales, une tentative de trouver des méthodes mortes peut renvoyer des faux positifs. Le même problème existe dans tout langage qui permet d'appeler du code par réflexion.
dspfnder
Points
847
Le code mort inconditionnel peut être détecté et supprimé par des compilateurs avancés.
Mais il existe aussi un code mort conditionnel. Il s'agit du code qui ne peut pas être connu au moment de la compilation et qui ne peut être détecté que pendant l'exécution. Par exemple, un logiciel peut être configuré pour inclure ou exclure certaines fonctionnalités en fonction des préférences de l'utilisateur, rendant certaines sections de code apparemment mortes dans des scénarios particuliers. Ce n'est pas du vrai code mort.
Il existe des outils spécifiques qui peuvent effectuer des tests, résoudre les dépendances, supprimer le code mort conditionnel et recombiner le code utile au moment de l'exécution pour plus d'efficacité. C'est ce qu'on appelle l'élimination dynamique du code mort. Mais comme vous pouvez le constater, cela dépasse le cadre des compilateurs.
