# Sur l'interprétation des schémas de programmes monadiques

Maurice Nivat

► To cite this version:

Maurice Nivat. Sur l'interprétation des schémas de programmes monadiques. [Rapport de recherche] IRIA-RR-001, IRIA. 1972, pp.19. hal-04715998

HAL Id: hal-04715998

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

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
RIA
laboria

Institut de Recherche
d'Informatique
et d'Automatique

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

laboratoire de recherche
en informatique
et automatique

ARCHIVES

# Sur l'interprétation des schémas de programmes monadiques

Maurice Nivat

19P

Rapport de Recherche n° 1
décembre 1972
SUR L'INTERPRÉTATION DES SCHÉMAS DE PROGRAMMES MONADIQUES

M. Nivat

Le présent article constitue une tentative de définition algébrique de la fonction calculée par un schéma de programme, recursif ou non, pour une interprétation donnée. Une construction analogue à la nôtre fait l'objet de l'article de DANA SCOTT "Lattice of flow diagrams" [5] qui a été la principale source d'inspiration pour notre travail. Mais si la construction que l'on trouvera dans ces pages et celle de DANA SCOTT conduisent à des définitions identiques, elles sont pourtant d'inspirations différentes dans la mesure où les structures algébriques mises en jeu ne sont pas les mêmes. Ce que nous avons surtout voulu faire, c'est expliciter l'analogie formelle entre schémas de programmes et systèmes d'équations algébriques, et de ce fait l'accent se trouve déplacé de la structure d'ordre qui sous-tend la construction de DANA SCOTT, vers la structure de magma dont se trouve muni l'ensemble des schémas de programme.

C'est très naturellement que nous sommes alors conduits à généraliser la règle de recopie utilisée par les auteurs du langage ALGOL 60 [3] pour définir la sémantique des procédures récursives.

Le présent travail n'est qu'une ébauche dont nous prions le lecteur d'excuser les imperfections. C'est aussi le début d'une plus longue étude, la construction ci-dessous se généralisant aux schémas non monodiques. A ce propos, nous terons à remercier Mademoiselle Irène GUESSARIAN qui tout en travaillant à cette généralisation, nous a été d'un précieux conseil dans la rédaction du présent article.
# PREMIERE PARTIE

## 1 - MAGMA LIBRE

Dans ce qui suit une loi de composition sur un ensemble $M$ est le couple formé d'un entier $n$ dit arité de la loi et d'une application $b$ de $M^n$ dans $M$.

Nous appellerons magma tout ensemble muni d'un certain nombre de lois de composition. Plus précisément si $B = \{ (n_i, b_i) \mid i \in I \}$ est un ensemble de lois de composition sur $M$, c'est-à-dire si pour tout $i \in I$ $b_i$ est une application de $M^i$ dans $M$ nous dirons que $M$ est un $B$ magma.

L'application $\varphi$ de $M$ dans $M'$, où $M$ et $M'$ sont deux $B$-magnas est un morphisme de $B$-magma si et seulement si pour tout $i \in I$: $b_i \circ \varphi^{n_i} = \varphi^{n_i} \circ b_i$ (en notant $\varphi^n$ l'application de $M^n$ dans $M'^n$ qui applique

$$ (m_1, m_2, \dots, m_n) \in M^n \text{ sur } (\varphi(m_1), \dots, \varphi(m_n)) \in M' $$

Les faits suivants sont bien connus :

- Si $B$ est un ensemble de lois de composition et $F$ un ensemble quelconque, il existe un $B$ magma unique à un isomorphisme près, soit $M$ ($F$, $B$) tel que toute application $\pi$ de $F$ dans un $B$-magma $M'$ se prolonge de façon unique en un morphisme de $M$ ($F$, $B$) dans $M'$.

$M$ ($F$, $B$) est le $B$ magma libre engendré par $F$.
Considérons l'ensemble des expressions, noté $\overline{M}$ (F,B) que l'on définit au moyen des trois règles :

a - tout élément $f \in F$ est une expression .

b - si $\Sigma_1, \dots, \Sigma_{n_i}$ sont des expressions, $(b_i, \Sigma_1, \dots, \Sigma_{n_i})$ est une expression, point tout $i \in I$ .

c - Il n'y a pas d'autres expressions que celles que l'on peut former au moyen des règles a et b .

$\overline{M}$ (F,B) est aussi le langage engendré par la grammaire algébrique :

$$ S = \bigcup_{i \in I} \left( \bigwedge_{n_i} (b_i, S, \dots, S) + F \right) $$

sur l'alphabet X formé de la réunion de F, de l'ensemble des symboles $\{ b_i \mid i \in I \}$ et des signes de ponctuation "( ", " )" et ", " .

Clairement $\overline{M}$ (F,B) est un B magma : l'application $b_i$ de $\overline{M}$ (F,B) $^{n_i}$dans $\overline{M}$ (F,B) applique

