Le langage d'opérateurs

 

1) Le langage d'opérateurs

Les mathématiques définissent un langage par un ensemble d'opérateurs. Cet ensemble constitue ce que l'on appel la présentation du langage. Il énumère tous les opérateurs générateurs du langage en fixant leur comportement pour chacun d'eux.

Un opérateur est avant tout un identifiant, il possède un nom sous forme d'une chaîne de caractères, et un genre "variable" ou "constant" fixant sa capacité à mémoriser un terme ou non.

Les opérateurs sont des termes. Un terme est un objet plus général qu'un opérateur, une construction faite à partir d'opérateurs, qui n'a ni nom ni genre mais qui possède tous les autres attributs d'un opérateur : un terme est susceptible d'opérer sur une liste de termes appelés opérandes et de produire un terme appelé résultat.

De plus, le terme étant implémenté dans une mémoire qui peut être partagée, le terme peut se composé de sous-termes partagés et ce partage peut être récursif. Le terme est un graphe orienté où chaque noeud correspond à un opérateur du langage et où les arrêtes partant d'un noeud sont ordonnée (c.a.d. numérotées de `1` à `n`).

Les termes ont un type qui détermine leur comportement c'est à dire qui précise, en langage de type, sur quoi ils opèrent et ce qu'ils retournent. Le type d'un terme précise les types des opérandes et le type du résultat. Ceci afin que tout terme du langage est un type déterminé et donc un comportement déterminé et ceci quelque soit les valeurs des variables qu'il contient. Cela a pour conséquence la construction d'un langage de type associé au langage d'opérateurs. Et on reporte sur le langage de type tout les choix de construction qui ne sont pas strictement nécessaires au niveau du langage d'opérateurs.

Le typage des variables limite leur pouvoir d'unification, à savoir qu'une variable d'un type donné ne peut prendre de valeur que parmi les termes de ce type.

Le langage est dit du premier ordre si nous n'utilisons qu'un seul type de variable.

Pour des raisons pratiques, on ajoute pour chaque opérateur une syntaxe. Les opérateurs unaires peuvent ainsi avoir une syntaxe gauche ou droite, et les opérateurs binaires peuvent avoir une syntaxe centrée, permettant ainsi d'omettre des parenthèses, tel que les opérateurs suivants : `¬, ', +` dans les exemples suivants : `¬x, x', x + y`. Ces opérateurs possèdent en plus, une priorité sous forme d'une valeur entière, qui détermine dans quel ordre ils doivent être évalués en cas d'ambiguïté syntaxique comme dans l'exemple `x**y+z`, l'opérateur `**` étant prioritaire par rapport à l'opérateur `+`, cette expression correspond à `(x**y)+z` et non à `x**(y+z)`.

L'arité d'un opérateur est le nombre d'arguments sur lequel il opère. Un opérateurs `f` possédant une arité `3`, sans syntaxe particulière, peut alors s'exprimer sous la forme fonctionnelle `f(x,y,z)`, sachant que les types des opérandes `x,y,z` sont déterminés par le type de `f`, et que le type du résultat est également déterminé par le type de `f`.

2) Mécanisme de reconnaissance d'un nom d'opérateur, la table de hachage

L'interprétation d'un langage d'opérateurs comprend une opération informatique fondamentale qu'est la reconnaissance d'un nom d'opérateur.

Pour que cette reconnaissance soit rapide, on construit une table de hachage. On choisi une fonction `h` de hachage qui appliqué à un nom `s`, va produire un entier `h(s)` compris entre `0` et `N-1`, et qui va permettre d'accéder à l'opérateur par un adressage indirect. Chaque opérateur est ainsi haché en un entier appelé code de hachage. La table de hachage associe à chaque code de `0` à `N-1`, la liste des opérateurs ayant ce code de hachage. La reconnaissance d'un opérateur se fait en calculant son code de hachage, et en accédant par adressage indirect à la liste des opérateurs ayant le même code de hachage, et en cherchant le nom de l'opérateur dans cette liste. Ces listes sont généralement très petites, `0, 1, 2` ou `3` opérateurs.

Étant donné un langage composé de `n` opérateurs. Sachant que le temps de calcul de la fonction de hachage `h` est du même ordre que celui nécessaire pour comparer deux noms d'opérateur, sachant que la recherche d'un nom dans une très petite liste de `k` noms se fait grosso modo en effectuant `k"/"2` comparaisons, sachant que le code de hachage se répartie aléatoirement, on peut déduire le temps de reconnaissance en fonction de la taille `N` de la table de hachage et du nombre `n` d'opérateurs générateurs du langage :

Taille `N` de la
table de hachage
Temps de
reconnaissance
`n "/" 2.5`
`2`
`n "/" 1.5`
`1.5`
`n`
`1.25`
`2n`
`1.1`
`oo`
`1`

`n` : Nombre d'opérateurs générateurs du langage
`N` : Taille de la table de hachage

La fonction de hachage transforme un nom en un entier modulo `N`. Et on choisie généralement `N=2n`.

L'interpréteur lit une phrase. C'est à dire qu'il lit une succession de caractères puis sépare chaque mot, transformant la liste de caractères en une liste de mots. Chaque mots correspond à un nom d'un opérateur générateur du langage. Les premières règles syntaxiques doivent permettrent de séparer rapidement les mots, et sont généralement la présence d'un caractère blanc, le passage d'un caractère alphanumérique à un caractère non alphanumérique et inversement.

Le langage comprend une pile d'opérateurs, une fonction de hachage et une table de hachage :

  1. Une pile `P` de `n` opérateurs.
  2. Une fonction `h` de hachage.
  3. Une table `Q` de hachage de taille `N`.

 

La pile des opérateurs `P` est une table de `n` pointeurs, où chaque pointeur pointe sur un mot qui est le nom de l'opérateur concerné. L'ordre de rangement dans la pile associe un entier de `0` à `n-1` unique pour chaque opérateur, faisant que l'opérateur est identifié par ce numéro qui est son indice de rangement dans la pile.

La fonction de hachage `h(s)``s` est la chaîne de caractère contenant le nom d'un opérateur, est une fonction simple telle que par exemple : `h(s) = ((`Integer`)s)` modulo `N`. Dans cet exemple, on convertie la chaîne de caractère `s` en un entier et on effectue un modulo N pour obtenir un entier compris entre `0` et `N-1`.

