# Lambda langage pour la manipulation dune base de données associative

Pierre Boullier, Pierre Jancene

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

## To cite this version:

Pierre Boullier, Pierre Jancene. Lambda langage pour la manipulation dune base de données associa-
tive. [Rapport de recherche] IRIA-RR-025, IRIA. 1973, pp.35. hal-04715930

HAL Id: hal-04715930

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

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_2.png" /></figure>
RIA
laboria

laboratoire de recherche
en informatique
et automatique

LAMBDA
L'Angage pour
la Manipulation
d'une Base de
Données Associative

P.Boullier P.Jancène

3SP

Institut de Recherche
d'Informatique
et d'Automatique

Domaine de Voluceau
Rocquencourt
78150 - Le Chesnay
Tél. 954.90.20

Rapport de Recherche n° 25
août 1973
# LAMBDA

## Un LAngage pour la Manipulation d'une
Base de Données Associative

P. Boullier, P. Jancene

(présenté par A. Lemaire)

## Résumé

Le langage que nous allons décrire a été réalisé dans le cadre du projet graphique METAVISU ([1]).
Il permet de construire et manipuler une structure de données comprenant :

- des objets (items)

- des doublets et des triplets d'items

- des ensembles et des listes

- des données alphanumériques associées aux items

Suivant l'idée émise dans LEAP ([2]), les doublets et les triplets sont rangés dans une mémoire associative paginée simulée par software, en vue d'accélérer l'accès à l'information.

Ce langage est une extension de CPL1, sous ensemble conversationnel de PL/1 ([3]). L'extension a été faite de façon syntaxique afin de rendre la programmation plus claire et plus simple.

Bien qu'ayant été initialement conçu pour répondre aux nécessités d'un système graphique, nous pensons que ce langage peut faciliter la résolution de nombreux problèmes dans d'autres domaines tels que l'intelligence artificielle, documentation automatique . . .

## Abstract :

The language described in this paper was implemented for the graphic system METAVISU ([1]).
It allows building and manipulating a data structure including :

- items

- triples and pairs of items

- sets and lists

- alphanumeric data associated to items

According to the idea mentioned in LEAP ([2]), triples and pairs are stored into a paginated and associative memory simulated by software, to make the access time to information as short as possible.

The language is an extension of CPL/1, a conversational subset of PL/1 ([3]). This extension was carried out as a syntactic one, to make the language clearer and easier to use.

Although this language was previously designed for a graphic system, we think it can be a good aid for solving problems in other fields such as artificial intelligence.
# I - INTRODUCTION

L'étude suivante a été effectuée dans le cadre du projet graphique METAVISU. ([1]).

Le but d'un système graphique interactif est de donner à ses utilisateurs un moyen de construire un modèle du problème à résoudre, puis de tester et modifier ce modèle jusqu'à ce que les résultats soient jugés satisfaisants.

L'équation suivante, attribuée à D.T. Ross résume ainsi le problème :

Modèle = Données + Structure + Algorithmes.

Les informations contenues dans la structure de données doivent permettre à l'utilisateur de produire des images, mais également d'effectuer des calculs qui en général sont indépendants de l'aspect graphique du problème. La conception de la structure de données ne doit donc pas se baser sur des préoccupations uniquement graphiques.

Les buts que nous nous sommes efforcés d'atteindre sont les suivants :

* permettre de construire une structure générale à partir d'un nombre restreint de concepts de base

* implanter la structure de façon efficace, tenant compte de l'environnement paginé afin d'assurer un temps d'accès à l'information aussi court que possible, tout en n'utilisant qu'une place raisonnable en mémoire centrale

* fournir un langage clair et simple pour construire et exploiter la structure. L'attention du programmeur doit être concentrée sur le problème réel à résoudre et non sur des problèmes annexes comme l'allocation de mémoire principale ou secondaire, entièrement prise en charge par le système.

Le langage doit en outre permettre d'effectuer des calculs sur les éléments extraits de la structure avec les facilités habituelles des langages évolués comme Algol ou PL/1.
Comme signalé précédemment, le langage n'est pas orienté vers des applications purement graphiques, mais peut être utilisé indépendamment du système graphique METAVISU.

Les travaux de J.A. FELDMAN et P.D. ROVNER sur le langage LEAP([2]) nous ont semblé intéressants dans la mesure où ils correspondaient bien à nos préoccupations, et constituent le point de départ de notre étude.

La structure contient des objets (items), des associations de ces objets (doublets, triplets), et des constructions auxiliaires (ensembles et listes).

Le langage qui la manipule est intégré à CPL/1 ([3]) sous ensemble conversationnel de PL/1, CPL/1 proprement dit servant à décrire les algorithmes et à effectuer les calculs.

A une intégration par appels de procédures ([4]), nous avons préféré une intégration syntaxique permettant une programmation plus claire et plus simple. La mise au point des programmes est d'autre part facilitée par le caractère conversationnel du langage, tant à la compilation qu'à l'exécution.

## II - TRAITS PRINCIPAUX DU LANGAGE

Le langage que nous allons décrire permet de construire, modifier et explorer la structure de données.

L'efficacité de la recherche dans la structure est assurée par l'implantation très particulière des doublets et des triplets comme on le verra au chapitre suivant.

Dans ce qui suit, les mots clé du langage seront écrits en minuscule. Ces mots clé sont réservés.

### 2.1 - Les items et les itemvars

Les items peuvent être soit déclarés soit créés dynamiquement.

dcl item ARETE ;

Un item de nom externe ARETE est alors entré en tables et le système lui donne un nom interne qui sera utilisé dans les triplets, doublets... Un item peut avoir des données associées, en qualifiant sa déclaration. Les types de données autorisées sont : type simple (arithmétique, chaîne), et tableaux de ces mêmes types.

dcl item A(2) bin fixed ;

L'item A a un tableau associé de deux composantes de type 'bin fixed'.
L'accès au données d'un item est fait au moyen de l'opérateur unaire 'datum'.

(1) datum A(1) = 1024 ; datum A(2) = 512 ;

Par 'datum', les données d'un item peuvent être utilisées comme
toute variable CPL/1 (affectation, comparaison, expressions...).

Un item peut être accédé soit par son nom externe, soit par une
nouvelle entité appelée 'itemvar' : un itemvar est une variable dont la
valeur est un item, et doit être déclaré.

