Le langage d'opérateurs

 

1) Introduction

Les mathématiques définissent un langage par un ensemble fini d'opérateurs. Et qu'est-ce qu'un opérateur ?

Un opérateur est avant tout un identifiant, quelque chose que l'on peut identifier et que l'on représente par un caractère. Puis l'opérateur a un aspect dynamique intrinsèque. C'est quelque chose qui opère sur le langage, et apriori, il opère de façon totalement libre sur le langage, c'est à dire qu'il s'applique à toute liste finie non vide de termes du langage appelés opérandes pour produire un terme du langage appelé résultat. Et ce terme résultat n'est que l'expression de l'opérateur appliqué à sa liste d'opérandes. On parlera de l'emboitement d'un opérateur avec sa liste d'opérandes.

A l'origine, ces opérateurs sont inclus dans l'univers du langage, c'est à dire qu'ils constituent des termes du langage. Chaque terme du langage est composé d'opérateurs emboités. C'est d'ailleurs pourquoi le langage est appelé « langage d'opérateurs ». Et il est parfois qualifié d'arité variable car les opérateurs peuvent s'appliquer à une liste d'opérandes de taille quelconque finie non nulle.

L'opérateur du langage est un atome c'est à dire qu'il ne se subdivise pas, et c'est un identifiant, il possède un nom sous forme d'un caractère.

Un terme est un objet plus général qu'un opérateur, une construction finie faite à partir d'opérateurs. L'ensemble des termes constitue l'univers du langage, tandis que l'ensemble des opérateurs constitue la présentation du langage. Ces opérateurs sont aussi appellés plus précisement les opérateurs générateurs du langage car ils engendrent à eux seuls tous les termes du langage, et sont de plus eux mêmes des termes du langage.

Comme il n'y a pas de différence entre un opérateur et un terme, autre que l'insubdivision, le terme se comporte comme un opérateur et opère donc également sur le langage de façon totalement libre, c'est à dire qu'il s'applique à toute liste finie non vide de termes du langage appelés opérandes pour produire un terme du langage appelé résultat. Et ce terme résultat n'est que l'expression du terme initial appliqué à sa liste d'opérandes. On parlera de l'emboitement d'un terme avec sa liste d'opérandes.

De ce qui précède, le langage est constructible, c'est à dire qu'il existe un programme de taille finie appelé énumérateur du langage qui énumére tous les termes du langage. La présentation du langage, notée `L` engendre par emboitement l'univers du langage `L^•`. C'est la clôture de `L` par emboitement noté `L^•`, où le symbole `•` en exposant est l'opération de clôture par emboitement.

Dans la façon de parler, le « langage » désigne aussi bien la présentation que l'univers. La même lettre `L` peut parfois être choisi pour désigner l'un et l'autre en laissant au contexte le soin de levé l'ambiguité. Pour être précis, on dira l'ensemble des « termes du langage » qui est un synonyme de l' « univers du langage ». Et on dira « l'ensemble des opérateurs générateurs du langage » qui est un synonyme de la « présentation du langage ».

S'il n'y a pas d'opérateur générateur, le langage engendré est vide. Considérons tout d'abord le cas où il y a un unique opérateur générateur. Alors celui-ci va non seulement engendrer un langage d'opérateurs mais on verra que ce langage contiendra tous les langages d'opérateurs possibles. Dans la littérature contemporaine cet opérateur unique porte un nom. Il s'appelle alpha, `alpha`. Il est d'arité variable. C'est à dire qu'il peut s'appliquer à toute liste finie non vide de termes du langage alpha, `{alpha}^•`. Et il fait partie de l'univers du langage alpha, `alpha"∈" {alpha}^•`.

Regardons comment se construit le langage alpha. Sa présentation est `{alpha}`. À partir du terme `alpha` on peut construire le terme `alpha(alpha)` puis le terme `alpha(alpha,alpha)` ou le terme `alpha(alpha(alpha))` ou bien encore le terme `alpha(alpha)(alpha)`....

2) 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 multiples 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.

3) Axiomatique du langage d'opérateurs

Nous construisons un cadre pour notre langage d'opérateurs en faisant le moins de choix arbitraires possibles. Ou plus exactement, on fait des choix les plus généraux possibles afin d'en minimiser l'arbitraire.

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 traitera à part le cas plus simple de la présentation singleton, constitué du seul opérateur `alpha`. On étudira d'abord les présentations finis c'est à dire contenant un nombre fini d'opérateurs générateurs. Puis on verra plus-tard comment étendre l'axiomatique au cas des présentations infinis énumérables, en remplaçant les énumérations infinis par les programmes de taille fini qui les énumèrent.

Le procédé de construction de notre langage d'opérateurs est l'emboitement totalement libre. La description de ce langage d'opérateurs se formalise en 4 axiomes :

  1. Tout opérateur est un identifiant et possède un nom unique sous forme d'un caractère.
  2. Tout opérateur est un terme.
  3. Tout terme peut s'appliquer à toute liste finie non vide de termes appelés opérandes pour produire un terme appelé résultat.
  4. L'application d'un terme à une listes finie non vide d'opérandes produit un terme résultat qui est l'emboitement du terme initiale appliqué à la liste de ses opérandes.

