Le langage d'opérateur

Les suffixes `"(.)"` et `"(.,.)"` précise l'arité des opérateurs. Une fois déclaré dans un langage mère, il n'est pas nécessaire de le rappeler dans la suite du chapitre, tout opérateur `f` sera unaire et tout opérateur `g` sera binaire.

Et on note `L°` l'ensemble des termes clos par emboitement d'opérateurs de `L`.

La structure libre `"<"L">"` désigne l'ensemble des termes clos par composition d'opérateurs de `L`.

`L°` et `"<"L">"` sont deux façons différentes de voir la même chose. Chaque termes clos du langage `{a,b,f,g}°` désigne un élément distinct de la structure libre `"<"a,b,f,g">"` et réciproquement. Ainsi il n'y a pas de différence entre le langage engendré par emboitement clos d'opérateurs et la structure libre engendrée par composition close d'opérateurs.

Intéressons-nous au langage par emboitement mais non nécessairement clos `L^•`. Voici des exemples de termes non clos :

Les sous-termes manquants sont désignés ici par des points "`"."`". On peut considérer ce point "`"."`" comme un élément rajouté pour désigner les fils libres du terme non clos. Ainsi les termes du langage `L` correspondent à aux termes clos du langage `Luu{"."}` où "`"."`" est un opérateur d'arité zéro que l'on rajoute pour désigner les fils libres.

Un terme est un arbre dans lequel chaque noeud de l'arbre est un opérateur d'arité supérieur à zéro, possèdant autant de fils que son arité, et chaque feuille de l'arbre est un opérateur d'arité zéro et qui peut être l'élément "`"."`".

Un terme non clos désigne une application dont la liste des arguments correspond à la liste des fils libres du terme tels qu'ils sont disposés de gauche à droite. Par exemple le terme `g(.,f(.))` désigne l'application `(x,y)|->g(x,f(y))`.

Cette construction définie l'ensembles des applications constructibles par emboitement (ou autrement dit par composition sans permuter ni fusionner les entrées). Nommons `φ` l'application procédant à cette construction. Elle transforme par exemple le terme `g(".",g(a,"."))` en l'application `(x,y)|->g(x,g(a,y))`. L'application `φ` constitue une concrétisation. Son ensemble de départ est `L°["."] `. Son ensemble image est l'ensemble des applications sur `L°` engendré par composition sans permutation ni fusion des entrées.

Considérons un exemple d'application. Elle est notée par l'expression suivante :

Cette expression correspond au programme de calcul de l'application. Elle comprend une séquence de variables de nom distincts `(x,y)` qui constitue l'entête de l'application, la liste de ses entrées. Elle comprend l'opérateur binaire `|->` qui est le constructeur d'application. Et elle comprend un terme clos `g(x,g(a,y))` de `L°[x,y]` qui constitue le corps de l'application.

Le langage des termes de `L` est désigné par `L^• = L°["."]` et la concrétisation sera implicite. De tel sorte que chaque terme désignera une application opérant sur la structure `"<"L">"` et dont l'arité est égale aux nombres de points "`"."`" qu'il possède. L'appel de cette application se fait en distribuant les variables d'appel sur les points "`"."`" du terme clos de `L°["."]` dans l'ordre de gauche à droite.

On remarque que chaque terme du lanage `L`, c'est à dire chaque terme clos du langage `Luu{.}`, désigne une application opérant sur le langage `L` qui peut être étendue au langage `Luu{.}`. Cela définie une opération notée `@` entre termes du langage `L` qui est à la fois l'application d'un terme sur un autre et la composition d'un terme avec cet autre. Cela consiste à remplaçer le premier fils libre rencontré dans le premier terme en le parcourant de gauche à droite par le second terme. Et cette composition est naturellement associative. Mais elle n'est définie que si le premier terme possède au moins un fils libre représenté ici par un point "`"."`". Par exemples :

Si on essaye d'étendre cette composition au autres termes que sont les termes clos du langage `L`, alors on cherche une valeur pour `a@b`. Et comme aucune définition ne convient, par défaut on choisi comme résultat l'expression de l'appel, autrement dit `a@b` est définie comme étant égal au terme `a@b` qui correspond à une séquence de deux termes `a` et `b`.

On étend ainsi la composition `@` qui ressemble alors à une opération de concaténation mais en plaçant le second terme à la place du premier point rencontré (de gauche à droite) dans le premier terme, puis s'il n'y a pas de point, en le plaçant comme terme suivant. Par exemple :

Ainsi nous avons définie une structure en ajoutant un opérateur binaire `@` de syntaxe centrée :

On peut facilement voir que l'opération `@` est associative. On appel cette composition la concaténation polonaise, car elle met en oeuvre la logique polonaise.

2) Le langage de caractère `L"*"`

Le langage d'opérateurs peut être ramené à l'aide de la logique polonaise en un langage de caractères plus simple. Chaque opérateur de L est un caractère. Un terme clos est traduit en enlevant les parenthèses, en une suite de caractères formant un mot. Un terme clos constitue un arbre. Sa traduction en un mot de `L"*"` correspond au parcours de l'arbre de gauche à droite et en profondeur d'abord.

L'arité des opérateurs est préalablement définie dans une présentation du langage.

Voici quelques exemples de termes clos appartenant à `L°` avec leur traduction en mots appartenant à `L"*"` :

Un terme clos est un flux de caractères qui se composent selon la logique polonaise. Si l'on s'autorise tout flux fini de caractères, on obtient le langage de caractère complet noté `L"*"`. Et ce langage correspond à un langage d'opérateurs plus générale dit langage des séquences terminal-closes, notée `L°^m`, que nous allons décrire.

Autrement dit, la transformation que nous faisons de certain mot de `L"*"` pour les transformer en terme clos de `L°`, peut être étendue à tout les mots de `L"*"`, et produit dun langage plus large dit langage de séquence terminal-closes, noté `L°^m`, que nous allons décrire.

3) La cloture terminale des séquences

`L°^m` est l'ensemble des séquences terminal-closes. Ce sont des séquences de termes clos de `L°` sauf pour le dernier terme qui peut ne pas être clos mais dont seuls les dernières opérandes, feuilles de l'arbre les plus à droite, ne sont pas nécessairement déterminées et sont alors représentées par des points.

Le dernier terme de la séquence est dit terminal-clos. Toutes les opérandes laissées libres sont en places terminales de ce terme, c'est à dire occupent les dernières places à droite dans le terme. Par exemple le terme `g(f("."),f("."))` n'est pas terminal-clos. Parcontre le terme `g(f"(.)",".")` est terminal-clos.

Une séquence terminal-close est une séquence de termes tous clos à l'exception du dernier terme qui est seulement terminal-clos.

4) La cloture terminale des termes

`L°^t` est l'ensemble des termes terminal-clos, c'est à dire l'ensemble des termes de `L°` où seul les dernières opérandes, celles les plus à droite dans le terme, ne sont pas nécessairement déterminées et sont alors représentées par des points.

Le langage des termes terminal-clos `L°^t` peut être enrichie en ajoutant le mécansime de construction des séquences, le langage est alors dit avec séquence et il est notée `L°^(ts)`. Remarquer que ce langage est plus grand que le langage des séquences terminal-closes `L°^m`. Par exemple `(f(.), f(.))` appartient à `L°^(ts)` mais pas à `L°^m`. (Parcontre le langage des termes terminals-clos avec séquence terminale close `L°^tm` et est égale au langage des termes terminals clos avec séquence `L°^(ts)`.)

Voici quelques exemples de mot de `L"*"` avec leur traduction en séquences terminal-closes appartenant à `L°^m` et en terme terminal-clos appartenant à `L°^t`.

5) La currification tout ou rien

On commence par la currification tout ou rien, qui consiste a autoriser un terme sous deux formes, une forme dite fonctionnelle, avec toutes ces opérandes, et une autre forme dite élémentaire sans aucune opérande.

Par exemple l'opérateur `g"(.,.)"` peut former le terme `g(a,b)` ou simplement le terme `g`.

Cela consiste à donner une arité supplémentaire, nulle, à tous les termes, qui se cumule éventuellement avec une arité supérieur à zéro spécifique au terme. Ce faisant, les termes de type n possèdes en faite deux arités que sont l'arité 0 et l'arité n, et dans la pratique nous disons qu'ils ont une arité n, l'arité nulle ne comptant pas car étant en faite qu'une conséquence de l'axiome n°3. La currification tout ou rien va étendre le langage d'opérateur simple en le respectant, c'est à dire que le langage d'opérateur simple sera inclus dedans.

Le type d'un terme correspond toujours exactement à son arité, que l'on note par un entier naturel. C'est l'arité qui a un sens un peu différent. Par exemple, le terme `g` a une arité `2`, et il peut apparaître tel quel comme une opérande.

Ainsi les termes peuvent avoir des opérandes d'arité supérieur à zéro et retourner un terme résultat d'arité supérieur à zéro. Par exemple le terme `g (g,f)` est d'arité `3` et peut donc être appliqué à un triplet de termes tel que par exemple `(f,b,a)`pour former le terme `g (g,f) (f,b,a)` d'arité `1` qui peut donc être appliqué à son tours à un terme tel que `g` pour former le terme `g (g,f) (f,b,a) (g)` d'arité `2`. Un terme exprimé ainsi est dit développé par palier. On peut le développé en série comme suit : `g` opère sur le couple `(g,f)` pour produire un opérateur d'arité `3` présenté par le programme `g (g"(.,.)",f"(.)")`. La liste des `3` termes suivants viennent alimenter les `3` places libres du terme dans l'ordre de leur arrivé en se plaçant de gauche à droite selon la logique polonaise, et ainsi de suite pour les paliers suivant :

