Flux de contrôle - Control flow

En informatique , le flux de contrôle (ou flux de contrôle ) est l'ordre dans lequel des instructions individuelles , des instructions ou des appels de fonction d'un programme impératif sont exécutés ou évalués. L'accent mis sur le flux de contrôle explicite distingue un langage de programmation impératif d' un langage de programmation déclaratif .

Au sein d'un langage de programmation impératif , une instruction de flux de contrôle est une instruction qui entraîne un choix parmi deux ou plusieurs chemins à suivre. Pour les langages fonctionnels non stricts , des fonctions et des constructions de langage existent pour obtenir le même résultat, mais elles ne sont généralement pas appelées instructions de flux de contrôle.

Un ensemble d'énoncés est à son tour généralement structuré comme un bloc , qui en plus de regrouper, définit également une portée lexicale .

Les interruptions et les signaux sont des mécanismes de bas niveau qui peuvent modifier le flux de contrôle d'une manière similaire à un sous - programme , mais se produisent généralement en réponse à un stimulus ou à un événement externe (pouvant se produire de manière asynchrone ), plutôt que l'exécution d'un en ligne instruction de flux de contrôle.

Au niveau du langage machine ou du langage assembleur , les instructions de flux de contrôle fonctionnent généralement en modifiant le compteur du programme . Pour certaines unités centrales (CPU), les seules instructions de flux de contrôle disponibles sont des instructions de branchement conditionnelles ou inconditionnelles , également appelées sauts.

Catégories

Un organigramme montrant le flux de contrôle.

Les types d'instructions de flux de contrôle pris en charge par différents langages varient, mais peuvent être classés en fonction de leur effet :

  • Continuation à une autre instruction ( branchement ou saut inconditionnel )
  • Exécuter un ensemble d'instructions uniquement si une condition est remplie (choix - c'est-à-dire branche conditionnelle )
  • Exécuter un ensemble d'instructions zéro ou plusieurs fois, jusqu'à ce qu'une condition soit remplie (c'est-à-dire boucle - identique à la branche conditionnelle )
  • Exécution d'un ensemble d'instructions distantes, après quoi le flux de contrôle retourne généralement ( subroutines , coroutines et continuations )
  • Arrêt du programme, empêchant toute exécution ultérieure (arrêt inconditionnel)

Primitives

Étiquettes

Une étiquette est un nom ou un numéro explicite attribué à une position fixe dans le code source , et qui peut être référencé par des instructions de flux de contrôle apparaissant ailleurs dans le code source. Une étiquette marque une position dans le code source et n'a aucun autre effet.

Les numéros de ligne sont une alternative à une étiquette nommée utilisée dans certaines langues (comme BASIC ). Ce sont des nombres entiers placés au début de chaque ligne de texte dans le code source. Les langages qui les utilisent imposent souvent la contrainte que les numéros de ligne doivent augmenter en valeur dans chaque ligne suivante, mais peuvent ne pas exiger qu'ils soient consécutifs. Par exemple, en BASIC :

10 LET X = 3
20 PRINT X

Dans d'autres langages tels que C et Ada , une étiquette est un identifiant , apparaissant généralement au début d'une ligne et immédiatement suivi de deux points. Par exemple, en C :

Success: printf("The operation was successful.\n");

