Nous allons discourir des fondements informatiques et mathématiques. Et afin de rendre moins ingrats nos travaux d'études, en même temps que l'on établira les concepts premiers, nous developprerons un framework les mettant en oeuvre. Cela consiste en la construction de structures et d'algorithmes ayant une grande généralité et une forte interopérabilité. Et par un lien subtil d'abstraction, la problèmatique informatique étant lié à une problèmatique mathématique, cela correspond à la construction par le bas d'une mathématique, tout en restant proche de la machine pour en assurer à la fois l'efficacité et la densité.
Le framework ou simplement boite à outils, est un ensemble de morceaux de programme, définitions de types, de variables, de fonctions, de procédures, d'objects, de classes, de méthodes..., servant de briques élémentaires pour la programmation en C++, il enrichit donc le langage de programmation. Le framework précise pour chacun de ses éléments, des paramètres par défauts mettant en valeur sa richesse. Ainsi une simple déclaration d'un élément sans autre précision de paramètres proposera directement une version générique de l'élément parmi les plus illustratives.
Au départ, on décrit la topologie des données et de la mémoire, puis celles des transformations, et en final celles des propriétés elle-mêmes. On explore les cas premiers et on explore chaque construction possible en faisant une classifcation, et toujours en passant en revue, la topologie de la donnée, ses algorithmes, et ses propriétées, (voir Les 3 concepts (Données, Programme, Théorie) ), une construction par le bas, exhaustive, pédagogique, ordonnante...
L'aspect séquentiel de la mémoire est une structure fondamentale de l'ordinateur contemporain, et d'avantage encore, de celle d'un flux d'information simple. L'object informatique admet une forme atomique qu'est le bloc mémoire contiguë et qui possède un type statique déclaré avant, qui n'est pas référencé dans le bloc lui-même et qui décrit son comportement. En effet, tout ne peut pas être dynamique c'est-à-dire être référencé dans le bloc lui-même, la description de ce référencement nécessite forcément une convention initiale constituant un type. Le type de l'object est appelé sa structure. Et par abstraction on parlera de structure pour désigner un object générique ayant cette structure.
On ne va pas développer tout de suite dans le cas général. On procède par le bas, c'est à dire par les structures premières, les plus simples, celles rencontrées en premiers, pour ensuite se composer et aboutire à une notion d'object plus générale. La structure la plus simple se présente topologiquement comme un bloc mémoire contiguë de taille fixe, que nous appellerons modon.
Trouver un nom qui n'a pas de sense est parfois difficile, et qui évoque de surcroit quelque intuition compatible avec l'object que l'on veut nommer. Modon ne signifie rien de spéciale, une ville..., et il y a mod comme modulo et on comme sur quelque chose. Somme toute, modon convient.
Une telle structure atomique de taille fixe appelée modon est un object particulièrement simple. C'est un bloc mémoire contiguë dont la taille est déterminée préalablement par un type. Et pour une structure aussi simple, il est facile de définire les premiers concepts à mettre en oeuvre sans prendre le risque de brider arbitrairement les possibilitées de développement.
Le modon est donc une mémoire avec une adresse et une taille, cela veut dire 3 caractéristiques premières :
Dans le cas générale, l'élément désigne le contenu, et l'objet désigne le contenant, et la caractéristique externe n'interfère pas faisant que l'object peut être déplacé par copie brute sans contrainte ni altération. En cela, deux objects d'égal contenu sont égaux en tant qu'élément mais distincts en tant qu'object s'ils n'occupent pas le même espace mémoire.
L'object est donc une variable contenant un élément, et le type de l'object correspond à l'ensemble des éléments qu'il peut valoir.
On exhibe le type du modon, un type static qui joue le rôle moteur, et on établit une distance entre l'élément et le contenue brute car l'élément ne doit pas être lié à la machine par des liens aussi contraingnant. La donnée brute constitue l'état microscopique du modon et l'élément constitue l'état macroscopique du modon. 5 caractéristiques apparaissent alors :
La caractéristique n°2 est déterminé par la n°1 c'est-à-dire que la taille du modon est définie préalablement dans son type static. La caractéristique n°4 est déterminé par la n°1, la n°3 et la n°4 c'est-à-dire que l'élément qui est contenu par le modon est déterminé par son type, son état microscopique et éventuellement par sa caractéristique externe.
En établissant cette distance entre l'élément et la donné brute, on libère sa définition (voir Philosophie et construction). Nous commençons par un procédé explicitement constructif lié à la machine mais dont le sens intuitif n'est pas directement l'élément que nous recherchons. Ceci afin que le procédé constructif au quel nous nous soumettons n'altère en rien la liberté de définition des éléments que nous voulons découvrir.
Dans le cas le plus simple, la donnée brute est libre, c'est à dire qu'aucune règle de syntaxe restrictive ne vient limiter les différents états microscopiques possibles. Chaque états correspond à une configuration unique des n bits du modon, et il y en a exactement 2^n. Le modon possède un état microscopique libre.
Sinon il existe une règle restrictive n'autorisant qu'un certain nombre d'états microscopiques. Et ce sont les différentes formes que peuvent prendre ces règles restrictives que nous allons utiliser pour construire un langage de programmation et de proposition, un langage conforme à notre démarche qui établira ses choix premiers en fonction des propriétés topologiques.
Ces règles restrictives entraine l'existance d'états microscopiques non conformes. Nous pouvons les considérer comme des erreurs de syntaxe. On défini l'état macroscopique spécial, nommé FAIL, pour désigner tous les états microscopiques non autorisés.
L'élément est définis par l'intermediaire de la relation d'équivalence entre ces différentes représentations. La donnée brute du modon constitue une représentation, et désigne un élément selon la relation d'équivalence qui est fixé dans le type du modon.
Lorsque la caractéristique externe, l'adresse du modon, est utilisée dans la définition de l'éléments qu'il contient, le modon n'est plus déplaçable par simple copie. Le concept de modon définie comme un conteneur, contenant un élément, devient moins pertinent, mais peut toujours être maintenu. La seul différence est que ce que nous appelons le contenue de bas niveau, contient non seulement la donnée brute, mais également l'adresse du modon, et plus exactement une adresse relative. (En effet comme on ne veut pas de référence absolu, l'adresse ne peut être que relative. Et elle est relative à un object parent implicite, qui devra être mentionné lors de son utilisation concrète.)
L'élément, le contenu du modon, est défini à partir de la donné brute du modon et de l'adresse physique du modon, ou d'une adresse relative à un autre object, le tout restreint de la même façon selon des règles syntaxiques (voir 2.3) et modulo une relation d'équivalence (voir 2.5), de tel sorte que certain de ces modons peuvent quant même être déplacés sous certaines règles et en subissant des transformations singulières.
Grace à ce nouveau genre de type, un modon indéplaçable peut contenir comme élément, une mémoire, voir un autre modon. Un élément définie mathématiquement, ne représente pas habituellement une mémoire, mais cela est possible et constitue un autre genre d'élément. Parcontre les règles permettant de garantir l'exclusivité d'accès à des donnés ou précisant le partage de donnés, peuvent devenir compliquées.
Enfin toute cette reflexion sert à bien construire les concepts de type, d'object et d'élément.
Le modon, comme tout type, est vu d'une manière mathématique comme l'ensemble de tous les éléments qu'il peut valoir. Le modon étant de taille fixe, il ne peut définir qu'un nombre fini d'éléments. L'élément correspond à un état macroscopique du modon, tandis que les états microscopiques sont appelés représentations, ou éléments de bas niveau. L'élément est une classe d'équivalence d'éléments de bas niveau. Le type du modon est un ensemble d'éléments, et c'est aussi un ensemble d'éléments de bas niveau.
Les opérations mathématiques fondamentales sur le modon, qui devront donc être mises en oeuvre dans le framwork, sont celles propres aux ensembles finis muni d'une relation d'équivalence.
La structure est dense si elle occupe le moins de mémoire possible. Et la structure est efficace si il y a peu de complexité dans les calculs qu'elle opère.
On définie l'entropie du modon contenant un élément, comme étant égale au logarithme en base 2 du nombre d'états microscopiques possible pour le même état macroscopique correspondant à l'élément en question. C'est le nombre de bits nécessaires pour compter les différents états microscopiques possibles du même état macroscopique concidéré.
Le modon est dit totalement dense si toutes les possibilités de configuration de bits sont autorisés et produisent des éléments distincts. Il s'en suit qu'une tel structure est d'entropie nulle.
Un moyen de parvenir à cette forme totalement dense consiste à énumérer les éléments que le modon peut engendrer, en un nombre égale à une puissance de deux, 2^n, et à le mémoriser par le biais de ce nombre sur exactement n bits.
Lorsque ce nombre n'est pas une puissance de deux, cela introduit, lorsque le dernier bits, le bit de point fort, vaut 1, des valeurs non prévues qui peuvent alors représenter des éléments déja énumérés et constituées des doublons ou constituées des configurations interdites. D'une manière générale, on dira que la structure est quasi-totalement dense si il existe un bit dans la configuration de bas niveau, et qu'on puisse choisir un représentant pour chaque élément, de tel sorte que tous les doublons et toutes les configurations interdites aient tous ce bit dans le même état.
Nous reprenons la discussion sur les pointeurs vue au chapitre Structuration informatique par le bas pour construire trois premiers types de modons, mettant en oeuvre cette opération informatique fondamentale qu'est l'adressage indirecte.
La mémoire se subdivise en une suite d'octets numérotés de 0 à 2^32. Le numéro de l'octet est son adresse physique, et tient sur un mot de 32 bits, soit 4 octets consécutifs. La mémoire contenant l'adresse est appelé un pointeur. L'addressage indirecte est une opération fondamentale qui consiste de façon imagée à partir d'un pointeur pour aller vers l'octet pointé, l'octet dont l'adresse est mémorisée dans le pointeur.
Le pointeur est nativement de taille 32 bits et pointe vers un bloc nativement de taille 8 bits. Si on incrémente le pointeur, celui-ci pointe sur le bloc suivant. Le pointeur constitura le modon de type P (Pointeur). Le bloc pointé constitura le modon de type B (Bloc), et l'ensemble des blocs pointables constitura le modon de type L (List).
L'adressage indirecte relatif est mis en oeuvre en appliquant au pointeur trois opérations très rapides (interne au CPU) que sont le shifftage, le masquage et la translation, le shifftage pour doubler ou diviser par deux la taille des blocs pointés consécutifs, le masquage pour réduire la taille des pointeurs ou pour réserver ses derniers bits à d'autres fonctionnalités, et la translation pour adresser le premier bloc d'adresse relative 0.
Il s'en suit que les blocs doivent avoir une taille en nombre de bits égale à une puissance de deux, B=2^b, et se succéder jointivement. La succession des blocs forme une liste de blocs numérotés de 0 à N-1. Et comme chaque valeur du pointeur doit pouvoir être utilisé afin que la structure de pointeur puisse être totalement dense, il s'en suit que N doit être aussi une puissance de 2, et que le pointeur est de taille n bits avec N = 2^n. La taille de la liste est donc égale à 2^b*2^n = 2^(b+n) bits.
De plus, certaine contrainte d'alignement doivent être respectées. Une structures doit commencer par un octet, parceque l'adresse physique de la structure est celle d'un octet. Pour permettre de placer des structures à n'importe quel endroit dans l'octect il faut compléter l'adresse avec 3 bits supplémentaire pour obtenir ainsi une adresse physique du bits.
On généralise la notion de pointeur en réservant u bits sur le pointeur pour d'autre fonctionnalité, et en réservant les w premières adresses comme éléments symboliques, des éléments qui ne possèdent pas de mémoire. La taille du pointeur est P = n + u bits. Le nombre d'adresses symboliques adressables est w, le nombre d'adresses réels adressables est N = 2^n - w
On a donc définie 3 premiers types de structure, trois types de modons premiers, totalement denses, sans faire de choix arbitraire :
Les adresses de 0 à w-1 sont réservées pour désigner les éléments symboliques qui n'ont pas de mémoire. Le premier bloc pointé est d'adresse w, et ne vaut donc pas toujours 0.
Le type bloc B(1) correspond à l'ensemble {0,1}
Le type bloc B(2) correspond à
l'ensemble {0,1,2,3}
Le type bloc B(3) correspond à
l'ensemble {0,1,2,3,4,5,6,7}
Le type liste L(1,2,3) correspond à l'ensemble {(0),
(1)}
Le type liste L(1,2,2) correspond à
l'ensemble {(0,0), (0,1), (1,0), (1,1)}
Le type liste L(1,2,1) correspond à
l'ensemble {(0,0,0), (0,0,1), (0,1,0), (0,1,1), (1,0,0), (1,0,1),
(1,1,0), (1,1,1)}
Le type de pointeur P(L,0,b,2,2) correspond à
l'ensemble {s1, s2, L[0], L[1]}
Le type de pointeur P(L,1,b,2,2)
correspond à l'ensemble {(0,s1), (0,s2), (0,L[0]), (0,L[1]), (1,s1),
(1,s2), (1,L[0]), (1,L[1])}
Le type de pointeur P(L,0,b,2,1)
correspond à l'ensemble {s1, L[0], L[1], L[2]}
Le type de pointeur P(L,0,b,2,0)
correspond à l'ensemble {L[0], L[1], L[2], L[3]}
L'object déplaçable n'inclut pas son adresse dans la définition de l'élément qu'il contient. L'adresse absolut ou relative peut être mémorisée par l'object lui-même ou par d'autres objects, mais cette mémorisation rompre la totale densité de la structure qui les mémorise. L'object indéplaçable inclut son adresse dans la définition de l'élément qu'il contient, sans la mémoriser. Si c'est une adresse relative à l'object X, alors il est indéplaçable relativement à X. Cela veut dire que X et tout les objects relatif à X peuvent être déplaçés en même temps par translation, que X et tous les objects nondéplaçables qui lui sont relatifs forment un object complexe, qui lui, est déplaçable.
L'adresse absolue n'a pas de sens en soi, tout est relatif, et l'indéplaçabilité est également relative. On note le type par le suffixe 1 le fait que le modon est indéplaçable et qu'il prend en compte son adresse relative sans la mémoriser pour déterminer l'élément qu'il contient. Et on note les types faisant référence à un autre type, par le suffixe 0 lorsque cet autre type est indéplaçable.
Une liste de 2^n - w blocs de type B1(b) consécutifs et relatif à la liste en question.
Une autre structure plus hétéroclite est accessible avec ce mécanisme rapide d'adressage indirecte. Et comme nous ne voulons pas faire de choix arbitraire, nous n'excluons pas cette autre voie. La taille des blocs est simplement différente du pas d'indexation, faisant que les blocs peuvent se chevaucher ou au contraire laisser des interstices. On ajoute donc un paramètre p définissant le pas d'indexation, distinct de b définissant la taille du bloc. Les interstices s'obtiennent plus simplement en réservant dans chaque bloc v bits, c'est pourquoi on ne concidèrera que le cas ou p < b, le cas ou les blocs se chevauchent, et qui constitue une première structure qui auto-partage ses données.
On veut classifier de la façon la moins arbitraire. On ne connait pas encore les critères qui déterminerons les grandes familles si ce n'est leurs caractères topologiques les plus visibles.
Lorsque les blocs de la liste contiennent des pointeurs vers d'autres blocs de la même liste, nous obtenons un graphe, une structure reflexive qui possède un fort pouvoir mésentropique. Le bloc et le pointeur étant de taille fixe, le nombre de tels pointeurs contenue dans un bloc est majorés, et dans les cas simple, il est fixe.
Dans une liste de blocs, le bloc peut contenir un pointeur pointant un autre blocs de la même liste. C'est cette configuration qui sera proposée par défaut. On dira que la liste se projette sur elle-même.
La première structure sera donc une auto-application (et d'une façon plus générale une k-auto-application).
Pour que la structure soit totalement dense il faut que la taille du bloc soit égale à la taille du pointeur. On pourrait ajouter un autre paramètre, le nombre de bits dans le bloc, réservés pour une autre fonctionnalité que celle du pointeur, mais ce paramètre existe déja dans le pointeur, c'est le paramètre u.
La liste comprend N = 2^n - w blocs adressables par le type de pointeur concidéré. La taille d'un bloc B est égale à la taille du pointeur B = P = n + u. Et le nombre de bits du bloc doit être égal à une puissance de deux, B = 2^b, soit des blocs de 1, 2 et 4 bits (plus petits que l'octet), et des blocs de 8, 16, 32 et 64 bits.... Il ne doit pas y avoir de bits non utilisés. Le pointeur doit pouvoir contenir exactement toutes les adresses relatives des blocs, c'est à dire les numéros des blocs, et pas d'avantage. Cela se traduit par les équations suivantes :
Nombre de blocs de la liste. Taille d'un bloc en nombre de bits. Taille d'un pointeur en nombre de bits Nombre de bits utilisés pour énumérer les N blocs et les w symboles. Nombre d'éléments symboliques (sans mémoire). Nombre de bits utilisés pour énumérer les B bits d'un bloc. Nombre de bits réservés à d'autre fonctionnalité dans le pointeur.
Le nombre d'éléments symboliques w auquel on ajoute le nombre de bloc adressables N, doit être une puissance de 2. La taille d'un bloc est une puissance de 2. Le pointeur peut exactement numéroter les w valeurs symboliques et tous les blocs de la liste. Le bloc contient exactement un pointeur.
Il y a donc 3 paramètres entiers b, n, u liés par l'équations : (n+u) = 2^b
La taille du bloc par défaut sera celle de l'octet (et non du mot de 32 bits qui peut adresser a priorie toute la mémoire) et la taille de la liste par défaut sera 2^8 = 256 blocs de tel sorte qu'un bloc contienne exactement une adresse désignant un bloc de la même liste. Le bloc par defaut sera donc un pointeur vers un bloc de la même liste. Les valeurs par défaut sont : u=0, b=3, n=8, w=0. la liste par défaut sera donc une auto-application de {0..255}.
On peut compliquer un peu, en considérant une liste de k-uplet de pointeurs, chaque bloc étant constitué de k pointeurs, pointant sur des blocs de la même liste. Cela correspond alors à une k-auto-applications. Lorsque k>1 on peut ajouter un autre paramètre v, le nombre de bits dans le bloc, réservés pour une autre fonctionnalité que celle des pointeurs sans que ce paramètre se superpose au paramètre u des pointeurs.
Nombre de pointeurs dans un bloc.
Le nombre d'éléments symboliques w auquel on ajoute le nombre de blocs adressables N, doit être une puissance de 2. La taille d'un bloc est une puissance de 2. Le pointeur peut exactement numéroter les w valeurs symboliques et tous les blocs de la liste. Le bloc contient exactement k pointeurs auquel on ajoute v bits réservés à d'autre fonctionnalité.
Il y a donc 5 paramètres entiers b, k, n, u, v liés par l'équations : (n+u)*k+v = 2^b
La seconde structure utilise deux listes, une liste de départ et une liste d'arrivée. C'est une k-application, les blocs de la liste de départ sont constitués de k-pointeurs pointants vers des blocs de la liste d'arrivé.
Les mathématiques nous guides sur l'importance et la pertinance des structures qu'il faut choisir et construire. L'application en est une, mais la fonction en est une autre. La fonction s'obtient à partir de l'application en ajoutant la possibilité de pointer sur rien, sur nil. On peut ajouter l'élément nil dans la liste d'arrivé et la fonction devient alors une application. Mais sa mémoire étant inutile, procéder comme cela romprait la totale densité. On choisie de définire un élement symbolique (sans mémoire) w=1. Tous se passe comme si un élément nil a été ajouté à la liste d'arrivé. Conventionnellement le nil est égale à zéro. Cela se fait alors en comptant les éléments de la liste à partir de 1 au lieu de 0, et en considérant l'adresse 0 comme un non lien, un lien vers l'élément symbolique nil qui n'est pas compté comme élément de la liste d'arrivé. La structure correspond alors à une k-fonction.
On peut généraliser cette opération en ajoutant, non pas 1 valeur particulière pour désigner le non-lien, mais w valeurs particulières pour désigner w non-liens distincts, des liens vers des éléments symboliques sans mémoire mais distincts. La structure correspond alors à une k-application sur {0..w-1}symboles union {w..N}éléments. Noter que N désigne la somme du nombre d'éléments avec mémoire, (N-w), et du nombre d'éléments symboliques, w.
Dans les k-applications ou k-auto-application, les blocs contenant k pointeurs possèdent finalement le type L(n+u,n',w') où n+u est la taille des pointeurs, et n' minimum et w' tel que 2^n' - w' = k. Il s'agit alors d'une liste de listes toujours optimisées pour possèder un pointeur spécifique totalement dense. On entrevoit ici la superposition des hierachies de types.
Dans les cas plus complexes le nombre de pointeurs par blocs est variables. Cela signifie qu'une partie du bloc détermine le nombre de pointeurs et forme ainsi une sorte de typage dynamique partiel, qu'une autre partie est constituée de la liste des pointeurs proprement dite, et qu'une dernière partie restante est de taille variable.
L'object général que nous entrevoyons est un modon, comprenant un nombre variable de sous-modons de mêmes types, une partie (éventuellement de taille variable) pour déterminer ce nombre, et une autre partie restante de taille variable. Mais avant de décrire ce type de modon, nous allons décrire un object plus simple, mais qui n'est pas un modon, une liste de taille variables de modons. Puis nous reprendrons notre construction en cours.
La liste de taille variable n'est pas un modon. Nous l'appelerons un varon. Le fait de donner un nom à un type générale permet d'ordonner notre conception des structures.
Le varon est un bloc contigüe de mémoire de taille variable déterminé par son type et par la lecture de ses données brutes dans l'ordre. L'adresse relative est concidérée comme la première donnée, puis les bits sont lus dans l'ordre selon leur poids, du poid faible au poid fort. Le type met en oeuvre un algorithme de lecture ordonnée déterminant le moment venu quand se termine le varon en intégrant dans celui-ci tous les bits qui ont été lu par l'algorithme et éventuellement d'autres bits suivants. L'algorithme peut ne jamais s'arréter si le varon n'a pas de fin et est de taille infinie, ou même s'arréter en proposant cette alternative. Cela s'applique à un flux aussi bien qu'à une mémoire de taille infinie tel le ruban d'une machine de Turing.
Soit le varon est indécomposable et alors on peut se poser des questions sur son intéropérabilité, soit il se decompose en sous-objects dont certains peuvent être en nombre variables. Nous ne pouvons pas proposer dans l'immédiat une vision exhaustive. Mais puisque nous avons posé deux types topologiquement différents que son le modon et le varon, et que nous envisageons en premier trois modes adjonctifs : singulier, de multiplicitée fixe et de multiplicité variable. Il s'en suit que nous envisageons en premier 6 classes : le varon contenant un modon, le varon contenant un nombre fixe de modons, le varon contenant un nombre variable de modons, et 3 autres classes similaires en remplaçant les modons par des varons.
Le varon contiendra nécessairement une partie supplémentaire spécifiant le typage dynamique partiel, c'est-à-dire complétant le type de ses sous-objects déja déclarés dans son type, et déterminant leur nombres.
Le type du varon donne l'algorithme permettant de déterminer la taille du varon en le lisant par le début, et donne les algorithmes nécessaires pour déterminer l'élément qu'il contient.
Un sous-object n'est pas une partie du contenu de l'object, c'est-à-dire n'est pas une partie de l'élément contenu par l'object. C'est le contenu du sous-object qui est une partie du contenu de l'object. Autrement dit, l'élément contenu par le sous-object est une partie de l'élément contenu par l'object.
Un type est un object. Un pointeur de type est un object.
Le type du varon ne précise pas complètement le type du modon, sinon il n'y aurait pas besoin de données supplémentaire pour compléter le type de modon à l'aide d'un typage dynamique partielle, et le varon serait de taille fixe et constiturait un modon.
Se pose la question de savoir si la référence à un type est de taille non borné ou suffisament grande pour qu'une implémentation en taille variable soit valable, ou non. Cela ouvre une question générale sur la nature du type.
Le type détermine le comportement de l'object.
Dans l'absolu, ne faisant aucun choix, le type et l'object ont un rôle symétrique complémentaire, et c'est la réunion des deux qui détermine l'élément qu'il désigne, de tel sorte que l'on peut concevoir des types distincts en nombres non borné pour des objects de petite taille. Par exemple considérons l'object déplacable constitué d'un seul bit, et considérons son type paramètré par l'entier n qui précise que l'objet désigne l'élément -n ou +n selon la valeur du bit. Nous avons ainsi défini un varon contenant un modon de taille fixe, et c'est la référence à son type qui est de taille variable. On pourrait penser que l'object et le type sont de même nature, leur rôle se différenciant par leur seul position relative. Mais concrètement on ne sait pas ce qu'est un type, car on met implicitement la donnée brute dans l'object et la sémentique dans le type. L'exemple précédent est en faite un varon contenant un varon désigant n et un modon désigant le signe, le reste comprenant toute la sémentique étant définie dans le type du varon contenant. Alors la question se repose, le type paramétrique étant décomposé en un type non paramètrique et des objects paramètres, peut-on considérer un nombre non borné de types non paramètriques distincts ?
On n'est pas dans la quantité mais dans la qualité, et donc le nombre de types non paramètriques distincts considérés est limité, à moins de concevoir des programmes de taille et de complexité gigantesque ou infini, le nombre de types, comme de sous-programmes, peut-être borné, à 1 Giga par exemple. Et comme on veut avoir une vision appréhendable et compréhensible de l'ensemble des types, cela nous ramène plutôt à 1 Kilo, voir seulement une centaine ou encore moins pour de petit programmes.
Le type constitue la matérialisation de la compréhension, ils constituent des points de concentration des analyses, qui si elles sont poussées, en réduisent le nombre par fusion et paramètrage (et hiérarchisation, analogie, superposition...)
Il s'en suit que la référence à un type est un modon de petite taille et que cette taille peut naturellement être encore réduite pour ne désigner qu'un nombre plus réduit de types, et que pour cette raison nous faisons le choix d'exclure l'implémentation d'une référence à un type, qui soit une référence de taille variable. Cela nous permet de garder toute la pertinence du critère topologique de la variabilité de la taille, comme moyen de classification.
Pour cette raison (la nature du type), le type du varon ne doit pas déterminer la taille du modon qu'il contient. Et il contient un second object qui est une référence au type dynamique partiel, qui vient compléter le type du modon, et dont une première partie est écrite dans le type du varon, et qui détermine entre autre la taille du modon.
Le varon contient en faite deux modons : une référence à un type dynamique partiel, et un modon. Et le typage dynamique partiel peut ne concerner que le modon, ou d'avantage. Dans ce dernier cas le varon intégre un typage dynamique partiel.
Il est nécessaire d'évoquer les objects ayant un typage dynamique partiel.
Le modon comprend une référence à un type partiel et un modon. Comme la référence à un type partiel est de taille fixe selon le choix (voir 6), il s'en suit que le modon contenue est toujours de même taille c'est à dire que le type partiel qui complète son type ne change pas sa taille. Il reste à déterminer si le type partiel complète le seul type du modon contenu ou également du modon contenant, et si cette distinction a lieu d'être....
Le type du varon peut préciser le type du modon avec des paramètres non précisés qui influent sur la taille du modon
Les paramètres forme une complétion du type, et peuvent jouer un rôle symétrique avec le type, de tel sorte que l'on pourrait inverser leur rôles et considérer les paramètres comme un type, et le type comme un paramètre..
Un cas simple : le varon contenant modon quelconque. Ce type de varon ne contient au préalable aucun renseignement sur le type de modon. Ces renseignements sont placés dans le varon et constitus un type dynamique. Le varon comprend simplement un pointeur de type suivi d'un modon de ce type.
....
L'étude des graphes orientés fait apparaitre un maillage sous-jacent servant de mémoire et qui constitue une sorte de grille sur laquelle repose le raisonnement. Selon les intuitionistes, le raisonnement s'identifie au fonctionnement d'une machine. Et ce constat empirique nous amène a considérer cette grille comme une partie non immédiatement visible mais nécessaire à la nature machiniste du raisonnement (de la même façon que les philosophes physiciens avait considéré l'atome comme une nécessité sans pourtant être en mesure de le percevoir directement).
La grille est une mémoire, et la mémoire se présente dans la plus simple configuration comme un flux de bits, c'est à dire une succession de bits. On regroupe ces bits dans une première quantification appelé mot pour pouvoir mémoriser une adresse ou un pointeur. Et cette quantification va limiter la taille de la mémoire adressable. La quantification la plus courante est le mot de 32 bits, c'est à dire de 4 octects, et permet de mémoriser 4 Giga adresses différentes. Si ces adresses sont utilisées pour adresser des blocks de 20 octets, cela permet d'utiliser 80 Giga octets de mémoires vive.
On effectue une deuxième quantification qu'est la cellule et qui regroupe deux mots consécutifs. La cellule peut ainsi mémoriser deux pointeurs, chaque pointeur pouvant désigner une autre cellule. La cellule peut représenter un noeud du graphe orienté et possèder deux fils. Le graphe orienté représente le monoïde engendré par les deux générateurs. Cette structure de données de bas niveau appelée grille, est la structure utilisée par l'interpréteur du langage LISP.
La cellule est identifiée par sa position dans la grille. Et elle mémorise deux pointeurs. Lorsqu'elle est utilisée, elle désigne un élément du monoïde. Son premier pointeur pointe sur la cellule représentant l'élément obtenue en le multipliant selon la loi * du monoïde par le premier générateur, et son second pointeur pointe sur la cellule représentant l'élément obtenue en le multipliant par le second générateur. Comme la construction passe nécessairement par une phase incomplète, on autorise une autre valeur pour ces pointeurs, qu'est la valeur Nil, et qui signifie que l'élément produit est non encore déterminé ou plus exactement non encore exploré.
On se place dans un cas un peu plus général où la cellule est composée non pas seulement de deux mots consécutifs mais d'un premier bloc de g mots consécutifs correspondant à g générateurs, d'un mot supplémentaire pour mémoriser une redirection vers un autre noeud, d'un mot supplémentaire pour mémoriser une relation vers un autre noeud, et d'un mot supplémentaire pour mémoriser différentes informations relatives au noeud en question.
Le varon comprenant un nombre variable de blocs de taille B et éventuellement une partie déterminant ce nombre. Ce varon n'est donc pas de taille fixe déterminé par un type static (déclaré avant). Seul la taille des blocs B est déterminé. Le nombre de blocs de taille B sera soit limité par le type du varon ou non limité.
Il y a a priori 4 façons courantes d'implémenter cette liste variables : une liste comptée, une liste chainée, une liste comptée-chainée ou une liste avec fin.
4.3.1.1) Liste comptée
Un bloc de taille m bits est réservé pour déterminer le nombre de bloc de taille B. Ce nombre varie donc de 0 à 2^m - 1. La taille de la liste doit donc être supérieur ou égale à m + 2^m * B et cela pour assurer sa totale densité. En effet si la taille s'avère plus petite, le nombre maximum de blocs sera déterminé par plusieurs valeurs, la valeur maximum et les suivantes.
Dans le cas plus générale on peut n'autoriser que quelques valeurs discrètes, comme nombre de blocs de taille B, selon une échelle monotone déterminé par le type de la liste. Les valeurs sont rangées dans l'ordre, V[i] indique le nombre de bloc correspondant au nombre i. Le problème est identique il doit y a voir 2^m valeurs, et la taille de la liste doit être supérieur ou égale à m + B*V[2^m-1]. Reste à trouver un sense sémantique à cette discrétisation des nombres de blocs.
L'autre difficulté est de trouver un sense sémantique au bloc restant, une quantité d'information variable de tel sorte que la quantité totale d'information par sommet soit fixe.
4.3.1.2) Liste de bits collés
Pour des raisons d'alignement on ne peut pas intercaler un bit entre des blocs plus gros, cela rallentirait l'adressage indirecte. Un cas particulier se produit pour les blocs constitués d'un seul bit. Dans ce cas la chaine est une suite alterné de bits de colle et de bits de données qui commence par un bit de colle et qui finie par un bit de colle. Lorsque tout l'espace est utilisé et qu'il reste un bit de colle celui-ci est redondant. Pour garantir la totale densité, ce bit final ne doit pas exister et la taille de la liste en nombre de bits doit donc être paire.
Cela revient à un comptage par baton répartie tout au long de la donnée.
4.3.1.3) Liste chainée
L'information de chainage qui vaut un seul bit, devra être intégré au bloc et vaut 1 lorsque un bloc suivant existe et 0 lorsque il n'y a pas de bloc suivant. Cette liste chainée n'est pas vide, elle contient obligatoirement au moins un élément. Et lorsque tout l'espace est utilisé, l'information de chainage devient redondante. Il faut lui donner un sens supplémentaire pour garentire la totale densité. On dira, lorsque tout l'espace est utilisé, et que le dernier bloc possède ce bit à 1, que le sommet du graphe est pointé.
Cela revient à un comptage par baton répartie tout au long de la donnée, commençant à 1 et finissant à une valeur X pouvant être pointé.
4.3.1.3) Liste comptée-chainée
Le procédé mixte revient à un comptage séparé répartie tout au long de la donnée. Un bloc de taille m bits est réservé pour déterminer le nombre de bloc de taille B, et est suivis d'un second bloc de taille m bits pour déterminer le nombre de bloc de taille B suivants, et ainsi de suite.
L'information de chainage qui vaut un seul bit, devra être intégré au bloc et vaut 1 lorsque un bloc suivant existe et 0 lorsque il n'y a pas de bloc suivant. Cette liste chainée n'est pas vide, elle contient obligatoirement au moins un élément. Et lorsque tout l'espace est utilisé, l'information de chainage devient redondante. Il faut lui donner un sens supplémentaire pour garentire la totale densité. On dira, lorsque tout l'espace est utilisé, et que le dernier bloc possède ce bit à 1, que le sommet du graphe est pointé.
Cela revient à un comptage par baton répartie tout au long de la donnée, commençant à 1 et finissant à une valeur X pouvant être pointé.
4.3.1.4) Liste avec fin
On réserve une valeur particulière de bloc pour désigner la fin de la liste des blocs consécutifs. Lorsque tout l'espace est utilisé l'information de fin de chaine n'existe pas de tel sorte qu'il n'y a pas de redondance.
4.3.1) Les listes variables
On défini un modon appellé liste variable, comprenant un nombre variable de blocs de taille B et un bloc restant, et éventuellement un bloc déterminant ce nombre. Ce modon étant de taille fixe déterminé par un type static (déclaré avant), le nombre de blocs de taille B sera donc limité par la taille de la liste et il peut l'être naturellement par le type de la liste lui-même. On considérera qu'il est limité par le type de la liste qui par cohérence respectera évidement sa taille.
Il y a a priori 4 façons courantes d'implémenter cette liste variables : une liste comptée, une liste chainée, une liste comptée-chainée ou une liste avec fin.
4.3.1.1) Liste comptée
Un bloc de taille m bits est réservé pour déterminer le nombre de bloc de taille B. Ce nombre varie donc de 0 à 2^m - 1. La taille de la liste doit donc être supérieur ou égale à m + 2^m * B et cela pour assurer sa totale densité. En effet si la taille s'avère plus petite, le nombre maximum de blocs sera déterminé par plusieurs valeurs, la valeur maximum et les suivantes.
Dans le cas plus générale on peut n'autoriser que quelques valeurs discrètes, comme nombre de blocs de taille B, selon une échelle monotone déterminé par le type de la liste. Les valeurs sont rangées dans l'ordre, V[i] indique le nombre de bloc correspondant au nombre i. Le problème est identique il doit y a voir 2^m valeurs, et la taille de la liste doit être supérieur ou égale à m + B*V[2^m-1]. Reste à trouver un sense sémantique à cette discrétisation des nombres de blocs.
L'autre difficulté est de trouver un sense sémantique au bloc restant, une quantité d'information variable de tel sorte que la quantité totale d'information par sommet soit fixe.
4.3.1.2) Liste de bits collés
Pour des raisons d'alignement on ne peut pas intercaler un bit entre des blocs plus gros, cela rallentirait l'adressage indirecte. Un cas particulier se produit pour les blocs constitués d'un seul bit. Dans ce cas la chaine est une suite alterné de bits de colle et de bits de données qui commence par un bit de colle et qui finie par un bit de colle. Lorsque tout l'espace est utilisé et qu'il reste un bit de colle celui-ci est redondant. Pour garantir la totale densité, ce bit final ne doit pas exister et la taille de la liste en nombre de bits doit donc être paire.
Cela revient à un comptage par baton répartie tout au long de la donnée.
4.3.1.3) Liste chainée
L'information de chainage qui vaut un seul bit, devra être intégré au bloc et vaut 1 lorsque un bloc suivant existe et 0 lorsque il n'y a pas de bloc suivant. Cette liste chainée n'est pas vide, elle contient obligatoirement au moins un élément. Et lorsque tout l'espace est utilisé, l'information de chainage devient redondante. Il faut lui donner un sens supplémentaire pour garentire la totale densité. On dira, lorsque tout l'espace est utilisé, et que le dernier bloc possède ce bit à 1, que le sommet du graphe est pointé.
Cela revient à un comptage par baton répartie tout au long de la donnée, commençant à 1 et finissant à une valeur X pouvant être pointé.
4.3.1.3) Liste comptée-chainée
Le procédé mixte revient à un comptage séparé répartie tout au long de la donnée. Un bloc de taille m bits est réservé pour déterminer le nombre de bloc de taille B, et est suivis d'un second bloc de taille m bits pour déterminer le nombre de bloc de taille B suivants, et ainsi de suite.
L'information de chainage qui vaut un seul bit, devra être intégré au bloc et vaut 1 lorsque un bloc suivant existe et 0 lorsque il n'y a pas de bloc suivant. Cette liste chainée n'est pas vide, elle contient obligatoirement au moins un élément. Et lorsque tout l'espace est utilisé, l'information de chainage devient redondante. Il faut lui donner un sens supplémentaire pour garentire la totale densité. On dira, lorsque tout l'espace est utilisé, et que le dernier bloc possède ce bit à 1, que le sommet du graphe est pointé.
Cela revient à un comptage par baton répartie tout au long de la donnée, commençant à 1 et finissant à une valeur X pouvant être pointé.
4.3.1.4) Liste avec fin
On réserve une valeur particulière de bloc pour désigner la fin de la liste des blocs consécutifs. Lorsque tout l'espace est utilisé l'information de fin de chaine n'existe pas de tel sorte qu'il n'y a pas de redondance.
Il existe d'autre transformation rapide qui peut être appliquée aux pointeurs : not, and, or, xor, ++, --, <<, >>, +, -, et avec le processeur arithmetique *, et qui vont faire aparaître de nouvelles structures de données de bases.
3) Les permutations
La permutation s'obtient plus difficilement.
C'est aussi une auto-application
Construisont toutes les permutations sur {0..N} dans un ordre natif : Le premier élément (l'élément numéro 0) peut être envoyé sur n'importe quel élément, soit un élément de 0 à N-1. Le second élément peut être envoyé sur les éléments restants que l'on peut renuméroter de 0 à N-2. Et ainsi de suite. Il y a bien N! permutations possibles, et chacune d'elle correspond à une suite de N termes dont le terme n°1 est pris parmi 0..N-1, le terme n°2 est pris parmi 0..N-2, le terme n°x est pris parmi 0..N-x, et le terme n°N vaut 0. La structure ainsi construite n'est ni dense ni efficace.
Une représentation dense est obtenue par le numéro natif de la permutation compris entre 1 et N!.
Peut t'on trouver une structure représentant une permutation qui soit à la fois dense et de complexité faible pour le calcule de l'image d'un élément ?.
4) Les classes
Le type d'un object est également un object appelé classe. Une classe est un object et possède un type qui est donc lui-même une classe. Aussi le terme de type est-il synonyme de classe et aussi de structure mais avec cette différence coutumière que le terme de structure sera souvent employé par abstraction pour désigner non pas la déclaration de la structure proprement dite mais un object générique ayant cette structure.
Les classes sont des objects en nombre limité qu'il n'est pas nécessaire de densifier.
Nous avons déja évoqué 3 types : la classe des blocs B(b), la classe des listes L(b,n,w) et la classe des pointeurs P(E0,u,b,n,w). On définie maintenant un quatrième type, la classe des symboles S(X) où X est un paramètre égale à un type donné. S(X) est la classe des éléments symboliques de type X. Cela ressemble au object de type X à part que cela ne possède aucune mémoire et donc pas d'adresse physique. Autrement dit, l'élément symbolique est une sorte de photo instantané de l'état de la mémoire d'un object de type X, une photo figé dans le temps, et référencé par un symbole dont le nom est la données même, qui comme l'identifiant de symbole S(X), est une caractéristique externe, non contenue dans l'object, mais contenue dans la classe.
5) Les superpositions inclusives
La structure mère étant totalement dense, une superpositions inclusives est simplement une structure de taille plus-petite ou égale partageant le même espace mémoire. Une superpositions inclusives d'une structure totalement dense est une structure qui n'admet pas de configration de bits invalides, néanmoins elle peut être d'entropie non nulle. Toutes les configuration de bits doivent être valides mais deux configurations distinctes peuvent désigner le même objects.
...
(voir Les ensembles, et la dénombrabilité et La calculabilité des ensembles ),
Quotientage et concrétisation
...
Notre discution pour l'instant n'a porté que sur des ensembles dit énumérés. Considérons maintenant des ensembles infinies. Ils sont énumérables mais pas énumérés, car la mémoire, comme le temps de calcul, est finie. La structure met en oeuvre le procédé de constructions des éléments de l'ensemble, et ne construit pas tous les éléments, voir n'en construit aucun. l'ensemble infini dénombrable est définie par le procédé de production de ses éléments. Le procédé se scinde conceptuellement en deux partie l'une est la source, l'ensemble père qui est l'ensemble des entiers naturels, et l'autre est la transformation qui va convertir l'entier en un élément. En cela le procédé de production énumère l'ensemble. Exception faite si la source est externe à la machine et ne peut donc être ramené à la donnée d'entropie nulle qu'est l'entier naturel. Une tel source peut ne pas être énumérable (et être non calculable) auquel cas son adjonction va augmenter le domaine des ensembles énumérables (et augmenter le domaine des fonctions calculables).
3) Les conceptes mathématiques avancés
Les hypothèses sont propositionels et procédurale. On possède les algorithmes de calcul d'opération +,-,*,/ sur un ensemble
| uint8_t | 1 octet | 0 à 255 |
| uint16_t | 2 octets | 0 à 65 535 |
| uint32_t | 4 octets | 0 à 4 294 967 295 |
|
uint64_t |
8 octets | 0 à 18 446 744 073 709 551 615 |
On n'utilisera pas les fonctions C avec ellipse, avec un nombre variable d'arguments. On utilisera à la place des mini-interpréteurs. Cela nécessite de formaliser un langage de programmation intermédiaire. Chaque objet comprend des méthodes de lecture et d'écriture, transformant l'objet en une chaine de caractère et vis-versa. La chaine de caractère représente l'objet dans le langage de programmation intermédiaire.
Les Piles et les Files sont représentées par une liste d'entiers entre parenthèse séparés par des virgules ou par des caractères blancs. Ainsi pour créer une pile d'éléments 2, 5, 7, 3, 12, les instructions suivantes sont équivalentes :
Pile A;
A.Empile(2);
A.Empile(5);
A.Empile(7);
A.Empile(3);
A.Empile(12);Pile A;
istrstream s( "(2,5,7,3,12)" );
s >>A;
2) Les objets généraux
On décide de créer des objets plus généraux pouvant être soit une Pile ou une File et donc le langage de programmation intermédiaire se perfectionne en conséquence. L'objet Pile sera représenté par le mot Pile suivie par sa liste d'éléments, et l'objet File sera représenté par le mot File suivie par sa liste d'éléments. Ainsi la pile précédante est représentée par "Pile(2,5,7,3,12)", et sera créée par les instructions suivantes :
ObjetGeneral A;
istrstream s( "Pile(2,5,7,3,12)" );
s >>A;
L'objet général hérite de tous les objets qu'il désigne et met en oeuvre un mécanisme de typage dynamique qui allourdie l'exécution (consommation de mémoire et de temps CPU).
On peut contourner cette difficulté en rendant systématique un niveau d'interpretation. Pour cela il faut formaliser un langage de programmation intermediaire qui soit complet et qui constitura au final une partie de notre langage évolué.
3) Le langage de programmation intermédiaire
Ce langage peut se liberer des containtes du langage C++ et épouser les règles d'un langage d'opérateurs d'arité fixe ou variable en intégrant les règles syntaxiques des opétateurs avec leur priorités. La question devient alors beaucoup plus générale : Quel langage évolué voulons nous utiliser. Etant libéré des contraintes du C++, on quitte l'analyse par le bas que nous étions en train d'opérer, pour une analyse par le haut. Et nous réecrivons toutes les opérations que nous avons programmées dans un nouveau langage idéal, dégagé des contraintes liées à la programmation C++.
3.1) Les entiers
Il y a trois sortes d'entiers, les entiers signés sur 8 bits, les entiers signés sur 32 bits et les entiers signés de taille variables. Nous ne les différencions pas dans le nouveau langage. La conversion se fera lorsque nécessaire.
Nous définissons le concept d'entier dans ce nouveau langage indépendemment des contraintes de programmation en C++. C'est notre premier type d'objet.
3.2) Les objets
Un objet possède un type, tel le type entier. Puis il possèdes des arguments qui sont d'autres objets, en nombre fixe ou variables. Un objet est ainsi composé d'une liste de sous-objets.
Quand n'est-il de la chaine de caractère ?. C'est un objet possèdant une liste de caractères avec caractère de fin de liste. Le caractère étant un entier compris entre -128 et 127, le caractère de fin de liste étant 0.
Il y a donc deux genres d'objets aux nombres variables d'arguments, ceux avec une liste d'argument avec fin de liste, et ceux avec une liste d'argument de taille variable. Le premier genre se décline uniquement pour des listes d'arguments qui sont des caractères. En effet pour des arguments de plus grande taille, ce procédé de construction de liste avec fin de liste n'est plus pertinant.
Lorsque le nombre d'argument est variables, on pose qu'ils ont tous le même type. On verra que cette restriction ne réduit pas outremesure le pouvoir d'expression des objets ainsi définis.
Il y a donc trois genres d'objet. Un genre constitué d'un type (faisant partie de ce genre) et d'une chaine de caractère. Un second genre constitué d'un type (faisant partie de ce genre) et d'une liste d'objets de même type. Un troisième genre constitué d'un type (faisant partie de ce genre) et d'un n-uplet d'objets de type divers précisés par le type en question. Le premier genre sera appelé chaine, le second genre sera appelé suite, le troisième genre sera appelé produit.
Dernière remarque, est-il necessaire de concidérer plusieurs type de genre chaine, sachant que l'on peut construire un type produit d'une chaine et d'un entier ?. Bien évidement non, c'est pourquoi le genre chaine ne contient qu'un seul type dit type chaine. De même le genre entier ne contient qu'un seul type dit type entier.
Le type d'un objet est aussi appelé classe. Une classe est un ensemble, l'ensemble des objets de la classe. Les ensembles finis ont une représentation unique à bijection près. On défini donc le type ensemble fini de n éléments, que l'on note Zn, que l'on appel entiers modulo n, et qui représente l'ensemble des n premiers entiers {0,1,2,... n-1}. Pour la même raison que celle des entiers, il n'est pas utile de considérer plusieur type d'entier modulo n.
D'un point de vue mathématique le type Chaine est équivalent au type Entier. Il peut donc être enlevé. Mais pour des raisons de convivialités, on le laisse.
Le type peut être construit comme un mot d'un langage possédant les règles de construction suivantes : Le type Entier est désigné par la lettre Z. Le type entier modulo n est représenté par le symbole paramètré Zn. Le type chaines est représentés par la lettre S. Le type suite est obtenu par l'opération de Kleen * appliqué à un type quelconque A. Le type produit est obtenue par le produit de deux types quelconques A et B :
A et B sont des variables muettes désignant n'importe quel type (ou classe)
Le type s'exprime dans un langage régulier, et on peut ajouter l'opération supplementaire d'union tout en restant dans ce langage régulier. C'est pourquoi cette opération est opportune, elle découle de source pour redonner toute la généralité au concepte de type sans entraver sa simplicité. Le type A union B, noté A|B, est le type représentant un objet de type A ou de type B :
La suite est prioriraire au produit qui est prioritaire sur l'union. Par exemple un objet de type (Z|S)(Z3.S)* est constitué d'un entier ou d'une chaine suivie d'une suite de couples composés d'un entier modulo 3 et d'une chaine.
On verra plus tard que l'on peut construire des objets plus savants dont le type ne peut s'exprimer dans un langage régulier.
On peut ajouter un type supplémentaire. le type lui-même est un objet d'un type particulier. On l'appel le type Type et on le désigne par la lettre T.
Notre esprit cartesien nous fait privilègier les n-uplet et les suites, mais nous pouvons concevoir des objets qui sont des mots d'une grammaire. Le type Type en est un exemple.
Les types sont des structures, et les procédés de construction de nouveaux types à partir d'autres types induisent des procédés de construction de nouvelles structures à partir d'autres structures.
La formalisation d'un langage passe d'abord par la formalisation d'un procédé de construction des structures. C'est pourquoi il nous faut d'abord étudier les catégories qui sont les structures vues d'une façon plus générale.
Il existe une analogie entre le concept informatique objet élémentaire-méthodes et le concept en physique particules-champs. La particule représente un objet élémentaire, un bloc mémoire contigü, et le champ qu'elle émet représente la méthode qui émane de l'object.
La méthode possède une forme d'object que sont les scripts mettant en oeuvre la méthode. Un script peut être écrit dans différent langage, et.peut être dupliqué pour agire parallèlement sur différents objects cibles, tel l'action d'un champ sur différentes particules.
Il y a donc deux formes générales que sont l'implicite et l'explicite, l'acceptant et l'énumérant. Cet aspect constitue la topologie du type. La topologie étudie le type par le haut, en utiilisant le concept générale de transformation quelconque, puis combine ces transformations, procédant alors à une construction par le bas, pour en développer les différentes variétées.
2.1.1) Le procédé implicite (acceptant)
Le procédé implicite s'exprime par une fonction caractéristique X qui appliqué à un modon m retourne true ou false selon que le modon est du type considéré ou non, et ceci en un temps fini. On peut généraliser en enlevant cette dernière propriété et en ajoutant ainsi une troisième réponse oracle possible qu'est l'infini de Turing. Ce pose alors la question de savoir si dans ce troisième cas, le modon est du type considéré ou non ? L'infini de Turing signifit que la question n'est pas tranché, et le fait de trancher la question pour une valeur va modifier le type, et cette modification ne portera que sur les valeurs non encore tranchés qui seront alors tranchées pour certaines d'entre elles. Autrement dit, la complétion d'un type, la complétion d'une fonction caractéristique de typage, est analogue à la complétion d'une théorie.
Le procédé ou la fonction implicite sera dite complète ou incomplète, et le type sera dit complet ou incomplet.
2.1.2) Le procédé explicite (énumérant)
Le procédé explicite s'exprime par une fonction énumérante f. C'est une fonction qui s'applique à un object x d'un type initial pour retourner un modon m du type considéré, et cela en un temps fini. On peut généraliser en enlevant cette dernière propriété et en ajoutant ainsi une réponse oracle supplémentaire qu'est l'infini de Turing. L'infini de Turing signifit ici que la réponse n'arrive jamais. Ainsi pour assurer l'énumérabilité exhaustive, on est obligé de cumuler en parallèle les calculs des infinis de Turing (minimisation), faisant qu'une quantité de mémoire non bornée est nécessaire, ce qui constitue une caractéristique topologique.
La fonction énumérable sera dite directe (sans minimisation) ou indirecte (avec minimisation). Le type sera dit énumérable s'il est constitué d'une fonction énumérable directe à partir d'un type énumérable. Cette définition récursive nécessite de définir un type énumarable initial. Ce type est celui des entiers naturels dont on édudira plus tard une implémentation.
2.1.3) les variétées
La combinaison de ces deux sortes de procédé de base, va produire toute une variété de procédés plus élaborés.
Fonction calculable (synonyme : partiellement recurcive)
Fonction totalement calculable (synonyme : totalement recurcive)
Ensemble calculable (synonymes : recurcif, décidable) : Il existe une fonction calculable f acceptante (f(x)=1 ssi x présent, f(x=0 ssi x absent)
Ensemble calculablement énumérable (synonymes : recurcivement énumérable, semi-décidable) : Il existe une fonction calculable f semi-acceptante (f(x)=1 si x présent). Souvent f ne retourne que 1 ou l'infinit de Turing et l'ensemble correspond dans ce cas au domaine de calculabilité de f (domaine de définition de f) domaine de f.
Relation calculable
Relation calculablement énumérable
l'énumération n'est pas garantie en un temps finie Autrement dit, la complétion du type, de la fonction caractéristique de typage, est analogue à la complétion d'une théorie. Le procédé ou la fonction implicite sera dite complète ou incomplète, et le type sera dit complet ou incomplet.
Les entiers naturels constituent une structure clé. La fonction énumérante classique s'applique à un entier pour retourner un modon de type considéré.
3 formes apparaisent qui peuvent après se combiner :
Construction typée {a,b,f(.)Xf(.),g(.,.)Xg(.,.)}