Quand êtes-vous tombé sur le problème qui s’arrête sur le terrain? [fermé]

Question

Quand avez-vous personnellement rencontré le problème bloquant Sur le terrain? Cela peut arriver lorsqu'un collègue / chef suggère une solution qui violerait les limites fondamentales du calcul, ou lorsque vous réaliserez vous-même qu'un problème que vous essayez de résoudre est en fait impossible à résoudre.

La dernière fois que j'ai eu cette idée, c’était lors de l’étude des dactylographes. Notre classe s'est rendu compte qu'il serait impossible d'écrire un vérificateur de type parfait (celui qui accepterait tous les programmes s'exécutant sans erreur de type et rejetterait tous les programmes qui s'exécuteraient avec des erreurs de type), car cela résoudrait en fait le problème d'arrêt . Une autre a été lorsque nous avons réalisé, dans la même classe, qu’il serait impossible de déterminer si une division se ferait jamais par zéro, à l’étape de la vérification du type, car vérifier si un nombre, au moment de l’exécution, est égal à zéro, est également correct. une version du problème d’arrêt.

Answer 1

J'ai littéralement reçu le problème d'arrêt, comme dans "écrire un plug-in de moniteur pour déterminer si un hôte est hors service". Sérieusement? OK, alors je vais juste lui donner un seuil. "Non, car il pourrait remonter par la suite."

De nombreux exposés théoriques ont suivi.

Answer 2

Il y a des années, je me souvenais d'avoir lu une critique (dans le magazine Byte, je crois) d'un produit appelé Basic Infinite Loop Finder ou BILF. BILF était censé analyser votre code source Microsoft Basic et rechercher les boucles qui ne se terminaient pas. Il prétendait pouvoir trouver n'importe quelle boucle infinie dans le code.

L’examinateur a été assez avisé pour souligner que, pour que ce programme fonctionne dans tous les cas, il devait résoudre le problème persistant et allait jusqu’à fournir une preuve mathématique de la raison pour laquelle il ne pouvait pas fonctionner dans tous les cas.

Dans le prochain numéro, ils ont publié une lettre d'un représentant de l'entreprise expliquant que le problème serait résolu dans la prochaine version.

Mise à jour : j'ai rencontré une image de l'article sur imgur. Je me suis souvenu du mauvais magazine. C'était l'informatique créative, pas Byte. Sinon, c'est à peu près ce dont je me souvenais.

Vous pouvez en voir une version haute résolution sur imgur .

Answer 3

Le projet sur lequel je travaille en ce moment présente des problèmes indécidables. Il s’agit d’un générateur de tests unitaires. En général, il s’efforce donc de répondre à la question "Que fait ce programme" ? Ce qui est un exemple d’un problème d’arrêt. Un autre problème qui est apparu au cours du développement est "ont deux fonctions (de test) identiques la même" ? Ou même "L’ordre de ces deux appels (assertions) est-il important" ?

Ce qui est intéressant à propos de ce projet est que, même si vous ne pouvez pas répondre à ces questions dans toutes , vous pouvez trouver des solutions intelligentes permettant de résoudre le problème à 90%. le temps, qui pour ce domaine est en fait très bon.

