# Application d'une methode descendante a la specification d'un système de simulation conversationnelle

Jean Boulenger, Marc Kronental

► To cite this version:

Jean Boulenger, Marc Kronental. Application d'une methode descendante a la specification d'un système de simulation conversationnelle. [Rapport de recherche] IRIA-RR-167, IRIA. 1976, pp.63. hal-04716393

HAL Id: hal-04716393

https://inria.hal.science/hal-04716393v1

Submitted on 1 Oct 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
IRIA

laboria

Institut de Recherche
d'Informatique
et d'Automatique

Domaine de Voluceau
Rocquencourt
B. P. 5 78150 - Le Chesnay
France
Tél.: 954 90 20

laboratoire de recherche
en informatique
et automatique

<figure><img src="image_2.png" /></figure>

APPLICATION D'UNE
MÉTHODE DESCENDANTE
A LA SPÉCIFICATION
D'UN SYSTÈME DE
SIMULATION
CONVERSATIONNELLE

Jean Marc
J. Boulenger, M. Kronental

Rapport de Recherche N°167

Avril 1976
APPLICATION D'UNE MÉTHODE DESCENDANTE A LA
SPÉCIFICATION D'UN SYSTEME DE
SIMULATION CONVERSATIONNELLE

J. Boulenger, M. Kronental

IRIA/LABORIA

Résumé :

Cette étude décrit l'application d'une méthode descendante à la spécification d'un petit système de simulation conversationnelle. Le système est décrit en termes de processus parallèles. Nous utilisons la notion de type définie dans le rapport LABORIA n° 108 pour raffiner les algorithmes de certains de ces processus.

L'une des façons les plus concises pour décrire les relations entre processus est d'utiliser la notion de «monitor» de Brinch Hansen. Malheureusement cela ne permet pas de spécifier ces relations autrement que par le rôle implicite des instructions «delay» et «continue» utilisées.

Pour parvenir à expliciter ces relations, nous introduisons ici une méthode informelle de spécification articulée autour de la notion de type de «machine».

Abstract :

This paper presents the application of a top down approach to the specification of a small interactive simulation-oriented system. The system is described in terms of parallel processes. We use the data type concept defined in the LABORIA report n° 108 to refine the algorithms of some of these processes.

One of the most concise way of describing the relations between processes is to use Brinch Hansen's «monitor» concept. Unfortunately this does not help to specify these relations : these ones remain implicit in the use of the «delay» and «continue» statements.

In order to make these relations more explicit we introduce here an informal specification method which uses a concept of «machine» type.
## SOMMAIRE

INTRODUCTION ;

1. JEUX CONVERSATIONNELS ;

2. SPECIFICATION ET REPRESENTATION DU STR ;

3. COMPORTEMENT DU PROCESSUS UNIVERS ;

4. REPRESENTATION DES TYPES UTILISES DANS LE PROCESSUS UNIVERS ;

CONCLUSION ;

REFERENCES.
Si l'on se rapporte à C. PAIR, ([Pont à Mousson 74]) la résolution d'un problème quelconque par une méthode informatique devrait comporter les trois étapes suivantes :

1. appréhension de la situation concrète dans laquelle se pose le problème et de l'environnement informatique dans lequel on devra le résoudre ;

2. conception, consistant à trouver un algorithme "facile à programmer" dans l'environnement ci-dessus, et un moyen de le comprendre (c'est-à-dire de se convaincre qu'il est correct) ;

3. fabrication et entretien, consistant à produire le texte du programme et sa documentation (c'est-à-dire la relation entre ce programme et l'algorithme ci-dessus ainsi que la procédure de mise en oeuvre de ce programme).

On trouve dans la littérature informatique de nombreuses tentatives d'application de ce schéma au cas de systèmes séquentiels simples (notamment dans [Hoare 72], [Hoare 72A], [Dijkstra 69], [Dijkstra 71], [Liskov 74], etc). En revanche, son application au cas des systèmes d'exploitation est assez rarement exposée (on ne peut guère citer que [Hoare 73], [Habermann 73], [Bezivin 74]) ; de plus, les exposés existants ne sont pas exactement conformes à ce schéma faute d'un procédé d'abstraction de "ce que fait" un système d'exploitation. Le but de la présente étude est de montrer que ce schéma est effectivement applicable dans le cas d'un petit système parallèle.

Entre juillet 71 et juillet 72, nous avons réalisé un sous-système du système ESOPE ([Bétourné 71]) appelé STR pour la simulation conversationnelle (voir plus loin le paragraphe 1). A cette époque, nous disposions

des notions de processus et de sémaphore introduites dans ESOPE ;

d'un langage de bas niveau, analogue au PL 360 ([Boulenger 74]).

Compte tenu du fait que nous ne savions ni spécifier ce que faisait STR ni décrire son architecture autrement qu'en français ou en langage de programmation, ce système a été construit de façon ascendante c'est-à-dire qu'une collection de processus, synchronisés au moyen de sémaphores et d'une horloge a été introduite sans justification.

Une autre difficulté était qu'il fallait réaliser des structures de données compliquées au moyen d'un langage de programmation de bas niveau. Pour y pallier, on a défini un langage de programmation non compilé (analogue au SIMULA 67).

Il a été ainsi possible de décrire ces structures de données et les algorithmes les manipulant, et de vérifier à la main leur comportement. Le tout a été
ensuite traduit dans le langage de programmation disponible, avec une phase de mise au point très brève.

Malgré tout le soin que nous avons apporté à cette expérience, celle-ci nous a laissé insatisfaits pour plusieurs raisons :

• la spécification du STR obtenue est difficilement récupérable, même partiellement parce qu'elle est exprimée en termes d'une machine et d'un système d'exploitation particulier ;

• en l'absence d'un énoncé précis, il était impossible de vérifier formellement les algorithmes du STR ;

• nous n'avions pas réussi à structurer la documentation du STR de telle sorte qu'il soit facile d'y retrouver toute information (par exemple un choix de réalisation).

Cela nous a conduit à choisir le STR comme sujet d'expérimentation d'une méthode descendante.
# SOMMAIRE

## 1 JEUX CONVERSATIONNELS :

1.1 Notion de jeu conversationnel ;

1.2 Exemple ;

1.3 Réalisation ;

1.4 Synchronisation des joueurs et de l'univers ;

1.5 Communication entre les joueurs et l'univers.

# NOTATIONS

Les noms des ensembles sont en italiques, ceux des autres entités (notions, variables et valeurs) en caractères droits.

Les valeurs sont en minuscules, les notions et variables en majuscules.

Les notations utilisées dans cet exposé emploient la collection suivante de caractères (éventuellement ornés d'indices, d'apostrophes,...) :

U univers simulé,

U ensemble des configurations possibles u de cet univers,

T temps dans lequel évolue l'univers,

T ensemble des instants possibles t de T,

I ensemble des instants où la date est communiquée aux joueurs,

J joueur.
# 1 JEUX CONVERSATIONNELS :

## 1.1 Notion de jeu conversationnel.

L'objet d'un jeu conversationnel est de confronter n joueurs humains $J_1, J_2, \dots, J_n$, isolés les uns des autres à un univers simulé U. Une **partie** consiste en une succession d'interactions entre l'univers et les joueurs dans le temps $T$ de cet univers [Boucher 70].

Il s'agit pour U de placer chaque joueur J dans une situation qui évolue dans $T$, et de tenir compte des initiatives que J ou d'autres joueurs prennent pour influer sur cette situation.

On appelle $T$ l'ensemble de toutes les dates possibles du temps $T$. Cet ensemble est une caractéristique du jeu. Il est totalement ordonné.

Les interactions entre le joueur J et l'univers U sont de l'un des quatre types suivants :

**renseignement** : le joueur J est informé de sa situation dans U à la date $t$;

**exemple** : bilan au 1er juillet 1975 de l'entreprise de papier dirigée par J ;
on dit que le renseignement **intervient** à la date $t$;

**choix** : U invite J à choisir la valeur d'une (ou plusieurs) grandeur(s) et fixe la date $t$ à laquelle le choix prendra effet ;

**exemple** : définir le taux d'augmentation de la production de papier pour l'année 1975 ; valeurs admissibles du taux : 0%, 1%, 2% ; la nouvelle valeur du taux sera prise en compte à partir du 1er janvier 1975 ;
on dit que le choix **intervient** à la date $t$;

**décision** : à la suite de l'analyse qu'il fait de sa situation J prend, de sa propre initiative, une décision et fixe la date $t$ à laquelle elle s'appliquera ;

**exemple** : arrêter la production de papier pour une durée de un mois à partir du 1er Août 1975 ;
on dit que la décision **intervient** à la date $t$;
**question** : J demande à U de lui fournir la valeur d'une (ou plusieurs) grandeur(s) à la date t ; ces valeurs constituent la **réponse** à la question ;

exemple : fournir la valeur du stock de papier au 1er juin 1975 ; on dit que la question **intervient** à la date t.

Les interactions s'expriment au moyen de messages alphanumériques ; l'ensemble des messages possibles constitue alors un langage propre à chaque jeu que l'on appellera dans la suite **langage d'interaction**.

Toute interaction intervient à une date t de T et est instantanée (dans T). La date est communiquée (pseudo) périodiquement à tous les joueurs. On appelle *l'ensemble des dates communiquées* aux joueurs au cours de la partie ; c'est un sous-ensemble fini de T. Ceci permet de matérialiser l'écoulement du temps T : une fois que la date t est communiquée à un joueur celui-ci ne peut plus prendre de décision ou fixer de choix intervenant à une date antérieure à t.

Pour plusieurs parties du même jeu, on a le même ensemble T mais les ensembles *I* peuvent être différents.

Par définition, toutes les informations sur l'univers U, qui figurent dans un renseignement ou en réponse à une question intervenant à la date t sont déduites de la **situation** de l'univers à cette date. Par ailleurs la situation de l'univers à une date t est fonction de toutes les décisions et de tous les choix qui interviennent à cette date.

Remarque : On verra dans le paragraphe 3 que pour des raisons inhérentes au procédé de simulation employé cette situation ne peut pas être assimilée à une collection de coordonnées fonctions de la date t.

La **règle d'un jeu** conversationnel décrit :

1 : ce qu'est l'univers U et son temps T,

2 : le rôle de chaque joueur dans U,

3 : le langage d'interaction.
## 1.2 Exemple de jeu conversationnel.

Afin d'illustrer les définitions du paragraphe précédent, montrons comment elles s'utilisent pour décrire un jeu d'entreprise très élémentaire. La règle de ce jeu est la suivante :

1. L'univers $U$ est une collection d'entreprises confrontées à un marché. Elles produisent toutes du papier dont le coût unitaire de production, constant au cours du temps est le même pour toutes les entreprises. A tout instant $t$, chaque entreprise dispose d'un stock de papier $stock(t)$ et d'une encaisse en monnaie $encaisse(t)$ ; elle produit du papier au taux de production $taux(t)$ et elle le vend au prix $prix(t)$. Initialement, toutes les entreprises ont la même encaisse, le même stock de papier, le même taux de production, le même prix de vente. L'ensemble $T$ est l'ensemble des premiers de chaque mois des années 1974 à 1984.

2. Chaque joueur $J$ est le chef d'une entreprise de papier. Il peut, au cours du jeu, fixer son prix de vente et son taux de production. On lui propose des commandes de papier à ce prix (ou à un prix voisin) qu'il peut accepter ou refuser. $J$ détermine sa stratégie en fonction des éléments suivants :
    * la durée du jeu,
    * le prix de vente moyen courant du marché,
    * les commandes reçues,
    sachant qu'en fin de jeu, le joueur qui a gagné est celui qui a l'encaisse la plus élevée.
    Au cours du jeu, le stock de papier et l'encaisse d'une entreprise ne doivent jamais devenir négatifs. Si cela arrive, l'entreprise et son chef sont éliminés.

3. Les interactions entre un joueur et l'univers sont définies par le langage d'interaction du jeu. Nous les décrivons ici de façon informelle. Chaque joueur reçoit périodiquement les renseignements :
    * concernant le marché :
        * date courante,
        * temps de jeu restant,
        * prix de vente moyen actuel ;
concernant son entreprise :

stock de papier actuel,

encaisse actuelle,

prix de vente actuel,

taux de production actuel,

