1) Introduction

La science de notre ére a cette capacité unificatrice, de réunir toutes les questions fondamentales une seule, en un seul principe qu'est la loi qui généralise..., et qui rammène toutes les explications en une seule explication. Elle est la cause de l'avènement des religions monothéistes sur celles plurithéistes, et elle constitue un argument en faveur de cette unicité dans la démarche de construction des sciences et de notre langage informatique idéal.

Les formes d'implémentation à la fois rudimentaires et fondamentales correspondent à des mécanismes de raisonnement à la fois rudimentaires et fondamentaux. On commence par exhiber le principe de l'égalité et de la transitivité qui joue un rôle fondamental en logique du premier ordre. Comment implémenter efficacement l'égalité et sa transitivité ? On le fait en utilisant les pointeurs, et en chaînant ces pointeurs pour procéder à des affectations permanentes.

Pour unifier variable et pointeur, on pose qu'une variable possède un premier pointeur dont l'adresse où il est mémorisé n'est pas modifiable, sauf à supprimer la variable et à la recréer. Ce choix se justifie pour des raisons d'efficacité de l'interpreteur. Les valeurs désignées par les variables sont de taille très variables, c'est pourquoi il est plus pratique de procéder à un adressage indirecte passant d'une table de hachage des variables de taille fixe pour aller dans un empilement de données de taille trés variables couvrant l'ensemble de l'espace mémoire. C'est également pourquoi ces pointeurs-ci devront être capables de pointer n'importe quel octet dans la mémoire vive.

Un pointeur pointe un octet qui est le premier octet d'un bloc constituant la donnée pointée par le pointeur. Ce bloc peut désigner un autre pointeur ou une donnée. Notez qu'il doit donc y avoir une première information de type pour déterminer si c'est un pointeur ou une donnée.

Par exemple considérons trois variables contenant directement `x"='ga'"`, `y"='bu'"` et `z"='zo'"`. Ces variables possèdent chacune un premier pointeur qui pointe respectivement sur les valeurs `"'ga'","'bu'","'zo'"`. Un pointeur peut pointer une valeur ou un autre pointeur. La valeur de `x` s'obtient en regardant ce que pointe `x` et si c'est un pointeur, en regardant ce qu'il pointe à son tour et ainsi de suite jusqu'à arriver sur une valeur. Et si on tourne en rond alors la valeur de `x` désigne une valeur inconnue représentée par cette boucle de pointeurs.

Le pointeur nil n'est pas utilisée pour indiquer que la variable est libre. La variable `x` est libre si son premier pointeur pointe sur lui-même. Et si son premier pointeur pointe une succession de pointeurs aboutissant à une boucle de pointeurs, alors la variable `x` pointe une variable libre. Le pointeur nil désignera plutôt l'échec, l'absence de possibilité, ou autre chose.

Chaque variable constitue une chaine de pointeurs avec un premier pointeur et un dernier pointeur qui peuvent coïncider. Le dernier pointeur pointe une valeur, ou pointe une boucle, ou coïncide avec le premier pointeur.

L'instruction `x"="y` modifie le premier pointeur de `x` pour le faire pointer sur ce que désigne `y`. C'est l'affectation classique des variables. L'inconvénient de cette affectation, c'est qu'il y a une perte d'information. Les instructions `x"="y; y"="z` ne vont pas nécessairement entrainer que `x"=="z`. Pour remédier à cela on définira un autre type d'affectation qu'est l'égalité permanente.

On ne rentre pas dans les détailles de l'implémentation, de ce que fait le bas niveau de protocole, on donne seulement les degrés de liberté suffisants pour que le protocole de bas niveau est au moins la possibilité de le faire, à défaut de préciser comment il le fait.

2) Variable

Ainsi il n'y a plus de différence entre une variable et un pointeur. Une variable peut pointer sur une cascade de pointeurs aboutissant à une valeurs ou à un terme dont les arguments peuvent aussi être des cascades de pointeurs pointant vers des valeurs ou des termes.... Un pointeur est une variable anonyme contenant une addresse désignant une case mémoire pouvant contenir une valeur, un terme ou un autre pointeur. Le nom du pointeur est son adresse mémoire.