On remarque que l'on peut évaluer les séquences intermédiaires `(g,f)(f,b,a)` de la même manière en alimentant les `3` places libres de la séquence `(g"(.,.)",f"(.)")` avec les `3` termes suivant `(f,b,a)` pour former le couple `(g (f,b),f (a))` et ainsi de suite.

La composition peut s'opérer entre deux séquences contigües. La composition est associative, elle peut être évaluée dans n'importe quel ordre :

La contrainte porte sur la longueur de la séquence qui doit être égale à l'arité de la séquence précédente. Nous verrons avec la currification comment cette contrainte peut être levée.

Construction :

Le langage d'opérateurs simple avec currification tout ou rien, se note `L°^¢`. L'écusson `¢` représente une propriété additionelle au langage d'opérateur simple qui ajoute un nouveau procédé de construction qu'est la currification tout ou rien.

Le principe de construction est le suivant : Si le type du terme `u` est égale à `n`, alors la composition entre `u` et la liste d'arguments `(v_1,v_2,v_3...,v_n)` est autorisée et se note `u(v_1,v_2,v_3...,v_n)`. On définie sur le langage des types, l'opération correspondante avec la même notation. Quelque soit un types `tau` et quelque soit une liste de n types `(t_1,t_2...,t_m)`, si `tau=n` alors la composition est autorisée. Le type résultant s'obtient par la formule suivante :

La libéralisation des types des opérandes va augmenter le pouvoir d'expression du langage, qui pourra exprimer des opérateurs d'arité non nulle. Voici quelques exemples :

Les opérateurs `L°^¢`-exprimables appelés aussi `L`-emboitables avec currification tout ou rien, sont caractérisés comme suit : Les variables sont sans permutation ni projection, et pour chaque opérateur de `L`, elles occupent soit aucune de ses opérandes, soit toutes ses opérandes. Voici quelques contre-exemples :

Forme normale :

La structure n'est plus libre, deux mots différents de `L°^¢` peuvent désigner le même opérateur. Par exemple nous avons `g(a,f(b)) = g(a,f)(b)`. Nous dirons que les mots sont équivalent et que les opérateurs qu'ils désignent sont égaux. Néanmoins il existe deux formes normales que sont la forme série (parcours de l'arbre en profondeur d'abord) et la forme parallèle (parcours de l'arbre par niveau d'abord) :

Deux mots sont équivalents si et seulement si leur forme normale (série ou parallèle) sont identiques.

6) L'opérateur identité "."

L'opérateur identité d'arité 1 que l'on note "." peut être rajouté au langage. Il s'agit d'un opérateur avec son programme défini par `x|->x`. Le langage est alors dit unitaire, et est marqué à l'aide de l'écusson `u` qui représente l'axiome n°10 suivant :

Dans le langage d'opérateur simple unitaire avec currification tout ou rien, noté L°^(u¢), voici des exemples typiques de règle de simplification :

L'opérateur "." permet d'exprimer par redondance l'arité des opérateurs ou des termes sans modifier substantielement leur expression :

Construction :

Les opérateurs `L°^(u¢)`-exprimable appelé aussi opérateurs `L`-constructible-faible. sont caractérisés comme suit : Les variables sont sans permutation ni projection, c'est à dire qu'elles doivent avoir des noms distincts et se présenter dans le même ordre dans le n-uplet d'entré et dans le corps de la fonction.

Par exemple l'opérateur `x|->g(x,b)` est égale à l'opérateur `g(.,b)`. Par contre les opérateurs : `(x,y)|->g(y,x)` et `x|->g(x,x)` ne sont pas exprimables dans ce langage.

Forme normale :

Dans le langage d'opérateurs simple unitaire avec currification tout ou rien `L°^(u¢)`, Il existe toujours deux formes normales, la forme série simplifiée et la forme parallèle simplifiée. Par exemple le terme `g(.,g(f,.))(.,.,b)` possède une forme série `g(.,g(f(.),b))` qui se simplifie en `g(.,g(f,b))` et possède une forme parallèle `g(.,g)(.,f,.)(.,.,b)` qui se simplifie en `g(.,g)(.,f,b)`. Deux termes sont égaux si et seulement si leur forme normale (série simpifié ou parallèle simplifié) sont identiques.

7) Les séquences finies

Le concept de séquence de termes apparait naturellement. Mais elle doit être encadré par un terme et constituer la séquence de ses opérandes. Une séquence de termes se comporte comme une application de `(L°)^n -> (L°)^m`, et possède une arité `n` appelé arité d'entré, et une arité de sortie `m` :

La différence entre une séquence et une liste tient en ce que la séquence ne peut pas contenir de séquence ou plus exactement qu'elle fusionne implicitement toutes les séquences qu'elle contient faisant qu'elle se présente toujours comme une séquence d'un seul premier niveau. Par exemple la séquence `(a, b, (a, (a), b), (b, a))` est égale à la séquence `(a, b, a, a, b, b, a)`.

Le langage avec séquence finie est marqué avec l'écusson `s` qui représente ce nouveau procédé de construction qu'est la consruction de séquence finie. `s` est une propriétée additionnelle au langage d'opérateur simple.

Cette généralisation consiste à modifier l'axiomatique en ajoutant un procédé de construction de terme par concatenation. Cette généralisation respecte les langages d'opérateurs simple avec ou sans currification tout ou rien, unitaires ou non.

Les opérateurs générateurs du langage n'ont pas besoin d'être composés, ni de constitués des séquences.

Cela définie un nouveau moyen de construction de terme par concaténation, produisant une séquence de termes. L'autre procédé de construction de termes se fait par la composition d'un opérateur avec une séquence de termes. La séquence de termes étant un terme, la composition se définie entre un opérateur et un terme avec comme unique contrainte que l'arité d'entré de l'opérateur soit égale à l'arité de sortie du terme.

Tout terme de type `(m,r)` opèrent sur un terme de type `(n,m)`, et retourne comme résultat un terme de type `(n,r)`.

Construction :
On définie, sur le langage d'opérateurs simple avec séquences finies, deux opérations que sont la concaténation et la composition. La concaténation des termes `u` et `v` est notée `(u,v)`. La composition des termes `u` par `v` n'est possible que si l'arité d'entré de `u` est égale à l'arité de sortie de `v`, et alors on note cette composition par `uv`. On définie, sur le langage des types, les opérations correspondantes avec la même notation. Quelque soit deux types `(n1,m1`) et `(n2,m2)`, nous avons `"(" ( n1,m1) , (n2,m2 ) ")" = (n1+n2, m1+m2)`, et si `m1=n2` alors la composition est autorisée `"(" ( n1,m1),(n2,m2 ) ")" = (n2,m1)`.

Forme normale :
Dans le langage d'opérateurs simple unitaires avec currification tout ou rien et séquences finies `L°^(¢us)`, Les formes normales série simplifié et parallèle simplifié existe toujours. La différence tient dans la forme parallèle, en ce que le premier opérateur du terme peut être remplacé par une séquence d'opérateurs.

Pouvoir d'expression :
L'introduction des séquences finies va changer la nature des opérateurs. Les opérateurs étaient des applications de `(L°)^n` vers `(L°)`, ils deviennent après introduction des séquences, des application de `(L°)^n` vers `(L°)^m` où `(n,m)` est le type de l'opérateur. Mais en dehors de ce changement de nature il n'augment pas le pouvoir d'expression. Les opérateurs exprimables dans le langage `L°^(¢s)` sont dit opérateurs L-emboitable avec currification tout ou rien et séquences finies. Les opérateurs exprimables dans le langage `L°^(¢us)` sont les opérateurs L-constructibles-faibles avec séquences.

Dans le langage `L°^(¢us)`. L'opérateur "." est de type `(1,1)`. La séquence d'opérateurs `(.,.)` est de type `(2,2)`. Voici les exemples typiques de règle de simplicication :

8) La currification

Le principe est simple, prenons par exemple une fonction d'arité 4, `h(x,y,z,t)`. La currification permet d'appliquer `h` par exemple à seulement `2` opérandes, et cela produit comme résultat, la fonction d'arité `2` suivante : `h(x,y) = ((z,t)|->h(x,y,z,t) )`.

On note un langage avec currification à l'aide de l'écusson c. L'écusson c représente donc une propriété additionelle au langage d'opérateur simple qui ajoute ce nouveau procédé de construction qu'est la currification.

Le langage d'opérateur simple, unitaire ou non, avec séquence finies ou non, avec currification tout ou rien ou non, peut mettre en oeuvre le procédé de currification.

La currification réduit les contraintes de composition et applique la logique polonaise par palier.

Cas des langages sans séquence finie :

Lorsque un opérateur d'arité `n` est appliqué à une séquence d'opérandes de taille `m`, trois cas peuvent se produire, soit `m=n` auquel cas le résutat est un terme d'arité égale à la sommes des arités des `m` opérandes, soit `n>=m` au quel cas le résultat est un terme d'arité égale à la somme des arités des `m` opérandes à la quelle on ajoute `n-m`, soit `m>n` et la composition est interdite.

Les termes n'ont plus une arité simple. On reformule l'axiome n°B comme suit :