La table de hachage `Q` est une pile de pointeurs, où chaque pointeur pointe sur une liste d'opérateurs, c'est à dire une liste de numéros. Chaque numéro désignant l'opérateur placé dans la pile `P` à ce numéro. Autrement dit, ce numéro correspond l'indice de rangement de l'opérateur dans la pile `P`. Une liste d'opérateurs est donc une liste de numéros se terminant par un symbole fin de liste. Les opérateurs contenus dans une telle liste ont tous le même code de hachage, et qui correspond à l'indice de rangement dans la table de hachage.

3) A la recherche des principes fondamentaux

L'étude des fondements du langage nécessite, comme pour l'étude des fondements de l'informatique, de rechercher les opérations les plus élémentaires possibles, les plus petites, les plus décomposées possibles, afin d'ordonner à une description la plus générale possible. Y a-t-il une limite à notre recherche dichotomique ?, peut-on toujours diviser les opérations mises en oeuvres, en opérations plus simples ?, et à quel prix ?, en utilisant des outils de plus en plus lourd, qui apportent une complexité de plus en plus grande, nécessaire pour accéder à ces nouveaux objets réputés plus simples. Tout se passe comme dans la quête des physiciens à la recherche de l'infiniment petit, utilisant des énergies de plus en plus grandes pour percer le mystère de quelque noyau. Or la quasi totalité de ce que nous voyons jaillir lors de l'expérience ne provient pas du noyau, mais est constitué d'une multitude d'objets, résultat de la création chaotique causée par l'énergie utilisée nécessaire à l'observation. L'observation perturbe l'expérience ! jusqu'à créer un univers. La même problématique se pose dans l'étude d'un fondement. Ici pour le langage, notre observation mettra en oeuvre des outils mathématiques que sont les entiers, les relations d'ordres, les relations d'équivalence, les permutations, les graphes, les fonctions, les ensembles..., projetant autant d'arbitraires, de préjugés et de dissymétries, qui seront causes de la création de multiple objets hétérogènes et déroutants. Notre observation va créer du désordre, et l'art consistera à découvrir dans ce désordre les invariants fondamentaux qui se rattachent à notre sujet d'observation.

L'opérateur est une notion clef, à la fois dynamique et objectuel. L'analogie avec la physique des particules élémentaires peut être développée davantage. Devant l'impossibilité de percevoir directement ces objets, le physicien a naturellement, par le biais d'une démarche hypothético-déductive propre aux sciences exactes, construit des objets hypothétiques que sont les particules. Et il est intéressant de remarquer qu'il pousse son raisonnement au point de considérer également une interaction comme véhiculée par une autre particule. Par exemple l'atome est un objet, et plus précisément un système physique, c'est à dire un objet auquel les physiciens attribuent des variables d'état et qui respecte des invariants fondamentaux tel que la conservation de la masse-énergie, et autres quantités tel que la charge électrique, la quantité de mouvement, le moment cinétique, etc..., et son interaction électromagnétique avec un autre atome se fait par l'intermédiaire du champ électromagnétique qui, quantifié également, est réduit à l'état de photons, une autre particule élémentaire. Bien que le photon soit beaucoup plus fondamental, beaucoup plus élémentaire, que l'atome, il n'en reste pas moins que c'est le même procédé hypothético-déductif qui nous amène à considérer l'existence de toutes ces particules. Et ce sont les grecs qui à l'époque antique on définie l'atome de cette manière, et donc l'on découvert d'une certaine façon, simplement en optant pour une thèse philosophique moins risquées et moins exigeante vis à vis de la nature, que sa négation. La question posée était "Pouvons nous diviser indéfiniment la matière sans que celle-ci ne change de nature ?". Il s'avère que l'hypothèse de finitude du processus de division est beaucoup moins exigeante pour la nature que celle de l'infinitude du processus de division, l'existence de cette infinitude étant une méga-hypothèse aux conséquences impondérables.

Un objet en mathématique est quelque chose de beaucoup plus générale qu'un système physique, car l'objet n'est pas obliger de respecter une liste de principes. L'objet mathématique doit pouvoir être traité mathématiquement, c'est à dire s'inscrire dans un processus hypothético-déductif construisant des théories relatives à l'objet. A part cette périssologie, nous ne pouvons pas aller plus loin sans prendre le risque de nous mettre des oeillères. L'objet reste la première pierre, la première hypothèse d'une construction, l'hypothèse qui rend une construction possible, et ce choix ne semble pas être restreignable sans prendre le risque de brider la liberté consubstantielle des mathématiques.

4) Axiomatique du langage d'opérateurs

Nous construisons un cadre pour notre langage d'opérateurs en faisant le moins de choix arbitraires possibles. On fait des choix les plus généraux possibles afin d'en minimiser l'arbitraire, et tous les autres choix arbitraires qui peuvent être reportés sont reportés dans un autre cadre non encore construit, base du langage des types.

Nous rendons explicite ce qui est implicite, et nous définissons le langage nécessaire pour formuler problèmes et hypothèses. Puis introspectivement, différentes hypothèses incompatibles apparaissent d'elles-mêmes que nous pouvons alors explorer comme autant de voies.

L'analyse va faire émerger un certain nombre de concepts. Et ces concepts deviendront l'objet d'une axiomatique. Les constructions mathématiques concernant le squelette du langage devront respecter le principe constructif, c'est à dire devront s'apparenter à la construction d'une machine, sans pour autant que les objets désignés par le langage ne soient nécessairement soumis à cette logique. Cette méthodologie permet de dévoiler les secrets du calcul logique intuitionniste dans toute sa généralité.

Pour aborder cette axiomatisation, on commencera par traiter le cas fini. Puis on verra plus-tard comment cette axiomatique peut s'étendre au cas infini énumérable, en remplaçant les énumérations infinis par les programmes de taille fini qui les énumèrent.

La description du langage d'opérateurs se formalise en 5 axiomes :

  1. Tout opérateur est un identifiant et possède un nom unique.
  2. Tout opérateur possède un genre "constant" ou "variable"
  3. Tout opérateur est un terme.
  4. Tout terme possède un type qui définie les différentes manières dont il opère, le nombre d'opérandes, les types de ses opérandes et le type du résultat.
  5. Tout opérateur variable ne peut prendre comme valeur que des termes possédant un type identique au sien.