On utilise l'opérateur spécial `&` qui appliqué à `x` produit son prermier pointeur. Ainsi `&x` est le premier pointeur de `x`, identifié à son adresse mémoire. Comme nous somme toujours dans un langage monotype, nous avons `x"=="&x`, les variables comme les pointeurs, passés en argument sont d'abord évalué en valeur d'un seul type.

Puis les termes eux-mêmes peuvent être identifiés à des structures de pointeurs en considérant l'appel d'un opérateur n-aire comme un n-uplet de variables labelisé par l'opérateur. Par exemple l'appel de l'opérateur binaire `f` appliqué aux opérateurs `x` et `y`, que l'on note `f(x,y)`, s'il est anonymisé, il représente un triplet de premiers pointeurs.

`f(x,y)`
`&f(&x,&y)`

Comme nous sommes dans un langage monotype, la variable, la valeur, le terme et le pointeur doivent être de même type, seul le mécanisme de calcul présidé par les opérateurs change.

La notion de variable évolue, elle doit toujours commencer par un premier pointeur. Ainsi la variable peut toujours être perçu comme un pointeur. Et l'adresse de cette permière case mémoire contenant ce pointeur, et qui est identifié à la variable, ne change pas sauf si on détruit la variable et qu'on la recrée.

De même la notion de terme évolue. Un terme constitué d'un opérateur n-aire appliqué à `n` arguments, est perçu comme un assemblage constitué de `n"+"1` variables, une pour chaque argument de l'opérateur et l'opérateur en question.

Le concept de pointeur ouvre un nouvel horizon permettant de définir des arbres, des données partagées, des termes partageant en commun des sous-terme, et permetant de définir des graphes. Il permet de programmer un algorithme d'unification de complexité linéaire. On conçoit dans notre langage terminologique monotype différents opérateurs spéciaux gérant ces graphes.

3) Variable libre

La variable étant un pointeur, vers quoi doit-elle pointer pour indiquer qu'elle est libre ?. Elle peut pointer sur elle-même ou pointer sur une boucle de pointeurs. De même un terme composé d'un opérateur appliqué à `n` arguments libre (c'est à dire que l'on peut à cette instant affecté arbitrairement à n'importe quelle valeur) correspond à un `(n"+"1)`-uplet de pointeurs, le premier pointeur étant celui de l'opérateur, les suivants pointant sur eux-mêmes ou sur des boucles de pointeurs distincts.

4) Les différentes évaluations

La variable `x` sera évaluée de façons différentes selon que l'on attend une valeur, un terme, un premier pointeur ou un dernier pointeur :

• Si on attend une valeur, on regarde vers quoi pointe le premier pointeur chez `x` et si c'est un pointeur on regarde vers quoi pointe le pointeur et ainsi de suite jusqu'à obtenir une valeur ou un terme dont on réitère le calcul pour retourner une valeur. Mais si on repasse par un même pointeur ce qui dénote une boucle, alors il s'agit d'une variable libre, non évaluable, alors on retroune le terme `x` telle quelle. Puis on effectue un aspect qui modifie tous les pointeurs du chemin ainsi parcouru pour les faire pointer sur le dernier pointeur pointant sur la valeur, le terme ou la boucle.
  
• Si on attend un terme, on regarde vers quoi pointe le premier pointeur chez `x` et si c'est un pointeur on regarde vers quoi pointe le pointeur et ainsi de suite jusqu'à obtenir une valeur ou un terme que l'on retourne. Si c'est une valeur, on la remplace par son expression brute hexadécimale ou par son éventuel alias primaire (un opérateur nullaire qui lui est égal). Mais si on repasse par un même pointeur ce qui dénote une boucle, alors dans ce cas la boucle représente un terme anonyme qui est retourné. Puis on effectue un aspect qui modifie tous les pointeurs du chemin ainsi parcouru pour les faire pointer sur le dernier pointeur pointant sur la valeur, le terme ou la boucle.
   