livraisons à faire (prix, quantité, date de la livraison).

On lui propose des commandes sous la forme du choix unique :

acceptez-vous de me livrer la quantité q de papier au
prix p pour la date t ?

Réponses possibles : oui ou non ; en cas d'acceptation le choix intervient immédiatement.

Il peut prendre les décisions suivantes concernant son entreprise :

fixation du prix de vente actuel ;

fixation du taux de production actuel.

Cet exemple sera repris dans les paragraphes suivants pour illustrer
les problèmes de simulation discrète et de synchronisation.

1.3 Réalisation d'un jeu conversationnel.

La réalisation d'un jeu conversationnel sur un ordinateur comprend trois
éléments :

. un programme, propre au jeu, pour simuler le comportement de l'univers, c'est-à-dire évaluer sa situation aux dates de I ;

. un compilateur, propre au jeu, pour traduire les décisions, les choix et les questions en événements destinés à contrôler le comportement (simulé) de l'univers ;

. un système, appelé STR pour, assurer la communication entre les joueurs et l'univers et synchroniser les exécutions du programme de simulation et du compilateur avec les joueurs ; le système STR ne dépend que du nombre n des joueurs d'un jeu conversationnel : il est donc quasi-indépendant de celui-ci. Dans la réalisation faite sur l'ordinateur CII 10070, géré par le système d'exploitation ESOPE, le système STR est l'usager "temps-réel" de ce système ; la communication entre joueurs et univers se fait par l'intermédiaire de terminaux alphanumériques ; une partie est initialisée par un "meneur de jeu" à partir d'un terminal particulier.

1.4 Synchronisation des joueurs et de l'univers.

Synchroniser les joueurs et l'univers, c'est assurer que toute décision
prise au vu de renseignements intervenant à t, et devant intervenir à t'>t
soit prise en compte dans l'évaluation de la situation de l'univers à t' par le
programme de simulation. Il en est de même pour un choix ou une question. De
plus, le procédé de synchronisation doit être tel que l'on puisse reconstituer
une partie à partir de ce qui a été imprimé sur les terminaux des joueurs.
On le soumet donc aux contraintes suivantes :

. toute date de I est imprimée sur tous les terminaux des joueurs ;

. si t' est la date qui succède à t dans I, tout renseignement
intervenant à t est imprimé entre les dates t et t',

. toute décision imprimée par un joueur entre les dates t et t' peut,
si elle est reconnue correcte par le compilateur, intervenir à t' ou
à une date ultérieure ;

. la date t' ne dépend que de t et de la situation de l'univers à la date
t;

. l'intervalle de temps physique (nécessaire à la réflexion des joueurs) qui sépare les impressions des dates t et t' est fixé à l'initialisation de la partie ; il peut être modifié au cours de celle-ci soit par le meneur de jeu soit par le programme de simulation.

1.5. *Communication entre les joueurs et l'univers.*

Du point de vue du système STR les interactions entre les joueurs et l'univers se traduisent par des transmissions de messages alphanumériques. En effet, un renseignement est un message adressé par l'univers à un joueur. Il en est de même pour un choix; la contrainte qu'un choix exige une décision du joueur concerné par ce choix relève du programme de simulation. Une décision est un message adressé par un joueur à l'univers via le compilateur. Il en est de même pour une question; la contrainte qu'une question exige en retour un renseignement relève du programme de simulation.

Il en résulte que le rôle de STR revient, en ce qui concerne la communication entre les joueurs et l'univers, à gérer les messages transmis en respectant les dates auxquelles les interactions qu'ils représentent doivent intervenir.
## SOMMAIRE

### PREAMBULE.

2 SPECIFICATION ET REPRESENTATION DU SYSTEME STR :

2.1. Notions utilisées :

2.11 Généralités ;

2.12 Notations ;

2.13 Spécification d'un type de machine ;

2.14 Spécification d'une machine de production - consommation ;

2.15 Représentation d'un type de machine.

2.2. Spécification informelle du STR :

2.21 Processus JOUEURᵢ (1≤i≤n) ;

2.22 Processus UNIVERS ;

2.23 Relation entre les processus.

2.3. Décomposition du système STR :

2.31 Etude de la communication entre les joueurs et le système ;

2.32 Etude des sorties ordonnées par le processus UNIVERS ;

2.33 Compilation des messages ;

2.34 Décomposition de l'enregistrement ;

2.35 Sélection des messages dans ARRIVEES ;

2.36 Schéma récapitulatif ;

2.37 Types utilisés.

### PREAMBULE

Ce paragraphe utilise les notations du paragraphe 1. Il suppose connue la notion de type développée dans [BK 75]. Par rapport à la notion d'opération qui y est définie on a ajouté la notion de paramètre résultat ; par exemple la **procedure** faire(Y,R) ; obs(T₁)Y ; res(T₂)R aura une spécification de la forme de :

X=x & Y=y {X.faire(Y,R)} X=f(x,y) & R=g(x,y).
## 2.1 Notions utilisées.

On se propose dans ce qui suit d'ébaucher une théorie des systèmes à processus parallèles analogue à celle qui a été faite dans [BK 75] pour les systèmes séquentiels (à un seul processus).

## 2.11 Généralités.

La notion première est celle d'action, au sens usuel du terme. Une action a une date de début, à laquelle elle commence, et une date de fin à laquelle elle se termine.

Ces dates sont des dates du temps physique.

Une action porte sur des objets, qu'elle transforme éventuellement. Un processus est un ensemble ordonné d'actions. Si $a_1$ et $a_2$ sont deux actions consécutives d'un processus, la date de début de $a_2$ est supérieure ou égale à la date de fin de $a_1$ ; en ce sens le processus est séquentiel, et on dit que $a_1$ précède $a_2$. Un système à processus parallèles est une collection fixe de processus. Si a et b sont des actions faisant partie de processus différents, il n'existe a priori aucune relation entre les dates (de début et de fin) de a et celles de b ; en ce sens il y a parallélisme. On considère dans ce qui suit des systèmes dont chaque processus résulte de l'exécution d'un algorithme. Toute action résulte donc de l'exécution d'une instruction, qui est elle même l'invocation d'une opération.

Il existe deux sortes d'objets :

* ceux qui ne sont manipulés que par des actions d'un seul processus ; ces objets ne sont pas modifiés dans l'intervalle de temps séparant deux actions consécutives du processus ; on peut donc leur associer un état observable dans de tels intervalles et les identifier aux variables de l'algorithme qui engendre ce processus ; les propriétés de ces objets peuvent donc être décrites à l'aide des notions et notations de [BK 75].

* ceux qui sont manipulés par des actions de plusieurs processus. On les appelle des machines. L'état d'une machine n'est pas observable par un processus. En effet considérons deux invocations successives de l'observation hypothétique M vue de la machine M par un processus. Bien que ces invocations ne soient séparées par l'invocation d'aucune transformation de M, elles peuvent avoir des résultats différents. Cette différence est due à l'exécution de transformations de M par d'autre processus. La notion d'état d'une machine pour un processus est donc
caduque, et par conséquent la spécification des opérations de
la machine par des fonctions de cet état est impossible. Il
faut donc un autre procédé pour spécifier les types de machines.
Ceci est l'objet du paragraphe 2.13.

Un processus est spécifié par son algorithme. Par suite spécifier un
système consiste essentiellement à exprimer les relations de synchronisation
et d'échange d'information existant entre les processus de ce système. Ces
relations n'ayant lieu qu'au travers d'objets manipulés simultanément par
plusieurs processus, c'est à dire de machines, la spécification d'un système
se compose de :

• la collection des algorithmes des processus de ce système ;

• la collection des spécifications des types de machines de ce système.

## 2.12 Notations.

Un type de machine est caractérisé par la collection des opérations qui
permettent de manipuler toute machine M de ce type par des instructions de
la forme :

$M.p<paramètres effectifs>$,

l'opération p ayant un en-tête de la forme :

procedure p<paramètres formels> ; <declaration des paramètres formels>
où tout paramètre formel X est soit déclaré par machine(T) X, soit déclaré
par obs(T) X ou res(T) X suivant qu'il est une variable observée ou assignée
dans le corps de la procedure p.

Lorsqu'il n'existe dans un système qu'un seul objet de type T (type de variable ou type de machine) on convient de donner le nom T à cet objet et de parler de spécification ou de représentation de l'objet T sans en mentionner explicitement le type.

On convient de schématiser les relations entre processus et machines
de la façon qui suit.

Une machine est schématisée par un rectangle ; on peut éventuellement
faire correspondre un point de la frontière de ce rectangle à une opération
du type de cette machine.

Un processus est schématisé par un cercle.

Le fait que le processus P adresse des actions à la machine X sera
schématisé par une flèche de P vers X comme ci-dessous :

<figure><img src="image_3.png" /></figure>

Par exemple, dans le cas des producteurs-consommateurs du paragraphe 2.14, on a :

<figure><img src="image_4.png" /></figure>

Par convention, lorsque l'opération p du type de machine T comporte un
paramètre formel machine tel que pour toute invocation de p, le paramètre
effectif correspondant soit toujours la même machine Y, on omet de déclarer
ce paramètre et on représente (pour toute machine X du type T) cette relation
par :

<figure><img src="image_5.png" /></figure>

si q est l'opération (manipulant Y) invoquée par l'opération p.
## 2.13 Spécification d'un type de machine.

Dans ce qui suit, on définit la spécification d'un type de machine M qui devrait jouer un rôle analogue à celui de la spécification d'un type de variable.

Pour ce faire, on considère l'histoire d'une machine M du type considéré entre les instants physiques 0 et $\phi$. Cette histoire est définie par deux ensembles notés $M.E(\phi)$ et $M.S(\phi)$ ($E(\phi)$ et $S(\phi)$ lorsqu'il n'y a pas d'ambiguïté sur M, $E$ et $S$ lorsqu'il n'y a pas non plus d'ambiguïté sur $\phi$) définis comme suit. A toute action s'adressant à M et dont la date de début est inférieure ou égale à $\phi$ correspond biunivoquement un élément de $E(\phi)$. A toute action s'adressant à M et dont la date de fin est inférieure ou égale à $\phi$ correspond biunivoquement un élément de $S(\phi)$. A partir d'un élément de $E$ ou de $S$ on peut retrouver :

* le processus dont fait partie l'action correspondante,

* l'opération invoquée,

* la valeur des paramètres effectifs (mais seulement de ceux qui sont observés dans le cas de $E$).

Par abus de langage on dira que c'est l'action qui est dans $E$ ou dans $S$. Par définition de $E$ et $S$, toute action qui est dans $S(\phi)$ est dans $E(\phi)$. On note $S(\phi),\psi$ l'ensemble des actions terminées entre les dates $\phi$ exclue et $\psi$ incluse.

$E$ est totalement ordonné par les dates de début des actions qui en font partie. De même $S$ est totalement ordonné par les dates de fin des actions qui en font partie.

La spécification du type de machine considéré est l'énoncé des propriétés qui caractérisent $E(\phi)$ et $S(\phi)$ pour toute date $\phi$. On va en donner un exemple dans le paragraphe 2.14.

On aura fréquemment à représenter les relations entre dates de début et de fin d'actions adressées à une machine M. On le fera sur un axe du temps physique associé à cette machine de la façon suivante :

<figure><img src="image_6.png" /></figure>

La flèche située au-dessus de l'axe correspond à la date $\phi$ de début de l'action $p$, la flèche située au-dessous à la date $\psi$ de fin de cette action. On appelle *intervalle* de l'action l'intervalle de temps compris entre $\phi$ et $\psi$. Deux actions sont dites disjointes si leurs intervalles respectifs sont disjoints.
2.14 Spécification d'une machine de production-consommation.

Le problème des producteurs-consommateurs ([Habermann 72]) s'énonce de la façon suivante :

* une collection de processus $P_1, P_2, \dots$ produisent des objets d'un certain type item ;

* une collection de processus $C_1, C_2, \dots$ consomment les objets ainsi produits ;

* les échanges entre les $P_i$ et les $C_j$ se font par l'intermédiaire d'une machine X, que l'on va spécifier.

La machine X comporte deux opérations :

procedure envoyer(L) ; obs(item) L et

procedure retirer(R) ; res(item) R