Les axiomes n°B, n°A et n°16 réforme le procédé de composition d'un opérateur avec un terme. Avec l'axiome n°xx la composition s'applique également aux termes et pas seulement aux opérateurs. Tout terme de type `n` opèrent sur `m` opérandes de type quelconque `(n>=m)`, et retourne comme résultat un terme de type égale à la somme des types de ses opérandes à la quelle on ajoute le type du terme opérant moins le nombre de ses opérandes.

Construction :
On définie, sur le langage d'opérateurs simple avec currification, la composition : Si le type de `u` est supérieur ou égale à la taille de la séquence `(v1,v2,v3...,vm)`, c'est à dire si le type de `u` est supérieur ou égale à `m`, alors la composition est autorisé et se note : `u(v1,v2,v3...,vm)`. On définie sur le langage des types, les opérations correspondantes avec la même notation. Quelque soit un type `n1` et quelque soit `m` types `(t1,t2...,tm)`, si `n1>=m` alors la composition est autorisée `n1(t1,t2...,tm) = t1 + t2... + tm + n1 - m`.

Pouvoir d'expression :
Les opérateurs `L°^c`-exprimables appelé aussi L-emboitable avec currification, sont caractérisés comme suit : Les variables sont sans permutation ni projection et pour chaque opérateur de L, elles ne peuvent occuper que les opérandes les plus à droite. On parlera d'opérateur terminal-clos. Voici quelques exmple et contre-exemples :

`L°^c` est aussi appelé le langage d'opérateurs simples avec opérateur terminal clos.

Forme normale :
Dans le langage `L°^c` il existe toujours 2 formes normales, la forme série (parcours de l'arbre en profondeur d'abord) et la forme parallèle (parcours de l'arbre par étage d'abord). Et dans le langage `L°^(cu)` en donnant la priorité à la currification vis à vis de l'usage de l'opérateur identité. Il existe toujours 2 formes normales, la forme série simplifiée et la forme parallèle simplifiée. Deux termes sont équivalent si et seulement si leur forme normale (série simplifié ou parallèle simplifié) sont identiques.

Les termes n'ont plus une arité simple, mais toutes les arités leur sont permises. On reformule l'axiome n°11 comme suit :

L'axiome n°12 définie un nouveau moyen de construction de terme par concaténation, produisant une séquence de termes. L'autre seul procédé de construction de termes que nous connaissons est la composition d'un opérateur avec une séquence de termes que sont ses opérandes. La séquence de termes étant maintenant un terme, la composition se définie maintenant entre un opérateur et un terme.

L'axiome n°12 avec l'axiome n°15 a pour conséquence que l'axiome n°12 s'applique également aux termes et pas seulement aux opérateurs. Tout terme de type `(n1,m1)` opère sur un terme de type quelconque `(n2, m2)`, et retourne comme résultat un terme de type `(n2 + sup(0, n1-m2), m1+sup(0, m2-n1))`.

Il n'y a plus de contrainte sur la composition des termes. Toutes les combinaisons de concaténation et de composition de termes sont permises.

Construction :
Dans le langage d'opérateurs simple avec currification et séquence finie `L°^(cs)`, il existe deux opérations que sont la concaténation et la composition. La concaténation des termes `u` et `v` est notée `(u,v)`. La composition des termes `u` par `v` est notée `uv`. On définie, sur le langage des types, ces mêmes opérations avec la même notations. Quelque soit deux types `(n1,m1)` et `(n2,m2)`, nous avons : `((n1,m1) , (n2,m2)) = (n1+n2, m1+m2)` et `((n1,m1)(n2,m2)) = ((n2 + sup(0, n1-m2), m1+sup(0, m2-n1))`.

Une séquences de séquences se simplifie en une seul séquence. Quelque soit des termes `u,v,w...` nous avons :

La composition `uv` est égale à la concaténation `(u,v)` lorsque l'arité d'entré de `u` est nulle.

Pouvoir d'expression :
Les opérateurs `L°^(cs)`-exprimables appelé aussi `L`-emboitable avec currification et séquence finie, sont caractérisé comme suit : Les variables sont sans permutation ni projection et pour chaque opérateur de L, elles ne peuvent occuper que les opérandes les plus à droite.

L°cs est aussi appelé le langage d'opérateurs simples avec opérateur terminal clos et séquence finie.

Forme normale :
Dans le langage `L°^(cs)` il existe toujours 2 formes normales, la forme série (parcours de l'arbre en profondeur d'abord) et la forme parallèle (parcours de l'arbre par étage d'abord). Et dans le langage `L°^(cus)` en donnant la priorité à la currification vis à vis de l'usage de l'opérateur identité. Il existe toujours 2 formes normales, la forme série simplifiée et la forme parallèle simplifiée. Deux termes sont équivalents si et seulement si leur forme normale (série simplifié ou parallèle simplifié) sont identiques.

9) Quelques langages de caractères

Il existe une bijection canonique entre le langage de caractères `L"*"` et le langage d'opérateurs `L°^m`. La différence tient dans les parenthèses qui transportent l'information sur l'arité des opérateurs, absentes dans le langage de caractère et présentes dans le langage d'opérateurs. L'information véhiculé par les parenthèses est contenue dans la présentation `L` du langage.

Il existe une bijection canonique entre le langage de caractères `L"'*"` et le langage d'opérateurs `L°^(¢m)`. Le caractère apostrophe est un suffixe des opérateurs d'arité superieur à zéro, qui signifie que l'opérateur est sous sa forme élémentaire.

Il existe une bijection canonique entre le langage de caractères `L|*` et le langage d'opérateurs `L°^(cs)`. Le caractère "|" est un séparateur de palier qui implémente la logique polonaise par palier. Le caractère "|" ne doit pas être placé ni au début ni à la fin du flux de caractère, et la séquence de caractères entre deux caractère "|" consécutifs ou entre le début et le premier caractère "|", doit représenter un opérateur d'arité non nul (sans quoi il n'y a pas de bijection).

Il existe un lien canonique entre le langage de caractères `L·"*"` et le langage d'opérateurs `L°^(¢us)`.

`f` et `f(.)` sont deux mots distincts de `L°^(¢us)` qui désignent le même opérateurs. On dira que ces deux mots sont équivalent. De même ont dira que `f` et `f·` sont deux mots équivalents de `L·*`.

10) Hierarchie des langages

Chaque écussons du langage est une propriété aditionnelle, ajoutant un procédé de construction au langage.

Les liens d'inclusion entre langage sont la traduction des liens logiques entre ces propriétés :

Lorsque un langage possède plusieurs noms, on choisit un nom minimal selon les 3 implications simples `m=>s`, `c=>¢`, `c=>t`. Par exemple le langage `L°^(¢us)=L°^(cus)=L°^(¢um)=L°^(cum)` est désigné par `L°^(¢us)`.

L'opérateur identité n'est pertinante que dans les langages possédant au moin la currification tout ou rien, c'est pourquoi il n'est pas évoqué dans les autres langages. L'ordre d'inclusion des langages est alors représenté par le diagramme transitif suivant :

Noter que les constantes `L`-calculables, `L`-recurcives, `L`-constructibles, `L`-emboitables avec currification, `L`-emboitables terminales closes avec currification tout ou rien, `L`-emboitables terminales close, et `L`-emboitable avec currification tout ou rien, sont les mêmes et constitue l'univers de Herbrand.

On note entre crochet les opérateurs générateurs exterieur au langage que l'on ajoute pour produire une extention du langage. La présetation des opérateurs exterieurs doit être connue. Par exemple prenons les opérateurs constants `c` d'arité nulle et `h(.)` d'arité `1`, nous pouvons définir le langage étendu `L°[c,h] = (L union {c,h})°`. Cette extention peut s'appliquer à tous les langages précédement décrits et n'en change pas leur nature. Par exemple nous pouvons considérer le langage `L°^(u¢)[c,h]` et en voici quelques mots `h(f(.),c), g(a,b), f(c)`.

De même on peut étendre le langage en ajoutant des opérateurs variables `x,y` d'arité nulle, appelés simplement variables, et obtenir le langage `L°[x,y]`. Les variables jusqu'à présent sont d'un unique type (`0` ou `(0,1)` selon la nature du langage). La variable se comporte comme la constante, et c'est son utilisation future qui la différenciera de la constante.

Les extensions successives du langage par ajout d'opérateur, et par ajout de procédé de construction, crée une hierarchie des langages. Et les opérateurs générateurs se positionnent dans cette hierarchie à leur plus haut niveaux possibles, formant une stratification. Chaque couche correspond alors à un protocole de communication.

Dans le langage L°s, un opérateur constant de type (n,m) est une application de L°0^n vers L°0^m, qui possède un nom.

Les opérateurs L-constructibles sont construits par composition au sens général, c'est à dire correspondent à des programmes sans boucle, à des assemblages sans boucle d'opérateurs L-constructibles vus comme autant de sous-programmes.

Le méta opérateur "-->" de construction d'opérateurs.
On défini le meta-opérateur"-->" d'arité 2 en notation centrée ( . --> .). Il prend comme premier argument appelé entré, une séquence de variables de noms distincts parmis x,y,z..., et comme second argument, une séquence de termes de L°[x,y,z...], soit un terme de L°s[x,y,z...]. Et retourne comme résultat l'opérateur ainsi défini. On exclue les séquences vides. Par exemple :

Si nous appelons h l'opérateur retourné par cette expression, nous avons par exemple :