L'axiome n°1 affirme que le nom d'un opérateur est un caractère. 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 permet au langage de se déployer avec un niveau de généralité plus grand. 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 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°3 définie les possibilités de production des termes, c'est à dire définie la composition totalement libre. Le nombre d'opérandes est fini et non vide, 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 la question se reposera lorsqu'on s'intéressera à la complexité de calcul des termes.).

On remarquera que l'application d'un terme à une liste vide n'est pas autorisée. Cette possibilité n'est pas retenue car le langage n'est pas un langage de listes. Intuitivement une liste d'opérandes ne doit pas être vide. Mais il est possible d'ajouter cette possibilité qui n'apporte néanmoins pas grand chose. On modifie l'axiome n°3 en : Tout terme peut s'appliquer à toute liste finie de termes appelés opérandes pour produire un terme appelé résultat. Le principe d'un terme est d'apporter une quantité d'information suffisante pour désigner un élément. Si on l'applique sur aucun opérande, on ne lui apporte aucune autre information et le résultat ne peut être que terme initiale lui-même. C'est pourquoi, par soucis de simplification, on rend aussitôt caduc cette nouvelle liberté en posant l'axiome d'identité suivant, axiome n°3bis : Tout terme appliqué à une liste vide retourne lui-même comme terme résultat.

L'axiome n°4 affirme que le résultat de la composition est l'expression telle qu'elle de la composition. Ainsi est-on assuré qu'il n'y a aucune perte d'information. Par exemple le terme `x` appliqué aux termes `y, z` produit le terme résultat `x(y,z)`. L'axiome n°4 affirme que la composition correspond à l'emboitement et qu'aucune simplification n'est opérée après. L'axiome n°4 affirme ainsi que le langage n'exprime que lui-même, ou que les termes du langage désigne les éléments d'une structure libre selon son langage, ou autrement dit, que deux termes distincts désignent nécessairement deux éléments distincts.

4) La séparation entre le langage et la structure

Considérons le langage de présentation suivante :

`{f,g,h}`

Ce langage est engendré par trois opérateurs `f,g,h`, mais il peut y en avoir un nombre quelconque fini non nul, le raisonnement présenté s'appliquera pareillement.

Afin que le langage exprime autre chose que lui-même. On sépare le signifié, du signifiant. On sépare l'élément désigné, du terme le désignant. Les uns sont regroupés dans la structure, dans son ensemble sous-jacent notée `"<"f,g,h">"` et qui représente la cloture par composition. Les autres sont regroupés dans le langage, dans son univers `{f,g,h}^•` qui représente la cloture par emboitement. Tandis que la présentation du langage `{f,g,h}` regroupe les seuls opérateurs générateurs du langage.

Au départ, la structure est libre. Deux termes distincts désignent nécessairement deux éléments distincts. Il n'est considéré aucune égalité entre termes. Autrement dit la théorie d'égalité de la structure est vide. Et donc la structure est identique à son langage. Son ensemble sous-jacent est identifée à l'univers de son langage.

Puis la structure s'agrémentera d'une théorie d'égalités et se distinguera alors de son langage.

L'ensemble des éléments de la structure est l'ensemble des classes d'équivalences de la relation d'égalité définie par la théorie `T` sur l'ensemble des termes du langage. L'égalité initiale entre deux termes `x,y` sera notée par `x-=y` tandis que l'égalité nouvellement définie par la théorie `T` entre deux termes ou deux éléments `x,y` sera notée `x=y`.

Souvent on désignera la présentation du langage par `L` et l'ensemble sous-jacent de la structure par `E` :

`L = {f,g,h}`
`L^• = {f,g,h}^•`
`E = "<"f,g,h">"`

Le symbole `•` en exposant désigne la clôture par emboitement, tandis que les crochets `"<" ">"` désigne la clôture par composition, une distinction purement sémantique tant qu'il n'y a pas de théorie d'égalité. L'égalité entre termes se note avec le symbole `-=` tandis que l'égalité entre éléments se note avec le symbole `=`.

Pour simplifier les notations, on considère égale `"<"f,g,h">" = "<"{f,g,h}">" = "<"L">"`, de telle sorte qu'un ensemble d'opérateurs `L` placé entre crochets` "< >"` est interprété en le remplacant par son contenu. Néanmoins si `L` s'avère être aussi un opérateur, alors il faudra lever l'ambiguité en adoptant une notation explicite, en utilisant le symbole `"@"`, pour désigner le contenu de l'ensemble. Ainsi nous avons `"<"f,g,h">"="<@"{f,g,h}">"="<@"L">"`.

Étant donné un ensemble `K` de termes du langage, `K sube Omega`. Celui-ci peut être interprété également comme un ensemble d'éléments, les éléments désignés par les termes en questions, `K sube E`. La même lettre étant utilisée, il est laissé au contexte le soin de lever l'ambiguité, à savoir si on parle de l'ensemble des termes ou si on parle de l'ensemble des termes à égalité près, c'est à dire de l'ensemble d'éléments.

Par contre, on convient qu'à partir d'un ensemble quelconque d'éléments, `K`, on autorisera l'évocation d'un ensemble de termes les désignant, que si on précise un procédé pour les obtenir à partir de l'ensemble des éléments, `K`.

5) La structure

