Boucle infinie - Infinite loop

En programmation informatique , une boucle infinie (ou boucle sans fin ) est une séquence d'instructions qui, telle qu'elle est écrite, se poursuivra indéfiniment, à moins qu'une intervention extérieure ne se produise (« tirez le bouchon »). C'est peut-être intentionnel.

Aperçu

Cela diffère de :

• "un type de programme informatique qui exécute les mêmes instructions en continu jusqu'à ce qu'il soit arrêté ou interrompu."

Considérez le pseudo - code suivant :

how_many = 0
while is_there_more_data() do
    how_many = how_many + 1
end
display "the number of items counted = " how_many

Les mêmes instructions ont été exécutées en continu jusqu'à ce qu'elles soient arrêtées ou interrompues . . . par le FALSE retourné à un moment donné par la fonction is_there_more_data .

En revanche, la boucle suivante ne se terminera pas d'elle-même :

birds = 1
fish = 2
while birds + fish > 1 do
    birds = 3 - birds
    fish = 3 - fish
end

les oiseaux alterneront étant 1 ou 2, tandis que les poissons alterneront étant 2 ou 1. La boucle ne s'arrêtera pas à moins qu'une intervention extérieure ne se produise (« tirez le bouchon »).

Des détails

Une boucle infinie est une séquence d'instructions dans un programme informatique qui boucle sans fin, soit parce que la boucle n'a pas de condition de fin, en a une qui ne peut jamais être remplie, soit parce que la boucle recommence. Dans les anciens systèmes d'exploitation avec multitâche coopératif , les boucles infinies faisaient normalement que l'ensemble du système ne répondait plus. Avec le modèle multitâche préemptif désormais répandu, les boucles infinies obligent généralement le programme à consommer tout le temps processeur disponible, mais peuvent généralement être interrompues par l'utilisateur. Les boucles d' attente occupées sont aussi parfois appelées "boucles infinies". Les boucles infinies sont une cause possible du « gel » d' un ordinateur ; d'autres incluent le thrashing , le blocage et les violations d'accès .

Bouclage intentionnel ou non intentionnel

Le bouclage consiste à répéter un ensemble d'instructions jusqu'à ce qu'une condition spécifique soit remplie. Une boucle infinie se produit lorsque la condition ne sera jamais remplie, en raison d'une caractéristique inhérente à la boucle.

Bouclage intentionnel

Il y a quelques situations où ce comportement est souhaité. Par exemple, les jeux sur les consoles de jeux à cartouche n'ont généralement pas de condition de sortie dans leur boucle principale, car il n'y a pas de système d'exploitation vers lequel le programme peut quitter ; la boucle s'exécute jusqu'à ce que la console soit éteinte.

Les ordinateurs interactifs modernes nécessitent que l'ordinateur surveille en permanence les entrées de l'utilisateur ou l'activité de l'appareil. Ainsi, à un certain niveau fondamental, il existe une boucle de traitement inactive infinie qui doit se poursuivre jusqu'à ce que l'appareil soit éteint ou réinitialisé. Dans l' ordinateur de guidage Apollo , par exemple, cette boucle externe était contenue dans le programme Exec, et si l'ordinateur n'avait absolument aucun autre travail à faire, il exécuterait en boucle un travail factice qui éteindrait simplement le voyant "activité de l'ordinateur".

Les ordinateurs modernes n'arrêtent généralement pas les horloges de pilotage du processeur ou de la carte mère lorsqu'ils se bloquent. Au lieu de cela, ils reviennent à une condition d'erreur affichant des messages à l'opérateur et entrent dans une boucle infinie en attendant que l'utilisateur réponde à une invite pour continuer ou pour réinitialiser l'appareil.

Multi-threading