$(\Sigma_1, \dots, \Sigma_{n_i}) \in \overline{M} (F,B)^{n_i}$ sur l'expression $(b_1, \Sigma_1, \dots, \Sigma_{n_i})$ .

Et toute application $\pi$ de F dans un B magma M' se prolonge en un morphisme de $\overline{M}$ (F,B) dans M' en posant

$$ \pi (b_i, \Sigma_1, \dots, \Sigma_{n_i}) = b_i (\pi (\Sigma_1), \dots, \pi (\Sigma_{n_i})) . $$

Ainsi $\overline{M}$ (F,B) est isomorphe au B magma libre (F,B) engendré par F. Nous identifierons ces deux objets dans la suite, ou du moins utiliserons indifféremment M (F,B) et $\overline{M}$ (F,B) pour désigner le B magma libre engendré par F .

Une autre identification utile dans la suite est celle de M (F,B) avec l'ensemble des arbres étiquetés et ordonnés tels que

a - tout sommet pendant est étiqueté par un élément de F.

b - tout sommet non pendant est étiqueté par un symbole $b_i \in B$ et si un tel sommet est étiqueté par $b_i$ son demi-degré extérieur est exactement $n_i$ .
c- L'ensemble des successeurs de chaque sommet est ordonné.

Nous définissons maintenant certaines familles remarquables de parties du magma libre.

## 2 - LANGAGES ALGÉBRIQUES SUR UN MAGMA LIBRE

Nous définissons une grammaire algébrique sur le magma libre $M(F,B)$ comme un système d'équations de la forme
$$ \sum_i \begin{cases} \xi_i = \rho_i \\ i = 1, \dots, N \end{cases} $$

où $\Theta = \{\xi_1, \dots, \xi_N\}$ est un ensemble de variables et pour tout $i = 1, \dots, N$, $\rho_i$ est une partie finie du magma libre $M(F \cup \Theta, B)$.

Nous appelons solution d'une telle grammaire tout $N$-uple de parties de $M(F,B)$, soit $\sigma = <\sigma_1, \dots, \sigma_N>$ satisfaisant les deux conditions :

$$ 1 - \sigma_i = \text{Sub}_{\sigma} \xi_i \rho_i \text{ pour tout } i = 1, \dots, N. $$

$$ 2 - \text{Pour tout } N \text{ - uple } \sigma' \text{ de parties de } M(F,B) \text{ satisfaisant la condition } 1 \text{ on a} $$

$$ \sigma_i \subseteq \sigma'_i \text{ pour tout } i = 1, \dots, N. $$

L'écriture $\text{Sub}_{\sigma} \xi_i \rho_i$ dénote le sous-ensemble de $M(F,B)$ obtenu en substituant, pour tout $j = 1, \dots, N$, $\sigma_j$ à chaque des occurences de $\xi$ ; dans $\rho_i$.

La condition 1 est une condition de stabilité de $\sigma$ pour $\sum_i \sigma'_i = \sum_i \xi_i \rho_i$.
plus précisément elle exprime le fait pour $\sigma$ d'être un point fixe de l'application $\hat{\sum} \text{ de } (M(F,B))^N$ dans lui-même défini par
$$ \hat{\sum} (\sigma) = \langle \text{Sub}_{\sigma} \xi_i \rho_i \rangle. $$

La condition 2 est une condition de minimilté pour l'ordre produit sur $(M(F,B))^N$ de l'ordre par inclusion dans $M(F,B)$.
On peut établir ainsi l'existence d'une solution unique pour toute grammaire algébrique sur un magma libre, soit en faisant appel au théorème du point fixe pour les treillis, soit plus simplement en
utilisant le théorème se SCHUTZENBERGER [4] établissant l'existence d'une
solution unique pour toute grammaire algébrique sur un monoïde libre. En
effet nous avons identifié M (F,B) à une partie d'un monoïde libre X*,:
la grammaire Σ peut alors être considérée comme une grammaire algébrique
sur X*, et chaque solution de Σ sur M (F,B) est aussi une solution sur X*
Réciproquement, toute solution sur X* est une solution sur M (F,B) en
vertu de la propriété suivante :

$$
\bigvee_{i} e_{1}, \ldots, e_{n_{i}} \in \bar{M}(F,B), b_{i} \in B \\
(b_{i}, e_{1}, \ldots, e_{n_{i}}) \in M(F,B) \Rightarrow e_{1}, \ldots, e_{n_{i}} \in \bar{M}(F,B)
$$

Nous pouvons énoncer le

**THEOREME 1** - Toute grammaire algébrique sur un magma libre admet une solution unique.

Le même théorème de SCHUTZENBERGER établit que cette solution
n'est autre que le N - uple < L(Σ, ξ₁), ..., L (Σ, ξN) > où l'on
définit L (Σ, ξᵢ) de la façon suivante :

- Posons pour tout $f, f' \in (X \cup \Theta)^*$
$f \to f' \Leftrightarrow \exists u \in X^*, v \in (X \cup \Theta)^*, i \in [1,N], g \in \rho_i$.
tels que $f = u \xi_i v, f' = u g v$.

