Discussion :

[neuromencien]

Bonjour.

Je voudrais savoir s'il est possible de calculer de façon statique les chemins d'exécution d'un programme?

J'ai recherché sur Google et je tombe sur beaucoup de thèses et de documents de recherche qui parlent du calcul du chemin d'exécution le plus long, mais ce n'est pas ce que je recherche. Je voudrais être capable de calculer tous les chemins d'exécution possible.

J'ai déja essayé de créer un prototype mais il ne fonctionne pas correctement.

Par exemple si on a :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
 
if (a == b) {
   //Une action A
}
else {
   //Une action B
}
 
//Une action C
 
if ((a == b) && (b < 2)) {
   //Une action D
}

Les chemins d'exécution possible sont :
A -> C -> D,
A -> C,
B -> C.

Mon prototype n'est déja pas capable de détecter que D ne peut suivre C que dans le cas ou l'on a pris la branche qui ne commence pas par A. Comment faire comprendre à mon programme que les deux conditions ont une partie commune? D'autant plus que le nom des variables peut changer voir leur valeur. Un

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

b++;

placé avant la dernière condition change complètement la liste des chemins d'exécution.

Est ce que tout celà est possible, ou est ce que ça relève de la SF? Et si c'est possible, ou peut-on trouver infos sur la façon de faire ça?

Merci d'avance pour vos réponses.

[10_GOTO_10]

Si un programme était capable de calculer la longueur du chemin le plus long dans un algorithme, il serait capable de déterminer si un programme boucle ou pas (longueur du chemin le plus long = infini). Or, un certain Mr Turing a démontré le contraire, donc il semblerait que ce soit impossible...

A condition que le théorème de Turing soit juste. Et personnellement, sans vouloir ouvrir une polémique, j'ai de sérieux doutes sur cette démonstration.

[Nemerle]

Allons-allons... sa démonstration est en béton armé!

[nletteron]

J'allais le dire.

On en revient à l'éternel problème de la décidabilité/indécidabilité d'un programme. Je te conseille tous les ouvrages qui trainent là dessus, tu risques d'être surpris sur le nombre de choses qu'on ne peut pas faire en informatique . Ensuite tout ce qui concerne les cours de calculabilité. Tu seras surpris aussi.

Théorème de Turing ? Ca me dit rien par contre.

Je pencherais plutôt pour le théorème de Gödel ou de Rice qui suffise à prouver qu'on est dans l'impossibilité à partir d'une propriété non triviale donnée de savoir si elle se termine ou non.

Tu pourras calculer le chemin d'un programme uniquement si ton algorithme est "décidable" (impropre au niveau du terme).

[10_GOTO_10]

Allons-allons... sa démonstration est en béton armé!

Aïe, ça y est. J'ai mis le doigt dans l'engrenage, j'aurais pas dû.

Il y a quelques années, j'ai eu un long échange de mails avec quelques spécialistes de la chose, qui n'avaient pas conclu sur le fond, mais plutôt avec des réponses du genre "mais qui es-tu, pauvre c.n, pour remettre en cause cette démonstration".

Sans entrer dans les détails, cette démonstration fait une joyeuse confusion entre un programme (suite d'instructions) et une instance de programme (instructions + données initiales). Elle conclut qu'un certain programme se termine et ne se termine pas à la fois. D'où contradiction, donc ce programme n'existe pas. Or, il ne s'agit pas de programmes mais de deux instances du même programme, et l'une peut très bien s'arrêter et pas l'autre. C'est comme si on disait que si W.....s plante sur un PC et pas sur un autre, il n'existe pas...

[nletteron]

L'engrenage m'intéresse perso .

J'aimerais bien que tu rentres dans le détail justement. J'aurais sans doute des questions là dessus. Ca m'intéresse fortement puis ça fait longtemps que j'ai pas eu le plaisir de palabrer de calculabilité.

[borisd]

Juste pour répondre à la question initiale, il semble que dans le cas général, la seule chose que tu puisses faire est de construire un émulateur (ou pourquoi pas te trouver un ordinateur ) et lancer ton programme dessus avec tous les jeux d'entrée possibles.
Après, tu peux certainement, heuristiquement, détecter un certain nombre de chemins et effectuer un certain nombre de déductions logiques qui invalideront des chemins impossibles. Et là, si tu considères que théoriquement ton programme ne sera pas parfait, tu peux en faire un qui s'approche de la perfection en, par exemple, tronquant simplement les arbres de recherche...

[10_GOTO_10]

L'engrenage m'intéresse perso .

Bon, ben si ça intéresse du monde...

De mémoire, j'avais, sur le même principe de démonstration, prouvé toutes sortes de choses toutes plus absurdes les unes que les autres (qu'un programme capable de dire si un nombre est pair ou pas n'existe pas), ce qui prouve que la démonstration est fausse. J'avais trouvé un contre-exemple: un langage de programmation (donc une machine de Turing, puisque tout automate à états finis est une machine de Turing) dans lequel il était très facile de dire si un programme s'arrêtait ou pas.

Je n'ai pas ces mails sous la main, mais ce soir je peux les retrouver. Je les mettrais ici.

[Jean-Marc.Bourguet]

Je voudrais savoir s'il est possible de calculer de
façon statique les chemins d'exécution d'un programme?

Théoriquement impossible (on a déjà cité le problème de l'arrêt). Même si
c'était théoriquement possible, résoudre le problème exactement aurait un
intérêt pratique limité pour cause de complexité trop grande (pire que
NP-Complet).

Pratiquement on peut arriver à des sur-ensembles et des sous-ensembles de
la solution exacte avec une complexité raisonnable. C'est utilisé dans la
phase d'optimisation des compilateurs.

J'ai déja essayé de créer un prototype mais il ne fonctionne pas
correctement.

Par exemple si on a :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
 
if (a == b) {
   //Une action A
}
else {
   //Une action B
}
 
//Une action C
 
if ((a == b) && (b < 2)) {
   //Une action D
}

Les chemins d'exécution possible sont :
A -> C -> D,
A -> C,
B -> C.

Mon prototype n'est déja pas capable de détecter que D ne peut suivre C que
dans le cas ou l'on a pris la branche qui ne commence pas par A. Comment
faire comprendre à mon programme que les deux conditions ont une partie
commune?

Regarde ce qui ce fait pour l'optimisation "common sub-expression". Une
autre chose que tu peux chercher est "symbolic evaluation".