Dans les programmes multi-threads, certains threads peuvent s'exécuter à l'intérieur de boucles infinies sans que le programme entier soit bloqué dans une boucle infinie. Si le thread principal se termine, tous les threads du processus sont arrêtés de force, ainsi toute exécution se termine et le processus/programme se termine. Les threads à l'intérieur des boucles infinies peuvent effectuer des tâches de « maintenance » ou ils peuvent être dans un état bloqué en attente d'une entrée (du socket/de la file d'attente) et reprendre l'exécution à chaque fois qu'une entrée est reçue.

Bouclage involontaire

Le plus souvent, le terme est utilisé pour les situations où ce n'est pas le résultat escompté ; c'est-à-dire lorsqu'il s'agit d'un bogue . De telles erreurs sont plus courantes chez les programmeurs novices, mais peuvent également être commises par des programmeurs expérimentés, car leurs causes peuvent être assez subtiles.

Une cause courante, par exemple, est que le programmeur a l'intention d'itérer sur une séquence de nœuds dans une structure de données telle qu'une liste chaînée ou un arbre , en exécutant le code de boucle une fois pour chaque nœud. Des liens mal formés peuvent créer une boucle de référence dans la structure de données, où un nœud se lie à un autre qui se produit plus tôt dans la séquence. Cela transforme une partie de la structure de données en un anneau , provoquant une boucle indéfinie du code naïf.

Alors que la plupart des boucles infinies peuvent être trouvées par une inspection minutieuse du code, il n'y a pas de méthode générale pour déterminer si un programme donné s'arrêtera un jour ou s'exécutera indéfiniment ; c'est l' indécidabilité du problème de l' arrêt .

Interruption

Tant que le système est réactif, les boucles infinies peuvent souvent être interrompues en envoyant un signal au processus (comme SIGINT sous Unix), ou une interruption au processeur, provoquant l'abandon du processus en cours. Cela peut être fait dans un gestionnaire de tâches , dans un terminal avec la commande Control-C , ou en utilisant la commande kill ou l' appel système . Cependant, cela ne fonctionne pas toujours, car le processus peut ne pas répondre aux signaux ou le processeur peut être dans un état ininterrompu, comme dans le bogue de coma Cyrix (causé par le chevauchement d'instructions ininterrompues dans un pipeline d'instructions ). Dans certains cas, d'autres signaux tels que SIGKILL peuvent fonctionner, car ils ne nécessitent pas que le processus soit réactif, tandis que dans d'autres cas, la boucle ne peut pas être terminée avant l'arrêt du système.

Support linguistique

Des boucles infinies peuvent être mises en œuvre à l'aide de diverses constructions de flux de contrôle . Le plus souvent, dans la programmation non structurée, il s'agit de revenir en arrière ( goto ), tandis que dans la programmation structurée, il s'agit d'une boucle indéfinie (boucle while) définie pour ne jamais se terminer, soit en omettant la condition, soit en la définissant explicitement sur true, comme while (true) ....

Certains langages ont des constructions spéciales pour les boucles infinies, généralement en omettant la condition d'une boucle indéfinie. Les exemples incluent Ada ( loop ... end loop), Fortran ( DO ... END DO), Go ( for { ... }), Ruby ( loop do ... end) et Rust ( loop { ... }).

Exemples de boucles infinies intentionnelles

Un exemple simple (en C ) :

#include <stdio.h>

int main()
{
  for (;;) // or equivalently, while (1)
    ;  
  return 0;
}

La forme for (;;)d'une boucle infinie est traditionnelle, apparaissant dans la référence standard The C Programming Language , et est souvent prononcée "pour toujours".

Il s'agit d'une boucle qui imprimera "Infinite Loop" sans s'arrêter.

Un exemple similaire dans le BASIC des années 1980 :

10 PRINT "INFINITE LOOP"
20 GOTO 10

Un exemple similaire dans les fichiers batch DOS :

:A
echo Infinite Loop
goto :A

Ici, la boucle est assez évidente, car la dernière ligne renvoie inconditionnellement l'exécution à la première.

Un exemple en Java

while (true) {
    System.out.println("Infinite Loop");
}

Un exemple dans Bourne Again Shell

for ((;;)); do
	echo "Infinite Loop"
done

Un exemple dans Rust

loop {
    println!("Infinite loop");
}

Exemples de boucles infinies involontaires

Erreurs mathématiques

Voici un exemple de boucle infinie en Visual Basic :

dim x as integer
do while x < 5
  x = 1
  x = x + 1
loop

Cela crée une situation où xne sera jamais supérieur à 5, car au début de la boucle, le code xreçoit la valeur 1, ainsi, la boucle se terminera toujours par 2 et la boucle ne se brisera jamais. Cela pourrait être corrigé en déplaçant l' x = 1instruction en dehors de la boucle. Essentiellement, cette boucle infinie demande à un ordinateur de continuer à ajouter 1 à 1 jusqu'à ce que 5 soit atteint. Puisque 1+1 est toujours égal à 2, cela n'arrivera jamais.

Dans certains langages, la confusion du programmeur sur les symboles mathématiques peut conduire à une boucle infinie involontaire. Par exemple, voici un extrait en C :

#include <stdio.h>

int main(void)
{
   int a = 0;
   while (a < 10) {
      printf("%d\n", a);
      if (a = 5)
         printf("a equals 5!\n");
      a++;
   }
   return 0;
}

La sortie attendue est les nombres 0 à 9, avec un intercalé "a égal 5!" entre 5 et 6. Cependant, dans la ligne " if (a = 5)" ci-dessus, le programmeur a confondu l'opérateur = (affectation) avec l'opérateur == (test d'égalité). Au lieu de cela, cela affectera la valeur de 5 aà ce stade du programme. Ainsi, ane pourra jamais avancer jusqu'à 10, et cette boucle ne peut pas se terminer.

Erreurs d'arrondi

Un comportement inattendu lors de l'évaluation de la condition de fin peut également être à l'origine de ce problème. Voici un exemple en C :

float x = 0.1;
while (x != 1.1) {
  printf("x = %22.20f\n", x);
  x += 0.1;
}

Sur certains systèmes, cette boucle s'exécutera dix fois comme prévu, mais sur d'autres systèmes, elle ne se terminera jamais. Le problème est que la condition de fin de boucle (x ! = 1.1) teste l'égalité exacte de deux valeurs à virgule flottante , et la façon dont les valeurs à virgule flottante sont représentées dans de nombreux ordinateurs fera échouer ce test, car elles ne peuvent pas représenter exactement la valeur 0,1, introduisant ainsi des erreurs d'arrondi sur chaque incrément (cf. encadré).

La même chose peut arriver en Python :

x = 0.1
while x != 1:
    print(x)
    x += 0.1

En raison de la probabilité que les tests d'égalité ou de non-égalité échouent de manière inattendue, il est plus sûr d'utiliser des tests supérieurs ou inférieurs à lorsqu'il s'agit de valeurs à virgule flottante. Par exemple, au lieu de tester si xest égal à 1.1, on pourrait tester si (x <= 1.0) , ou (x < 1.1) , dont l'un ou l'autre serait certain de se terminer après un nombre fini d'itérations. Une autre façon de corriger cet exemple particulier serait d'utiliser un entier comme index de boucle , en comptant le nombre d'itérations qui ont été effectuées.

Un problème similaire se pose fréquemment en analyse numérique : pour calculer un certain résultat, une itération est destinée à être effectuée jusqu'à ce que l'erreur soit inférieure à une tolérance choisie. Cependant, en raison d'erreurs d'arrondi au cours de l'itération, la tolérance spécifiée ne peut jamais être atteinte, ce qui entraîne une boucle infinie.

Boucles multi-parties

Une boucle infinie peut être causée par l'interaction de plusieurs entités. Considérez un serveur qui répond toujours avec un message d'erreur s'il ne comprend pas la requête. Même s'il n'y a aucune possibilité pour une boucle infinie au sein du serveur lui-même, un système comprenant deux d'entre eux ( A et B ) peut boucler sans fin : si A reçoit un message de type inconnu de B , alors A répond avec un message d'erreur à B ; si B ne comprend pas le message d'erreur, il répond à A avec son propre message d'erreur ; si A ne comprend pas le message d'erreur de B , il envoie encore un autre message d'erreur, et ainsi de suite.

Un exemple courant d'une telle situation est une boucle de courrier électronique . Un exemple de boucle de courrier électronique est le cas où quelqu'un reçoit du courrier à partir d'une boîte de réception sans réponse, mais que sa réponse automatique est activée. Ils répondront à la boîte de réception de non-réponse, déclenchant la réponse « ceci est une boîte de réception de non-réponse ». Celui-ci sera envoyé à l'utilisateur, qui enverra ensuite une réponse automatique à la boîte de réception de non-réponse, et ainsi de suite.

Boucles pseudo-infinies

Une boucle pseudo-infinie est une boucle qui semble infinie mais qui n'est en réalité qu'une très longue boucle.

De très grands nombres

Un exemple en bash :

for x in $(seq 1000000000); do
#loop code
done

Condition de résiliation impossible

Un exemple de boucle en C :

unsigned int i;
for (i = 1; i != 0; i++) {
  /* loop code */
}

Il semble que cela durera indéfiniment, mais en fait, la valeur de ifinira par atteindre la valeur maximale stockable dans un unsigned intet l'ajout de 1 à ce nombre reviendra à 0, brisant la boucle. La limite réelle de idépend des détails du système et du compilateur utilisés. Avec l'arithmétique de précision arbitraire , cette boucle se poursuivrait jusqu'à ce que la mémoire de l'ordinateur ne puisse plus contenir i. S'il is'agissait d'un entier signé plutôt que d'un entier non signé, le débordement serait indéfini. Dans ce cas, le compilateur pourrait optimiser le code dans une boucle infinie.

Récursivité infinie

La récursivité infinie est un cas particulier de boucle infinie causée par la récursivité .

L'exemple suivant dans VBA renvoie une erreur de débordement de pile :

Sub Test1()
    Call Test1
End Sub

Déclaration de rupture

Une " while (true)" boucle semble infinie à première vue, mais il peut y avoir un moyen d'échapper à la boucle via une instruction break ou return . Exemple en PHP :

while (true) {
    if ($foo->bar()) {
        return;
    }
}

boucle d'Alderson

La boucle d'Alderson est un terme d' argot ou de jargon rare pour une boucle infinie où il existe une condition de sortie disponible, mais inaccessible dans l'implémentation actuelle du code, généralement en raison d'une erreur de programmeur. Celles-ci sont les plus courantes et les plus visibles lors du débogage du code de l' interface utilisateur .

Un exemple de pseudocode de type C d'une boucle d'Alderson, où le programme est censé additionner les nombres donnés par l'utilisateur jusqu'à ce que zéro soit donné, mais où le programmeur a utilisé le mauvais opérateur :

int sum = 0;
int i;
while (true) {
   printf("Input a number to add to the sum or 0 to quit");
   i = getUserInput();
   if (i * 0) { // if i times 0 is true, add i to the sum. Note: ZERO means FALSE, Non-Zero means TRUE. "i * 0" is ZERO (FALSE)!
      sum += i; // sum never changes because (i * 0) is 0 for any i; it would change if we had != in the condition instead of *
   }
   if (sum > 100) {
      break;    // terminate the loop; exit condition exists but is never reached because sum is never added to
   }
}

Le terme aurait reçu son nom d'un programmeur (nom de famille Alderson) qui, en 1996, avait codé une boîte de dialogue modale dans Microsoft Access sans bouton OK ou Annuler, désactivant ainsi l'ensemble du programme chaque fois que la boîte s'affichait.

Voir également

• Détection de cycle
• Impasse
• Divergence (informatique)
• Bombe à fourche (une boucle infinie est l'un des deux composants clés)
• Aller à
• Régression infinie
• Récursivité (informatique)

Les références

Liens externes

• Faites une boucle infinie en plusieurs langues, sur Programming-idioms.org .