L'axiome n°1 affirme que le nom d'un opérateur est une chaîne finie de caractères. C'est le premier axiome car on ne peut rien énoncer si l'on n'a pas de nom. Les opérateurs en question sont les opérateurs générateurs énumérés dans la présentation du langage.

L'axiome n°2 crée deux genres "constant" ou "variable". C'est le deuxième axiome car on ne peut pas énoncer de règles non triviale autre que des relations entre quelques trermes, si l'on n'a pas la notion de variable. Cela correspond à l'implémentation de la mémoire. Une variable est une mémoire informatique. La variable permet de programmer de façon impérative. Cela nous permettra de programmer de façon impérative un énumérateur ou un processus de raisonnement. Cela correspond aussi à une variable universelle, une variable désignant l'ensemble de tous les termes de même type. Cela nous permettra d'énoncer des propriété s'appliquant à tous les termes d'un même type.

Notez que la mémoire peut être partagée, c'est à dire qu'elle peut constituer une structure de données partagées. Et ce partage peut se mordre la queue et former des cycles. On parlera de terme récurcif. Cela permet des définitions récursives. De même l'unification entre termes possédant des variables peut former des termes récurcifs, dont l'interprétation reste à faire.

On appellera simplement "variable", un opérateur variable. Et on appellera simplement "constante", un opérateur constant mais avec la condition supplémentaire que son arité soit exclusivement nulle, c'est à dire qu'il n'opère que sur une liste vide d'opérande. En effet le terme "constant" utilisé pour une fonction serait source de confusion avec la notion de fonction constante. Un opérateur, s'il n'est pas qualifié de variable, sera implicitement considéré comme constant.

Il faut interpréter l'axiome n°3 au sens fort, c'est à dire que, tous les autres axiomes qui s'appliquent aux termes, s'appliquent également aux opérateurs, de tel sorte que l'on pourra parler de type d'un opérateur, que l'on pourra faire opérer un opérateur sur une liste de termes ou d'opérateurs, appelés opérandes, pour produire un terme ou un opérateur, appelé résultat, et que le comportement de l'opérateur sera déterminé par son type. On doit pouvoir évoquer des objets plus généraux autres que ceux posés initialement d'où cet axiome. Les opérateurs du langage sont les éléments de base permettant de construire des objets plus généraux appelés termes, et l'on énumère les lois s'appliquant à ces objets plus généraux incluant les opérateurs.

La réciproque est fausse, la transformation d'un terme en un opérateur, s'il ne constitue pas déjà un opérateur, nécessite une opération de nommage afin de donner un nom pour ce nouvel opérateur et de l'ajouter à la présentation du langage.

L'axiome n°4 définie la production de terme. La nature du procédé de production n'est pas précisée. Seul le nombre d'opérandes est fini et le résultat est constitué d'un seul terme. Le terme doit pouvoir être énoncé complètement dans son fonctionnement d'où la contrainte d'un nombre fini d'opérandes et de résultats. Et le résultat n'est composé que d'un terme car s'il était composé de plusieurs termes on pourrait le simplifier en plusieurs termes plus simples ne produisant qu'un terme à la fois. L'axiomatique définie les objets les plus simples qui permettent de construire les autres objets. Néanmoins lorsqu'on s'intéressera à la complexité effective des termes, on sera amené à étudier la production de plusieurs termes résultats parallèles.

La construction et la production sont deux phases distinctes. Par exemple l'opérateur `f` appliqué aux termes `a, b` construit d'abord le terme `f(a,b)`, puis s'évalue en produisant ce que l'opérateur `f` appliqué à `a,b` est sensé produire. La phase de construction correspond à l'assemblage des termes. La phase de production correspond à l'exécution du programme `f` appliqué aux entrés `a,b`. Mais alors que se passe-t-il si l'opérateur `f` n'a pas de définition autre que son arité, s'il n'a pas de programme ? On choisi la mise en oeuvre du langage libre, on produit le terme à l'identique, le moyen le plus simple d'assurer qu'il n'y ait aucune perte d'information. Ainsi, si `f` n'a pas de programme, l'opérateur `f` appliqué à `a, b` produira le terme `f(a,b)`.

L'axiome n°4 définie la dynamique du langage en donnant implicitement un programme à chaque terme. Il est naturel de munir un opérateur d'un programme constituant sa définition dynamique. Lorsque celui-ci n'en a pas, il possède un programme par défaut qui consiste à retourner l'expression de l'appel. Mais pour un terme, il n'est pas nécessaire de lui attribuer un programme par défaut, car le terme est une expression non évaluée qui constitue déjà un programme. Le terme est un programme. Et l'exécution du programme correspond à l'évaluation du terme.

L'opérateur agit selon son programme. Et il possède un programme par défaut qui consiste à produire le terme d'appel. Selon notre paradigme constructif, le programme d'un opérateur doit également être écrit dans un langage et avoir une taille finie. Nous entre-apercevons ainsi le langage des programmes. Il est reporté dans le langage des programmes, tout ce qui concerne le calcul des productions des opérateurs. Un terme est un programme qui utilise des sous-programmes que sont les opérateurs du langage et dont les programmes sont écrits dans un autre langage de plus bas niveau. C'est ainsi que l'on décrit l'implémentation des langages d'opérateurs.

Un terme s'applique à une liste d'opérandes pour produire un autre terme qui s'applique à son tour à une autre liste d'opérandes et ainsi de suite. Le terme se décompose donc, avant toute évaluation, en une suite d'appels `T(...)(...)(...)...`, et chaque opérande est aussi un terme et se décompose pareillement en une suite d'appels. L'évaluation se fait de gauche droite et `T` est appelé le premier terme du terme. Le premier terme `T` du terme est d'abord évalué, puis les opérandes de la première liste `(...)` son évaluées de gauche à droite puis l'appel `T(...)` est résolue, puis les opérandes de la seconde liste `(...)` son évaluées de gauche à droite puis l'appel `T(...)(...)` est résolue, et ainsi de suite.

L'axiome n°4 ne précise pas si les opérateurs sont limités à ne pouvoir produire que des résultats calculables. Et donc ils ont un pouvoir de production qui n'est pas nécessairement calculable. Dans ce cas, notre approche restant constructive, tout se passe comme si des fonctions non calculables appelées oracles, nous avaient été transmises, étendant le langage des programmes ainsi que notre capacité calculatoire.