Nous utiliserons plus tard ce méta-opérateur "-->" dans le langage avec currification L°cs, mais dans un premier temps on se contentera de l'utiliser dans ce langage étendu de façon limitée noté L°s^2. Néamoins cela à une conséquence sur la notion d'opérateur. L'opérateur x-->f(x) coïncide avec l'opérateur (x,y)-->f(x) et avec l'opérateur (x,y,z)-->f(x) dans le langage avec currification L°cs. Aussi ces trois opérateurs sont considérés égaux.

Si la sortie contient une variable ne figurant pas dans l'entré, l'opérateur est dit paramétrique.

Le langage des L-construction L°&
Deux tels opérateurs sont égaux si on peut passer de l'un à l'autre en permuttant leurs variables. Ils admettent donc une représentation unique si on nomme les variables d'entrés toujours de la même façons. En faisant le choix de nommer les variables d'entré par les entiers 1,2,3...., considérés ici comme des variables, on définie le langage des L-constructions noté L°& :

Un opérateur L-constructible correspond à un mot de L°&, et son ensemble image correspond à un mot de L°& à une permutation près des variables. L'ensemble image d'un opérateur L-constructible correspond à un mot de L°& dans lequel les variables distinctes sont numérotées dans l'ordre de leur première apparition.

Les opérateurs isolés peuvent être remplacés comme dans l'exemple suivant (g,f(2),f) = (g(3,4),f(2),f(5)) et correspondent à autant de variables supplémentaires que la somme de leur arité.

19) Les fonctions L-constructibles, leur domaine de définition et leur image.

Première généralisation : On fait opérer le méta opérateur "-->" sur la totalité du langage.
On généralise le meta-opérateur --> en le faisant opérer sur L°s[x,y,z...], c'est à dire sur deux termes de Ls°[x,y,z...] appelé entré et sortie. Le résultat n'est plus une application mais une fonction définie sur un domaine restreint. On exclue les séquences vides. Voici un exemple :

Dans cet exemple, le domaine de définition est l'ensemble des éléments de L°^2 unifiables à (g(x,y),f(y)), c'est à dire l'ensemble image de l'application (x,y)-->(g(x,y),f(y)) sur L°^2. Avec la currification, le domaine de définition devient l'ensemble des termes de L°s unifiables à (g(x,y),f(y)). Seul les deux premiers termes de la séquence sont soumis à cette unification, les termes suivants non aucune contraintes imposées. Ce domaine de définission est également égale à l'ensemble image de l'application (x,y)-->(g(x,y),f(y)) sur L°s.

Et d'une façon encore plus générale, le terme résultat est une application de L°s[x,y,z] vers L°s[x,y,z] dont le domaine de définition est l'ensemble des élément de L°s[x,y,z] unifiables au terme d'entré (g(x,y),f(y)), sachant que les termes récurcifs sont interdits et que cette unification ne contraint que les deux premier termes. Ce domaine de définition est aussi égale à l'ensemble image de l'application (x,y)-->(g(x,y),f(y)) sur L°s[x,y,z].

L'unification d'un opérateur isolé avec ce même opérateur mais appliqué à des opérandes s'effectue simplement en ajoutant autant de variable nécéssaire.

Seconde généralisation : On fait opérer le resultat sur la totalité du langage.