Le langage ALGOL 60 autorisait à la fois des nombres entiers et des identificateurs comme étiquettes (tous deux liés par des deux-points à l'instruction suivante), mais peu ou pas d'autres variantes d' ALGOL autorisaient des nombres entiers. Les premiers compilateurs Fortran n'autorisaient que les nombres entiers comme étiquettes. Depuis le Fortran-90, les étiquettes alphanumériques sont également autorisées.

Aller à

L' instruction goto (une combinaison des mots anglais go et to , et prononcée en conséquence) est la forme la plus basique de transfert inconditionnel de contrôle.

Bien que le mot - clé puisse être en majuscule ou en minuscule selon la langue, il s'écrit généralement comme suit :

   goto label

L'effet d'une instruction goto est de faire en sorte que l'instruction suivante soit exécutée pour être l'instruction apparaissant à (ou immédiatement après) l'étiquette indiquée.

Les déclarations Goto ont été considérées comme nuisibles par de nombreux informaticiens, notamment Dijkstra .

Sous-programmes

La terminologie des sous-programmes varie ; elles peuvent aussi être appelées routines, procédures, fonctions (surtout si elles renvoient des résultats) ou méthodes (surtout si elles appartiennent à des classes ou à des classes de type ).

Dans les années 1950, les mémoires des ordinateurs étaient très petites par rapport aux normes actuelles, de sorte que les sous-programmes étaient principalement utilisés pour réduire la taille du programme. Un morceau de code a été écrit une fois, puis utilisé plusieurs fois à partir de divers autres endroits d'un programme.

Aujourd'hui, les sous-routines sont plus souvent utilisées pour aider à rendre un programme plus structuré, par exemple, en isolant un algorithme ou en masquant une méthode d'accès aux données. Si de nombreux programmeurs travaillent sur un programme, les sous-routines sont un type de modularité qui peut aider à diviser le travail.

Séquence

Dans la programmation structurée, le séquençage ordonné de commandes successives est considéré comme l'une des structures de contrôle de base, qui est utilisée comme bloc de construction pour les programmes aux côtés de l'itération, de la récursivité et du choix.

Flux de contrôle structuré minimal

En mai 1966, Böhm et Jacopini ont publié un article dans Communications of the ACM qui montrait que tout programme avec goto s pouvait être transformé en une forme goto-free impliquant uniquement des choix (IF THEN ELSE) et des boucles (WHILE condition DO xxx), éventuellement avec du code dupliqué et/ou l'ajout de variables booléennes (vrais/faux drapeaux). Des auteurs ultérieurs ont montré que le choix peut être remplacé par des boucles (et encore plus de variables booléennes).

Qu'un tel minimalisme soit possible ne signifie pas qu'il soit nécessairement souhaitable ; après tout, les ordinateurs n'ont théoriquement besoin que d' une seule instruction machine (soustrayez un nombre d'un autre et branchez si le résultat est négatif), mais les ordinateurs pratiques ont des dizaines voire des centaines d'instructions machine.

L'article de Böhm et Jacopini montrait que tous les programmes pouvaient être goto-free. D'autres recherches ont montré que les structures de contrôle avec une entrée et une sortie étaient beaucoup plus faciles à comprendre que toute autre forme, principalement parce qu'elles pouvaient être utilisées n'importe où comme instruction sans perturber le flux de contrôle. En d'autres termes, ils étaient composables . (Les développements ultérieurs, tels que les langages de programmation non stricts - et plus récemment, les transactions logicielles composables - ont poursuivi cette stratégie, rendant les composants des programmes encore plus librement composables.)

Certains universitaires ont adopté une approche puriste du résultat de Böhm-Jacopini et ont fait valoir que même les instructions comme breaket returnau milieu des boucles sont une mauvaise pratique car elles ne sont pas nécessaires dans la preuve de Böhm-Jacopini, et ils ont donc préconisé que toutes les boucles devraient avoir un seul point de sortie. Cette approche puriste est incarnée dans le langage Pascal (conçu en 1968-1969), qui jusqu'au milieu des années 1990 était l'outil privilégié pour l'enseignement de la programmation d'introduction dans les universités. L'application directe du théorème de Böhm-Jacopini peut entraîner l'introduction de variables locales supplémentaires dans le graphique structuré, et peut également entraîner une duplication de code . Pascal est affecté par ces deux problèmes et selon des études empiriques citées par Eric S. Roberts , les étudiants programmeurs ont eu des difficultés à formuler des solutions correctes en Pascal pour plusieurs problèmes simples, notamment l'écriture d'une fonction pour rechercher un élément dans un tableau. Une étude de 1980 d'Henry Shapiro citée par Roberts a révélé qu'en utilisant uniquement les structures de contrôle fournies par Pascal, la solution correcte n'était donnée que par 20 % des sujets, alors qu'aucun sujet n'écrivait un code incorrect pour ce problème s'il était autorisé à écrire un retour du milieu d'une boucle.

Les structures de contrôle en pratique

La plupart des langages de programmation avec des structures de contrôle ont un mot-clé initial qui indique le type de structure de contrôle impliqué. Les langages se divisent ensuite pour savoir si les structures de contrôle ont ou non un mot-clé final.

  • Pas de mot-clé final : ALGOL 60 , C , C++ , Haskell , Java , Pascal , Perl , PHP , PL/I , Python , PowerShell . De tels langages ont besoin d'un moyen de regrouper les déclarations :
    • ALGOL 60 et Pascal : begin...end
    • C, C++, Java, Perl, PHP, et PowerShell : accolades { ...}
    • PL/I : DO...END
    • Python : utilise le niveau de retrait (voir règle de hors-jeu )
    • Haskell : le niveau de retrait ou les accolades peuvent être utilisés, et ils peuvent être mélangés librement
    • Lua : utilise do...end
  • Mot-clé final : Ada , ALGOL 68 , Modula-2 , Fortran 77 , Mythryl , Visual Basic . Les formes du mot-clé final varient :
    • Ada : le mot-clé final est end+ espace + mot-clé initial, par exemple, if... end if, loop...end loop
    • ALGOL 68, Mythryl : mot-clé initial épelé à l'envers par exemple, if... fi, case...esac
    • Fortran 77 : le mot-clé final est END+ le mot-clé initial, par exemple, IF... ENDIF, DO...ENDDO
    • Modula-2 : même mot-clé final ENDpour tout
    • Visual Basic : chaque structure de contrôle a son propre mot-clé. If... End If; For... Next; Do... Loop; While...Wend

Choix

Instructions Si-alors-(sinon)

Les expressions conditionnelles et les constructions conditionnelles sont des caractéristiques d'un langage de programmation qui effectuent différents calculs ou actions selon qu'une condition booléenne spécifiée par le programmeur est vraie ou fausse.

  • IF..GOTO. Un formulaire trouvé dans des langages non structurés, imitant une instruction de code machine typique, sauterait à (GOTO) une étiquette ou un numéro de ligne lorsque la condition était remplie.
  • IF..THEN..(ENDIF). Plutôt que d'être limité à un saut, n'importe quelle instruction simple, ou bloc imbriqué, pourrait suivre le mot clé THEN. Il s'agit d'une forme structurée.
  • IF..THEN..ELSE..(ENDIF). Comme ci-dessus, mais avec une seconde action à effectuer si la condition est fausse. C'est l'une des formes les plus courantes, avec de nombreuses variantes. Certains nécessitent un terminal ENDIF, d'autres non. Le C et les langages apparentés ne nécessitent pas de mot-clé de terminal, ni de 'then', mais nécessitent des parenthèses autour de la condition.
  • Les instructions conditionnelles peuvent être et sont souvent imbriquées dans d'autres instructions conditionnelles. Certains langages permettent ELSEet IFd'être combinés dans ELSEIF, évitant ainsi d'avoir une série d' ENDIFinstructions finales ou d'autres instructions finales à la fin d'une instruction composée.
Pascale : Ada : C : Script shell : Python : Lisp :
if a > 0 then
  writeln("yes")
else
  writeln("no");
if a > 0 then
      Put_Line("yes");
else
      Put_Line("no");
end if;
if (a > 0) { 
    printf("yes");
}
else {
    printf("no");
}
if [ $a -gt 0 ]; then
      echo "yes"
else
      echo "no"
fi
if a > 0: 
    print("yes")
else:
    print("no")
(princ
  (if (plusp a)
      "yes"
      "no"))

Les variantes moins courantes comprennent :

  • Certains langages, tels que Fortran , ont un if à trois voies ou arithmétique , testant si une valeur numérique est positive, négative ou nulle.
  • Certains langages ont une forme fonctionnelle d' ifinstruction, par exemple Lisp's cond .
  • Certains langages ont une forme d' opérateur d' ifinstruction, comme l' opérateur ternaire de C .
  • Perl complète un style C ifavec whenet unless.
  • Smalltalk utilise ifTrueet envoie des ifFalsemessages pour implémenter des conditions, plutôt que toute construction de langage fondamentale.

Instructions case et switch

Les instructions Switch (ou les instructions case , ou les branches multivoies ) comparent une valeur donnée avec des constantes spécifiées et prennent des mesures en fonction de la première constante à correspondre. Il existe généralement une disposition pour une action par défaut ("autre", "autrement") à prendre si aucune correspondance ne réussit. Les instructions Switch peuvent permettre des optimisations du compilateur, telles que les tables de recherche . Dans les langages dynamiques , les cas peuvent ne pas être limités à des expressions constantes et peuvent s'étendre à la correspondance de motifs , comme dans l' exemple de script shell à droite, où le *)implémente le cas par défaut en tant que glob correspondant à n'importe quelle chaîne. La logique de cas peut également être mis en oeuvre sous une forme fonctionnelle, comme dans SQL de decodedéclaration.

Pascale : Ada : C : Script shell : Lisp :
case someChar of
  'a': actionOnA;
  'x': actionOnX;
  'y','z':actionOnYandZ;
  else actionOnNoMatch;
end;
case someChar is
  when 'a' => actionOnA;
  when 'x' => actionOnX;
  when 'y' | 'z' => actionOnYandZ;
  when others => actionOnNoMatch;
end;
switch (someChar) {
  case 'a': actionOnA; break;
  case 'x': actionOnX; break;
  case 'y':
  case 'z': actionOnYandZ; break;
  default: actionOnNoMatch;
}
case $someChar in 
   a)    actionOnA ;;
   x)    actionOnX ;;
   [yz]) actionOnYandZ ;;
   *)    actionOnNoMatch  ;;