L'axiome n°4 affirme qu'un terme possède un type. Cet axiome introduit un nouveau concept, le concept de type. Le type d'un terme détermine son comportement en matière de type, c'est à dire, définie les nombres et types d'opérandes autorisée, et le type du résultat. La configuration définie doit marchée quelque soit les valeurs des variables et des opérandes du moment qu'elles sont en nombre voulu et qu'elles ont le typage voulu.

L'évaluation d'un terme ne change pas son type. Par exemple considérons deux opérateurs `a` et `b` de type `A`, considérons un opérateur `f` de type `(A,A)->(A->A)`, considérons un opérateur `g` de type `(A,A)->A`, et considérons un opérateur `f` défini par `f : (x,y) -> (z -> g(x,f(y,z)))`. On constatera que le terme `f(a,b)(a)` est de type `A`, et que son évaluation produisant `g(a,f(b,a))` est bien encore de type `A`.

L'axiome n°4 définie le champs de compétence du langage des types. Il est reporté dans le langage des types, tout ce qui concerne la détermination du comportement des termes en matière de type. Ce comportement est alors indépendant des valeurs des variables et des constantes dans le langage d'opérateurs du moment qu'elles ont le type voulu et qu'elles sont en nombre voulu, et le résultat possède nécessairement le type annoncé.

Cette séparation des compétences permet un premier calcul sur les types qui correspond en programmation, à la compilation, et est suivie par un autre calcul appelé l'exécution. Ce calcule préparatoire appelé compilation reste valable quelques soient les valeurs des variables connues par la suite. Le résultat de cette compilation peut donc être appliqué plusieurs fois pour différentes valeurs des variables, sans nécessiter de recompilation.

Un type représente l'ensemble des termes possédant ce type, c'est l'extension du type en opposition à la compréhension du type qui regroupe l'ensemble des propriétés caractérisant le type.

L'axiome n°5 affirme qu'une variable ne peut prendre comme valeur que des termes de son type.

Les axiomes n°4 et n°5 ont pour conséquence la construction d'un langage de types associé au langage d'opérateurs, dans le quel sont reportés tout les choix de construction qui ne sont pas strictement nécessaires au niveau du langage d'opérateurs. Cette séparation des compétences permet de séparer la compilation de l'exécution.

5) Les trois pans du langage

Le langage est au départ de toute chose. Comment définir un langage ? Comment définir une construction de la façon la plus générale possible ?. Nous n'avons pas de solution exacte à cette question, mais déja une réponse assez générale apparaît, qu'est le langage d'opérateurs.

Chaque terme du langage désigne un objet. Les termes sont regroupés dans l'univers du langage, tandis que les objets sont regroupés dans la structure. Cela se concrétise à l'aide d'un programme qui énumére tous les termes et donc tous les objets, et qui constitura l'énumérateur de la structure. Puis on sépare le langage de la structure, afin que le langage serve à exprimer autre chose que lui-même, en introduisant des égalités entre termes qui constitueront la théorie de la structure.

L'ensemble des termes du langage forme l'univers du langage, et il est énumérable par principe de construction. Le langage d'opérateurs constitue un premier langage dit langage de données capable de désigner tous les objets de la structure.

L'énumération de tous les termes du langage nécessite un programme, un programme de taille finie, écrit dans un langage de programmation. Le langage d'opérateurs engendre un second langage dit langage de programmation capable de programmer tous les calculs possibles. Il s'obtient en agrémentant le langage d'opérateurs de quelques opérateurs spéciaux et d'une matrice physique minimaliste permettant la construction de machine. Dans ce langage les opérateurs variables prennent un sens particulier. Ce sont des mémoires informatiques.

Puis pour rompre l'identité entre la structure et son langage, sans sortir du pouvoir d'expression du langage, on commence par introduire les clauses d'égalité et d'inégalité entre termes. Cela permet de définir les théories. Le langage d'opérateurs engendre ainsi un troisième langage dit langage de propriété capable d'écrire toutes les théories possibles. Il s'obtient en agrémentant le langage d'opérateurs de quelques opérateurs spéciaux et d'une matrice logique permettant le raisonnement. Dans ce langage, les opérateurs variables prennent un autre sens particulier. Ils désignent tous les termes qui leurs sont unifiables. Ce sont des variables universelles.

La structure regroupe ces trois pans du langage ; le langage de données pour désignier ses éléments, le langage de programmation pour programmer un énumérateur de ses éléments, et le langage de propriété pour exprimer sa théorie.

Tant qu'il n'y a aucune règle posée, que la théorie de la structure est vide, la structure coïncide au langage d'opérateurs avec un type préalablement choisie, et elle sera dite libre. Autrement dit, une structure libre est identique à un langage d'opérateurs avec un type préalablement choisi. Son ensemble sous-jacent est identique à l'univers du langage implicitement restreint à tous les temes de type voulu.

6) Le langage d'opérateurs simple

Le langage d'opérateurs simple adopte une limitation importante en n'autorisant pas les opérateurs d'arité variables. Il procède en faite à deux simplifications :

La première simplification consiste à baser le typage uniquement sur l'arité. Chaque opérateur ne peut posséder qu'une seul arité qui est un entier naturel.

Les termes d'arité nulles sont appellés éléments. Les éléments ont donc tous le même type.

La seconde simplification est que tout terme n'opère que sur une liste d'éléments. Le type se résume en un entier naturel qu'est l'arité. Apparaît alors le concept de terme clos. Un élément est un terme clos c'est à dire une composition close d'opérateurs générateurs.

Le langage d'opérateurs simple s'obtient en posant les deux axiomes supplémentaires suivants :

  1. Le type d'un terme est un entier naturel qui correspond à son arité.
  2. Les éléments sont les termes d'arité nulle.
  3. Tout terme n'opère que sur une liste d'éléments.

Le type d'un terme correspond à son arité :

Le type des éléments est noté `0`.
Le type `0->0` est noté `1`.
Le type `(0, 0)->0` est noté `2`.
Le type `(0, 0, 0)-> 0` est noté `3`.
etc....

La présentation d'un langage d'opérateurs simple est un ensemble d'opérateurs générateurs précisant pour chacun d'eux leur arité. Par exemple :

`L ={a,f"(.)",g"(.,.)"}`