On étend le domaine de définition à L°s en attribuant comme image la constante FAIL à tout élément de L°s en dehors du domaine de définition précédement défini. (Et d'une façon générale, on étend le domaine de définition à L°s[x,y,z] en attribuant comme image la constante FAIL à tout élément de L°s[x,y,z] en dehors du domaine de définition précédement défini.)

Ces opérateurs sont appelés fonctions L-constructibles et constituent un sous-ensemble des fonctions L-constructible.

Deux fonctions L-constructibles sont égales si et seulement si on peut passer de l'une à l'autre en permuttant les variables. La numérotation des variables dans l'ordre de leur apparition, permet de désigner de façon unique la fonction dans L°s&^2.

Une fonction tel que (f(x),y)-->g(x,y) se décompose en deux fonctions successives : La résolution (ou l'opérateur inverse) (f(x),y)-->(x,y), et l'opérateur (x,y)-->g(x,y).

La première fonction (f(x),y)-->(x,y) est composé d'un mot de L°s[x,y,z...] et de la séquence des variables distinctes ordonnées selon l'ordre de leur première apparition dans le premier mot. C'est un opérateur inverse (appelé aussi une résolution), et constitue le noyaux de l'unification. La seconde fonction (x,y)-->g(x,y) est composé d'une séquence de variables distinctes parmis {x,y,z...} et d'un mot de L°s[x,y,z...]. C'est un opérateur (et un nom doit lui être attribué).

L'opérateur inverse (f(x),y)-->(x,y) définie ce que l'on appelle la résolution de l'unification, c'est à dire lorsque l'unification est achevé la fonction donne comme résultat la valeur des variables dans l'ordre de leur première apparition, ou retourne FAIL en cas d'échec. L'autre partie apparente de l'unification qui porte son nom est la fonction qui peut paraitre trivial mais qui ne l'est pas : (f(x),y)-->(f(x),y). Elle retourne le résultat de l'unification, c'est à dire la séquence de termes unifiés ou FAIL. On note U l'unification de deux séquences de termes, et R la résolution d'une séquence de terme unifié par une autre séquence de termes. U est symétrique mais que R ne l'est pas.

Pour tout terme de L° si celui-ci contient dans une des ses opérandes la valeur FAIL alors il retourne FAIL. Ce comportement se définie dans le langage des types. Le langage devient un langage avec type FAIL. Son axiomatisation consiste à modifier l'axiome n°10 et n°12 en ajoutant à la suite :

Dans L¢s, les séquences peuvent contenir des valeurs FAIL sans être transformé en la constante FAIL. Car la règle énoncé dans l'axiome n°12 stipule cette transformation pour les opérandes et non pour les éléments d'une séquence.

Une règle est une fonction à l'ordre près de ses opérandes et en supprimant les opérandes en doubles. Par exemple :

Le premier type concidéré est noté 0, et constitue le type d'un opérateur zéro-aire.

Le type d'un opérateur se décompose en une liste de types de ses opérandes et en le type de son résultat. Le meta opérateur "-->" de construction d'opérateur possède un homologue dans le langage des type noté plus simplement ">". Il a le sense d'un opérateur de construction de type, il prend en argument n types divers quelconques et comme dernier argument un type quelconque, et retourne le type du nouvel opérateur ainsi construit.

Nous utilisons le meta opérateur "type" qui appliqué à un terme retourne le type du terme. Nous avons quelque soit les termes x,y,z,t... :

type(x-->y) = type(x)>type(y)
type(x,y-->z) = type(x),type(y)>type(z)
type(x,y,z-->t) = type(x),type(y),type(z)>type(t)
etc...

Le type est définie à l'aides du type prédéfini 0 et de l'opérateur d'arité n ">" en notation (n,1) de construction de type.

Le type 0>0, noté également 1, désigne le type d'un opérateur unaire agissant sur un opérateur de type 0 pour produire un opérateur de type 0. Le type 0,0>0 , noté également 2, désigne le type d'un opérateur binaire agissant sur un opérateur de type 0 et sur un opérateur de type 0 pour produire un opérateur de type 0. Et ainsi de suite.... Le type x>(y>z) désigne le type d'un opérateur unaire agissant sur un opérateur de type x pour produire un opérateur de type y>z. Le type (x>y)>z désigne le type d'un opérateur unaire agissant sur un opérateur de type x>y pour produire un opérateur de type z. Etc...

Le type se présente comme un arbre dont les noeuds ont des arités diverses et où la dernière branche désigne une production scalaire.

H est le type d'un opérateur agissant sur un opérateur de type x>(y>z), c'est à dire un opérateur agissant sur un opérateur de type x pour produire un opérateur de type y>z. Et l'opérateur de type H produit un opérateur de type t,u>v, c'est à dire un opérateur qui agit sur un opérateur de type t et un opérateur de type u pour produire un opérateur de type v.

Lorsque le typage est monogène, c'est à dire engendré par un seul type générateur, Ce type générateur est prédéfini et se note 0 et correspond au type des constantes d'arité zéro du langage d'opérateurs, c'est à dire au type des éléments de <L>.

Les autres types dérivent de celui-ci. L'opérateur unaire est de type 1 = 0>0. L'opérateur binaire est de type 2 = 0,0>0. L'opérateur ternaire est de type 3 = 0,0,0>0. Et ainsi de suite....Un opérateurs d'arité simple possède un type égale à son arité, et agit sur des opérandes de type 0 pour retourner un terme de type 0. Le type d'un opérateur quelconque, ou d'un terme quelconque, est parcontre égale à son arbre d'arité.

Le type (0>0)>0 n'est pas simple. On peut concidèrer d'autres types d'opérateurs. Et on peut considérer d'autres opéeateurs possédant ces types, et construire d'autres termes utilisant ces opérateurs. Le langage se trouve enrichi par l'ajout de ces opérateurs de type non simple. Par exemple reprenons la présentation suivante :

Considérons l'opérateur constant q de type (0>0)>0 et ajoutons cet opérateur dans la présentation. Comme le type de l'opérateur q n'est pas simple, on perfectionne la notation et on n'affiche plus dans la présentation, l'arité de l'opérateur acollé à chaque opérateur, mais le type de l'opérateur acollé à chaque opérateur. La présentation du langage devient :

Le terme g(q(f),f(a)) est une terme clos, un terme du langage de présentation L. La cloture est alors une opération plus complexe puisque n'est autorisé le remplissage des places vides dans les termes meta-clos que si le type attendu correspond bien.

Et avec la composition en logique polonaise par palier et le créateur d'opérateur --> :

L'axiomes n°12 lit le langage d'opérateur, au langage de type. Et l'axiomes n°13 autorise les variables de type monogène.

On étend l'opérateur --> pour qu'il agisse sur des termes de type monogène quelconques pour produire un terme de type monogène quelconque. Par exemple le terme (x0>0,y0,z0,0>0) --> g(y,x(z)) est de type (0>0,0,(0,0>0)>(0,0>0)). L'opérateur --> fait partie du langage. En fait il y a une infinité de tel opérateur, un pour chaque type possible, et donc pour préciser de quel opérateur on parle, il faudra préciser son type. l'opérateur --> possède une syntaxe particulière dite (n,1), regroupant les n premières opérandes dans une séquence à sa gauche, et plaçant sa dernière opérande à sa droite.

On construit un sous langage de L° en choisisant comme générateurs quelques opérateurs L-constructibles. Par exemple, l'opérateur unaire h(.) = g(1,1) = (x-->g(x,x)), et la constante a.

Un sous ensemble S de L° est dit sous langage de L de type fini s'il est engendré par un ensemble fini de termes de L°, et il est dit sous-langage de L de type non fini si il est engendré par un ensemble infiini énumérable de termes de L° et par aucun ensemble fini de termes de L°, et c'est une partie non énumérable de L° dans les autres cas.

Etant donné un langage, ou un sous-langage, K, et étant donnés 3 opérateurs quelconques x,y,z n'appartenant pas à K. On note l'extension du langage par ajout de ces trois opérateurs comme suit :

Qu'est ce qu'une règle de simplification dans le langage L° ? A pemière vue une règle de simplification n'utilisant que 3 variables x ,y ,z est une proposition affirmant l'égalité de deux termes appelés atomes de L[x,y,z].

Les propositions obéissent au calcul logique qui est engendré par les opérations que sont la disjonction "ou" la conjonction "et" et la négation "¬". La théorie T est un ensemble énumérable correspondant à une conjonction. Il existe une forme réduite qui consiste à développer les équations logique en une conjonction de disjonction de littéraux, c'est à dire en un ensemble de disjonction de littéraux. Le litteral est une proposition d'égalité entre deux atomes ou une proposition d'inégalité entre deux atomes.

Nous avons donc besoin que d'une seul opération logique ou et des deux relations = et <>

Nous définissons un type µ spécifique pour désigner les propositions, le type 0 désigant les atomes. On note les types d'une manière plus explicite. Une fonction h d'arité 2 prenant une opérande de type u et de type v pour produire un terme de type w possèdera un type noté ((u,v)-->w). On pourra noter l'opérateur h également par h((u,v)-->w) pour rappeler son type.

Le langage utilisé par la théorie est donc (L union {x,y,z, =((0,0)-->µ), <>((0,0)-->µ), ou((µ,µ)-->µ)})° où l'opérateur = prend en argument deux atomes et retourne une proposition et de même pour l'opérateur différent <>. Par exemple la proposition f(x) = g(a,x) affirme que pour chaque valeur possible de la variable x, ces deux mots désignent le même élément dans <L>. Et donc que f(a)=g(a,a), f(b)=g(a,b), f(a(a))=g(a,f(a)), f(g(a,a))=g(a,g(a,a))...

Le langage des règles n'est plus un langage d'opérateur simple, il est appelé langage simple à 2 types. Son axiomatique modifie l'axiome n°12 par :

Les terme de type µ sont appelés propositions, et les termes de type 0 sont appelés atomes.

A l'aide de la représentation sous forme de graphe, le procédé de composition et d'unification, c'est à dire d'application et d'application inverse, peut être effectué selon une complexité linéaire, les données étant partageées et non répétées (chaque variable qui doit être affecté n'est affecté qu'une seul fois).

Jacques Herbrand, mathématicien français (1908 Paris - 1931 La Bérarde).
Thoralf Albert SKOLEM, mathématicien norvégien (1887-1963)

L'unification prend réellement sont sens avec la composition des règles de transformation. Et il est important de comprendre l'algorithme de complexité linéaire qui le permet.

Une règle est composé d'un premier membre et d'un second membre. Toutes les règles possèdant un même premier membre au renomage près des variables peuvent être regroupé en une seul règle ayant autant de second membre. Cette multi-règle est représentée par un graphe. Par exemple la multi-règles de transformattion g(x2,f(x1)) ->(f(g(x2,x1)), g(x1,x2),...) qui permet à partir d'un mots désignant une constante (un élément) de la L-Structure de fabriquer, après unification avec le premier membre, une liste d'autre mots de la même classe c'est à dire désignant la même constantes (le même élément). La fabrication se fait parallèlement puisque les variables sont partagées dans le graphe et qu'il n'y a qu'une seul unification.

La production de la logique intuituioniste est ce qui se construit. Le vrai est ce qui est constructible. La preuve est la construction. La preuve d'existence de l'objet x consiste à creer l'objet x. Une construction parallèle est une conjonction. La liste des seconds membres appaît ici comme une conjonction de preuve d'existence.

Soit deux graphes (arbres clos dans lesquel les feuilles sans nom sont autorisées à être relié à plusieur pères) considérés comme un seul graphe. L'algorithme d'unification est le suivant : Il prend comme argument deux points du graphe qui désigne initialement chacun un membre d'une règle. Si les deux points sont des opérateurs constants alors s'il sont différent, retourner false, sinon pour chaque fils appliquer l'algorithme d'unification entre un fils de l'un et le fils de l'autre correspondant, et si un algorithme retourne false alors retourner false. Si les deux points sont des variables alors si c'est la même variable ne rien faire, sinon faite pointer une variable sur l'autre. Si l'un est une constante et l'autre une variable alors faite pointer la variable sur la constante. De plus l'algorithme marque chaque point du graphe passé en premier argument et marque avec une autre marque chaque point du graphe passé en second argument. Et si le pemier argument s'avère déja marqué comme premier argument, l'algoritme s'arrète et retourne false. Et si le second argument s'avère déja marqué comme second argument, l'algoritme s'arrète et retourne false. Ceci afin d'éviter les boucles sans fin tel que causé par l'unification de x et de f(x) qui donne f(f(f(f(f(f(....)

L°[x,y,z...] et si on enlève le nom des variables (en gardant la structure de graphe qui lie les variables de même nom). Ce qui reviend à faire modulo une permutation quelconque des variables. Alors on obtient un ensemble de membre qui ont une autre signification.

Un membre représente l'ensemble des éléments qui sont unifiable avec lui. On peut le représenter sous forme d'un composant ayant n pattes, une pour chaque variable.

Lorsque la théorie T n'est pas vide, et qu'il existe des règles de simplification rendant égaux certain mots entre eux, la structure engendrée par L n'est plus libre et est notée :

Elle représente un ensemble de classe d'équivalence, une partition de <L>. La relation d'équivalence est ainsi définie : Quelque soit x et y appartenant à <L>, Si il existe une démonstration à partir des hypothèses sur x et y et de la théorie T, que x = y alors x est en relation avec y, sinon on fait le choix de la structure la plus libre possible et on concidère que x n'est pas en relation avec y. Cette définition utilise les hypothèses sur x et y exprimable

Une question subtile se pose, à savoir s'il existe une représentation des classes d'équivalence par un mot unique appartenant à la classe. En effet, à cause de la réfutation de l'axiome du choix, il ne nous est plus permis d'effectuer un nombre infini de choix arbitraires, tel que de choisir un réprésentant pour chaque classe d'équivalence lorsqu'il y en a un nombre infini.

Supposons qu'il existe une tel représentation. Nous appellons F l'application <L/T> --> <L> qui transforme tous éléments en un mot représentant sa classe d'équivalence, lui-même élément de cette classe.

On remarque que F est injectif et respecte les opérateurs de L à savoir : quelque soit x,y,u,v si F(x)=F(y) et F(u)=F(v) alors F(f(x)) = F(f(y)), F(g(x,y))) = F(g(u,v)), F(h(x)) = F(h(y)). Une application possédant ces propriétées s'appelle un plongement, un plongement involutif puisque F(F(x))=F(x), et est identifiable à une inclusion d'ensembles dans la même carrière qu'est l'ensemble L°.

Les langages s'emboitent les uns dans les autres comme des poupées russes. A chaque langage correspond un protocole qui constitue son aspect dynamique. Les protocoles s'empilent les uns sur les autres. En bas de la pile se trouve le protocole d'affectation des variables avec le meta-operateur binaire =. Puis se trouve le protocole de construction d'application avec le meta-opéretaur >. Puis se trouve le protocole de construction de terme clos avec les opérateurs de L.

Considérons la séquence A = (x,u,y,v) où x et y sont deux opérateurs de type t1 et u,v sont deux opérateurs de type t2. Le type de A est égale à (t1,t2,t1,t2). Dans une telle séquence seul x et y peuvent être permutés et u, v peuvent être permutés sans modifier le type de la séquence. On réécrit la séquence A par le doublon {(t1,t1),(t2,t2)}

Nous considérons les 3 types de comportements possibles de la fonction "ident", et donnons un nom pour chacun :

ident(x,y) décide en un temps fini si x=y ou si x#y.
ident=(x,y) semi-décide si x=y, c'est à dire répond oui en un temps fini si x=y sinon ne répond pas en un temps fini.
ident#(x,y) semi-décide si x#y, c'est à dire répond oui en un temps fini si x#y sinon ne répond pas en un temps fini.

Si la L-structure possède un moyen "ident" totalement caculable pour déterminer si deux éléments désignés par deux mots sont égaux, elle est dite constructible, et nous allons pouvoir l'utiliser comme model sans difficulté.

Si la L-structure possède seulement un moyen "ident=" qui semi-décide si deux éléments désignés par deux mots sont égaux, elle est dite inséparable. Il existe des éléments x et y tel que nous ne savons pas si x#y. models inséparables.

Si la L-structure possède seulement un moyen "ident#" qui semi-décide si deux éléments désignés par deux mots sont distinct, elle est dite séparable, model séparable.

Une égalité entre deux mots est une règles de simplification trop rudimentaire, on veut pouvoir exprimer des règles plus savantes de simplification, et l'on pourra par cette voix définir le langage de la logique. Noter qu'il n'y a pour l'instant aucune notion de vrai et de faux, et donc aucun calcul logique, il n'y a que des constuctions et des simplifications.

Par exemple, considérons le langage de présentation L = {a, f(.), g(.,.)}. La L-structure libre <a, f(.), g(.,.)> est égale à l'ensemble des mots du langage L :

<a, f(.), g(.,.)>= {a,f(a), g(a,a), f(g(a,a)), g(f(a),a), f(g(a,f(a)), f(f(a)), g(g(a,a),a), g(a,g(a,a))... }

La L-structure munie de ces règles de simplification, appellées axiomes de la L-structure, possède exactement 5 éléments :

Les éléments de la L-structure sont des classes d'équivalence de mots du langage L, et on les représente par un mot choisie dans leur classe. Deux mots m1, m2 sont équivalents ssi il existe une démonstration de leur égalité, c'est à dire ssi il existe une combinaison de règles de simplification qui mise bout à bout permette d'égaliser m1 à m2.

Deux objections de caractère intuisioniste apparaîssent. La première affirme que le procédé de construction du langage ne peut être appliqué indéfiniment si l'univers est fini. La seconde affirme qu'il n'existe pas toujours de procédé totalement calculable pour déterminer si deux mots d'une L-structure sont égaux. La notion même d'élément dépend de l'existence d'un algorithme, la meta fonction "ident" vue au chapitre "Philosophie et construction", déterminant si deux éléments sont égaux, c'est à dire si les deux mots du langages désignent le même élément.

/*****Ce type de règle de simplification qu'est l'égalité de deux mots s'exprime dans un langage plus riche obtenu en ajoutant le prédicat égale, = , d'arité 2, au langage initiale ainsi que le méta opérateur conjonction désigné par une virgule afin de pouvoir énumérer un ensemble fini de règles de simplification*****/

Mais avant d'approfondire cette question, nous allons prendre du recule afin de garder le niveau de généralité auquel nous prétendons, en introduisant un niveau d'abstraction supplémentaire avec le concepte de categorie de structures.

Qu'est-ce qui fait que deux structures mathématiques sont identiques au sens concret et pragmatique du terme et qu'elles soient finalement identifiables ?. Intuitivement, c'est la certitude de pouvoir exploiter avec la même force et le même développement toutes les connaissances propres de l'une des structures sur l'autre et inversement de tel sorte que l'on puisse mettre en oeuvre un procédé de traduction sûre pour passer de l'une à l'autre et inversement.

Par exemple, considérons le cas simple de deux langages similaires, le langage de présentation L1 = {a1, f1(.), g1(.,.)}et le langage de présentation L2 = {a2, f2(.), g2(.,.)} où seul les étiquettes changent. Considérons leurs L-structures libres respectives G1=<a1,f1,g1> et G2=<a2,f2,g2>

On parlera de fonction externe pour désigner une fonction en dehors du langage L, qui n'est ni une fonction élémentaire ni une composition de fonctions élémentaires.

On se libère du procédé de construction des L-structures, en considérant la définition des L-structures à isomorphisme totalement calculable près. Deux L-structures par exemple <a,f,g/A> et <a,f,g/B> sont isomorphes de façon totalement calculable ssi il existe une bijection totalement calculable h, fonction externe, entre ces deux L-structures traduisant chaque opérateur élémentaire d'une structure à l'autre, c'est à dire telque h(a)=a et h(f(x1))=f(h(x1)) et h(g(x1,x2))=g(h(x1),h(x2)). Toute propriétée dans une structures s'exprime dans l'autre structure grâce au procédé de traduction que constitue l'isomorphisme h totalement calculable.

Prenons quelques constantes d'arités diverses f(.), g(.,.), h(.), et quelques constants d'arité zéro a,b,c, que nous regroupons dans un ensemble d'opérateurs L = {a,b,c,f(.),g(.,.),h(.)}. L constitue une présentation d'un langage. L'univers de Herbrand L° = {a,f(a), g(a,a), f(g(a,a)), g(f(a),a), f(g(a,f(a)), f(f(a)), g(g(a,a),a), g(a,g(a,a))... } est l'ensemble des mots engendrés par L et par le procédé de composition, c'est à dire l'ensemble des arbres clos (appelé aussi termes clos) constitué par les opérateurs de L.

Un arbre est clos lorsque chaque opérateur dont il est constitué possède un nombre de fils égal à son arité. Par exemple les termes f, f(f), g(f,g) ne sont pas clos. Et si on respecte la convention de représenter les fils absents par un point, les termes précédent s'écrivent f(.) , f(f(.)), g(f(.),g(.,.)). De tels termes sont dit meta-clos. Pour les clore, il faut remplacer les points par des constantes tel que a,b,c ou par d'autres termes clos, et l'on obtient des termes clos suivants f(a), f(f(b)), g(f(c), g(a,a)), f(h(c))....

Implicitement les opérandes de g(.,.) sont différenciées et ordonnées, on étudira plus tard les cas dégénerés.

Ce qui se traduit par : pour tout mots u et v appartenants à L°1, u et v sont dans la même classe d'équivalence, si et seulement si : T |— u(x) = v(y), et pour tout mots r et s appartenants à L°2, r et s sont dans la même classe d'équivalence, si et seulement si : T |— r(x,y) = s(x,y).

L'axiome n°4 ouvre de nombreuses possibilités de complétions distinctes. Commençons par compléter notre théorie par une propriété sur les termes d'arité zéro. Un terme d'arité zéro peut être de nature fonctionnelle auquel cas il opére sur une liste vide d'opérande. On peut complèter l'axiome n°4 par un axiome d'inévolution, à savoir, qu'un terme n'opère pas sur une liste vide, ou alors qu'un terme qui opére sur une liste vide, produit seulement lui-même, et cette dernière règle peut alors, sans nous contraindre davantage, s'appliquer à tout terme.

Il s'agit là d'une bifurcation, c'est à dire que deux nouvelles voies ou branches apparaissent et peuvent être explorées, chacune complétant la théorie avec son axiome spécifique. Mais on peut continuer à explorer le tron commun, la théorie initiale, sans choisire ni l'une ni l'autre branches, ce qui constitue une troisième voie. Dans cette voie, l'application d'un terme à une liste vide n'est pas toujours possible et ne produit pas toujours le terme initiale.

Nomenclature codifiant les axiomes et les théories : On établi une nomenclature. Chaque théorie possède un numéro unique. Chaque axiome possède un numéro unique. Chaque théorie, exceptée la théorie initiale n°0, complète une théorie précédente appelé théorie père, à l'aide d'un axiome appellé complétion, et cet axiome peut être sémantiquement proche d'un autre axiome de la théorie père. Le lien de proximité sémantique se note en remplaçant le numéros par une succession de numéros séparés par des points ou des lettres. Ainsi l'axiome (3.1.2) désigne un axiome sémantiquement proche et apparaissant comme un perfectionnement de l'axiome (3.1) lui même proche de l'axiome (3). La qualité de complétion d'un axiome se note en introduisant les lettres. Ainsi les axiomes (a1), (b1), (c1) représentent trois axiomes exclusifs construisant 3 théories fils. Les axiomes (3a1), (3b1) représentent deux axiomes exclusifs proche de l'axiome 3 et construisant 2 théories fils. Ce faisant les axiomes de la théorie sont toujours numérotés dans l'ordre numérique sans tenir compte des lettres. Le lien de parenté entre deux théories se note en les énumérant dans l'ordre parent-enfant. Par exemple la théorie 0(3a1)2(5b1)7 désigne la théorie 0 complété par l'axiome (3a1) en la théorie 2, puis complété par l'axiome (5b1) en la théorie 7.

Appliquons notre nomenclature. Nous définissons deux axiomes ouvrant deux branches :

Et nous avons alors trois théories disponibles numérotées dans l'odre 0, 1, 2 et s'écrivant selon la nomenclature : 0, 0(4a1)1, 0(4b1)2.

Mais en y regardant de plus près, la théorie 1 et la théorie 2 s'avèrent trés proche l'une de l'autre. La théorie 2 s'obtient à partir de la théorie 1 en ajoutant simplement la fonctionnalité demandée sans autres conséquences structurelles. Les deux théories sont donc inscrites dans une même vision linguistique, c'est à dire placées dans une même catégorie, et donc ne proposent pas de véritable alternative entre elles, seulement un enrichissement qui peut toujours être fait à tout moment. Parcontre elles proposent une réelle alternative à la théorie initiale n°0, car elles la restreignent avec perte. Nous dirons que l'axiome (4a1) constitue une rupture, et que l'autre axiome (4b1) constitue la même rupture.

Catégorie et rupture : La notion de catégorie apparait comme une classification des théories. Et il y a maintenant trois niveaux de classifications ou d'égalités. Le premier niveau est la forme skolèmisé de la théorie. Le second niveau est la classe d'équivalence. Et le troisième niveau est la catégorie. La rupture est une complétion de la théorie faisant changer de catégorie. La rupture représente ainsi l'ensemble des axiomes T-catégoriel-équivalent permettant de passer de la catégorie de la théorie T à une autre catégorie.

La présence des mots d'arité non nulle n'est pas indispenssable mais constitue une porte ouverte pour les extensions futures des notions de langage et de la structure. La currification tout ou rien permet de définire L°¢, un langage plus vaste que L°, dans lequel l'opérateur I(f) s'étend en une application de L°¢ vers L°¢.

9) Les opérateurs L-emboitables

On obtient ainsi un nouveau langage qui autorise un terme à s'appliquer à des termes d'arité supérieur à zéro et à produire un terme d'arités supérieur à zéro. Dans ce nouveau langage, Les axiomes n°10 et n°11 ne sont plus valable.

L'opérateur point "•" est l'application identité x-->x. Il peut être utilisé dans l'expression d'un terme et possède donc deux arités. Il est un terme unaire retournant un terme de même type que son argument, et il est aussi un terme zéro-aire et peut être utilisé comme un élément. De même, le terme g(a,•) est l'application x-->g(a,x) et il peut être utilisé comme un argument c'est à dire un élément, il possède donc deux arités, uhn arité zéro et une arité 1.. On peut donc construire les deux termes g(a,•) et g(a,•)(b). L'opérateur binaire g appliqué au terme unaire "•" et au terme unaire g(a,•) produit le terme binaire g(•,g(a,•)) qui est l'application (x,y)-->g(x,(a,y)).

11bis : Tout terme appliqué à des arguments retourne un résultat d'arité égale à la somme des arités de ses arguments.

Autre exemple la composition de l'opérateur unaire f avec l'opérateur unaire "." produit le terme f(.) unaire qui est une application habituellement décrite par l'expression x-->f(x), et qui peut donc être appliquée à son tour à un terme zéro-air. Par exemple nous avons :

L'application correspondant au terme g(.,f(.)) est définie par (x,y)-->g(x,f(y)). On a remplaçer les constantes "." par des variables de noms distincts et ordonnés x,y,z...., et obtenu ainsi un terme d'arité 2. Autrement dit l'opérateur binaire g appliqué à l'opérateur zéro-aire "." et au terme zéro-air f(.), produit un terme d'arité 2. Et ce terme est dit L-emboitable.

Les variables doivent apparaître dans le corps des fonctions L-emboitable dans le même ordre que dans le n-uplet d'entré. Autrement dit il n'y a ni permuttations ni projections des variables tel que dans les exemples (x,y)-->g(y,x) et x-->g(x,x).

Un terme binaire g(.,f(.)) ne désigne pas un opérateur binaire, tant qu'il n'a pas été nommé par un nom unique (qui peut être le terme lui-même) et qui correspond alors à une extension du langage et à une concrétisation que constitue la définition du nouvel opérateur. Le terme représente plus qu'un nom, il constitue un programme, le programme du nouvel opérateur écrit dans le langage (L⋃{.})°. Si nous nommons le nouvel opérateur, nous sommes contraint pour obtenir la même structure d'ajouter dans la théorie la définition de l'opérateur par son programme sous forme d'une règle d'égalité.

Il y a bien un acte de nommage qui complète le langage, et il y a bien une acte de définision de l'opérateur par son programme qui complète la théorie.

Si nous choisissons de nommer l'opérateur avec le terme lui-même par g(.,f(.)) qui constitue son programme, alors la structure devient simplement <a,b,f(.),g(.,.),g(.,f(.))> et aucune règle d'égalité n'a besoin d'être ajoutée car elle est déjà comprise dans la formulation de l'opérateur g(.,f(.)). Il s'agit alors d'un opérateur complexe, une forme de racourci permettant de transposer des règles d'égalités particulièrement simple dans un opérateur complex. Ainsi par exemple, nous avons :

Si nous choisissons de nommer l'opérateur de façon anonyme sans préciser son programme, on ajoute dans la présentation du langage un nouvel opérateur h(.,.), ce qui étend le langage. Mais la théorie de la structure se complète également d'une règle de simplification supplémentaire qu'est l'égalité entre l'opérateur et le terme pour toutes les valeurs possibles de ses paramètres. Ce qui s'écrit h(x,y) = g(x,f(y)) en utilisant deux opérateurs variables x,y d'arité zéro et l'opérateur 2-aire "=" de type propositionnel. Le nouvel opérateur n'est qu'un raccourci. Il ajoute bien des degrés de liberté au langage mais n'ajoute pas de degré de liberté à la structure. La présentation du langage devient L = {a,b,f(.),g(.,.),h(.,.)}. Et la théorie contient une règle supplémentaire T = {h(x,y) = g(x,f(y))}. La présentation de la structure devient <a,b,f(.),g(.,.),h(.,.) / h(x,y) = g(x,f(y)>, et nous avons :

Le langage propositionnel utilisé peut être également limité de la même façon, tel le langage propositionnel L-constructible-faible constitué de (L union {.})°0 auquel on ajoute l'opérateur 2-aire "=" de type propositionnel. Nous avons :

Cela constitue deux façons de présenter la même structure. La diffférence tient dans le choix de définir h par un programme ou par une propriété, de poser le programme h = g(.,f(.)) ou la propriété h(.,.) = g(.,f(.)). On remarque alors que le langage L° auquel on ajoute l'opérateur 2-aire "=" de type propositionnel (qui est symétrique) permet d'expimer à la fois les programmes et les propriétées. Une expression du genre h=g signifie que le programme de h est égale au programme de g, et une expression du genre g(.,.)=f(.) signifie g(x,y)= f(x).

Ensemble image :
Les ensembles images sont représentée par des termes de (L union {x,y,z})°. Un terme correspond à l'ensemble des termes de L° qui lui sont unifiables.

Le terme g(.,f(.)) n'est pas l'opérateur proprement dit, c'est son programme écrit dans un langage rudimentaire de programmation qu'est le langage d'opérateur simple (L union {.})°.

Pour les opérateurs isolés, la currification tout ou rien permet de définir les expressions suivantes comme suit : f = f(x), f(f) = f(f(x)), g(f,a) = g(f(x),a), g(f,g) = g(f(x),g(y,z)).

Forme normale :
Deux termes distincts de (L union{.})°0 désignent nécessairement deux opérateurs différents. Soit ils n'ont pas la même arité, soit il existe un n-uplet de L°0^n qui est transformé par les deux opérateurs en deux mots distincts. Autrement dit, la structure des opérateurs L-constructibles-faibles est libre et est bien liée de façon biunivoque au langage libre (L union{.})°0.

Les termes du langage (L union {.})° sont tous de type 0 à l'exceptions des opérateurs isolés f et g, respectivement de type 1 et 2. Nous voulons définir des langages plus riche autorisant la production d'opérateurs d'arité diverses et permettant de les manipuler nativement. La currification va nous permettre de construire naturellement des opérateurs d'arité supérieur à zéro. Elle autorise la composistion avec des opérandes de tout type.

Dans un langage L°, un terme d'arité n est une application de L°ⁿ vers L°, et une fois nommé, il constitue un opérateur d'arité n. Cela constitue une extesion du langage et une complétion de la théorie d'égalité.

Un autre procédé de construction consiste à définir une opération de composition et à en prendre sa clôture. Mais un opérateur d'arité supérieur à 1 possèdent plusieurs façons de se composer. Pour préciser sur quel entré la composition s'opère on transmet une liste d'argument dans laquelle les arguments laissés libres sont désignés par l'élément point "•". Il faut donc procéder préalablement à une extension élémentaire L°[•]. Et dans cette extension, l'élément point possède deux rôles, celui d'élément permettant de désigner les fils libres, et celui d'application identité • = (x-->x). Tous les termes clos dans L°[•] jouent un double rôle, celui d'élément et celui d'application produisant le terme en question en remplaçant les points dans l'ordre de leur apparition de gauche à droite par les variables dans l'ordre de leur appel.

Dans ce langage tous les termes sont à la fois éléments et applications. Les termes sans point "•" sont des applications prenant en argument une liste vide d'argument. Par exemple f(a) est un élément et est aussi une application mais qui ne peut s'appliquer que sur la liste vide d'argument f(a)( ).

par des langages plus simples tel que la construction des termes terminals clos, et des séquences terminales close.

Remarquez alors que le terme `g(a)` correspond au terme clos `g(a,.)` et non au terme clos `g(.,a)`. On a donc fait un choix, celui de remplire les opérandes attendues de gauche à droite en laissant éventuellement ses dernières opérandes vides.

Un noeud dont seul les dernières opérandes à droite peuvent être vides, est appellé un noeud terminal-clos. Un terme est donc un arbre dont les noeuds sont terminal-clos.

Les termes clos de `Luu{"."}` sont donc un peu plus riche que les seuls termes de `L`.

`L^@`	`L"*"`
`a`	`a`
`b`	`b`
`f(a)`	`fa`
`f(b)`	`fb`
`g(a,a)`	`gaa`
`g(f(a),b)`	`gfab`
`g(a,g(b,f(a)))`	`gagbfa`

`L"*"`	`L°^m`
`g`	`g"(.,.)"`
`gg`	`g(g"(.,.)",".")`
`a`	`a`
`ga`	`f(a,".")`
`ag`	`a, g"(.,.)"`
`ggabf`	`g(g(a,b),f"(.)")`
`abfga`	`a, b, f(g(a,"."))`
`fafbb`	`f(a), f(b), b`
`agab`	`a, g(a,b)`

Opérateurs `L°^¢`-exprimables	`L°^¢`
`a`	`a`
`x\|->f(x)`	`f`
`x\|->f(f(x))`	`f(f)`
`(x,y)\|->g(x,y)`	`g`
`x\|->g(f(x),a)`	`g(f,a)`
`(x,y)\|->g(f(x),f(y))`	`g(f,f)`

Opérateurs non `L°^¢`-exprimable	Cause
`x\|->a`	C'est une projection.
`x\|->x`	L'identité n'est pas définie.
`(x,y)\|->x`	C'est une projection.
`x\|->g(x,a)`	L'opérateur g possède comme opérandes une variable et un terme qui n'est pas une variable.
`x\|->g(x,x)`	C'est une projection.
`(x,y)\|->g(y,x)`	Il y a permutation des variables.

Forme série	Forme parallèle avec opérateur identité "."	Forme parallèle avec currification	Forme parallèle sans opérateur identité ni currification
`g(a, f(b))`	`g(a,f)(b)`	`g(a,f)(b)`	`g(a,f)(b)`
`g(f(b), f)`	`g(f,f)(b,.)`	`g(f, f)(b)`	`g(f(b), f)`
`g(g(g(g,a), f(b)),f)`	`g(g,f)(g,f,.)(g,a,b,.)`	`g(g,f)(g,f,)(g,a,b)`	`g(g(g(g,a), f(b)),f)`
`g(a, f(f(b)))`	`g(a,f)(f)(b)`	`g(a,f)(f)(b)`	`g(a,f)(f)(b)`
`g(f(f(b)), g)`	`g(f,g)(f,.,.)(b,.,.)`	`g(f,g)(f)(b)`	`g(f(f)(b), g)`

Langage d'opérateurs (suite)

1) Les termes