• Si on attend un premier pointeur, on retourne le pointeur correspondant à `x` c'est à dire le pointeur identifié à `x`, appelé aussi le pointeur de début de chaine.
   
• Si on attend le dernier pointeur, on regarde vers quoi pointe le premier pointeur chez `x` et si c'est une valeur ou un terme alors on retourne ce premier pointeur. Par contre si c'est un pointeur on regarde vers quoi pointe le pointeur et ainsi de suite jusqu'à obtenir une valeur ou un terme et dans ce cas on retourne le pointeur pointant vers cette valeur ou ce terme. Mais si l'on repasse par un même pointeur ce qui dénote une boucle, alors on retourne le dernier pointeur pointant vers le pointeur de repassage, c'est à dire pointant sur la boucle. Puis on effectue un aspect qui modifie tous les pointeurs du chemin ainsi parcouru pour les faire pointer sur le dernier pointeur.

Toute variable peut être vue comme une valeur, un terme, un premier pointeur ou un dernier pointeur. Et c'est l'opérateur qui précice comment est attendu chacun de ses arguments. Les pointeurs ainsi définis vont permettre de concevoir des algorithmes de complexité linéaire qui n'auraient pas pu être facilement mis en oeuvre sans cette artifice.

On peut ainsi définir la modification physique de `x` qui établit un lien physique vers `y` notée `x":="y` qui raccorde le dernier pointeur de `x` sur le premier pointeur de `y`. Ainsi après l'aspect mettant en oeuvre les raccourcis, toutes les variables pointant sur `x` pointent désormais sur le premier pointeur de `y`. Et chacune de leur modification future de valeur changera la valeur de toutes.

En n'utilisant que cet opérateur de modification physique `":="`, on met en oeuvre la transitivité de l'égalité, il n'y a aucune perte d'information sur l'égalité entre variable. Puis, l'aspect mettant en oeuvre les raccourcis est appliqué. Cela consiste à chaque parcour d'un chemin de pointeurs, à faire pointer tous les pointeurs du chemin sauf le dernier sur ce dernier pointeur. Cet aspect applique la transitivité de l'égalité pour racourcir le chemin. De nombreux algorithmes vont devenir de complexité linéaire grace à cette simple astuce.

5) Affection d'un terme à une variable

L'affectation d'un terme à une variable se fait par une instruction d'égalité plus forte. On utilise l'opérateur spécial d'affectation, de nom long affectationForte, et qui s'applique à deux arguments. Le premier argument est une variable, et le second argument est un terme. Puis on le dote d'une syntaxe centrée de priorité faible avec comme nom court `"≡"`. Par exemple :

`x"≡"g(a,y)`

Dans cette instruction, ce n'est pas la valeur calculée par `g(a,y)` qui est affectée à la variable `x` mais le terme lui-même `g(a,y)` qui est affecté à `x`. Ainsi la variable `x` contiendra un programme d'expression `g(a,y)` qui sera donc réévalué au moment où l'on calculera `x`. Considérons maintenant le cas où le second argument est simplement une variable `y`, nous avons l'instruction suivante :

`x"≡"y`

Et c'est le terme `y` qui est affecté à `x` et non sa valeur, et qui sera évalué au moment où l'on évaluera `x`. Considérons maintenant l'instruction suivante :

`x"≡"x`

Cette instruction rend libre la variable `x`. Et on l'a remplacera par un pointeur pointant sur lui-même qui constitue une configuration équivalente mais plus simple. Considérons maintenant l'instruction suivante :

`x"≡"f(x)`

Alors on est dans une situation récurcive. L'évaluation de `x` va produire le terme `f(x)` qu'il faudra à son tour évaluer si on attend une valeur, pour produire `f(f(x))` et ainsi de suite. La valeur de x sera mutliple, elle sera `x,f(x),f(f(x))...`

Comme nous souhaitons optimiser la complexité des calculs, on ne peut pas rester sur un modèle de calcul ne proposant qu'un seul résultat à la fois. Il convient de prévoir des séquences de termes ou de valeurs comme résultat, et de se donner un moyen pratique pour ré-aiguiller arbitrairement ces sorties vers les différentes entrées des opérateurs.

