L'expression du non-déterminisme

DIJKSTRA (75) propose deux constructions pour introduire le non déterminisme dans l'exécution d'un programme séquentiel. Ces deux structures de contrôle (alternative et répétitive) sont basées sur les commandes gardées.

<commandeGardee> ::= <garde> -> <listeCommandes>
<garde>          ::= <expressionBooleenne>|<commandeEntree>|<commandeSortie>
<listeCommandes> ::= <commande>{;<commande>}*
<commande>       ::= <instruction>|<commandeEntree>|<commandeSortie>
<commandeEntree> ::= <idProcessus>?<idMessage>
<commandeSortie> ::= <idProcessus>!<idMessage>

Une commande gardée ne peut être exécutée que lorsque la(le) garde est vrai(e). L'instruction (si elle existe) associée à la garde est exécutée, puis la liste de commandes associée.

Les structures de contrôles :

<ensembleCommandeGardees> ::= <commandeGardee>{[] <commandeGardee>}*
<alternative>          ::= if <ensembleCommandeGardees> fi
<repetitive>           ::= do <ensembleCommandeGardees> od

et leurs sémantiques.

Alternative

 

1. Evaluation de tous les gardes.
2. Si aucun garde n'est vrai alors ECHEC sinon
   1. Sélection (non déterministe) d'un garde parmi ceux évalués à vrai.
   2. Exécution de la commande gardée associée.
   3. FIN de l'alternative.

Répétitive

 

1. Evaluation de tous les gardes.
2. Si aucun garde n'est vrai alors FIN sinon
   1. Sélection (non déterministe) d'un garde parmi ceux évalués à vrai.
   2. Exécution de la commande gardée associée.
   3. RETOUR en (1).

Ce concept n'existe que dans peu de langages (ADA, CSP, OCCAM).