La structuration informatique consiste à créer des petits objets suffisaments généraux pour pouvoir être utilisés de multiple façons possibles, trés fréquemment, et avec la plus grande et libre expression possible, nécessitant une forte interopérabilité. L'objet doit avoir une autonomie adaptée pour allier rapidité d'exécution de ses methodes, utilisation de méthodes héritées, économie d'espace, partage de structure....
L'object est toujours vue dans un contexte. Soit il est de type totalement déterminé par le contexte, c'est à dire qu'il n'a pas besoin de contenir de référence à un type puisque tous ses comportement sont déja accessibles dans le contexte. Soit il est de type totalement inconnue par le contexte, c'est à dire que le contexte n'a acune information sur le type de l'object, et que celui-ci doit donc apporter toutes les informations sur ses comportements, il est alors libre de changer de type et il contient donc une référence à un type qui décrit tous ses comportements. Soit il est de type partiellement connu par le contexte avec alors une certaine liberté, une autonomie partielle, il contient une référence à un type partiel qu'il peut changer et qui complète celui apporté par le contexte. Si le contexte est celui de la compilation : Dans le premier cas, le typage est connue au moment de la compilation et il est dit statique. Dans le second cas, le typage n'est connue qu'au moment de l'exécution et il est dit dynamique. Dans le troisième cas le typages est mixte, c'est un typage statique partiel complété par un typage dynamique partiel.
Une des opérations clef de l'ordinateur consiste en l'adressage indirecte. Pour pleinement exploiter la puissance mésentropique de l'adressage indirecte il faut concevoir des suites non bornée d'adressages indirectes, à l'aide d'un typage dynamique partiel.
Nous allons d'abord définir ce qu'est un pointeur d'une facon un petit peu plus générale :
La fonction d'un pointeur p est de pointer un bloc parmis d'autres. La taille nécessaire d'un pointeur, ainsi que sa fonction d'adressage la plus efficace, dépend d'hypothèses sur les blocs pointés. La première hypothèse que nous faisons est qu'il existe un metabloc d'adresse A0 et de taille A qui contient des blocs de tailles multiples de B se succédant continûment. La taille nécessaire d'un telle pointeur est celle pouvant contenir A/B valeurs distinctes. Les tailles sont toujours exprimées en nombre d'octets. L'octet est la première quantification opérées par l'ordinateur contemporain. Nous introduisons donc une seconde quantification qui décompose le métabloc en A/B cases contigües de taillle B.
Un tel pointeur possède une fonction d'adressage qui calcule l'adresse du bloc qu'il pointe. La fonction d'adressage est une fonction nommée ß. Elle prend en argument une variable de type Pointeur qui est un type d'entier de taille adaptée d'un ou deux ou trois ou quatre octets, et elle retourne une adresse de bloc :
ß(p) = A0 + p*B
Pour que la fonction d'adressage soit efficace, il faut que B soit une puissance de 2, pour que la multiplication soit alors une simple opération de shifftage. Posons B = 2^b.
La taille de p est soit 1 ou 2 ou 3 ou 4 octets. Pour que toutes les données de p soient utilisées il faut que A/B soit donc égale à 2^8 ou 2^16 ou 2^24 ou 2^32.
On peut réserver d'autres fonctionnalités au pointeur, en réservant 1 bit pour une fonctionnalité série autre, et en réservant 1 bit pour une fonctionnalité parallèle autre. Pour que toutes les données du pointeur p soient utilisées, il faut alors que A/B soit égale à l'un des modes suivants : 2^(8-2) ou 2^(16-2) ou 2^(24-2) ou 2^(32-2)
Comme nous privilègions l'interopérabilité, la taille d'un pointeur p devra être égale à la taille d'une case, c'est à dire égale à B, afin de pouvoir convertir le pointeur en une donnée et vis-versa sans perte de donnée. On considerera plus tard le cas similaire où la case de taille B contient exactement k pointeurs.
L'intéroperabilité apporte la récursivité, le pointeur dit récurcif peut pointer un autre pointeur recurcif qui peut pointer encore un autre pointeur recurcif et ainsi de suite. Et le processus n'a pas forcement de fin, il peut boucler. Pour déterminer si le pointeur pointe une feuille ou un autre pointeur nous devrons utiliser un bit, le bit réservé pour une autre fonctionnalité série, et nous l'appelerons flag de pointeur. Et pour déterminer si l'on est déja passé par ce pointeur afin de détecter les boucles nous devrons utiliser un autre bit, le bit réservé pour une autre fonctionalité parallèle, et nous l'appelerons flag de passage.
On note p.u le bit de p réservé pour une autre fonctionalité série, c'est le flag de pointeur. On note p.v le bit réservé pour une autre fonctionnalité parallèle, c'est le flag de passage. Et on note p.w les autres bits de p.
Ces structures de metabloc, subdivisés en A/B cases, sont intéressantes car elles réunifient données et pointeurs, et permettent l'implémentation des pointeurs recurcifs, avec un minimum de perte de données. Dans le cas où l'on reserve 2 bits pour chaque pointeur (le flag de pointeur et le flag de passage), il y a alors 3 structures posssibles de metabloc : une en 64 cases, une en 16 milles cases, et une en 1 milliard de cases, le nombre de pointeurs par case étant fixé librement.
-----
Quelque soit un type T, on définie un type nouveau noté T@ appelé pointeur récurcif de bloc de type T, qui est une succession de pointeur se pointant à la queulele jusqu'à un bloc de type T. On appellera noeud une case de type T@ et on appelera feuille un bloc de type T.
Il est nécessaire de différencier un pointeur recurcif pointant une feuille, d'un pointeur récurcif pointant un noeud, et pour cela on réserve un bit qui lorsqu'il est à zero, indique que le pointeur récurcif pointe une feuille et lorsqu'il est à un, indique que le pointeur recurcif pointe sur un noeud c'est à dire un autre pointeur récurcif. C'est le bit p.u de p réservé pour une autre fonctionalité série, et que nous appelons flag de pointeur, qui jouera ce rôle de typage dynamique partiel.
Les fonctions en C++ manipule des blocs de taille fixes, c'est pourquoi il est plus simple lorsque l'on manipule un bloc de taille supérieur à une case, de manipuler en fait à sa place un pointeur sur ce bloc, le pointeur ayant la taille d'une case.
La qualité pour un pointeur récurcif p de type T@, de pointer sur une case de type T@ ou de pointer sur un bloc de type T, est déterminé par un bit particulier p.u appelé flag de pointeur.
On définie l'évaluation totale d'un tel pointeur recurcif p comme étant égale à p si p.u=0 ou comme étant égale à *ß(p) si ß(p)->u=0 et ainsi de suite..., c'est à dire comme étant égale au dernier pointeur pointant sur le bloc de donnée de type T, qui est au bout de la liste des pointeurs recurcifs se pointant successivement. S'il y a une boucle, l'évaluation sera dite indéterminé. Mais même dans ce cas l'évaluation sera faite en partie et donnera un pointeur récurcif pointant là où commence la boucle, ou plutôt le premier pointeur récurcif rencontré faisant partie d'une boucle, ou plus simplement le premier pointeur rencontré pointant sur un pointeur où on est déja passé, cette dernière definission semble la plus cohérente.
Pour implémenter ce mécanisme il est nécessaire de repérer les éventuelles boucles afin d'éviter des calculs sans fin. Pour cela on réserve un bit qui lorsqu'il est à 0, indique que l'on n'a pas encore rencontré le pointeur et lorsqu'il est à 1, indique que l'on est déja passé par ce pointeur. C'est le bit p.v de p réservé pour une autre fonctionalité parallèle, et que nous appelons flag de passage, qui jouera ce rôle. Pour remettre ce bit à zéro, il sera nécessaire d'effectuer un second passage.
Le pointeur récursif de type T@ occupe une case, et contient exactement : une référence d'une case du métabloc, un flag de pointeur, et un flag de passage.
On définie 4 fonctions E1(p), E2(p), E(p,n), Ei(p) d'évaluation. E1(p) calcule l'évaluation d'un niveau du pointeur recurcif p. E2(p) calule l'évaluation d'exactement deux niveaux du pointeur recurcif p. E(p,n) calcule l'évaluation d'exactement n niveau du pointeur recurcif p. Ei(p) calcule l'évaluation totale du pointeur recurcif p.
Etant donnée une variabble p de type T@, l'adressage indirecte récursif de cette variable est noté @p et correspond à un élément de type T@ resultat de la fonction Ei(p). L'adressage indirecte récursif d'exactement n niveaux sera noté @(n)p et correspond à un élément de type T@ resultat de la fonction E(p,n).
Le type T@ hérite d'une certine façon du type T*, mais surdéfinie l'opérateur * de tel sorte que pour un pointeur p de type T@, *p désigne l'objet pointé directement par p qui est de type T si p.u=0 ou de type T@ si p.u=1. La déclaration de *p comprend la déclaration de p et le flag de pointeur p.u, elle n'est donc pas connue au moment de la compilation, et la compilation devra donc prévoir les deux cas.
inline
Pointeur E1(Pointeur p){ if (!p.u) return p; return *(A0 + p.w<<b); } |
inline Pointeur
E2(Pointeur p){ |
inline Pointeur
Ei(Pointeur p){ |
inline
Pointeur Ei(Pointeur p, int n){ Pointeur I=p,J; if (!p.u || !n) return p; do { J = *(A0 + I.w<<b); n--; if (!J.u || !n){I=J;break;} if (J.v){break;} J.v++; I = *(A0 + J.w<<b); n--; if (!I.u || !n){break;} if (I.v){I=J;break;} I.v++; } while(true) J = *(A0 + p.w<<b); while(J.v) { J.v--; J = *(A0 + J.w<<b); } return I; } |
Si nous nous plaçons dans le cas d'un pointeur de 4 octets, comme il y a des contraintes d'alignement des mots de 4 octet, leur adresse étant nécessairement un mutiple de 4, on peut utiliser les deux premiers bits comme flag. Le pointeur récurcif peut alors se définir en C++ par la structure suivante :
union Pointeur {
T *r;
Pointeur *R;
unsigned int f:2;
struct{
unsigned int u:1;
unsigned int v:1;
unsigned int w:30;
};
};
un Pointeur p possède un flag de pointeur p.u et un flag de passage p.v et si p.u=0 alors p.r pointe sur le bloc de type T, et si p.u=1 alors p.R pointe sur un pointeur récursif. Et p.f contient les deux flags qui doivent être basculé à zéro à chaque fois que l'on lit les valeur p.r ou p.R.
inline
Pointeur E1(Pointeur p){ if (!p.u)) return p; p.f=0; return *p.R; } |
inline
Pointeur E2(Pointeur p){ if (!p.u) return p; p.f=0; Pointeur p1 = *p.R; if (!p1.u) return p1; p1.f=0; if (p1==p) return p; return *p1.R; } |
inline Pointeur
Ei(Pointeur p){ |
inline Pointeur
E(Pointeur p, int n){ |
Si nous nous intéressons qu'aux boucles, il n'est plus utile de préciser vers quoi pointe le pointeur recurcif. Lorsque l'on ommet de préciser le type de feuille, cela signifie que le pointeur récursif ne pointe jamais sur une feuille. Par exemple voici plusieurs graphes de type @ :
Chaque case sur ce shéma est de type @.
Le typage mixte précisant la qualité de pointeur de feuille ou de pointeur de noeud, est redondante puisque celle-ci est déja déclaré par l'absence de feuille. Les cases de type @ peuvent donc utiliser le flag de pointeur à autre chose, parcontre le flag de passage sera toujours utilisé pour détecter les boucles.
Ce pointeur récurcif sans feuille peut alors se définir en C++ par la structure suivante :
union PointeurSansFeuille {
PointeurSansFeuille *p;
struct{
unsigned int v : 1;
unsigned int n : 31;
};
};
un PointeurSansFeuille p possède un flag de passage p.v initialisé à zéro et qui permet de detecter les boucles.
La case est une quantification propre à notre pointeur. Un bloc est composé de plusieurs cases contigües et est à l'interieur du metabloc. La fonction d'un bloc est de contenir des données tout en permettant une grande interopérabilité.
Le bloc est traité avec la connaissance d'un type déclaré préalablement qui prévoit dans certain cas d'être complété par un type dynamique contenu dans le bloc en question, et/ou contenue dans sa référence qui est un pointeur pointant le bloc en question.
Par exemple le type pointeur récurcif T@ appliqué à un bloc va nous permettre de voir le bloc selon ce type. Le bloc doit possèder le type dynamique partiel, appelé flag de pointeur, qui précise si c'est un pointeur recursif pointant sur un pointeur recurcif ou si c'est un pointeur recurcif pointant sur un bloc de type T, c'est à dire si son type est T@*1 ou T*0 qui sont des spécialisations du type T@.
Les types de bloc de taille supérieur à une case sont définies grace au structure et au tableau
On peut déclarer un pointeur de bloc de type T. Le bit flag de pointeur et le bit flag de passage ne sont alors pas utilisés. Le type T*, lorsque son flag de pointeur est fixé à 0, est noté type T*0, et constitue une spécialisation du type T*, et constitue également une spécialisation du type T@.
T@ possède un typage dynamique qui précise une alternative entre les types T*0 (avec flag de pointeur à zéro) ou type T@*1 (avec flag de pointeur à 1). Si le flag de passage est utilisé, alors il faut initialiser le flag de passage lors de l'initialisation du pointeur.
La déclaration d'un type pointeur ou pointeur recurcif n'effectue pas d'initialisation à l'exception du typage dynamique, et n'effectue pas d'allocation mémoire autre que celle de la variable pointeur dans la pile (stack). Cela reste à la charge du programmeur.
On peut déclarer une structure comme en C++. Par exemple le type struct{T, R, S} est une structure juxtaposant une succession de types quelconques déja déclarés T, R, S. Le bloc de ce type devra être une juxstaposition contigüe de sous-bloc de type T puis R puis S.
Comme en C++, nous pouvons définir des structures récurcives. Nous définissons des types struct que l'on nomme et dont on réutilise le nom à l'interieur par l'intermediaire de pointeurs. Exemple de déclaration de structures recursive en utilisant les pointeurs :
T = Type des entiers non signés de taille variable
struct A {A*, B*}
struct B {A*, T}
Chaque blocs sur ce shéma possède l'un des types A ou B.
Noter sur cette exemple, la présence du typage mixte de tableau fini, utilisé pour définir les entiers de taille variable µ.
Le flag de passage n'est apriori pas utilisé. Pour l'utiliser il faut simplement les initialiser à zéro lors de l'initialisation des pointeurs utilisant ce flag.
Le pointeur de type T@@ corrrespond à un pointeur récurcif de pointeur récurcif. S'il n'y a pas de boucle et si le pointeur récurcif pointé, qui est de type T@, n'a pas de boucle non plus, alors cela correspond à une chaine de pointeurs de type T@@*1 à l'exception du dernier dont le type est T@*0 et pointe sur une autre chaine de pointeur de type T@*1 à l'exception du dernier dont le type est T*0 et pointe sur un bloc de type T, et on ajoute la contrainte que les flags de passage de chacun de ces pointeurs ont bien été initialisé à zéro.
Nous pouvons définir des structures récurcives par l'intermediaire de pointeurs et de pointeurs recurcifs. Exemple de déclaration de structures recursive en utilisant des pointeurs et des pointeurs récurcifs :
T = Type des entiers non signés de taille variable
struct A {A@, B*}
struct B {A*, B*}
Chaque blocs sur ce shéma possède l'un des types A ou A@ ou B.
Noter sur cette exemple, la présence du typage mixte des pointeurs recurcifs de type A@ qui sont spécialisés soit de type A*0 (couleur rouge) ou de type A@*1 (couleur vert), ainsi que la présence du typage mixte de tableau fini utilisé pour définir les entiers de taille variable µ.
Même remarque que précédement s'il on souhaite utiliser le flag de passage sur certains pointeurs, il faut simplement les initialiser à zéro lors de l'initialisation des pointeurs en questions.
On peut formaliser le typage de pointeur mixte comme suit : Une variable de type pointeurMixte{A,B,C,D} est un pointeur de type A* ou B* ou C* ou D* selon la valeurs des flags séries, appelés flags de pointeur, contenue dans le pointeur. L'implémentation des pointeurs devra contenir n flags de pointeur pour pouvoir définir des pointeurs d'au plus 2^n alternatives.
Si on implémente en plus le flag de passage, il faudra veiller à initialiser ce flag à zéro lors de l'initialisation des pointeurs mixtes.
Le type T@ est identique au type pointeurMixte(T, T@).
Nous définissons comme pour les structures, des types pointures mixtes que l'on nomme et dont on réutilise le nom à l'interieur par l'intermediaire du pointeur mixte lui-même, et que nous appelons pointeurs mixtes récurcifs.
Le type pointeurMixte A (T, A) est égale au type T@.
Nous pouvons définir des structures récurcives par l'intermediaire de pointeurs et de pointeurs mixtes. Exemple de déclaration de structures recursive en utilisant les pointeurs mixtes :
T = Type des entiers non signés de taille variable
struct A {pointeurMixte(A,T), pointeurMixte(A,T)}
Chaque blocs sur ce shéma possède l'un des types A ou T.
Noter que chaque bloc de type A contient 2 cases qui sont des pointeurs mixtes, et donc qui contiennent chacun d'eux un typage mixte présisant leur spécialisation en type A*1 (couleur vert) ou T*0 (couleur rouge).
Un bloc de type T[n], où n est un entier plus grand que 1, est composé de n blocs de type T juxtaposés les uns après les autres. Le type T[n] peut être obtenue à partir du type struct {T,T,T.... n fois...} auquel on a jouté les méthodes spécifiques aux tableaux. On définie le type tableau A {T, n} : Une variable de type A est un bloc composé de n blocs de type T. Lorsque le type de tableau est utilisé pour préciser le type des éléments du tableau lui-même par l'intermediaire de pointeurs, le type est appelé tableau recursif. Voici 3 exemples de tableau récursif :
tableau A {A*, 2}
tableau A {A@, 2}
tableau A {pointeurMixte(A,int), 2}
On définie un type nouveau noté T[] qui est une succession contigüe de blocs de type T et dont le nombre doit être précisé dans un typage mixte. Ce typage utilise la première case du bloc pour contenir un nombre µ. On définie le type tableauFini A T : Une variable de type A est un bloc composé d'une case contenant µ, suivie de µ blocs de type T. Voici 3 exemples de tableau fini récursif :
tableauFini A A*
tableauFini A A@
tableauFini A pointeurMixte(A,int)
La définition de tableau infini de type T<n> correspond à la définition d'une fonction (int-->T) dont le programme est de taille n, prenant comme entré un argument de type entier, et produisant en sortie une donnée de type T. La fonction est un programme contenue dans les n premières cases. Si le résultat T est un pointeur, on suppose que la fonction calcule un pointeur cohérent avec ce qu'il pointe. On définie le type tableauInfini A {T n}: Une variable de type A est un bloc composé de n cases contenant le programme d'une fonction (int-->T). Mais on utilisera plutot le type tableau infini de programme de taille fini, T<>. On définie le type tableauInfini A T : Une variable de type A est un bloc composé d'une case contenant un nombre µ suivie de µ cases contenant le programme d'une fonction (int-->T). Voici 4 exemples de tableau infini récursif :
tableauInfini A A
tableauInfini A A*
tableauInfini A A@
tableauInfini A mixte(A,C)
La définition de type (A-->B)<n> correspond à la définition d'une fonction (A-->B) dont le programme est de taille n, prenant comme entré un argument de type A, et produisant en sortie une donnée de type B. La fonction est un programme contenue dans les n premières cases. On définie le type tableauInfiniType A {B, C, n}: Une variable de type A est un bloc composé de n cases contenant le programme d'une fonction (B-->C). Mais on utilisera plutot le type tableau infini de programme de taille fini (A-->B)<>. On définie le type tableauInfiniType A {B, T} : Une variable de type A est un bloc composé d'une case contenant un nombre µ suivie de µ cases contenant le programme d'une fonction (B-->T). Voici 4 exemples de tableau infini récursif :
tableauInfiniType A {B, A}
tableauInfiniType A {B, A*}
tableauInfiniType A {B, A@}
tableauInfiniType A {B, mixte(A,C)}
Ce type n'est qu'une autre façon d'écrire un type struct {T,R,S,...}. Une variable de type StructAuto {f(int x){...} , n} est un bloc composé de n blocs, où la fonction préalablement déclaré f prend en argument un entier compris entre 1 et n et retourne le type du n-ième bloc de la structure. Mais on utilisera plutot la structure autogénérée avec un programme de taille fini. On définie le type StructAuto A f(int x){...} : Une variable de type A est un bloc composé d'une case contenant µ suivie de µ blocs, où la fonction préalablement déclaré f prend en argument un entier n compris entre 1 et µ et retourne le type du n-ième bloc suivant de la structure. Exemple de structure autogénéré recursive :
StructAuto A f(int x){if (x%2==0) return "A*"; if(x%2==1) return "B";}
Une variable de type BlocDynamique est composé d'une case pointant un type type, et d'un bloque de type égale au type pointé par la case.
Une variable de type StructDynamique n est un bloc composé
de n bloc dynamiques.
Une variable de type StructDynamique est un bloc composé d'une
case contenant µ suivie de µ blocs dynamiques.
Une variable de type StructAuto est un bloc composé d'une case
contenant µb suivie d'une case contenant µf suivie de µf cases
contenant le programme d'une fonction f (int-->type) suivie
de µb blocs, où la fonction f prend en argument un entier n compris
entre 1 et µb et retourne le type du n-ième bloc suivant de la
structure.
Le type type est une construction faite à partir des opérateurs de type et du type de base int..
Notation courte et anonyme
Quelque soit T, R, S, n, ... |
Notation avec nommation A
|
Description
|
Arité de l'opérateur de type
|
struct
{T, R, S,...}
|
struct A
{T, R, S,...}
|
![]() |
µ
|
pointeurMixte
{T, R}
|
pointeurMixte
A {T, R}
|
![]() |
2
|
T[n]
|
tableau A
{T, n}
|
![]() |
1
|
T[]
|
tableau A
T
|
![]() |
1
|
T<n>
|
tableauInfini
A {T,n}
|
![]() |
1
(+ 1 int) |
T<>
|
tableauInfini
A T
|
![]() |
1
|
(T-->R)<n>
|
tableauInfiniType
A {T, R, n}
|
![]() |
2
(+ 1 int) |
(T-->R)<>
|
tableauInfiniType
A {T, R}
|
![]() |
2
|
structAuto
f(int x){...}
|
structAuto
A f(int x){...}
|
![]() |
µ
|
blocDynamique
|
blocDynamique
A
|
![]() |
0
|
structDynamique
n
|
structDynamique
A n
|
![]() |
0
(+ 1 int) |
structDynamique
|
structDynamique
A
|
![]() |
0
|
structAuto
|
structAuto
A
|
![]() |
0
|
Comment sont décrit les types ? Le type le plus simple est l'entier signé ou non contenue dans une case. On construit des types dérivés grace à la définition de pointeur T*, de pointeur récursif T@, de pointeur mixtes pointeurMixte{A,B}, de structure struct {T,R,S...}, de tableau T[n], de tableau fini T[], de tableau infinie T<>, de tableau infinie (T-->R)<>, de structAuto, de blocDynamique, de structDynamique. Et on construit d'autres types dérivés grace à la définition de méthodes, à l'héritage et à la surdéfinition des méthodes.
L'addressage indirecte est une fonction. Ce qui la différencie des autres fonctions est qu'elle ne consiste qu'en une seul opération machine. Elle est donc executé en un seul cycle, l'unité de temps de l'ordinateur, qui est de l'ordre d'une nano seconde (1E-9 secondes) pour les ordinateurs contemporains.
En généralisant la notion de pointeur, on introduit la notion de fonction d'adressage. Le typage se surajoute à la fonction d'adressage.
Il faut nous affranchire du typage. Le typage est un frein à l'interopérabilité. Il a été développé dans le but de perfectionner les mécanismes de preuve des programmes à la compilation basée sur la syntaxe et le typage. Or cette démarche va à l'encontre de la responsabilisation des utilisateurs à qui doit revenir cette tache de contrôle. Nous privilègions un contrôle interactif, un mécanisme de preuve des programmes à l'éxecution, qui redonne la responssabilité à l'utilisateur de vérifier la validité des calculs, par un procédé effectif mis à disposition par le programme lui-même.
La logique d'économie libérale, laisse à l'exploitant la possibilité de concentrer les pouvoirs de décisions en une main et de restreindre l'accés à l'information sur le processus de développement. Elle institue ainsi une hierarchie basée sur la désinformation des niveaux infèrieurs, une sorte de modèle de société fondé sur le mensonge, qui garantie la pérennité des privilèges indus.
Ce principe est incompatible avec notre projet axé sur la recherche d'une plus grande interoperabilité et qui privilègie un mécanisme de preuve à l'éxecution.