D'une manière générale, une suite que l'on n'aplatit pas peut contenir des sous-suites et donc peut former un arbre. Or cela recouvre le principe de construction d'un terme que l'on a déjà mis en oeuvre et qui correspond à l'opérateur binaire virgule.

Une suite que l'on aplatit constitue une séquence, un flux de termes. Et il y a trois distinctions à faire :

• Soit le flux n'est pas borné, c'est un canal qui peut transmettre un nombre non borné de termes ou de valeurs. Ce cas sera traité avec les canaux.
   
• Soit le flux est de taille variable mais bornée. Ce cas sera traité avec les opérateurs d'arité variable.
   
• Soit le flux est de taille fixe.

On s'en tient d'abord à une arité de sortie fixe sous une forme symétrique de l'arité d'entrée. L'opérateur possède une arité d'entrée qui est le nombre d'arguments qu'il prend, et il possède une arité de sortie qui est le nombre d'arguments qu'il produit. Et nous devons pouvoir rediriger chaque sortie vers une entrée de notre choix. Prenons par exemple un opérateur `f` d'arité (2,3) c'est-à-dire d'arité d'entrée 2 et d'arité de sortie 3. Et considérons l'instruction d'affectation suivante :

`(x,y,z)=f(a,b)`

Cela signifie que les valeurs d'entrées de l'opérateur sont celle de `a` et `b`, et qu'une fois le calcul fait, le résultat est une séquence de trois valeurs de sortie affecté à la séquence des trois variables `x,y,z` respectivement.

On peut alors représenter l'opérateur `f` comme un composant possédant 2 entrées et 3 sorties, et au lieu de donner des noms à ces entrées et sorties, on trace des lignes reliants, comme dans un circuit electrique, les sorties de certains composants vers les entrées d'autres composants, mais sans faire de cycle pour l'instant, formant juste un arbre.

Puis on ajoute des composants qui vont aiguiller les flux de données, et on ajoute la possibilité de faire des boucles, les opérateurs devant alors proposer des résultats initiaux. Le circuit devient un graphe algorithmique. Les variables disparaissent pour désigner simplement des raccords liant une sorties de composant à plusieurs entrées de composant.

On voit ici l'ébauche d'une nouvelle notation dite "notation de l'informaticien" qui se distingue de la "notation du physicien" identifiant le nom de la fonction à celui de la variable contenant le résultat de la fonction. Pour l'informaticien, le processus `f` est un composant qui prend deux entrées et qui retourne trois sorties.

8) Opérateur variable

L'opérateur peut également être variable. Autrement dit, la variable peut posséder une arité non-nulle d'entrée et une arité de sortie. Une variable d'arité `(n,m)` contient un terme particulier qui est un programme écrit dans le langage idéal, qui prend `n` arguments en entrée et qui retourne `m` résultats en sortie.

Pour définir sous la forme d'un terme un programme d'arité `(2,2)`, on utilise l'opérateur de définition de fonction de nom long fonction et de nom court `|->` d'arité variable, avec une syntaxe centrée et où les arguments sont séparés par des virgule. Par exemple :

`x,y |-> g(x,f(x)),g(y,x)`

Cela correspond exactement au bloc de code suivant :

`{x,y | g(x,f(x)),g(y,x)}`

Les termes de gauche forment l'entête de l'opérateur et correspondent à des déclaration de nouvelles variables dont la portée est limitée à l'opérateur `|->` ou au bloc de code. Les termes de droite forment le corps de l'opérateur et correspondent aux résultats. La priorité syntaxique de l'égalité étant plus faible, nous pouvons écrire :

`h ≡ x,y |-> g(x,f(x)),g(y,x)`
`h ≡ {x,y | g(x,f(x)),g(y,x)}`

La variable `h` est alors modifiée pour contenir le terme `x,y |-> g(x,f(x)),g(y,x)` c'est à dire le bloc de code `{x,y | g(x,f(x)),g(y,x)}` qui correspond à un programme d'arité (2,2) c'est à dire d'arité d'entrée 2 et d'arité de sortie 2. Déjà il est possible d'écrire des fonctions récurcives telle que par exemple :