- Dénotons par $\underset{\Sigma}{\stackrel{*}{\to}}$ la fermeture réflexive et transitive de $\Sigma$

- Pour tout $f \in (X \cup \Theta)^*$ nous posons

$$
L (\Sigma, f) = \{ g \in X^* \mid f \stackrel{*}{\to} g \}
$$

Ainsi $L(\Sigma, \xi_i)$ n'est autre que le langage engendré par la grammaire $\Sigma$
avec $\xi_i$ comme axiome.

Nous ne nous étendrons pas sur les grammaires algébriques et les langages
algébriques qu'elles engendrent sur un magma dans la mesure où c'est un
sous-ensemble de ces langages qui va désormais retenir notre attention.
## 3 - LANGAGES SCHEMATIQUES SUR UN MAGMA LIBRE

Nous supposerons désormais que $F$ contient un élément distingué noté $\Omega$ et dont la signification sera explicitée dans la suite. Cet élément $\Omega$ nous permet de définir une relation d'ordre sur $M(F,B)$, relation la plus grossière compatible avec les opérations de $B$-magma telle que $\Omega \} f$ pour tout $f \in F$.

Intuitivement si $m$ et $m'$ sont deux éléments du magma $M(F,B)$ m $\{ m'$ si et seulement si $m'$ est obtenu en substituant certains éléments de $M(F,B)$ à certaines occurences de $\Omega$ dans $m$.

Une grammaire algébrique sur $M(F,B)$ est dite schématique si et seulement si elle est de la forme