dcl itemvar X ;
X < - ARETE ;

Après l'instruction ci-dessus, l'itemvar X pointe sur ARETE, c'est
à-dire que toute occurence de X dans une expression est identique à celle de
l'item ARETE.

Un itemvar peut être également utilisé pour référencer les données
d'un item. Il faut pour cela qualifier la déclaration de l'itemvar, en repre-
nant les mêmes types que ceux de l'item à pointer.

(2)
dcl item A(2) bin fixed ;
dcl itemvar Y(2) bin fixed ;
Y < - A ;
datum Y(1) = 1024 ; datum Y(2) = 512 ;

Après exécution de la dernière instruction, le tableau associé à
l'item A est modifié comme après (1).

Les items peuvent être créés dynamiquement de plusieurs manières

Y < - new ; /* 'new' est une fonction système */

Un item est créé sans nom accessible à l'utilisateur, et Y pointe
sur lui.

Y < - 'NOUVEL ITEM 1' ;

Ici l'item construit a un nom externe, NOUVEL\u{em}Item\u{e}l.

Y - > new ;

L'item est créé avec des données associées de la même forme que celle
spécifiée lors de la déclaration de l'itemvar, un tableau de deux composantes
'bin fixed' dans ce cas particulier.

Y - > 'NOUVEL ITEM 2' ;

Même chose que ci-dessus, mais l'item a un nom externe. Toute expression
CPL/1 rendant comme valeur une chaîne est utilisable pour donner un nom à un
item créé dynamiquement.

Les items et les itemvars peuvent être comparés entre eux comme des
variables CPL/1.
Y < - A ; X < - ARETE ;

if Y = A & X = ARETE then put list ('O.K') ;
else put list ('K.O') ;

Les seules comparaisons autorisées sont l'égalité et l'inégalité.

Des fonctions-système permettent d'obtenir différents renseignements sur les items :

. value : rend comme valeur un entier représentant le nom _interne_ de l'item

. name : rend une chaîne de caractères qui est le nom externe de l'item

. isitem: appliqué à une chaîne de caractères ou un itemvar répond '1'B si l'argument est un item, '0'B s'il ne l'est pas.

Par exemple après l'instruction

Y < - 'ALPHA' ; /* création de l'item ALPHA */

on aura

value (Y) = 32727
name (Y) = 'ALPHA'
isitem (’ALPHA’) = ’1’B

## 2.2 - Les ensembles et les listes

Les items peuvent être regroupés dans des ensembles (collection non ordonnée d'objets) et dans des listes (collection ordonnée d'objets).

Listes et ensembles doivent être déclarés

dcl set S ;
dcl list L ;

S et L sont entrés en table et créés vides.

L'ensemble vide est noté [ ], la liste vide [..]

L'affectation permet de modifier le contenu des ensembles et des listes, et peut conduire à la création de nouveaux items.

S = [A, 'B', 'B'] ;
L = [ . ARETE, ARETE, A, A. ] ;

Un item de nom externe B est créé et inclus dans l'ensemble S qui contiendra 2 items, B n'étant pas répété. Par contre L aura 4 éléments, ARETE et A apparaissant chacun deux fois dans la liste.
L'opérateur unaire 'count' appliqué à un ensemble ou une liste
rend pour valeur un entier égal au nombre d'éléments de l'ensemble ou de la
liste (count(S) = 2, count(L) = 4).

Les opérations disponibles sur les ensembles sont les opérations
classiques : union (notée par $\cup$), intersection ($\cap$), différence ($-$).

Les listes peuvent être concatenées (opérateur $\|$). La fonction
système 'atom' permet d'extraire un élément de la liste et 'sublist' extrait de
la liste une sous-liste.

Dans la liste L spécifiée ci-dessus on aura par exemple :

`atom(L,3) désigne le premier item A`

`sublist (L, 2, 3) désigne la sous-liste [.ARETE, A, A.]`

