Un environnement d'exécution peut-il détecter une boucle infinie?

Serait-il possible pour un environnement d'exécution de détecter des boucles infinies et d'arrêter par la suite le processus associé, ou la mise en œuvre d'une telle logique équivaudrait-elle à résoudre le problème d'arrêt?

Aux fins de cette question, je définis une «boucle infinie» pour désigner une série d'instructions et les données de pile / tas de démarrage associées qui, une fois exécutées, ramènent le processus exactement au même état (y compris les données) qu'il était auparavant. initier la boucle infinie. (En d'autres termes, un programme générant une expansion décimale indéfiniment longue de pi n'est pas "coincé" dans une "boucle infinie", car à chaque itération, il a plus de chiffres de pi quelque part dans sa mémoire associée.)

(Porté depuis /programming//q/16250472/1858225 )

Il peut être théoriquement possible pour un environnement d'exécution de rechercher de telles boucles en utilisant la procédure suivante:

Après chaque instruction exécutée, l'environnement d'exécution ferait une image complète de l'état d'un processus en cours (c'est-à-dire toute la mémoire qui lui est associée, y compris les registres, le PC, la pile, le tas et les globaux), enregistrer cette image quelque part, puis vérifier pour voir s'il correspond à l'une de ses images précédemment enregistrées pour ce processus. S'il y a correspondance, le processus est bloqué dans une boucle infinie. Sinon, l'instruction suivante est exécutée et le processus est répété.

En fait, plutôt que d'effectuer cette vérification après chaque instruction, l'environnement d'exécution pourrait simplement interrompre périodiquement le processus et créer un état de sauvegarde. Si le processus est bloqué dans une boucle infinie impliquant n états, alors au plus n vérifications, un état en double sera observé.

Notez, bien sûr, que ce n'est pas une solution au problème d'arrêt; la distinction est discutée ici .

Mais une telle caractéristique serait un énorme gaspillage de ressources ; interrompre continuellement un processus pour enregistrer toute la mémoire qui lui est associée le ralentirait énormément et consommerait une énorme quantité de mémoire très rapidement. (Bien que les anciennes images puissent être supprimées après un certain temps, il serait risqué de limiter le nombre total d'images qui pourraient être enregistrées car une grande boucle infinie - c'est-à-dire une avec plusieurs états - pourrait ne pas se coincer s'il y en a trop peu états conservés en mémoire.) De plus, cette fonctionnalité ne fournirait pas vraiment autant d'avantages, car sa capacité à intercepter les erreurs serait extrêmement limitée et parce qu'il est relativement simple de trouver des boucles infinies avec d'autres méthodes de débogage (comme simplement parcourir le code et reconnaître l'erreur logique).

Par conséquent, je doute qu'un tel environnement d'exécution existe ou qu'il existera jamais, à moins que quelqu'un ne le programme juste pour des coups de pied. (Ce que je suis un peu tenté de faire maintenant.)

Supposons que le programme n'interagisse pas avec le monde extérieur, il est donc vraiment possible d'encapsuler tout l'état du programme. (Cela signifie qu'il ne fait aucune entrée, au moins.) En outre, supposons que le programme s'exécute dans un environnement déterministe de sorte que chaque état ait un successeur unique, ce qui signifie que le runtime n'est pas threadé ou que le threading peut être réduite de façon déterministe à une séquence.

Sous ces hypothèses hautement improbables mais théoriquement non limitatives, nous pouvons dupliquer le programme et l'exécuter en deux temps d'exécution distincts; chacun fera exactement le même calcul.

Alors faisons ça. Nous l'exécuterons une fois dans le runtime Tortoise, et en même temps nous l'exécuterons dans le runtime Hare. Cependant, nous ferons en sorte que le runtime Hare fonctionne exactement deux fois plus vite; chaque fois que le runtime Tortoise fait un pas, le runtime Hare fait deux pas.

$n$$p$$kn$$k$$kn\ge p$

Le coût total du test est d'un état supplémentaire et d'une comparaison d'état par étape, et il se terminera en pas plus de trois fois le nombre d'étapes nécessaires au programme pour terminer sa première boucle. (Une fois dans la tortue et deux fois dans le lièvre, pour un total de trois fois.)

Comme les termes que j'utilise impliquent, ce n'est que le célèbre algorithme de détection de cycle de Tortue et Lièvre de Robert Floyd .

Tout comme j'allais suggérer l'algorithme de détection de cycle de Floyd, le post de rici m'a battu. Cependant, le tout peut être rendu plus pratique en accélérant les comparaisons d'états complets.

Le goulot d'étranglement de l'algorithme proposé serait de comparer l'état complet. Ces comparaisons ne se terminent généralement pas, mais s'arrêtent tôt --- à la première différence. Une optimisation consiste à se rappeler où les différences passées se sont produites et à vérifier d'abord ces parties de l'état. Par exemple, conservez une liste d'emplacements et parcourez cette liste avant d'effectuer une comparaison complète. Lorsqu'un emplacement de cette liste expose une différence, arrêtez la comparaison (avec échec) et déplacez l'emplacement au début de la liste.

Une approche différente (et potentiellement plus évolutive) consiste à utiliser le hachage incrémentiel. Choisissez une fonction de l'état complet de telle sorte que les valeurs de hachage sont faciles à ajuster dans O (1) lorsqu'une partie de l'état change. Par exemple, prenez une somme pondérée de mots d'état mod un grand premier et concaténer avec la somme non pondérée mod un autre grand premier (peut également ajouter une somme pondérée modulaire de carrés de mots, avec un poids et un module différents). De cette façon, les mises à jour de hachage prendront O (1) à chaque étape d'exécution et les comparaisons prendront O (1) jusqu'à ce que vous obteniez un hit. La probabilité d'un faux positif (c'est-à-dire que les hachages correspondent alors que les états diffèrent) est très faible, et même si cela se produit, il amortira sur un grand nombre de vrais négatifs (les faux négatifs sont impossibles).

Bien sûr, dans la pratique, il semble plus probable de se retrouver dans des situations telles que la génération de chiffres du nombre pi --- les choses continuent à changer, mais ne finissent jamais. Une autre possibilité fréquente est que la boucle infinie alloue de la mémoire, auquel cas elle épuise rapidement toute la mémoire disponible.

Dans mon cours sur les algorithmes et les structures de données, notre autograder doit traiter les soumissions des étudiants qui se retrouvent parfois dans des boucles infinies. Ceci est pris en charge par un délai d'attente de 30 secondes et une certaine limite de mémoire. Les deux sont beaucoup plus lâches que les budgets d'exécution et de mémoire que nous imposons dans le cadre de l'évaluation. Je ne sais pas si l'implémentation d'une véritable détection de boucle infinie aurait beaucoup de sens dans ce contexte, car ces programmes s'exécuteront un peu plus lentement (c'est là que le support matériel pour le hachage d'état pourrait aider, mais encore une fois, vous auriez besoin d'utilisations supplémentaires pour justifier cela). Lorsque les élèves savent que leur programme a expiré, ils peuvent généralement trouver la boucle infinie.

L' outil de terminaison AProVE effectue une analyse statique sur les systèmes de réécriture (y compris une sous-classe de programmes Haskell) qui peut prouver la non-terminaison, donnant un exemple réel de programme sans terminaison. La technique est assez puissante et fonctionne en utilisant une variante d'une technique appelée rétrécissement .

Pour autant que je sache, il n'y a pas eu beaucoup de travail sur la détection de non-terminaison réelle pour les langues générales.