L'arité des opérateurs générateurs est indiqué par le suffixe `"(.)"` qui désigne une arité `1`, ou par le suffixe `"(.,.)"` qui désigne une arité `2`, ou par une absence de suffixe qui désigne une arité zéro. Un opérateur d'arité zéro constitue un élément.

Un terme clos est une composition close d'opérateurs générateurs. Par exemple :

`g(g(a,f(a)),a)`

Les opérateurs générateurs engendrent par composition close l'univers de Herbrand noté `{a,f"(.)",g"(.,.)}°"`. C'est l'ensemble de toutes les compositions closes d'opérateurs générateurs. Par exemple :

`{a,f"(.)",g"(.,.)"}° = {a,f(a),g(a,a),g(f(a),a),g(f(a),a), g(f(a),f(a)), g(g(a,a),a),...}`

Etant donné une présentation `L`, dans la façon de parler, le « langage » désigne aussi bien `L` que `L°`. Parler de langage `L` ou de langage `L°` est synonyme et signifie indifféremment les deux à la fois. Pour être plus précis, on dira l'ensemble des « termes clos du langage » ou l' « univers du langage » pour désigner l'univers de Herbrand, l'ensemble `L°`. Et on dira l'ensemble des « opérateurs générateurs du langage » ou la « présentation du langage » pour désigner la présentation, l'ensemble `L`.

Etant donné une présentation `L`, afin que le langage serve à exprimer autre chose que lui-même, on sépare le signifié du signifiant. On appelle élément, le signifié. Et on appelle terme clos, le signifiant. Les éléments sont regroupés dans la structure, dans son ensemble sous-jacent noté `"<"L">"`. Et les termes clos sont regroupés dans le langage, dans son univers noté `L°`.

Considérons par exemple la présentation `L={a,f"(.)",g"(.,.)"}`. Par convention, les deux notations suivantes sont égales :

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

La présentation d'une structure énumère les différents opérateurs générateurs de son langage et les met entre crochets `"< >"` pour produire l'ensemble sous-jacent de la structure :

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

Au départ la structure coïncident avec le langage, chaque élément est désigné par un unique terme clos. Deux termes clos distincts désignent forcement deux éléments distincts. Il n'y pas de différence entre les termes clos et les éléments, entre l'ensemble sous-jacent de la structure et l'univers du langage, sauf d'un point de vue sémantique : l'opérateur est emboitant dans le langage alors qu'il est agissant dans la structure. Dans un cas, c'est un légo qui s'emboite avec d'autres légos. Et dans l'autre cas, c'est une application de `E^n->E``E` désigne l'ensemble sous-jacent de la structure et où `n` désigne l'arité de l'opérateur générateur en question.

Pour rompre l'identité entre la structure et son langage, sans sortir de la carrière qui représente le pouvoir d'expression du langage, on commence par introduire les égalités entre deux termes clos. Cela permet de définir les théories d'égalités de dimension zéro, dit de dimension zéro car n'utilisant aucune variable.

Tant qu'il n'y a aucune règle posée, la structure coïncide au langage d'opérateurs simple, et elle sera dite libre. Autrement dit, une structure libre est identique à un langage d'opérateurs simple, son ensemble sous-jacent est identique à l'univers de Herbrand.

Le nom des opérateurs ne change pas la structure de l'univers de Herbrand. Une traduction changeant de façon biunivoque les noms des opérateurs (nécessairement de même arité) constitue un isomorphisme c'est à dire une bijection respectant les opérations d'emboitement. Fort de cette remarque, on définie la signature d'un langage d'opérateurs simple, comme étant la suite finie d'entiers `(n_0, n_1, n_2, n_3,...)` définie comme suit : L'entier `n_0` désigne le nombre d'éléments générateurs, l'entier `n_1` désigne le nombre d'opérateurs unaires générateurs, l'entier `n_2` désigne le nombre d'opérateurs binaires générateurs, l'entier `n_3` désigne le nombre d'opérateurs générateurs d'arité `3` figurant dans la présentation du langage, et ainsi de suite. Par exemples :

Signature`{a, b} = (2)`
Signature`{a, f"(.)"} = (1,1)`
Signature`{a,b, g"(.,.)"} = (2,0,1)`
Signature`{a,b,c,f"(.)",g"(.)",h"(.,.)"} = (3,2,1)`

Cette signature caractérise la structure des univers de Herbrand à isomorphisme près.

7) Le langage d'opérateurs simple du premier ordre

Le langage est dit du premier ordre s'il n'existe qu'un seul type de variable. Et l'on choisie pour la variable, le type le plus simple, celui désignant les éléments. Le langage d'opérateurs simple du premier ordre s'obtient en ajoutant l'axiome suivant :

  1. Tout opérateur variable est d'arité nulle.

Tout opérateur variable constitue donc un élément variable. Et il n'y a pas d'autre type de variable.

Dans le langage de propriété, une variable évoque tous ce qu'il est possible d'unifier à elle, c'est à dire tous les éléments. Dans le langage de programmation, une variable évoque tous ce qu'elle peut mémoriser, c'est à dire tous les éléments. Une variable peut contenir un élément. Si la variable ne contient rien, alors elle se contient elle-même et constitue un élément. Ainsi pour le langage de données, il n'y a pas de différence entre variable et élément.

Etant donné une présentation `L` on note l'univers du langage `L°`, et on note la structure libre associée `S = "<"L">"`. Le symbole `"<>"` désigne la cloture par composition close. Dans la façon de parler, le langage `L` désigne aussi bien l'univers `L°` que la présentation `L`.

Notez que `L` est le langage de la structure `S`, et que la théorie de `S` étant vide, la structure coïncide avec l'univers de son langage, c'est à dire que `S` est une copie biunivoque de `L°`.

L'ajout de variables `x, y, z` au langage de la structure `S` correspond à une extension élémentaire notée `S[x,y,z]` ou encore par `L°[x,y,z]`. Tout se passe comme si on ajoutait au langage les éléments `x, y, z` à part qu'ils sont variables, variable signifiant ici anonyme. La même nomenclature a lieu pour l'ajout d'éléments générateurs.

Pour le langage de données, il n'y a pas de différence entre une variable et un élément générateur, sauf si des conditions sont posés sur la dite variable.

L'extension d'un élément `x` est dite intérieure, intérieure récursive, extérieure, extérieure anti-récurcive, si elle est soumise aux conditions respectives suivantes :