$$ \Sigma \quad \left\{ \begin{array}{l} \xi_i = \rho_i + \Omega \\ i = 1, \dots, N \end{array} \right. $$

où $\rho_i$ est un élément de $M(F \cup \Theta, B)$ et non plus une partie finie.

L'ensemble des composantes des solutions de grammaires schématiques est noté $\text{Sch}(M(F,B))$, ses éléments étant appelés ensembles, ou langages schématiques sur $M(F,B)$.

Une propriété importante de ces ensembles joue un rôle fondamental dans ce qui suit :

**THEOREME 2** - Si $L$ est un langage schématique sur $M(F,B)$, deux éléments quelconques de $L$ ont dans $M(F,B)$ une borne supérieure et une borne inférieure (pour l'ordre défini ci-dessus) et ces deux bornes appartiennent à $L$.

### DEMONSTRATION

Supposons $L = L(\Sigma, \xi_1)$ où $\Sigma$ est le système schématique

$$ \Sigma \quad \left\{ \begin{array}{l} \xi_i = \rho_i + \Omega \\ i = 1, \dots, N \end{array} \right. $$
Nous montrons tout d'abord que pour tout $f \in (X \cup \Theta)^*$ et pour tout $\pi, m' \in L(\Sigma_1 f)$ il existe

$\alpha_0, \dots, \alpha_k, \beta_1, \dots, \beta_{k'}, \beta'_1, \dots, \beta'_k \in X^*$ satisfaisant

$$ - m = \alpha_0 \beta_1 \alpha_1 \beta_2 \dots \alpha_{k-1} \beta_h \alpha_k $$

$$ - m' = \alpha_0 \beta'_1 \alpha_1 \beta'_2 \dots \alpha_{k-1} \beta'_h \alpha_k $$

pour tout $h = 1, \dots, k$, $\beta_h$ ou $\beta'_h$ et un seul des deux est égal à $\Omega$.

Considérons pour ce faire les deux dériva\^tions (gauches) de $m$ et $m'$ dans $\Sigma$ soient

$$ f \rightarrow m_1 \rightarrow m_2 \rightarrow \dots \rightarrow m_h = m $$

$$ f \rightarrow m'_1 \rightarrow m'_2 \rightarrow \dots \rightarrow m'_h = m' $$

Si $m = m'$ il suffit de prendre $\alpha_0 = m = m'$ sinon il existe un plus petit entier $\ell$ tel que

$$ m_{\ell} = m'_{\ell}, \quad m_{\ell+1} \neq m'_{\ell+1}, \quad \ell < k. $$

On peut alors écrire $m_{\ell} = m'_{\ell} = \alpha_0 \xi_i \alpha_i$, où
$\alpha_0 \in X^*, \xi_i \in \Theta, \alpha' \in (X \cup \Theta)^*$ et certainement

$$ \underline{\text{soit}} \qquad m_{\ell+1} = \alpha_0 \rho_j \alpha', \quad m'_{\ell+1} = \alpha_0 \Omega \alpha' $$

$$ \underline{\text{soit}} \qquad m_{\ell+1} = \alpha_0 \Omega \alpha' \quad \dots \quad m'_{\ell+1} = \alpha_0 \rho_j \alpha' $$

(car $m_{\ell+1}$ et $m'_{\ell+1}$ sont obtenus en dérivant $\xi_j$ et ceci ne peut se faire que de deux façons par la forme même d'un système schématique).

Mais alors si $m_{\ell+1} = \alpha_0 \rho_j \alpha'$ (resp $m'_{\ell+1} = \alpha_0 \rho_j \alpha'$) on a
$m = \alpha_0 \beta_1 \alpha'$ (resp $m' = \alpha_0 \beta'_1 \alpha'$) où $\beta_1$ (resp $\beta'_1$) dérive de
$\rho_j$ dans $\Sigma$. La démonstration s'achève aisément par récurrence puisque
$m = \alpha_0 \beta_1 \bar{m}$, $m' = \alpha_0 \Omega \bar{m}'$ ou $m = \alpha_0 \Omega \bar{m}$ et $m' = \alpha_0 \beta'_1 \bar{m}'$
où dans l'un et l'autre cas $\bar{m}$ et $\bar{m}'$ dérivent de $\alpha'$ dans $\Sigma$, c'est-à-dire $\bar{m}, \bar{m}' \in L(\Sigma, \alpha')$.

La borne inférieure $m \le \Lambda m'$ et la borne supérieure $m \ge \Lambda m'$ de $m$
et $m'$ s'en déduisent immédiatement :

$$ m \Lambda m' = \alpha_0 \Omega \alpha, \quad \Omega \dots \alpha_{h-1} \Omega \alpha_h $$
$m \ V \ m' = \alpha_o(\beta_1 \ V \beta_1') \alpha_1(\beta_2 \ V \beta_2') \dots \alpha_{h-1}(\beta_{h-1} \ V \beta_{h-1}') \alpha_h(\beta_h \ V \beta_h')$ est égal à celui des $\beta_h \ \beta_{h'}$ qui n'est pas $\Omega$)

et l'on voit que $m \ \Lambda \ m'$ et $m \ V \ m'$ appartiennent bien à $L$.

Une autre importante propriété de Sch ($M(F,B)$) est la
**PROPRIETE 1** - Sch ($M(F,B)$) constitue un $B$-magma.
En effet si pour tout $b_i \in B$, $s_1, \dots, s_{n_i} \in \text{Sch}(M(F,B))$ l'on
définit

$(b_i, s_1, \dots, s_{n_i}) = \Omega + \{ (b_i, e_1, \dots, e_{n_i}) \mid e_j \in s_j \}$
on vérifie immédiatement que si

$s_j = L (\sum_j \xi_j^{(i)})$ pour tout $j = 1, \dots, n_j$ on a

$(b_i, s_1, \dots, s_{n_i}) = L (\sum_j \xi_j)$ où $\sum_j$ est la grammaire formée de la réunion des grammaires $\sum_j$ (supposées utiliser des ensembles de variables dis-joints) et de l'équation

$$ \xi_1 = (b_i, \xi_1, \dots, \xi_1^{(n_i)}) + \Omega . $$

Découle également d'un théorème classique de la théorie des langages algébriques ( théorème de substitution cf. S. GINSBURG [1] ) une propriété de clôture que l'on peut énoncer.

**PROPRIETE 2** - Sch ( Sch ($M(F,B)$), $B \supseteq$ Sch ($M(F,B)$)

Si l'on considère en effet une grammaire schématique sur Sch $M(F,B)$
c'est-à-dire une grammaire :

$$ \Sigma: \left\{ \begin{array}{l} \xi_i = \rho_i + \Omega \\ i = 1, \dots, N \end{array} \right. $$

où pour tout $i = 1, \dots, N$ $\rho_i \in M$ Sch($M(F,B)$) $\cup \Theta$, $B$)
on peut former, en se munissant d'un alphabet Y en correspondance
biunivoque avec les éléments de Sch($M(F,B)$) figurant dans l'un au moins
des $\rho_i$, une grammaire $\Sigma'$, schématique sur $M(Y,B)$ telle que pour tout $i$ :
$L(\Sigma, \xi_i)$ est obtenu en substituant dans $L(\Sigma', \xi_i)$ à chaque
$\eta \in Y$ l'ensemble schématique correspondant.
# DEUXIEME PARTIE

## 1 - SCHEMAS DE PROGRAMME

Nous utiliserons les trois ensembles finis de symboles.

F - dont les éléments sont dits symboles de fonctions et parmi lesquels nous distinguerons l'élément $\xi_1$ (identité).

B - dont les éléments sont dits symboles de prédicats.

Θ - dont les éléments sont provisoirement appelés variables, et parmi lesquels $\xi_1$ joue un rôle particulier.

Nous appelons instruction toute expression de l'une des trois formes suivantes :

$$ \xi = \alpha \text{ où } \xi \in \Theta \alpha \in F $$

$$ \xi = (\alpha_1 ; \alpha_2) \text{ où } \xi \in \Theta, \alpha_1, \alpha_2 \in F \cup \Theta $$

$$ \xi = (b \rightarrow \alpha_1 | \alpha_2) \text{ où } \xi \in \Theta, b \in B, \alpha_1, \alpha_2 \in \Theta $$

Soit S un ensemble d'instructions : un chemin allant de $\xi$ à $\xi'$ dans S est une suite $s_1, \dots, s_l$ d'instructions de S telle que pour tout $h = 2, \dots, l$ la variable figurant au membre gauche de $s_h$ ait une occurence dans le membre droit de $s_{h-1}$, $s_h$ ait pour membre gauche et $l$ ait une occurence dans le membre droit de $s_l$.

L'ensemble S est alors appelé schéma de programme sur F et B si et seulement si les deux conditions suivantes sont vérifiées :

a - toute variable $\xi$ de $\Theta$ apparaît une fois et une seule comme membre gauche d'une instruction de S.

b - il existe au moins un chemin allant de $\xi_1$ à $\xi$ dans S pour tout $\xi \in \Theta$.

Nous distinguons encore entre plusieurs types de schémas :
- le schéma S est dit non récursif si et seulement si toutes les instructions de la forme $\xi = (\alpha_1 ; \alpha_2)$ vérifient la condition $\alpha_1 \in \mathbb{F}_{e+\alpha_2}^\theta$.

- le schéma S, non récursif, est dit sans boucle si et seulement si il existe au plus un chemin allant de $\xi_1$ à $\xi$ dans S pour tout $\xi \in \Theta$.

Les schémas de programme sont destinés à être interprétés, une interprétation I du schéma S étant constitué par la donnée

- d'un domaine D non vide.

- pour tout $f \in \mathbb{F}$ d'une application partielle $f_I$ de D dans lui-même. Nous considèrerons en fait $f_I$ comme une application de $D \cup \Theta$ dans lui-même en posant $f_I(\Theta) = \Theta = f_I$ (d) pour tout $d \in D$ où $f_I$ n'est pas défini.

L'application $\eta_I$ est par définition l'identité sur $D \cup \Theta$.

- pour tout $b \in B$ d'une application partielle de D dans l'ensemble $\{0,1\}$ des valeurs de vérité. De la même façon $b_I$ est étendu en une application de $D \cup \Theta$ dans $\{0,1, \Theta\}$.
Le couple $(S, I)$ formé d'un schéma S et d'une interprétation I de S constitue un programme que nous définissons en utilisant un langage proche d'ALGOL 60 [ 3], en établissant les correspondances suivantes :

- si S est non récursif, l'instruction $\xi = (\alpha_1 ; \alpha_2)$ est remplacé par $\xi : \tilde{\alpha}_1 ; \tilde{\alpha}_2$ ; où $\xi$ est une étiquette et $\tilde{\alpha}$ est l'instruction $x := f_I(x)$ si $\alpha = f \in \mathbb{F}$ et l'instruction *aller à* $\xi'$ si $\alpha = \xi' \in \Theta$.

L'instruction $\xi = (b \to \alpha_1 | \alpha_2)$ est remplacée par $\xi :$ si $b_I(x)$ *alors* $\tilde{\alpha}_1$ *sinon* $\tilde{\alpha}_2$;

- si S est récursif les variables correspondent au contraire à des
procédures à un paramètre x et l'on fait correspondre à

$\xi = (\alpha_1; \alpha_2)$ la procédure .

proc $\xi(x)$, début $\bar{\alpha}_1$ ; $\bar{\alpha}_2$ fin où

$\bar{\alpha}$ est l'instruction $x := f_I(x)$ si $\alpha = f \in F$

et l'instruction $x := \xi'(x)$ si $\alpha = \xi' \in \Theta$.

A l'instruction $\xi = b \to \alpha_1$ | $\alpha_2$ on fait correspondre

proc $\xi(x)$; début si $b_I(x)$ alors $\bar{\alpha}_1$ sinon $\alpha_2$ fin ;

Dans le premier cas ( S non récursif) l'on rajoute comme première instruction **aller à** $\xi_1$ ;

dans le second cas, le programme se compose, outre les déclarations de procédures, de la seule instruction $x := \xi_1(x)$.

Grâce alors aux règles de la sémantique du langage ALGOL 60, que nous supposerons connues du lecteur, l'on peut définir le calcul du programme <S, I> pour une valeur initiale $d \in D \cup \Omega$ et définir la fonction calculée par <S,I> soit $S_I$. Sa valeur au point d est le résultat du calcul de <S,I> pour d si celui-ci se termine, ou, par définition, $\Omega$, si ce même calcul ne se termine pas. Le but de cet article est en fait de donner une définition précise et formée de la fonction $S_I$, valable dans tous les cas.

Pour ce faire il convient tout d'abord de remarquer que l'ensemble des schémas de programme sur F et B constitue un B'-magma où B' est l'ensemble de lois de composition formée.

- du produit noté $(m; m')$

- pour chaque $b \in B$ d'une $b$ - somme notée $(b \to m \mid m')$

Si S et S' sont deux schémas du programme sur F et B c'est-à-dire deux ensembles d'instruction satisfaisant aux conditions voulues et utilisant les unes l'ensemble de variables

$\emptyset$, les autres l'ensemble de variables $\emptyset$' supposé disjoint de

$\emptyset$ (ce qui est loisible, la dénomination des variables étant arbitraire)
on définit

( S; S') comme $S \cup S' \cup \{ \xi'' = ( \xi_1; \xi_1' ) \}$

( b → S | S' ) comme $S \cup S' \cup \{ ( \xi'' \to \xi_1 | \xi_1' ) \}$

qui sont bien des schémas de programme sur F et B, avec comme ensemble
de variables $\Theta'' = \Theta \cup \Theta'$ u $\{ \xi_1'' \}$.

D'autre part les règles de la semantique d'ALGOL 60 auxquelles nous
venons de faire appel pour définir $S_I$ assurent que l'on a, pour tout couple
S, S' de schémas de programme, toute interprétation I de S et S' dans
un domaine D et tout $d \in D$

$(S, S')_I (d) = S'_I (S_I (d))$

$(b \to S | S')_I (d) = \underline{si} \ b_I (d) = 1 \ \underline{alors} \ S_I (d) \ \underline{sinon} \ S_I^i (d)$

$(b \to S | S')_I (d) = \Omega \ si \ b_I (\bar{d}) = \Omega,$

ceci conformément a la règle qui veut que dans l'évaluation d'une expression
conditionnelle l'on évalue toujours en premier la condition (et si donc cette
évaluation ne se termine pas, l'expression conditionnelle n'est pas définie).
Une autre façon d'exprimer ces conditions est la suivante.

Munissons l'ensemble des applications de $D \cup \Omega$ dans lui-même de la
structure de B' - magma défini par

$(\varphi; \varphi') = \varphi \circ \varphi' \text{ où } \varphi \circ \varphi' \text{ dénote le produit de composition habituel.}$

$(b \to \varphi | \varphi') = \underline{\text{cond}} ( b_I, \varphi, \varphi') \text{ où } \text{cond} \text{ est l'application de}$
$\{ 0,1, \Omega \} \times (D \cup \Omega) \times (D \cup \Omega) \text{ dans } (D \cup \Omega)$

donnée par

$\underline{\text{cond}} ( \Omega, d, d' ) = \Omega$

$\underline{\text{cond}} ( 1, d, d' ) = d$

$\underline{\text{cond}} ( 0, d, d' ) = d'$

Notons $D_I$ l'ensemble des applications de $D \cup \Omega$ dans lui-même muni de cette structure de B' - magma (structure qui dépend de I).

La remarque faite plus haut devient alors :
l'application I qui fait correspondre à tout schéma de programme S la fonction $S_I$ calculée par S pour l'interprétation I est un morphisme du B' - magma des schémas de programme dans $D_I$.

C'est cela qui va nous permettre de définir cette correspondance I, en commençant par le cas particulier des schémas de programme sans boucle.

## 2 - INTERPRETATION DES SCHEMAS DE PROGRAMME SANS BOUCLE

Il est clair qu'à chaque schéma de programme sans boucle correspond un arbre étiqueté et ordonné satisfaisant les deux conditions
- tout sommet de $\frac{1}{2}$ degré extérieur égal à 0 ou 1 est étiqueté par un élément de F.

- tous les autres sommets sont de $\frac{1}{2}$ degré extérieur égal à 2 et sont étiquetés par des éléments de B.

Cet arbre est celui que l'on forme avec comme ensemble de sommets $\Theta$ :
si $\xi \in \Theta$ est le membre gauche d'une instruction de la forme
$$ \xi = (\alpha_1 ; \alpha_2) $$
, le sommet $\xi$ est étiqueté par $\alpha_1$ et relié par un arc au seul sommet $\alpha_2$ si $\xi \in \Theta$ est au contraire le membre gauche d'une instruction $\xi = (b \to \alpha_1 | \alpha_2)$, le sommet $\xi$ est étiqueté par b et relié aux deux sommets $\alpha_1$ et $\alpha_2$ dans cet ordre.
Réciproquement à tout arbre de cette forme correspond un schéma sans boucle ou plutôt plusieurs qui ne diffèrent que par la dénomination des sommets ( on ne considèrera de tels schémas comme différents).

En vertu d'une remarque faite plus haut, on peut énoncer :

### PROPRIETE 3 -

L'ensemble des schémas de programme sans boucles sur F et B n'est autre que le B' magma libre engendré par F.

Mais l'application I de F dans $D_I$ s'étend de façon unique en un morphisme, que nous noterons également I, du B' - magma libre engendré
par F dans $D_I$. Ainsi fait-on correspondre à tout schéma de programme sans boucles S l'application $S_I$ de $D \cup \Omega$ dans lui-même, dont le lecteur se convaincra sans peine que c'est bien la fonction calculée par S , au sens de la semantique d'ALGOL 60 évoquée plus haut. Nous énoncerons

**THEOREME 3** - Une interprétation I de l'ensemble des schémas de programme sur F et B dans le domaine D définit un morphisme de B' - magma de l'ensemble des schémas de programme sans boucle sur F et B dans le B' - magma $D_I$ des applications de $D \cup \Omega$ dans lui-même :

Nous achèverons ce paragraphe en montrant une importante propriété qui suppose qu'au préalable soit défini un ordre sur $D_I$. Disons que $\varphi \in D_I$ est une extension de $\varphi \in D_I$ si et seulement si pour tout $d \in D$ :

$$ - \varphi' (d) = \Omega \Leftrightarrow \varphi \quad (d) = \varphi' (d) $$

$$ - \varphi (d) = \Omega \Leftrightarrow \varphi' (d) = \Sigma \cdot $$

Intuitivement $\varphi$ est une extension de $\varphi'$ si elle est "plus définie" que $\varphi'$ c'est-à-dire égale à $\varphi'$ en tout point où celle-ci est définie (c'est-à-dire à une valeur différente de $\Omega$), $\varphi$ pouvant être définie en certains points où $\varphi'$ ne l'est pas.

Nous noterons $\varphi' \leq \varphi$ si et seulement si $\varphi$ est une extension de $\varphi'$. Il est immédiat que $\leq$ est bien une relation d'ordre compatible avec la structure de B' - magma de $D_I$. En effet $\varphi_1' \leq \varphi_1$ et $\varphi_2' \leq \varphi_2$

$$ \text{impliquent bien} \quad (\varphi_1', \varphi_2') \leq (\varphi_1 ; \varphi_2) $$

$$ \text{et pour tout } b \in B \in B \quad (b \to \varphi_1' | \varphi_2') \leq (b \to \varphi_1 | \varphi_2) $$

D'autre part nous étendrons le morphisme $I$ de $M(F, B')$ dans $D_I$ en un morphisme de $M(F \cup \Omega, B')$ dans $D_I$ en posant $\Omega_I(d) = \Omega$ pour tout $d \in D$ (ce qui fait de $\Omega_I$ la fonction constante égale à $\Omega$ sur $D \cup \Omega$). Rappelons que $M(F \cup \Omega, B')$ est un magma ordonné par la relation $\} \text{définie plus haut.}$
**PROPRIETE 4** - Le morphisme $I$ de $M(F \cup \Omega, B')$ dans $D_I$ préserve l'ordre.

En effet les ordres sur $M(F \cup \Omega, B')$, $B'$ magma libre engendré par $F \cup \Omega$ et sur $D_I$ sont compatibles avec la structure de $B'$-magma de ces deux ensembles. Il suffit alors de vérifier que $I$ préserve l'ordre sur $F \cup \Omega$, le morphisme $I$ étant entièrement déterminé par sa restriction à $F \cup \Omega$. Or pour tout

$f, f' \in F \cup \Omega, f \} f' \Rightarrow f = \Omega$ ou $f = f'$
comme $\Omega_I$ est la fonction constante égale à $\Omega$ sur $D_I \cup \Omega$, tout élément de $D_I$ en est une extension et par suite si $f = \Omega$ on a bien

$$f_I \le f'_I$$

Si $f = f'$ aussi $f_I \le f'_I$ trivalement.

**REMARQUE :** Les schémas de programme sur $F$ et $B$ sont un sous ensemble des schémas de programme sur $F' = F \cup \Omega$ et $B$ où $\Omega$ est l'élément indéfini, toujours interprété comme la fonction dont le domaine de définition est vide. Nous aurions pu définir directement les schémas de programme sur $F'$ et $B$ sauf à heurter quelques habitudes : nous avons préféré faire sentir progressivement la nécessité de l'élément $\Omega$ mise en lumière depuis longtemps par de nombreux auteurs et dont l'emploi a été systématisé par D. SCOTT [5].

## 3 - INTERPRETATION DES SCHEMAS DE PROGRAMME

Cette interprétation repose tout entière sur le **THEOREME 4** - Le morphisme $I$ de $M(F', B')$ dans $D_I$ se prolonge en un morphisme de Sch $(M(F', B'))$ dans $D_I$.

**DEMONSTRATION** - Soit $L \in \mathrm{Sch}(M(F', B'))$. En vertu du théorème 2, pour tout $m, m' \in L$ il existe $m'' \in L$ tel que $m m''$ et $m' m''$ (on prend $m'' = m \cup m'$).

Le morphisme $I$ préservant l'ordre on a

$$m_I \le m_I'' \text{ et } m_I' \le m_I''$$
d'où en revenant à la définition,

$m_I(d) \neq \Omega$ et $m'_I(d) \neq \Omega$ impliquent

$m_I(d) = m''_I(d) \neq m'_I(d)$

Ainsi on peut poser $L_I(d) = m_I(d)$ si il existe $m \in L$ tel que

$m_I(d) \neq \Omega$ et $L_I(d) = \Omega$ dans le cas contraire.

Il ne reste qu'à vérifier que l'application $I$ ainsi prolongée est bien un morphisme de Sch (M(F', B')) dans $D_I$.

Or $(L,L') = \{ (m,m') | m \in L, m' \in L' \}$

d'où $(L;L')_I(d) = (m_I, m'_I)(d)$ s'il existe $m \in L, m' \in L'$ tel que $(m_I; m'_I)(d) \neq \Omega$.

$(L;L')_I(d) \neq \Omega$ dans le cas contraire.

Dans le premier cas $(m_I; m'_I)(d) = d'$ s'écrit encore

$(m_I, m'_I)(d) = d'$ ou $m'_I(m_I(d)) = d'$ et

par suite il existe $d'' \neq \Omega$ tel que $m_I(d) = d'' m'_I(d'') = d$.

On a alors $L_I(d) = d'', L'_I(d'') = d'$ et

$(L;L')_I(d) = (L_I \circ L'_I)(d)$

Si au contraire $(m_I; m'_I)(d) = \Omega$ pour tout $m \in L$ et $m' \in L'$ ou bien il existe un $m \in L$ tel que $m_I(d) = d' \neq \Omega$ et certainement pour tout $m' \in L'$ $m'_I(d') = \Omega$ ou bien pour tout $m \in L$ $m_I(d) = \Omega$.

Dans l'un et l'autre cas nous avons encore

$(L;L')_I(d) = (L_I \circ L'_I)(d)$.

C Q F D

Il suffit maintenant d'établir un morphisme de l'ensemble des schémas de programme sur F et B dans Sch (M(F',B')) pour obtenir le morphisme cherché I de ce même ensemble dans $D_I$. Pour cela si S est un schéma de programme, c'est-à-dire un ensemble d'instructions de la forme décrite ci-dessus, on forme une grammaire schématique S aisément à partir de S en remplacant toute instruction $\xi = \alpha$ de S par l'équation

$$ \xi = \alpha + \Omega $$

L'application qui fait correspondre à S la première composante S de la solution de S est le morphisme cherché.
Nous laissons le lecteur se convaincre que $S_I$, ainsi rigoureusement défini, est
bien la même fonction que la fonction $S_I$ définie au moyen des régles de la
sémantique d'ALGOL 60.

En fait, d'après un théorème de Mac NAUGHTON [2] le morphisme de
l'ensemble des schémas de programme sur $M(F',B)$ dans Sch($M(F',B)$) est un
isomorphisme si l'on ne considère que les schémas propres (tels qu'ils ne
contiennent pas deux instructions de la forme $\xi = \alpha$ et $\xi' = \alpha$ avec
$\xi \neq \xi'$) et que l'on ne distingue pas entre deux schémas qui ne diffèrent
que par le nom des variables y figurant.

Nous énoncerons ainsi le

**THEOREME 5** - Le magma des schémas de programme sur $F$ et $B$ est
isomorphe au magma des langages schématiques sur le magma libre $M(F,B)$
et toute interprétation $I$ dans un domaine $D$, définit un morphisme de ce
magma dans le magma $D_I$ des applications de $D \cup \Omega$ dans lui-même.

**REMARQUE** : La correspondance qui fait correspondre à un schéma de programme un certain ensemble (schématique) de schémas de programme sans boucle est identique à la règle de recopie qui permet, dans le langage ALGOL 60, d'associer à un programme récursif un ensemble de programmes non récursifs tel que si l'un d'entre eux calcule une valeur pour une donnée initiale, cette valeur est aussi celle de la fonction calculée par le programme récursif. Il nous paraît assez clair que nous n'avons rien fait d'autre, dans ces pages, que de généraliser et formaliser cette règle de recopie.
B I B L I O G R A P H I E

<table>
  <tbody>
    <tr>
      <td>[1] S. GINSBURG</td>
      <td>Mathematical theory of context-free languages<br>MAC GRAW HILL Publishing Company, 1966</td>
    </tr>
    <tr>
      <td>[2] R. MAC NAUGHTON</td>
      <td>Parenthesis grammars JACM volume 14 (1967)<br>pages 490-500</td>
    </tr>
    <tr>
      <td>[3] P. NAUR (Edit.)</td>
      <td>Report on the Algorithmic language ALGOL 60, CACM<br>volume 3 (1960) pages 299-314</td>
    </tr>
    <tr>
      <td>[4] M.P. SCHUTZENBERGER</td>
      <td>Context-free languages and push-down automata<br>Information and Control, volume 6 (1963)<br>pages 246-264.</td>
    </tr>
    <tr>
      <td>[5] D. SCOTT</td>
      <td>The lattice of flow diagrams.<br>Symposium on semantics of algorithmic languages.<br>Springer-Verlag, Lecture notes in Mathematics n°188<br>1971.</td>
    </tr>
  </tbody>
</table>