2) Le langage de caractère `L"*"`

3) La cloture terminale des séquences

4) La cloture terminale des termes

5) La currification tout ou rien

Construction :

Forme normale :

6) L'opérateur identité "."

Construction :

Forme normale :

7) Les séquences finies

8) La currification

Cas des langages sans séquence finie :

9) Quelques langages de caractères

10) Hierarchie des langages

9) Les opérateurs L-emboitables

`L"*"`	`L°^t`
`a`	`a`
`g`	`g"(.,.)"`
`ga`	`g(a,".")`
`gg`	`g(g"(.,.)",".")`
`gga`	`g(g(a,"."),".")`

Opérateurs `L°c`-exprimables	L°c
`a`	`a`
`x\|->f(x)`	`f`
`x\|->g(a,x)`	`g(a)`
`(x,y)\|->g(x,y)`	`g`
`x\|->g(f(x),a)`	`g(f,a)`
`(x,y)\|->g(g(a,x),y)`	`g(g(a))`

Opérateurs non `L°^c`-exprimables	Cause
`x\|->a`	C'est une projection.
`x\|->x`	L'identité n'est pas définie.
`(x,y)\|->x`	C'est une projection.
`x\|->g(x,a)`	L'opérateur g possède comme opérandes une variable x qui n'est pas en place terminal
`x\|->g(x,x)`	C'est une projection.
`(x,y)\|->g(y,x)`	Il y a permutation des variables.