Extension `S[x]`
Condition
Intérieure `x in S`
Intérieure récursive `x in (S[x] - {x})`
Extérieure `x !in S`
Extérieure anti-récurcive `x !in (S[x] - {x})`

8) Les termes

Il existe une différence sémantique entre une présentation et un ensemble de générateurs. Une présentation contient la définition d'opérateurs, c'est à dire leur nom, leur type, leur genre et éventuellement leur programme. Elle s'apparente davantage à une structure de données. Parcontre un ensemble de générateurs contient des opérateurs qui vont engendrer la structure et qui ont été préalablement définis dans une présentation. La présentation contient la définition des objets, et l'ensemble contient seulement les objets.

Par commodité on adopte une seconde notation des opérateurs qui précises leurs arités et leurs genres. On rappel l'arité sous forme d'une expression fonctionnelle correspondant aux suffixes `"(.)"` ou `"(.,.)"` ou `"(.,.,.)"`... , et on rappel le genre en utilisant des caractères gras pour les opérateurs variables et des caractères non gras pour les opérateurs constantes. Ainsi la variable `x` se note également `bbx`, l'opérateur constant 2-aire `g` se note également `g"(.,.)"`, l'opérateur constant `f` unaire se note également `f"(.)"`, et l'opérateur élément constant `b` n'a pas d'autre notation que simplement `b`.

Dans le langage de donnée, il n'y a pas de différence entre les opérateurs constants et les opértateurs variables. Tout deux participent de façon identique au même processus de construction des termes.

Prenons quelques opérateurs d'arités diverses `f"(.)", g"(.,.)"`, et quelques opérateurs éléments `a,b`, que nous regroupons dans un ensemble appelé langage, et qui est en faite la présentation du langage :

`L = {a,b,f"(.)",g"(.,.)"}`

`L` constitue un ensemble d'opérateurs générateurs.

On note `L°`, l'ensemble des compositions closes. Les compositions doivent évidement respecter les types c'est à dire s'appliquer qu'à des listes d'éléments de taille égale à l'arité de l'opérateur. C'est l'ensemble des termes clos du lanage `L`  :

`L° = {a, b, f(a), f(b), g(a,a), g(a,b), g(b,a), g(b,b), f(f(a)), g(f(a),b), f(g(b,f(a)), g(g(a,b),a), ... }`

On note `L^•`, l'ensemble des compositions. Les compositions doivent évidement respecter les types c'est à dire s'appliquer qu'à des listes d'éléments de taille égale à l'arité de l'opérateur, mais n'étant pas nécessairement close, les opérandes peuvent être ommise et sont signalée dans ce cas par un point "`"."`". C'est l'ensemble des termes du langage `L` :

`L^• = {"." , a, b, f"(.)", f(a), f(b), g"(.,.)", g(.,a), g(a,.), ..., g(f(.),g(.,f(.))),...}`

Dans le langage d'opérateurs simple, les opérateurs n'agissent que sur des opérandes d'arité nulle, c'est à dire sur des termes clos pour former des termes clos. Des expressions comme `f(f)` ou `g(a,g)` qui se note explicitement par `f(f"(.)")` ou `g(a,g"(.,.)")`, ne sont pas autorisées. En effet le terme `f` est d'arité 1, le terme `g` est d'arité 2, et seul les termes d'arité zéro doivent être utilisés comme opérandes. Le langage d'opérateurs simple définie `L°`. Et on verra qu'il définit `L^•` comme étant `(Luu{"."})°`

Voici un exemple de terme du langage `L`  :

`g(g(f,.),g)`

Remarquez que dans cette expression, le symbole point "`"."`" signifie que l'opérande est manquante. On complète l'écriture en explicitant toute les opérandes manquantes. Le terme s'écrit alors :

`g(g(f,.),g"(.,.)")`

On constate alors que l'ensemble des termes du langage `L` correspond à l'ensemble des termes clos du langage `Luu{"."}`. Pour davantage percevoir ce constat, on va le démontrer de façon récurcive, comme est la construction de l'univers de Herbrand.

`L°` est l'ensemble des termes clos engendré par `L`. C'est l'ensemble des arbres finis dont les noeuds sont des opérateurs de `L` d'arité supérieur à zéro et possédant autant de fils que l'arité de l'opérateur, et dont les feuilles sont des opérateurs d'arité nulle de `L`.

`L° = {a, b, f(a), f(b), g(a,a), g(a,b), g(b,a), g(b,b), f(f(a)), g(f(a),b), f(g(b,f(a)), g(g(a,b),a), ... }`

Le processus de construction d'un tel arbre passe par des étapes intermédiaires qui sont des arbres plus généraux et plus simples à la fois, engendrés par `L uu {"."}`, où la constante "`"."`" joue un rôle dynamique particulier, le rôle du siège vide. La séquence de termes suivante trace les différentes étapes de construction du terme `g(f(a),g(b,a))` :

`"." , g"(.,.)", g(".",g"(.,.)"), g(".",g(b,".")), g(f"(.)",g(b,".")), g(f(a),g(b,".")), g(f(a),g(b,a))`

A chaque étape, une constante point "`"."`" est remplacé par un opérateur de `L` sous sa forme appliquée à des points, c'est à dire ici un terme parmi `a, b, f"(.)", g"(.,.)"`. Ce terme doit de plus respecter le type attendu par l'opérande, ce qui est le cas puisqu'ils sont tous d'arité 0. En effet, `g` est d'arité 2 mais `g(.,.)` est d'arité 0, car il s'agit ici non pas de la seconde notation de `g` rappelant sont arité, mais de l'application de `g` aux deux arguments point `"."` qui joue ici un autre rôle, le rôle d'un élément anonyme. Lorsque le terme ne contient plus aucun point, il est dit clos, et de par sa construction il est d'arité 0 et appartient à `L°`

Noter que la séquence commence par un point "`"."`" représentant un élément anonyme. Cela laisse penser que la séquence de construction vide est exclue, et qu'il n'y a donc pas de terme vide.

Cette déscription détaillée de l'ensemble des termes clos du langage `L`, dévoile ce qu'est l'ensemble des termes du langage `L`, qui correspond exactement à l'ensemble des termes clos du langage `Luu{"."}`.