Une structure `S` comprend un langage `L` et une théorie d'égalité `T`. La théorie d'égalité `T` définie une relation d'équivalence sur l'ensemble des termes du langages `L`. Deux termes `x,y` sont équivalents dans la structure, ce qui se note par `x"="y`, si et seulement si `T|--x"="y`. La subdivision de l'ensemble des termes en classes d'équivalences qui ne sont pas forcement d'égale cardinalité représente une division de l'ensemble des termes du langage `L` par la relation d'équivalence définie par `T`. C'est pourquoi la structure `S` se note sous forme d'un quotient, le quotient d'un langage par une théorie d'égalité :

`S = L^• "/" T`

Afin d'avoir une définition récursive qui peut se répéter comme on le verra et qui n'introduit que des éléments et aucun terme, on part de la structure libre selon le langage `L` qui se note `"<"L">"`. Nous pouvons définir la structure `S` à partir de cette structure libre :

`S = <L> "/" T`

---- 19 juillet 2017 ----

 

 

 

 

 

 

 

 

Puis il s'avère habituel, sans doute plus par paresse que pour d'autres raisons, de noter la clôture par composition d'un ensemble `L` par l'expression `"<"L">"` au lieu d'énumérer entre les crochets les éléments de `L`. Il faudra donc lever l'ambiguité si par une malchance extraordinaire `L` constituait à la fois un opérateur et un ensemble d'opérateurs.

`E = "<"L">"`

 

Implicitement, si on se situe dans la structure S, sa théorie d'égalité est supposé vrai. En ce sens, la définition d'une structure ouvre un contexte dans lequel la théorie d'égalité de la structure est implicite.

 

 

Il est habituel de nommer la structure par la même lettre que son ensemble sous-jacent.

`S "="<"L">" "/" T`

Et comme on confond aussi sous le nom de langage, la présentation et l'univers.Il arrive que l'on note

`S = L "/" T`

 

 

Deux termes x,y sont égaux si et seulement si T|-x=y. Et nous avons aussi deux éléments x,y sont égaux si et seulement si T|-x=y. Et donc cette définition se note habituellement de façon récurcive en n'évoquant à chaque fois que des éléments :

`S_0={f,g,h}^• = "<"f,g,h">"` La théorie d'égalité est vide

`S_1=S_0 "/" T_1` après cette définition la théorie d'égalité de S1 comprend T1

`S_2=S_1 "/" T_2` après cette définition la théorie d'égalité de S2 comprend T1 et T2

`"<"f,g,h">"={f,g,h}^•`

sachant que dans le premier membre de l'égalité, la théorie `T` est sous-entendue.

 

 

 

 

 

---- 16 juillet 2017 ----

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 le langage, tandis que les objets sont regroupés dans la structure. Concrètement, il existe 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 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 de taille finie écrit dans un langage de programmation. Le langage d'opérateurs engendre ainsi 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 d'implémenter la mémoire, permettant la construction de machine. Dans ce langage les opérateurs variables prennent un sens particulier. Ce sont des mémoires informatiques capable de mémoriser tout terme de type compatible.

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 logique. 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 que sont ; le langage de données pour désigner 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.

 

 

 

 

 

 

 

 

5) Logique du premier ordre

Malgrès l'arité variable, il est possible de construire une logique du premier ordre

 

 

 

 

5) second ordre

Le langage d'opérateurs a pour object de désigner des élément. Pour introduire une logique du second ordre, on définie un second langage qui a pour object de désigner des ensembles d'éléments. Et ces ensembles d'éléments sont appelés des types.

le type représente l'ensemble des termes du langage satisfaisant les propriétés décrites par le type, c'est l'extension du type en opposition à la compréhension du type qui regroupe dans une théorie les propriétés caractérisant le type c'est à dire décrivant un ensemble de comportements possibles et de propriétés satisfaites par tous les termes ayant ce type, au quel on ajoute l'exigence d'appartenir à l'univers du langage et la propriété d'être contradictoire si aucun terme ne satisfait ce type. Ces deux contraites supplémentaires scellent la véritable symétrie qui existe entre l'extension et la compréhension. C'est la définition antique des ensembles, une définition constructive limitée et basée sur un langage d'opérateurs qui en constitue sa fondation logique.

 

on donne à chaque terme un type, faisant qu'un type représente un ensemble de termes. Et on construit un second langage, appellé langage de type, servant à les définir.

D'autre part les opérateurs possèdes dans l'usage ocourant un type qui détermine leur comportement c'est à dire qui précise, en langage de type, sur quoi ils s'appliquent et ce qu'ils retournent. Le type d'un opérateur précise les compositions possibles qu'il peut faire en fonction uniquement des types des opérandes, et précise le type du résultat pour chaque cas. Le résultat est un terme, et donc le typage des opérateurs a pour consésquence un typage des termes. Ce typage des termes est formalisé à travers un langage des types

Notez que le langage de type, ou langage des types, n'est pas un langage composé de types mais est le langage qui définie les types, c'est pourquoi il n'y a pas de "s" à "langage de type". Ce second langage qui est définie à partir d'un premier langage d'opérateurs, est lui-même un langage d'opérateurs que nous allons développer.