De plus la fonction 'index' permet de savoir si une liste L1 apparait
dans une liste L2. La valeur retournée est l'index dans la liste L2 où se
trouve la première occurence de L1 (O s'il n'y a pas d'occurence).

`index (L,[.ARETE.]) = 1 (première occurence)`

`index (L,[.'B'.]) = 0 (B n'est pas dans L)`

Les comparaisons entre listes et entre ensembles sont les suivantes :
'égalité (=), l'inégalité ($\neg=$), l'inclusion ($<$) et la non-inclusion ($\neg<$).

L'appartenance et la non-appartenance d'un item à un ensemble ou
une liste pour être testée par 'in' et '$\neg$in'.

`if ARETE $\neg$ in S then put list ('S ne contient pas ARETE') ;`

Jusqu'à maintenant les listes et les ensembles n'ont que des items
comme constituants : par exemple il n'est pas possible qu'une liste soit
le composant d'une autre liste. La création dynamique de nouveaux types
d'items permet de compenser cette lacune.

`dcl list L2 ;`

`L = [.A, A.]; L2 = [.ARETE.];`

(3) $X \subset L2$ as 'ITEM DE LISTE' ;

Cette dernière instruction crée un "item de liste", dont le nom
externe est donné par la chaîne de caractères suivant 'as'. L'itemvar X
pointe sur lui et permet ainsi de manipuler le nouvel item comme ceux décrits
précédemment.

(4) $L = L || [.X.]; /* concatenation de deux listes */$
L'item pointé par X est ajouté à la queue de la liste L, donnant
la représentation suivante de la liste

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

Le contenu d'un item de liste ou d'ensemble est obtenu par l'inter-
médiaire de 'list' ou de 'set'. Si au lieu de (4) on avait écrit :

(4') L = L || list(X) ;

on aurait en le schéma suivant représentatif de L :

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

ce qui est nettement différent du résultat obtenu après (4).

Des "items d'ensemble" peuvent être créés de la même façon.

Les opérateurs unaires 'isset' et 'islist' permettent de savoir
si un itemvar pointe sur un item de liste ou d'ensemble ; ils renvoient comme
valeur une chaîne de bit de longueur 1 (’0’B ou ’1’B).

if islist(X) then ; /* (3) a marché */
else ; /* (3) ..... */

La création dynamique de ces nouveaux types d'items permet
d'accroître la généralité des ensembles et des listes, autorisant ainsi des
constructions plus élaborées.

2.3 - Les doublets et les triplets.

Les doublets et les triplets forment la partie associative de la
structure de données. Ils sont rangés dans une mémoire associative à deux
ou trois champs simulée par software. L'implantation de la structure et le
mécanisme d'accès à l'information seront décrits au chapitre suivant.
Un triplet (doublet) est une collection ordonnée de trois (deux) items.

On peut interpréter un triplet comme :

1'ATTRIBUT de 1'OBJET est la VALEUR (le PERE de PAUL est JEAN) et
un doublet comme :

1'OBJET a la PROPRIETE (PAUL est JEUNE)

La structure associative se compose alors d'un univers de triplets et de doublets. Initialement, elle est vide.

Ces associations ne sont pas déclarées mais créées dynamiquement
au moyen de l'instruction MAKE ; elles sont ainsi ajoutées à la structure
existante à moins qu'elles ne s'y trouvent déjà.

(5) make < PERE, PAUL, JEAN > ;

make < PAUL, JEUNE > ;

ajoute à la structure le triplet et le doublet spécifiés.

Les associations peuvent être retirées de la structure par
1 'intermédiaire de l'instruction ERASE.

erase <PERE, PAUL, JEAN> , <PAUL, JEUNE> ;

supprime ce qui avait été construit précédemment.

La spécification de l'item à l'intérieur du triplet peut également
se faire au moyen d'un itemvar :

dcl itemvar T ;

T <- PERE ;

make <T, PAUL, JEAN> ;

produit le même résultat que l'instruction (5).

L'exécution d'une instruction MAKE peut conduire à la création de
nouveaux types d'items comme le montre l'exemple suivant :

dcl item PERE, FILS, JEAN, PAUL, INVERSE ;

(6) make < INVERSE, < PERE, PAUL, JEAN >, < FILS, JEAN, PAUL >> ;

On remarquera tout d'abord qu'un triplet peut être l'un des composants
d'un autre triplet. L'instruction (6) entraîne l'insertion dans la structure
des deux triplets les plus intérieurs, puis les transforme en "items de triplets'
utilisés pour la création de l'association avec l'item INVERSE.
Les items de triplet peuvent être créés et atteints par un itemvar.

Des données peuvent même leur être attribuées :

dcl itemvar W char(100) varying ;

(7) W -> < PERE, PAUL, JEAN > ;

datum W = 'TRIPLET DONNANT LA RELATION ENTRE PAUL ET JEAN' ;

(7) forme le triplet et l'ajoute à la structure, puis crée un nouvel item ayant des données associées du même type que celui qui apparaît dans la déclaration de l'itemvar, et W pointe sur cet item. Il est ensuite possible de modifier par affectation les données de l'item.

Ensembles et listes peuvent servir à la construction des triplets et doublets, permettant de spécifier en une seule instruction tout un groupe d'associations à créer.

dcl set DEPART, ARRIVEE ;

DEPART = ['PARIS', 'BORDEAUX'] ;

ARRIVEE = ['LYON', 'MARSEILLE'] ;

make < 'TRAIN', DEPART, ARRIVEE > ; /* Un item de nom TRAIN est créé. */

On enregistre ainsi le fait qu'il y a des liaisons par train Paris-Lyon, Paris-Marseille, Bordeaux-Lyon et Bordeaux-Marseille, la structure s'augmentant de 4 nouveaux triplets.

Pour retirer toutes ces associations, il suffit d'écrire :

erase < 'TRAIN', DEPART, ARRIVEE > ;

Tout ce qui a été dit sur les composants de triplets, les items de triplet et leur création est également valable pour les doublets, les items de doublet... Il suffit d'ajouter qu'un doublet peut entrer dans la composition d'un triplet et inversement.

L'existence d'un doublet ou d'un triplet dans la structure est testée par les fonctions 'isdouble' et 'istriple', retournant comme valeur une chaîne de bits de longueur 1 ('0' B ou '1' B).

if istriple(<PERE, PAUL, JEAN>) & isdouble(<PAUL, JEUNE>) then...

Il est de même possible de savoir si l'item pointé par un itemvar est un item de doublet ou de triplet :

if istriple(X) | isdouble(X) then......

Enfin, les constituants d'un doublet et d'un triplet sont accessibles par l'intermédiaire des opérateurs suivants : 'first' 'second' et 'third' (ce dernier n'ayant pas de sens pour un doublet).
W <- < INVERSE, <PERE, PAUL, JEAN>, <FILS, JEAN, PAUL>> ;

W pointe sur le triplet créé et first(W) sera l'item INVERSE,
tandis que first(second(W)) sera l'item PERE.

2.4 - Destruction des items.

Tous les items, sauf ceux qui ont été déclarés, peuvent être
détruits au moyen de l'instruction DELETE.

delete 'ALPHA' ;

Si un item de nom ALPHA existait dans la structure, il en est
retiré.

(8) X <-< 'ALPHA', 'BETA', 'GAMMA' > ;

delete X ;

Ici seul l'item de triplet est détruit ; l'association créée par (8)
demeure toujours dans la structure, de même que les items ALPHA, BETA et GAMMA.

(9) X <-< 'ALPHA', <'PI', 'RO' >, 'MU' > ;

delete X ;

Comme décrit plus haut, (9) entraîne la construction d'un doublet
(<PI, RO>), d'un item de doublet, d'un triplet et enfin d'un item de ce
même triplet sur lequel pointe X. L'instruction DELETE ne supprime que ce
dernier item.

dcl set S ;

S = ['MU', 'NU'] ;

delete S ;

Tous les éléments de S sont détruits et S devient vide.

Remargue importante

C'est à la responsabilité de l'utilisateur de veiller à ce qu'un
item détruit n'intervienne dans aucune construction triplet, doublet,
ensemble ou liste. Le système ne se charge de retirer de la structure que
l'item, sans regarder ses occurences dans les différentes associations.
## 2.5 - Recherche associative dans la structure

Une instruction spéciale permet de retrouver l'information dans l'univers des doublets et triplets. Elle permet de spécifier le contexte dans lequel rechercher l'information intéressante.

Les questions élémentaires que l'on peut poser à la structure sont en nombre relativement limité étant donné la simplicité des entités rangées dans la structure. Le tableau suivant donne toutes les formes de questions possibles, la ou les inconnues étant notées par ?

<table><thead><tr><td>FORME</td><td>EXEMPLE</td><td>REPONSE</td></tr></thead><tbody><tr><td>A O ?</td><td>PERE PAUL ?</td><td>les pères de PAUL (!)</td></tr><tr><td>A ? V</td><td>PERE ? JEAN</td><td>les fils de JEAN</td></tr><tr><td>? O V</td><td>? PAUL JEAN</td><td>les relations entre PAUL et JEAN</td></tr><tr><td>A ? ?</td><td>PERE ? ?</td><td>les couples fils -père</td></tr><tr><td>? O ?</td><td>? PAUL ?</td><td>les couples A - V des triplets où PAUL est en deuxième position</td></tr><tr><td>? ? V</td><td>? ? JEAN</td><td>-id- A - O avec JEAN en 3e position</td></tr><tr><td>? ? ?</td><td></td><td>tous les triplets de la structure</td></tr><tr><td>O ?</td><td>JEAN ?</td><td>les propriétés de JEAN</td></tr><tr><td>? P</td><td>? JEUNE</td><td>tous les jeunes</td></tr><tr><td>? ?</td><td></td><td>tous les doublets</td></tr></tbody></table>

L'instruction `FOREACH` permet de combiner ces questions élémentaires (par des AND) et d'exécuter un certain nombre d'instructions (corps du `FOREACH`) pour chaque élément de réponse, s'il en existe.

Supposons par exemple que dans la structure se trouvent des triplets ayant pour premier item `PERE`, et que les fils aient des propriétés parmi les suivantes : `JEUNE`, `BEAU` et `GENTIL` entrées sous forme de doublets.

dcl itemvar X, Y ;

(a) `foreach <PERE,*X,*Y> ;` and `<X,[BEAU, GENTIL]> ;`

(b1) put list (X) ;

(b2) put list (Y) ;

(c) end ;
La partie (a) du FOREACH sert à poser la question qui dans notre cas est à deux volets :

- trouver tout d'abord tous les couples fils-père de la structure. Un itemvar précédé de '*' indique que ce champ du triplet est une inconnue.

- et parmi ces couples, ne retenir que ceux dont le fils est beau ou gentil ou les deux à la fois. Ici X n'est plus précédé de '*' parce que ça n'est plus une inconnue à proprement parler.

Le corps du FOREACH est constitué de (b1) et (b2). Il est exécuté autant de fois qu'on a trouvé de couples répondant aux deux questions, X et Y pointant successivement sur les éléments d'un même couple.

La fin du corps du FOREACH est indiquée par (c).

La recherche dans l'univers des doublets et des triplets se fait de façon associative, ce qui permet d'accélérer ce processus. Le chapitre 3 décrit en détail 1 'organisation des fichiers de triplets et doublets et le moyen d'accès à ces fichiers.

La spécification du FOREACH peut comporter des expressions logiques, par exemple des tests d'appartenance d'un item à un ensemble ou des comparaisons arithmétiques ou de chaînes. Cependant seules les recherches correspondant aux questions élémentaires spécifiées plus haut sont faites de façon associative.

Par exemple si dans la structure précédente les enfants sont regroupés dans deux ensembles GRANDS et PETITS suivant leur taille et ont d'autre part une donnée associée indiquant leur âge, on peut écrire :

foreach *X in GRANDS and <X, GENTIL> and datum X<10 ;
        ........ ;

end ;

Dans le corps du FOREACH, X pointera successivement sur les différents grands enfants gentils de moins de 10 ans.

L'imbrication de questions élémentaires permet de condenser l'expression du contexte dans lequel on se place

dcl itemvar X, Y, Z, T, U ;

dcl item A, B, C ;

(10) foreach <A, <*X, <B, *Y>, *Z>, *T> and T = Y ;
        ............ ;

end ;
Le système pose alors les diverses questions à la structure
"de l'intérieur vers l'extérieur et de gauche à droite". Ainsi l'énoncé
précisé en (10) sera transformé dans la succession suivante de FOREACH
imbriqués :

foreach <B,*Y> ;
foreach <*X,<B,Y>,*Z> ;
foreach <A,<X,<B, Y>,Z>,*T> ;
    if T = Y then
        do ;
        ....................;
    end ;
end ;
end ;

Une instruction identique dans sa forme au FOREACH, FORONE n'exécute
son corps qu'une seule fois pour un élément quelconque de la réponse s'il
existe.

## Expressions particulières

Lorsque l'ensemble (au sens mathématique) des items répondant à une
question simple à une inconnue est recherché, il existe une façon plus
commode de récupérer cet ensemble que par une instruction FOREACH.

P et Q étant des items, on a les formes suivantes :

| [P : Q] | est l'ensemble <P,X,Q> | existe dans |
| [P ** Q] | des items X <P,Q,X> | l'univers des |
| [P'' Q] | tels que <X,P,Q> | associations. |
| [ : Q] |  | <X,Q > |
| [ ** Q] |  | < P,X > |

Ces formes dérivées d'ensembles peuvent se rencontrer dans toutes les
expressions où est admis un ensemble.
Lorsqu'un ensemble d'associations ou d'items de doublets ou de triplets doit être détruit, l'emploi d'une astérisque en un champ quelconque du doublet ou du triplet permet de répéter l'opération pour toutes les valeurs (items) satisfaisant la relation spécifiée.

```
erase <P,*,*> ; /* retire de la structure tous les triplets ayant
                  P en premier élément */
delete <*,*> ; /* détruit tous les items de doublets */
```

## 2.6 - Les procédures

Les items, itemvars, ensembles et listes sont autorisés en arguments et paramètres de procédures qui peuvent retourner comme valeur un item, un ensemble ou une liste. Toutes les procédures peuvent être récursives.

Les données associées à un item sont passées comme les variables CPL/1 du même type.

```
P : proc(ENSEMBLE, LISTE, ITAIM) set ;
    dcl set ENSEMBLE ; dcl item ITAIM ;
    dcl list LISTE ;
    ............;
    return(ENSEMBLE | [ITAIM]) ;
end P ;
```

L'appel de la procédure s'écrit comme celui d'une procédure CPL/1 normale :

```
dcl list L ; dcl set S ;
dcl item A, B, C ;
S = P([A,B],L,C) ;
```

Les arguments sont passés "par référence" tandis que les valeurs sont retournées "par valeur".

Les points d'entrée secondaires d'une procédure admettent les mêmes types d'arguments que les points d'entrée principaux.

Dans la déclaration de points d'entrée, les spécifications d'items, de liste ou d'ensemble sont permises :

```
dcl P1 entry (float, item, char(*), set) returns(list) ;
```

Enfin, un appel de procédure peut remplacer dans toutes les expressions décrites un élément du même type que la valeur retournée.
## 2.7 - Les entrées-sorties

Les règles de manipulation de fichiers (ouverture...) sont celles admises par le langage CPL/1.

L'entrée (sur fichier ou télétype) des items, ensembles et listes se fait dans les modes 'list' ou 'data' définis dans PL/1. Les données associées à un item peuvent être lues dans les 3 modes connus de CPL/1, 'list', 'data' et 'edit'.

```
dcl set S;
dcl itemvar X(2) bin fixed;
get data (S, X, datum X);
```

Lors de l'exécution du 'get data', le système demande à l'utilisateur de frapper au télétype les valeurs à attribuer aux différentes variables.

Si la ligne suivante est entrée :

```
S = [A,B] X -> C datum X(1) = 0 datum X(2) = 1024;
```

Le système

* créé 2 items A et B, les met dans un ensemble et affecte cette valeur à S

* crée un item C avec des données associées du même type que celui de X et X pointe sur C

* affecte aux données de C les valeurs 0 et 1024.

La sortie des items, ensembles et listes se fait en mode 'list', 'edit' ou 'data'.

En mode édit le contenu des variables est décomposé au maximum alors qu'en mode list et data, le système s'arrête au "premier niveau":

```
dcl set S;
dcl item A, B, C;
S = [A, B, <B, C>];
put list(S);
put edit(S) (aov);
```

La sortie sur le télétype sera :
```
['B', 'A', doublet]
['B', 'A', '<B', 'C'>]
```

En 'edit' le doublet apparaissant dans S a été imprimé en clair.
## 2.8 - Sauvegarde de la structure

La structure créée lors de l'exécution d'un programme peut être conservée en vue d'une utilisation ultérieure. L'utilisateur donne à l'appel du compilateur le nom sous lequel il voudra retrouver sa structure

```
*CPL1 SDO = STRUCTURE
e : proc ;
        ............ ;
end e ;
% exec ;
% end ;
```

L'exécution du programme est provoquée par % exec ;. Une structure de travail se crée alors au fur et à mesure des besoins. A la fin de l'exécution, % end ; entraîne le sauvetage des données créées sous le nom STRUCTURE.

La récupération de la structure se fait par l'option inverse de SDO, SDI

```
*CPL SDI = STRUCTURE
f : proc ;
        ............ ;
end f ;
```

Dans f, tous les résultats de l'exécution du programme e sont disponibles.

Une structure se compose de plusieurs fichiers (1 à 9), mais l'utilisateur n'a à connaître que le nom sous lequel il veut la sauvegarder.

La taille des fichiers évolue au cours de l'exécution. Initialement elle est de 1 page. Si à un moment donné un nouvel élément ne peut se ranger dans un fichier, la structure double automatiquement de taille, les informations existantes sont réorganisées et le nouvel élément est inséré. (La taille maximum des fichiers est de 256 pages).

Ce processus de doublement est coûteux et l'utilisateur peut diminuer le nombre de ces opérations en spécifiant au départ la taille approximative qu'atteindra sa structure.
CPL
SDO = (5, STRUCTURE)

...

Les fichiers auront ici une taille initiale de $2^5$ pages et la
structure pourra subir au maximum 3 doublements ($256 = 2^8$).

Enfin, une structure peut être commune à plusieurs usagers. L'un
de ceux-ci, le propriétaire, autorise les autres à accéder à ses données
en lecture uniquement, ou en lecture et en écriture. Le système se
charge de régler les problèmes d'accès aux fichiers, un fichier ne pouvant
être utilisé au même instant par plus d'un utilisateur.

### III - PRINCipe D'IMPLANTATION DE LA STRUCTURE DE DONNEES ASSOCIATIVE

Les principales idées directrices sont les suivantes :

- tenir compte de l'environnement paginé

- utilisateur ne doit pas se soucier de la façon dont les
associations sont rangées et manipulées physiquement

- performances élevées pour chacune des 7 questions

- taille maximale de la structure pouvant varier dynamiquement.

La première idée directrice montre la nécessité d'avoir un schéma
partitionné. En effet dans un environnement à partage de ressources une
représentation de la structure de données dans un espace linéaire sera découpée
en pages, par le système, de façon arbitraire. Une simple recherche demandera
de nombreux accès en mémoire secondaire ce qui ralentira considérablement le
temps de réponse. L'implantation choisie assure que, dans les cas courants,
la réponse à l'une quelconque des 7 questions puisse être assurée en au plus
un accès disque.

La deuxième idée directrice permet à l'utilisateur de n'avoir à se
soucier que du concept logique d'association. Le manque apparent de structure
du côté utilisateur est mis à profit par le système pour organiser l'information
traitée à sa propre convenance.

Ex. Du point de vue utilisateur un ensemble est une collection non
ordonnée d'items. Cependant de façon interne un ensemble est ordonné par les
noms internes de ses éléments ce qui augmente l'efficacité des routines
systèmes de manipulation d'ensembles. La tâche de vérifier si 2 ensembles de m et n éléments sont disjoints nécessite au plus m + n comparaisons si les ensembles sont ordonnées (sinon au plus m x n comparaisons).

La troisième idée directrice est obtenue de la façon suivante :

**Table des items**

De façon interne on associe à chaque item un nombre entier binaire de n bits (nom interne statique) en correspondance bijective avec cet item.

Ce nom interne statique dépend de l'item et de l'état de la structure de données au moment de sa création. Il est fixé au cours de la vie de l'item cela même si la taille de la structure de données vient à changer.

Pour le système la taille de la structure de données est un nombre entier de t bits tel que $0 \le t \le n - k$ ce nombre pouvant varier dynamiquement avec la vie de la structure.

Construction du nom interne statique.

Une fonction de Hash-code transforme le nom externe de l'item en un entier de n bits.

Les t bits intermédiaires donnent un numéro de page P. Les k - 1 bits de faible poids servent d'index dans la page P. Le traitement des collisions est effectué dans cette page et rend un nombre de k bits qui , concaténé avec les n - k bits précédents constitue le nom interne statique.

Les k + t bits de faible poids du nom interne statique constituent le nom interne dynamique.

<figure><img src="image_5.png" /></figure>
Le nom interne dynamique est donc interprété par le système comme une
adresse : les t bits de fort poids donnent un numéro de page P et les k bits
de faible poids servent d'index dans la page P. A cette adresse se trouvent
des renseignements nécessaires au système (nom externe, type et adresse des
data associées, etc...).

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

## Triplets

L'organisation de l'espace dans lequel sont rangées les associations est telle qu'elle permette de répondre rapidement aux 7 questions de base. Pour cela il est divisé en trois univers, chaque univers étant divisé en pages : l'Univers des A-pages, l'Univers des O-pages, l'Univers des V-pages.

Un triplet donné figure dans les trois univers mais avec une structure différente, chaque représentation permettant de répondre à deux questions.

L'implantation dans les trois univers est symétrique. La question posée permet de déterminer :

- un univers accès

- un item d'accès A et éventuellement :

- un item de contrôle C

- un item sémantique $S^{(*)}$

(*) A,C,S désignent soit un item soit son nom interne statique.
<table><caption>Tableau 1</caption><thead><tr><th>Question</th><th>Type</th><th>Univers de recherche</th><th>item d'accès</th><th>item de contrôle</th><th>item sémantique</th></tr></thead><tbody><tr><td>AOV</td><td>0</td><td>indifférent par ex. A-pages</td><td>A</td><td>0</td><td>V</td></tr><tr><td>AO?</td><td>1</td><td>A-pages</td><td>A</td><td>0</td><td></td></tr><tr><td>A?V</td><td>1</td><td>V-pages</td><td>V</td><td>A</td><td></td></tr><tr><td>A??</td><td>2</td><td>A-pages</td><td>A</td><td></td><td></td></tr><tr><td>?OV</td><td>1</td><td>O-pages</td><td>O</td><td>V</td><td></td></tr><tr><td>?O?</td><td>2</td><td>O-pages</td><td>O</td><td></td><td></td></tr><tr><td>??V</td><td>2</td><td>V-pages</td><td>V</td><td></td><td></td></tr></tbody></table>

Les t bits de fort poids du nom interne dynamique de l'item d'accès donnent un numéro de page dans l'univers considéré.

Un hash-code de l'item d'accès et de l'item de contrôle (A@C) permet de déterminer une adresse dans cette page, à laquelle sera rangé le triplet considéré.

Si la fonction de hash-code @ est telle que :

$$ \text{si } A \neq A' \quad A@C \neq A'@C \qquad (I) $$

alors il est inutile de ranger A et C à l'adresse considérée, la connaissance de C et de l'adresse (A@C) est suffisante pour lever l'ambiguïté. Supposons qu'un triplet < A,C,S > soit rangé à l'adresse a = A@C si un triplet < A',C,S' > est tel que A'@C = a = A@C on est sur (d'après I) que A = A' les deux triplets considérés ont donc leurs deux premiers champs égaux.
Tous les items sémantiques S correspondant aux mêmes items d'accès et de contrôle sont rangés sur une même liste, ordonnée par noms internes statiques croissants, dans la page considérée.

Il est évident que l'on peut avoir $A \oplus C = A' \oplus C'$ avec $C \neq C'$ il y a alors collision. Les triplets entrant en collision sont chaînés entre eux dans la même page et ordonnés par nom interne statique croissant de l'item de contrôle.

L'organisation précédante permet de résoudre aisément les questions de type 0 et 1 (cf Tableau n° 1).

Pour répondre aux questions de type 2 on ajoute un chaînage liant entre eux tous les triplets ayant même item d'accès A. Le point de départ de cette chaîne est situé dans la page considérée à une adresse dépendant des k premiers bits du nom interne de l'item d'accès.

Une page est donc logiquement divisée en quatre parties :

- départ des chaînages A liant entre eux tous les triplets ayant même item d'accès

- zone de hash-code direct

- zone de traitement de collisions

- zone dans laquelle sont rangés les items sémantiques.

Ex : Fig. 1 décrit une A-page après avoir rentré les triplets suivants :

$<A_1, O_1, V_1>, <A_1, O_1, V_2>, <A_2, O_2, V_3>, <A_2, O_2, V_4>, <A_1, O_2, V_3>$,
$<A_1, O_1, V_3>$

$$ \text{avec : } - A_1 \oplus O_1 = A_2 \oplus O_2 $$

$$ - V_1 < V_2 < V_3 $$

$$ - O_1 < O_2 $$

Avantage :

Accès direct à l'information cela quel que soit le type de question posée.
Inconvénient :

Chaque triplet figure trois fois, une fois dans chaque univers.
La principale justification à ce fait est que la place est
perdue uniquement en mémoire secondaire, la place utilisée en
mémoire centrale, pour répondre à une question est moindre
que celle nécessaire pour répondre à la même question un triplet
ne figurant qu'une seule fois.

<figure><img src="image_7.png" /><figcaption>Fig. 1</figcaption></figure>

La quatrième idée directrice est liée au traitement des débordements.
Débordement de la table-hash

Si, à un item donné, on ne peut plus lui associer de nom interne (la page correspondante de la table-hash est pleine) on effectue la procédure suivante.

La taille de la structure de données est un nombre de t bits.

Dans toutes les pages de N° p telles que $0 \le p \le 2^t - 1$ on regarde chaque item. Si le k + t + 1<sup>ième</sup> bit de son nom interne statique est :

- 0 on ne fait rien

- 1 l'item est supprimé de la page N° p et mis dans la page N° $2^t + p$ à l'adresse telle que son nom interne statique ne change pas.

Lorsque la structure de données passe de la taille $2^t$ à la taille $2^t + 1$ les noms internes statiques des items ne changent pas, les triplets les contenant ne changent donc pas. Lorsqu'un item passe de la page N° p à la page N° $2^t + p$ tous les triplets l'ayant comme item d'accès dans les trois univers doivent être déplacés de la page d'accès N° p à la page d'accès N° $2^t + p$.

Lorsque la taille de la structure double on n'a donc, en moyenne, qu'à déplacer la moitié des items et des triplets la constituant.

Débordement des pages des univers

Lorsqu'une telle page déborde on pourrait songer à utiliser le même algorithme, c'est-à-dire doubler la taille de la structure de données. Si le débordement est du à un grand nombre de triplets ayant même item d'accès, le fait de doubler la structure n'empêchera pas ces triplets de se trouver dans la même page, le numéro de cette page dépendant uniquement de l'item d'accès. Dans ce cas le système fournit des pages de débordement liées à la page d'accès. Pour atteindre une information donnée il faut suivre les chaînages partant de la page d'accès à travers les pages de débordement. Le classement des collisions par item de contrôle croissant et des items sémantiques par ordre croissant permet de réduire la longueur de ce parcours et en conséquence le nombre d'accès en mémoire secondaire. Il est envisagé, le système étant conversationnel à l'exécution, de demander à l'utilisateur s'il préfère doubler
la taille de sa structure ou prendre des pages de débordement, des statistiques système pouvant l'aider à faire son choix.

La taille de la structure peut varier dynamiquement cela jusqu'à un maximum compatible avec le système. Cependant le doublement de la taille de la structure est une opération de plus en plus coûteuse en temps au fur et à mesure que celle-ci croît. L'utilisateur a donc la possibilité, avant toute exécution, de donner au système la taille probable de sa structure de données.

# IV - EXEMPLES

## 4.1 - Constitution et interrogation d'une mini bibliothèque

Cet exemple montre, entre autres aspects du langage, la possibilité de sauvegarder une structure de données et de la réutiliser ensuite par différents programmes.

La bibliothèque est formée de références à des articles pour lesquels les renseignements suivants sont fournis :

- le titre de l'article

- la revue dans laquelle il a paru

- le nom du ou des auteurs

- l'année de parution

- le ou les mot-clé associés à l'article.

On voudra ensuite pouvoir poser des questions à cette bibliothèque, du genre :

"Qui a publié quoi ?"

"Quels articles ont été publiés dans telle revue ?"....

Chaque article est conservé dans la bibliothèque sous la forme d'un item ayant pour donnée associée son titre. Puis cet item est associé par doublets à ses mot-clés, et par triplets à chacun de ses auteurs, à la revue et à l'année de parution.

En outre bien que ceci ne soit pas nécessaire, mais pour faciliter l'énoncé de certaines questions, de nouvelles associations sont établies : triplets liant chaque auteur de l'article d'une part, à chaque mot-clé, la revue et l'année de parution d'autre part.
Enfin, trois ensembles regroupent respectivement les articles,
les auteurs et les mot-clés.

La suite d'exécutions présentée est la suivante.

• CONSBIB crée une bibliothèque (BIB) en lisant les informations contenues dans le fichier DATABIB et sauve cette structure (les données lues sur le fichier sont imprimées du fait de la présence de l'option LS dans la ligne CPL...).

• QUID pose quelques questions à la structure BIB (option SDI = BIB) et en imprime le résultat sur télétype.

• CONSBIB exécuté à nouveau modifie la bibliothèque précédente (SDI = BIB) en lisant les nouveaux articles sur le télétype (nom de fichier standard SYSIN) et sauve le résultat dans BIB (SDO = BIB).

• QUID appelé avec la nouvelle structure montre que les réponses aux questions sont modifiées en fonction des articles rajoutés.

• IMBIB imprime la totalité de la bibliothèque dans le fichier BIBLI. (pour avoir directement le résultat sur télétype il aurait fallu frapper SYSPRINT).

• Enfin, le fichier BIBLI est imprimé sur télétype à l'aide de l'éditeur de texte du système.

Structure élémentaire pour un article :

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

nom des relations :

1 NOM

2 AN

3 PUB

4 NOM AN

5 NOM PUB

6 NOM MC
ESOPE

*EDI SI=BIBLI

**** FRAquez votre texte:

74 ?IMP

1

2

3 AN ALGOL-BASED ASSOCIATIVE LANGUAGE

4 'ACM' '1969'

5

6 AUTEURS:

7 'J.A.FELOMAN'

8 'P.D.ROVNER'

9

10 MOTCLES:

11 'ALGOL'

12 'PROGRAMMING LANGUAGE'

13 'ASSOCIATIVE'

14 'DATA STRUCTURE'

15

16

17 WEIGHTED INCREMENT LINEAR SEARCH FOR SCATTER TABLES

18 'ACM' '1972'

19

20 AUTEURS:

21 'F.LUCCIO'

22

23 MOTCLES:

24 'HASH TABLE'

25 'HASH ADDRESS'

26 'CLUSTERING'

27

28

29 A SURVEY OF DATA STRUCTURES FOR COMPUTER GRAPHICS

30 'COMPUTING SURVEYS' '1971'

31

32 AUTEURS:

33 'R.WILLIAMS'

34

35 MOTCLES:

36 'DISPLAY SYSTEMS'

37 'COMPUTER GRAPHICS'

38 'DATA STRUCTURE'

39

40

41 A GENERAL PURPOSE GRAPHIC LANGUAGE

42 'ACM' '1968'

43

44 AUTEURS:

45 'H.E.KULSRUD'

46

47 MOTCLES:

48 'GRAPHIC LANGUAGE'

49 'INTERACTIVE'

50 'LANGUAGE DESIGN'

51

52

53 DISPLAY PROCEDURES

54 'ACM' '1971'

55

56 AUTEURS:

57 'W.M.NEWMAN'

58

59 MOTCLES:

60 'COMPUTER GRAPHICS'

61 'DISPLAY FILES'

62 'PROGRAMMING LANGUAGE'

63

64

65 GPL/1 A PL/1 EXTENSION FOR COMPUTER GRAPHICS

66 'SJCC' '1969'

67

68 AUTEURS:

69 'D.N.SMITH'

70

71 MOTCLES:

72 'GRAPHIC LANGUAGE'

73 'COMPUTER GRAPHICS'

74 ?FER

ESOPE
*CPL SDI=SDPATH

CPL1 VERSION 8 AVEC AGV ET GRAPHIQUE

:SD001,00 %EXEC(GORECH);

*** ENTREZ LES SOMMETS DE DEPART ET D ARRIVE ***

L:01041,00 A E

IL Y A 5 CHEMINS ENTRE 'A' ET'E'

**********

['A', 'R1', 'B', 'R2', 'C', 'R3', 'D', 'R8', 'E']

['A', 'R1', 'B', 'R7', 'E']

['A', 'R1', 'B', 'R4', 'D', 'R8', 'E']

['A', 'R5', 'D', 'R8', 'E']

['A', 'R5', 'D', 'R9', 'B', 'R7', 'E']

**********

L:01045,00 E A

IL Y A 5 CHEMINS ENTRE 'E' ET'A'

**********

['E', 'R11', 'B', 'R2', 'C', 'R6', 'A']

['E', 'R11', 'B', 'R4', 'D', 'R10', 'C', 'R6', 'A']

['E', 'R12', 'D', 'R9', 'B', 'R2', 'C', 'R6', 'A']

['E', 'R13', 'A']

['E', 'R12', 'D', 'R10', 'C', 'R6', 'A']

**********

L:01045,00 B E

IL Y A 4 CHEMINS ENTRE 'B' ET'E'

**********

['B', 'R2', 'C', 'R3', 'D', 'R8', 'E']

['B', 'R2', 'C', 'R6', 'A', 'R5', 'D', 'R8', 'E']

['B', 'R7', 'E']

['B', 'R4', 'D', 'R8', 'E']

**********

L:01045,00 ''

FIN EXECUTION CPL1

:SD001,00 %EXIT;

ESOPE

*CPL SDI=SDPATH,SDO=SDPATH

CPL1 VERSION 8 AVEC AGV ET GRAPHIQUE

:SD001,00 %EXEC(GOCSTR);

***ENTREZ LE GRAPHE***

L:01044,00 R14 D A

L:01047,00 R15 A C

L:01047,00 R16 E C

L:01047,00 R17 B A

L:01047,00 R18 E C

L:01047,00 '' '' ''

FIN EXECUTION CPL1

:SD001,00 %END;

FIN ANALYSE CPL1 . SANS EXEC

ESOPE
*CPL SOI=SDPATH

CPL1 VERSION 8 AVEC AOV ET GRAPHIQUE

:00001,05 %EXEC(GORECH);

*** ENTREZ LES SOMMETS DE DEPART ET D ARRIVE ***

L:01041,00 A E

IL Y A 7 CHEMINS ENTRE 'A' ET'E'

**********

['A', 'R1', 'B', 'R2', 'C', 'R3', 'D', 'R8', 'E']

['A', 'R1', 'B', 'R4', 'D', 'R8', 'E']

['A', 'R1', 'B', 'R7', 'E']

['A', 'R5', 'D', 'R8', 'E']

['A', 'R5', 'D', 'R9', 'B', 'R7', 'E']

['A', 'R15', 'C', 'R3', 'D', 'R8', 'E']

['A', 'R15', 'C', 'R3', 'D', 'R9', 'B', 'R7', 'E']

**********

L:01045,00 E A

IL Y A 16 CHEMINS ENTRE 'E' ET'A'

**********

['E', 'R11', 'B', 'R2', 'C', 'R3', 'D', 'R14', 'A']

['E', 'R11', 'B', 'R2', 'C', 'R6', 'A']

['E', 'R11', 'B', 'R4', 'D', 'R10', 'C', 'R6', 'A']

['E', 'R11', 'B', 'R4', 'D', 'R14', 'A']

['E', 'R11', 'B', 'R17', 'A']

['E', 'R12', 'D', 'R9', 'B', 'R2', 'C', 'R6', 'A']

['E', 'R12', 'D', 'R9', 'B', 'R17', 'A']

['E', 'R12', 'D', 'R15', 'C', 'R6', 'A']

['E', 'R12', 'D', 'R14', 'A']

['E', 'R13', 'A']

['E', 'R18', 'C', 'R3', 'D', 'R9', 'B', 'R17', 'A']

['E', 'R18', 'C', 'R3', 'D', 'R14', 'A']

['E', 'R18', 'C', 'R6', 'A']

['E', 'R16', 'C', 'R3', 'D', 'R9', 'B', 'R17', 'A']

['E', 'R16', 'C', 'R3', 'D', 'R14', 'A']

['E', 'R16', 'C', 'R6', 'A']

**********

L:01045,00 B E

IL Y A 6 CHEMINS ENTRE 'B' ET'E'

**********

['B', 'R2', 'C', 'R3', 'D', 'R8', 'E']

['B', 'R2', 'C', 'R6', 'A', 'R5', 'D', 'R8', 'E']

['B', 'R7', 'E']

['B', 'R17', 'A', 'R5', 'D', 'R8', 'E']

['B', 'R4', 'D', 'R8', 'E']

['B', 'R17', 'A', 'R15', 'C', 'R3', 'D', 'R8', 'E']

**********

L:01045,00 ''

FIN EXECUTION CPL1

:00001,00 %EXIT;

ESOPE
V - CONCLUSION

Les objectifs initiaux, à savoir une structure de données générale
implantée de façon efficace et manipulée par un langage clair et puissant
ont été atteints.

Diverses applications réalisées à l'aide du système METAVISU
montrent que les choix effectués tant du point de vue du langage que de
l'implantation sont satisfaisants.

Bien qu'ayant été initialement conçus pour répondre aux nécessités
d'un système graphique, le langage et sa structure de données associative nous
paraissent suffisamment puissants et généraux pour faciliter la résolution
de problèmes dans d'autres domaines tels que l'intelligence artificielle,
la documentation automatique.....
REFERENCES

[1] P. BOULLIER, J. GROS, P. JANCENE, A. LEMAIRE, F. PRUSKER, E. SALTEL.
"METAVISU A general purpose graphic system",
IFIP Working Conference on graphic languages,
University of British Columbia
Vancouver, Canada, May 1972

[2] J.A. FELDMAN, P.D. ROVNER.
"An Algol based Associative language",
Comm. ACM, V 12, n° 8, August 1969.

[3] F. BLAIZOT, L. BLAIZOT, B. LORHO, M. VATOUX.
"Organisation du compilateur interpréteur CPL/1",
Congrès AFCET, Paris, Septembre 1970.

[4] A.J. SYMONDS.
"Auxiliairy storage associative data structure for PL/1",
IBM syst. Journal n° 3 & 5, 1968.

[5] C. BETOURNE, J. BOULENGER, C. KAISER, J. FERRIE, S. KRAKOWIAK, J. MOSSIERE.
"Process Management and resources sharing in the multi access
system ESOPE",
Comm. ACM V 13, n° 12, December 1970.