Le C est un langage de programmation impératif, proche du langage machine, inventé par Dennis Ritchie en 1972. Ce langage révolutionna l'informatique. Le système d'exploitation Linux est programmé en C.
Dennis MacAlistair Ritchie (né en 1941 à Bronxville dans l'Etat de NewYork, décédé en 2011 à Berkeley Heights dans le New Jersey) est un des pionniers de l'informatique moderne, inventeur du langage C et co-développeur de Unix. Il est parfois désigné par dmr, son adresse e-mail aux Laboratoires Bell.
Le langage C est un langage de programmation modulaire. Le module est la brique élémentaire de programmation. Les modules sont liés entre eux lors de la compilation par la mise en partage d'appels de fonctions, de variables et de structures. Les modules sont compilées à l'aide du compilateur gcc.
Pour pleinement exploiter l'efficience et la puissance mésentropique de la programmation modulaire, il faut intégrer l'outils gcc à l'intérieur du programme, un programme capable d'écrire un programme, de le compiler et de l'exécuter, ce qui permet d'implémenter effcacement l'emboitement des structures mathématiques et in fine leur construction, en utilisant l'aspect modulaire du langage de programmation. Chaque structure est définie par une succession de modules emboitées. La structure se construit en compilant ses modules et en renommant les types à chaque emboitement pour faire la liaison. Voilà par où commence le paradigme.
Pour illustrer notre propos, nous mettons en oeuvre un exemple, le calcul du pgcd selon l'algorithme d'Euclide sur un anneau euclidien.
Un premier module mod1.c pose un anneau euclidien avec quelques types et opérations.
Pour les structures de taille trés grande ou infinie, et pour éviter les objects de taille variables, on peut utiliser le concepte de structure tronquée. On ne regarde qu'une partie de la strructure. La structure tronquée comprend un noyau et une partie adhérente plus vaste. Le noyaux regroupe un ensemble pertinent d'éléments interopérants fortements entre-eux. La partie adhérente comprend le noyaux et les éléments obtenus par une opérations sur les éléments du noyaux. La structure tronquée ne permet de représenter que les seuls éléments adhérents de l'anneau au travers une structure de taille bornée.
Dans notre exemple, l'anneau en question est l'anneau des entiers tronqué. Le noyaux est représenté par {0, 1, 2, 3..., 215-1}. Un élément du noyaux est mémorisable dans une variable de type short sans utiliser le bit de signe. La partie adhérente est représentée par {0, 1, 2, 3..., 231-1}. Un élément adhérent est mémorisable dans une variable de type int sans utiliser le bit de signe.
Dans le cas d'une structure tronquée, l'opération Rand( ) retourne un élément du noyaux au hasard, tandis que les autres opérations opérant sur des éléments du noyaux, retourne des éléments adhérents.
Le module mod1.c comprend une entête mod1.h et un corps mod1.c. Le corps a besoin de l'entête, d'où l'instruction #include "mod1.h" établissant ce lien (cela inclue l'entête dans le corps). La fonction printf(...) nécessite la librairie stdio, d'où l'instruction #include <stdio.h>
typedef int Element;
inline void Aff(Element);
inline Element Mult(Element, Element);
inline Element Mod(Element, Element);
inline Element Rand( );
#include "mod1.h"
#include <stdio.h>inline void Aff(Element a) {printf("%d \n",a);}
inline Element Mult(Element a, Element b) {return a*b;}
inline Mod(Element a, Element b) {return a%b;}
inline Rand( ) {return rand( )>>16;}
Un second module mod2.c compléte cet anneau euclidien avec une opération :
Le module mod2.c n'a besoin que de la seul entête mod1.h qui lui transmet le prototype de la fonction Mod(.,.) ainsi que le type Element, d'où l'unique lien qu'est l'instruction #include "mod1.h". Le corps a toujours besoin de l'entête, d'où l'instruction #include "mod2.h".
#include "mod1.h"
Element Pgcd(Element, Element);
#include "mod2.h" Element Pgcd(Element a, Element b) {
Element p;
for(;;) {
p = Mod(b,a);
if (p == 0) return a; else{b=a; a=p;}
}
}
Le programme principal main.c a besoin de l'entête mod2.h qui lui transmet le prototype de la fonction Pgcd(.,.), et de l'entête stdio.h qui lui transmet le prototype de la fonction printf(...). Le programme principal main.c teste si l'opération Pgcd(.,.) satisfait la propriété Pgcd(Mult(z,x), Mult(z,y)) = Mult(z, Pgcd(x,y)) quelque soit x, y, z appartenant à la structure. Pour cela, il teste une dizaine de fois avec des valeurs prises au hasard dans le noyaux. Puis la fonction main retourne le code 0 de non erreur si le test réussie ou le code -1 d'erreur si le teste échoue.
#include "mod2.h"
#include <stdio.h>
int main( ) {
int V=0;
int i;
for (i=0;i<10;i++){
Element x = Rand( );
Element y = Rand( );
Element z = Rand( );
if (Pgcd(Mult(x,z),Mult(y,z)) != Mult(z,Pgcd(x,y))) V=-1;
}
if (V==0) printf("Pgcd : OK"); else printf("Pgcd : Erreur");
return V;
}
Et si l'on souhaite programmer le calcul du pgcd sur un autre anneau euclidien, alors seul le premier module devra être changer.
La commande de compilation des modules pris séparements est :
gcc -c mod1.c
gcc -c mod2.c
gcc -c main.c
L'option -c empêche le linkage qui ne peut pas être fait séparemment. Cela crée trois fichiers objects mod1.o, mod2.o, main.o. Puis la commande de linkage est :
gcc main.o mod1.o mod2.o
Cela crée l'exécutable a.out
Pour transmettre aux utilisateurs finaux, une plus grande capacitées d'adaptabilité et de développement, on leur donne le moyen de démonter le programme par le haut en plusieurs pièces exécutables et de les réassembler autrement, pour faire autre chose. Cela consiste à donner aux exécutables binaires les qualitées de la programmation modulaire décrite par Bertrand Meyer à quelques modifications près :
La décomposabilité : La division du logiciel par le haut en plusieurs pièces éxécutables.
La composabilité : L'assemblage des différentes pièces éxécutables à l'aide d'un langage.
La compréhensibilité : Chaque pièce décrit de manière compréhensible ce qu'elle fait.
L'auto-preuve : Chaque pièce possède un mecanisme d'auto-preuve statistique.
L'assemblage des pièces exécutables se fait selon un langage interprété qui sers de ciment. Cela revient à créer une structure possèdant ce langage, mais à la différence de la construction des structures mathématique, faite par le bas en présentant des générateurs rudimentaires, celle-ci est faite par le haut en subdivisant le logiciel existant en pusieurs grosse pièces exécutables, jouant le rôle d'opérateurs élémentaires.
Un module mod1.c, une fois compilés avec l'instructiuon gcc -c mod1.c produit le fichier object mod1.o. Ce fichier n'est pas encore un exécutable car le linkage n'a pas été effectué. Le linkage, qui a lieu après la compilaton, construit les liens entre les modules que sont les structures, variables et appels de fonctions communs.
La pièce exécutable possède des entrés-sorties et des segments de mémoires partagées.
Nous ne souhaitons pas donner l'ensemble de la charge du linkage à l'utilisateur, mais seulement lui donner les moyens d'agir sur des entités exécutables plus larges que les modules initiaux, appelées pièces exécutables, et dont on classifie le comportement des entrés-sorties et des segments de mémoires partagées.
L'utilisateur final pourra combiner les pièces exécutables à sa guise en aiguillant leurs entrés-sorties et en permuttant leurs segments de mémoires partagés.
On sépare les entré-sortie en deux genres.
Si le langage qui sers de ciment est un shell tel le shell Bash, alors les entrés-sorties sont assez rudimentaires. La sortie comprennd un code entier sur 32 bits contenant le code erreur, ainsi que les deux unités standards de sortie stdout et stderr qui peuvent être redirigées sur un fichier ou sur l'écran. L'entré comprend une chaine de caractères passé en argument, ainsi que l'unité standart stdin qui peut être redirigée sur un fichier.
On se libère de ces choix limitatifs en redéfinissant un nouveau shell. On veut pouvoir manipuler certains objets que les pièces exécutables manipulent. Un tel objet possède un type définie dans la pièce en question. Il faut donc que lors du linkage de ces pièces, les types des objects que nous voulons manipuler à l'exterieur soient partagés avec le shell. Le shell encapsulera l'object dans un object shell un peu plus grand, comprenant son type.
Le principe d'un langage fonctionnel consiste à enlever tout les effets de bord. Mais, ne pouvant se restreindre à cette limitation expressive, on offre un cadre stricte aux effets de bords appelés modifications physiques et que nous appliquons à la pièce exécutable. La nature fonctionnelle de la pièce exécutable se présente alors non plus comme une fonction pure sans effet de bord, mais comme une transformation d'un système où les effets de bords sont justement cantonnés à la transformation du système. Le système est mémorisé à coté du processus, que constitue l'exécution de la pièce, dans un ou plusieurs segments de mémoire partagé chacun idendifié par une clef unique.
Le segment partagé est un object manipulé par les pièces exécutables qui s'y réfèrent. Il constitue une mémoire qui perdure après l'exécution des pièces jusqu'à sa suppression mise en oeuvre également par une pièce exécutable. La pièce qui crée le segment partagé retourne la clef du segment. Les pièces agissant sur un segment recoivent en argument d'entré, la clef qui désigne le segment à utiliser.
L'accès au disque dur est lent et ne peut égaler la vitesse de lecture/écriture de la mémoire vive du système. C'est pourquoi on utilise des fichiers mémorisés en mémoire vive pour accumuler les résultats et les transmettre rapidement à un éventuel autre programme. Si la transmission doit se faire directement d'un processus en cours d'éxecution à un autre, alors on utilisera plustôt un tube en redirigeant la sortie du premier processus sur l'entré du second.
On crée un répertoire en mémoire vive comme suit, en étant root. C'est un système de fichiers volatiles temporaire (type tmpfs) que l'on monte généralement dans
mkdir /mnt/ram
mount -t tmpfs -o size=100M none /mnt/ram
et on rend l'utilisateur propriétaire du repertoire /mnt/ram :
chown utilisateur /mnt/ram
On y copie les sources mod1.c, mod1.h, mod2.c, mod2.h, main.c et on positionne le répertoire courant sur /mnt/ram. Ainsi la commande gcc main.c mod1.c mod2.c va crée le fichier a.out dans /mnt/ram sans faire le moindre accès aux disques durs.
Pour démonter le volume ram, assurez-vous que le volume n’est pas utilisé, puis, en étant root, tapez ceci : umount /mnt/ram
Il n'y a pas de méthode directe pour obtenir une clef vierge. On pose une clef k au hasard
#include <eerno.h>
#include <sys/ipc.h>
#include <sys/shm.h>
k = (key_t) rand( );
La fonction shmget(k, T, IPC_CREAT|IPC_EXCL|SHM_NORESERVE|0666) renvoie -1 si elle échoue, sinon renvoie l'identifiant i du segment nouvellement créé de taille T octects. (errno == EEXIST) si existe déjà. On réessaye alors avec une autre valeur de clef k.
La fonction shmget(k, T, 0666) renvoie -1 si elle échoue, sinon renvoie l'identifiant i du segment désigné par la clé k et qui doit être de taille T.
La fonction shmat(i, NULL, 0) renvoie -1 si elle échoue, sinon renvoie l'adresse du segment désigné par l'identifiant i.
La fonction shmctl(i, IPC_RMID, NULL) renvoie -1 si elle échoue, sinon renvoie 0. Le segment d'identifiant i sera alors supprimé lorsque plus aucun processus ne le partagera.
On utilise le processeur arithmetique capable de multiplier deux entiers unsigned long (type uint32_t) en un entier unsigned long long (type uint64_t), et capable de multiplier deux entiers long (type int32_t) en un entier long long (type int64_t). Reste à définire la taille variable de l'entier. Pour cela on réserve un premier mot de 32 bits (type uint32_t) qui contiendra le nombre de mots de l'entier.
mod1.h |
mod1.c |
typedef unsigned long*
BIGINT;
|
#include "mod1.h" void Aff(Element a){ {printf("%d \n",a);} |
---- 9 février 2014 ----
Il existe des types simples, copiées en valeur, qui correspondent à des blocs contigüs de mémoire de taille fixe, et que nous appellons modons. Et il existe des types un peu plus complexes, de taille variable mais toujours mono bloc, qui sont désignées par un pointeur et que nous appellons varons.
6 types de base sont prédisposés par la machine. Ce sont les types int8_t, int16_t, int32_t et leur homologues non signés uint8_t, uint16_t, uint32_t déclarés dans le fichier entête stdint.h. Ils correspondent aux structures des entiers modulo 28, 216, 232 avec une représentation signé ou non-signé. Ils correspondent aussi aux structures des sous-ensembles de {0,1,2,3...,7}, {0,1,2,3...,15}, {0,1,2,3...,31}. Ils correspondent aussi aux structures des vecteurs de 8, 16, 32 variables booléennes, et Ils correspondent aussi aux structures (Z/2Z)8, (Z/2Z)16, (Z/2Z)32. Remarquez la pluralité des définitions possibles pour une même structure !.
Pour des raisons propres à la machine, Il est préférable que les tailles des blocs mémoires soit égale à un nombre entier de mots c'est à dire égale à un nombre paire d'octets. On généralise donc ces 6 types de base en un type représentant la structure (Z/2Z)16*k ou Z/(216*k)Z, puis d'une manière plus générale, on définira un type représentant la structure Z/nZ ayant des méthodes analogues.
Pour utiliser les mêmes noms de méthode dans ces différentes structures similaires, il faut introduire une couche d'abstraction, une couche logiciel où se trouve les prototypes des méthodes avec des noms de type renommables à volontés et qui seront reliées, lors de la compilation, à un noyaux implémentant ces méthodes pour les différents types similaires.
modon et varon
à revoirint x Elem x
Elem * x = CreerElem()Crée un Elem initialement à zéro. x = y Elem x = y
Elem Assigne(x,y)Copie la valeur de y dans x. (int) y Elem (Elem) y
ElemConertToElem(y)Convertie y en Elem. PUT1(A,i) void Put1(A,i) A[i]=1 PUT0(A,i) void Put0(A,i) A[i]=0 PUTX(A,i) void PutX(A,i) A[i]=¬A[i] PUT(A,i,v) void Put(A,i,v) si v==0 alors A[i]=0
si v==1 alors A[i]=1
si v==-1 alors A[i]=¬A[i]GET(A,i) Bool Get(A,i) A[i] NEXT(A,i) Int Next(A,i) Le plus petit entier plus grand ou égale à i tel que A [i]==1 NEXT(A,i) Entier Next(A,i) Le plus petit entier plus grand ou égale à i tel que A [i]==1 A = ~B Elem A = Non(B) Complément de B A = B|C Elem A = Ou(B,C) B union C A |= B Ou_(A,B) A = A union C A = B&C A = Et(B,C) B inter C A &= B Et_(A,B) A = A inter B A = B^C A = W(B,C) B différence symétrique C A ^= B W_(A,B) A = A différence symétrique B A==B A==B
Egal(A,B)Teste si A égale B en valeur. INCLUS(A,B) Inclus(A,B) Teste si A inclus dans B A=Rand() A=Rand() Calcul un Elem au hasard. A=Rand(B,C) A=Rand(B,C) Calcul un Elem au hasard compris entre B et C compris. A = B<<i
A = ShiftL(B,i) Shift gauche (multiplie par 2). A<<=i A = ShiftL(A,i) Shift gauche (multiplie par 2), modification physique. A= B>>i A = ShiftR(B,i) Shift droit (divise par 2). A=>>i A = ShiftR(A,i) Shift droit (divise par 2), modification physique. AffEns(A) AffEns(A) Affiche A sous format d'ensemble. Ex : {0,1,2,9,15,31}
AffU10(A) AffInt(A) Affiche A non signé en base 10. Ex : 123564512 AffU2(A) Aff2(A) Affiche A non signé en base 2. Ex : 1101001010 Aff10(A) AffInt(A) Affiche A signé en base 10. Ex : - 1235 Aff2(A) Aff2(A) Affiche A signé en base 2. Ex : - 1101001 AffB(A) AffB(A) Affiche A bit à bit. Ex : 0000101100 A = LitEns() A = LitEns() Lit sous format d'ensemble. Ex : {0,1,2,9,15,31} A = LitU10() A = Lit10() Lit en base 10. Ex : 123564512 A = LitU2() A = Lit2() Lit en base 2. Ex : 001101001010 A = Lit10() A = Lit10() Affiche A signé en base 10. Ex : - 1235 Aff2(A) Aff2(A) Affiche A signé en base 2. Ex : - 1101001 AffB(A) AffB(A) Affiche A bit à bit. Ex : 0000101100 A = B+C A = plus(B,C) Addition dans Z/28Z, Z/216Z, Z/232Z ou Z/kZ A = B-C A = moins(B,C) Soustraction dans Z/kZ A = B*C A = mult(B,C) Multiplication dans Z/kZ A = B/C A = divE(B,C) Division entière (signé ! ou non signé ! selon le type) A = B%C A = mod(B,C) Modulo (signé ! ou non signé ! selon le type) div_t(B,C) div_t(B,C) Retourne une paire .quot pour le quotient et .rem pour le modulo. A = div(B,C) A = div(B,C) Division dans Z/kZ A < B PlusPetit(A,B) Teste si A plus petit que B (signé ! ou non signé ! selon le type) A <= B PlusPetitOuEgal(A,B) Teste si A plus petit ou égal à B (signé ! ou non signé ! selon le type) Un Un L'unité de l'anneau (Un=1) Zero Zero L'élément neutre de l'anneau (Zero=0)
Le modon est manipulé par une variable contenant directement un bloc de taille fixe. Le varon est manipulé par une variable contenant un pointeur pointant vers un bloc de taille variable. Lorsque le modon devient de taille importante, il peut être plus judicieux d'utiliser un varon.
Si nous voulons optimiser efficacement la gestion de la mémoire, il nous faut réserver des lands pour chaque taille de blocs. Aussi, on ne doit pas envisager toutes les tailles. Une bonne approche consiste à ne considérer comme seul taille possible un nombre de mots égal à une puissances de 2. Les types considérés ont donc comme taille un nombre de mots égal à un puissance de 2. Les structures (Z/2Z)(2(k+4)) sont donc en quelque sorte les structures de base proches de la machine.
Le qualificatif signé ou non signé correspond à un plongement de Z/2*nZ dans l'intervalle entier respectivement [-n, +n-1] ou [0, 2*n-1], et correspond à un plongement de Z/(2*n+1)Z dans l'intervalle entier respectivement [-n, +n] ou [0, 2*n]. Sur cet intervalle, il est définie l'opération de division euclidienne qui se superpose à l'opération de division programmées de façon plus générale dans la structure des entiers relatifs.
D'un point de vue mathématique, nous pourrions partir des booleans Z/2Z. Mais du point de vue de la machine, il existe une structure plus efficace en terme de temps de calcul et d'espace mémoire, qui est (Z/2Z)16 dont les éléments peuvent être mémorisés dans un mot mémoire c'est à dire dans deux octets consécutifs. Cette structure prédisposées par la machine peut servir de structure de base pour construir les autres structures.
Mais se serait une erreur de vouloir établir les fondements à partir de caractéristiques machines. Ces caractéristiques interviendront certe, mais après la construction abstraite, pour optimiser la construction concrète lors de la compilation.
C'est pourquoi on reprend notre énumération qui se veut exhaustive, des premières structures de petites tailles. On va énumèrer tous les objects possibles.
L'étude des structures finies a ceci de particulier, que tout étant fini, il est possible d'avoir une vision exhaustive de toutes les constructions possibles, de tous les objects possibles en dessous ou égale à une taille de N éléments. C'est cette vision cartésienne qui nous ramène à une problématique purement combinatoire.
Et on commence par la conception la plus figée et la plus détaillée de toutes. On prédispose N éléments numérotés de 0 à N-1, qui constitue notre horizon Ω, et on s'intéresse aux objects composées d'opérateurs opérant sur cet ensemble d'éléments Ω. Un tel objet est définie de façon brute, totalement instanciée, sans factoriser l'information de quelque façon, ni en laissant la moindre inconnue s'insinuer.
On énumère les opérateurs de l'object faisant que l'object est une liste d'opérateurs totalement définis et opérant sur Ω.
On nomme les opérateurs par leur définition complète.
Deux objects sont identiques si et seulement si ils ont la même liste d'opérateurs.
Par exemple en posant l'univers Ω={0,1}, l'objet (0,(1,0),1,((0,0),(0,1))) qui correspond à l'objet (0, ¬(.), 1, et(.,.)) est différent de l'objet (0, 1, ¬(.), et(.,.)) puisque les opérateurs ne sont pas dans le même ordre.
Se pose alors une question sur la construction des objects. N'y aurait-il pas un procédé de construction plus rudimentaire, sous-jacent, à la base des constructions précédement décrites ?. L'object est une liste d'opérateurs totalement définis, c'est à dire une liste de tableaux avec k dimensions de taille n, soit des tableaux de taille nk, d'éléments appartenant à Ω. Un tableau de dimension zéro est un élément désigné par un entier de 0 à N-1. (Un autre système plus simple pourrait être envisagé, voir système listes et entiers.)
Le premier univers non trivial possède deux éléments Ω={0,1}, il existe exactement 2 opérateurs zéro-air {0,1}. il existe exactement 4 opérations unaires internes possibles {0, id, ¬, 1}, et il existe exactement 16 opérations binaires internes possibles {0, et, ¬=>, g, ¬<=, d, w, ou, ¬ou, <=>, ¬d, <=, ¬g, =>, ¬et, 1}, et il existe 256 opérations ternaires...., Voir Les opérateurs booléens
Le codage liste big-endian d'un opérateur binaire × est ((0×0), (0×1), (1×0), (1×1)).
Le codage liste big-endian d'un opérateur ternaire f est (f(0,0,0), f(0,0,1), f(0,1,0), f(0,1,1), f(1,0,0), f(1,0,1), f(1,1,0), f(1,1,1)).
Le codage entier big-endian d'un opérateur est le codage entier big-endian de son codage liste big-endian.
Le codage des opérateurs opérant sur Ω, ainsi défini, est totalement dense. C'est à dire que le codage d'un opérateur k-air est une bijection entre les n(nk) opérateurs d'arité k possibles et les entiers de 0 à n(nk)-1.
Dans un univers à deux éléments, une constantes, qui est un opérateur d'arité zéro, est définie dans un 1 bit. Un opérateur unaire est défini dans 2 bits. Un opérateur binaire est défini dans 4 bits. Un opérateur k-air est défini dans une mémoire de taille 2k bits.
Le raisonnement se généralise pour les univers à N éléments. Les éléments sont numérotés dans l'ordre à partir de zéro. Une constantes (opérateur d'arité zéro) est définie dans log(N) bits. Le logarithme est en base 2. Un opérateur unaire est défini dans N*log(N) bits. Un opérateur binaire est défini dans N2 * log(N) bits. Un opérateur k-air est défini dans une mémoire de taille Nk * log(N) bits. Voir Probabilité et quantité d'information (volume 1)
L'application d'un opérateur k-air à k éléments consiste en un adressage indirecte qu'est l'accès au résultat contenue dans le tableau de l'opérateur k-air. En terme d'effectivité on pourrait dire que la complexité de cette opération vaut 1 cycle de calcul. Mais en terme d'espace mémoire utilisé on pourrait dire que la complexité vaut la taille de l'opérateur en question c'est à dire nk * log(n) bits.
Nous voulons aussi avoir une codification complétement dense des objects. Nous avons posé une borne N sur le nombre d'éléments dans notre univers, il nous faut également poser une borne n sur l'arité des opérateurs concidérés. L'objet est une suite d'opérateurs, et l'opérateur peut être codé en deux parties, une première partie qui précise sont arité k < A et qui tient sur log(A) bits, et une seconde partie qui contient le tableau de Nk éléments et qui tient sur Nk * log(N) bits. On obtient ainsi un codage trés dense, mais pas totalement dense.
Une autre conception de l'objet consiste à le décomposer en une liste ordonnée des listes des opérateurs d'arité k, pour k variant de 0 à A-1. Chaque liste d'opérateus d'arité k est codé en une succession de nk blocs de Nk * log(N) bits. Et la liste des entiers (n0,n1,n2...,nA-1) constitue la signature de l'objet.
Nous avons décrit ici les bases du langage de données et du langage de programmation, ce qui nous a permis de construire nos objets cartésiens. Mais il nous manque le langage de propriété pour parfaire la trilogie. Voir Les 3 concepts (Donnée, Programme, Propriété)
On choisie comme langage de propriété, celui des théories d'égalités. Voir Structures fondamentales.
Une théorie d'égalité est écrite avec les opérateurs présentés dans la présentation de la structure, le prédicat =, les variables universelles x,y,z..., et les seuls connecteurs logiques et, ou.
Une théorie d'égalité se développe en conjonction de clauses. La théorie admet une forme normale, un développement en conjonction de clauses, unique à l'ordre près des clauses, à l'ordre près des égalités dans chaque clause, et à une permutation près des variables universelles. La forme normale de la théorie est appelée l'expression de la théorie. Néanmoins deux théories distinctes, c'est à dire d'expressions différentes, peuvent être quand-même logiquement équivalentes.
La structure regroupe les objets compatible avec la structure. Un objet est compatible avec la structure si elle satisfait la théorie de la structure pour au moins un choix des opérateurs de la structure parmi ceux de l'objet. En théorie des modèles, l'objet est un modèle précis, et la structure est une théorie avec une couche d'abstraction permettant d'assigner chaque opérateur de la théorie, à un opérateur de même arité de l'objet. Ce choix est libre, et sépare le caratère abstrait de la théorie présentant quelques opérateurs par leur nom et quelques propriétés, du caractère concret de l'objet présentant quelques opérateurs par leur définition complète dans Ω.
La structure se définie par une présentation et une théorie d'égalité. La présentation présente quelques noms d'opérateurs avec leur arités, sans préciser leur définition. La théorie expose des propriétés sur ces opérateurs. La présentation est ainsi une extension du langage d'égalité permettant d'écrire la théorie d'égalité de la structure. Le langage de la struture, aussi appelée langage de sa théorie, est décrit dans la présentation de la struture.
Un objet n'est pas une structure, car la définition des opérateurs dans l'objet s'appuit sur un autre langage dans lequel les éléments sont nommés par des entiers de 0 à N-1, et les opérateurs sont nommés par des tableaux d'éléments. Néanmoins certains objets peuvent être converti canoniquement en une structure, par simple traduction, sans aucun choix arbitraire. Cette conversion correspond alors à une abstraction.
Pour qu'un objet soit ainsi convertible par simple traduction en une structure, il faut que soit contenu dans l'objet tous les éléments nécessaires à leur définition. Par exemple en posant l'univers Ω={0,1}, l'objet (0,(1,0)) qui correspond à l'objet (0, ¬(.)) ne peut pas être traduit canoniquement en une structure parce que la définition complète de l'opérateur ¬(.) ne peut pas être écrite tel quelle avec le seul élément 0. Parcontre l'objet (0, 1, (1,0)) qui correspond à l'objet (0, 1, ¬(.)) est bien convertible canoniquement en une structure. La traduction est <a, b, f(.)> / {f(a)=b, f(b)=a}. On voit bien la couche d'abstraction qui conciste à renommer tous les opérateurs utilisés 0, 1, ¬(.) par des noms de variables a, b, f(.) et qui sert de langage à la théorie d'égalité de la structure.
La théorie d'une strucure est toujours cohérente, car c'est une théorie d'égalité, elle ne contient pas de négation. Les cas dégénérés correspondent à l'égalité d'opérateurs de même arité.
Un object omniscient contient tous les opérateurs possibles. Un objet omniscient est donc compatible avec toutes les structures.
On se restreint aux objets de taille maximum de L bits, ou bien ayant une signature particulière telle que par exemple (N, 1, 2)
Nous avons en quelque sorte exposées tous les objets finies possibles servant de modèles, et choisie un langage de propriété (basé sur des opérateurs d'arité fixe nommés dans une présentation, utilisant le prédicat =, un seul type de variable universelle x,y,z..., et les seuls connecteurs logiques et, ou) pour pouvoir définir les structures. Mais alors comment maintenant sélectionner parmi toutes ces structures, celles jugées pertinentes pour servir de brique de construction ?. La pertinence tient dans plusieurs capacités : une capacité entropique, une capacité de factorisation de l'information, une capacité calculatoire, une capacité déductive... ?
L'entropie d'un état macroscopique est le logarithme du nombre d'états microscopiques possibles compatibles avec l'état macroscopique en question. La structure A constitue l'état macroscopique. L'objet X constitue l'état microscopique. Les structures sont des classes d'équivalence sur les objets.
L'objet X est compatible avec la structure A si et seulemet si il y a un choix possible associant à chaque opérateur de la présentation de la structure A, un opérateur de l'objet X, tel que l'ensemble de ces affectations satisfasse la théorie de A. On dira que X est compatible avec la structure A. Et par analogie à la théorie des modèles, on dira que X peut satisfaire A, que X peut réaliser A, que A peut se réaliser en X, que A peut être satisfait dans X, et de manière plus rustre que X possède la structure A, et que A contient l'objet X.
La (s,N)-entropie d'une structure A est égale au logarithme du nombre d'objets X distincts compatibles avec A, parmi les objets de signature s et opérant dans un univers de N éléments.
Puis nous ne souhaitons pas garder les objets, car leur conception est trop contigente des conditons caculatoires. On opère donc une abstraction, en ne retenant que les objects capables de cette abstraction. En particulier dés qu'un object énumère tous les éléments de l'univers Ω, il possède cette capacité d'abstraction, une traduction canonique en une structure. Cela produits les structures complètes avec des théories sans variables. Ces théories ne peuvent pas être complétés sans procéder à une extension du langage. Voici un exemple de structure complète : <a,b,f(.),g(.,.)> / {f(a)=b, f(b)=a, g(a,a)=a, g(a,b)=a, g(b,a)=a, g(b,b)=b}. Les opérateurs d'une structure complète sont complètement définis en interne.
Délors le langage de propriété, prétend au statut de langage de données. Les structures complètes à une permutation près des opérateurs de même arité, vont constituer nos données de base.
---- 29 septembre 2013 ----
Puis on introduit la notion d'isomorphisme. Considérons deux structures telles que :
S1 = <a, b, f(.), g(.,.)> / T1
S2 = <A, B, F(.), G(.,.)> / T2
Ces deux structures sont isomorphes si et seulement si il existe un isomorphisme φ de l'une vers l'autre qui associe chaque opérateur de la présentation de l'une à chaque opérateur de la présentation de l'autre et dans l'ordre de leur présentation. Un isomorphisme φ de S1 sur S2 vérifie les propriétés suivantes :
morphisme en a : φ(a) = A
morphisme en b : φ(b) = B
morphisme en f(.) : ∀x∈S1, φ(f(x)) = F(φ(x))
morphisme en g(.,.) : ∀x∈S1, ∀y∈S1, φ(g(x,y)) = G(φ(x),φ(y))Surjection : ∀Y∈S2 ∃x∈S1, Y=φ(x)
Injection : ∀x∈S1, ∀y∈S1, φ(x)≠φ(y) ou x=y
Puis on introduit les permutations interne aux présentations de structures. Considérons deux structures telles que :
Les propriétés de morphisme s'appliquent à tous les opérateurs de la présentation de la structure.
On définie les classes de structure
Par exemple ler groupe multiplivatif Z/3Z est mémorisé comme suit :
{0, 1, 2, *[000,010,020,100,111,122,200,212,221]}
Et si on représente les éléments comme des fonctions
{0[00,10,20], 1[00,11,22], 2[00,12,21]}
On considèrera 3 structures infinies de base (voir Structures fondamentales) :
Si on s'en tient à la quantification de la taille en un nombre de mots égal à une puissance de 2, alors le premier octet du varon suffie pour spécifier sa taille mémoire en contenant justement cette puissance de 2. A notre époque, la taille limite de 2255 mots est techniquement inatteignable. L'octet suivant est gardé pour un développement futur. Cet octet et les mots suivants qui sont en nombre variable contiennent donc la données brute proprement dite. Voila comment sont constitués nos varons.
Ces 3 structures diffèrent dans leur panel de fonctions mais se plonge comme suit : N* --> N --> Z faisant que Z peut récupérer toutes les fonctions définies sur N* et sur N en des fonctions images opérant sur Z avec des domaines de définition restreints. Néanmoins il est utile de garder la distinction entre ces trois structures pour servir de brique de construction pour d'autres structures, chaque structure portant avec elle une axiomatique spécifique.
Une structure constructive est définie par un énumérateur énumérant ses éléments, et par une théorie énumérant ses prropriétés, ces deux énumérateurs devant être deux programmes de taille finie dans un langage de programmation fini et non dégénéré c'est à dire suffisament riche pour atteindre la puissance d'expression d'une machine de Turing.
Une structures présentable est définie par un nombre fini d'opérateurs qui engendrent par composition close tous les éléments de la structure, et par un nombre fini d'égalités entre termes clos qui engendrent à l'aide des règles de déduction toutes les propriétés de la structure. Ces deux collections forment la présentation de la structure.
Comme toute théorie récursivement énumérable peut être étendue en une théorie finie, on en déduit que les structures constructives sont toutes présentables.
Les structures de monoïde et de groupe peuvent être traduites en des structures de fonctions unaires. C'est d'ailleur pourquoi elles sont jugées premières puisque n'utilisant que des opérateurs unaires (voir Structures fondamentales).
Décrivons quelques exemples non triviaux pour étudier la problématique de leur implémentation informatique.
Le monoïde bigène se présente en notation linguistique par :
<a,b,*(.,.)>/{*(.,.) est associatif}
<a,b,*(.,.)>/{∀x∀y∀z (x*y)*z=x*(y*z)}
et en notation programmative avec un patron par :
Monoïde bigène (*,a,b)
En l'absence d'autres règles d'égalité que celles liées à l'associativité de l'opération, le monoïde est considéré libre. On remarque par ailleur que le Monoïde unitaire bigène libre (*,1,a,b) est obtenue simplement en ajoutant l'élément neutre 1 au Monoïde bigène libre (*,a,b).
Lorsque l'on identifie l'opération de composition * avec l'opération de concaténation de mot (notée par absence de caractère), le monoïde bigène s'identifie au langage des mots d'alphabet {a,b} mais où le mot vide n'est pas autorisé. Il s'identifie à un langage de caractère définie par une grammaire. La grammaire se présente sous forme d'un quadruplet comprenant un alphabet A, une extension W, un ensemble M de mots appartenant au langage étendu, et un ensemble G de règles appartenant à ((A⋃W)*)2.
(A,W,M,G) = ({a,b}, {S}, {aS,bS}, {S-->aS|bS|ε})
(A,W,M,G) = ({a,b}, { }, {a,b}, {ε-->a|b})
Ces deux exemples de grammaires produisent le même langage qu'est le langage mère d'alphabet {a,b} sans le mot vide ε, et qui s'identifie à la structure de monoïde bigène libre.
Les mots d'alphabet {a,b} peuvent être énumérés en respectant l'ordre de complexité usuel que constitue la taille du mot. Le mot vide ε a le code zéro. Les caractères sont codés comme suit : a=1, b=2. Le code d'un mot s'obtient par un développement en base 2. Le mot aba possède comme code 1*20 + 2*21 + 1*22 = 9, et le mot aaaa possède comme code 1*20 + 1*21 + 1*22 + 1*23 = 15 . Ce codage est une bijection entre {a,b}* et N. Autrement dit, il constitue un algorithme de compression totale, on ne peut pas comprimer davantage.
La structure peut aussi se traduire en une structure de fonctions unaires. La présentation ressemble alors à :
<a(.), b(.)>(.)
Le suffixe (.) ajouté aux lettres a et b signifiant que a et b sont des fonctions unaires, et le suffixe (.) ajouté à la présentation <a(.), b(.)> signifie que les éléments de la structure considérée sont les fonctions unaires engendrées par composition non close. Noter que ce procédé ne permet pas de construire la fonction identité à partir de rien.
Mais sur quoi agissent ces fonctions unaires me direz-vous ? on en sait rien. La seul chose que l'on sait, c'est qu'elles sont définies sur tous les résultats possibles de tous les autres éléments de la structure, et qu'elles agissent ainsi dans un même ensemble inconnu E. On peut néanmoins supposer que cet ensemble E est également une structure constructive, et qu'il doit être suffisament grand pour différencier chaque fonction unaires distinctes.
Il convient d'être plus explicite dans la définition des types de fonctions et d'éléments mis en jeux. Deux notations sont alors utilisées, la notation par entête telle que E(F,G) et la notation applicative telle que (F,G)-->E où E,F,G représentent des types d'éléments c'est à dire des ensembles non nécessairement disjoints. Le symbôle point "." est alors réservé uniquement pour désigner l'ensemble des éléments de la structure.
La présentation exacte est alors :
<aE(E), bE(E)>E(E)
ou bien
<aE-->E, bE-->E>E-->E
Le groupe bigène se présente en notation linguistique par :
<*(.,.), inv(.), 1, a, b> / {
- *(.,.) est associative,
- inv(.) est l'opposé pour atteindre 1 avec *(.,.),
- 1 est l'élément neutre pour *
}
ce qui se développe en :
<*(.,.), inv(.), 1, a, b> / {
- ∀x∀yz (x*y)*z=x*(y*z),
- ∀x inv(x)*x=1, x*inv(x)=1,
- ∀x x*1=x, 1*x=1
}
(Noter que x,y,z sont des variables universelles et que a,b sont des constantes du langage.)
Le groupe bigène se présente en notation programmative par :
Groupe bigène (*, inv, 1, a, b)
où * est l'opération du groupe, inv est l'opération inverse que l'on note aussi par inv(x) = 1/x et par inv(x) = x-1. L'élément 1 est l'élément neutre pour l'opération *. Les éléments a et b sont les deux générateurs du groupe.
La structure peut se présenter, sans mettre la fonction inverse inv(.) parmi ses générateurs, sous forme d'un monoïde unitaire quadrigène ayant la propriété que chacun de ses générateurs possède un générateur inverse :
<*(.,.), 1, a, A, b, B> / {
- *(.,.) est associative,
- a*A=1, A*a=1, b*B=1, B*b=1,
- 1 est l'élément neutre pour *
}
Ce qui s'écrit en notation programmative par :
Monoïde unitaire quadrigène (*, 1, a, A, b, B) / {a*A=1, A*a=1, b*B=1, B*b=1}
La fonction inv(.) est alors calculée après coup, par une définition récurcive comme suit :
inv(a)=A, inv(b)=B, inv(A)=a, inv(B)=b
inv(x*y) = inv(y)*inv(x)
Lorsque l'on identifie l'opération de composition * avec l'opération de concaténation de mot (notée par absence de caractère), l'élément neutre 1 s'identifie au mot vide ε, le groupe bigène s'identifie à un langage de caractère d'alphabet {a,b} avec 4 règles de réduction que sont :
aA = ε
Aa = ε
bB = ε
Bb = ε
et qui constituent en terme informatique, un aspect, une couche logiciel qui va effectuer l'éventuelle simplification en tout endroit du mot, avant sa mémorisation.
La grammaire va présenter les règles complémentaires en quelque sorte, les règles permettant de construire tous les mots en évitant les cas interdits qui nécessiterait une simplification.
Le groupe bigène s'identifie à un langage de caractère définie par une grammaire. La grammaire se présente sous forme d'un quadruplet comprenant un alphabet A, une extension W, un ensemble M de mots appartenant au langage étendu, et un ensemble G de règles appartenant à ((A⋃W)*)2.
(A,W,M,G) = ({a,A,b,B}, {S,T}, {S}, {
- S --> aT | bT | AT | BT | ε,
- aT --> aaT | abT | aBT | ε,
- AT --> AAT | AbT | ABT | ε,
- bT --> baT | bAT | bbT | ε,
- BT -->BaT | BAT | BBT | ε
})
(A,W,M,G) = ({a,A,b,B}, { }, {a,A,b,B,aa,ab,aB,AA,Ab,AB,ba,bA,bb,Ba,BA,BB}, {
- aεa --> aaa | aba | aBa,
- aεb --> aab | abb,
- aεB --> aaB | aBB,
- AεA --> AAA | AbA | ABA,
- Aεb --> AAb | Abb,
- AεB --> AAB | ABB,
- bεa --> baa | bba,
- bεA --> bAA | bbA,
- bεb --> bab | bAb | bbb,
- Bεa --> Baa | BBa,
- BεA --> BAA | BBA
- BεB --> BaB | BAB | BBB
})
Ces deux exemples de grammaires produisent le même langage qu'est le langage mère d'alphabet {a,b} réduit par les 4 règles précitées, et qui s'identifie à la structure de groupe bigène libre.
La structure admet un codage bijectif relativement simple. Les élements de la structure sont les mots composés d'une succession d'atomes parmi {a, a-1, b, b-1} avec 4 restriction pour éviter de répéter le même éléments plusieurs fois. La constitution d'un mot se fait en choisissant un première atome parmi {a, a-1, b, b-1} que l'on codera de 1 à 4, puis en choissant les atomes suivants parmi les trois atomes autorisés selon le contexte et que l'on codera de 1 à 3, à savoir :
Contexte |
a |
a-1 |
b |
b-1 |
Première atome |
1 |
2 |
3 |
4 |
Après un a |
1 |
2 |
3 |
|
Après un a-1 |
1 |
2 |
3 |
|
Après un b |
1 |
2 |
3 |
|
Après un b-1 |
1 |
2 |
3 |
Ainsi la chaine 22311 désigne le mot a-1bbaa. Le code est rendu bijectif (et donc complètement dense) en le remplaçant par le développement 2 + 2*(4*30) + 3*(4*31) + 1*(4*32) + 1*(4*33) = 190. Ainsi le code du mot a-1bbaa vaut 190.
La structure peut être traduite en une structure de fonctions unaires opérant sur un ensemble E inconnue. La présentation de notre structure devient :
<aE(E), AE(E), bE(E), BE(E)>E(E) / {∀x∈E(E), a(A(x)) = x, A(a(x)) = x, b(B(x)) = x, B(b(x)) = x}
ou
<inv.(.), 1E(E), aE(E), bE(E)>E(E) / {∀x∈E(E), ∀e∈E, inv(x)(x(e)) = e, x(inv(x)(e)) = e}
Le suffixe E(E) ajouté aux lettres signifie que ce sont des fonctions unaires de E dans E, et le suffixe E(E) ajouté à la présentation signifie que les éléments de la structure considérée sont les fonctions unaires de E dans E, engendrées par composition non close.
---- 26 septembre 2013 ----
Néanmoins l'inverse peut être également recherché. Augmenter la redondance afin de pouvoir corriger d'éventuelles modifications accidentelles. Cette autre démarche ouvre des possibilités de rendre davantage lisible les données.
L'élément est alors mémorisé comme un entier avec une information supplémentaire qui est son appartenance à sa structure. Cette information supplémentaire est un typage qui peut être statique ou dynamique, c'est à dire contenue dans le contexte de l'utilisation ou explicitement mémorisé dans le varon ou le modon.
Il se peut alors qu'on préfère mémoriser la taille exacte dans le second mot du varon, une taille donc limité à 4 Giga atomes, et que la données brute soit une succession de valeurs binaires permettant ainsi de mémoriser 16 lettres (ou atomes) par mots. Les données brutes du varon sont alors mémorisées dans le troisième mot et suivants.
On utilise les principes de la programmation orienté object avec une plus grande liberté que le seul langage C++ ne pourrait pas nous apporter, en utilisant le renommage des types et le compilateur gcc au sein même de notre logiciel, afin de structurer et adapter à la source nos classes et nos objects.
Prenons deux exemples de structure. Z/nZ qui se présente en notation linguistique implicite par <a> / {an = 1}, et <a,g(.,.)>.
La structure est une classe. La classe mémorise les opérations d'addition, de soustraction, de multiplication, de division, l'opération produisant l'élément zéro, et l'opération produisant l'élément un....
Les objects de cette structure sont les constantes 0,1,2,3...n-1 et n'ont pas besoin d'être mémorisés. Ce ne sont donc pas à proprement parler des objects, mais plutôt des valeurs. Seul leur codage définie dans la classe est mémorisé. La classe comprend un énumérateur qui énumère tous ses éléments.
Une variable x appartenant à Z/nZ constitue un autre type d'object. Mais il y a plusieurs conceptions possibles :
Il faut donc considérer deux classes dérivées que sont la classe des constantes appartenant à la structure, et la classe des variables appartenant à la structure. Mais dans les faits, on regroupe ces deux classes en un seul, en ajoutant un attribut const pour reconnaitre les variable contantes des variables pouvant varier aux cours du temps.
Une variable possède donc un attribut const (true ou false) et un nom l'identifiant
Une structure définira une classe et les élémentrs de la structure
L'implémentation de la structure consiste en deux opérations : en une codification de ses éléments afin de pouvoir les mémoriser dans les objects, et en une programmation de ses opérations suivie d'une codification des programmes afin de pouvoir les mémorisés dans la classe . La structure étant infinie les éléments sont mémorisés dans des varons.
Comme nous voulons être efficient, il nous faut être paresseux et ne pas refaire ce qui n'est pas necessaire d'être refait. C'est la tâche principale auquel se consacre l'outils make. make exécute un fichier makfile et crée un fichier.
La structure de base du Makefile est :
cible : dépendances
commandes
....
où cible est le nom du fichier créé, dépendance représente la liste des fichiers (ou règles) nécessaires à la construction de la cible, commandes représente les commandes à effectuer pour créer la cible.
La cible n'est construite que si le fichier source est plus récent. On appelle cette structure une règle. Le fichier Makefile n'est rien de plus qu'un ensemble de règles.
Par exemple considérons un programme c comprenant 4 modules main.c, mod1.c, mod2.c, mod3.c avec les liens de dépendance suivants : main.c dépend de mod.3.c et de mod1.c et mod3.c dépend de mod1.c et de mod2.c. Les commandes à exécuter pour compiler ce programme sont alors :
gcc -c mod1.c -o mod1.o
gcc -c mod2.c -o mod2.o
gcc -c mod3.c mod1.o mod2.o -o mod3.o-c main.c -o main.o gcc main.o fonctions.o -o Programme
mod1.h |
mod1.c |
#include <stdlib.h> typedef int Element; |
#include "mod1.h" union {div_t t1; Pair t2;} T; inline void Aff(Element a){printf("%d \n",a);} |