*`L""`**	`L°^m`
`fa`	`f(a)`
`fab`	`f(a), b`
`ga`	`g(a,.)`
`gg`	`g(g(,.),.)`

*`L"'"`**	`L°¢m`
fa	f(a)
f'a	f, a
f'fa	f, f(a)
gf'a	g(f,a)
gg'fa	g(g,f(a))

*`L\|""`**	`L°^(cs)`
`fa`	`f,a`
`f\|a`	`f(a)`
`ff\|ab`	`f(a),f(b)`
`ff\|fg`	`f(f),f(g)`

*`L·""`**	`L°^(¢us)`
`f`	`f`
`f·`	`f(.)`
`f··`	`f(.),.`
`f·a`	`f(.),a`
`fa`	`f(a)`
`g·a`	`g(.,a)`
`g··f·`	`g(.,.), f(.)`

Propriété	Description
`u`	Unitaire.
`t`	Cloture terminal des termes.
`¢`	Currification tout ou rien.
`c`	Cloture terminal des opérateurs. Currification.
`s`	Avec séquence.
`m`	Avec séquences terminal-closes.

Lien logique entre les propriétés	Description
`m => s`	Les séquences terminales closes contiennent les séquences.
`c => ¢`	La currification contient la currification tout ou rien.
`c => t`	La currification (opérateurs terminals clos) comprend les termes terminals clos.
`(t et s) => m`	Les termes terminals clos avec séquence contiennent les séquences terminales closes.
`(¢ et u) => c`	La currification tout ou rien avec l'identité comprend la currification
`(c et s) => m`	Les termes terminals clos avec séquence contiennent les séquences terminales closes.