`f ≡ x |-> g(f(x),x)`

L'évaluation de `f(a)` va produire le terme `g(f(a),a)` qu'il faudra à son tour évaluer pour produire `g(g(f(a),a),a)` et ainsi de suite.

9) La compilation

L'opérateur peut se compiler en un programme directement exécutable, il contient alors une valeur qu'est le programme compilé c'est à dire un exécutable écrit en langage machine, qui prend `n` arguments en entrée et qui retourne `m` résultats en sortie. On perçoit donc plusieurs entrées qui se raccordent à l'opérateur et qui produit plusieurs sorties.

-*-*-*-*-*-*-*-*-*-*-

L'opérateur spécial de compilation est `ℭ`.

`f=ℭ(x |-> g(g(x,b),x))`

Le programme ainsi compilé pourra s'exécuter dans le même contexte c'est à dire dans le même bloc de code ou dans un sous-bloc de code sachant que si la variable `x` est masquée dans un sous bloc, la compilation n'en tiendra pas compte et le `x` du programme correspondra au `x` du bloc parent où a eu lieu la compilation. Les composantes du programmes compilés doivent avoir été déclarées dans un bloc parent ou de manière static, sinon leur référence pointe dans le décor !. On voit ainsi la distinction entre l'exécution d'un programme compilé qui ne consulte pas le contexte et l'interprétation d'un programme qui dépend du contexte :

`f=ℭ(x |-> g(f(x),x))`
`f(a)`

`f ≡ x |-> g(f(x),x))(a)`
`f(a)`

Le langage machine s'abstraitise. C'est en fait un langage de bas niveau de protocole dont nous avons tout loisir de définir et qui permet de construire le langage universel par dessus. Le protocole de bas niveau constitue un moteur à l'image du runtime java par exemple.

Pour effacer un opérateur ternaire `f` on pourra écrire :

`f≡x,y,z|->f(x,y,z)`    ou   `f"≡"ℭ (x,y,z|->f(x,y,z))`

10) Filtre par unification et par condition

On étend la définition de fonction en ajoutant un mécanisme d'unification des argments lors de l'appel de la fonction qui constitue un filtre des données d'entrée. On utilise pour cela, l'opérateur de définition de fonction avec pré-unification de nom long fonctionUnification et de nom court `↬` d'arité variable, avec une syntaxe centrée et où les arguments sont séparés par des virgules. Considérons la fonction suivante :

`h = g(x,x),y ↬m(x,y)`

Le calcul de `h(z,t)` va d'abord procéder à l'unification de `z,t` et de `g(x,x),y`. Puis si l'unification réussit alors le calcul va retourner `m(x,y)` en remplaçant `x` et `y` par leur valeur issue de l'unification. Et si l'unification échoue alors le calcul va retourner fail, ce qui signifie que les données sont en dehors du domaine de définition de `h` et que la fonction est arrivé à le déterminer.

Si on souhaite créer une variable dont le nom est déjà présent, on ajoute simplement l'opérateur `tt"var"` devant. Et l'opérateur `tt"var"` sera distributif vis à vis de l'opérateur virgule faisant que var `tt"var" x,y,z` sera identique à `tt"var" x, tt"var" y , tt"var" z`. Notez que dans cette exemple `g` peut être une variable libre dont l'arité sera déduite par la forme d'appel standart utilisée.

On ajoute comme filtre une condition. On utilise l'opérateur `?` `↬` :

`h = g(x,x),y  ? f(x)"=="y ↬m(x,y)`

Délors il ne suffit pas que l'unification réussisse mais il faut également que la condition retourne vrai.

11) Définition par morceau

On autorise la définition par morceau. On utilise l'opérateur "ou" représenté par le symbole `||`. Par exemple :

`h = f(x),g(y,x) |->m(x,y) "||"`
        `f(y),y |->g(y,y) "||"`
        `a,x ? g(a,x)"=="g(x,a)|->f(x)`

Les unifications sont testées dans l'ordre jusqu'à obtenir une réussite, et on s'arrète à la première réussite pour retourner le corps correspondant et l'évaluer.