Le type représente l'ensemble des termes du langage satisfaisant les propriétés décrites par le type, c'est l'extension du type en opposition à la compréhension du type qui regroupe dans une théorie les propriétés caractérisant le type c'est à dire décrivant un ensemble de comportements possibles et de propriétés satisfaites par tous les termes ayant ce type, au quel on ajoute l'exigence d'appartenir à l'univers du langage et la propriété d'être contradictoire si aucun terme ne satisfait ce type. Ces deux contraites supplémentaires scellent la véritable symétrie qui existe entre l'extension et la compréhension. C'est la définition antique des ensembles, une définition constructive limitée et basée sur un langage d'opérateurs qui en constitue sa fondation logique.

Un type `A` représente soit son extension c'est à dire l'ensembles des termes du langage ayant ce type, ou soit sa compréhension c'est à dire la théorie déccrivant son comportement ou les caractéristiques communes à tous les termes de ce type, à laquelle on ajoute l'exigenxe d'être un terme du langage et la propriété d'être contradictoire si aucun terme ne satisfait ce type. Et on laisse le soin au contexte de lever l'ambiguité pour savoir si c'est l'extension ou la compréhension dont il est question.

Chaque propriété sur les extensions a une version duale équivalente sur les compréhensions :

On dit qu'un type `A` respecte un type `B` si et seulement si, `A` est inclus dans `B` ce qui se note par `A sube B`. Et par symétrie, il y a la définition duale équivalente : Un type `A` respecte un type `B` si et seulement si, `A` implique `B` ce que l'on note par `A=>B`.

On dit qu'un type `A` spécialise un type `B` si et seulement si, en terme d'extension, `A` est inclus strictement dans `B` ce qui se note par `A sub B`, ou bien par `A sube B "et" B !sube A`. Et par symétrie, il y a la définition duale équivalente : Un type `A` spécialise un type `B` si et seulement si, `A` implique `B` et `B` n'implique pas `A` ce que l'on note par `A=>B " et " B!=>A`. On dira que `A` implique strictement `B` ce que l'on notera par `A=>>B`.

Deux types sont dits incompatibles si et seulement si leur extension ont une intersection nulle. Et par symétrie, il y a la définition duale équivalente : Deux types sont incompatibles si et seulement si leur conjonction est contradictoire.

(Ainsi lorsque l'on introduira les variables, on verra que le typage des variables va limiter leur pouvoir d'unification, à savoir qu'une variable d'un type donné ne pourra pas prendre comme valeur un terme dont le type lui est incompatible. L'unification d'une variable de type `A` et d'une variable de type `B` produira une variable de type d'extension `AnnB`, et un type dont l'extension est vide traduit l'échec de l'unification.)

On ne donne pas de cadre limitatif à la définition d'un type. On exige seulement une condition : Le type d'un emboitement d'un terme avec une liste d'opérandes, doit respecter une règle d'indépendance vis à vis des valeurs des opérandes, sachant que ces valeurs doivent évidement respecter le type des opérandes en question décrit par le type du terme en question : Ces valeurs ne peuvent que laisser inchanger ou restreindre les possibilités de comportement du terme résultat par rapport au type anoncé du résultat. Autrement dit, le type d'un terme résultat ne peut qu'être invariant ou se spécialiser lorsque le type des opérandes dont il est issu se spécialisent.

Tout terme du langage possède un type qui détermine son comportement, c'est à dire la façon dont il peut s'appliquer à une liste d'opérandes et le type du résultat pour chaque cas, et ceci, à spécialisation près c'est à dire que quelque soit les valeurs des opérandes de la liste sur laquelle il s'applique, le terme résultat appartient toujours au type annoncé du résultat. 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.

Cette séparation des compétences entre le langage des types et le langage des opérateurs, 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 opérandes connues par la suite. Le résultat de cette compilation peut donc être appliqué plusieurs fois pour différentes valeurs des opérandes, sans nécessiter de recompilation. Ainsi cette séparation des compétences permet de séparer la compilation de l'exécution.

 

 

 

 

 

4) Le langage alpha

 

 

 

 

 

 

 

 

Le langage `{f,g,h}` se construit à partir du langage `{alpha}` simplement en prenant 3 termes distincts quelconques `a, b, c` avec `a!=b, a!=c, b!=c`, et en posant :

`f "=" alpha(a),   g "=" alpha(b),   h "=" alpha(c)`

Le langage étant libre et, comme il n'existe pas de construction possible par emboitement pour calculer `alpha(a)` à partir de `alpha(b)` et réciproquement, ces deux racines forment des langages alpha qui ne se marchent pas sur les pieds et qui peuvent donc être unifiés à tous les langages d'opérateurs possibles, et de même pour la troisième racine `alpha(c)`.

 

 

Les éléments de la structure sont des applications de

Les éléments de la structure sont des applications de `E"*"->E` `"*"` est le symbole de Kleene. `E"*"` désigne l'ensemble des suites finies d'éléments de `"E"`.

L'opération de produit `×` possède une priorité syntaxique moins élevées que l'opération d'application `->`. L'opération de produit construit l'ensemble les couples d'éléments, `E×E`, ou consruit l'ensemble des triplets d'éléments, `E×E×E`, ou encore construit l'ensemble des listes finies d'éléments contenant au moins `3` éléments, `E×E×E×E"*"`. Déjà à ce niveau de précision, on voit apparaitre un embrillons de langage de programmation.

Cette nature applicative, `E×E"*"->E`, constitue le type applicatif des éléments de la structure auquel il faut ajouter par polymorphisme le fait qu'ils constituent aussi des éléments de la structure. Cela se note par l'opération d'ajout polymorphique `+`. Le type des éléments de la structure se note donc par :