Le signe `•` en exposant désigne la clôture par emboîtement fini et clos, en respectant les types, c'est à dire l'ensemble de tous les arbres atteints par le procédé de construction d'arbres clos décrit précédemment. Nous avons par définition :

`L^• = (Luu{"."})°`

Noter que la clôture peut être réitérée et que nous avons naturellement `(L^•)^•`.

Par exemple `{e,f(.)}°` est égale à `{e,f(e),f(f(e)),f(f(f(e))),...}` qui constitue l'ensemble des entiers de Péano. Et `{e,f(.)}^•` est égale à `{"." ,e,f"(.)",f(e),f(f"(.)"),f(f(e)),f(f(f"(.)")), f(f(f(e)))...}`.

9) La séparation entre le signifiant et le signifié, entre le langage et la structure.

Les univers de Herbrand constituent des langages trés généraux. Une fois posé ce mécanisme de construction, une fois définie ce genre de langage, on sépare le sens, des terme clos..., le signifié, du signifiant...., afin que le langage serve à exprimer autre chose que lui-même. On appelle élément le signifié, et terme clos le signifiant. Les éléments sont regroupés dans la structure `"<"L">"`, et les termes clos sont regroupés dans le langage `L°`.

La présentation d'une structure énumère les différents opérateurs générateurs et se note entre crochet `"<"...">"`. Ces crochets désigne la cloture par composition close, ils s'appliquent à un ensemble d'opérateurs générateurs ou soit directement à son contenant, comme par exemple :

`L   =   {a,b,f"(.)",g"(.,.)"}`
`"<"L">"   =   "<"a,b,f"(.)",g"(.,.)>"`

Au départ la structure est libre, chaque élément est désigné par un unique terme clos, et il n'y pas de différence entre les termes clos et les éléments sauf d'un point de vue sémantique : l'opérateur est emboitant dans le langage alors qu'il est agissant dans la structure.

Le langage, vu de manière plus générale, est plus vaste que `L°` car il comprend les termes non clos. De même la structure, vue de manière plus générale, est plus vaste que `"<"L">"` car elle comprend les applications que l'on peut construire par compositions :

Langage
Structure
`a`
  `|->a`
`b`
  `|->b`
`f(a)`
  `|->f(a)`
`f"(.)"`
  `x |-> f(x)`
`g"(.,.)"`
  `(x,y) |-> g(x,y)`
`g(f(.),b)`
  `x |->g(f(x),b)`

L'ensemble sous-jacent de la structure, noté `"<"L">"`, est l'ensemble des éléments désignés par les termes clos de `L°`. Et lorsqu'il n'y a aucune théorie d'égalité posée, la structure est libre et les éléments sont identifiables aux termes clos de `L°` :

`L°` = `"<"L">"`

Les deux écritures suivantes sont valables :

`"<"a, b, f"(.)", g"(.,.)>" = "<"a, b, x|->f(x), (x,y)|->g(x,y)">"`

`f"(.)"` est un terme non clos du langage. `x|->f(x)` est l'application désignée par le terme `f"(.)"`, c'est une application de `L° -> L°`.

On privilègie souvent la définition d'applications par rapport à la définition de fonctions qui peuvent ne pas être définie partout, car on souhaite opérationnaliser, c'est à dire faire que toute construction produise un résultat.

Faire agire un opérateur d'arité `n` sur un ensemble `E` signifie que l'opérateur `n`-aires devient une application de `E^n -> E`. On fait agire les opérateurs appartenant à `L` sur `L°`, et on leur donne un nom, le même nom, mais en lettre ronde :

`"<"a,b,f"(.)",g"(.,.)>" = "<"a, b, ccf : x->f(x), ccg : (x,y)->g(x,y)">"`

Il s'agit de la même structure libre mais la présentation est plus riche car elle contient deux noms supplémentaires `ccf` et `ccg` qui constituent des raccourcis. Le langage se différencie de la structure sur les opérateurs `f` et `g`. En effet `f` est différent de `ccf`. L'un se compose, l'autre s'emboite. Il en est de même pour tous les opérateurs générateurs d'arité non nulle. D'un coté les opérateurs s'emboitent et de l'autre coté ils se composent.

Lorsque on est dans le langage `L°`, l'opérateur `g` d'arité 2 est une pièce d'un jeu de construction noté `g"(.,.)"`, possédant une tête et deux réceptacles, et lorsqu'on est dans la structure `"<"L">"`, l'opérateur `ccg` est l'application `(x,y)|->g(x,y)`. Cette dernière définition signifie que lorsqu'on applique `ccg` sur un couple de termes clos `x` et `y` quelconques de `L°`, on obtient un autre terme clos de `L°` qui est `g(x,y)` dans lequel on a substitué `x` et `y` par leur valeur. L'opérateur `ccg` est donc une application de `(L°)^2 -> L°` totalement calculable et son programme correspond simplement et exactement à sa définition et à la substitution de son couple de variables d'entré.

Les clotures `L°` ou `"<"L">"` désignent respectivement la clôture de l'ensemble `L` par emboitement clos d'opérateurs, et la cloture de l'ensemble `L` par application. Dans le premier cas les opérateurs élémentaires sont considérés comme des éléments d'un jeux de construction que l'on assemble pour former des arbres clos, et dans le deuxième cas les opérateurs élémentaires d'arité non nulle sont considérés comme des applications internes à l'ensemble sous-jacent `L°`, c'est à dire qui prennent en argument des éléments de `L°` pour produire en résultat un élément de `L°`.

L'application possède un potentiel beaucoup plus grand, elle peut opérer une transformation de toute nature que le simple emboitement ne permet pas. L'opérateur agissant possède donc un potentiel que ne possède pas l'opérateur emboitant, et sa construction constitura une concrétisation homomorphe de la structure. Néanmoins ce potentiel n'est pas encore mis en oeuvre et la structure est toujours libre.

10 ) Le constructivisme

Dans notre démarche intuitionniste, les seuls ensembles dont l'existence est prouvé, sont les ensembles énumérables, présentés par un énumérateur ou une fonction énumérante. La fonction énumérante part de l'ensemble des entiers naturels qui est un langage, le langage de Péano, pour aller dans l'ensemble énuméré en question. Nous généralisons la notion de fonction énumérante en prenant comme ensemble de départ, non pas le langage de Péano, mais un autre langage arbitraire `L°`. La fonction énumérante est alors un peu plus complexe mais constitue toujours une fonction énumérante. Dans le cas où cette fonction est l'identité, l'ensembles présenté est alors `L°` lui-même, construisant tous ses éléments par emboitement d'opérateurs en des termes clos.