Les producteurs $P_i$ adressent à X des actions envoyer ; les consommateurs $C_j$ lui adressent des actions retirer. X.S et X.E sont donc des ensembles d'actions résultant des invocations de envoyer par les $P_i$ et de retirer par les $C_j$. A toute action X.retirer(R) de X.S ayant comme résultat R=x (où x est un élément de *item*) correspond une action X.envoyer(L) avec L=x, dont la date de fin est inférieure ou égale à celle de l'action X.retirer(R) considérée. Cette correspondance est telle qu'à deux actions X.retirer(R) distinctes correspondent deux actions X.envoyer(L) distinctes.

La machine X est supposée *saine* au sens suivant :

* toute action envoyer se termine au bout d'un temps fini ;

* si n actions retirer commencent à la date $\phi$, k d'entre elles (pour $1 \le k \le n$) se terminent au bout d'un temps fini *si et seulement si* il existe une date $\Psi$ (fonction de k) telle que le nombre d'actions envoyer dans $S(\Psi)$ surpasse de k le nombre d'actions retirer commencées à une date inférieure à $\phi$.
Exemple : dans le schéma ci-dessous,

<figure><img src="image_7.png" /></figure>

une flèche verticale correspond au commencement d'une ou plusieurs actions envoyer (en abrégé e) ou retirer (en abrégé r) ; à la date $\psi_1$, on peut affirmer qu'une des deux actions $r_2$ ou $r_3$ se termine ; à la date $\psi_2$, on peut affirmer que les deux actions $r_2$ et $r_3$ se terminent.

Dans ce qui suit, on n'utilisera la machine de production-consommation X qu'avec un seul processus consommateur. Dans ce cas, on impose à la correspondance précédente de respecter l'ordre des envoyer adressés à X par chaque processus producteur :

si deux actions envoyer $e_1$ et $e_2$ sont adressées à X par le même processus, si $e_1$ précède $e_2$, et si $r_1$ et $r_2$ sont les actions retirer qui leur correspondent respectivement, alors $r_1$ précède $r_2$.

Dans ce cas, la machine X est **saine** au sens suivant :

* toute action envoyer se termine au bout d'un temps fini ;

* toute action retirer (nécessairement adressée par l'unique consommateur) commençant à la date $\phi$ ne se termine au bout d'un temps fini que s'il existe une date $\Psi > \phi$ telle que le nombre d'actions envoyer dans $S(\Psi)$ surpasse de 1 le nombre d'actions retirer commencées à une date $< \phi$.

Si on suppose de plus que le processus consommateur est de la forme :

```
process C;
begin
    var(item)R;
    repeat
        begin
            X.retirer(R);
            traiter R
        end
    end
```

et que le traitement de R se termine toujours alors on peut montrer que :
si à la date $\phi$, S contient h ($h \ge 0$) actions envoyer, alors il existe
une date $\Psi > \phi_0$ à laquelle S contient h actions retirer.

Soit k le nombre d'actions retirer dans S ($\phi = (\phi_0)$). D'après la spécification, on a $0 \le k < h$. Si $k=h$, $\Psi = \phi_0$. Si $k < h$, de la forme du processus consommateur, on déduit qu'il existe une date supérieure ou égale à $\phi_0$ à laquelle une action retirer sera commencée et non terminée. A cette date, S contient au moins h envoyer. D'après la spécification, il existe une date $\phi_1$ à laquelle cette action retirer se terminera. A la date $\phi_1$, S contient k+1 actions retirer. On construit ainsi par récurrence une suite d'instants $\phi_0, \phi_1, \dots, \phi_{h-k}$. A la date $\Psi = \phi_{h-k}$, S contient h actions retirer. CQFD.

## 2.15 Représentation d'un type de machine.

Comme la représentation d'un type de variable, la représentation d'un type de machine comprend :

* la représentation de toute machine de ce type en termes de variables et de machines (de types "plus simples" que le type représenté),

* la représentation de toute opération p du type par un algorithme séquentiel manipulant les paramètres de p ainsi que des objets locaux (variables ou machines),

* l'algorithme d'initialisation de la représentation de toute machine du type.

Toute action a correspondant à l'invocation d'une de ces opérations est donc représentée par une séquence d'actions $a_1; a_2; \dots a_n$, comme le montre le schéma ci-dessous.

<figure><img src="image_8.png" /></figure>

Les intervalles de temps séparant le début de a du début de $a_1$ et la fin de $a_n$ de la fin de a dépendent de la réalisation du système et on ne sait rien sur eux.
Représentation de la machine de production-consommation spécifiée
au paragraphe 2.14.

Cette machine peut être représentée au moyen de la variable A de
type itemqueue spécifié dans [BK 75] et de deux machines MUTEX et TAILLE
de type sémaphore.

procedure envoyer(L) ; obs(item) L ;

begin

MUTEX.p ;

A.append(L) ;

MUTEX.v ;

TAILLE.v

end ;

procedure retirer(R) ; res(item) R ;

begin

TAILLE.p ;

MUTEX.p ;

R := A head ;

A.remove ;

MUTEX.v

end ;

initialisation : begin

comment A a la valeur initiale "vide" par
construction ;
MUTEX.initialiser(1) ;
TAILLE.initialiser(0)

end

Le type de machine sémaphore comporte les opérations :

procedure initialiser(I); obs (integer) I

procedure p

procedure v

et est spécifié pour toute machine X du type sémaphore par :

• une seule action initialiser peut s'exécuter ; soit $i_o$ la valeur du
paramètre I ; aucune action p ou v ne peut se terminer avant que cette
action ne soit elle même terminée ;

• toute action v se termine au bout d'un temps fini ;

• si n actions p commencent à la date $\phi$, k d'entre elles (pour $i \le k \le n$) se terminent au bout d'un temps fini _si et seulement si_ il existe une date $\psi \ge \phi$ telle que si nv désigne le nombre d'actions v de $X.S(\psi)$ et np le nombre d'actions p de $X.S(\phi)$, alors :

$i_o + nv - np \geq k.$

On trouvera une justification de cette représentation de la machine de
production-consommation dans [Crocus 75].
## 2.2 Spécification informelle du STR.

Le schéma général du STR est le suivant :

<figure><img src="image_9.png" /></figure>

On considère dans ce paragraphe 2 que le comportement des processus JOUEURᵢ et UNIVERS est une donnée qui sera justifiée dans le paragraphe 3.

### 2.21 Processus JOUEURᵢ (1≤i≤n).

Contrairement au processus UNIVERS, le processus séquentiel JOUEURᵢ n'est pas programmé. On représente toutefois son comportement au moyen d'un algorithme. Quel que soit le type d'interaction envisagé, le joueur se manifeste uniquement par l'émission de messages. L'émission d'un message se décompose en la succession des transformations suivantes :

**appeler** STR et attendre sa réponse pour commencer l'émission du message proprement dite ;

composer le message et le **transmettre**

d'où

```
process JOUEURᵢ ;
begin
repeat
    begin
        appeler ;
        transmettre
    end
end
```
2.22 *Processus* UNIVERS.

Soient t et t' deux instants consécutifs de *I* (voir paragraphe 1)
u et u' les situations correspondantes de *U*. Le passage de u à u' résulte
de la succession des transformations suivantes :

sortir l'heure (t') sur l'ensemble des terminaux ;

enregistrer les messages (corrects) émis par les joueurs entre
t et t';

faire **évoluer** la situation de *U* de u à u' compte tenu de ces
messages.

Cette succession de transformations est répétée pour toute paire d'instants
t, t' de *I*. D'où :

process UNIVERS ;

begin

repeat

begin

HORLOGE.attendre ;

sortir ;

enregistrer ;

évoluer

end

end

où HORLOGE est une machine servant à synchroniser (voir paragraphe 1.4) les
JOUEURᵢ et l'UNIVERS dont les vitesses d'évolution dans le temps physique
sont sans relation. Seuls les messages corrects parviennent à l'UNIVERS. Les
messages émis par les JOUEURᵢ sont donc compilés dans STR₁, ce qui permet de
les filtrer.

2.23 *Relation entre les processus.*

On considère la séquence $M_i$ des messages transmis par le JOUEUR$_i$ entre
les sorties respectives des dates t et t' sur son terminal. On se fixe pour
objectifs qu'une partie puisse être reconstituée à partir de ce qui est
imprimé sur l'ensemble des terminaux. Ceci est le cas si on adopte un procédé
de synchronisation soumis aux contraintes explicitées au paragraphe 1.4.

<figure><img src="image_10.png" /></figure>
Ce procédé consiste en ce que tout message transmis au cours d'une action transmettre terminée avant sortir (t') (et après sortir (t)) soit enregistré au cours de l'action enregistrer immédiatement consécutive (voir schéma ci-dessus). Plus généralement, si on considère la séquence $M_1$ des messages transmis par le JOUEUR$_i$ entre les sorties respectives des dates t et t', il suffit que l'enregistrement exécuté par le processus UNIVERS entre les sorties de ces dates prenne en compte tous les messages corrects des séquences $M_1, ..., M_i, ..., M_n$ et aucun autre. On impose de plus que la prise en compte des messages de chaque séquence $M_i$ émise soit faite dans l'ordre de cette séquence.

## 2.3. Décomposition du système STR.

### 2.3.1 Etude de la communication entre les joueurs et le système.