`E + (E×E"*"->E)` erreur !

->E + E->E + ExE->E + ExExE->E

Mais une simplification est faite en interprétant correctement le type `->E`. Ce type désigne les applications qui ne prennent aucun opérande et qui retourne un élément de la structure. Soit `f` et `g` deux telles applications. Par principe `f=g` si et seulement si `f()=g()`, car en effet ces applications ne se caractérisent que par la seul valeur qu'elle retourne. De telle sorte qu'il existe une bijection entre `E` est l'ensemble des applications `->E`. Et donc il et possible d'identifier les éléments de `E` avec les application de `->E` qui les produisent. Se faisant, le type des éléments de la structure peut être désigné aussi bien par `->E` que par `E` si on en adopte l'identification. Ce principe d'identification se ramène à l'axiome d'identité suivant : `AAx in E,  x()"="x`, ou dit littéralement : tout élément est une application qui appliquée à une liste vide d'argument retourne l'élément lui-même.

Délors, le type `->E` définis bien le type des éléments de la structure qui n'opèrent pas. Délors, le type des éléments de la structure se note simplement par :

`E"*"->E`

 

Afin d'atteindre explicitement ce niveau de précision, celle-ci doit être mentionnée lorsqu'on présente le langage. C'est pourquoi la présentation d'un langage énumèrera la liste des opérateurs générateurs en mettant en indice leur type avec ce niveau de détaille. La présentation du langage sera donc :

`{ f_("<"f,g,h">*→<"f,g,h">"), g_("<"f,g,h">*→<"f,g,h">"), h_("<"f,g,h">*→<"f,g,h">")}`

ou bien de façon explicite sous forme d'un quotient d'une présentation par une théorie :

`{f,g,h} "/" {`
       `f"∈"("<"f,g,h">*→<"f,g,h">"),`
       `g"∈"("<"f,g,h">*→<"f,g,h">"),`
       `h"∈"("<"f,g,h">*→<"f,g,h">")`
`}`

La présentation du langage alpha sera :

`{alpha_("<"alpha">*→<"alpha">")}`

ou bien de façon explicite sous forme d'un quotient d'une présentation par une théorie :

`{alpha} "/" {alpha"∈<"alpha">*→<"alpha">"}`

 

 

La description du comportement des termes et opérateurs se fait par l'intermédiaire d'un langage, appelé langage des types que nous allons construire. Mais pour faire cela tout en suivant notre processus de construction, nous allons d'abord construire d'autres langages d'opérateurs à partir du seul et unique langage alpha.

 

5) Typage des opérateurs

A partir du langage alpha, comment créer des opérateurs aux comportements différents, plus restreints ? Cela peut être simulé en ne faisant qu' ajouter une théorie d'égalité. Mais pour écrire cette théorie d'égalité, il nous faut developper un méta langage. Il nous faut pouvoir utiliser des variables notées `x,y,z,...` pouvant représenter n'importe quel élément de la structure, ainsi que des listes finies variables de variables notées `u"*",v"*",w"*",...` pouvant représenter n'importe quel liste finie d'éléments de la structure. Et on utilise le produit pour construire des n-uplets de variables qui seviront de liste d'opérandes. Et on utilise la concaténation terminale c'est à dire la possibilité de concaténer un n-uplet de variables avec une liste finie variable de variables qui seviront également de liste d'opérandes.

Etant donné un opérateur `f`. L'application de `f` sur aucun opérande redonne le terme initial selon l'axiome d'identié `f()"="f`. L'application de `f` à la variable `x` se note `f(x)`. L'application de `f` aux variables `x` et `y` dans cet ordre se note `f(x,y)`. L'application de `f` à la liste variable de variables `u"*"` se note `f(u"*")`. L'application de `f` à la liste composée d'une première variable `x` et d'une liste variable de variables `u"*"` se note `f(x,u"*")`. Etc.. Une liste variable de variables de taille au moins égale par exemple à 3 se note `(x,y,z,u"*")`. Ainsi, on voit apparaître avec ce méta-langage un embryon de langage de programmation.

On définie un élément qui possède comme arité seulement `0` et `n`, en le rendant égal à lui-même à chaque fois qu'il se compose avec un nombre d'opérandes autre que `n`. Ainsi, chaque type simple correspond à une théorie d'égalité :

Type applicatif simple
Théorie d'égalité
`E`
`f(x,u"*") "=" f`
`E->E`
`f(x,y,u"*") "=" f`
`E×E->E`
`f(x)"="f`
`f(x,y,z,u"*") "=" f`
`E×E×E->E`
`f(x)"="f`
`f(x,y)"="f`
`f(x,y,z,t,u"*") "=" f`

Les variables `x,y,z,t,u"*"` étant quantifiées universellement. Autrement dit :

`AAx"∈"E,AAy"∈"E,AAz"∈"E,AAt"∈"E,AAu"*∈"E"*"`

---- 16 juillet 2017 ----

 

 

5) L'arité d'un opérateur

