Une stucture correspond à un type. Elle comprend des éléments, qui sont les éléments du type en question. Elle comprend des opérateurs unaires internes, qui sont les méthodes unaires définies dans le type en question. Et le qualificatif interne s'ignifie qu'appliqué à un élément du type en question l'opérateur retourne un élément du type en question. Elle comprend des opérateurs binaires internes. Ce sont les méthodes binaires définies dans le type et qui appliquées à une séquence de deux éléments de ce type produisent un élément de ce type. Et nous commençons par décrire ces opérateurs internes.
Le langage doit être en mesure de pouvoir définir toutes structures mathématiques énumérables. Pour cela, on utilise trois opérations fondamentales sur les structures :
Mais commençons par décrire la première structure énumérable à la quelle on pense, qu'est le semi-groupe des entiers strictement positifs. On le note `"N"`, tandis que le groupe des entiers positifs qui contient le zéro se note `NN`. Et ces structures servent de modèle, dans le sens que l'on peut créer autant de copies distinctes de ces structures que l'on veut. Et qu'on peut les retrouver par morphisme dans de multiples endroits même les plus inattendus.
Etant donné la structure `"N"`, il est possible de la dupliquer en autant de structures copies que l'on pourrait nommer `"N"_1,"N"_2,"N"_3,....`, et le fait qu'elles soient des copies de `"N"` se traduit par l'existence d'un isomorphisme entre chacune de ces copies et `"N"`. Plus concrètement, la création d'une copie de `"N"` se fait en créant un isomorphisme `varphi` de `"N"->varphi("N")`. Et toutes les possibilités sont ouvertes sur les images possibles de `varphi`. Les éléments `varphi("N")` peuvent être égaux à des éléments de `N` ou former de nouveaux éléments distincts de tous les éléments de `"N"`. Seule la contrainte que `varphi` est un isomorphisme de semi-groupe est posée, munissant l'ensemble `varphi("N")` d'opérateurs images pour former un semi-groupe. On ne connait pas l'ensemble d'arrivé mais on sait comment nommer les éléments et opérateurs images, et c'est la première étape de l'implémentation informatique.
Dans un langage d'opérateurs d'arité fixe, le semi-groupe `"N"` se définit formellement de deux façons :
Voyons en détaille ces deux constructions et la façon dont elle peuvent être implémentée.
On part de la structure vide. On procède à une extension élémentaire en ajoutant un élément, noté `1`, qui jouera le rôle de premier élément générateur. Puis on procède à une seconde extension élémentaire en ajoutant un opérateur unaire, noté `s"(.)"`, qui jouera le rôle d'incrémentation. L'élément `s(x)` est appelé le successeur de `x`. La structure ainsi obtenue se note :
`P= "<"1,s"(.)>"`
Un élément est un opérateur nullaire. Le suffixe `"(.)"` ajouté à `s` signifie que l'on désigne bien l'opérateur unaire de nom `s`. C'est une façon non obligatoire de rappeler l'arité de l'opérateur `s`, et cela est necéssaire s'il y a d'autres opérateurs de même nom et d'arité différente. Le suffixe `"(.,.)"` désigne l'arité 2. Le suffixe `"(...)"` désigne l'arité multi-aire, qui, selon le contexte, peut être autorisée ou non à être nulle. Autrement dit, l'argument est une séquence d'éléments (qui dans certain contexte n'est pas autorisés à être vide). L'opérateurs d'engendrement `"<...>"` retourne la structure engendrée par les opérateurs énumérées à l'intérieur des crochets. Les opérateurs énumérés entre les crochets sont dits générateurs, et sont dits appartenant à la présentation de la structure.
La structure `P` est une poêle de taille inconnue et de circonférence inconnue. Mais si nous avons les propriétés suivantes :
`AAxAAy,`
`s(x)"≠"1`
`(x"≠"y) => (s(x)"≠"s(y) )`
qui signifient littéralement ; « Aucun élément n'a `1` pour successeur » et « Quelque soit deux éléments distincts, leurs successeurs sont distincts », alors la structure monogène est libre, et est isomorphe à `"N"`.
Ces deux propriétés sont du premier ordre, c'est à dire qu'elles n'utilisent qu'un seul type de variable universelle représentant les éléments de la structure, et que son langage est limité aux quantificateurs `AA, EE`, aux opérateurs générateurs de la structure, au prédicat d'égalité entre élément, et aux connecteurs logiques qui sont des opérations booléennes. Ces deux propriétés forment une théorie du premier ordre, la théorie de la liberté d'une structure ayant comme opérateurs générateur `1` et `s"(.)"`. C'est la théorie du premier ordre de la structure libre `P`.
Le nom des opérateurs générateurs en soi n'a pas d'importance. C'est le rôle qu'on leur donne qui est important, et une partie du rôle est déterminé par l'arité de l'opérateur. On parlera de la signature de la structure, `(0,1)`, qui est la liste des arités des opérateurs générateurs dans l'ordre croissant.
Conventionnellement, on regroupe la théorie du premier ordre de la structure dans un patron. Et on présente la structure par ce patron appliqué à une séquence d'opérateurs, qui seront les opérateurs générateurs de la structure, chacun affublé d'un rôle défini par le patron.
`"P" = sf"Structure-libre"(1,s"(.)")`
La théorie portée par le patron est par principe du premier ordre. Elle ne suffit pas pour définir complètement la structure. Il faut ajouter à cela une théorie d'engendrement qui, elle, n'est pas du pemier ordre. C'est la propriété d'engendrement, `P"=<"1,s"(.)>"`, le fait que tout élément de la structure est obtenu par une composition close d'opérateurs générateurs. On la représente mathématiquement par la propriété du second ordre suivante :
`AA E "⊆" N, 1 "∈" E "et" (AAx"∈" E,s(x) "∈" E) => (E"="N)`
Notez l'ordre des priorités syntaxiques de la plus forte à la moins forte `"et/ou", =>, <=>, =, AA`. Cette propriétée est dite du second ordre, car elle utilise deux types de variable universelle que sont le type élément et le type ensemble. La théorie d'engendrement se présente aussi d'une façon informatique, de façon plus simple, en utilisant le méta-opérateur d'engendrement `"<...>"` :
`P= "<"1,s"(.)>"`
On s'aperçois alors que nous n'avons pas besoin de la théorie du premier ordre `sf"Structure-libre"`, ni de la théorie du second ordre qui circonscrit son engendrement, pour construire informatiquement la structure libre. On identifie la structure libre au langage d'opérateurs engendré. Le langage, dénué de signification, ne signifit que lui-même, et constitue le squelette permettant de construir tous ses éléments.
De la même façon que l'on définit les listes d'éléments, on définit les termes d'un langage.
En mathématique les compositions de tailles quelconque d'opérateurs appartenant à une présentation telle que par exemple `L={a,b,f("."),g(".,.")}`, se note à l'aide de l'opérateur de Kleene généralisé, `L"°"`, ou à l'aide des crochets entourant les opérateurs générateurs ou ensembles d'opérateurs générateurs :
`"<"a,b,f("."),g(".,.")"> = "<"L">"`
Le sixième type fondamentale est le type terme d'un langage. Mais on ne va pas utiliser un nom spécifique pour le désigner. On utilise directement l'opérateur constructeur `°` ou `"<...>"` ou une extension telle que `A["_"x, "_"y, "_"h(.)]`.
La méthode new du type terme est identifié à l'appel fonctionnelle, comme dans de nombreux types, et pour le type terme, la création peut s'écrire simplement par :
`{a,s(.)}°.new"( s(s(s(a))) )`
`{a,s(.)}°( s(s(s(a))) ) = s(s(s(a)))`
Et la création de terme peut s'écrire plus simplement encore, comme une composition sans nom, utilisant des opérateurs mis à disposition par le contexte. Néanmoins dans cette écriture dénudée, l'inférence de type va jouer tout son rôle et donner un type de terme plus précis selon le type des opérateurs présents.
On part de la structure vide. On procède à une extension élémentaire en ajoutant un élément, noté `1`, qui jouera le rôle de premier élément générateur. Puis on procède à une seconde extension élémentaire en ajoutant un opérateur binaire, noté `"+(.,.)"`, qui jouera le rôle d'addition. On le dote d'une syntaxe centrée et d'une priorité syntaxique plus faible que celle de l'égalité. L'élément `x"+"y` est appelé la somme de `x` et `y`. La structure ainsi obtenue se note :
`M= "<"1,"+(.,.)>"`
Et par défaut, la sructure est libre et s'identifie au langage engendré par ces deux opérateurs. Mais l'opérateur binaire `"+(.,.)"` n'ayant pour l'instant aucune propriété affirmée, il s'apparente à un produit non commutatif. La structure ainsi obtenue est celle des arbres nus, également appelé le magma monogène libre :
`M = {1, 1"+"1, 1"+"(1"+"1), (1"+"1)"+"1, 1"+"(1"+"(1"+"1)), 1"+"((1"+"1)"+"1), ... }`
Notez que le même nom de variable `M` est utilisé pour désigner la structure et son ensemble sous-jacent. Et c'est le type que la formule confère à la variable, qui permet de lever l'ambiguité. Ce mécanisme de typage s'appelle l'inférence de type.
Puis on quotiente ce magma par une théorie universelle conjonctive d'égalité `T` qu'est l'associativité de `"+(.,.)"` :
`T = {AAxAAyAAz, (x"+"y)"+"z=x"+"(y"+"z)}`
Cela revient à quotienter le magma par une relation d'équivalence, qui rend équivalant deux arbres nus en les applatissants c'est à dire en enlevant les parenthèses. On note se quotientage en omettant les quantificateurs dans la théorie universelle d'égalité. En effet la théorie est interne et ne fait donc pas référence à des opérateurs extérieurs à la sructure, et tout opérateur non mentionné dans la présentation de la structure (c'est à dire entre les crochets `"<...>"`) est donc considéré comme quantifié universellement sur la structure :
`N = M/T`
`N = ("<"1,"+(.,.)>")/{(x"+"y)"+"z=x"+"(y"+"z)}`
C'est la définition du semi-groupe monogène. Puis on peut doter l'opérateur `"+"` d'une syntaxe plus simple qui s'opère par absence de symbole et de parenthèse en juxtaposant les arguments de tel sorte que `1"+"1 "=" 11`. Ainsi nous avons :
`N= {1, 11, 111, 1111, 11111, ...}`
C'est le comptage par batons de `x`, qui est de complexité `x`, car pour lire un entier sous cette forme, il faut passer en revue tous ses `1`. Là où cela va devenir intéressant, c'est dans le choix d'une écriture des entiers permettant une lecture de complexité logarithmique. C'est par exemple, l'écriture en base `10` des entiers comme nous avons l'habitude de le faire, et c'est dans sa version la plus simple, l'écriture binaire, qui constitue un des fondements de l'informatique.
Mais avant cela, il nous faut décrire ce qu'est une structure, d'un point de vue pré-informatique puisque le binaire n'est pas encore mis en oeuvre. Et il faut commencer par les structures les plus simples et les plus vastes à la fois que sont les structures libres, c'est à dire les langages d'opérateurs d'arité fixe.
Le semi-groupe monogène libre peut être présenté en présentant la structure de Péano `"<"1,s"(.)>"` car il existe un lien entre l'incrémentation `s"(.)"` et l'addition `"+(.,.)"`, qui est `AAx, s(x)"="x"+"1`. Le lien inverse est plus compliqué à établir. L'addition se définie récurcivement à partir de l'incrémentation grace aux règles d'égalités suivantes :
`AAxAAy,`
`x"+"1"="s(x)`
`x"+"s(y) "=" s(x)"+"y`
C'est le calcul de la somme `x"+"y` par comptage de batons, de complexité `y`. Mais ces deux propriétés d'égalités ne dévoilent pas de façon explicite le programme de calcul de l'addition. On définie l'opérateur d'addition sous forme d'une fonction possèdant des entrées sélectives et s'appelant elle-même. En reprenant la syntaxe des blocs de code à entrée sélective, la fonction récurcive s'écrit :
`"+" = { x,1 | s(x)} {x, s(y) | s(x)"+"y}`
Les variables `x, y` utilisées dans les entêtes sont, ici, locale à la fonction, c'est pourquoi dans le paragraphe suivant, décrivant un exemple d'exécution, elles apparaissent marquées (en majuscule) `X, Y`, pour les différentier des variables de même nom déjà existantes.
On prend deux éléments de la structure de Péano `x` et `y` et on applique la fonction `"+"`. La fonction va comparer la liste des entrées `(x,y)` à la liste d'entête `(X,1)`, et si `y` vaut `1` alors l'unification va réussir ; `X"="x` et la fonction retournera `s(x)`. Parcontre si l'unification échoue, la fonction va tenter la seconde entête `(X,s(Y))`, et comme `y` est un élément de la structure de Péano qui n'est pas `1`, il est de la forme `y"="s(z)`. Et donc l'unification va réussire ; `X"="s(x)` et `Y"="z`, et la fonction va retourner l'évaluation de `s(x)"+"z`, une expression qui doit être évaluée car la fonction binaire `"+(.,.)"` est celle que nous sommes entrain de définir, et cela relance le calcul. C'est pourquoi la fonction `"+(.,.)"` ainsi définie est récurcive.
On passe donc du semi-groupe monogène libre `N` à la structure de Péano `P`, en définissant l'opérateur `s"(.)" = {x|x"+"1}` et en rendant privé la méthode `"+(.,.)"`. Et réciproqement, on passe de la structure de Péano au semi-groupe monogène en définissant l'opérateur `"+(.,.)" = { x,1 | s(x)} {x, s(y) | s(x)"+"y}` et en rendant privé la méthode `"s(.)"`.
On voit commun l'implémentation diffère selon que l'on construit `N` à partir de `P` ou `P` à partir de `N`. Le changement d'implémentation constitue une compilation dite structurelle.
Une structure libre se présente par une liste d'opérateurs générateurs d'arité fixe constituant sa présentation, tel que par exemple `S="<"a,b,f"(.)",g"(.,.)>"`. Et il n'y a pas de différence entre une structure libre et un langage d'opérateurs d'arité fixe. La structure libre est définie par ce qu'elle peut construire à partir de ses opérateurs générateurs, sans évaluation des opérateurs générateurs.
On étend notre langage mathématique pour pouvoir exprimer la propriété de structure libre dans le cas général. Cela se fait en 7 points :
Un élément est identifié par un mot du langage, qui s'apparente à son nom, et qui corrrespond à la composition close d'opérateurs générateurs qui l'a construit, sans évaluation des opérateurs générateurs. Exemple, l'élément `g(a,f(a))`. Etant donnés deux variables `x,y` désignant des éléments, l'expression `x"="y` signifie qu'ils ont un même nom, qu'ils sont identifiés par un même mot du langage, par une même composition close d'opérateurs générateurs, sans évaluation des opérateurs générateurs. Et réciproquement, l'expression `x"≠"y` signifie qu'ils ont des noms différents, qu'ils sont désignés par deux compositions closes différentes d'opérateurs générateurs, sans évaluation les opérateurs générateurs.
La théorie de la structure libre s'écrit :
`bar AA A bar AA B AA tilde u AA tilde v,`
`(A"≠"B) "ou" (tilde u"≠" tilde v) => (A(tilde u)"≠"B(tilde v) )`
Elle stipule que si les opérateurs générateurs ont des noms distincts dans la présentation ou que les séquences d'arguments sont distinctes dans la structure alors l'application des opérateurs sur ces séquences d'arguments doit produire nécessairement des éléments distincts dans la structure, ce qui est assuré en identifiant l'élément à la composition close qui l'a construit, sans évaluation les opérateurs générateurs. La contraposée peut aussi être utile :
`bar AA A bar AA B AA tilde u AA tilde v,`
`(A(tilde u)"="B(tilde v) ) => (A"="B) "et" (tilde u"=" tilde v)`
Cela signifie textuellement : « Quelque soit des opérateurs générateurs `A,B`, quelque soit des séquences d'arguments `tilde u, tilde v`, si `A(tilde u)"="B(tilde v)` alors `A` et `B` désignent le même opérateur générateur identifié par un même nom dans la présentation, et les séquences d'éléments sont égales dans la structure, `tilde u "=" tilde v` ».
Afin que le langage exprime autre chose que lui-même, on sépare le signifiant d'avec le signifié, le mot d'avec l'élément désigné par le mot, l'élément de la structure libre d'avec l'élément réel qu'il désigne. Il en découle que plusieurs mots peuvent désigner le même élément. Le mot est un élément de la structure libre, notons le, `x`. L'élément désigné par `x` est un élément du monde réel, noté `sigma(x)`. C'est un élément image d'une application d'évaluation `sigma`.
Chaque élément représenté ici par la variable `x` est un opérateur nullaire. Mais `x` est une variable, donc il y a une première évaluation de variable qui expose ce qu'elle contient, une composition close d'opérateurs générateurs sans évaluation des opérateurs générateurs. Et cette évaluation de variable est implicite et est repétée à chaque fois, faisant que l'on manipule le nom de la variable au lieu de son contenant.
Puis il y a une seconde évaluation qui elle, est explicite. C'est l'évaluation du langage, produisant ce que désigne un mot du langage. L'élément `x` qui n'est qu'une composition clause d'opérateurs générateurs sans évaluation, désigne un élément réel noté `sigma(x)`. L'élément `x` s'évalue en un élément image `sigma(x)` qui représente l'élément réel qu'il désigne.
La structure libre n'est qu'un langage. L'élément `x` n'est qu'un nom, une composition d'opérateurs générateurs sans évaluation. La variable `x` contient ce nom. Prenons par exemple l'élément `f(a)`. C'est un opérateur nullaire non-générateur. Il s'évalue en un élément image `sigma(f(a))` qui est l'élément réel qu'il désigne, et `f(a)` constitue son nom dans la structure libre. Et, il se peut que des noms distincts désignent le même élément réel. L'évaluation est une application `sigma` de la structure libre `S` vers le monde réel `M`. Considérons deux éléments, représentés par les variables `x, y`. Chacune de ces variables contient un élément de la structure libre, qui est un mot du langage, une composition close d'opérateurs générateurs sans évaluation. Il y a deux sortes d'égalité, l'une dans la structure libre `S` qui se note `x=y`, et l'autre dans le monde réel `M` qui se note `sigma(x)=sigma(y)`.
Ainsi l'évaluation du langage introduit un ensemble d'égalités entre des éléments de la structure libre. On appel théorie d'égalité, un ensemble d'égalités.
Dans l'approche constructive, la désignation est une construction. Si un opérateur générateur nullaire `x` désigne quelque chose autre que lui-même, c'est qu'il peut s'évaluer, tel l'exécution d'un programmealors cela défini une évaluation appelé concrétisation. Les éléments nullaires `x` peuvent être évalués par concrétisation. Et pour distinguer l'élément de la structure libre et sa concrétisation, on note `x` l'élément de la structure libre et `x()` sa concrétisation.
Toute structure s'obtient à partir d'une structure libre en la quotientant par une relation d'équivalence qui respecte les opérateurs internes (forme implicite) ou en la transformant par un morphisme (forme explicite), qui envoie l'élément sur sa classe d'équivalence. Etudions la forme implicite.
La structure libre, `L`, est un langage d'opérateurs d'arité fixe, et possède une signature qui est la séquence des arités de chaque opérateur générateur dans l'ordre croissant.
Une théorie d'égalité de langage `L` est un ensemble d'égalité entre éléments de la structure libre `L`, interprété comme une conjonction d'égalités, une formule logique du premier ordre c'est à dire avec un seul type de variable représentant un élément de la structure, ne comprenant que des quantificateurs universelles, ne comprenant que des opérateurs générateurs de `L`, ne comprenant comme connecteur logique que la conjonction, `"et"`. ne comprenant que le prédicat d'égalité `"=(.,.)"`, et ne comprenant que les opérateurs générateurs du langage `L`.
Une tel théorie `T`, définie une structure quotient notée `L"/"T`, et engendre une relation d'équivalence sur `L` définie comme suit : deux éléments de la structure libre `x` et `y` sont équivalents, ce qui se note `xTy`, si et seulement s'il existe une démonstration de leur égalité à partir de `T`, ce qui s'écrit `T|--x"="y`. Et ils désignent alors le même élément dans la structure quotient.
L'opérateur de démontrabilité `|--` est de priorité la plus faible, et l'opérateur `T"(.,.)"` est de priorité la plus forte.
L'opérateur de démontrabilité `|--`, qui est mécaniquement déterminé, dans le cas générale admet 3 valeurs logiques possibles exclusives et exhaustives : `"vrai"`, `"faux"`, `"indécidable"`. La théorie `T` est dite discernante si elle tranche toutes les propositions d'égalité entre éléments de `L`. Et dans ce cas nous avons :
`AAxAAy,`
`xTy <=> (T|--x"="y)`
La recherche de la notation la plus ergonomique est importante, autant pour des raisons de motivation que pour des raisons de construction. Et l'évolution de la notation permet souvent une transcription en douceur vers d'autres formes de structure mathématiques plus appropriées. La relation d'équivalence définie par `T` se note le plus simplement par un opérateur binaire lié à `T`. Et le lien le plus simple consiste à utiliser le même nom `T`, en tant que variable contenant une théorie universelle conconctive d'égalité, pour en faire une variable contenant un opérateur binaire `T"(.,.)"`, sachant qu'il n'existe pas déjà. On choisie en suite une syntaxe centrée pour cet opérateur : `T(x,y)=xTy`
Ainsi, sous la condition précédente, la relation `"T(.,.)"` est une relation d'équivalence, c'est à dire qu'elle satifsait :
`AAxAAyAAz,`
Reflexif : `xTx` Symétrique : `xTy=>yTx` Transitif : `xTy "et" yTz => xTz`
Le morphisme qui envoit l'élément sur sa classe d'équivalence, définie par `T`, se note le plus simplement par un opérateur unaire lié à `T`. Et le lien le plus simple consiste à utiliser le même nom `T`, en tant que variable contenant une théorie, pour en faire un opérateur unaire `T"(.)"`, sachant qu'il n'existe pas déjà. Ainsi, par convention on note `T(x)` la classe d'équivalence de `x`. Deux éléments sont équivalents s'il font partie de la même classe :
`xTy <=> (T(x)=T(y))`
`xTy <=> x "∈" T(y)`
`xTy <=> y "∈" T(x)`
Pour savoir si deux éléments `x,y` sont équivalent, il est nécessaire de calculer `xTy`, c-à-d de regarder si la classe d'équivalence de `x` est bien égale à la classe d'équivalence de `y`, c-à-d de regarder si `x` appartient à la classe d'équivalence de `y`, c-à-d de regarder si `y` appartient à la classe d'équivalence de `x`.
La forme implicite est la théorie d'égalité `T`, tandis que la forme explicite est l'opérateur `T"(.)"`.
On étend notre langage pour pouvoir exprimer la structure quotient à partir de la structure libre. Cela se fait en `6` points :
La strucure quotient `L"/"T` regroupe les classes d'équivalence. La relation `"T(!(.),!(.))"` correspond à l'égalité dans la structure quotient. La relation `"T(.,.)"` est respectueuse vis-à-vis des opérateurs générateurs, c'est à dire que pour chaque opérateur générateur unaire `f`, pour chaque opérateur générateur binaire `g`, etc., nous avons :
`bar AA f"(.)"bar AA g"(.,.)"AAxAAyAAzAAt,`
`xTy => f(x)Tf(y) `
`(xTz) "et" (yTt) => g(x,y)Tg(z,t) `
Cela s'écrit de façon plus générale comme suit. Pour chaque opérateur de construction interne `A`, pour chaque séquence d'éléments `tilde u, tilde v`, nous avons :
`AA A AA tilde x AA tilde y,`
`tilde x T tilde y => A(tilde x)TA(tilde y) `
Et il découle de cela que le respect de `T"(.,.)"` s'étend à tous les opérateurs construit à partir des seuls opérateurs générateurs. On définie la notion d'opérateur construit de façon interne s'ils sont construit à partir des seuls opérateurs générateurs. Et par défaut, les opérateurs seront de construction interne. Ainsi `AA A` signifie quelque soit un opérateur de construction interne `A`. Il ne faut pas confondre pour un opérateur, le fait d'être de construction interne, et le fait d'être interne c'est à dire de s'appliquer à des éléments de la structure pour produire un élément de la structure. Nous avons :
`AA tilde u AA tilde v,`
`tilde u T tilde v <=>(T(tilde u) "=" T(tilde v) )`
Et cela s'applique donc aussi pour deux éléments quelconque `x` et `y`, puisque'une séquence peut être un élément.
`AA x AA y,`
` (xTy) <=>(T(x) = T(y) )`
Les opérateurs internes transportent l'égalité, c'est une évidence :
`(tilde u "=" tilde v) => (A(tilde u)"="A(tilde v) )`
Les opérateurs internes transportent aussi l'équivalence puisqu'elle respecte les opérateurs de construction internes :
`(tilde u T tilde v) => (A(tilde u) T A(tilde v) )`
L'application `T"(.)"` qui envoi l'élément sur sa classe d'équivalence respecte les opérateurs générateurs (et donc aussi les opérateurs de construction interne), et donc constitue un morphisme de `L` sur `L"/"T` :
`T"(.)"∈ L "→" L/T`
On étend le domaine de `T` pour l'appliquer aux opérateurs générateurs :
`AA A, T(A) = T"∘"A"∘"!`
C'est à dire :
`AA A,AA tilde u, T(A)( tilde u) = T(A(!(tilde u))) `
L'ensemble des classes d'équivalences munis des opérateurs générateurs forment la structure quotient que l'on note `L"/"T` ou encore `T(L)`. Les opérateurs de construction interne `A` de `L` possèdent une image que l'on note `T(A)`. Et nous avons :
`AA A, T(A) = T"∘"A"∘"!`
C'est à dire :
`AA A "∈" L, AA tilde e "∈" T(L), T(A)(tilde e) = T(A(!(tilde e)))`
Toute structure s'obtient à partir d'une structure libre en la quotientant par une relation d'équivalence qui respecte les opérateurs internes (forme implicite) ou en la transformant par un morphisme (forme explicite), qui envoie l'élément sur sa classe d'équivalence. Etudions la forme explicite.
Notez qu'un opérateur est dit générateur si et seulement s'il appartient à la présentation de la structure libre.
Le morphisme dont il est question est une fonction `varphi"(.)"` dont l'image est une structure munie des mêmes noms d'opérateurs générateurs mais avec une quote pour les distinguer. La quote n'est qu'une autre dénomination du morphisme `varphi` qui étend son domaine de définition pour pouvoir s'appliquer non seulement aux éléments mais aux opérateurs également.
Le morphisme `varphi` est déterminé formellement en fixant les images des éléments et opérateurs générateurs. Pour chaque élément générateur `e`, pour chaque opérateur générateur unaire `f`, pour chaque opérateur générateur binaire `g`, etc.,
`bar AAe bar AAf"(.)" bar AAg"(.,.)"AAxAAy,`
`varphi(e)=e'`
`varphi(f(x))=f'( varphi(x))=f'(x')`
`varphi(f)=f'`
`varphi(g(x,y))= g'(varphi(x), varphi(y))= g'(x',y')`
`varphi(g)=g'`
Et il découle du fait que varphi et un morphisme et que les opérateurs sont générateurs, que la présente stabilité s'applique à tous les opérateurs construits de façon interne :
`AAf"(.)" AAg"(.,.)"AAxAAy,`
`varphi(x)=x'`
`varphi(f)=f'`
`varphi(f(x))=f'(x')`
`varphi(y)=y'`
`varphi(g(x,y))=g'(x',y')`
Cela s'écrit de façon plus générale comme suit. Pour chaque séquence d'éléments générateurs `tilde u`, pour chaque opérateur de construction interne`A`, nous avons :
`AA A AA tilde x,`
`varphi(tilde x)= tilde x'`
`varphi(A)= A'`
`varphi(A(tilde x)) = A'(tilde x')`
A partir des opérateurs générateurs, on construit l'ensemble sous-jacent qui regroupe toutes les compositions closes d'opérateurs générateurs. On construit également l'ensemble des opérateurs dit de construction interne à la structure. Chaque opérateur non-nullaires de construction interne est défini par un programme conçu à partir des opérateurs générateurs, et on classifie plusieurs niveaux de programmation :
Niveau n°0 - Présentation - Ce niveau ne contient que les opérateurs générateurs, qui sont les éléments et opérateurs exposés dans la présentation de la structure. Exemples : `1`, `s"(.)"` , `"+(.,.)"`
Niveau n°1 - Termes clos - Ce niveau contient tous les éléments qu'il est possible de construire par composition close d'opérateurs générateurs. Exemples : `1`, `s(1)`, `s(s(1))`, `1"+"1`, `(1"+"1)"+"1`, `1"+"(1"+"1)`. Ces l'ensemble sous-jacent.
Niveau n°2 - Termes non clos - Ce niveau contient tous les opérateurs qu'il est possible de construire par composition non nécessairement close d'opérateurs générateurs, et où les places libres de gauche à droite, sans changer d'aucune façon l'ordre, constituent l'ordre d'appel des arguments. Cela correspond à la logique polonaise. Exemple : l'opérateur `(".+"1)"+"((1"+.")"+.")` correspond à l'opérateur `(x,y,z)|->(x"+"1)"+"((1"+"y)"+"z)`, et si nous avons l'associativité et la commmutativité de `"+"` alors cet opérateur est égal à l'opérateur `(x,y,z)|->1"+"1"+"x"+"y"+"z`.
Niveau n°3 - Composition générale - Ce niveau contient tous les opérateurs qu'il est possible de construire à partir des précédents à l'aide de la composition générale. Cela correspond à la programmation sans boucle ni condition. On introduit dans le langage le méta opérateur `"↦"` qui prend en premier argument une entête constituée de `n` variables de noms distincts, et qui prend comme second argument un terme clos du langage étendu par ces `n` variables, appelé corps de l'opérateur. Cela produit un opérateur d'arité `n`. Lors de l'appel de l'opérateur d'arité `n`, l'entête récupère les `n` arguments d'appel dans ses `n` variables locales. Exemples : `x"↦"x`, `x"↦"x"+"x`, `(x,y)"↦"x"+"y"+"x"+"1`. Noter que ce niveau permet de définir la fonction identité `x"↦"x`
Niveau n°4 - Programmation sans boucle
Ce niveau contient tous les opérateurs qu'il est possible de construire à partir des précédents à l'aide d'une succession d'instruction sans boucle. Il contient les conditions, et les sélection d'entrées. L'entête est constituée de `n` expressions non nécessairement distinctes. Lors de l'appel de l'opérateur d'arité `n`, l'entête tente de s'unifier au `n` arguments d'appel, et si cela échoue le processus passe à l'alternative suivante.
Niveau n°5 - Programmation primitive récurcive
Contient tous les opérateurs qu'il est possible de construire à partir des précédents à l'aide de la programmation primitive récurcive, c'est à dire programmés par composition et par récursion primitive, ou dit autrement dans un langage de programmation impératif, programmés uniquement avec des boucles "for" et non avec les boucles "while", et sans modifier les indexes des boucles "for" autrement que par augmentation, ni modifier les bornes des boucles "for" autrement que par réduction, permettant ainsi de garantir l'arrêt borné du programme.
Ce niveau introduit la récursivité primitive. On la définie de manière générale appliquée à une structure autre que les entiers. La récursivité primitive met simplement en oeuvre le principe de clôture, un principe co-substantiel à la notion de structure. A savoir : Si des éléments `a, b` satisfont une propriété `P"(.)"`, c'est à dire si nous avons `P(a)` et `P(b)`, et que des opérateurs `f"(.)", g"(.,.)"` respectent la propriété `P"(.)"` sur la structure `"<"a,b,f"(.)",g"(.,.)>"`, c'est à dire si pour tout élément `x` de la structure `"<"a,b,f"(.)",g"(.,.)>"` nous avons `P(x) => P(f(x))` et si pour tout couple d'éléments `x` et `y` appartenants à la structure `"<"a,b,f"(.)",g"(.,.)>"` nous avons `P(x) "et" P(y) => P(g(x,y))`, alors nous pouvons déduire par récurrence primitive que tous les éléments de la structure `"<"a,b,f"(.)",g"(.,.)>"` satisfont la propriété `P"(.)"`. Nous déduisons par exemple `P(g(b,f(a)))`.
|
On note une séquence de `n` variables comme suit : `tilde u = (u_1, u_2, u_3, ... , u_n)`.
---- 16 mai 2021 ----
Une fonction primitive récurcive `r` d'arité `n"+"1` se construit à partir de `k` opérateurs tels que par exemple `a, b, f"(.)", g"(.,.)"`, formant implicitement une structure `"<"a,b,f"(.)",g"(.,.)>"`, et à partir de `k` fonctions `r_1, r_2, r_3, ... , r_k`, une fonction par opérateur, d'arité égale à `n` plus deux fois l'arité de l'opérateur. La fonction `r` se programme alors comme une suite d'alternative :
`r(tilde u, a) = r_1(tilde u)`
`r(tilde u, b) = r_2(tilde u)`
`r(tilde u, f(x)) = r_3(tilde u, x, r(tilde u,x))`
`r(tilde u, g(x,y)) = r_4(tilde u, x, y, r(tilde u,x), r(tilde u,y))`
Notez que les dernières alternatives sont récurcives. La fonction r est réappelée dans un ou plusieurs arguments. L'opérateur r se note à l'aide du méta-opérateur d'alternative | comme suit, chaque alternative étant passée à la ligne pour plus de clarté :
`r = (tilde u, a) → r_1(tilde u) |`
`(tilde u, b) → r_2(tilde u) |`
`(tilde u, f(x)) → r_3(tilde u, x, r(tilde u,x)) |`
`(tilde u, g(x,y)) → r_4(tilde u, x, y, r(tilde u,x), r(tilde u,y))`
C'est une liste d'alternatives à prendre dans l'ordre. Lors de l'appel `r(tilde w)` où `tilde w` est une séquence de `n"+"1` termes clos, la fonction `r` va tester l'unification de `w` avec la première entête `(tilde u,a)`. Si l'unification réussi alors la fonction `r` retourne `r_1(tilde u)`, et si l'unification échoue alors on passe à l'alternative suivante, etc...
La récurcivité primitive peut ainsi être construite indépendament des entiers. De tel sorte que les entiers ne sont plus une structure particulière, nécessaire à la récurrence.
Niveau n°6 - Programmation récurcive
Niveau n°7 - Programmation d'arret non sûr
---- 1 mai 2021 ----
Voir un exemple de récurcivité non-primitive, la fonction d'Ackermann-Péter.
Masquage - L'utilisation de ce protocole de manière imbriquée tel que par exemple `x"↦"(y"↦"f(y))`, va entrainer la définition d'un typage, et un mécanisme de variables locales et de variables masquées. Les variables d'appel, à gauche du méta-opérateur de définition `"↦"` sont de nouvelles variables locale à la fonction. Et si elles ont été utilisé lors d'appel antérieur, il s'agit alors de nouvelle variable portant le même noms. Par exemple l'opérateur d'expression `x"↦"(x"↦"(x+a))` comprend deux niveaux de contexte emboités et la variable `x` du premier contexte est masquée par la variable `x` du second contexte, faisant que cette expression est équivalente à `x"↦"(y"↦"(y+a))`
Currification - Puisque qu'un opérateur `f` d'arité `n` est un programme avec `n` entrées, on peut scinder la liste des entrées en deux morceaux contigüs `n_1 + n_2 = n`, et considérer que `f` est une fonction d'arité `n_1` retournant une fonction d'arité `n_2`. Et ce procédé peut être répété. Par exemple nous avons :
`x |-> (y |-> g(x,y)) = (x,y) |-> g(x,y)`
`x |-> ((y,z) |-> h(x,y,z)) = (x,y,z) |-> h(x,y,z)`
`x |-> (y |-> (z |-> h(x,y,z))) = (x,y,z) |-> h(x,y,z)`
La currification réduit ainsi le nombre de types différents d'opérateurs. Et il y a deux formes normales, la forme série qui utilise l'opérateur de construction d'application binaire `"↦(.,.)"`, et la forme liste qui n'utilise qu'une seul fois un opérateur de construction d'application d'arité variable `"↦(...)"`. Par exemple l'opérateur `x"↦" ((y,z) "↦" h(x,y,z))` admet une forme normale série `x"↦"(y "↦" (z "↦" h(x,y,z)))` et admet une forme normale liste `(x,y,z) "↦" h(x,y,z)`
Extension - Si on autorise l'utilisation de variables tel que `x,y` dans le corps sans qu'elles n'apparaissent dans l'entête, on se place alors dans le langage étendu par extension élémentaire.
Par exemple dans le magma `M = sf"Magma monogène"("+(.,.)",1)`, l'opérateur `f = x"↦"a"+"x` se place dans la structure étendue `M[a]` qui se présente comme `sf"Magma bigène"("+",1,a)`.