Si on se place dans la structure libre engendrée par `L` et que l'on note `"<"L">"`, le processus énumérant passe en revue toutes les compositions d'opérateurs et construit ainsi l'ensemble des éléments qui correspondent de façon biunivoque aux termes clos du langage.

D'un point de vue intuitionniste, la présentation d'un ensemble n'est pas autre chose que la présentation d'une structure s'énumérant.

10.1) La calculabilité

La réfutation de l'axiome du choix nous interdit de construire une fonction en faisant un nombre infini de choix arbitraires. Cela correspond à l'exigence pour un programme informatique d'être de taille finie.

Il est impossible de prouver l'existence de fonction non calculable. Mais une fonction non calculable peut nous avoir été donnée. Elle peut être apportée par un axiome supplémentaire. Et dans ce cas, cela enrichie notre langage, cela étend notre domaine des fonctions existantes, d'existence prouvable. Et si cette fonction produit quelque fois une réponse, alors cela enrichie notre langage de programmation, ce qui étend notre domaine des fonctions calculables.

10.2) Les extensions

L'extension élémentaire consiste à ajouter au langage un nouvel élément ou un nouvel opérateur. Ces éléments ou opérateurs nouveaux s'ajoutent aux opérateurs générateurs déjà définies, et vont avoir une influence sur ceux déjà définis en agrandissant leur domaine de définition. Néanmoins rien ne prouve qu'ils soient différents d'éléments ou d'opérateurs déjà existant.

10.3) La concrétisation

Afin que le langage exprime autre chose que lui-même, on peut ajouter de l'information supplémentaire au signifié. On effectue pour cela une transformation des éléments de la structure, mais selon notre approche intuitionniste en se restreingnant qu'à des procédés calculables. Et on appelle cette transformation une évaluation. Tout les éléments de la structure sont ainsi évalués pour produire une structure image. La structure image est alors plus riche et peut posséder des égalités cachées, une théorie d'égalité implicites à la concrétisation. On dira que l'on concrétise la structure. Le langage reste libre, mais la structure peut ne plus l'être.

10.4) Le quotientage

Une autre façon de changer le sens des termes clos du langage est de rompre l'unicité qui les lie aux éléments, en considérant égaux certains éléments entre eux, c'est à dire en considérant équivalent certains termes clos entre eux à l'aide de règle d'égalité, faisant qu'ils désignent le même élément. Le quotientage consiste à choisir des règles d'égalités, formant une théorie d'égalité, et à construire la structure quotient, la structure des classes d'équivalence. On réduit ainsi la structure libre par des règles d'égalités. Le langage reste libre, et la structure ne l'est plus.

Le quotientage peut s'appliquer à une structure non libre pour former une structure image encore moins libre. L'application qui associe à chaque élément sa classe d'équivalence dans le cadre de ce quotientage par des règles d'égalité, est appellée concrétisation ou évaluation implicite ou transformation implicite.

Concrétisation et quotientage sont des procédés duaux de construction de structure à partir d'une structure quelconque. L'un définie des transformations et fait apparaitre des règles d'égalités implicites, l'autre définie des régles d'égalités, et fait apparaitre des transformations implicites.

11) L'approche intuitive opérationnelle

Nous recherchons, plus une pratique guidée par un sens intuitif que des preuves que nous laisserons à la charge du contradicteur. C'est pourquoi on avance par tatonnement en construisant des procédés et en les essayant comme un jeu pour appréhender les bases de leur maniement et finalement leur sens intuitif au travers leurs capacités opérationnelles. Tout est porté sur l'opération, le processus, car tout n'est que processus. En effet pourquoi créer une chose qui ne serait pas en mouvement, en évolution ?..., et ce processus doit être intélligible, car seul ce qui est intelligible intéresse les sciences. Et ce qui est intelligible est appréhendable par un procédé mécanique où tout mystère y a été chassé. Certe le procédé mécanique ne dit pas tout, n'appréhende pas tout, mais il est lui-même une chose en mouvement que nous pouvons fair évoluer, et son devenir incertain au grès des découvertes des pères ou de lui-même, lui rend son statut d'entité libre.

Alors, vous me direz que cela manque un peu de coeur et un peu de chaire, tout ce monde de machines.... Nous sommes de coeur et de chère, produit de la nature et de notre culture, de 4 milliards d'annés d'évolution naturelle, et de 4000 ans d'histoire. De même que l'on ne peut faire de mathématique en faisant table rase du passé, s'en que celle-ci perde de la pertinence et sa faculté à libérer la pensée, nous ne pourrons créer de raison émancipatrice sans donner en héritage, ce précieux acquit de la nature et de la culture.

Notre approche intuitive opérationelle est lente et descriptive. C'est une succession de construction décrites par de nombreux exemples, dont la simple lecture permet au lecteur d'acquerir ce sens intuitif. L'exemple est dynamique et vivant. Il possède un pouvoir pédagogique, de transmission du sens inuitif beaucoup plus fort que ne peut faire la définition froide et inerte, d'un synoptique trop rigide. L'exemple est applicable simplement en substituant les paramètres par ceux souhaités, or que la définition, pour être utilisée, nécéssite une gymnastique de l'esprit plus complexe, de choisire des d'arguments appartenant à des ensembles de départ et à des domaines de définition limitatifs, qu'ils faut préalablement définir, apréhender, circonscrire....

Le sens intuitif opérationnel veut s'abstraire des contraintes liées aux domaines de définition et aux ensembles de départ et d'arrivé qui sont trop limitatifs. Cela aboutie à utiliser une notion plus générale que la fonction, qu'est la transformation, une fonction basée sur le seul procédé calculable qu'elle met en oeuvre en faisant abstraction le plus possible des objets sur lesquels elle porte. Pour décrire ces transformlations, il nous faut développer un langage, et c'est ce à quoi nous nous attelons. Les structures se construisent comme des objects, par transformation, et nous avons mis en évidence trois types de transformation que sont ; l'extension, la concrétisation, et le quotientage.

Langage d'opérateurs (suite)

Dominique Mabboux-Stromberg (juin 2017)