Chaque JOUEUR$_i$ communique avec STR par l'intermédiaire d'un terminal physique TTY$_i$. Le traitement des actions que JOUEUR$_i$ adresse est assuré par une machine TERMINAL$_i$ qui lui est associée (si on avait une seule machine TERMINAL pour tous les TTY$_i$, un seul JOUEUR à la fois pourrait communiquer avec le système, ce qui n'est pas acceptable). Les opérations de TERMINAL$_i$ sont :

- appeler,

- transmettre(m), où m est le message à transmettre,

- sortir(m), où m est le message à sortir.

Deux actions quelconques sortir ou transmettre sont disjointes dans le temps physique. Les processus utilisateurs de la machine TERMINAL$_i$ doivent toujours faire précéder une invocation de sortir ou transmettre d'une invocation de appeler. On aura par exemple :

<figure><img src="image_11.png" /></figure>

où a est mis pour appeler, s pour sortir et t pour transmettre.
<figure><img src="image_12.png" /></figure>

Les messages transmis à TERMINALᵢ doivent être retransmis à STR₂.

2.32 Etude des sorties ordonnées par le processus UNIVERS.

Le processus UNIVERS commande la sortie :

de l'heure t,

de renseignements concernant sa situation u.

Une première solution est que UNIVERS adresse directement ces sorties à chaque TERMINALᵢ. Si une transmission est en cours dans TERMINALᵢ, il doit alors attendre qu'elle soit terminée (voir paragraphe précédent), ce qui peut être très long eu égard à la vitesse de frappe des joueurs. Cette solution doit donc être rejetée, pour ne pas gêner l'UNIVERS dans sa principale fonction qui est de faire à temps les calculs de simulation (évoluer).

On va donc faire adresser ces sorties par un processus PORTIERᵢ pour chaque JOUEURᵢ. La relation entre l'UNIVERS et chaque PORTIERᵢ est une relation de production-consommation de messages assurée par une machine DEPARTᵢ (voir paragraphe 2.14) d'où :

```
process PORTIERᵢ;
begin
    var(message) M;
    repeat
        begin
            DEPARTᵢ.retirer(M);
            TERMINALᵢ.appeler;
            TERMINALᵢ.sortir(M)
        end
    end
```
On a choisi d'avoir un PORTIER par JOUEUR pour assurer le plus de parallélisme possible entre les sorties.

<figure><img src="image_13.png" /></figure>

### 2.33 Compilation des messages.

Les messages émis par le JOUEUR$_{i}$ doivent être compilés pour être reconnus corrects. On pourrait intégrer la compilation dans l'enregistrement : il n'y aurait à ce moment là aucune compilation pendant que le processus UNIVERS est entre le début et la fin de HORLOGE.attendre,ce qui retarderait la sortie des diagnostics d'erreurs, etc... Cette solution est donc écartée au profit de celle qui consiste à faire faire la compilation par un processus appelé COMPILATEUR. On pourrait avoir un processus COMPILATEUR pour chaque JOUEUR. Cette possibilité est abandonnée parce qu'il n'y a qu'une unité de calcul disponible donc aucune chance de faire des compilations en parallèle.

La compilation d'un message correct en provenance du JOUEUR$_{i}$ produit un événement. On précisera ultérieurement ce qu'est un événement. Le COMPILATEUR produit donc des événements dans un certain ordre et l'UNIVERS les consomme dans le même ordre au cours de l'enregistrement. La relation entre le COMPILATEUR et l'UNIVERS est donc une relation de production-consommation d'événements assurée par une machine TRAVAUX (voir paragraphe 2.14).
Les messages transmis par le JOUEUR_i sont adressés au COMPILATEUR sous la forme de missives (contenant le message transmis et l'identité i de JOUEUR_i) par l'intermédiaire d'une machine ARRIVEES. En première approximation, il s'agit d'une machine de production-consommation de missives. Soit x un message transmis par JOUEUR_i par l'action TERMINAL_i. transmettre(x) et y la missive constituée à partir de x et i. Pour faire parvenir y au COMPILATEUR, il faut que l'action précédente entraîne l'action ARRIVEES.envoyer(y). Le COMPILATEUR obtiendra y par une action ARRIVEES.retirer(y). Pour que l'ordre dans lequel le JOUEUR_i transmet ses messages soit conservé, on impose que l'intervalle de l'action ARRIVEES.envoyer(y) soit inclus dans celui de l'action correspondante TERMINAL_i.transmettre(x). D'où la décomposition de STR₃ :

<figure><img src="image_14.png" /></figure>
avec pour le COMPILATEUR :

`process COMPILATEUR ;`

`begin`

`var(missive) M; var(evenement)E;`

`repeat`

`begin`

`ARRIVEES.retirer(M);`

compiler M, ce qui entraîne dans le cas où M est correcte,
une action. TRAVAUX.envoyer(E)

où E est l'événement engendré par la compilation de M et dans le
cas où M est incorrecte, une action

`DEPART_i.envoyer(diagnostic d'erreur) où i est l'identité du JOUEUR_i qui a envoyé la missive.`

`end`

`end`

## 2.34 Décomposition de l'enregistrement.

L'enregistrement associé à la date t' ne doit prendre en compte que la séquence des événements résultant de la compilation des séquences $M_1, ..., M_n$ (voir paragraphe 2.3). Cette contrainte n'est pas respectée par le découpage tel qu'il est défini ci-dessus. En effet, lors de l'enregistrement, on ne dispose d'aucune information permettant de savoir si un événement qu'on retire de TRAVAUX appartient ou non à la séquence précédente. Et même si on disposait d'une telle information, on ignorerait encore si on a retiré tous les événements de cette séquence.

La solution adoptée est la suivante :
on sépare les messages de $M_i(t, t')$ de ceux de $M_i(t', t'')$ par un message particulier appelé `message-heure(t')`. La séquence des messages transmis par le JOUEUR_i est donc découpée de la façon suivante :

<figure><img src="image_15.png" /></figure>
Pour obtenir cette séparation, il suffit que l'action `TERMINAL_i.sortir(x)` où x est le message-heure(t'), entraîne l'action `ARRIVEES.envoyer(y)` où y est la missive-heure constituée à partir de x et i. On sait que les actions sortir et transmettre sont toutes disjointes (paragraphe 2.31). Si l'intervalle de l'action `ARRIVEES.envoyer(y)` est inclus dans celui de l'action `TERMINAL_i.sortir(x)` correspondante alors l'ordre de _toutes_ les missives en provenance de `TERMINAL` sera conservé comme le schéma ci-dessous le montre dans un cas particulier.

<figure><img src="image_16.png" /></figure>

Dans ce schéma $t_1$ et $t_4$ sont des actions transmettre, $s_3$ est une sortie de message-heure, $e_1$ et $e_4$ sont les actions envoyer correspondant à $t_1$ et $t_4$, $e_3$ est l'action envoyer (missive-heure) correspondant à $s_3$, $s_2$ une action sortir quelconque.

Avec ce procédé, $STR_3$ est en mesure de sélectionner les messages appartenant aux $M_i(t,t')$ et de les compiler. Lorsque tous ces messages (et aucun autre) sont compilés, $STR_3$ envoie un événement particulier appelé événement-heure à UNIVERS (via TRAVAUX). L'enregistrement se décompose donc en :
var(événement) E ;
repeat

begin

TRAVAUX.retirer(E) ;
traiter E

end
until E est un événement-heure
end

## 2.35 Sélection des messages dans ARRIVEES.

Soit $M(t,t')$ la collection des missives issues de tous les $M_i(t,t')$, et $M(t',t'')$ celle des missives issues de tous les $M_i(t',t'')$. La machine ARRIVEES n'est pas exactement une machine de production-consommation. En effet soit $x$ un message de $M_i(t,t')$, $x'$ un message de $M_j(t',t'')$, y et $y'$ les missives correspondantes. Les intervalles des actions ARRIVEES.envoyer($y$) et ARRIVEES.envoyer($y'$) sont sans relation. En particulier la seconde peut se terminer avant la première comme le montre le schéma suivant :

<figure><img src="image_17.png" /></figure>