12) L'unification de terme

L'unification de termes joue un rôle fondamental dans la logique du premier ordre, et également en informatique car elle est de complexité linéaire grâce à l'usage des pointeurs comme nous allons le voir. La meilleur façon d'expliquer ce qu'est l'unification de deux termes, est de prendre un exemple. On définit le langage `"<"a,b,f"(.)",g"(.,.)>"`. A ce stade, `a,b,f"(.)",g"(.,.)"` sont des opérateurs constants et toute autre nom est un opérateur variable. On considère deux termes

`g(g(x,g(y,z)),y)`

`g(g(x,x),g(a,x))`

Il y a donc 3 opérateurs variables `x, y, z` qui sont initialement des variables libres (premier pointeur pointant sur lui-même). L'unification peut se programmer en une fonction récurcive. On construit un langage de programmation dans le quel cet algorithme s'écrit le plus simplement possible. Un terme se décompose en une racine et une séquence d'arguments. On note `X` une métavariable contenant le terme. On note `A(X)` la racine du terme et `S(X)` la séquences des arguments. On note `nb(S(X))` la taille de la séquence `S(X)`, et `S(X)[i]` le ième argument de la séquence `S(X)`. L'unification pourrait s'écrire ainsi :

`"unifier" =`
      `X,Y ? X"==nil" |-> X"="Y; "true ||"`
      `X,Y ? Y"==nil" |-> Y"="X; "true ||"`
      `X,Y |-> S(X)"=="S(Y) &&`
            `n"=nb"(S(X)); n"==nb"(S(Y)) &&`
            `b"=true"; "for"(i"="0,i"<"n,i"++"){b"="b && "unifier"(S(X)[i],S(Y)[i])}; b`

------

13) Extension libre de structure

Le développement de ce langage marie l'informatique aux mathématiques, développant une mathématique éminemment constructive. Une présentation est une liste d'opérateurs telle que `(a,b,f"(.)",g"(.,.))`. Et si les opérateurs en question n'ont pas de définition c'est à dire si

`a"≡"a`    ou   `a"≡"ℭ(a)`
`b"≡"b`    ou   `b"≡"ℭ(b)`
`f"≡"x|->f(x)`    ou   `f"≡"ℭ(x|->f(x))`
`g "≡"x,y|->g(x,y)`    ou   `f"≡"ℭ(x,y|->g(x,y))`

Alors elle engendre un langage libre. L'ensemble des valeurs désignées par les termes engendrés constitue une structure libre.

`E="<"a,b,f"(.)",g"(.,.)>"`

L'ajout d'opérateurs libres tel que `x, h"(.)"` constitue une extension libre de la structure.

Afin de rester conforme au paradigme et ainsi de pouvoir bénéficier de toutes les interopérabilités possibles, toute construction d'élément doit passer par la construction d'une telle structure qui l'engendre.

La première difficulté que rencontre les concepteurs du langage idéal, et qui peut en décourager certains, tient dans l'inefficacité des entiers naturels construit sous forme d'une structure de Péano. Pour franchir cette difficultée il faut pousser le procédé plus loin en dotant la structure d'une base et en compilant ses méthodes. Le langage idéal se construit par lui-même en compilant ses propres composantes, tout en laissant encore indéfini le langage de bas protocole sur lequel il se construit.

Mais ne sautons pas les étapes, les entiers seront construit lorsque nous introduirons plusieurs types. Pour l'instant, il n'y a qu'un seul type et donc qu'une seul structure, et un seul ensemble sous-jacent qui regroupe les valeurs désignées par les termes. L'introduction des opérateurs variables c'est à dire l'introduction des variables d'arité d'entrée non-nulle et/ou d'arité de sortie différente de 1 va entrainant la propriété syntaxique commune à tous les termes, de pouvoir s'appliquer à n'importe qu'elle séquence d'arguments pour produire une séquence d'arguments. Le langage change alors de nature en devenant le langage alpha multi-aire monotype.

14) Récurrence