L'arité d'un opérateur est le nombre d'opérandes sur lesquelles il peut s'appliquer. Un opérateur peut posséder plusieurs arités, ou plus exactement, dans ce cas, son arité est un ensemble d'entiers naturels. Par exemple, un opérateur qui s'applique sur un nombre paire d'arguments et qui constitue lui-même un terme du langage, possède comme arité `{0,2,4,6,8,10,...}`. Autre exemple, l'opérateur alpha possède comme arité, l'ensemble des entiers naturels `NN`.

Un opérateur `f` possède une arité nulle si et seulement si l'opérateur constitue lui-même un terme du langage. L'application de `f` sur aucun opérande se doit de produire `f`, car `f` est avant tout un identifiant. Autrement dit, nous posons par principe que pour tout opérateur générateur `f` nous ayons `f()=f`.

L'opérateur `f` est d'arité nulle si et seulement si il appartient au type `->E` et on dira que `f = |->f`.

Il est possible de concevoir des opérateurs qui ne possèdent pas d'arité nulle et donc qui ne sont pas eux-même des termes du langage et qui pourtant participe à sa construction.

L'arité ne décrit qu'une partie du comportemnt d'un terme ou d'un opérateur. C'est le type qui décrira complètement le comportement selon un langage de description du comportement.

Y-a-t-il possibilité de scinder chaque terme en un ensemble de termes distincts ayant chacun une seul arité ? Non, car dans le mécanisme d'emboitement choisi, le terme résultat est par principe unique et ne peut donc être scindé.

6) Un langage d'arité variable se ramène à un langage d'arité fixe possèdant deux opérateurs binaires.

Par le même procédé qui transforme un arbre quelconque en un arbre binaire, on peut redéfinir tout langage d'opérateurs d'arité variable en langage d'opérateurs d'arité fixe. Prenons par exemple le langage de présentation suivante :

`{f _(E uu E×E*"→"E), g_(E uu E×E*"→"E), h_(E uu E×E*"→"E)}`

ou bien de façon explicite :

`{f,g,h} "/" {f "∈" E^"+""→"E, g "∈" E^"+""→"E, h "∈" E^"+""→"E}`

Ce langage d'opérateurs d'arité variable peut être remplacé avantageusement par une structure basée sur un langage d'arité fixe comme suit : On définie l'opérateur binaire `**`, noté par absence de symbole, qui applique un terme sur un autre, et l'opérateur binaire `⊕` qui ajoute une opérande dans un terme appliqué à une liste d'opérandes. Ainsi nous avons par exemple :

`fg= f(g)`
`f(g)h = f(g)(h)`
`f(g)"⊕"h = f(g,h)`

On remarque que l'opération `f"⊕"g` n'est pas définie, et on la définie égale à `f(g)` pour que cela corresponde à l'ajout d'une opérande à la liste vide d'opérande d'un opérateur. Et donc on la définie égale à `fg`. Le cas se produit à chaque fois que le premier opérande de `"⊕"` est un opérateur générateur. Ainsi quelque soit deux termes `x,y` du langage, si `x` est un opérateur générateur alors `x"⊕"y=xy`. La présentation du langage d'opérateurs correspondante est :

`{f_E, g_E, h_E, **_((E,E)"→"E), ⊕_((E,E)"→"E)}`

ou bien de façon explicite :

`{f,g,h,**,+} "/" {`
        `f "∈" E, `
        `g "∈" E, `
        `h "∈" E, `
       `** "∈" (E,E)"→"E, `
        `+ "∈" (E,E)"→"E, `
`}`

Une présentation de structure regroupe une présentation d'un langage et une théorie d'égalité. En ce sens, une structure est un objet plus complet qu'un langage. Une structure comprend un langage. On évoquera souvent le langage d'une structure. Parcontre si on évoque la structure d'un langage, cela correspondra précisement à la structure composé de la présentation de ce langage et de la théorie d'égalité vide.

La présentation de la structure décrite précédement correspond à :

`{f_E, g_E, h_E, **_((E,E)"→"E), ⊕_((E,E)"→"E)} "/" {`
        `f"⊕"x=fx,`
        `g"⊕"x=gx,`
        `h"⊕"x=hx`
`}`

ou bien de façon explicite :

`{f,g,h,**,+} "/" {`
        `f "∈" E, `
        `g "∈" E, `
        `h "∈" E, `
       `** "∈" (E,E)"→"E, `
        `+ "∈" (E,E)"→"E, `
        `AAx"∈" E, f"⊕"x=fx`
        `AAx"∈" E, g"⊕"x=gx`
        `AAx"∈" E, h"⊕"x=hx`
`}`

Remarquez que dans la présentation d'une structure, on place la théorie au dénominateur. Et il y a deux niveaux de théorie, celle propre au langage qui décrit la dynamique de construction du langage et celle propre à la structure qui établit les égalités entre termes du langage.

Et il existe une traduction qui permet de passer d'un terme du premier langage à un terme du second langage et réciproquement, tel que cette traduction correspond à une bijection entre les deux structures. Par exemple dans le premier langage `f(f,g,h(f,g))` se traduit dans le second langage par `((ff)"⊕"g)"⊕"((hf)"⊕"g)`. On conclue donc que le langage d'opérateurs d'arité variable n'apporte pas de pouvoir d'expression plus important qu'un langage d'opérateurs d'arité fixe du moment que celui-ci posséde au moins deux opérateurs binaires. C'est pourquoi on se restreindra par la suite à n'étudier que les langages d'opérateurs d'arité fixe.