Classe d'opérateurs	Exemple d'opérateur	Mot	Langage d'opérateurs
L-emboitable avec currification tout ou rien Les variables sont sans permutation ni projection, et pour chaque opérateur elles occupent soit aucune de ses opérandes, soit toutes ses opérandes.	`x-->g(f(x),a)`	`g(f,a)`	`L°^¢`
L-emboitable terminal-clos Les variables sont sans permutation ni projection et sont en place terminal du terme, c'est à dire occupent les dernières places à droite.	`(x,y)-->g(g(b,x),y)`	`ggb` `g(g(b))` `g(g(b,.),.)`	`L` `L°^c` `L°^t`*
L-emboitable terminal-clos avec currification tout ou rien Les variables sont sans permutation ni projection et peuvent prendre les places terminales du terme, c'est à dire les dernières places à droite dans le terme, et pour chaque opérateur elles occupent soit aucune de ses opérandes, soit toutes ses opérandes.	`x-->g(f(x),g(a,y))`	`gf'ga` `g(f,g(a,.))` `g(f(.),g(a,.))`	`L'` `L°^(t¢)`* `L°^(u¢)`
L-emboitable avec currification Les variables sont sans permutation ni projection et en place terminal de chaque opérateur, c'est à dire qu'elles occupent les dernières places à gauche dans chaque opérateur.	`x-->g(g(a,x),b)`	`g\|gb\|a` `g(g(a),b)` `g(g(a,.),b)`	`L\|` `L°^c`* `L°^(u¢)`
L-constructible-faible Les variables sont sans permutation ni projection	`x-->g(x,a)`	`g(.,a)` `g·a`	`L°^(u¢)` `L·*`
L-constructible Composition des opérateurs au sens générale. Programmation sans boucle.	`(x,y)-->g(y,x)` `x-->g(x,x)`	`g(2,1)` `g(1,1)`	`L°^&`
L-recursif Programmation qu'avec des boucles "for".
L-calculable

Opérateur L-constructible		Ensemble image
L°s^2	L°s&	L°s&/Permutation
(x,y)-->(y,x)	2, 1	1,2
x-->(f(x),x)	f(1), 1	f(1),2
(x,y)-->g(y,f(x))	g(2,f(1))	g(1,f(2))
(x,y,z)-->g(z,g(x,x))	g(3,g(1,1))	g(1,g(2,2))
(x,y)-->f(y)	f(2)	f(1)
(x,y)-->f(x)	f(1)	f(1)
x-->f(x)	f(1)	f(1)

L°s[z]^2	L°s&[z]	L°s&[z]/Permutation
(x,y)-->g(y,g(z,x))	g(2,g(z,1))	g(1,g(z,2))

Fonction L-constructible		Ensemble image
L°s^2	L°s&^2	L°s&/Permutation
x-->a	1-->a	a
x-->x	1-->1	1
x-->f(x)	1-->f(1)	f(1)
f(x)-->x	f(1) -->1	1
(x,y)-->f(y)	(1, 2)-->f(2)	f(1)
(f(y),x)-->g(x,y)	(f(1),2)-->g(2,1)	g(1,2)
(f(y),x)-->(x,g(y,x))	(f(1), 2)-->(2, g(2,1))	1, g(1,2)
(x,y)-->g(y,x)	(1, 2)-->g(2,1)	g(1,2)
(x,y)-->(y,x)	(1, 2)-->(2,1)	1, 2
g(x,y)-->(x,y)	g(1, 2)-->(1,2)	1, 2

L°s[z]^2	L°s&[z]	L°s&[z]/Permutation
(f(x),y)-->g(y,g(z,x))	f(1),2-->g(2,g(z,1))	g(1,g(z,2))

(L union {x,y,z})°	Ensemble
a	{a}
x	L
f(x)	{f(x) / xL}
g(x,a)	{g(x,a) / xL}
g(x,f(y))	{g(x,f(y)) / (x,y)L^2}
g(f(x),g(y,z))	{g(f(x),g(y,z)) / (x,y)L^2}

(L union {.})°	Opérateur	Ensemble image (L union {x,y,z})°
a	a	a
.	x-->x	x
f(.)	x-->f(x)	f(x)
g(.,a)	x-->g(x,a)	g(x,a)
g(.,f(.))	(x,y)-->g(x,f(y))	g(x,f(y))
g(f(.),g(.,.))	(x,y,z)-->g(f(x),g(y,z))	g(f(x),g(y,z))