D'autres outils qui tentent de raisonner sur d'autres codes, tels que l'optimisation des compilateurs / interprètes, les outils d'analyse de code statique, voire les outils de refactoring, risquent de frapper (et donc d'être obligés de trouver des solutions de contournement) le problème en cours d'arrêt.

Answer 4

Exemple 1. Combien de pages de mon rapport?

Quand j’apprenais à programmer, j’ai joué à créer un outil pour imprimer de jolis rapports à partir de données. Évidemment, je voulais que ce système soit vraiment flexible et puissant afin que ce soit le générateur de rapports qui mette fin à tous les générateurs de rapports.

La définition du rapport était si flexible que Turing était terminée. Il pourrait examiner des variables, choisir entre plusieurs alternatives, utiliser des boucles pour répéter des choses.

J'ai défini une variable intégrée N, le nombre de pages de l'instance de rapport. Vous pouvez donc insérer une chaîne indiquant "page n sur N". sur chaque page. J'ai fait deux passes, la première pour compter les pages (au cours desquelles N était défini sur zéro) et la seconde pour les générer, en utilisant le N obtenu lors du premier passage.

Parfois, le premier passage calcule N, puis le second passe génère un nombre de pages différent (car à présent, le N différent de zéro modifierait ce que le rapport faisait). J'ai essayé de faire des passes de manière itérative jusqu'à ce que le N se calme. Ensuite, j’ai réalisé que c’était désespéré parce que si cela ne s’installait pas?

Ceci conduit alors à la question "Puis-je au moins détecter et avertir l'utilisateur si l'itération ne va jamais se régler sur une valeur stable pour le nombre de pages que leur rapport produit?" Heureusement, à ce moment-là, je m'intéressais à lire des informations sur Turing, Godel, la calculabilité, etc. et établissais le lien.

Des années plus tard, j’ai remarqué que MS Access imprime parfois "Page 6 sur 5", ce qui est une chose vraiment merveilleuse.

Exemple 2: compilateurs C ++

Le processus de compilation implique le développement de modèles. Les définitions de modèle peuvent être sélectionnées parmi plusieurs spécialisations (suffisamment bonnes pour servir de "cond") et peuvent également être récursives. Il s’agit donc d’un méta-système complet (purement fonctionnel) de Turing, dans lequel les définitions de modèle sont le langage, les types sont les valeurs et le compilateur est en réalité un interprète. C'était un accident.

Par conséquent, il n’est pas possible d’examiner un programme C ++ donné et de dire si le compilateur pourrait en principe se terminer par une compilation réussie du programme.

Les fournisseurs de compilateurs contournent ce problème en limitant la profondeur de pile du modèle récursif. Vous pouvez régler la profondeur en g ++.

Answer 5

Il y a bien des lunes, j'aidais un consultant de notre société qui mettait en place un système ferroviaire très complexe pour déplacer des paniers de pièces métalliques dans un haut fourneau à 1 500 degrés. La piste elle-même était un "mini-terrain de jeu" assez complexe dans l'atelier qui se croisait à quelques endroits. Plusieurs palettes motorisées transportaient des paniers de pièces selon un horaire. Il était très important que les portes du four restent ouvertes le moins longtemps possible.

Étant donné que l’usine était en pleine production, le consultant n’était pas en mesure d’exécuter son logiciel en temps réel pour tester ses algorithmes de planification. Au lieu de cela, il a écrit un joli simulateur graphique. Tandis que nous observions les palettes virtuelles se déplacer sur sa présentation de piste à l'écran, j'ai demandé: "Comment saurez-vous si vous avez des problèmes de planification?"

Sa réponse rapide, "Facile - la simulation ne s’arrêtera jamais."

Answer 6

Une analyse sophistiquée du code statique peut rencontrer le même problème.

Par exemple, si une machine virtuelle Java peut prouver qu'un morceau de code ne pourra jamais accéder à un index de tableau en dehors des limites, il peut omettre cette vérification et son exécution plus rapidement. Pour certains codes, c'est possible. plus il devient complexe, plus le problème s’arrête.

Answer 7

Cela pose toujours un problème pour les shaders dans les applications GPU. Si un shader a une boucle infinie (ou un calcul très long), le pilote (après un certain délai) doit-il l'arrêter, tuer le fragment ou le laisser simplement s'exécuter? Pour les jeux et autres contenus commerciaux, le premier est probablement ce que vous voulez, mais pour l'informatique scientifique / GPU, le dernier est ce que vous voulez. Pire, certaines versions de Windows supposent que le pilote graphique, qui ne répond plus, le tue, ce qui limite artificiellement la puissance de calcul lors des calculs sur le GPU.

Il n'y a pas d'API permettant à une application de contrôler le comportement du pilote ou de définir un délai d'expiration, et il n'a aucun moyen de dire si votre shader va finir ou non.

Je ne sais pas si cette situation s'est améliorée récemment, mais j'aimerais savoir.

Answer 8

Une autre version courante de ceci est "nous devons éliminer toute impasse dans notre code multithread". Une demande parfaitement raisonnable du point de vue de la gestion, mais pour éviter les blocages en général, vous devez analyser chaque état de verrouillage possible dans lequel le logiciel peut entrer, ce qui n’est pas une surprise si l’équivalent du problème en cours d’arrêt.

Il existe des moyens de "résoudre" partiellement " impasses dans un système complexe en imposant une autre couche par-dessus le verrouillage (comme un ordre d'acquisition défini), mais ces méthodes ne sont pas toujours applicables.

Pourquoi cela équivaut-il au problème d'arrêt:

Imaginez que vous avez deux verrous, A et B, et deux threads, X et Y. Si le thread X a le verrou A et veut le verrou B également, et que le thread Y a le verrou B et veut A aussi, alors vous avez une impasse .

Si X et Y ont tous les deux accès à A et à B, le seul moyen de vous assurer que vous ne tombez jamais dans le mauvais état consiste à déterminer tous les chemins possibles que chaque fil peut emprunter dans le code, ainsi que l'ordre. dans lequel ils peuvent acquérir et tenir des verrous dans tous ces cas. Ensuite, vous déterminez si les deux threads peuvent acquérir plusieurs verrous dans un ordre différent.

Mais, déterminer tous les chemins possibles que chaque thread peut emprunter à travers le code est (dans le cas général) équivalent au problème en cours d’arrêt.

Answer 9

Le système de test de Perl maintient un compteur de test. Soit vous mettez le nombre de tests que vous allez exécuter en haut du programme, soit vous déclarez que vous ne le suivrez pas. Cela vous évitera de quitter prématurément votre test, mais il y a d'autres gardes, donc ce n'est pas si important que ça.

De temps en temps, quelqu'un essaie d'écrire un programme pour compter le nombre de tests que vous avez effectués. Ceci est, bien sûr, vaincu par une simple boucle. Ils avancent quand même de toute façon, faisant de plus en plus d’astuces pour essayer de détecter les boucles, deviner le nombre de répétitions possibles et résoudre le problème persistant. Habituellement, ils déclarent que cela doit simplement être "assez bon".

Voici un exemple particulièrement élaboré.

Answer 10

Je travaillais jadis à un projet d’intégration dans le domaine ATM (Automated Teller Machines). Le client m'a demandé de générer un rapport de mon système pour les transactions envoyées par le commutateur de pays qui n'ont pas été reçues par mon système !!

Answer 11

J'ai trouvé un document de Berkeley: Looper: détection légère de boucles infinies à l'exécution http://www.eecs.berkeley.edu/~jburnim/pubs /BurnimJalbertStergiouSen-ASE09.pdf

LOOPER peut être utile car la plupart des boucles infinies sont des erreurs triviales. Cependant, ce document ne mentionne même pas le problème de l’arrêt!

Que disent-ils de leurs limites?

  

[LOOPER] ne peut généralement pas raisonner à propos des boucles où la non-résiliation   dépend des particularités de la mutation de tas dans chaque itération de boucle.   En effet, notre exécution symbolique est conservatrice dans   concrétiser des indicateurs, et notre raisonnement symbolique insuffisamment   puissant. Nous pensons associer nos techniques à l'analyse de forme.   et plus puissante génération invariante et prouver serait précieux   travaux futurs.

En d'autres termes, "le problème sera résolu dans la prochaine version".

Answer 12

Extrait de Présentation fonctionnelle de l'éditeur visuel (Eclipse) :

  

L’éditeur visuel Eclipse (VE) peut être   utilisé pour ouvrir tout fichier .java. Alors   analyse le code source Java à la recherche   pour les haricots visuels. ...

     

Certains outils d'édition visuelle ne permettent   fournir un modèle visuel de code   cet outil visuel particulier a lui-même   généré. Edition directe ultérieure   du code source peut empêcher la   outil visuel d'analyse du code et   construire un modèle.

     

Eclipse VE, cependant, ... peut être soit   utilisé pour éditer les interfaces graphiques à partir de zéro, ou   à partir de fichiers Java qui ont été   'codé en dur' ou construit dans un autre   outil visuel. Le fichier source peut   soit être mis à jour en utilisant le graphique   Visionneuse, arborescence JavaBeans ou Propriétés   afficher ou peut être modifié directement par   l'éditeur de source.

Peut-être que je devrais rester avec Matisse pour le moment.

Sans lien, voici quelqu'un demander le problème d’arrêt dans Eclipse.

Pour être juste, le domaine de VE est assez limité, et il ne sera probablement pas fou de choses délicates comme la réflexion. Reste que la prétention de créer une interface utilisateur graphique à partir de tout fichier java semble totalement interrompue.

Answer 13

"Comment pouvez-vous m'assurer que votre code est 100% exempt de bogues?"