Les mathématiques sont les sciences exactes. C'est à dire que chacune de leur déduction est vérifiable par un procédé mécanique, par le fonctionnement d'une machine idéale, composée de rouages parfaitement emboités et sans aucun jeu, procédant ainsi à un calcul parfaitement défini ne laissant rien au hasard. Et à bien y regarder, il s'agit plus précisement d'une mécanique classique.
Les mathématiques sont un jeu de construction, un jeu de légo, où chaque pièce s'encastre parfaitement dans un édifice servant de démonstration. Rien ne relève du mystère, tout est trivial..., c'est l'aspect exacte de la science. Puisque les notions mathématiques s'établissent les une après les autres et se démontrent de façon formelle en s'appuyant sur les résultats des notions antérieurs, il doit être possible de construire une oeuvre mathématique générale de façon formelle en démontrant chaque étape à partir des précédentes et en ne partant de rien. Cette construction s'appelle une génèse.
La logique et la programmation étant ainsi jumelles, le développement de l'une ne peut se faire sans le développement de l'autre. Le langage logique se construit en même temps que le langage de programmation, établissant un parallèle entre la puissance démonstrative et la puissance algorithmique.
Le démonstrateur peut avancer à l'aveugle et appliquer la méthode Shadok qui consiste à tester au hasard. Et dans ce cas, il n'est lui-même finalement qu'une machine produisant des démonstrations, une machine idéalisée, composée de rouages parfaitement emboités et sans aucun jeu. Ces machines sont décrites à l'aide d'un langage formel et d'un langage de programmation, que nous allons perfectionner tout au long de la génèse.
Comment proposer la logique sans l'aide de la logique ? Pour cela, on part de l'aspect mécanique des mathématiques. On part des programmes informatiques qu'il est possible d'écrire. La démonstration qu'un programme produise la chose attendue, s'obtient simplement en l'exécutant. Ainsi nous exposons les rudiments de la logique avec en parallèle des rudiments de la programmation.
Au départ, il y a l'embryon d'une programmation, puisque c'est par la programmation que nous voulons fonder cette genèse. On fait donc le choix d'une logique programmative qui consiste à poser les règles de déduction dans un langage formel. Et on commence par décrire la logique propositionnelle.
Le premier concept est la valeur booléenne "vrai" que l'on désigne par la tautologie `"⊤"` ou par le chiffre `1`, et la valeur booléenne "faux" que l'on désigne par l'antilogie `"⊥"` ou par le chiffre `0`. À ce stade, on ne peut écrire que deux propositions, l'une est vrai, l'autre est fausse. Le langage de la logique propositionnelle noté `ccL_1` est l'ensemble de ces deux propostions.
`ccL_1={"⊥","⊤"}`
Le second concept sont les opérateurs booléens couramment utilisés :
La négation La conjonction (et) La disjonction (ou) Le ou exclusif L'implication L'équivalence
Ces opérateurs sont ajoutés au langage et s'appliquent à des valeurs booléennes pour produire une valeur booléenne. On a suffixé les symboles pour rappeler leur arité avec `"(.)"` pour indiquer que l'opérateur est unaire, et avec `"(.,.)"` pour indiquer que l'opérateur est binaire.
Les règles de calcul des opérateurs booléens sont décrites par les tables de vérité suivantes :
À cette étape, le langage de la logique propositionnelle devient l'ensemble `ccL_2` des compositions d'opérateurs booléens `¬, "∧", "∨", =>, <=>,+` et de valeurs booléennes `"⊥","⊤"`, que l'on appelle terme, tel que par exemple :
`("⊤∧¬⊥") => "⊤"`
Pour définir le langage, on utilise l'opérateur de Kleene généralisé `°` ou les crochets symboles d'engendrement `"<...>"` qui indique la cloture par composition close :
`ccL_2 = {0,1,"¬(.)", "∧(.,.)", "∨(.,.)", "+(.,.)", "⇒(.,.)", "⇔(.,.)"}°`
`ccL_2 = "<"0,1,"¬(.)", "∧(.,.)", "∨(.,.)", "+(.,.)", "⇒(.,.)", "⇔(.,.)>"`
ou bien on utilise les grammaires décrites sous forme d'équations récurcives d'ensembles. On utilise la notation applatie des ensembles, c'est à dire tel que par exemple si `a` et `b` sont des éléments et si `A` et `B` sont des ensembles, alors :
`{a, A, b, B} = {a,b}uuAuuB`
Et on utilise la notation ensembliste des opérateurs, c'est à dire que par exemple `A"∧"B` désigne l'ensemble des termes composé d'un terme appartenant à `A` et d'un terme appartenant à `B` composé avec l'opérateur `"∧"` :
`A"∧"B = {a"∧"b "/" a "∈" A, b "∈" B}`
Avec ces deux notations, la grammaire s'écrit simplement :
`bbS = { 0, 1, "¬"bbS, bbS"∧"bbS, bbS"∨"bbS, bbS"+"bbS, bbS"⇒"bbS, bbS"⇔"bbS}`
`ccL_2=S`
Chaque terme désigne une proposition qui correspond à un calcul booléen et qu'il suffit d'effectuer pour découvrir sa valeur de vérité.
Afin d'éviter un usage intensif des parenthèses de priorisation, on établit une priorité syntaxique des opérateurs. L'ordre des priorités syntaxiques de la plus forte à la plus faible est :
`"+"` `=>` `<=>`
Ainsi la proposition `"¬⊥∧⊤" => "⊥"` est identique à la proposition `(("¬⊥)∧⊤") => "⊥"`. Puis on établit un sens syntaxique de gauche à droite faisant que `"⊤⇒⊤⇒⊤⇒⊤"` est identique à l'expression `"⊤⇒(⊤⇒(⊤⇒⊤))"`.
Notre recherche informatique consiste en la conception d'un framework c'est à dire d'un ensemble d'outils informatiques rudimentaires fondamentaux qui sont amenés à être utilsés par la suite comme des briques élémentaires de construction et ont pour ambition de constituer des références en terme de programmation.
La donnée sous forme de texte lisible par un humain joue un rôle fondamental. L'informatique utilise à ses débuts une norme de codage de caractère appelé ASCII (American Standard Code for Information Interchange) qui comprend juste 128 caractères. En étudiant les mathématiques ainsi que différents languages, on réalise l'handicap que constitue l'absence de caractères plus nombreux. La solution est apportée par la nouvelle norme internationale appelée Unicode et qui permet d'utiliser plus d'un million de caractères. Cette norme est complétée de manière économe pour avoir une représentation du caractère sur 1, 2, 3 ou 4 octets et s'appelle l'encodage UTF-8.
L'UTF-8 est la norme la plus répandue au monde, et sur les système Linux elle est utilisée par défaut.
Unicode en ruby\u{28} \u{29}
Dans l'interpéteur ruby irb, l'affichage de tels caractères se fait en introduisant le code tel quel dans la chaine de caractères. Ainsi l'instruction print "x\u21D4y" affichera x⇔y. Réciproquement, l'instruction "\u21D4".ord retournera le code décimale 8660 du caractère ⇔ qui peut être converti en code hexadécimal à l'aide de la méthode to_s(16). Ainsi l'instruction "\u21D4".ord.to_s(16) retournera "21d4". Ces nouveaux caractères peuvent être utilisé directement, ainsi l'instruction "⇔".ord.to_s(16) retournera le code hexadécimal "21d4". Et ils peuvent être utilisés dans les noms d'attribut et de méthode.
Le terme représenté sous forme de chaine de caractères ne met pas en évidence la composition des opérateurs booléens. L'implémentation consiste à définir une représentation interne de la proposition sous forme d'arbre mettant en exergue cet emboitement des opérateurs.
L'arbre est constitué d'un emboitement de noeuds et de feuilles, le premier noeud constituant la racine. La construction de l'arbre se fait de façon récurcive. L'arbre est donc une structure fractale. Chaque noeud constitue la racine d'un sous-arbre et réitère un processus de construction d'arbre. Le noeud est associé à un opérateur booléens, et possède éventuellement une ou deux adresses `"g"`, `"d"` désignant ses fils. Et s'il n'en possède pas, c'est que c'est une feuille de l'arbre.
Une des voies de développement ne concoit que des noeuds ayant 2 fils, car on peut représenter une liste `a,b,c,d` par une composition d'opérateurs binaires `(a,(b,(c,d))`. Ainsi dans cette voie, pour pouvoir manipuler des listes de propositions, on ajoute au langage de la logique propositionnelle, l'opérateur binaire virgule. Et cela permet de manipuler non seulement des listes de propositions, mais des arbres binaires de propositions. Notez alors que cet virgule n'est pas un opérateur booléen, car il s'applique à deux arbres binaires de propostions pour produire un arbre binaire de propositions.
Passons en revue les types rudimentaires dont nous avons besoin ici. Voici les trois types d'opérateurs booléens que nous utilisons :
`{0,1}`
`{0,1}"→"{0,1}`
`{0,1}"×"{0,1}"→"{0,1}`
Le premier type est le type booléen, le second type est le type opérateur booléen unaire, le troisième type est le type opérateur booléen binaire.
Nous décrivons ainsi un langage de type, utilisant le symbôle d'ensemble `{...}` pour énumérer les valeurs possibles contenues par un type énumératif, utilisant le produit directe d'ensemble `"×"` pour concevoir les types de couples, et utilisant le symbôle d'application `"→"` pour désigner le type d'entrée et le type de sortie d'un opérateur. Notez que l'opération `"×"` est de syntaxe prioritaire sur l'opération `"→"`.
Dans un programme informatique, l'objet est désigné de façon indirecte par une variable, mais l'objet possède une implémentation concrète de bas niveau qui, lorsque l'objet est rudimentaire, est constitué d'un bloc mémoire d'un seul tenant. Et c'est le type qui va décrire à quoi correspondent les données contenues dans ce blocs mémoire ainsi que sa taille qui peut dépendre d'une partie de ses données. Ce choix dichotomique semble constituer une fondation pour l'élaboration d'un langage de programmation en symbiose avec la structure linéaire de la mémoire telle qu'on la trouve sur les ordinateurs comtemporains. Et cela aboutit presque naturellement à la conception d'un langage de programmation orientée objet.
L'objet concret (de bas niveau) représentant un booléen, c'est à dire de type `{0,1}`, est un bloc mémoire constitué d'un seul bit. Et on représente sa valeur dans le langage de programmation par le nombre `0` ou le nombre `1`.
L'objet concret représentant l'opérateur booléen de négation `"¬"` qui est de type `{0,1}"→"{0,1}`, est un programme rudimentaire qui s'applique à un booléen pour produire un booléen. Il occupe un bloc mémoire d'un seul tenant généralement un octet contenant son nom, pour un programme aussi rudimentaire. Et on le représente dans le langage de programmation par le symbole `"¬"`. De façon dense, il pourrait également tenir sur un seul bit car il n'y a que 2 opérateurs booléens unaires non dégénérés possibles `{"id","¬"}`.
L'objet concret représentant l'opérateur booléen de conjonction `"∧"` qui est de type `{0,1}"×"{0,1}"→"{0,1}`, est un programme rudimentaire qui s'applique à un couple de booléens pour produire un booléen. Il occupe un bloc mémoire d'un seul tenant généralement un octet contenant son nom, pour un programme aussi rudimentaire. Et on le représente dans le langage de programmation par le symbole `"∧"`. De façon dense, il pourrait également tenir sur 4 bits car il n'y a que 16 opérateurs booléens unaires possibles (dont 10 non-dégénérés).
Ce qu'il faut retenir, c'est qu'un programme est un opérateur, et qu'un programme rudimentaire tient dans un bloc mémoire d'un seul tenant, et peut être contenu dans une variable `m`. Dans le langage de programmation, l'expression `m(a,b)` désigne l'application du programme contenue par la variable `m` aux objets contenue dans `a` et `b` dans cet ordre. Si le type du programme est `A"×"B"→"C` alors le contenue de `a` doit être de type `A` et le contenue de `b` doit être de type `B`, sans quoi une erreur se produit lorsque la discordance de type apparait, soit lors d'une compilation ou soit lors de l'exécution. Puis les variables peuvent être remplacées par leur valeur faisant que l'expression `"∧"(0,1)` désigne l'application du programme `"∧"` aux objets booléens `0` et `1` dans cet ordre.
Le système permet de manipuler les programmes et leurs arguments qui sont des éléments, et permet l'appel `m(a,b)`. Mais le nombre d'arguments d'un programme est variable. On considère pour l'instant les programmes d'arité fixe `n` c'est à dire qui prennent `n` éléments en entrées et retourne un élément. Et on pose que les éléments évoqués ici ne sont pas des programmes.
L'aspect séquentielle de la mémoire va nous amener presque naturellement à introduire la curryfication et la logique polonaise comme comportement par défaut, un comportement qui a l'avantage de ne pas tronquer la quantité d'information apportée par une séquence de programmes et d'éléments. La composition est représenté simplement par une séquence, par exemple `m,a,b`, et les programmes prennent les arguments sur leur droites selon leur arité d'entrée. Si `m` est un programme de type `A"×"B"→"C` alors la composition `m,a` est autorisée et forme un programme de type `B"→"C`.
C'est ce que l'on appelle la curryfication le passage d'une foncion de `A"×"B"→"C` à une fonction de `A"→"(B"→"C)`. Ainsi, par exemple, nous avons :
`m,a,b` `=` `m(a,b)` `=` `m(a)(b)`
Et s'il y a un exès d'arguments alors la logique polonaise va empiler les arguments en trops et produire ainsi une séquence qui est de type séquence bariolée. Par exemple si `u` est de type `U` et si `v` est de type `V`, alors la composition `m,a,b,u,v` retournera la séquence `m(a,b),u,v` de type `C"×"U"×"V`.
Et s'il y a un exès de programmes, par exemple si `f` est un programme de type `A"×"B"→"C` et `g in D"×"E"→"A` alors la composition `f,g` est autorisée et retournera un programme de type `D"×"E"×"B"→"A`
En procédant ainsi, on unifie la concaténation avec l'appel de fonction. Toutes les compositions sont représentées par des séquences.
Et on remarquera que cette composition sous forme de séquence est associative, c'est à dire que l'on peut commencer le calcul à partir de n'importe quelle sous-séquence. L'associativité rend pertinente cette représentation de bas niveau des compositions, permettant une évaluation dans un ordre quelconque et donc aussi avec plusieurs processus d'évaluation en parallèles, pouvant réduire d'un logarithme la complexité du calcul.
La notation anglaise de la composition, `f(a,b)`, qui met en premier la fonction `f` puis à la suite les arguments entre parenthèse `(a,b)` n'est pas la plus intuitive du point de vue calculatoire. La notation française remet dans l'ordre chronologique de calcul. Elle met en premier les éléments, qu'elle entoure de parenthèse d'appel `(a,b)` pour indiquer que ces éléments sont capturés, puis accole la transformation `f` qui est une application s'appliquant sur ce couple d'éléments. La séquence se retrouve avec une composition inversée, `(a,b)f` :
`f in A"×"B"→"C`
`a in A`
`b in B`
`a,b,f = (a,b)f`
`(a,b)f in C`
Mais si la composition est partielle, pour que correspondent la succession des arguments dans la curryfication avec la succesion des types déclarées dans le type de la fonction, l'ordre des arguments n'est certes pas inversé mais l'ordre des arguments dans la currifycation est inversé, faisant que la séquence `b, f` produit une fonction de `A"→"C`, et que la séquence `a, f` engendre une discordance de type si le type `B` est distinct du type `A`. On constate alors que les deux notations ne désignent pas les mêmes les appels partiels.
Considérons par exemple la séquence en notation française `b,f,g,f,a,b,f` où `g in C"→"B`. Cette séquence produit `(".",((".",b)f)g)f,(a,b)f` de type `A"×"A"→"C"×"C` où le symbole point "." désigne les entrées de la fonction dans l'ordre d'apparition. La séquence contenant des appels partiels ne peut pas être traduite en notation anglaise. Par contre en comblant les appels partiels par les éléments `a,a`, la séquence `a,a,b,f,g,f,a,b,f` qui produit `(a,((a,b)f)g)f,(a,b)f` de type `C"×"C` se traduit en notation anglaise par `f(a,g(f(a,b))), f(a,b)` et par la séquence `f,a,g,f,a,b,f,a,b`.
La propriétée d'associativité reste valable même si l'on considère des programmes ayant des arités de sortie supérieur à `1`, ou même égale à zéro. Un programme d'arité de sortie zéro est caractérisé par une arité d'entrée `n` et ne fait que supprimer les `n` arguments suivants. Par exemple, considérons le programme `f= (A"×"A"×"A"→")` et les éléments `u,v,w` de type `A`. Nous avons `f,u,v,w,x = x`
Considérons maintenant les programmes d'arité d'entrée variable. On retient deux mécanismes pour définir l'arité d'entrée d'un programme d'arité d'entrée variable : Soit l'arité d'entrée est définie par le premier argument +1 et les suivants sont d'un type prédéfini unique, soit les arguments sont d'un type prédéfini unique et le dernier argument est marqué comme fin de liste des arguments. La propriétée d'associativité reste encore valable. Par exemple, considérons les programmes suivants :
`f in (underset(n)NN"×"A^n→"B)`
`g in (A"*"→"B)`
L'élément `"nil"` désigne un élément symbolique qui n'apporte aucun argument. Il est de tous les types et est marqué comme fin de liste. Considérons les éléments `a,b,c` de type `A`. Nous avons par exemple `f,3,a,f,3,b,c,g,a,b,"nil",c ` qui produit `f(a,f(b,c,g(a,b)),c)` qui est un élément de type `B`.
Considérons maintenant les programmes d'arité de sortie variable. On retient pour l'instant un seul mécanisme pour définir dans la séquence, l'arité de sortie d'un programme d'arité de sortie variable : L'arité de sortie est définie par le premier argument +1 ou le second argument + 2 si celui-ci est déjà utilisé pour spécifier l'arité d'entrée. Et les résultats sont d'un type prédéfini unique. La propriétée d'associativité reste encore valable. Par exemple, considérons les programmes suivants :
`u in (underset(n)NN"×"A→B^n)`
`v in (underset(n)NN"×"underset(m)NN"×"A^n→B^m)`
`w in (underset(n)NN"×"A"*"→B^n)`
Et considérons les éléments. Nous avons par exemple `w,a,v,2,2,b,c,nil ` qui produit un élément de type `B^2`. On traitera le cas du type `A"→"B"*"` plus tard avec l'étude des fonctions ne s'arrètant jamais de calculer. Mais même avec ce type de fonction, on maintient l'associativité des séquences.
On remarque que le symbole virgule "," utilisé dans les séquences sert pour séparer les éléments et les programmes, une fonctionnalité que l'on retrouvera dans le hardware d'une façon ou d'une autre.
Par contre, si un programme prend comme argument un programme, par exemple un programme `m` de type `(A"→"A)"×"A"→"A` c'est à dire qui prend un premier argument qui est un programme de type `A"→"A`, et un second argument qui est de type `A`, pour produire un élément de type `A`, alors l'associativité précédement évoquée n'est plus valable. En effet, avec `f` de type `A"→"A`, la composition `m,f,a,a` peut se résoudre en `m(f,a),a` ou en `m,f(a),a` et qui peut de plus engendrer une discordance de type si `A` distinct de `A"→"A`.
Et s'il n'y a plus d'associativité, la représentation pertinente redevient une structure d'arbre qu'est l'arbre d'appel. En conclusion, il apparait deux modes ; la composition de programmes s'appliquant à des éléments pour laquelle une représentation sous forme de séquence est mis en oeuvre avec la logique polonaise et la curryfication, et la composition de programmes s'appliquant à des éléments et des programmes pour laquelle une représentation sous forme d'arbre d'appel est mis en oeuvre.
Nous partons du langage et d'une conception trés mathématique du typage pas encore complètement bien défini pour définir une forme de hardware la mieux adaptée à cette forme de pensée. Un élément appartient à un type. Il est dit de ce type. Mais il peut appartenir à d'autres types.
Le type joue le rôle d'ensemble, mais il donne en plus des méthodes à ses éléments qui sont définies dans le type en question. Néanmoins les objets manipulés doivent avoir un type, choisie parmi les diffférents types que l'objet peut se revêtir sans changement. L'objet est typé. Et les changement de type sont définis, soit ils consistent à ne changer que l'étiquette, soit ce changement s'accompagne d'un calcul, d'un programme convertisseur de type qui traduit un morphisme.
Ainsi un object rudimentaire qui est contenue dans un bloc mémoire d'un seul tenant commence généralement par un pointeur vers son type. Cela constitue la première partie du bloc. Et cette partie va donner les règles de calcul pour déterminer la taille de la seconde partie. La seconde partie du bloc sont ses données.
Une variable qui est déclarée de type Elément, le type le plus général qui soit, est un pointeur vers un bloc. Une variable qui est déclaré d'un type plus précis d'élément est un pointeur qui peut pointer directement vers la seconde partie du bloc. Et dans ce cas il est dit "directe". On dévoile donc deux sortes de type, les types directes qui désignent des blocs de données et les types indirectes qui désignent des éléments de différents types, et donc qui pointent vers un bloc qui commence par un pointeur de type. (Remarquez que les opérateurs dont l'arité est désignée par leur premier argument ressemblent étrangement à ce genre de type.)
L'opérateur est un élément qui possède une méthode d'application, et qui se comporte ainsi comme une application, c'est à dire comme un programme. Le second type le plus important est ainsi celui d'Opérateur, et par négation celui de Non-opérateur qui représente les éléments qui ne sont pas opérateur, c'est à dire tel que leur type ne prévoit pas qu'il se comporte comme une application, faisant qu'il n'y a pas d'ambiguité dans une composition exprimée sous forme de séquence en logique polonaise, où il est effectivement nécessaire de distinguer les programmes que sont les opérateurs, des non-programmes que sont les non-opérateurs.
Le hardware présente la mémoire sous forme d'une liste d'octets adressables par leur numéro d'ordre mémorisé sur `1, 2, 4` ou `8` octets. C'est le principe de l'adressage indirecte indexé telle qu'on la trouve dans les ordinateurs contemporains. Ainsi, la mémoire dans son ensemble se présente comme un objet de type Array, un tableau d'octets. L'addresse d'un octet va occuper un certain nombre d'octets. Un octet permet d'adresser `256` octets, un mot de `16` bits permet d'adresser environ `65 "ko"` (kilo octets), un mot de `32` bits permet d'adresser environ `4 "Go"` (giga octets), un mot de `64` bits permet d'adresser environ `18 "Eo"` (exa octets).
On adopte la notation scientifique des grandeurs, qui les subdivisent selon les puissances de `1000`. Et il existe `8` classes habituellement utilisées : `k,M,G,T,P,E,Z,Y`, qui couvrent quasiment l'éventaille des grandeurs rencontrées dans l'univers (ou plutôt la moitier, les grandeurs microscopiques étant couvertes par les classes : `m,µ,n,p,f,a,z,y`).
Notation scientifique :
Valeur Symbole Préfixe
Un élément de type `E`, mémorisé dans un bloc de taille fixe, est dit mémorisé de manière totalement dense, si chaque configuration de bits possible du bloc mémoire désigne un éléments distinct de `E` et si tous les éléments de `E` sont bien désignés par une configuration de bits possible du bloc mémoire. Autrement dit, la donnée, qui désigne un élément parcourant `E`, est mémorisé de manière totalement dense, elle ne peut pas être compresser davantage, chaque élément de `E` est numéroté, et un des constructeurs de `E` doit être une bijection de `{0 ".." |E|"-"1}->E`. Où le cardinal de `E` se note `|E|`, et où la suite des entiers successif entre `a` et `b` compris se note `{a ".." b}`.
On peut perfectionner le mécanisme d'adressage indirecte indexé, pour rendre l'adresse totalement dense. Par exemple si on considère `2^n` blocs mémoires de `1000` octets chacun. L'adresse sous sa forme totalement dense pour désigner un bloc tient sur exactement `n` bits, c'est le numéro d'odre du bloc, et ce n'est plus le numéro d'ordre du premier octet du bloc. L'addressage passe alors par une phase de pré-calcul.
Puis on peut concevoir des strucures irrégulières composées de blocs de tailles diverses mais où le numéro d'ordre du bloc doit permettre de calculer sa taille et l'adresse de son premier octet.
Puis la donnée d'un bloc peut contenir de telles addresses que l'on appelle pointeurs, faisant que l'objet dans son ensemble représente un graphe composé de sommet ordonnée où chaque sommet possède des arêtes partantes ordonnées. Le qualificatif ordonné précise que l'on a numéroté chaque élément. (Notez qu'un ensemble d'éléments ordonnées, c'est-à-dire dit formellement, un ensemble muni d'un ordre total, un tel ensemble constitue une liste d'éléments.)
Ces structures de graphe sur lesquelles vont agir des programmes, vont servir d'élément central pour concevoir des langages de programmation évolués tout en restant proche de la machine, reliant ainsi les concepts du hardware avec celles du software.
La taille d'une adresse de bloc dépend du nombre maximal de blocs envisagé. Elle est égale à `log_2(N)` bits où `N` est le nombre maximal de blocs. Pour former d'une donnée totalement dense, le nombre de blocs successifs doit être une puissance de `2`, afin que l'adresse d'un bloc utilise toute les configurations possibles de bits dans l'espace mémoire qui lui est réservée.
En explorant les types de la forme `E^p"→"E^k` et en n'utilisant que des adresses totalement dense, il apparait une succession d'objects totalement denses.
D'une manière générale, un objet de type `E^p"→"E^k` où `|E|=2^n`, comprend `2^(pn)` blocs. Chaque bloc est constitué de `k` pointeurs. Chaque pointeur occupe `n` bits. Il est de taille de `kn2^(pn) ` bits. Il représente `k` lois de composition `p`-aire interne dans un ensemble de `2^n` éléments.
Une autre façon de calculer le nombre de bits nécessaire pour mémoriser de façon dense une application de `E^p"→"E^k` consiste à calcule la cardinalité de `E^p"→"E^k` et à en prendre le logarithme en base `2` :
`|E^p"→"E^k| = (|E|^k)^(|E|^p) = (2^(kn))^(2^(pn)) = 2^(kn2^(pn))`
`log_2(|E^p"→"E^k|) = log_2(2^(kn2^(pn))) = kn2^(pn)`
Remarquez qu'une loi de composition `1`-aire interne dans `E` est une application dans `E`, c'est-à-dire un graphe où tous les sommets ont exactement une arête partante.
Les structures de données contenant des liens internes que sont ces pointeurs, transportent une quantité d'informations dites introspectives, qui peut se refléter comme deux miroir en vis-à-vis jusqu'à l'infini. L'objet acquère de par ces liens sur lui-même et cette reflexivité, une capacité d'organisation qui lui est propre, et qui, utilisé d'une certaine façon, permet de réduire l'entropie. Cela s'appelle de la néguentropie.
On remarque qu'il existe une bijection canonique entre `{0,1,2,3}` et `{0,1}"×"{0,1}` et qu'il y a une égalité entre les ensembles `{0,1}"×"{0,1}"×"..."×"{0,1}` et `{0,1}^n` et ainsi qu'entre les ensembles `{0,1}^x"×"{0,1}^y` et `{0,1}^(x+y)`. On remarque qu'il existe une bijection canonique entre `{0 ".." 2^n"-"1}` et `{0,1}^n`.
Un nombre `k` d'applications forment un graphe où chaque sommet est d'arité `k` c'est-à-dire possèdent `k` arêtes partantes. Le choix de `k` applications sur un ensemble de `2^n` éléments, se mémorise de manière totalement dense sur `2^n` bits et constitue un objet de type `{0,1}^n->{0,1}^(kn)`.
Ces objet sont susceptibles de contenir une grande quantité d'information introspective constituée par les arêtes du graphe formant des boucles, capables de mettre en oeuvre un processus récurcif, et d'itérer un shémat d'organisation, que l'on peut mesurer sous forme de néguentropie.
Puis, rien n'empêche de concevoir des structures plus irrégulières telles que par exemple celles composées de deux tailles de bloc, les blocs numéro paire contenant `a` pointeurs et les blocs de numéro impaire contenant `b` pointeurs. Cela représente un graphe de sommets ordonnés, composé d'une moitié de sommets d'arité `a` (ceux numérotés pairs) et d'une moitier de sommets d'arité `b` (ceux numérotés impraires).
On peut s'inspirer de cette remarque informatique pour concevoir des structures mathématiques plus irrégulières et donc plus riches que les seules fondamentales..., ouvrant l'accès à une flore exotique, débordantes de variétés. De quoi remplir un herbier gigantesque.
Mais commençons par explorer les structures fondamentales classique :
Posons `E = {0,1,2,...,2^n"-"1}`. Le cardinal de `E` est `|E|=2^n`. Notez qu'une application dans `E` est une application de `E"→"E`, et que `k` applications dans `E` constitue une application de `E"→"E^k`.
Considérons un tableau à une dimension de `2^n` blocs. Où chaque bloc est composé de `n` bits. Ce tableau représente de manière totalement dense, une application portant sur `2^n` éléments ordonnés, c'est-à-dire par exemple une application dans `E`, autrement dit, un graphe où les sommets sont les éléments de `E` et sont ordonnées, et où sur chaque sommet il y a exactement une arête partante. Puis, si chaque bloc est composé de `kn` bits. Alors ce tableau représente de manière totalement dense, `k` applications dans `E`. autrement dit, un graphe où les sommets sont les éléments de `E` et sont ordonnées, et où sur chaque sommet il y a exactement `k` arêtes partantes ordonnées.
Considérons maintenant un tableau à deux dimensions de `2^(2n)` blocs. Où chaque bloc est composé de `n` bits. Ce tableau représente de manière totalement dense une loi de composition binaire interne portant sur `2^n` éléments ordonnés, c'est-à-dire par exemple une loi de composition binaire interne dans `E`. Chaque bloc contient un entier qui représente un élément de `E`. Puis, si chaque bloc est composé de `kn` bits. Alors ce tableau représente de manière totalement dense, `k` lois de compositions binaires internes dans `E`.
Considérons maintenant un tableau à `p` dimensions de `2^(pn)` blocs. Où chaque bloc est composé de `n` bits. Ce tableau représente de manière totalement dense une loi de composition `p`-aire interne portant sur `2^n` éléments ordonnés, c'est-à-dire par exemple une loi de composition `p`-aire interne dans `E`. Chaque bloc contient un entier qui représente un élément de `E`. Puis, si chaque bloc est composé de `kn` bits. Alors ce tableau représente de manière totalement dense, `k` lois de compositions `p`-aire internes dans `E`. Notez qu'une loi de composition `p`-aire interne dans `E` est une application de `E^p"→"E`, et que `k` lois de composition `p`-aire internes dans `E` constituent une application de `E^p"→"E^k`.
Voici la taille des éléments totalement dense de type de la forme `E^p"→"E^k` :
Nombre de bits du pointeur |
|E| |
Taille d'un élément de `E"→"E` |
Taille d'un élément de `E^2→"E` |
Taille d'un élément de `E^3→"E` |
Taille d'un élément de `E^4→"E` |
Taille d'un élément de `E^5→"E` |
Taille d'un élément de `E^6→"E` |
Taille d'un élément de `E^7→"E` |
Taille d'un élément de `E^8→"E` |
n |
`2^n` |
`n2^n "b"` |
`n2^(2n) "b"` |
`n2^(3n) "b"` |
`n2^(4n) "b"` |
`n2^(5n) "b"` |
`n2^(6n) "b"` |
`n2^(7n) "b"` |
`n2^(8n) "b"` |
`2`
|
`4`
|
`1 "o"` |
`4 "o"` |
`16 "o"` |
`64 "o"` |
`256 "o"` |
`1 "ko"` |
`4 "ko"` |
`16 "ko"` |
`4`
|
`16`
|
`8 "o"` |
`128 "o"` |
`2 "ko"` |
`33 "ko"` |
`524 "ko"` |
`8 "Mo"` |
`134 "Mo"` |
`2 "Go"` |
`6`
|
`64`
|
`48 "o"` |
`3 "ko"` |
`197 "ko"` |
`13 "Mo"` |
`805 "Mo"` |
`52 "Go"` |
`3 "To"` |
`211 "To"` |
`8`
|
`256`
|
`256 "o"` |
`66 "ko"` |
`17 "Mo"` |
`4 "Go"` |
`1 "To"` |
`281 "To"` |
`72 "Po"` |
`18 "Eo"` |
`10`
|
`1 "k"`
|
`1 "ko"` |
`1 "Mo"` |
`1 "Go"` |
`1 "To"` |
`1 "Po"` |
`1 "Eo"` |
`1 "Zo"` |
`1 "Yo"` |
`12`
|
`4 "k"`
|
`6 "ko"` |
`25 "Mo"` |
`103 "Go"` |
`422 "To"` |
`2 "Eo"` |
`7 "Zo"` |
`29 "Yo"` |
|
`14`
|
`16 "k"`
|
`29 "ko"` |
`470 "Mo"` |
`8 "To"` |
`126 "Po"` |
`2 "Zo"` |
`24 "Yo"` |
||
`16`
|
`66 "k"`
|
`131 "ko"` |
`9 "Mo"` |
`563 "To"` |
`37 "Eo"` |
||||
`18`
|
`262 "k"`
|
`590 "ko"` |
`155 "Go"` |
`41 "Po"` |
`11 "Zo"` |
||||
`20`
|
`1 "M"`
|
`3 "Mo"` |
`3 "To"` |
`3 "Eo"` |
`3 "Yo"` |
||||
`22`
|
`4 "M"`
|
`12 "Mo"` |
`48 "To"` |
`203 "Eo"` |
`851 "Yo"` |
||||
`24` |
`17 "M"` |
`50 "M"` |
`844 "To"` |
`14 "Zo"` |
`2 "Yo"` |
||||
`26` |
`67 "M"` |
`218 "M"` |
`15 "Po"` |
`982 "Zo"` |
|||||
`28` |
`268 "M"` |
`940 "M"` |
`252 "Po"` |
`68 "Yo"` |
|||||
`30` |
`1 "G"` |
`4 "Go"` |
`4 "Eo"` |
||||||
`32` |
`4 "G"` |
`17 "Go"` |
`74 "Eo"` |
||||||
`34` |
`17 "G"` |
`73 "Go"` |
`1 "Zo"` |
||||||
`36` |
`69 "G"` |
`309 "Go"` |
`21 "Zo"` |
||||||
`38` |
`275 "G"` |
`1 "To"` |
`359 "Zo"` |
||||||
`40` |
`1 "T"` |
`5 "To"` |
`6 "Yo"` |
||||||
`42` |
`4 "G"` |
`23 "To"` |
`102 "Yo"` |
||||||
`44` |
`18 "G"` |
`97 "To"` |
|||||||
`46` |
`70 "G"` |
`405 "To"` |
Le hardware va nous proposer d'autres structures davantage irrégulières, et on va énumérer les premières techniques permettant de les construire.
La première technique consiste à concevoir différents types de pointeur désignant des éléments de plus petites structures.
La seconde technique consiste à concevoir des pointeurs dits mixtes, en réservant `v` valeurs d'adresse pour désigner des constantes de genre `"nil"`. Ces pointeurs totalement denses désignent `2^n"-"v` éléments ou bien désignent `v` constantes de genre `"nil"`.
Puis la mixitude est généralisée en associant à chaque valeur d'adresse, le pointage d'un élément de type distinct spécifique, ou une constante.
Notez que le programme mettant en oeuvre ce procédé étant commun à tous les objets du type en construction, se situe dans le type en question et non dans l'objet, ce qui permet de maintenir la cohérence du concept de totale densité des objects.
Cela va nous permettre de définir la somme de types, ou plus exactement l'union disjointe de types, qui concrétise ce procédé d'une façon générale.