Dans ce schéma $s_1$ est une action sortir(message-heure(t')), $s_4$ une action sortir(message-heure_i(t')), $t_2$ est l'action transmettre(x'), $t_3$ l'action transmettre(x), $e_1$, $e_2$, $e_3$, $e_4$ les actions envoyer correspondant respectivement à $s_1$, $t_2$, $t_3$ et $s_4$. On constate que $e_3$ se termine après $e_2$.
La machine ARRIVEES doit donc séparer les messages des $M_i(t,t')$ de ceux des $M_j(t', t'')$ de telle façon que le COMPILATEUR commence par retirer toutes les missives de $M(t,t')$. Le COMPILATEUR sait qu'il a retiré toutes les missives de $M(t,t')$ lorsqu'il retire une missive-heure. La "fusion" des missives-heure$_i(t')$ en une seule est à la charge de la machine ARRIVEES. Lorsque le COMPILATEUR a retiré cette missive-heure, il peut envoyer un événement-heure dans TRAVAUX et entamer la compilation de $M(t',t'')$.

2.36 Schéma récapitulatif

<figure><img src="image_18.png" /></figure>
## 2.37 Types utilisés

Un certain nombre de types non spécifiés ont été utilisés dans ce qui précède, à savoir identité, message, missive et événement. La signification de ces types est intuitive. On peut néanmoins récapituler les éléments de leur modèle ou de leur spécification qui sont actuellement fixés.

<table><thead><tr><td>Type</td><td>spécification (partielle)</td></tr></thead><tbody><tr><td>Identité</td><td>L'ensemble des valeurs possibles est {1, 2, ... n}.</td></tr><tr><td>Message</td><td>On sait copier un message dans un autre message et déterminer si un message est un message-heure ou non.</td></tr><tr><td>Missive</td><td>On sait constituer une missive à partir d'un message et d'une identité ; on sait copier une missive dans une autre missive ; on sait déterminer si une missive est une missive-heure ou non.</td></tr><tr><td>Evénement</td><td>On sait copier un événement dans un autre événement et déterminer si un événement est un événement-heure ou non.</td></tr></tbody></table>
# SOMMAIRE

## NOTATIONS.

### 3 COMPORTEMENT DU PROCESSUS UNIVERS :

3.1 Etude de l'exemple du jeu d'entreprise ;

3.2 Relation entre l'univers simulé et le processus UNIVERS ;

2.2 Représentation d'une évolution :

3.31 Généralités ;

3.32 Représentation d'un calcul dans le cas du jeu d'entreprise;

3.33 Représentation d'un calcul dans le cas général ;

3.4 Retour sur la représentation de l'enregistrement ;

3.5 Récapitulation.

## NOTATIONS

Outre les notations des paragraphes 1 et 2 on emploie dans ce paragraphe la collection suivante de caractères (éventuellement ornés d'indices, d'apostrophes,...) :

A ensemble des avenirs a possibles,

d date dans T,

E ensemble des événements e possibles,

F ensemble des applications de U dans U,

P ensemble de tous les présents p possibles,

S ensemble (inclus dans T) des dates de tous les événements d'une partie,

U = P x A, ensemble des situations possibles u = (p,a) de l'univers simulé ; on notera u.présent=p et u.avenir=a les composantes d'une valeur u dans U.
### 3 COMPORTEMENT DU PROCESSUS UNIVERS.

Dans le paragraphe 1, on a introduit l'univers $U$ d'un jeu conversationnel. Dans le paragraphe 2, on a fait intervenir un processus UNIVERS dont le rôle est de simuler le comportement de $U$. L'objet du présent paragraphe est d'expliciter la relation entre l'évolution de $U$ dans son temps $T$ et le comportement de UNIVERS. On continue à utiliser l'exemple du jeu d'entreprises cité dans le paragraphe 1 pour introduire les notions utiles que l'on généralise ensuite.

#### 3.1 Etude de l'exemple du jeu d'entreprise.

L'évolution de $U$ est dans ce cas celle des entreprises et du marché. Dans ce qui suit nous laissons de côté le marché.

Une entreprise est caractérisée à un instant $t$ par cinq grandeurs qui sont :

* stock($t$),
* encaisse($t$),
* prix($t$),
* taux($t$),

déjà définies au paragraphe 1.2, et la grandeur booléenne :

* vif($t$),

égale à true à la date $t$ si et seulement si l'entreprise considérée n'est pas éliminée de la partie à cette date.

Soient $t$ et $t'$ deux instants de $T$ tels qu'il n'intervient aucune interaction dans l'intervalle $]t, t']$. L'évolution de l'entreprise entre $t$ et $t'$ est traduite par les équations suivantes :

* stock($t'$) = stock($t$) + ($t' - t$) x taux($t$),
* encaisse($t'$) = encaisse($t$) - ($t' - t$) x taux($t$) x coût,

les autres grandeurs restant constantes.

Une décision concernant l'entreprise et intervenant à la date $t$ entraîne, d'après la règle du jeu, un changement de valeur du prix ou du taux à cette date.

Chaque fois que la grandeur taux est ainsi modifiée, on peut définir une date $t_e(t)$ à laquelle l'entreprise sera éliminée si aucune décision n'intervient d'ici là. On rappelle qu'une entreprise est éliminée en particulier lorsque son encaisse devient négative.
<figure><img src="image_19.png" /></figure>

Si une livraison intervient à la date $t_1 < t_e(t)$, l'encaisse est augmentée à $t_1$ ce qui déterminé une nouvelle valeur $t_e(t_1)$ à laquelle l'entreprise risque d'être éliminée (voir figure ci-dessus).

L'acceptation d'une commande k, caractérisée par les trois grandeurs :

k.quantité : quantité de papier à livrer,

k.prix d'achat : prix auquel sera payé le papier livré,

k.date : date de la livraison,

oblige le chef de l'entreprise concernée à livrer la quantité de papier k.quantité à la date k.date.

Soit un intervalle $[t, t']$ de $T$ dans lequel il n'intervient aucune autre interaction qu'un certain nombre de commandes qui doivent être acquittées à la date $t'$. L'évolution de l'entreprise entre $t$ et $t'$ est alors traduite par les équations :

$$ \text{stock}(t') = \text{stock}(t) + (t'-t) \times \text{taux}(t) - \text{livraison}(t'), $$

$$ \text{encaisse}(t') = \text{encaisse}(t) - (t'-t) \times \text{taux}(t) \times \text{coût} + \text{revenu}(t'), $$

dans lesquelles :

$$ \text{livraison}(t') = \sum_{k:k.date=t'} \text{k.quantité}, $$

$$ \text{revenu}(t') = \sum_{k:k.date=t'} \text{k.quantité} \times \text{k.prix d'achat}. $$
Dans le cas où stock(t') est négatif, l'entreprise est éliminée de la
partie à la date t'.

L'instant $t_e$ où l'entreprise est éliminée peut ne pas coïncider avec
un instant de $I$.

Il ne suffit donc pas de connaître la situation de l'univers aux
instants de $I$ pour reconstituer une partie. Il n'est pas pour autant
nécessaire de connaître cet état à tous les instants de $T$ puisque le
comportement d'une entreprise est déterministe dans tout intervalle où
n'intervient aucune interaction. On appelle $S$ le sous-ensemble
minimal (contenant $I$) de $T$ aux instants duquel il est nécessaire de
connaître la situation de $U$ pour reconstituer une partie.

On appelle **événement concernant une entreprise à une date t de S** :

une interaction intervenant à la date t et la concernant,

l'éventualité de son élimination à la date t.

La situation d'un joueur est caractérisée par les six grandeurs
date, stock, encaisse, prix, taux, vif, qui sont liées par les
relations :

situation.date = t,
situation.stock = stock(t),
situation.encaisse = encaisse(t),
situation.prix = prix(t),
situation.taux = taux(t),
situation.vif = vif(t).

Pour reconstituer une partie, on a vu qu'il n'est pas nécessaire de
connaître la situation de tous les joueurs à tous les instants de $T$,
mais seulement à ceux de $S$. En fait il n'est même pas nécessaire de
connaître la situation de tous les joueurs à tout instant de $S$. En
effet, soient $d, d', d''$ trois instants consécutifs de $S$. Supposons
qu'à la date $d'$, il n'y ait aucun événement concernant l'entreprise
d'un certain joueur $J$. Il n'est pas utile de calculer la situation de
$J$ à la date $d'$ pour deux raisons :

la situation de tous les autres joueurs est indépendante de
celle de $J$ dans l'intervalle $]d, d''[$ ;

on est capable de calculer la situation de $J$ à tout instant
de l'intervalle $]d, d''[$ à partir de sa situation à la date $d$.
Dans le schéma suivant, on a marqué d'un point . sur un premier axe T les dates des événements concernant l'entreprise J. On a fait de même pour l'entreprise K sur un second axe. Si J et K sont les seules entreprises du jeu, on en déduit S sur le troisième axe.

<figure><img src="image_20.png" /></figure>

De façon générale S est l'ensemble des instants de T pour lesquels il y a au moins une entreprise concernée par un événement.

## 3.2 Relation entre l'univers simulé et le processus UNIVERS.

L'univers U est représenté par une collection d'**objets** existant en permanence. Dans le cas du jeu d'entreprise ces objets sont les entreprises, et le marché. Chaque objet est décrit par sa **situation** qui comporte une date et la valeur de certaines grandeurs (caractéristiques de cet objet à cette date). Ce que l'on a appelé situation de l'univers dans le paragraphe 1 est en première approximation la collection des situations de ces objets. Soient t et t' deux instants consécutifs de I, u et u' les situations correspondantes de U. On va expliquer comment on passe de (t, u) à (t', u').

D'après le paragraphe 1.4 il existe une fonction appelée successeur telle que :

$t' = \text{successeur}(t, u).$

Par contre, pour calculer $u'$, il ne suffit pas de connaître $t$ et $u$ ; il faut en plus connaître tous les événements intervenant dans l'intervalle $[t, t']$. Il y a deux sortes de tels événements :

* ceux qui résultent d'interactions (voir paragraphe 1.3),

* ceux qui sont la conséquence de l'évolution d'un objet de U.

On appelle S l'ensemble des instants auxquels intervient au moins un événement. Un événement est toujours "connu" avant qu'il intervienne. On définit donc la situation de U à un instant d de S comme étant la collection des situations des objets de U (qu'on appelle le **présent**) à laquelle on adjoint la collection (qu'on appelle avenir) des événements connus à d et dont on sait qu'ils vont intervenir à une date supérieure à d.
Remarque : en généralisant ce qui a été dit au paragraphe précédent, il n'est pas nécessaire que la situation d'un objet de U soit calculée à tout instant de S.

La transformation qui permet de passer de u à u' est donc décomposée en deux transformations :

• la première qu'on appelle enregistrement transforme u en $u_1$ qui diffère de u par le fait qu'il contient en particulier toutes les interactions intervenant jusqu'à t' ;

• la deuxième qu'on appelle évolution transforme $u_1$ en $u'$ ; elle est déterministe en ce sens que le procédé qui permet de calculer $u'$ à partir de $u_1$ et de $t'$ ne dépend d'aucune autre grandeur ; en ce sens l'enregistrement, lui, n'est pas déterministe.

Cette décomposition est résumée par le schéma suivant :

<figure><img src="image_21.png" /></figure>

Pour une partie donnée, la transformation de la situation initiale $u_0$ en la situation finale $u_∞$ se décompose donc en une séquence de transformations :

enregistrement ; évolution ; enregistrement ;... évolution dont la définition résulte de la donnée de *I* et des interactions qui interviennent au cours de la partie.

Ceci justifie la forme du processus UNIVERS donnée au paragraphe 2.22, que l'on peut compléter compte-tenu de ce qui vient d'être dit :
process UNIVERS ;

begin

var U ; var(date) DATE EXTERIEURE ;

repeat

begin

comment DATE EXTERIEURE = t' ;

HORLOGE.attendre ;

comment U = u ;

sortir ;

comment la valeur de DATE EXTERIEURE a été

communiquée à tous les joueurs ;

enregistrer ;

comment U = u_1 ;

évoluer ;

comment U = u' ;

DATE EXTERIEURE := successeur (DATE EXTERIEURE, U)

end

end

où les variables U et DATE EXTERIEURE contiennent respectivement la
situation de l'univers du jeu et la date. En effet, d'après le paragraphe
2.34, enregistrer revient à prendre en compte les messages émis par les
JOUEUR_i entre les sorties respectives des dates t et t'. Les messages
sont les supports des interactions, donc lorsque l'enregistrement est
terminé, toutes les interactions intervenant jusqu'à t' sont connues :
la variable U est dans l'état u_1.

On a vu dans le paragraphe 2.34 que l'enregistrement est représenté
par l'algorithme :

enregistrer : begin

var(événement) E ;

repeat

begin

TRAVAUX retirer(E) ;

traiter E

end

until E est un événement-heure

end
L'opération traiter consiste en première approximation à adjoindre
l'événement e à la composante avenir de U. En particulier, l'événement-
heure correspondant à t' est dans $u_1$.avenir.

3.3 Représentation d'une évolution.

3.31 Généralités.

L'évolution transforme $u_1$ en $u'$. On sait que $u_1$.avenir = $a_1$
contient au moins :

. l'événement-heure correspondant à t',

. tous les événements issus d'interactions intervenant entre t et t'.

Il existe donc dans $a_1$ au moins un événement de date d inférieure ou
égale à t'. Soit $t_2$ la plus petite date d possible ($t<t_2\le t'$) : $t_2$ =
prochaine date ($a_1$). On peut calculer la situation $u_2$ de l'univers à
$t_2$ à partir de $u_1$ et de $t_1 = t$ par le procédé suivant. On détermine à
partir de l'ensemble de tous les événements de date $t_2$ contenus dans $a_1$
une fonction calcul_2 : $U\to U$, et on applique calcul_2 à $u_1$ pour obtenir
$u_2$, ce qui se résume par :

$$
\text{calcul}_2 = \text{extraction}(a_1),
$$

$$
u_2 = \text{calcul}_2(u_1).
$$

On peut répéter ce procédé et construire les suites :

$$
t_{j+1} = \text{prochaine date}(a_j),
$$

$$
\mathrm{calcul}_{j+1} = \mathrm{extraction}(a_j),
$$

$$
u_{j+1} = \mathrm{calcul}(u_j), \text{ pour } j = 1, 2, \dots
$$

La suite $t_j = t, t_2, \dots, t_j, \dots$ se termine en t' puisque $a_1$ contient
l'événement-heure correspondant à t'. D'où le schéma :

<figure><img src="image_22.png" /></figure>
Remarque : La fonction extraction est la même quel que soit l'instant $t_j$ considéré alors que la fonction calcul change à chaque instant $t_j$.

L'évolution est donc représentée par l'algorithme :

évoluer : repeat

begin

var(date) D;

fixer la date courante dans D;

calculer

end

until DATE EXTERIEURE = D

avec pour les opérations qui y apparaissent les spécifications :

U=(p,a) {calculer} U=(p',a')=extraction(a)(p,a)

U=(p,a) {fixer la date courante dans D} U=(p,a) & D=prochaine date(a).

### 3.32 Représentation d'un calcul dans le cas du jeu d'entreprise.

On se propose de dire dans ce paragraphe ce qu'est le calcul de la situation de l'univers du jeu d'entreprise à une date d'appartenant à la suite $t_1,t_2,...,t_j,...,t'$. Pour ce faire on associe à chaque type d'événement qui peut influer sur la situation d'une entreprise une fonction qui exprime la relation entre les situations qu'elle avait respectivement avant et après que cet événement intervienne. Le calcul est en première approximation obtenu par composition des fonctions associées aux événements intervenant à la date d.

Considérons les événements qui peuvent influer sur la situation de l'entreprise à la date d :

* l'élimination,

* des livraisons,

* l'acceptation ou le refus d'une commande,

* le changement du taux ou du prix.

On n'examine dans ce qui suit que les deux premiers types d'événements.

### 3.32.1 Traitement d'une élimination.

D'après le paragraphe 3.1, une entreprise est éliminée à la date d lorsque son encaisse devient négative à cette date ; ce qui se traduit par la condition :

encaisse(d) <o | (encaisse(d)=o & taux(d)>o)

dont le deuxième terme exprime que l'encaisse va devenir négative immédiatement après d (voir le schéma ci-dessous).
<figure><img src="image_23.png" /></figure>

Entre l'instant où la date d'élimination a été calculée et d, il a pu intervenir des événements (modification du taux) qui font que l'entreprise ne sera pas éliminée à d. Pour déterminer si l'élimination a lieu ou non, il faut calculer la situation de l'entreprise à d. Si on suppose qu'aucun autre événement concernant l'entreprise n'intervient à d, il existe entre la situation s' de l'entreprise à cet instant d et sa situation antérieure s une relation que l'on note :

$$s' = h_e(d)(s)$$

et qui est définie dans le cas où s.vif=false par s'=s et dans l'autre cas par :

$$ 
\begin{align*}
s'.date&=d, \\
s'.stock&=s.stock+(d-s.date) \times s.taux, \\
s'.encaisse&=s.encaisse-(d)s.date) \times s.taux \times \text{coût}, \\
s'.prix&=s.prix, \\
s'.taux&=s.taux, \\
s'.vif&= (s'.encaisse<0 | (c'.encaisse=0 & s'.taux>0)).
\end{align*} $$

L'entreprise est éliminée à la date d si et seulement si on a $s'.vif=false$.

### 3.322 Traitement d'une livraison.

Supposons qu'une livraison par l'entreprise doive intervenir à la date d et qu'aucun autre événement concernant cette entreprise n'intervient à d.

Il existe alors entre la situation s' de l'entreprise à cet instant d et sa situation antérieure s une relation que l'on note :
$s'=h_1(d,k)(s)$

et qui est définie dans le cas où $s.vif=false$ par $s'=s$ et dans l'autre cas par :

```
s'.date=d,
s'.stock=s.stock+(d-s.date) x s.taux - k.quantité,
s'.encaisse=s.encaisse-(d-s.date) x s.taux x coût + k.quantité
x k.prixdachat,
s'.prix=s.prix,
s'.taux=s.taux,
s'.vif=(s'.stock≥0).
```

Le seul cas d'élimination à envisager est celui où la livraison est impossible ($s'.stock<0$). En effet, l'encaisse n'a pas pu devenir négative dans l'intervalle $s.date,d$, sinon il y aurait eu un événement (élimination) concernant cette entreprise à un instant $t_e$ de cet intervalle (voir schéma) et on a donc $s'.encaisse>0$.

<figure><img src="image_24.png" /></figure>

### 3.323 Superposition des événements.

Dans le cas où plusieurs événements concernant une même entreprise interviennent simultanément à la date d, le calcul de la situation de cette entreprise à d résulte de la composition des fonctions associées à ces événements. Toutefois, dans le cas où un événement élimination intervient à d il faut appliquer la fonction correspondante avant toute autre. Cela veut dire que l'ensemble des événements concernant une
entreprise et intervenant à une même date est partiellement ordonné.
On suppose dans la suite l'existence d'un critère permettant d'ordonner
les événements qui interviennent à une même date.

### 3.33 Représentation d'un calcul dans le cas général.

On fait sur l'ensemble E des événements possibles e les hypothèses
suivantes :

• il existe une fonction date : $E \to T$ partout définie, qui à tout événement e fait correspondre la date à laquelle il doit intervenir et qu'on note e.date ;

• il existe une relation d'ordre partiel sur E permettant de
comparer deux événements $e_1$ et $e_2$ de même date, relation que l'on
note $e_1 < e_2$ lorsque $e_1$ doit intervenir avant $e_2$ ;

• il existe une fonction invocation : $E \to F$ partout définie qui à tout événement e fait correspondre une fonction $f=e-invocation$ ; cette fonction f permet d'exprimer la relation entre les situations de l'univers U avant et après l'intervention de l'événement.

On fait maintenant sur l'ensemble A des avenirs a possibles les
hypothèses suivantes :

• a est une collection ordonnée d'événements ;

• la fonction prochaine date : $A \to T$ est telle que prochaine date(a) est la plus petite date d telle qu'il existe un événement de date d dans a ;

• il existe une fonction prochain : $A \to E$ telle que prochain(a) est le premier événement (au sens de la relation d'ordre sur E) de date égale à prochaine date(a) ;

• il existe une fonction vide : $A \times T \to \{\text{true},\text{false}\}$ telle que
$vide(a,d) = \text{true}$ si a ne contient aucun événement de date d
$\underline{false}$ autrement ;

• il existe une fonction adjonction : $A \times E \to A$ telle que adjonction(a,e) est en première approximation la réunion de a et de l'événement e ;

• il existe une fonction reste : $A \to A$ telle que :
$a = \text{adjonction}(\text{reste}(a), \text{prochain}(a))$

On est maintenant en mesure de représenter l'opération calculer
introduite au paragraphe 3.31. Pour cela on remplace la variable U par
deux variables P et A ayant pour valeurs respectives le présent et
l'avenir. L'algorithme de calculer est alors :
calculer : begin
var(événement)E ;
repeat
begin
A.retirer(E) ;
déclencher E
end
until A.vide(D)

Où les opérations retirer, déclencher, vide sont spécifiées par :

A=a & a non vide {A.retirer(E)} A=reste(a) & E=prochain(a)

A=a & D=d {A.vide(D)} A.vide(D)=vide(a,d)

P=p & A=a & E=e {déclencher E} (P,A)=e.invocation(p,a).

Remarque : la précondition a non vide est vérifiée la première fois que l'on entre dans la boucle calculer puisqu'alors a contient au moins un événement-heure, et les fois suivantes puisque a.vide(D)=false implique a non vide.

### 3.4 Retour sur la représentation de l'enregistrement.

Compte-tenu de l'introduction de la variable A, la représentation de l'enregistrement explicitée dans le paragraphe 2.34 se réécrit :

enregistrer:begin
var(événement) E ;
repeat
begin
TRAVAUX.retirer(E) ;
A.adjoindre(E)
end
until E est un événement-heure
end

où ranger est une opération spécifiée par :

A=a & E=e {A.adjoindre(E)} A=adjonction(a,e).
3.5 Récapitulation.

process UNIVERS ;
begin

var P ;

var A ;

var(événement) E ;

var(date) DATE EXTERIEURE,D ;

repeat

begin

comment DATE EXTERIEURE = t' ;

HORLOGE.attendre ;

comment U = u ;

sortir ;

comment la valeur de DATE EXTERIEURE a été communiquée à
tous les joueurs ;

enregistrer : repeat

begin

TRAVALX.retirer(E) ;

A.ranger(E)

end

until E est un événement-heure ;

comment U = u₁ ;

évoluer:repeat

begin

fixer la date courante dans D ;

calculer:repeat

begin

A.retirer(E) ;

déclencher E

end

until A.vide(D)

end

until DATE EXTERIEURE = D ;

comment U = u' ;

DATE EXTERIEURE:=successeur(DATE EXTERIEURE,P,A)

end

end.
# SOMMAIRE

## PREAMBULE.

## 4 REPRESENTATION DES TYPES DU PROCESSUS UNIVERS.

### 4.1 Notions utilisées.

### 4.2 Rappels des spécifications des types utilisés :

4.21 Type date ;

4.22 Type événement ;

4.23 Type avenir.

### 4.3 Représentation du type avenir :

4.31 Idée directrice ;

4.32 Abstraction et invariant de la représentation ;

4.33 Représentation des opérations ;

4.34 Vérification de conformité.

### 4.4 Représentation du type tranche.

### 4.5 Notes de réalisation.

## PREAMBULE

Ce paragraphe rappelle la spécification des types utilisés dans l'algorithme qui décrit le comportement du processus UNIVERS (voir paragraphe 3) et décrit la représentation du type avenir. Il en envisage enfin des réalisations possibles.
## 4.1 Notions utilisées.

Dans ce qui suit on utilise fréquemment des types ne possédant comme opérations que l'assignation et le test de l'égalité. Pour ces types on ne donnera en fait de spécification que l'ensemble des valeurs possibles et éventuellement la valeur initiale, le reste étant évident.

On utilise comme opérateur de composition particulier une boucle "while" généralisée, la répétition étant commandée par l'évaluation d'une condition pouvant prendre une parmi un nombre fini $k \ge 2$ de valeurs distinctes. Cette boucle se note :

```pascal
S : repeat case C of
    c₁:S₁ or
    ...
    cₖ:Sₖ
```

où $c_1, \dots, c_k$ sont les valeurs possibles de C et $S_1, \dots, S_k$ sont soit des instructions composées (forme 1), soit de la forme :

```
begin instruction composée ; exit end,
1'instruction exit commandant la sortie de boucle (forme 2).
Pour que la transformation de prédicat
```

```
P {S} Q
```

soit vérifiée il suffit de vérifier :

* pour tout $c_i$ correspondant à une instruction $S_i$ de la forme 1,

```
P & C=cᵢ {Sᵢ} P
```

* pour tout $c_j$ correspondant à une instruction $S_j$ de la forme 2, soit `begin S'j; exit end`

```
P & C=cⱼ {S'ⱼ} Q.
```

Pour vérifier la terminaison de cette boucle il suffit de trouver une fonction minorée (de la valeur des variables manipulées par S) que chacune des instructions $S_i$ de la forme 1 fait strictement décroître.

La boucle "while" ordinaire se ramène à $k=2, c₁=true, c₂=false, S₁ quelconque et S'₂ vide.
Dans la vérification d'un algorithme, il est commode lorsque l'on rencontre une instruction d'assignation, d'appliquer la règle de substitution des variables assignées que l'on peut énoncer ainsi :

pour que le prédicat P portant sur les variables de l'algorithme soit vrai
après exécution de l'instruction $X:=e$ , il suffit que le prédicat $P_e^X$ (obtenu en remplaçant dans P toute occurrence de X par e) soit vrai
immédiatement avant l'exécution de cette instruction.

L'application de cette règle à une suite d'instructions d'assignation conduit à "remonter" de la dernière de ces instructions à la première. Pour conserver malgré tout la disposition des instructions on indique le sens dans lequel on a fait la vérification par une flèche ascendante (voir par exemple le paragraphe 4.35).
## 4.2 Rappel des spécifications des types utilisés.

### 4.21 Type date.

Le type date a été utilisé dans le paragraphe 3. Son modèle se compose de :

* l'ensemble de valeurs possibles $T$ (voir paragraphe 1) muni d'une relation d'ordre total notée <.

* la valeur initiale notée 0,

Sa spécification se compose des déclarations d'opérations :

l'assignation := ,

la comparaison, spécifiée par

comparaison ($T_1, T_2$) = si $T_1$ = $T_2$ alors égal

sinon si $T_1$ > $T_2$ alors supérieur
sinon inférieur

où égal, supérieur et inférieur sont trois constantes d'un même type discret.

Remarque : dans le cas où $T$ est l'ensemble des nombres réels, la réalisation de la comparaison pose des problèmes d'approximation (représentation des nombres réels dans le calculateur).

### 4.22 Type événement.

Le type événement a été introduit dans le paragraphe 2, il a été utilisé dans le paragraphe 3. On ne peut pas déterminer le modèle de ce type puisqu'on n'a pas explicité comment il était utilisé dans le COMPILATEUR. On connait néanmoins un certain nombre de fonctions de ce modèle :

* la fonction date : $E \to T$ partout définie, qui à tout événement e fait correspondre la date à laquelle il doit intervenir et qu'on note e.date;

* la relation d'ordre partiel sur $E$ permettant de comparer deux événements $e_1$ et $e_2$ de même date, relation que l'on note $e_1 < e_2$ lorsque $e_1$ doit intervenir avant $e_2$;

* la fonction invocation : $E \to F$ partout définie qui à tout événement e fait correspondre une fonction $f=e-invocation$; cette fonction f permet d'exprimer la relation entre les situations de l'univers U avant et après l'intervention de l'événement;
Une fonction de E dans {true>false} permettant de savoir si un événement est un événement-heure ou non et notée est un événement-heure.

La spécification du type événement comporte :

des déclarations d'opérations :

l'assignation := ,
obs(invocation) procedure invocation ,
obs(date) procedure date ,
obs (boolean) procedure est un événement-heure ;

les transformations de prédicat immédiatement déductibles des déclarations et des fonctions précédentes.

4.23 *Type avenir*.

Le type avenir est le type de la variable A qui est la composante avenir de la situation de l'univers.

Son modèle se compose de :

l'ensemble de valeurs possibles A = ensemble des parties finies de E,

la valeur initiale : l'ensemble vide,

les fonctions :

adjonction : $AxE \to A$ telle que $adjonction(a,e) = a \cup \{e\}$;

prochaine date : $A \to T$ telle que prochaine date(a) est la plus
petite date d telle qu'il existe un
événement de date d dans a ; lorsque a est
vide cette fonction n'est pas définie ;

prochain : $A \to E$ telle que prochain(a) est le premier (au sens de
la relation d'ordre sur E) événement de date
égale à prochaine date(a) ;

reste : $A \to A$ telle que $a=adjonction(reste(a),prochain(a))$ ;

vide : $AxT \to \{true=false\}$ telle que vide(a,d)=true si a ne contient aucun événement de date d, false autrement.

Sa spécification comporte :

les déclarations d'opérations :

procedure adjoindre(E); obs(événement) E ,
procedure retirer(E); res(événement) E ,
obs(date) procedure prochaine date ,
obs (boolean) procedure vide(D) ; obs(date) D ;
les transformations de prédicats :

A=a & F=e {A.adjoindre(E)} A=adjonction(a,e) ;
A=a & a non vide {A.retirer(E)} E=prochain(a) & A=reste(a) ;
les spécifications des observations du type avenir se déduisent
immédiatement de leur déclaration et du modèle de ce type.

4.3 Représentation du type avenir.

4.31 Idée directrice

Pour tout avenir a dans A, on considère la partition de a en tranches
telle que deux événements e₁ et e₂ appartiennent à la même tranche si et
seulement si e₁.date=e₂.date. On appelle date d'une tranche la date de ses
événements. On note tranche l'ensemble des tranches possibles. Si x est une
tranche, on note x.date sa date.

On cherche à représenter l'avenir sous la forme d'une chaîne de tranches
ordonnées suivant leurs dates croissantes ; et ce de telle façon qu'il soit
facile de parcourir cette chaîne afin d'adjoindre un événement dans une tranche
quelconque. On choisit ce genre de représentation pour deux raisons :

. on a une relation d'ordre entre les événements de même date ;
on a donc intérêt à les regrouper pour pouvoir représenter plus
facilement la fonction prochain ;

. le découpage en tranches ordonnées suivant leurs dates croissantes
permet de représenter facilement les fonctions vide et prochaine
date.

Plus précisément, on identifie chaque tranche d'un avenir a par un indice choisi dans un ensemble noté *indice*. On matérialise l'ordre des tranches par une fonction suivant : *indice→indice* telle que si $j$=suivant($i$) :

. tranche(j).date>tranche(i).date,

. il n'existe aucune tranche de date intermédiaire.

On appelle $i_1, i_2, \dots, i_k, \dots, i_m (m \ge 0)$ la suite ordonnée des indices des tranches de $a$. Par commodité, pour parcourir cette suite, on se fixe deux éléments distincts de *indice* que l'on note alors $i_0$ et $i_{m+1}$ tels que :

suivant (i₀)=i₁,

...

suivant (iₖ)=iₖ₊₁ pour 1≤k<m

...

suivant (i<sub>m</sub>) = i<sub>m+1</sub>

suivant (i<sub>m+1</sub>) non défini.
4.32 Abstraction et invariant de la représentation.

On décide de représenter l'avenir par une collection R de variables :

existe:indice → {true, false},
tranche:indice → tranche,
date:indice → date,
suivant:indice → indice.

Une configuration possible de valeurs de R représente un avenir a lorsqu'elles vérifient les propriétés qui suivent.

1) . la fonction existe est partout définie dans indice, et toujours égale à true en dessous et en dessus ;

. le sous ensemble existe⁻¹(true) est identique à :

{i_k=suivant^k(dessous) pour 0≤k≤m+1}
avec suivant^0(dessous)=dessous, suivant^{m+1}(dessous)=dessus et suivant
(dessus) non défini.

On note $P_1$ ces propriétés.

2) . la fonction date n'est définie qu'en i₁, i₂, ... i_m et vérifie la relation :
date(iₖ) < date(iₖ+₁) pour 1≤k<m.

On note P₂ cette propriété.

3) . la fonction tranche n'est définie qu'en i₁, i₂, ... i_m et il y a entre date et tranche la relation :

date(i_k)=tranche(i_k).date pour 1≤k≤m.

On note $P_3$ cette propriété.

Ces propriétés constituent l'invariant de la représentation.

Lorsque R vérifie cet invariant, elle représente l'avenir a :

a=abstraction(R)= ⋃ tranche(i_k) pour 1≤k≤m.
Ces propriétés sont illustrées par le schéma suivant :

<figure><img src="image_25.png" /></figure>

La valeur initiale du type avenir est représentée par une configuration de R vérifiant l'invariant avec m=0 :

<figure><img src="image_26.png" /></figure>

### 4.33 Représentation des opérations.

#### 3.331 Opération adjoindre.

L'algorithme qui la représente manipule deux variables I et J de type indice, ainsi que, bien entendu, la représentation d'une variable de type avenir. Il s'écrit :

procedure adjoindre(E); obs(événement)E;
begin
    initialiser;
    repeat case situation of
        inférieur:avancer or
        égal:exit or
        supérieur:begin insérer;exit end;
    tranche(I).adjoindre(E)
end
au moyen des opérations :

initialiser : begin J:=dessous; I:=suivant(J) end

avancer : begin J:=I; I:=suivant(J) end

insérer : begin

H:=nouveau(existe);

existe(H):=true,suivant(J):=H,suivant(H):=I;

date(H):=E.date;

tranche(H):=tranche vide;

I:=suivant(J)

end

La fonction nouveau est définie par :

nouveau(existe) = si existe⁻¹(false)=1'ensemble vide
  alors non défini
  sinon h dans existe⁻¹(false)

La fonction situation, à valeurs dans {inférieur, égal, supérieur}

est définie par :

situation=si I=dessus alors supérieur
  sinon comparaison(date(I),E.date).

De par l'algorithme de adjoindre, cette fonction n'est jamais utilisée dans le
cas I=dessous.

### 4.332 Opération retirer.

L'algorithme qui la représente manipule une variable I de type indice. Il
s'écrit :

procedure retirer(E); res (événement)E;

begin

I:=suivant(dessous);

tranche(I).retirer(E);

if tranche (I) = tranche vide

then begin

suivant(dessous):=suivant(I);

existe(I):=false

end

end

### 4.333 Opération prochaine date.

obs (boolean) procedure prochaine date;

prochaine date:=date(suivant(dessous))
### 4.334 Opération vide.

L'algorithme qui la représente manipule une variable *I* de type indice. En utilisant la fonction situation rencontrée dans la représentation de l'opération adjoindre, on peut l'écrire sous la forme :

```
obs (boolean) procedure vide(D); obs (date) D;
begin
```

```
I:=suivant (dessous);
```

```
repeat case situation of
```

```
inférieur: I:=suivant(I) or
```

```
égal: begin
```

```
vide:=(tranche(I)=tranche vide);
```

```
exit
```

```
end or
```

```
supérieur: begin vide:=true; exit end
```

```
end
```

### 4.34 Spécification des types utilisés dans la représentation de avenir.

Le type indice a pour ensemble de valeurs *indice* et il est muni de l'assignation et du test de l'égalité. Le procédé de description des chaînes utilisé dans la représentation du type avenir est généralisable à n'importe quelle chaîne en remplaçant éventuellement les fonctions *date* et *tranche* par d'autres fonctions de la forme :

```
f:indice -> ...
```

On utilisera ce procédé dans la suite pour représenter le type *tranche*, en conservant les mêmes notations concernant le type *indice* et les variables *existe*, suivant, *dessous* et *dessus*. Il n'y a aucune ambiguïté sur la portée des identificateurs de ces variables donc on peut les réutiliser sans problème. En revanche jusqu'à présent on n'a jamais limité la portée d'un type. Ici il est nécessaire de limiter la portée du type *indice* à la représentation d'une chaîne particulière pour deux raisons :

* éviter les confusions lors de la réalisation en admettant que plusieurs types *indice* soient réalisés de la même façon (chaînages indésirables de chaîne à chaîne),

* garder la possibilité d'avoir des réalisations différentes pour ces différents types *indice* (notion de domaine en LIS[Ichbiah 73]).

Avec cette limitation de portée on peut envisager une vérification syntaxique du caractère biunivoque de l'association d'un type *indice* à une chaîne.
Les types des quatre variables existe, tranche, date, suivant, sont tous spécifiés de la même façon que l'on explicite comme suit. A partir de deux types quelconques donnés, notés argument et valeur, on fabrique le type fonction.
Le modèle de ce type comporte :

* comme ensemble de valeurs possibles, l'ensemble des fonctions de argument dans valeur,

* comme valeur initiale, la fonction nulle part définie dans argument.

La spécification de ce type se réduit à dire que si $F$ est une variable de type fonction et $X$ une observation de type argument, alors $F(X)$ est une variable de type valeur. C'est à dire que :

* pour toute transformation associée au type valeur :

$$F=f \ \& \ X=x \ \{F(X).transformer(...)\} \ F=f \ \text{sauf en } x \ \text{où} \\ F(x)=\text{transformation}(f(x),...)$$

* pour toute observation associée au type valeur :

$$F=f \ \& \ X=x \ \{F(X).observation(...)\} \ F(X).observation= \\ \text{observation}(f(x),...)$$

Contrairement à ce qui se passe dans le cas des tableaux, il n'est pas nécessaire de savoir énumérer explicitement les éléments de *argument*.

Ainsi existe, par exemple, est du type fonction construit à partir des types indice et boolean ; de même tranche est du type fonction construit à partir des types indice et tranche ;...

Le modèle de ce type tranche comporte :

* comme ensemble de valeurs possibles l'ensemble des sous-ensembles de $E$ d'événements de même date,

* comme valeur initiale, l'ensemble vide *tranche vide*,

* deux fonctions :

adjonction : tranche $x \in E \rightarrow$ tranche telle que :

adjonction : $(x,e) = x \cup \{e\}$,

prochain : tranche $\rightarrow E$ telle que

prochain(x) = si $x \notin$ tranche vide, le premier événement au sens de la relation d'ordre sur $E$
sinon n'est pas définie,

reste(x) = si $x \notin$ tranche vide alors $x - \{\text{prochain}(x)\}$ sinon n'est pas définie.

La spécification de ce type comporte :

* les déclarations d'opérations :

procedure adjoindre(E); obs(événement) E,

procedure retirer(E); res(événement) E,

l'assignation par la tranche vide,

le test de l'égalité à la tranche vide ;
les transformations de prédicat :

$X=x \& E=e \{X.adjoindre(E)\} X=adjonction(x,e)$

$X=x \& x \neq \underline{tranche vide} \{X.retirer(E)\} X=reste(x) \& E=prochain(x)$

## 4.35 Vérification de conformité.

On se borne ici à exposer la vérification de l'algorithme représentant l'opération adjoindre, qui est le plus compliqué.

### 4.351 Vérification complète de la boucle "repeat case".

On se propose de vérifier que le prédicat $P_0$ :

$I=suivant(J) \& existe(J) \& J \neq dessous \& inf(J)$

(en notant $inf(J)$ le prédicat : pour tout $i_k$ tel que dessous $<i_k \leq J$, on a $date(i_k) < E.date$.) est un invariant de la boucle.

Ce prédicat est évidemment vrai après initialiser. D'après la propriété de l'opérateur "repeat case" énoncée au paragraphe 4.1, il suffit donc de vérifier :

$P_0 \& situation=inférieur \{avancer\} P_0$.

En appliquant la règle de substitution, on a la suite de déductions :

<figure><img src="image_27.png" /></figure>

existe(I) & $I \neq$ dessus & inf(I)

$\{J:=I\}$

true & existe(J) & $J \neq$ dessus & inf(J)

$\{I:=suivant(J)\}$

$I=suivant(J) \& existe(J) \& J \neq$ dessus & inf(J)

Il reste donc à vérifier :

$P_0 \& situation=inférieur \text{ implique existe(I) \& } I \neq$ dessus & inf(I)

ce qui résulte de :

situation=inférieur implique $I \neq$ dessus & date(I) < E.date

D'autre part :

$P_0 \& situation=inférieur \text{ implique } I=i_k \text{ & } 0 \leq k < m+1$.

On peut donc vérifier :

$I=i_k \text{ & } 0 \leq k < m+1 \{\text{avancer}\} I=i_{k+1} \text{ & } k+1 \leq m+1$

ce qui assure la terminaison de la boucle.

## 4.352 Conservation de l'invariant de la représentation.

On rappelle que l'on a mis dans le paragraphe 4.32 cet invariant sous la forme $P_1 \& P_2 \& P_3$ , qu'on note aussi invariant.

On commence par supposer vrai le lemme suivant :
$P_0$ & situation=$\underline{supérieur}$ & invariant
{insérer}

invariant & date(I)=E.date.

On a de plus :

$P_0$ & situation=$\underline{égal}$ & invariant
{ }

invariant & date(I)=E.date

Enfin, avancer ne modifie pas les variables représentant l'avenir, donc
conserve l'invariant, et on a par suite :

$P_0$ & situation=$\underline{inférieur}$ & invariant
{avancer}

$P_0$ & invariant.

En utilisant le schéma de vérification de la boucle "repeat case" donné au
paragraphe 4.1, on déduit :

$P_0$ & invariant {repeat case ...} invariant & date(I)=E.date

Il reste donc à vérifier :

invariant & date(I)=E.date
{tranche(I).adjoindre(E)}

invariant

ce qui est évident, puisque

existe, suivant et date n'étant pas modifiés, $P_1$ et $P_2$ sont
manifestement conservés,

d'après la spécification de adjoindre :

tranche(I)=x & E=e & x.date=&date(I)=E.date
{tranche(I).adjoindre(E)}
tranche(I)=x U {e}

et par conséquent $P_3$ est conservé puisque (x U {e}).date=&date(I).

Reste à vérifier le lemme. Pour simplifier l'exposé de cette vérification on énonce les prédicats sous forme de tableaux.

Le prédicat $P_0$ & situation=$\underline{supérieur}$ & invariant se réécrit :
<table><tr><td>indice</td><td>dessous</td><td>i<sub>1</sub></td><td>...</td><td>J=i<sub>k</sub></td><td>I=i<sub>k+1</sub></td><td>...</td><td>dessus</td><td>autres</td></tr><tr><td>existe</td><td colspan="5">true</td><td colspan="3">false</td></tr><tr><td>suivant</td><td>i<sub>1</sub></td><td>i<sub>2</sub></td><td>...</td><td>i<sub>k+1</sub></td><td>...</td><td>...</td><td>non définie</td><td></td></tr><tr><td>date</td><td>non définie</td><td colspan="2">&lt; E.date</td><td colspan="2">&gt; E.date</td><td colspan="3">non définie</td></tr><tr><td>tranche</td><td>non définie</td><td>x<sub>1</sub></td><td>...</td><td>x<sub>k</sub></td><td>...</td><td>...</td><td>non définie</td><td></td></tr></table>

L'exécution de insérer le transforme en :

<table><tr><td>indice</td><td>dessous</td><td>i<sub>1</sub></td><td>...</td><td>J=i<sub>k</sub></td><td>i<sub>k+1</sub></td><td>...</td><td>dessus</td><td>H=I</td><td>autres</td></tr><tr><td>existe</td><td colspan="5">true</td><td colspan="3">false</td></tr><tr><td>suivant</td><td>i<sub>1</sub></td><td>i<sub>2</sub></td><td>...</td><td>H</td><td>...</td><td>...</td><td>non définie</td><td>i<sub>k+1</sub></td><td>non définie</td></tr><tr><td>date</td><td>non définie</td><td colspan="2">&lt;E.date</td><td colspan="2">&gt;E.date</td><td colspan="3">non définie</td></tr><tr><td>tranche</td><td>non définie</td><td>x<sub>1</sub></td><td>...</td><td>x<sub>k</sub></td><td>...</td><td>...</td><td>non définie</td><td>tranche</td><td>non définie</td></tr></table>

(les cases hachurées correspondent aux modifications).
### 4.353 Vérification de l'effet de l'opération adjoindre.

Il faut vérifier, R désignant la collection des variables représentant l'avenir :

abstraction(R)=a & E=e {adjoindre(E)} abstraction(R)=a ⋃ {e}.

Cette transformation de prédicat résulte du fait que abstraction(R) n'est pas modifiée dans la boucle "repeat case" car lorsque R est modifiée elle l'est par :

abstraction(R)=a {insérer} abstraction(R)=a ⋃ tranche vide,
d'une part et d'autre part de l'effet déjà vu de l'instruction
tranche(I).adjoindre(E).

### 4.4 Représentation du type tranche.

Une tranche étant un ensemble d'événements de même date totalement ordonné (voir le paragraphe 4.22), on peut le représenter par une chaîne d'événements de la même façon qu'on représente l'avenir par une chaîne de tranches.

On représente alors une tranche par la collection R de variables :

existe : indice → {true, false},

suivant : indice → indice,

événement : indice → E,

dessous, dessus à valeurs dans indice,

Une configuration possible de valeurs de R ne représente une tranche que lorsqu'elle vérifie les propriétés qui suivent :

1) la propriété P₁ déjà énoncée au paragraphe 4.32,

2) la fonction événement n'est définie qu'en i₁, i₂, ..., iₘ et vérifie événement(iₖ) < événement(iₖ₊₁) pour 1≤k<m; on note P₂ cette propriété.

L'invariant de la représentation est donc P₁ & P₂.

Lorsque R vérifie cet invariant, elle représente la tranche

x=abstraction(R)= ⋃ {événement(iₖ)} pour 1≤k≤m.

La tranche vide, valeur initiale du type tranche est représentée par une configuration de R vérifiant l'invariant avec m=0.

Ceci nous permet de représenter les opérations du type tranche.

La représentation de l'opération adjoindre utilise deux variables I et J du type local indice. On a :
procedure adjoindre(E); obs(événement) E;

begin

initialiser;

while I précède E

do avancer;

insérer

end

avec:

initialiser: begin J := dessous; I:=suivant(J) end

avancer: begin J := I; I:=suivant(J) end

insérer: begin

H:=nouveau(existe);

existe(H):=true, suivant(J):=H; suivant(H):=I;

date(H):=E.date;

événement(H):=E

end

la fonction nouveau est définie comme au paragraphe 4.331 ;

le prédicat"I précède E"vaut :

si I = dessus alors false
sinon (événement(I)<E).

La représentation de l'opération retirer utilise une variable I du type local
indice. On a :

procedure retirer(E); res(événement) E;

begin

I:=suivant(dessous);

E:=événement(I);

suivant(dessous):=suivant(I);

existe(I):=false

end

La représentation des deux autres opérations est à peu près immédiate.

## 4.5 Notes de réalisation.

On ne raffine pas davantage les types et algorithmes introduits jusqu'ici.
En effet, ils sont facilement réalisables dans un langage de programmation
comme SIMULA 67 ou PASCAL. A titre d'exemple on examine maintenant deux
réalisations possibles du type avenir.
Pour réaliser ce type, on procède de la façon suivante :

on choisit une réalisation de la collection R de variables représentant ce type, sous la forme d'une structure de données ;

on en déduit la réalisation des algorithmes représentant les opérations de ce type.

### 4.51 Réalisation à l'aide de tableaux.

On laisse de côté la réalisation des composants date et tranche de R, et on décide de réaliser :

le type indice par un type discret dont l'ensemble de valeurs est l'intervalle $0,1,...$ taille, où taille est un entier positif, 0 correspondant à la valeur non définie,

la variable existe par une rangée de booléens :

<table><thead><tr><th></th><th>1</th><th>2</th><th>3</th><th>taille</th></tr></thead><tbody><tr><th>existe</th><td></td><td></td><td></td><td></td></tr></tbody></table>

la variable suivant par une rangée d'indices :

<table><thead><tr><th></th><th>1</th><th>2</th><th>3</th><th>taille</th></tr></thead><tbody><tr><th>suivant</th><td></td><td></td><td></td><td></td></tr></tbody></table>

la variable dessous par la constante 1,

la variable dessus par la constante 2.

La valeur initiale de la chaîne est réalisée par la configuration :

existe [1] = existe [2] = true,

existe [i] = false pour $2<i<taille$,

suivant [1] = 2, suivant [2] = 0.

L'opération existe(H):=b est réalisée par existe [H]:=b, il en est de même pour l'opération analogue sur suivant.

On choisit de calculer la fonction nouveau comme suit :
```
obs(indice)procedure nouveau;
begin
  var (indice)X;
    X:=3;
  repeat case existe[X]of
    false:exit or
    true:if X=taille then error
  else X:=X+1;
  nouveau:=X
end
```

### 4.52 Réalisation à l'aide de références au sens SIMULA 67.

Dans les mêmes conditions qu'au paragraphe précédent, on décide de réaliser
le type avenir au moyen de classes SIMULA 67 de la manière suivante :

* le type indice est réalisé par la classe `ref(noeud)` où la classe noeud décrit les noeuds de la chaîne C représentant l'avenir par :
  class noeud;
  begin
    ref(noeud)suivant;
    ...date...;
    ...tranche...;
    ...
  end

* la variable existe n'est pas réalisée par une structure de données, néanmoins on peut en reconstituer la valeur à partir de C ;
  c'est-à-dire évaluer existe(X) pour toute `ref(noeud)X`;

* la variable suivant est réalisée par l'ensemble des composants suivant des instances de la classe noeud figurant dans C ;

* la variable dessous est réalisée par une `ref(noeud)`;

* la variable dessus est réalisée par une `ref(noeud)`.

On initialise la réalisation de l'avenir par la suite d'instructions SIMULA 67 :

begin

dessous:-new noeud;
dessus:-none;
dessous.suivant:-dessus

end

On remarque que de cette façon, un noeud supplémentaire est associé de façon constante à dessous. Ceci est nécessaire pour définir la valeur de dessous.suivant.

Bien entendu, la tranche et la date associées à ce noeud n'ont pas de
signification. Cette difficulté est liée à l'utilisation du langage SIMULA 67.

L'opération existe(H):=true est réalisée par H:-new noeud.

L'opération existe(H):=false figurant dans l'algorithme représentant l'opération
retirer est réalisée par l'instruction vide, puisqu'on ne détruit pas explicitement
les instances de classe en SIMULA 67.

L'opération suivant(I):=J est réalisée par I.suivant:-J.
## CONCLUSION.

En guise de conclusion, nous ferons un certain nombre de remarques.

On est parvenu à une description descendante du STR à partir d'un énoncé précis (exprimé en termes des opérations que le STR fournit à ses utilisateurs). Cette description est facile à comprendre parce qu'elle se compose de petits algorithmes qu'on peut vérifier formellement, notamment en ce qui concerne le processus UNIVERS ; en ce qui concerne les aspects parallèles du système (décrits dans le paragraphe 2), les vérifications n'ont pas été données ici parce qu'elles sont relativement compliquées et ne contribuent en rien à une meilleure compréhension de ce système. A ce sujet, on peut signaler l'avantage d'un découpage (en processus et machines) du STR invariant dans le temps. Un tel découpage facilite la recherche d'invariants par des vérifications formelles ; par contre la réalisation précédente du STR (voir introduction) comportait des créations et destructions dynamiques de processus, ce qui rendait problématique la mise en évidence d'invariants.

Par ailleurs, il nous semble que cette description est récupérable pour une nouvelle réalisation d'un système analogue en économisant le gros investissement que constitue l'analyse d'un tel projet.

L'application méthodique de la notion de type de variables (telle qu'elle est définie dans [BK 75]) est satisfaisante moyennant quelques ajouts (comme la notion de paramètre résultat). Elle a permis de raffiner l'algorithme du processus UNIVERS jusqu'à un point où il est facile à réaliser. On doit néanmoins déplorer la lourdeur des notations et constater la nécessité d'introduire des classes standards de types de variables (par exemple pour les chaînes et les fonctions utilisées dans le paragraphe 4). On doit également déplorer que la vérification de conformité de la représentation du type avenir soit hors de proportion avec l'intuition qu'on en a.