Notez que dans ce second langage d'opérateurs d'arité fixe, il existe des opérateurs binaires qui ne possèdent pas l'arité nulle et donc qui ne constituent pas des termes du langages et ne désignent donc pas des éléments de la structure quoique participant à la construction du langage. Et il existe des opérateurs n'ayant qu'une unique arité nulle et qui sont donc des termes du langage et qui désignent des éléments de la structure mais qui n'opèrent pas. Ils peuvent constituer des opérandes mais il n'opèrent pas.

8) Les bases du langage des types

On commence par énumèrer 5 processus de constructions de type (type des éléments, sous-type, intersection et réunion, complémentaire, application, polymorphisme) qui nous parraisses particulièrement simple. Le langage des types est un langage d'opérateurs. Voici comment il est engendré :

1- Le type des éléments

L'ensemble des termes du langage constitue l'ensemble sous-jacent de sa structure et se note `E`. C'est le premier type à considérer, le type de tous les éléments du langage.

2- Sous-type

On doit pouvoir définir un sous type d'un type. Etant donné un type `A`, on définie un sous-type `T` inconnue. Cela affirme simplement que  `T sube A` et donc que `T=> A`

3- Intersection et réunion

On doit pouvoir définir le type intersection de deux types `A nn B` dont la compréhension est `A et B`, et le type réunion de deux types `A uu B` dont la compréhension est `A ou B`.

4- Complémentaire

On doit pouvoir définir le type complémentaire d'un type `A`. c'est l'ensemble des termes qui n'appartiennent pas au type `A` et que l'on note `bar A` et dont la compréhension est `non A`.

5- Application

On doit pouvoir définir le type d'un opérateur désignant le comportement d'une application partant d'une liste finie de type `(A_1,A_2,A_3,...,A_n)` dont on considère le produit cartésien `(A_1×A_2×A_3×...×A_n), et allant vers un type `B` . Cela se fait grace à l'opérateur de construction d'application `->` qui est d'arité variable. Par exemple, le type `A_1,A_2,A_3,... -> B` représente l'ensemble des termes qui forment des applications de `A_1×A_2×A_3×... ->B`. Notez que quelque soit un type `A`, le type `->A` est égale au type `A`.

6- Polymorphisme

On doit pouvoir définir le type qui cumule pour le même opérateurs les comportements applicatifs d'un type `A` et d'un type `B`. On note cela, le type `A+B`. Par exemple, le type `(A->B) + (C->D)` représente les termes qui peuvent être appliqués à un opérande de type `A` pour produire un terme de type `B` et qui peuvent être appliqués à une opérande de type `C` pour produire un terme de type `D`.

 

 

 

 

Si nous ne voulons utiliser que des opératurs d'arité fixe, alors on définie deux opérateurs : l'opérateur de composition `**` qui appliqué à deux types `A` et `B` produit le type `A->B`, et l'opérateur d'ajout d'opérande, `+` qui appliqué à un type de la forme (A_1×A_2×A_3×... ->B)` et à un type `C` produit le type `(A_1×A_2×A_3×... ×C->B)`. Notez que si l'opérateur `+` est appliqué à un type simple `A` et à un type `B`, alors il produit le type `(A->B)`. Si l'opérateur `+` est appliqué à un sous-type simple `A` et à un type `B`, alors il produit le type `(A->B)`.

Le langage d'opérateurs typés obéït à l'axiomatique suivante :

  1. Tout opérateur est un identifiant et possède un nom unique sous forme d'un caractère..
  2. Tout opérateur est un terme.
  3. Tout terme possède un type.
  4. Le type d'un terme précise son arité et le type de chacune de ses opérandes.
  5. Le type d'un terme précise le type de résultat qu'il retourne une fois appliquée.
  6. L'application d'un terme à une liste d'opérandes compatibles, produit un terme résultat qui est l'expression du terme initiale appliqué à la liste des opérandes.
  7. Il existe un type d'arité zéro nommé `Omega` qui représente tous les éléments
  8. Création de type par définition d'application.
  9. Création de type par intersection et réunion de types.
  10. Création de sous-type.

 

---- 4 juillet 2017 ----

6) Les théorie d'égalités

On commence par étudier les théories d'égalités les plus simples qui sont les conjonctions finies d'égalités entre termes.

 

 

 

Un pemier choix simple consiste à ne considérer q'un seul type universel par arité.

Un deuxième choix consiste