esac
(case some-char
  ((#\a)     action-on-a)
  ((#\x)     action-on-x)
  ((#\y #\z) action-on-y-and-z)
  (else      action-on-no-match))

Boucles

Une boucle est une séquence d'instructions qui est spécifiée une fois mais qui peut être exécutée plusieurs fois de suite. Le code "à l'intérieur" de la boucle (le corps de la boucle, illustré ci-dessous par xxx ) est obéi un nombre spécifié de fois, ou une fois pour chacun d'une collection d'éléments, ou jusqu'à ce qu'une condition soit remplie, ou indéfiniment .

Dans les langages de programmation fonctionnels , tels que Haskell et Scheme , les boucles peuvent être exprimées en utilisant la récursivité ou l' itération à virgule fixe plutôt que des constructions de boucle explicites. La récursivité de queue est un cas particulier de récursivité qui peut être facilement transformée en itération.

Boucles contrôlées par comptage

La plupart des langages de programmation ont des constructions pour répéter une boucle un certain nombre de fois. Dans la plupart des cas, le comptage peut aller vers le bas au lieu d'augmenter et des tailles de pas autres que 1 peuvent être utilisées.

   FOR I = 1 TO N           | for I := 1 to N do begin
       xxx                  |     xxx
   NEXT I                   | end;
------------------------------------------------------------
   DO I = 1,N               | for ( I=1; I<=N; ++I ) {
       xxx                  |     xxx
   END DO                   | }

Dans ces exemples, si N < 1, le corps de la boucle peut s'exécuter une fois (avec I ayant la valeur 1) ou pas du tout, selon le langage de programmation.

Dans de nombreux langages de programmation, seuls les entiers peuvent être utilisés de manière fiable dans une boucle contrôlée par comptage. Les nombres à virgule flottante sont représentés de manière imprécise en raison de contraintes matérielles, donc une boucle telle que

   for X := 0.1 step 0.1 to 1.0 do

peut être répété 9 ou 10 fois, selon les erreurs d'arrondi et/ou le matériel et/ou la version du compilateur. De plus, si l'incrément de X se produit par addition répétée, les erreurs d'arrondi accumulées peuvent signifier que la valeur de X à chaque itération peut différer assez significativement de la séquence attendue 0,1, 0,2, 0,3, ..., 1,0.

Boucles à conditions contrôlées

La plupart des langages de programmation ont des constructions pour répéter une boucle jusqu'à ce que certaines conditions changent. Certaines variantes testent la condition au début de la boucle ; d'autres le testent à la fin. Si le test est au début, le corps peut être complètement ignoré; si c'est à la fin, le corps est toujours exécuté au moins une fois.

   DO WHILE (test)          | repeat 
       xxx                  |     xxx 
   LOOP                     | until test;
----------------------------------------------
   while (test) {           | do
       xxx                  |     xxx
   }                        | while (test);

Une rupture de contrôle est une méthode de détection de changement de valeur utilisée dans les boucles ordinaires pour déclencher le traitement de groupes de valeurs. Les valeurs sont surveillées dans la boucle et un changement détourne le flux du programme vers la gestion de l'événement de groupe qui leur est associé.

   DO UNTIL (End-of-File)
      IF new-zipcode <> current-zipcode
         display_tally(current-zipcode, zipcount)
         
         current-zipcode = new-zipcode
         zipcount = 0
      ENDIF
      
      zipcount++
   LOOP

Boucles contrôlées par la collecte

Plusieurs langages de programmation (par exemple, Ada , D , C++11 , Smalltalk , PHP , Perl , Object Pascal , Java , C# , MATLAB , Visual Basic , Ruby , Python , JavaScript , Fortran 95 et versions ultérieures) ont des constructions spéciales qui permettent implicitement en parcourant tous les éléments d'un tableau ou tous les membres d'un ensemble ou d'une collection.

   someCollection do: [:eachElement |xxx].
   for Item in Collection do begin xxx end;

   foreach (item; myCollection) { xxx }

   foreach someArray { xxx }

   foreach ($someArray as $k => $v) { xxx }

   Collection<String> coll; for (String s : coll) {}

   foreach (string s in myStringCollection) { xxx }

   someCollection | ForEach-Object { $_ }
   forall ( index = first:last:step... )

Scala a for-expressions , qui généralisent les boucles contrôlées par la collection, et prennent également en charge d'autres utilisations, telles que la programmation asynchrone . Haskell a des expressions et des compréhensions do, qui ensemble fournissent une fonction similaire aux expressions for de Scala.

Itération générale

Itération générale construit tels que C de forla déclaration et Common Lisp de doformulaire peut être utilisé pour exprimer l' une des sortes au- dessus des boucles, et d' autres, comme une boucle sur un certain nombre de collections en parallèle. Lorsqu'une construction de bouclage plus spécifique peut être utilisée, elle est généralement préférée à la construction d'itération générale, car elle rend souvent le but de l'expression plus clair.

Boucles infinies

Les boucles infinies sont utilisées pour assurer qu'un segment de programme boucle pour toujours ou jusqu'à ce qu'une condition exceptionnelle se produise, telle qu'une erreur. Par exemple, un programme événementiel (tel qu'un serveur ) devrait boucler indéfiniment, gérer les événements au fur et à mesure qu'ils se produisent, ne s'arrêtant que lorsque le processus est terminé par un opérateur.

Des boucles infinies peuvent être implémentées à l'aide d'autres 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 { ... }) et Ruby ( loop do ... end).

Souvent, une boucle infinie est involontairement créée par une erreur de programmation dans une boucle contrôlée par condition, dans laquelle la condition de boucle utilise des variables qui ne changent jamais dans la boucle.

Continuation avec la prochaine itération

Parfois, dans le corps d'une boucle, il y a un désir de sauter le reste du corps de la boucle et de continuer avec l'itération suivante de la boucle. Certains langages fournissent une instruction telle que continue(la plupart des langages), skip, ou next(Perl et Ruby), qui le fera. L'effet est de terminer prématurément le corps de boucle le plus interne, puis de reprendre normalement à l'itération suivante. Si l'itération est la dernière de la boucle, l'effet est de terminer la boucle entière plus tôt.

Refaire l'itération actuelle

Certains langages, comme Perl et Ruby, ont une redoinstruction qui redémarre l'itération en cours depuis le début.

Redémarrer la boucle

Ruby a une retryinstruction qui redémarre toute la boucle à partir de l'itération initiale.

Sortie anticipée des boucles

Lors de l'utilisation d'une boucle contrôlée par comptage pour rechercher dans une table, il peut être souhaitable d'arrêter la recherche dès que l'élément requis est trouvé. Certains langages de programmation fournissent une instruction telle que break(la plupart des langages), Exit(Visual Basic) ou last(Perl), qui a pour effet de terminer immédiatement la boucle en cours et de transférer le contrôle à l'instruction immédiatement après cette boucle. Un autre terme pour les boucles à sortie anticipée est loop-and-a-half .

L'exemple suivant est réalisé dans Ada qui prend en charge à la fois la sortie anticipée des boucles et les boucles avec test au milieu . Les deux fonctionnalités sont très similaires et la comparaison des deux extraits de code montrera la différence : une sortie anticipée doit être combinée avec une instruction if tandis qu'une condition au milieu est une construction autonome.

with Ada.Text IO;
with Ada.Integer Text IO;

procedure Print_Squares is 
    X : Integer;
begin
    Read_Data : loop
        Ada.Integer Text IO.Get(X);
    exit Read_Data when X = 0;
        Ada.Text IO.Put (X * X);
        Ada.Text IO.New_Line;
    end loop Read_Data;
end Print_Squares;

Python prend en charge l'exécution conditionnelle de code selon qu'une boucle a été quittée tôt (avec une breakinstruction) ou non en utilisant une clause else avec la boucle. Par exemple,

for n in set_of_numbers:
    if isprime(n):
        print("Set contains a prime number")
        break
else:
    print("Set did not contain any prime numbers")

La elseclause de l'exemple ci-dessus est liée à l' forinstruction, et non à l' ifinstruction interne . Les boucles Python foret les whileboucles prennent en charge une telle clause else, qui n'est exécutée que si une sortie anticipée de la boucle ne s'est pas produite.

Certains langages prennent en charge la rupture des boucles imbriquées ; dans les cercles théoriques, on les appelle des pauses à plusieurs niveaux. Un exemple d'utilisation courante est la recherche d'un tableau multidimensionnel. Cela peut être fait soit via des pauses multiniveaux (sortie de N niveaux), comme dans bash et PHP, soit via des pauses étiquetées (sortir et continuer à une étiquette donnée), comme en Java et Perl. Les alternatives aux ruptures à plusieurs niveaux incluent les ruptures simples, ainsi qu'une variable d'état qui est testée pour casser un autre niveau ; les exceptions, qui sont détectées au niveau auquel elles sont ventilées ; placer les boucles imbriquées dans une fonction et utiliser return pour effectuer la terminaison de la boucle imbriquée entière ; ou en utilisant une étiquette et une instruction goto. C n'inclut pas de rupture à plusieurs niveaux, et l'alternative habituelle est d'utiliser un goto pour implémenter une rupture étiquetée. Python n'a pas de pause ou de continuation à plusieurs niveaux - cela a été proposé dans PEP 3136 et rejeté au motif que la complexité supplémentaire ne valait pas la rare utilisation légitime.

La notion de ruptures multi-niveaux présente un certain intérêt en informatique théorique , car elle donne lieu à ce qu'on appelle aujourd'hui la hiérarchie de Kosaraju . En 1973, S. Rao Kosaraju a affiné le théorème du programme structuré en prouvant qu'il est possible d'éviter d'ajouter des variables supplémentaires dans la programmation structurée, tant que des coupures à plusieurs niveaux et profondeur arbitraire sont autorisées dans les boucles. De plus, Kosaraju a prouvé qu'il existe une hiérarchie stricte de programmes : pour tout entier n , il existe un programme contenant une coupure multi-niveaux de profondeur n qui ne peut pas être réécrite comme un programme avec des coupures multi-niveaux de profondeur inférieure à n sans introduire variables.

On peut également returnsortir d'un sous-programme en exécutant les instructions en boucle, en sortant à la fois de la boucle imbriquée et du sous-programme. Il existe d'autres structures de contrôle proposées pour les pauses multiples, mais celles-ci sont généralement mises en œuvre en tant qu'exceptions.

Dans son manuel de 2004, David Watt utilise la notion de séquenceur de Tennent pour expliquer la similitude entre les pauses à plusieurs niveaux et les instructions de retour. Watt note qu'une classe de séquenceurs connus sous le nom de séquenceurs d'échappement , définis comme « un séquenceur qui termine l'exécution d'une commande ou d'une procédure contenant du texte », englobe à la fois les interruptions des boucles (y compris les interruptions à plusieurs niveaux) et les instructions de retour. Comme couramment mis en œuvre, cependant, les séquenceurs de retour peuvent également porter une valeur (de retour), alors que le séquenceur de rupture tel qu'il est mis en œuvre dans les langages contemporains ne le peut généralement pas.

Variantes et invariants de boucle

Les variantes de boucle et les invariants de boucle sont utilisés pour exprimer l'exactitude des boucles.

En termes pratiques, une variante de boucle est une expression entière qui a une valeur initiale non négative. La valeur du variant doit diminuer à chaque itération de la boucle mais ne doit jamais devenir négative lors de l'exécution correcte de la boucle. Les variantes de boucle sont utilisées pour garantir que les boucles se termineront.

Un invariant de boucle est une assertion qui doit être vraie avant la première itération de boucle et rester vraie après chaque itération. Cela implique que lorsqu'une boucle se termine correctement, la condition de sortie et l'invariant de boucle sont satisfaits. Les invariants de boucle sont utilisés pour surveiller les propriétés spécifiques d'une boucle au cours d'itérations successives.

Certains langages de programmation, tels que Eiffel, contiennent une prise en charge native des variantes et des invariants de boucle. Dans d'autres cas, la prise en charge est un module complémentaire, comme la spécification du langage de modélisation Java pour les instructions de boucle en Java .

Sous-langue de boucle

Certains dialectes Lisp fournissent un sous-langage étendu pour décrire les boucles. Un premier exemple peut être trouvé dans Conversional Lisp of Interlisp . Common Lisp fournit une macro Loop qui implémente un tel sous-langage.

Tableau de concordance du système de boucle

Langage de programmation conditionnel boucle sortie anticipée continuation de la boucle refaire réessayez installations d'exactitude
commencer milieu finir compter collection général infini une variante invariant
Ada Oui Oui Oui Oui tableaux Non Oui profondément imbriqué Non
APL Oui Non Oui Oui Oui Oui Oui profondément imbriqué Oui Non Non
C Oui Non Oui Non Non Oui Non profondément imbriqué profondément imbriqué Non
C++ Oui Non Oui Non Oui Oui Non profondément imbriqué profondément imbriqué Non
C# Oui Non Oui Non Oui Oui Non profondément imbriqué profondément imbriqué
COBOL Oui Non Oui Oui Non Oui Non profondément imbriqué profondément imbriqué Non
Lisp commun Oui Oui Oui Oui intégré uniquement Oui Oui profondément imbriqué Non
Oui Non Oui Oui Oui Oui Oui profondément imbriqué profondément imbriqué Non
Eiffel Oui Non Non Oui Oui Oui Non un niveau Non Non Non entier seulement Oui
F# Oui Non Non Oui Oui Non Non Non Non Non
FORTRAN 77 Oui Non Non Oui Non Non Non un niveau Oui
Fortran 90 Oui Non Non Oui Non Non Oui profondément imbriqué Oui
Fortran 95 et versions ultérieures Oui Non Non Oui tableaux Non Oui profondément imbriqué Oui
Haskell Non Non Non Non Oui Non Oui Non Non Non
Java Oui Non Oui Non Oui Oui Non profondément imbriqué profondément imbriqué Non non natif non natif
JavaScript Oui Non Oui Non Oui Oui Non profondément imbriqué profondément imbriqué Non
Naturel Oui Oui Oui Oui Non Oui Oui Oui Oui Oui Non
OCaml Oui Non Non Oui tableaux, listes Non Non Non Non Non
PHP Oui Non Oui Non Oui Oui Non profondément imbriqué profondément imbriqué Non
Perl Oui Non Oui Non Oui Oui Non profondément imbriqué profondément imbriqué Oui
Python Oui Non Non Non Oui Non Non profondément imbriqué profondément imbriqué Non
REBOL Non Oui Oui Oui Oui Non Oui un niveau Non Non
Rubis Oui Non Oui Oui Oui Non Oui profondément imbriqué profondément imbriqué Oui Oui
ML standard Oui Non Non Non tableaux, listes Non Non Non Non Non
Visual Basic .NET Oui Non Oui Oui Oui Non Oui un niveau par type de boucle un niveau par type de boucle
PowerShell Oui Non Oui Non Oui Oui Non ? Oui
  1. a while (true) ne compte pas comme une boucle infinie dans ce but, car ce n'est pas une structure de langage dédiée.
  2. a b c d e f g h Labouclede Cest une construction de boucle générale, pas spécifiquement une construction de comptage, bien qu'elle soit souvent utilisée pour cela.for (init; test; increment)
  3. a b c Des ruptures profondes peuvent être accomplies en APL, C, C++ et C# grâce à l'utilisation d'étiquettes et de gotos.
  4. une itération sur les objets a étéajoutéeen PHP 5.
  5. a b c Une boucle de comptage peut être simulée en itérant sur une liste ou un générateur d'incrémentation, par exemple Python'srange().
  6. a b c d e Des ruptures profondes peuvent être accomplies en utilisant la gestion des exceptions.
  7. a Il n'y a pas de construction spéciale, puisque lawhilefonction peut être utilisée pour cela.
  8. a Il n'y a pas de construction spéciale, mais les utilisateurs peuvent définir des fonctions de boucle générales.
  9. a LanormeC++11 aintroduit leformat basé surlaplage pour. Dans laSTL, il existe unefonctionstd::for_each modèlequi peut itérer sur lesconteneursSTLet appeler unefonction unairepour chaque élément. La fonctionnalité peut également être construite sous forme demacrosur ces conteneurs.
  10. un bouclage commandé par comptage est effectué par itération sur un intervalle entier ; sortie anticipée en incluant une condition supplémentaire de sortie.
  11. a Eiffel prend en charge un mot réservéretry, mais il est utilisé dans lagestion des exceptions, pas dans le contrôle de boucle.
  12. a Nécessite lelangage despécification d'interface comportementaleJava Modeling Language(JML).
  13. a Exige que les variantes de boucle soient des entiers ; les variantes transfinies ne sont pas prises en charge. [1]
  14. a D prend en charge des collections infinies et la possibilité d'itérer sur ces collections. Cela ne nécessite aucune construction particulière.
  15. a Des ruptures profondes peuvent être obtenues à l'aide deGO TOprocédures et .
  16. a Common Lisp est antérieur au concept de type de collection générique.

Flux de contrôle non local structuré

De nombreux langages de programmation, en particulier ceux qui favorisent des styles de programmation plus dynamiques, offrent des constructions pour un flux de contrôle non local . Celles-ci provoquent le saut du flux d'exécution hors d'un contexte donné et sa reprise à un point prédéclaré. Les conditions , les exceptions et les continuations sont trois types courants de constructions de contrôle non locales ; il en existe aussi des plus exotiques, comme les generators , les coroutines et le mot-clé async .

Conditions

PL/I a quelque 22 conditions standard (par exemple, ZERODIVIDE SUBSCRIPTRANGE ENDFILE) qui peuvent être levées et qui peuvent être interceptées par : ON condition action ; Les programmeurs peuvent également définir et utiliser leurs propres conditions nommées.

Comme le if non structuré , une seule instruction peut être spécifiée, donc dans de nombreux cas, un GOTO est nécessaire pour décider où le flux de contrôle doit reprendre.

Malheureusement, certaines implémentations avaient un surcoût substantiel à la fois dans l'espace et dans le temps (en particulier SUBSCRIPTRANGE), de nombreux programmeurs ont donc essayé d'éviter d'utiliser des conditions.

Exemples de syntaxe courante :

 ON condition GOTO label

Exceptions

Les langages modernes ont une construction structurée spécialisée pour la gestion des exceptions qui ne repose pas sur l'utilisation de GOTOsauts ou de retours (à plusieurs niveaux). Par exemple, en C++ on peut écrire :

try {
    xxx1                                  // Somewhere in here
    xxx2                                  //     use: '''throw''' someValue;
    xxx3
} catch (someClass& someId) {             // catch value of someClass
    actionForSomeClass 
} catch (someType& anotherId) {           // catch value of someType
    actionForSomeType
} catch (...) {                           // catch anything not already caught
    actionForAnythingElse
}

N'importe quel nombre et variété de catchclauses peuvent être utilisées ci-dessus. S'il n'y a pas de catchcorrespondance particulière throw, le contrôle revient à travers des appels de sous-programmes et/ou des blocs imbriqués jusqu'à ce qu'une correspondance catchsoit trouvée ou jusqu'à ce que la fin du programme principal soit atteinte, moment auquel le programme est arrêté de force avec un message d'erreur approprié.

Via l'influence de C++, catchest le mot-clé réservé à la déclaration d'un gestionnaire d'exceptions de correspondance de modèle dans d'autres langages populaires aujourd'hui, comme Java ou C#. Certains autres langages comme Ada utilisent le mot-clé exceptionpour introduire un gestionnaire d'exceptions et peuvent même utiliser un mot-clé différent ( whenen Ada) pour la correspondance de modèle. Quelques langages comme AppleScript incorporent des espaces réservés dans la syntaxe du gestionnaire d'exceptions pour extraire automatiquement plusieurs informations lorsque l'exception se produit. Cette approche est illustrée ci-dessous par la on errorconstruction d'AppleScript :

try
    set myNumber to myNumber / 0
on error e  number n  from f  to t  partial result pr
    if ( e = "Can't divide by zero" ) then display dialog "You must not do that"
end try

Le manuel de David Watt de 2004 analyse également la gestion des exceptions dans le cadre des séquenceurs (présenté dans cet article dans la section sur les premières sorties de boucles). Watt note qu'une situation anormale, généralement illustrée par des débordements arithmétiques ou des échecs d' entrée/sortie comme un fichier introuvable, est une sorte d'erreur qui "est détectée dans une unité de programme de bas niveau, mais [pour laquelle] un gestionnaire est plus naturellement localisé dans une unité de programme de haut niveau". Par exemple, un programme peut contenir plusieurs appels pour lire des fichiers, mais l'action à effectuer lorsqu'un fichier n'est pas trouvé dépend de la signification (objectif) du fichier en question pour le programme et donc une routine de gestion pour cette situation anormale ne peut pas être situé dans le code système de bas niveau. Watts note en outre que l'introduction de tests d'indicateurs d'état dans l'appelant, comme entraînerait une programmation structurée à sortie unique ou même des séquenceurs de retour (sorties multiples), aboutit à une situation dans laquelle "le code d'application a tendance à être encombré par des tests d'indicateurs d'état" et que « le programmeur peut négliger ou paresseusement omettre de tester un indicateur d'état. En fait, les situations anormales représentées par des indicateurs d'état sont ignorées par défaut ! » Watt note que contrairement aux tests d'indicateurs d'état, les exceptions ont le comportement par défaut opposé , provoquant l'arrêt du programme à moins que le programmeur ne traite explicitement l'exception d'une manière ou d'une autre, éventuellement en ajoutant du code explicite pour l'ignorer. Sur la base de ces arguments, Watt conclut que les séquenceurs de saut ou les séquenceurs d'échappement ne sont pas aussi adaptés qu'un séquenceur d'exceptions dédié avec la sémantique décrite ci-dessus.

Dans Object Pascal, D, Java, C# et Python, une finallyclause peut être ajoutée à la tryconstruction. Quelle que soit la façon dont le contrôle laisse le trycode à l'intérieur de la finallyclause, l'exécution est garantie. Ceci est utile lors de l'écriture de code qui doit abandonner une ressource coûteuse (telle qu'un fichier ouvert ou une connexion à une base de données) une fois le traitement terminé :

FileStream stm = null;                    // C# example
try
{
    stm = new FileStream("logfile.txt", FileMode.Create);
    return ProcessStuff(stm);             // may throw an exception
} 
finally
{
    if (stm != null)
        stm.Close();
}

Étant donné que ce modèle est assez courant, C# a une syntaxe spéciale :

using (var stm = new FileStream("logfile.txt", FileMode.Create))
{
    return ProcessStuff(stm); // may throw an exception
}

En quittant le usingbloc, le compilateur garantit que l' stmobjet est libéré, liant efficacement la variable au flux de fichier tout en faisant abstraction des effets secondaires de l'initialisation et de la libération du fichier. L' withinstruction de Python et l'argument de bloc de Ruby à File.opensont utilisés avec un effet similaire.

Tous les langages mentionnés ci-dessus définissent des exceptions standard et les circonstances dans lesquelles elles sont levées. Les utilisateurs peuvent lancer leurs propres exceptions ; en fait, C++ permet aux utilisateurs de lancer et d'attraper presque n'importe quel type, y compris les types de base comme int, alors que d'autres langages comme Java ne sont pas aussi permissifs.

Suite

Asynchrone

C# 5.0 a introduit le mot-clé async pour prendre en charge les E/S asynchrones dans un « style direct ».

Générateurs

Les générateurs , également connus sous le nom de semi-coroutines, permettent de céder temporairement le contrôle à une méthode de consommation, généralement à l'aide d'un yieldmot - clé ( yield description ) . Comme le mot-clé async, cela prend en charge la programmation dans un "style direct".

Coroutines

Les coroutines sont des fonctions qui peuvent se contrôler mutuellement - une forme de multitâche coopératif sans threads.

Les coroutines peuvent être implémentées en tant que bibliothèque si le langage de programmation fournit soit des continuations, soit des générateurs - la distinction entre coroutines et générateurs en pratique est donc un détail technique.

Référence croisée du flux de contrôle non local

Langage de programmation conditions exceptions générateurs/coroutines asynchrone
Ada Non Oui ? ?
C Non Non Non Non
C++ Non Oui oui, en utilisant BOOST ?
C# Non Oui Oui Oui
COBOL Oui Oui Non Non
Lisp commun Oui Non ? ?
Non Oui Oui ?
Eiffel Non Oui ? ?
Erlang Non Oui Oui ?
F# Non Oui Oui Oui
Aller Non Oui Oui ?
Haskell Non Oui Oui Non
Java Non Oui Non Non
JavaScript ? Oui Oui Oui
Objectif c Non Oui Non ?
PHP Non Oui Oui ?
PL/I Oui Non Non Non
Python Non Oui Oui Oui
REBOL Oui Oui Non ?
Rubis Non Oui Oui ?
Rouiller Non Oui expérimental Oui
Scala Non Oui via extension expérimentale via extension expérimentale
Tcl via des traces Oui Oui via la boucle d'événement
Visual Basic .NET Oui Oui Non ?
PowerShell Non Oui Non ?

Structures de contrôle proposées

Dans un article parodiant de Datamation en 1973, R. Lawrence Clark a suggéré que la déclaration GOTO pourrait être remplacée par la déclaration COMEFROM , et fournit quelques exemples amusants. COMEFROM a été implémenté dans un langage de programmation ésotérique nommé INTERCAL .

L'article de 1974 de Donald Knuth "Programmation structurée avec go to Statements", identifie deux situations qui n'étaient pas couvertes par les structures de contrôle énumérées ci-dessus, et a donné des exemples de structures de contrôle qui pourraient gérer ces situations. Malgré leur utilité, ces constructions n'ont pas encore trouvé leur place dans les langages de programmation traditionnels.

Boucle avec test au milieu

Ce qui suit a été proposé par Dahl en 1972 :

   loop                           loop
       xxx1                           read(char);
   while test;                    while not atEndOfFile;
       xxx2                           write(char);
   repeat;                        repeat;

Si xxx1 est omis, nous obtenons une boucle avec le test en haut (une boucle while traditionnelle ). Si xxx2 est omis, nous obtenons une boucle avec le test en bas, équivalente à une boucle do while dans de nombreuses langues. Si while est omis, nous obtenons une boucle infinie. La construction ici peut être considérée comme une boucle do avec la vérification while au milieu. Par conséquent, cette construction unique peut remplacer plusieurs constructions dans la plupart des langages de programmation.

Les langues dépourvues de cette construction l'émulent généralement en utilisant un idiome équivalent de boucle infinie avec rupture :

while (true) {
    xxx1
    if (not test)
        break
    xxx2
}

Une variante possible est d'autoriser plus d'un test while ; dans la boucle, mais l'utilisation de exitwhen (voir la section suivante) semble mieux couvrir ce cas.

Dans Ada , la construction de boucle ci-dessus ( loop - while - repeat ) peut être représentée à l'aide d'une boucle infinie standard ( loop - end loop ) qui a une clause exit when au milieu (à ne pas confondre avec l' instruction exitwhen dans la section suivante ).

with Ada.Text_IO;
with Ada.Integer_Text_IO;

procedure Print_Squares is 
    X : Integer;
begin
    Read_Data : loop
        Ada.Integer_Text_IO.Get(X);
    exit Read_Data when X = 0;
        Ada.Text IO.Put (X * X);
        Ada.Text IO.New_Line;
    end loop Read_Data;
end Print_Squares;

Nommer une boucle (comme Read_Data dans cet exemple) est facultatif mais permet de quitter la boucle externe de plusieurs boucles imbriquées.

Sortie anticipée multiple/sortie de boucles imbriquées

Cela a été proposé par Zahn en 1974. Une version modifiée est présentée ici.

   exitwhen EventA or EventB or EventC;
       xxx
   exits
       EventA: actionA
       EventB: actionB
       EventC: actionC
   endexit;

exitwhen est utilisé pour spécifier les événements qui peuvent se produire dans xxx , leur occurrence est indiquée en utilisant le nom de l'événement comme instruction. Lorsqu'un événement se produit, l'action appropriée est effectuée, puis le contrôle passe juste après endexit . Cette construction fournit une séparation très claire entre déterminer qu'une situation s'applique et l'action à prendre pour cette situation.

exitwhen est conceptuellement similaire à la gestion des exceptions , et des exceptions ou des constructions similaires sont utilisées à cette fin dans de nombreux langages.

L'exemple simple suivant implique la recherche d'un élément particulier dans un tableau à deux dimensions.

   exitwhen found or missing;
       for I := 1 to N do
           for J := 1 to M do
               if table[I,J] = target then found;
       missing;
   exits
       found:   print ("item is in table");
       missing: print ("item is not in table");
   endexit;

Sécurité

Une façon d'attaquer un logiciel est de rediriger le flux d'exécution d'un programme. Une variété de techniques d' intégrité de flux de contrôle , y compris les canaries de pile , la protection contre le débordement de tampon , les piles d'ombre et la vérification de pointeur vtable , sont utilisées pour se défendre contre ces attaques.

Voir également

Les références

Lectures complémentaires

  • Hoare, CAR « Partition : algorithme 63 », « Quicksort : algorithme 64 » et « Rechercher : algorithme 65 ». Comm. ACM 4, 321-322, 1961.

Liens externes