La notion de "monitor" reprise dans [Hoare 73] étant insuffisante pour spécifier la synchronisation d'une collection de processus parallèles, nous avons introduit la notion de machine, qui a l'avantage de ne pas s'exprimer en termes d'une réalisation particulière de ses opérations (au moyen des primitives "wait" et "signal"), mais par des relations temporelles entre des invocations de ces opérations. Cette notion n'a pas été complètement formalisée (voir paragraphe 2). Une continuation de la présente étude est donc le développement d'une théorie de cette notion de machine, comportant :
• des procédés de spécification,

• les techniques de vérification associées,

• un procédé de représentation, en termes plus simples tels que par exemple les sémaphores,

• les techniques de vérification de la conformité d'une telle représentation.

La spécification du STR que nous avons donnée ci-dessus est incomplète. Il reste principalement :

• à exposer la vérification du système,

• à représenter les différentes machines,

• à raffiner l'algorithme du processus COMPILATEUR (il existe des techniques classiques pour cela).
REFERENCES

Betourné C., Boulenger J., Ferrié J., Kaiser C., Krakowiak S., Mossière M.

70 : Process management and resource sharing in the multiaccess system ESOPE.

C. ACM, December 1970, pp 727-733.

Bezivin J.

74 : MINOS : a mini operating system.