Le langage met en oeuvre un mécanisme de récurrence générale pour se construire. Le langage permet de définir les fonctions récurcives. Pour être sûre d'avoir atteint le degrès de généralité maximal, on reprendra l'exemple de la fonction d'Ackermann-Péter `A"(.,.)"` qui est un exemple simple de fonction récursive non récurcive primitive. Mais pour l'instant, on définit la structure des entiers naturels par la structure de Péano.

On pose la présentation `0,s"(.)"`. Les entiers `1,2,3` correspondent aux termes `s(0)`, `s(s(0))`, `s(s(s(0)))`. L'évaluation de `s(n)` consiste à calculer `n"+"1`. On obtient par récurrence l'ensemble des entiers naturels :

`NN=<0,s"(.)>"`

Les crochets signifient la cloture par compositions closes, c'est à dire l'ensemble de toutes les compositions possibles d'opérateurs parmi `{0,s}` avec autant d'occurences que l'on veut. Il s'agit ici d'une récurrence primitive. On peut y définir l'addition par une fonction de récurrence primitive :

`"syntaxe"("+") = "centrée"`
`"+" ≡ x,0 |-> x "||"`
         `x,s(y) |->s(x)"+" y`

Et on peut y définir la multiplication par une fonction de récurrence primitive :

`"syntaxe"("∗") = "centrée"`
`"priorité"("∗","+")`
`"∗"≡ x"∗"0 |-> 0 "||"`
           `0"∗"x |-> 0 "||"`
           `1"∗"x |-> x "||"`
           `s(x)"∗"y |->x"∗"y"+" y`

Voyons comment on peut traduire la fonction d'Ackermann définie dans `NN` comme suit :

`AAn, A(0,n) = n"+"1`
`AAm!=0, A(m,0) = A(m"-"1,1)`
`AAm!=0,AAn!=0, A(m,n) = A(m"-"1,A(m, n"-"1))`

On définit dans notre langage la fonction `A` comme suit :

`A ≡ 0,n|->s(n) "||"`
         `s(m),0 |->A(m,s(0)) "||"`
         `s(m),s(n) |->A(m,A(s(m),n))`

15) Opérateur multi-aire libre

Chaque opérateur `f` peut définir une fonction distincte selon le nombre d'arguments d'appel. Et donc lorsqu'il n'est pas définie, nous devrions avoir comme valeur par defaut :

`f ≡ |-> f() "||"`
        `x |-> f(x) "||"`
        `x,y |-> f(x,y) "||"`
        `x,y,z |-> f(x,y,z) "||"`
        ...

Cette expression est un terme de taille infinie qui ne peut donc pas s'écrire pour l'instant. On définie un nouveau type de variable qu'est la séquence variable de termes que l'on note `x"*"`. Chaque opérateur `f` à pour valeur par défaut : `x"*" |-> f(x"*")`. L'expression précédente peut donc s'écrire come suit :

`f ≡ x"*" |-> f(x"*")`

Si on redéfinit `f` par exemple comme suit : `f ≡ x,y|->f(x,y)` On supprime toutes les autres formes d'appel, et donc `f(x)` et `f(x,y,z)` échoue et retourne fail.   

La séquence variable joue un rôle important car les algorithmes d'unifications des termes avec séquences variables uniques et placés toujours tout en fin ou toujours tout en début, sont encore de complexité linéaire.

16) Grammaire et axiomatique du langage

Un langage se définit par un ensemble d'opérateurs et par une axiomatique. Et il se définit aussi par une grammaire.

Axiomatique du langage terminologique monotype :

1. Tout opérateur est un identifiant et possède une arité qui est un entier naturel.
2. Tout opérateur d'arité zéro est un terme
3. Tout opérateur d'arité `n">"0` peut s'appliquer à une séquence de `n` termes quelconques pour produire un terme.
4. Le langage est l'ensemble des termes que l'on peut construire en appliquant cette axiomatique.

Le langage terminologique monotype engendré par les 4 opérateurs suivants `a,b,f"(.)",g"(.,.)"`, est définie par la grammaire suivante notée sous forme d'une définition récurcive d'ensembles :

`E={a,b,f(E),g(E,E)}`