6) Axiomatique du langage d'opérateurs simple

  1. Tout opérateur est un identifiant et possède un nom unique sous forme d'un caractère.
  2. Tout opérateur est un terme.
  3. Tout terme possède un type qui est un entier naturel.
  4. Tout terme de type `n` peut s'appliquer à tout `n`-uplet de termes de type zéro appelés opérandes pour produire un terme de type zéro appelé résultat.
  5. L'application d'un terme de type `n` à un `n`-uplet d'opérandes de type zero produit un terme résultat qui est l'expression du terme initiale appliqué à la liste des `n` opérandes.

 

 

 

 

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)`.

d'arité fixe ou variable, l'arité d'un opérateur étant le nombre d'arguments qu'il prend.

 

 

 

7) Le langage d'opérateurs simple

L'arité d'un terme est le nombre autorisé de ses opérandes. Par exemple un terme `T` est d'arité `3` s'il ne peut s'appliquer qu'à une liste de trois opérandes, tel que par exemple `T(x,y,z)`.

Le langage d'opérateurs simple adopte deux limitations importantes. Il n'autorise pas les opérateurs d'arité variables, et il limite les valeurs possibles des opérandes au seuls termes d'arité zéro. Il procède ainsi à deux simplifications majeurs : 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. Et les termes d'arité nulles sont appellés éléments. La seconde simplification est que tout terme n'opère que sur une liste fini d'éléments. Apparaît alors le concept de composition close d'opérateurs générateurs. Les éléments correspondent aux compositions closes d'opérateurs générateurs.

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

  1. Le type d'un terme est un entier naturel qui correspond à son arité.
  2. Les termes d'arité nulles sont appellés éléments.
  3. Tout terme n'opère que sur une liste fini 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....

On explicitera plus tard plus précisement le sens du symbole `->` dans la définition des types.

---- 25 juin 2017 ----

 

 

 

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.

Voici un exemple de terme clos désignant un élément :

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

A ce stade, l'axiomatique n'ayant pas proposé de moyen de construction pour les termes non clos, les seuls termes non clos sont les opérateurs générateurs d'arité supérieur à zéro, qui sont dans l'exemple `f` et `g`.

Les opérateurs générateurs engendrent par composition close l'univers de Herbrand noté `L°`. C'est l'ensemble de toutes les termes clos. Dans notre exemple :

`L° = {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` d'un langage d'opérateur simple. 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 » pour désigner l'univers de Herbrand c'est à dire 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 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 de Herbrand 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'ensemble des termes clos 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 terme, 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. 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.

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. C'est pourquoi dans la présente description des langages de données, on n'utilise pas d'opérateurs variables, ou plus exactement il n'est pas fait de distinction entre opérateur variable et opérateur constant.

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 définie un moyen de construction des termes clos qu'est la composition close d'opérateurs. On note `L°`, l'ensemble des compositions closes. Les compositions doivent évidement respecter les types c'est à dire s'appliquer qu'à des listes de termes clos de taille égale à l'arité de l'opérateur. C'est l'ensemble des termes clos du langage `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 définie un moyen de construction des termes qu'est la composition d'opérateurs, des compositions d'opérateurs qui peuvent être incomplètes. On note `L^•`, l'ensemble des compositions. Les compositions doivent évidement respecter les types c'est à dire que chaque opérateur ne s'applique 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 "`"."`" qui joue le rôle d'un élément générateur supplémentaire ajouté au langage `L` pour désigner les places libres dans les termes. L'ensemble des termes du langage `L` se note `L^•` est correspond exactement à l'extension `L°[{"."}] = (Luu{"."})°`

`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. Des expressions comme `f(f)` ou `g(a,g)` ne sont pas autorisés. 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. Parcontre dans le langage étendu les expression `f(f"(.)")` ou `g(a,g"(.,.)")`, sont autorisées et constituent des termes clos de `(Luu{"."})°`.

Voici un exemple de terme du langage `L` :

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

Les termes de `L°` sont les termes clos de `L°[{"."}]`.

Le processus de construction de l'univers de Herbrand est récurcif. `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 générateur désigant les sièges vides. Lorsque le terme ne contient plus aucun point, il est dit clos, et appartient à `L°`

Noter que la séquence commence par un point "`"."`" représentant un élément. 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 composition dans L

 

 

dans le langage étendu `L°[{"."}]`, 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)))...}`.

 

 

Etant donné une présentation `L` on note l'ensemble des termes clos du langage `L°`, et on note la structure libre associée `S = "<"L">"`. Le symbole `"<>"` désigne la cloture par composition close. Notez que 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 son langage, c'est à dire que `S` est une copie de `L°`.

L'ajout de variables `bbx, bby, bbz` au langage de la structure `S` correspond à une extension élémentaire notée `S[bbx,bby,bbz]` ou encore par `L°[bbx,bby,bbz]`. Tout se passe comme si on ajoutait au langage les éléments `bbx, bby, bbz` à part qu'ils sont variables, variable signifiant ici anonyme. Les mêmes notations ont 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.

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})`

 

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)

 

Le langage est dit du premier ordre si c'est un langage d'opérateurs simple dans lequel seuls les opérateurs d'arité nulle peuvent être variables et constituent l'unique type de variables universelles. Le langage du premier ordre s'obtient en ajoutant l'axiome suivant :

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

Tout opérateur variable constitue donc un élément variable universelle. Et il n'y a pas d'autre type de variable. L'ensemble des valeurs que peut prendre une variable correspond à l'ensemble des termes clos. Par exemple considérons le langage du premier ordre suivant :

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

Notez que l'opérateur `bbx` est noté en gras pour préciser qu'il est variable.

Pour le langage de données, il n'y a pas de différence entre variable et élément. Une variable est considéré comme une extension du langage, c'est à dire comme un élément générateur supplémentaire. Pour le langage de propriété, une variable évoque tous ce qu'il est possible d'unifier à elle c'est à dire ici tous les termes clos. Pour le langage de programmation une variable évoque tous ce qu'elle peut mémoriser c'est à dire également tous les termes clos.

On appel terme clos fonctionnelle, les termes clos qui contiennent des variables. Par exemple `g(bbx,a)` est un terme clos fonctionnel puisqu'il possède une variable dans sa définition.