U. de Rennes, note technique 25, Mars 1974.

Boucher H.

70 : Definition d'un "langage temps réel".

Note interne IRIA, 1970.

Boulenger J.

74 : Ecriture de systèmes d'exploitation à l'aide d'un langage de type PL 360.

Rapport LABORIA n° 48, Janvier 1974.

Boulenger J., Kronental M. (BK).

75 : Aspects de la notion de type,

Rapport LABORIA n° 108, Janvier 1975.

Brinch Hansen

73 : Concurrent programming concepts.

Computing Surveys vol. 5, December 1973.

Dahl O.J.

66 : Discrete event simulation languages.

NATO Summer school lectures, 1966.

Dijkstra E.W.

69 : Notes on structured programming.

Note EWD 249, August 1969.

71 : A short introduction to the art of programming.

Note EWD 316, 1971.
Crocus (nom collectif)

75 : Systèmes d'exploitation des ordinateurs.
Dunod 1975.

Evans II G.W., Wallace G.F., Sutherland G.L.

67 : Simulation using digital computers.
Prentice Hall, 1967.

Habermann A.N.

72 : Synchronisation of communicating processes,
C.ACM, Vol. 15, pp. 171-176.

Habermann A.N. & alii

73 : Designing and documenting operating systems.
Newcastle U., C.L. report SRM/40.

Hoare C.A.R.

72 : Proof of correctness of date representation.
Acta Informatica, 1972, pp 271-281.

72A : Proof of a structured program : the sieve of Erathosthenes.
The computer journal, 1972, pp 321-325.

73 : A structured paging system.
The computer journal, 1973, pp 209-215.

Ichbiah J.D., Rissen J.P., Heliard J.C.

72 : Specifications de définition de LIS.
Carnet de notes CII, octobre 1972.

Liskov B.M., Zilles S.N.

74 : Programming with abstract data types.
SIGPLAN notices, April 1974, pp 50-59.

Pont à Mousson

74 : Compte rendu des journées d'études sur les outils d'aide à la programmation.
Document IRIA, 1974.