Comme le langage est monotype, l'ajout de variable ayant une arités d'entrée et de sortie quelconque, entraine que tout terme peut s'appliquer à une séquence de termes pour produire une sequence de termes. Cette nouvelle fonctionnalité transforme le langage terminologique monotype en un langage alpha multi-aire monotype

Axiomatique du langages alpha multi-aire monotype :

1. Tout opérateur est un identifiant.
2. Tout opérateur est un terme.
3. Tout terme peut s'appliquer à une séquence de termes quelconque pour produire un terme.
4. Le langage est l'ensemble des termes que l'on peut construire en appliquant cette axiomatique.

Appliqué aux seuls opérateurs générateurs `a,b,f,g` cela correspond à la grammaire suivante notée sous forme d'une définition récurcive d'ensembles. On note `E"*"` l'ensemble des séquences finies d'éléments de `E` :

`E={a,b,f,g,a(E"*"),b(E"*"),f(E"*"),g(E"*")}`

Le concept de séquence peut s'inclure dans celui de terme. Toute séquence peut être vue comme un terme utilisant l'opérateur binaire virgule. Délors, tout opérateur peut être considéré comme prenant qu'un seul argument et ne produisant qu'un seul argument. Cela définie le langage alpha monotype.

Axiomatique du langages alpha monotype :

1. Tout opérateur est un identifiant.
2. Il existe un opérateur appelé virgule qui n'est pas un terme.
3. Tout opérateur autre que la virgule est un terme.
4. L'opérateur virgule s'applique à deux termes quelconques pour produire un terme.
5. Tout terme peut s'appliquer à un terme quelconque pour produire un terme.
6. Le langage est l'ensemble des termes que l'on peut construire en appliquant cette axiomatique.

On note l'opérateur virgule `"𐎟"`. Considérons les opérateurs `a,b,f,g,"𐎟"` Ceux-ci engendrent le langage de grammaire suivante notée sous forme d'une définition récurcive d'ensembles :

`E={a,b,f,g,E"𐎟"E,E(E)}`

Ainsi par exemple le terme `a"𐎟"(b"𐎟"(a"𐎟"b))` désignera la séquence `a,b,a,b`. On remarque que l'opérateur virgule `"𐎟"` est le seul opérateur binaire, tous les autres opérateurs sont à la fois unaires et nullaires. Il existe un second opérateur binaire, mais encore abstrait en dehors du langage, qui est l'application d'un terme sur un terme. On le note par le symbole `"@"` et on l'appelle combine. En intégrant cet opérateur dans le langage on peut rendre nullaires tous les autres opérateurs à l'exception de la virgule. Le langage se ramène à un langage d'opérateur nullaires avec deux opérateurs binaires, la virgule et la combine.

1. Tout opérateur est un identifiant.
2. Il existe un opérateur appelé virgule qui n'est pas un terme.
3. Il existe un opérataur appelé combine qui n'est pas un terme.
4. Tout opérateur autre que la virgule et la combine est un terme.
5. L'opérateur virgule s'applique à deux termes quelconques pour produire un terme.
6. L'opérateur combine s'applique à deux termes quelconques pour produire un terme.
7. Le langage est l'ensemble des termes que l'on peut construire en appliquant cette axiomatique.

Considérons les opérateurs `a,b,f,g,"𐎟","@"` Ceux-ci engendrent le langage de grammaire suivante notée sous forme d'une définition récurcive d'ensembles :

`E={a,b,f,g,E"𐎟"E,E"@"E)}`

Reste à définir les valeurs par défaut. Un opérateur `x` non initalisé représente par défaut une variable nullaire, un élément inconnu. Mais le même nom `x` représente un opérateur pouvant s'appliquer à un terme `u` quelconque pour produire le terme `x(u)`. Alors se pose la question en quoi va être évalué ce terme ? La réponse en est trés simple. L'opérateur unaire `x` n'étant pas définie, il vaut par défaut `x ≡ |-> x "||" u|->x(u)`  et donc l'évaluation de `x` donne le terme `x` et l'évaluation de `x(u)` donne le terme `x(u)` dans le quel on a remplacé `u` par son évaluation.