Qu'est-ce qui génère le concept, l'idée structurante ?. Cela nécessite un lieu et une opportunité, "ici et maintenant" disent les révolutionnaires. Toute la difficultée consiste à générer une explication qui relève davantage de la psychanalyse que des mathématiques. Créer des concepts qui soient pertinents, et qui prédisposent. Voila notre première démarche, qui est une sorte d'induction créatrice. Donc inévitablement sujette à des choix arbitraires. Subjective par nécessitée dirons-nous.
Il existe une approche objective des plus solides et qui constitue la ligne directrice de nos travaux, celle décrite par les intuitionnistes et qui ramène les mathématiques au monde des machines. La difficulté reste néanmoins entière, et consiste à choisir le moins arbitrairement possible une machine.
Qu'est ce qu'une théorie mathématique ?. Nous allons traiter des théories en générale. On ne doit pas s'autosaisir afin de limiter l'arbitraire. On nous soumet un problème. On remarque qu'une des prédispositions à la résolution du problème est le langage dans lequel il peut être écrit. Puis, les mathématiques étant une science hypothético-déductive exacte, vient l'hypothèse finie, appréhendable, une énumération finie de propriétées écrites dans ce même langage qui peut être augmenté au cas ou la nature disible de l'hypothèse est plus complexe que celle du problème.
On réunit les deux concepts que sont le langage et la théorie dans un troisième concept appelé structure. La structure est l'objet mathématique que nous privilègions vis à vis de la démonstration. La démonstration n'est qu'un moyen de vérifier l'intégrité de la structure, une autopsie en quelque sorte. Le concept de structure possède l'avantage de se rapprocher du vivant et de l'informatique, et va nous donner un point d'appuis pour hiérarchiser les langages et meta-langages dans une pile de protocoles.
Un langage est une machine, un processus qui énumère tous ses mots. Une théorie est une machine, un processus qui énumère toutes les propositions qu'elle peut démontrer. La description du moteur d'un langage se fait à l'aide d'un méta langage. De même la description du moteur de la théorie se fait à l'aide d'une méta théorie utilisant ce meta langage.
Pour les intuitionnistes, un ensemble est une machine, un processus qui énumère ses éléments. Décrire l'ensemble consiste à décrire le processus dans un langage augmenté en un langage de programmation. Un interpreteur prend comme entrée un programme et une donnée, et interprète le programme avec la donnée, et il n'y a pas de différence de nature entre le programme et la donnée. Le programme peut être écrit sous forme d'une donnée et la donnée peut être un programme. Mais Il existe un non-dit qu'est l'implémentation des programmes et des données, et qui consiste à quantifier les opérations et à quantifier les données.
Nous voulons construire pas à pas une structure, c'est à dire un langage et une théorie, à la manière intuitionniste en respectant la plus grande généralité qu'il nous est possible de percevoir, et nous allons établir les liens existant entre structure mathématique et structure informatique.
Pour désigner les éléments, on choisie un langage d'opérateurs, langage libre extrêmement générale et répandu (voir Langage d'opérateurs). Il se définie par un ensemble d'opérateurs générateurs. Par exemples :
L = {a, f(.), g(.,.)}
A chaque langage correspond une structure libre de même nom qui comprend tout les termes clos exprimables par le langage.
L = <a,f(.),g(.,.)>
L = {a, f(a), g(a,a), g(a,f(a)), g(f(a),a), g(f(a),f(a)), g(a,g(a,a)), g(a,g(a,f(a)))...}
Les crochets <...> expriment la cloture par composition close.
La structure est libre, c'est à dire qu'il n'existe aucune règle de simplification. Deux termes distincts du langage L désignent nécessairement deux éléments distincts de la structure.
Le langage est une machine, un processus, qui énumère les termes du langage en question. Ce processus n'est pas complètement décrit dans la présentation du langage. Il est implicite et consiste en la libre composition des opérateurs du langage. On va l'expliciter grace à un meta-langage, un langage augmenté permettant d'écrire un programme et des règles de productions. Mais la question peut-être abordée d'une manière plus générale. Comment écrire, et donc programmer, un processus qui énumère un sous-ensemble éventuellement infini de termes de L. L'écriture d'un tel processus se fait dans un langage augmenté de quelques opérateurs permettant d'écrire un programme.
Il apparait alors un préalable nécessaire : Rendre explicite l'implémentation des programmes et l'implémentation des données.
D'un point de vue informatique, il y a deux cas de figure, soit la donnée est de taille bornée, auquel cas on parlera d'un paramètre, soit elle ne l'est pas, auquel cas on parlera d'un flux de données.
Une donnée non bornée va être transmise dans un flux. La donnée est un terme du langage c'est à dire une composition close d'opérateurs générateurs, mais dans laquelle on n'évalue aucun opérateur.
Et en se laissant guider par l'ébauche de structure du flux, et en y apportant le moins de restrictions possibles, nous sommes naturellement amenés à considérer un flux de termes, et non plus un flux contenant un terme unique.
Le langage d'opérateurs peut être ramené en un langage de caractères en enlevant les parenthèses et les virgules et en considérant chaque opérateur comme un caractère. Le flux d'opérateurs devient un flux de caractères. Le flux de termes devient un flux de mots. L'arité des opérateurs générateurs est fixés préalablement dans la définition d'un langage et cette information n'est pas transmise dans le message, mais est préalablement connue.
Un message désigne une portion contigüe quelconque du flux de caractères et se terminer par le symbole nil de fin de message qui signale une coupure arbitraire dans le flux. Prenons par exemple le terme suivant :
f(f(a,s(a)),f(a,s(a)))
Les données sont mémorisées dans des cases succécives numérotées ici de 0 à 9. Les données sont quantifiées : Une donnée est une référence à un opérateur appartenant à L ou correspond au symbole nil.
Le nil fait partie d'un méta-langage, au dessous du langage dans la pile des protocoles, un protocole de bas niveau, et il désigne la fin du message.
ffasafasa
On ajoute après coups les parenthèses, qui apportent une information supplémentaire qu'est l'arité de chaque opérateur défini dans L, mais qui n'est pas transmise dans le message :
f(f(a,s(a)),f(a,s(a)))
Le message est donc constitué d'une succession quelconque d'opérateurs de L terminées par un meta-opérateur nil de bas niveau. Et il constitue une liste de termes dite terminale-close, c'est à dire que seul le dernier terme peut ne pas être clos. Et dans ce terme, dit terminal-clos, les fils libres, représentés par des point ".", sont tous groupés à la fin du terme. Voici quelques exemples :
Message en
logique polonaise Liste de termes terminale-close f f(.,.) ff f(f(.,.),.) a a fa f(a,.) af a, f(.,.) ffabf f(f(a,b),f(.,.)) aabsfa a, a, b, s(a), f(a,.) fabfaab f(a,b), f(a,a), b afa a, f(a,.)
Un terme terminal-clos possède des fils libres, représentés par des points, placés en fin de terme, et qui seront affectés par les termes transmis dans les messages suivants dans l'ordre de leur arrivés.
Le message constitue une liste d'opérateurs. Chaque opérateur a une adresse relative dans cette liste en commençant par zéro.
Un sous-terme peut être partagé, c'est à dire qu'il apparait plusieurs fois, il peut même être répété indéfiniment de manière récurcive, mais sa mémorisation n'est faite qu'une fois. Cela s'implémente grâce à des opérateurs spéciaux appelés pointeur qui sont des entiers variant de 0 à N-1 où N est le nombre d'opérateurs du messages, et qui pointe dans le message des sous-termes partagés.
Terme avec partage Apparence f(s(a),1) f(s(a),s(a)) s(0) s(s(s(...))) f(a,0) f(a,f(a,f(a,...))) s(1) s(...) 0 ... f(2,1) f(...,...)
Le terme devient alors un graphe.
La quantité de mémoire est exprimée en bits. Les logarithmes sont en base 2 car l'unité est le bit. Une case mémoire contenant un opérateur de L, c'est à dire a, b, s, f, ou ne contenant rien c'est à dire nil, contient un choix parmis 5 possibilitées, auxquelles il faux ajouter les possibilités de partages. Celle-ci dépendent de la longueur du message. Par exemple si nous considérons des messages de 8 opérateurs, il faux alors considérer les opérateurs spéciaux 0,1,2,3,4,5,6,7, soit un totale de 5+8=13 possibilités.
Cette donnée élémentaire correspond à une quantité de log(13) = 3,7 bits soit d'un point de vue pratique, à 4 bits, et cela permet le codage suivant par exemple :
Opérateur Codage
binaire 0 000 1 001 2 010 3 011 4 100 5 101 6 110 7 111 a 1000 b 1001 s 1010 f 1011 nil 1111
Ainsi un message de 8 opérateurs de L tel que f(f(4,a),f(2,s(0)) est mémorisable sur 8*4 = 32 bits.
Les cases mémoires constituent les briques élémentaires d'un système de mémoire.
En bon ordre dans la conception d'une application, il convient de programmer en premier la gestion de la mémoire. Une des opérations clef de l'ordinateur consiste en l'adressage indirecte indexé.
La mémoire est composée d'une succession contiguë de 2n cellules de taille fixe. Chaque cellule est composé d'une successions contiguë de K briques de taille fixe. Chaque brique contient soit une donnée, soit un pointeurs. Le pointeur est un entiers compris entre 0 et 2n-1. Chaque pointeur doit pointer vers une cellule ou désigner un symbole.
La mémoire ainsi organisée forme une structure de données, un graphe complexe qui peut être appréhendé comme un système thermodynamique, un système de mémoire. Plusieurs organisations sont possibles. Pour pleinement exploiter la puissance mésentropique de ces assemblages de pointeurs et de données, il faut concevoir des suites de pointeurs se pointant successivement et qui peuvent boucler (voir Structuration informatique par le bas). Et il faut que la structure de donnéess soit dense, c'est à dire que tous les bits ait une utilités autant que possible.
Les contraintes techniques (mais pas seulement, aussi algorithmiques) nous amènent à concevoir des briques de taille B = 2b bits ou éventuellement de taille B = (2b + 2b-1)*8 car l'octet et la quantification choisie par les ordinateurs comtemporains et la multiplication et la division par 2 consiste à effectuer un simple shiftage à gauche et à droite. Nous avons ainsi : B = 2, 4, 8, 16, 24, 32, 48, 64, 96, 128, 192, 256, 384, 512, 768 ou 1024... bits.
Si nous privilègions l'interopérabilité donnée-pointeur, la taille de la données contenue dans une brique devra être égale à la taille d'un pointeur. Ceci afin de pouvoir convertir le pointeur en une donnée dans la même brique et vis-versa sans perte d'information. On réserve alors dans la brique un bit particulier appelé flag de pointeur. Le bit est à 0 si la brique contient une donnée et il est à 1 si la brique contient un pointeur. Parcontre si les données ne représentent qu'un petit nombre de symboles distincts, alors au lieu de réserver un bit spécifique dans chaque brique, on réserve les dernières valeurs d'adressage pour désigner ces symboles. Les deux procédés peuvent se cummuler.
Dans chaque cellule, pour déterminer si l'on est déja passé par cette cellule, et détecter ainsi les boucles et les partages, nous réservons dans la cellule, un bit appelé flag de passage.
Dans chaque cellule, un flag d'occupation indique si la cellule est libre ou utilisée. Les cellules libres contiennent un pointeur pointant vers une autre cellules libres, et forment ainsi la liste des cellules libres. Ainsi la gestion de la mémoire est simple à programmer.
D'autre bits peuvent être réservés pour d'autres fonctions. On réserve ainsi r bits dans chaque brique pour des fonctionnalités spécifiques (flag de pointeur, autres flags...), et s bits dans chaque cellule pour des fonctionnalités spécifiques (flag d'occupation, flag de passage, autres flags...)
Deux possibilités s'offre à nous. Soit on répartie les bits réervés de la cellule sur chacune de ses briques, et s est alors un multiple de K. Soit on attribut à la première brique de la cellule un autre rôle, tel que celui de mémoriser tous les flags mêmes ceux de ses briques.
Dans le premier cas. Le nombre de flag de la cellule doit être un multiple de K. Les adresses (les pointeurs) doivent être mémorisables sur un nombre de bits égal à B - r - s/K. La mémoire doit être composée de 2n = 2(B-r-s/K) cellules et symboles. L'arité d'une cellule est K, c'est à dire qu'elle contient K pointeurs ou données.
Dans le deuxième cas. Les flags sont regroupés dans la première brique de chaque cellule, B = s + r*K. Les adresses (les pointeurs) et données, sont mémorisées sur un nombre de bits égal à B. La mémoire doit être composée de 2n = 2B cellules et symboles. L'arité d'une cellule est K-1, c'est à dire qu'elle contient K-1 pointeurs ou données.
Nous avons :
Cas n°1 Cas n°2 s multiple de K
n = B-r-s/K B = s + r*K
n = Bn : Nombre de bits pour mémoriser une adresse.
2n : Nombre de cellules du sytème.
r : Nombre de bits réservés dans chaque brique.
s : Nombre de bits réservés dans chaque cellule.
K : Nombre de briques par cellule.
B : Nombre de bits d'une brique. B∈{2, 4, 8, 16, 24, 32, 48, 64, 96, 128, 192, 256, 384, 512, 768, 1024....}
Ces systèmes sont caractérisés par le paramètre K, le paramètre B qui est de la forme B = (2b + 2b-1)*8, le paramètre r librement choisie entre 0 et B, et par le paramètre s, qui dans le premier cas est un multiple de K, et qui dans le second cas est égale à B-r*K.
Une cellule doit pouvoir contenir au moins deux pointeurs pour que le système de mémoire constitue un graphe non dégénéré.
Cas n°1 |
Cas n°2 |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
Lorsque la cellule est d'arité deux on l'appel une paire. La paire est le constituant mémoire élémentaire des systèmes LISP.
Le système de mémoire doit pouvoir réserver des cellules composée d'un nombres entier variable de briques contiguës afin de pouvoir utiliser le mécanisme d'adressage indexé, c'est à dire d'effectuer un adressage en sautant un nombre entier de briques successives, avec la plus grande liberté au sein de ces cellules de différentes tailles.
Un pointeur ne doit pointer que des cellules c'est à dire la première brique d'une cellule.
La première brique de la cellule contient les informations générale sur la cellule, sa taille, un flag de pointeur pour savoir si la cellule est une donnée ou un pointeur, un flag d'occupation pour savoir si elle est utilisée ou libre, un flag de passage pour savoir si on est déjà passé par cette cellule, et éventuellement d'autres flags pour d'autres usages spécifiques.
Puis on doit pouvoir réserver une cellule de taille t, et pouvoir la libérer. A cause des tailles différentes des cellules, l'allocation d'une cellule peut nécessité une recherche longue.... Pour réduire cette difficulté, on ne retient que des tailles égales à des puissances de 2. La cellule possède alors deux tailles, une taille réservée qui est de la forme 2n et une taille efficiente qui est un entier inferieur à la taille réservé. La cellule peut alors s'agrandire jusqu'à sa taille réservée sans nécessité une réalocation.
Les cellules libres contiennent un pointeur vers une autre cellules libre de même taille réservée. La gestion de la mémoire est un peu plus sophistiquée.
On verra plus-tard que la cellule ainsi constituée constitue une liste compilée, une liste capable d'accéder à n'importe quel de ses éléments par un simple adressage indexé. Par contre, une liste lispienne composée d'une succession de paires se pointant, n'est pas capable d'accéder à un de ses éléments par adressage indexé, il lui faut appliquer une succession de n adressages indirectes pour accéder au n ième élément.
Un pointeur désignant une case mémoire quelconque d'un message, désigne une portion final d'un message qui constitue encore un message, c'est à dire une liste terminale-close de termes. Et si le pointeur désigne la dernière case mémoire qui contient nil, alors il désigne un message vide. Lorsque le pointeur est interprété de cette façon, il est appelé pointeur de liste ou lien de liste.
La concaténation de deux messages de taille T1 et T2, peut être fait symboliquement en une opérations d'aiguillage. L'aiguillage consiste en l'affectation de la dernière case mémoire du premier message, à l'adresse de la première case mémoire du second message. L'aiguillage consiste à modifier le pointeur, pointant ves nil, en un pointeur pointant vers un autre message.
Le collage qui est une opération supplémentaire, s'apparente à une compilation. Elle consiste à souder les deux messages, en allouant (T1 + T2 - 1) cases mémoires consécutives, et en recopiant dedans les cases mémoires des deux messages, puis en libérant les cases mémoires des deux messages initiaux :
Le collage représente un travail plus couteux en effectivité que le parcours des deux messages. Pour éviter ce travail on se dispense de faire le collage et on généralise l'implémentation des messages en ajoutant cette possibilité de liens de liste : Un message peut être composée de plusieurs messages liés de façon non récursive, c'est à dire de tel sorte qu'il n'y ai pas de boucle. Par exemple voici un message composé de trois messages :
Il peut se produire une cascade de liens, en cas de messages vides. La simplification d'une tel cascade de liens par un lien unique, un raccourci, n'est pas couteuse en effectivité si elle s'opère dès qu'un processus parcours cette cascade de liens. Ce procédé de programmation s'appel un aspect, c'est une couche logiciel chargée de simplifier les cascades de liens traversées en les remplaçant par un lien racourcis, et qui se situe ainsi à un niveau de protocole plus bas :
Noter que le raccourci doit être mémorisé par tous les pointeurs intermédiaires, car dans le cas générale, il peut y avoir un partage de données, à savoir que plusieurs messages peuvent se rejoindrent et avoir une partie commune jusqu'à la fin.
Si nous choisissons l'implémentation des données la plus défavorable en quantité de mémoire, c'est à dire éclatée, opérateur par opérateur, on obtient les listes chainées du Lisp. La concaténation est constitué par la seul opération d'aiguillage. Par exemple, le terme terminal-clos f(f(s(a),.),.) est concaténé avec la liste terminale-close b, a, s(b) en une seul opération pour produire la liste terminale-close f(f(s(a),b),a), s(b) :
Le nil est-il necessaire ? Dans un langage de caractères, ou de liste de termes terminale-close, il constitue le seul moyen de marquer la fin d'un message. Et cette fin peut, par une substitution en un lien de liste, reprendre et se continuer. Il est alors nécessaire de définir un autre symbôle de fin, nil2, pour signifier une fin définitive.
Par contre dans un langage de terme clos, pour transmettre un terme, il n'est pas nécessaire d'avoir un symbôle de fin de terme. Car si on connait les arités des opérateurs on peut connaitre à tous instant, si le terme en cours de lecture est clos ou non. Mais le terme n'étant pas borné, et le système informatique devant pouvoir procéder par portion plus petite, le nil redevient nécessaire, ici appliqué à un terme terminal-clos. Il signifie que le message est momentanément interrompue et qu'il peut reprendre à tout moment. C'est un protocole de bas niveau.
Pour transmettre un terme clos, le nil2 n'est pas nécessaire. Le nil2 est nécessaire pour transmettre une liste de termes, ce que notre langage ne peut pas exprimer puisqu'il est composé que d'opérateur d'arité fixe.
Les listes peuvent être définie à l'aide des deux opérateurs suivants, {nil, cons(.,.)}. Le nil représente la liste vide, et aussi la fin de liste, et l'opérateur cons(x, L) construit une liste en ajoutant l'élément x en tête de la liste L.
Noter que le nil réapparait ici comme un opérateur constant du langage et non plus comme un protocole de bas niveau.
Nous adoptons la notation abrégée des listes lispiennes entre crochets [ ] . Nous avons par exemples :
[ ] = nil
[x] = cons(x,nil)
[x,y] = cons(x,cons(y,nil))
[x,y,z] = cons(x,cons(y,cons(z,nil)))
Et on remarque que le programme de construction de la liste, est lui-même une liste plus complexe puisqu'elle intègre l'opérateur de construction cons (Les variable x,y,z sont représentées ici par des pointeurs pointant vers leur valeurs) :
Ainsi l'évaluation correspond à une simplification, et d'une certraine manière à une compilation.
Il y a une dimension supplémentaire que le calcul formel ignore. Cette dimension est la machine qui implémente le calcul formel, et qui peut partager les données, et ainsi ramener les algorithmes fondamentaux à une complexité linéaire. Vous pourriez rétorquer que d'un point de vue mathématique la complexité peut être calculée après la construction. Ce n'est pas le choix de notre heuristique qui préconise de rester proche du barycentre des 3 pans du langages que constitue la donné, le programme et la théorie, chacun de ces pans dévoilant un mystère inexplicable sans la présence des deux autres.
Cette dimension supplémentaire peut paraitre bien matériel, c'est une machine, et qui va permettre le partage. Mais cela ne s'écrit pas facilement en suites de symbôles. C'est l'adressage indirecte indexé, opération fondamentale en informatique, qu'il convient de modèliser d'une certaine façon..
On définie plusieurs types d'objet :
Les opérateurs appartiennent à un langage prédéfini L et sont posés constants. On numérote les variables en commençant par zéro, et c'est ce numéro qui constituera leur nom, un nom assurément dense. On pourrait affiner notre discussion pour tenter d'enlever l'arbitraire que semble porter cette construction. A ce stade les arité des opérateurs sont variables.
Le système de mémoire se présente comme une suite de cases numérotées, où le numéro de la case représente son addresse. La Variable est une case contenant un pointeur, la Constante est une case contenant un opérateur du langage, le Noeud est un ensemble de n+1 cases consécutives dont la première contient un opérateur du langage et les suivantes contiennent des pointeurs, et le Bloque est un ensemble de n+1 cases consécutives contenant des pointeurs, où n est un entier strictement positif.
La liste lispienne [x,y,z] se présente ainsi :
où x,y,z sont des cases mémoires de type Variables. Sur le shéma le symbole x est mis au bout de la flêche, pour mettre l'attention sur ce quoi il désigne. Mais x représente la case (ou le pointeur) avant son contenue. Le contenue de x est obtenue en effectuant l'adressage indirecte.
Et le nil retrouve sa fonction première de protocole de bas niveau, en étant ici un pointeur pointant sur 0, c'est à dire une variable pointant sur l'adresse 0, dont la signification est spécifique au protocole.
L'implémentation procède à une simplification en supprimant l'opérateur cons(.,.) au profit d'un bloque de deux pointeurs appellés paire pointée. Cette traduction constitue une opération élémentaire de compilation.
La paire pointée cons(x,y) ce note également par x • y. Elle correspond au type Bloque de taille 2, c'est un bloque de deux pointeurs qui se présente ainsi :
où x, y sont des cases mémoires de type Variables.
La structure que nous avons précédement décrite, généralise l'implémentation lispienne, pour des bloques de pointeurs de taille quelconque.
Pourquoi la notion de bloque joue t-elle un rôle particulier ? cela provient de la nature de la mémoires et des flux de donnée qui sont des suites de cases contenant des données élémentaires, et qui se regroupent en bloques de cases.
La structures lispienne utilise 2 opérateurs que sont : {nil, cons(.,.)} et qui constitue une extension du langage pour permettre de construire les listes emboités et pointés. Il y a en effet deux sortes de liste, les listes normales et les listes pointées. On note les listes pointés avec un point • à la place de la dernière virgule. Mais attention, ce point • dans la notation abrégé n'a pas exactement la même signification que l'opérateur • alias de l'opérateur cons. Voici une liste pointée :
[x,y,z • t] = cons(x, cons(y, cons(z, t)))
[x,y,z • t] = (x • (y • (z • t)))
Ce type anecdotique n'est pas recherché, mais découle des mécanismes de construction choisis. Ainsi on est obligé de faire avec, sauf à poser une règle arbitraire. Mais poser une règles arbitraire est plus préjudiciable. L'heuristique consiste a éviter autant que possible les règles arbitraires.
Nous adoptons la notation abrégée des listes lispiennes entre crochets [ ] avec éventuellement un point • en fin de liste. Voici une série d'exemples :
[ ] = nil
[a] = a • nil
[a • b] = a • b
[a,b] = a • (b • nil)
[a,b • c] = a • (b • c)
[a,b,c] = a • (b • (c • nil))
[[a,b],c] = (a • (b • nil)) • (c • nil)
[a,[b,c]] = a • ((b • (c • nil)) • nil)
---- 15 juillet 2013 ----
9) Les liens de terme
La compression consiste à partager des données identiques qui sont sous forme de sous-termes. Pour cela nous définissons un nouveau type de liens, appelé lien de termes, qui désigne le premier sous-terme terminal-clos rencontré et non la liste terminale-close. Ce type de lien va permetre de représenter les termes sous forme d'arbres. Le terme exemple f(f(a,s(a)),f(a,s(a))) est un arbre qui possède deux sous-arbres égaux. Il peut partager les données de ses sous-arbres comme suit :
Les liens indiqués sont des liens de termes, et désigne le premier terme qu'il pointe et non la liste de termes qui y débute. Pour percevoir les sous-arbres égaux on a augmenter l'entropie du message, on a subdivisé le message en créant les liens de terme. C'est à dire qu'il existe sur ce shémat de nombreux états microscopiques correspondant au même état macroscopique. L'état microscopique étant les différents messages obtenus en déplaçant les blocs de mémoires. Et l'état macroscopique étant le terme (ou la liste de termes terminale-close) identique pour chacun de ces messages.
Par analogie, on augmente la température du message en quelque sorte. Le message est une molécule composée d'atomes, et chaque atome acquère une certaine autonomie, de tel sorte que le message peut présenter ses atomes dans un ordre quelconque tous en gardant les liens entre eux. On peut alors plus facilement unifier les sous arbres identiques. Une fois cette unification achevée, ce partage des données effectué, on refroidie le message en remplaçant les cascades de liens par des racourcis et en collant tous les morceaux. Dans l'exemple, cela aboutie à deux états microscopiques possibles :
Le terme f(f(a,s(a)),f(a,s(a))) avec partage du sous arbre f(a,s(a)) peut s'écrire de deux façons différentes : f(3,f(a,s(a))) ou f(f(a,s(a)),2).
Le flux de donnée s'est enrichie d'un nouveau type de liens. La mémoire peut contenir soit un opérateur de L ou bien la valeur NIL, ou bien un lien de termes, ou bien un lien de liste. Et donc S=2. Un lien est une adresse d'une case mémoire d'un message. Un lien est synonyme de pointeur. Le message possède des données partagées avec d'autre message ou lui-même. Par analogie aux programmes impératifs, le lien de liste et le lien de terme correspondent au goto et au gosub.
La pile de protocole contient trois niveau. Le niveau le plus bas contient les liens de listes, le niveau intermédiaire contient les liens de termes, le niveau au dessus contient les opérateurs de L. Et il découle qu'il y a deux valeurs NIL possibles : La liste vide et le terme vide qui sont respectivement dans le premier et deuxième niveau de protocole.
Comme on souhaite rester dans la plus grande généralité, on se laisse guider par l'ébauche de structure du flux en y apportant le moins de restrictions possibles afin qu'elle atteigne son plus haut degré de liberté. On, se place au dessus du premier niveau de protocole, de tel sorte que l'on ignore l'existance de liens de listes, cette tache étant assurée de manière transparente par une couche logiciel de bas niveau. Seul reste la gestion des liens de terme. Le message est alors une suite d'opérateurs de L, et de pointeurs vers des cases mémoire d'autres messages (ou du même message). Un pointeur désignant la dernière case mémoire d'un message (contenant NIL), désigne la fin du message, et il désigne aussi un terme vide en place terminale. Si l'on note par "." les termes vides, cela signifie par exemple :
a = (a,.) = (a,.,.) = (a,.,.,.) = a(.) = a(.,.) = a(.,.,.) = (a(.,.),.)
f = (f,.) = (f,.,.) = (f,.,.,.) = f(.) = f(.,.) = f(.,.,.) = (f(.,.),.)
Mais on réserve le symbole point pour désigner l'opérateur identité que l'on ajoute au langage L, et qui joue ce même rôle sans être obligé d'être en place terminale.
Il apparaît une nouvelle sorte de terme que sont les termes récursifs. Ils sont caractérisé par l'existance de boucle de liens de termes. Par exemple voici quelques termes recurcifs les plus simples :
s(1) s(2) f(a,1) f(3,2)
Dans un langage d'opérateurs simple, tout terme est obtenue par emboitement finie d'opérateurs (axiome n°15). Ces cas de figure ne sont donc pas autorisé. Mais il le sont dans un langage d'opérateurs récurcifs.
L'approche mathématique est plus bavarde. Le terme exemple est le suivant : f(f(a,s(a)),f(a,s(a))). Si on factorise le sous-arbre f(a,s(a)), la factorisation s'écrit mathématiquement en utilisant une variable intermédiaire X qui désignera les différentes occurences du sous-arbre, et l'opérateur binaire "=" qui permet de définir X. Le terme factorisé s'écrit ainsi :
f(X,X), X=f(a,s(a))
ou d'une façon plus concise fXX=Xfasa dans le langage {X, a, b, s(.), f(.,.), =(.,.)}. Le langage est ainsi augmenté d'un opérateur variable X d'arité zéro, et de l'opérateur constant = d'arite 2 et de type propositionnel
Cette formule est à la fois une donnée et un programme. Nous allons estomper les différences entre données et programme.
L'interpretation de cette formule ce fait en 3 opérations que sont l'interpretation, l'unification, et le raccourcissement :
Le langage s'est complété. Ce n'est plus un langage d'opérateurs simple. C'est un langage d'opérateur à 2 niveaux simples. On ajoute au langage L un ensemble de variables dites universelles car pouvant être unifiées avec tout terme de <L> que l'on note par des majuscule, par exemple {X,Y,Z...}, et on ajoute un meta-opérateur d'arité 2 noté =(.,.) qui signifie "est affecté par". Ce meta opérateur a comme premier argument une variable universelle et comme second argument un terme de L°[X,Y,Z...].
voir Implémentation des langages d'opérateurs
9) Les opérateurs L-constructibles dans L°s
On se place dans le langage d'opérateur simple avec séquence finie L°s. Un opérateur constant est une application de L°^n vers L°^m, qui possède un nom. n>0 et m>0 car les séquences vides sont exclus. L'opérateur est L-constructible si on peut le construire par composition d'applications de L au sens général, c'est à dire avec permutation-projection des variables tel que par exemple l'opérateur suivant : (x,y)-->(g(x,f(y)),f(x)). Une composition au sens générale constitue une programmation sans boucle, un assemblage de sous-programmes sans boucles.
On définie l'opérateur de création d'application "-->". Il prend comme premier argument une séquence de n variables X,Y,Z... de noms distincts et , et comme second argument une séquence de m termes de L°[X,Y,Z...] chacun de type (1,0), et retourne comme résultat un opérateur de type (n,m). Par exemple :
(X,Y)-->(g(X,f(Y)), f(X))
Cela produit un opérateur qui est une application L-constructible de L°^2 vers L°^2. L'opérateur appliqué à la séquence (a,b) produit la séquence (g(a,f(b)), f(a)).
On généralise l'opérateur --> en prenant comme premier argument une séquence de n éléments quelconques de L°[X,Y,Z...] et comme second argument une séquence d'éléments quelconques de L°[X,Y,Z...], tel que par exemple :
( f(X), g(Y,X) )-->( g(X,f(Y)), f(X) )
Cela produit un opérateur qui est une fonctions de L°^n sur L°^m. Le premier argument est appelé séquence d'entré de la fonction et le second argument est appellé séquence de sortie de la fonction. Le domaine de définition de la fonction est constitué par toutes les séquences de termes de L° unifiables à la séquence d'entré. La séquence d'entré est transformer en la séquence de sortie en respectant les variables muettes qui transportent l'information transmise à la séquence d'entré au cours de l'unification. La fonction précédente appliqué à la séquence f(a),g(b,a) produit la séquence g(a,f(b)),f(a).
On étend le domaine de définition de la fonction à tous les autres séquences de termes de L° non unifiables à la séquence d'entré de la fonction, en leur donnant comme image le terme FAIL. C'est une constante de type FAIL que l'on ajoute dans L°. Pour tout terme de L° si celui-ci contient parmis une de ses opérandes la valeur FAIL alors il retourne FAIL. Ce comportement est définie dans le langage des types. Le langage devient alors un langage d'opérateurs de type simple avec type FAIL et séquences finies. (Une séquence ne contenant qu'un terme est identifié à son terme. Une séquence peut contenir des termes FAIL sans être FAIL).
Le domaine de définition de la fonction est étendue aux séquences de termes de L°[X,Y,Z...]. Et les séquences non unifiables à la séquence d'entré de la fonction ont comme image FAIL. Dans un langage d'opérateur simple avec sequence finie, les termes récurcifs sont interdits, faisant par exemple que f(X) ne peut pas être unifié à X.
Ainsi nous avons :
(f(X)-->g(XX)) (a) = FAIL
(f(X)-->g(XX)) (f(a)) = g(a,a)
((X,Y)-->(g(XX),f(Y))) (a,b) = (g(a,a),f(b))
(g(X,Y)-->h(Y,X)) (g(Y,b)) = h(b,b)
(X-->(g(X,Y)-->h(Y,X))) (a) = g(a,Y)-->h(Y,a)
Currification :
On peut ajouter au langage le procédé de currification.
((X,Y)-->g(f(X),Y)) (a) = Y-->g(f(a),Y)
(X-->f(f(X))) (a,b) = (f(f(a)),b)f = X-->f(X)
f(f) = X-->f(f(X))
g(f) = (X,Y)-->g(f(X),Y)
g(a,f) = X-->g(a,f(X))f(a,b,f) = (f(a), b, X-->f(X))
a(b) = (a,b)
Variables locales :
Les variables X et Y
précédement utilisées, sont locales, c'est à dire
qu'elles sont uniques pour chaque fonction isolée concernée. Mais
par abus de langage on utilise le même nom. Le nom exacte devrait être
X suivi d'un numéro différent pour chaque fonction isolées.
L'opérateur d'identité "." :
On peut ajouter au langage l'opérateur identité ".".
Il est remplacé par l'application X-->X où
la variable X est locale. c'est à dire que
son nom est différent des variables évoquées dans les autres
termes.
. = Z-->Z
(g(.,X)-->g(X))) = ((Z-->g(Z,X))-->g(X))
g(.,b) = (Z-->g(Z,b))
((Z-->g(Z,X))-->g(X)) (Z-->g(Z,b)) = g(b)
(g(.,X)-->g(X))) (g(.,b)) = g(b)
Les paramétriques :
les para
f(X)
On considère des ensembles dLes opérateurs L-constructible-faible sont remplacés par les applications de base où la variable X est locale, c'est à dire de nom différents des autres variables évoqué dans les autres termes.
ggX = (Y,Z)-->g(g(X,Y),Z)
gX = T-->g(X,T)
ggb = (A, B)-->g(g(X,A),B)
(((Y,Z)-->g(g(X,Y),Z))-->(T-->g(X,T)) ((A,B)-->g(g(b,A),B) = (T-->g(b,T))
(ggX-->gX) (ggb) = gb
10) L'unification et la résolution
Il y a 4 types d'opérateurs :
1) Les permutation-projection. Par exemple (X,Y,Z) --> (X,Z)
2) les application(X,Y) --> (f(X),g(Y,X))
(f(X),g(Y,X)) --> (X,Y) résolution
(f(X),g(Y,X)) --> (f(X),g(Y,X)) unifcation
L'opérateur inverse (f(x),y)-->(x,y) définie ce que l'on appelle la résolution de l'unification, c'est à dire lorsque l'unification est achevé positivement la fonction donne comme résultat la valeur des variables ou retourne FAIL en cas d'échec de l'unification. L'autre partie apparente de l'unification qui porte son nom est la fonction (f(x),y)-->(f(x),y). Elle retourne le résultat de l'unification, c'est à dire la séquence de termes unifiés ou FAIL. On note U l'unification de deux séquences de termes, et R la résolution d'une séquence de terme unifié par une autre séquence de termes. Noter que U est symétrique mais que R ne l'est pas.
g(x,y) U g(f(y),a) = g(f(a),a)
g(x,y) R g(f(y),a) = (f(a),a)
(f(x),y) U (z,g(z,z)) = (f(x),g(f(x),f(x)))
(f(x),y) R (z,g(z,z)) = (x,g(f(x),f(x)))
On généralise les règles en les faisant appliquer sur une liste de premier terme. La règle f(X),g(X,Y)--> h(Y,X) appliqué à deux termes dans le même ordre f(a), g(a,b), produit le terme h(b,a).
On définie un opérateurs d'application d'arité 3 noté identiquement @. Cette opérateur prend en premier argument une règle et comme second et troisième argument deux termes et retourne comme terme résultat le résultat de l'application de la foncion sur les deux termes en question. Si l'unification échoue l'opérateur retourne le terme FAIL de type FAIL.
Ainsi nous avons :
f(X),Y -->g(f(Y),X) @ a,b = FAIL
f(X),X-->g(XX) @ f(a),a = g(a,a)
X,Y-->g(XY) @ f(a),b = g(f(a),b)
X,f(Y)-->(g(f(X),Y) --> h(Y,X)) @ a, f(b) = g(f(a),b) --> h(b,a)
g(X,Y),f(Y) -->h(Y,X) @ g(a,b),f(b) = h(b,a)
f(X),f(Y) -->h(Y,X) @ f(Y),f(b)) = h(b,b)
On définie les opérateurs de création d'opérateur d'arité 4,5,6... notés -->, et les opérateurs d'application d'arité 4,5,6... notés @ de la même façon. Nous avons définie des opérateurs de création d'opérateur --> d'arité diverse et des opérateurs d'application d'opérateurs @ d'arité diverse, tout en restant dans un langage d'opérateur simple à 2 types.
15) Structure de données des termes :
La structure de donnée d'un terme est un arbre un peu plus générale où des sous-arbres peuvent être partagés. L'arbre possède un noeud racine, qui peut être directement une feuille. Les noeuds de l'arbre sont des séquences de pointeurs composée d'un premier lien vers un opérateur et d'un ou plusieurs liens suivants vers ses opérandes. Les feuilles de l'arbre sont des opérateurs qui possèdent chacun un genre et un type. Les opérateurs de genre "variable" sont représentés par une case mémoire contenant NIL et d'adresse correpondant au nom de la variable. Les opérateurs de genre "constant" sont représentés par une case mémoire contenant le nom de l'opérateur.
Par exemple le terme f(f(X,Y),f(f(a,X),f(a,Y))) est représenté par :
Les termes sont des arbres qui peuvent avoir des sous-arbres, ou sous-terme, partagés par d'autres termes. Un sous-terme est également un terme.
Noter que les label X et Y ne sont pas contenus dans cette structure de données, mais sont indiqués dans ce shéma pour désigner leurs adresses mémoires respectives. Ce n'est pas leur label qui est utile à l'unification mais leurs occurences. Quant une variable universelle libre s'unifie à un terme, son pointeur, valant initialement NIL, va pointer sur l'adresse du sous-terme en question, et il n'y a pas de recopie du sous-terme.
Les constantes et opérateurs appartenant à la présentation du langage, qui constituent les feuilles de l'arbre, sont des cases mémoires contenant leur label. La négation de Skolème fait permuter les rôles entre les opérateurs constants et les opérateurs variables, d'où l'intérêt de cette implémentation symétrique vis-à-vis des genres constant et variable.
Néanmoins les opérateurs constants peuvent ne pas être partagées. On peut les répliquer autant de fois que l'on veut dans la structure de donnée, puisque leur label est mémorisé et peut servire pour vérifier si on a à fair au même opérateur constant. Il n'en est pas de même pour les variables universelles qui constituent les points dynamiques de l'arbre et qui sont caractèrisées par leur adresse mémoire. Une duplication de celles-ci changerait leur sense.
C'est pourquoi le shéma précédent se présente souvent comme suit :
Lorsque l'on rencontre une variable possèdant un pointeur différent de NIL, cela correspond à un addressage indirecte, un lien vers un sous-terme, qui s'est construit antèrieurement lors de l'unification de la variable universelle à ce sous-terme. Et il peut même y avoir une succession d'adressages indirectes, une succession de liens. Pour que l'algorithme d'unification reste en complexité linéaire, il faut qu'à chaque parcours d'un lien par un processus, à chaque application d'un addressage indirecte, on établisse le raccourci correspondant, pour ne pas avoir à réappliquer cet adressage indirecte lors d'un prochain passage. Cela est assuré par un aspect, un protocole de bas niveau implémenté dans le programme du processus qui parcours l'arbres.
L'unification s'applique à une liste de termes. La structure de données devra donc contenir plusieurs termes, c'est à dire plusieurs arbres, un arbre par terme, et devra partager les variables universelles communes à plusieurs de ces termes. C'est à dire que des feuilles désignant des variables universelles pouront être communes à plusieurs arbres le cas échéant.
Cette structure de données est un graphe orienté acyclique, DAG (Directed Acyclique Graph).
On ajoute dans cette structure de données, une liste de pointeurs, la liste des liens vers les variables universelles X1, X2, X3... Xn où n désigne le nombre de variables universelles distinctes utilisées dans l'unification en question, ainsi qu'un pointeurs R vers le noeud racine d'un des termes devant être unifiés.
16) Interpretation ensembliste des termes
Un terme de L°[X,Y,Z...] définit l'ensemble de tous les termes de L° unifiables aux termes en question. Par exemple :
g(X,X) = { g(a,a), g(b,b), g(s(a),s(a)), g(g(a,a),g(a,a))....}
Terme Ensemble image FAIL Ø X <L> a {a} f(X) f(<L>)
Par convention, on ajoute le terme vide noté Ø, et on applique la règle suivante : Un terme qui possède un sous-terme vide est égale au terme vide. Voici quelques exemples :
Ø = s(Ø)
Ø = g(a,Ø)
Ø = g(g(a,X),g(Ø,Y))
C'est une règle de simplification de la méta-théorie. Elle agit en préproduction sur tous les termes et forme une sous-couche en bas du méta-langage.
La constante FAIL est noté Ø.
Un terme t1 est dit indépendant du terme t2 si et seulement si il n'ont pas de variables commune.
L'unification de n termes indépendants produits un terme correspondant à l'ensemble intersection des n ensembles associés aux n termes.
Un couple de terme de L°[X,Y,Z...] définit une fonction unaire L-constructibles. Par exemple le couple (g(X,X), f(X)) représente la fonction g(X,X)-->f(X). Le couple (g(X,X), f(X)) représente le graphe de la fonction g(X,X)-->f(X).
17) L'algorithme d'unification de complexité linéaire
Le mécanisme d'unification constitue un point essentiel de la dynamique des théories. Il donnent un sense spécifique aux mots du langage L°[X,Y,Z...], un sense que nous allons formaliser en respectant la plus grande généralité possible.
L'unification U est une opération n-aire de L°[X,Y,Z...]n vers L°[X,Y,Z...]. C'est à dire qu'elle s'applique à n termes et retourne soit un terme résultat ou soit FAIL. Dans le cas courant, n vaut 2. Mais le même algorithme s'applique sans difficulté particulière à 3 ou 4 termes en même temps. Nous allons décrire cette algorithme d'unification de complexité linéaire (proportionelle à la taille des termes). Il faut choisire une structure de données permettant cette complexité linéaire. Elle doit mettre en oeuvre le partage de données, afin que là où un seul traitement est nécessaire, cela ne nécesssite pas plusieurs traitements. Un graphe orienté acyclique (DAG) permet cela.
Au lieu d'unifier simplement n termes, on peut être amené à unifier n listes de m termes, c'est à dire à se placer dans un langage de m-uplet de L°[X,Y,Z...]. Et d'un point de vue algorithmique cela se rammène à une succession de m unifications de n termes chacun. D'une manière générale, l'unification est en faite une succession d'unification simple. C'est pourquoi l'algorithme que nous décrivons prend en argument une liste de travaux à faire, c'est à dire une liste de listes de termes à unifier, et n'impose pas de règles de tailles. On appellera un travail, une liste de termes devant être unifiés.
Une des premières taches de l'unification consiste à créer la structure de donnée initiale décrite précédemment, et d'établire la liste des travaux d'unification à faire, c'est à dire une liste de listes de pointeurs de termes dans la structure initiale. Cela constitue la couche logiciel n°0.
On établit un aspect relatif aux variables, à chaque fois que l'occasion nous est donnée, on évalut le lien contenue dans la variable et on établit le raccourci. Cela constitut la couche logiciel n°1. Au dessus de cette couche logiciel, un pointeur désigne trois types de données possibles :
Pour simplifier l'écriture on appellera ces trois types de données : (0) Constante, (1) Variable , (2) Noeud.
Voici l'algorithme :
Début :
L'algorithme s'applique à une liste de travaux, c'est à dire à une liste de listes de termes passés en arguments. L'algorithme s'attaque au premier travail, à la première liste de termes. L'algorithme se présente en trois cheminements, ou sous-programme appelés de même noms : "constante", "variable", "noeud". Si le premier pointeur extrait de la liste désigne une constante on lance le sous-programme "constante", si c'est une variable on lançe le sous-programme "variable", et si c'est un noeud on lançe le sous-programme "noeud"Le programme prend fin lorsqu'il n'y a plus de travaux suivant. On réitère le programme avec le travail suivant.
Le sous-programme "Constante" :
Le terme en cours est une constante.Tant qu'il y a des termes suivant. On prend connaissance du terme suivant, et selon les trois cas :
Si c'est une constante, on vérifie qu'elle est égale sinon on retourne FAIL. Si c'est une variable, on l'affecte à la constante en cours. Si c'est un noeud, on retourne FAIL.Puis on réitère la boucle "Tant que" avec le terme suivant.
Le sous-programme "Variable" :
Le terme en cours est une variable universelle à l'état libre.Tant qu'il y a des termes suivant. On prend connaissance du terme suivant, et selon les trois cas :
- Si c'est une constante, on unifie la variable en cours à la constante et on effectue un saut vers le sous-programme "Constante".
- Si c'est une variable, on l'affecte à la variable en cours.
- Si c'est un noeud, on unifie la variable en cours au noeud et on effectue un saut vers le sous-programme "Noeud"
Puis on réitère la boucle "Tant que" avec le terme suivant.
Le sous-programme "Noeud" :
Le terme en cours est un noeud. On crée des travaux supplémentaires initialisés avec les fils de ce noeud, un fils par nouveaux travaux.Tant qu'il y a des termes suivant. On prend connaissance du terme suivant et selon les trois cas :
- Si c'est une constante, on retourne FAIL.
- Si c'est une variable, on l'affecte au noeud en cours.
- Si c'est un noeud, on vérifie qu'il possède le même nombre de fils sinon on retourne FAIL, puis on ajoute ses fils dans les travaux supplémentaires (un fils par nouveaux travaux).
Puis on réitère la boucle "Tant que" avec le terme suivant.
Une fois terminé, si la liste de travaux supplémentaire ne contient que des listes d'un seul élément, on les supprime.
(Si on souhaite une unification en "profondeur d'abord" alors on placera ces travaux supplémentaires en tête de pile).
Fin :
Le résultat est contenu dans deux endroits :
Pour chaque travail d'unification, les termes ont été modifiés physiquement et sont maintenant chacun égaux au terme résultat. Les variables universelles dont les références sont dans une table de la structure de données, ont été modifiées physiquement et contiennent maitenant leur valeurs qui sont des termes spécifiques.Le résultat est composé de deux listes de termes (R1,R2,R3...,Rn), (X1,X2,X3,Xk), où n est le nombre de travaux initiaux d'unification, et où k désigne le nombre de variables universelles distinctes utilisées. R1 pointe sur le premier terme du premier travaux d'unification, Ri pointe sur le premier terme du i-ième travaux d'unification et ainsi de suite. X1 pointe sur la première variables rencontrée, Xi pointe sur la i-ième variables rencontrée.
On introduit un second aspect relatif au boucle sans fin. En effet, des termes cycliques peuvent apparaîtrent au cours de l'unification pouvant entrainer l'algorithme dans une boucles sans fin. Dans ce cas l'unification doit s'arréter et retourner FAIL. Les travaux initiaux sont numérotés de 1 à n. Et chaque noeud racine, évoqué dans un travail initial, est marqué par le numéro du travail initial. Puis à chaque construction de nouveaux travaux, les termes concernés hériteront du numéro de travail, du travail père, et alors le teste peut être fait, de vérifier si ce numéro de travail n'est pas déja présent, ce qui signifierait que l'on ait déja passé par là et dénoterait une boucle sans fin.
Grace à cette aspet, qui nécessite d'allourdire un peu la structure de donnée en adjoignant à chaque noeud un nombre de bits égale au nombre de travaux initiaux, comme autant de marqueur marquant le passage, l'algorithme évite ainsi les boucles sans fin et s'arrète en un temps fini.
17.0) Programmation de la construction de la structure de donnée (couche logiciel n°0)
Pour programmer la construction de la structure de données, on va décentraliser le programme au profit des éléments de base du langage qui constituront des sous-programmes.
Soit par exemple le langage L ={a,b,s(.), f(.,.)}. On ajoute les entiers pour désigner des sous-arbre paratagés. Ainsi f(f(X,6),f(a,2)) désigne le terme f(f(X,a),f(a,f(X,a))).
On crée trois piles globales :
On associe à chaque opérateurs un sous-programme qui construit la partie de la structure de données le concernant.
Ainsi l'expression f(f(X,6),f(a,2)) constitue le programme qui va créer une structure de données (DAG) et retourner un pointeur vers cette structure.
Le programme de création d'un travail T prend un nombre d'arguments variables supérieurs à 1, alloue une pile de termes, puis empile les pointeurs résultats des programmes correspondants à ses arguments, puis retourne un pointeur désignant cette pile de termes. Le programme de création d'une liste de travaux K prend un nombre d'arguments variables supérieurs à 0, alloue une pile de travaux, puis empile les pointeurs résultats des programmes correspondants à ses arguments, puis retourne un pointeur désignant cette pile de travaux.
Ainsi K( T(f(f(X,6),f(a,2)), f(Y,X)), T(f(Y,Z), f(Z,Y)) ) construit la structure de données nécessaire avant l'éxecution de l'algorithme d'unification.
17.1) Programmation de l'aspect relatif aux variables (couche logiciel n°1)
Sans cette aspet, un pointeur peut désigner une variable liée. Il faut alors effectuer l'adressage indirecte et remplacer le pointeur afin qu'il pointe sur ce que pointe la variable. Et si l'objet pointé est encore une variable liée, il faut réitérer l'adressage indirecte. La façon dont sont affectées les variables fait qu'il ne peut y avoir de boucle sans nud.
L'aspect ajoute une opération supplémentaire au moment de l'évaluation d'un pointeur faisant parti de la structure. Un pointeur p est une variable du programme et apriorie ne fait pas partie de la structure de données. On s'intéresse au pointeur p faisant partie de la structure de donnée. Il y a deux cas de figure, ou bien p est un pointeur contenu dans une variable de la structure, ou bien p est un pointeur contenu dans une case mémoire d'un noeud de la structure. (La structure en question est un DAG).
Dans les deux cas, l'aspect va modifier le pointeur par un pointeur raccourci qui ne pourra plus désigner de variable liée. Le pointeur, une fois évalué, désignera une constante, une variable libre, ou un noeud. L'aspect modifie la structure de données comme suit :
Un pointeur p peut désigner une constante, une variable, ou un noeud. On définie les procédures suivantes :
IsConst(p) Retourne TRUE si et seulement si p désigne une constante. IsVar(p) Retourne TRUE si et seulement si p désigne une variable. IsNoeud(p) Retourne TRUE si et seulement si p désigne un noeud.
Si p désigne une variable, *p est le pointeur de la variable, c'est à dire qu'il désigne ce que désigne la variable, et de plus il est la mémoire de la variable, de tel sorte que l'instruction *p=q va modifier physiquement la mémoire de la variable, et la variable va pointer dorénavant vers ce que pointe le pointeur q.
p désigne une variable libre si et seulement si p désigne une variable et si *p est égale à NIL.
Le programme d'évaluation R(p) s'applique à un pointeur p passé en référence. Il y a toujours deux cas de figure, ou bien p est un pointeur contenu dans une variable, ou bien p est un pointeur contenu dans une case mémoire d'un noeud. Le passage du paramètre p par référence est essentiel si l'on veut modifier physiquement la structure de données. Cela est représenté par le symbole & dans la déclaration de fonction.
void function R(Pointeur &p){
Pointeur q=p; |
Alloue un pointeur q et l'initialise à p. |
while (IsVar(q) & *q<>NIL) q=*q; |
Tant que q est une variable liée, on évalue q d'un niveau
afin que celui-ci pointe sur ce que pointe la variable liée. |
Pointeur r=p; Pointeur s; |
Alloue un pointeur r et l'initialise à p. |
p=q; |
p doit être une référence pour que cette affectation modifie physiquement la structure de données. p est modifié par une copie de q. |
while (IsVar(r) & *r<>NIL) { s=*r; *r=q; r=s; } |
Tant que r est une variable liée, on modifie la variable désignée par r en remplaçant son pointeur par une copie de q, et on évalue r d'un niveau afin que celui-ci pointe sur ce que pointait la variable liée avant modification. |
}
Le programme de reconnaissance Type(p) s'applique à un pointeur p passé en référence, et retourne 0, 1 ou 2 selon que p désigne une constante, une variable libre, ou un noeud. Le programme de reconnaissance évalue le pointeur en le remplassant par un raccourcie le cas échéant, modifiant ainsi physiquement la structure de données.
int function Type(Pointeur &p){
if (IsVar(p)) R(p); | Si p désigne une variable alors on évalue p. |
if (IsConst(p)) return 0; | Si p désigne une constante alors on retourne 0. |
if (IsVar(p)) return 1; | Si p désigne une variable alors on retourne 1. La variable est libre car p a été préalablement évalué. |
if (IsNoeud(p)) return 2; | Si p désigne un noeud alors on retourne 2. |
}
17.2) Programmation de l'unification
Le type "Pile" désignera une pile de pointeurs. On utilise différentes piles :
K : Une pile de travaux.
T : Une pile de termes représentant un travail.
KS : Une pile de travaux supplémentaires
TS : Une pile de termes représentant un travail supplémentaire.
Une pile possèdera un numéro de 1 à n où n est le nombre de travaux initiaux (la taille initiale de K). Et un noeud possèdera une zones de marquage pouvant mémoriser plusieurs numéro, n bits réservés à cet effet, le i-ième bits étant à 1 si le noeud est marqué par le numéro i.
Soit une pile L, un pointeur p, et un entier i. On définie les 8 procédures suivantes :
L = CreerPile() Alloue dynamiquement une nouvelle pile désignée par L. (L est un pointeur). Liberer(L) Libère l'espace mémoire réservé pour la pile L. Après cette instruction L est égale à NIL. Empile(L,p) Empile dans L une copie du pointeur p. p = Depile(L) Retire de L un premier pointeur et le copie dans p. p = L[i] Retourne le i-ième pointeur contenue dans la pile L et le copie dans p. L[i] = p Modifie la pile L en remplaçant son i-ième pointeur par une copie de p. i = Num(L) Retourne le numéro de la pile L et le copie dans i. Num(L) = i Modifie la pile L en remplaçant son numéro par une copie de i.
Soit un pointeur de noeud X. On définie les 5 procédures suivantes :
IsMarque(X,i) Teste si le noeud désigné par X est marqué par le numéro i. C'est à dire si le i-ième bits réservé à cet effet est à 1. Marque(X,i) Marque le noeud désigné par X avec le numéro i . C'est à dire met à 1 le i-ième bits réservé à cet effet. i = Arite(X) Retourne l'arité du noeud X et la copie dans i. p = X[i] Retourne le i-ième pointeur du noeud X et le copie dans p. X[i] = p Modifie le noeud X en remplaçant son i-ième pointeur par une copie de p.
Soit X un pointeur de variable. On définie les 2 procédure suivantes :
p = *X Retourne le pointeur contenue par la variable désigné par X, et le copie dans p. Si ce pointeur est NIL cela signifie que la variable désigné par X est libre. *X = p Modifie la variable désignée par X, en remplaçant son pointeur par une copie de p.
Soit X un pointeur de constante. On définie la procédure suivante :
*X == i Teste si la valeur identifiant la constante désigné par X, et égale à i.
La fonction unification prend en argument une pile de travaux K. Elle se programmme comme suit :
function Unification(Pile K){
Pile T; | T est un travail, c'est une liste de termes devant être unifiés. |
Pointeur U,V; | U et V sont deux termes. |
int n; | n est le numéro du travail en cours. |
Pile KS; | KS est une liste de travaux supplémentaires. |
Pile TS; | TS est un travail supplémentaire, c'est à dire une liste de termes devant être unifiés. |
while (!IsVide(K)) { | Tant que la liste K des travaux n'est pas vide. |
T = Depile(K); | On retire de K un premier travail T. T est une liste de termes devant être unifiés. |
n = Num(T); | n est le numéro du travail T en cours. |
U = Depile(T); | On retire de T un premier terme U. U est un terme. |
switch (Type(U)) { |
Selon le type de U, on lance le sous-programme appropriée. |
} | |
exit(); |
constante : | U est une constante. |
while (! IsVide(T)) { | Tant que la liste T des termes n'est pas vide. |
V = Depile(T); | On retire de T un terme V. V est un terme qui va être unifié à la constante U. |
switch (Type(V)) { |
|
case 0: if (*V<>*U) return FAIL; break; |
Si V est une constante alors : Si la constante U est différente de la constanteV, on retourne FAIL. |
case 1: *V = U; break; |
Si V est une variable libre alors : On affecte V à U. |
case 2: return FAIL; |
Si V est un noeud alors : On retourne FAIL. |
} | |
} |
variable : | U est une variable libre. |
while (! IsVide(T)) { | Tant que la liste T des termes n'est pas vide. |
V = Depile(T); |
On retirer de T un terme V. |
switch (Type(V)) { |
|
case 0: |
Si V est une constante alors : On affecter U à V. On passe la main au sous-programme constante. |
case 1: *U = V; break; |
Si V est une variable libre alors : On affecter U à V. |
case 2: if (IsMarque(V,n)) return FAIL; Marque(V,n); *U = V; goto noeud; |
Si V est un noeud alors : |
} |
noeud : | U est un noeud. | |
bool b = FALSE; | Alloue un flag b qui est FALSE tant qu'il n'y a pas d'ajout dans les travaux supplémentaires. | |
if (IsMarque(U,n)) return FAIL; Marque(U,n); |
Si U est déja marqué par n, on retourne FAIL.
On marque U par n. |
|
KS = CreerPile(); | Alloue dynamiquement une pile KS. | Creer une pile KS de travaux supplémentaires. Et met un fils dans chaque travail supplémentaire. |
for(int i=0;i<Arite(U);i++) { | Pour chaque fils de U. | |
TS = CreerPile(); | Alloue dynamiquement un travail TS. | |
Num(TS) = n; |
Numérote la pile TS avec n. | |
R(U[i]); | Evalue le i-ième pointeur du noeud U. | |
Empile(TS,U[i]); | Empile le i-ième fils de U dans TS | |
Empile(KS,TS); | Empiler TS dans KS. | |
} | ||
while (! IsVide(T)) { | Tant que la liste T des termes n'est pas vide. | |
V = Depile(T); | On retire de T un terme V V est un terme qui va être unifié au noeud U. |
|
switch (Type(V)) { |
||
case 0: return FAIL; |
Si V est une constante alors : On retourne FAIL |
|
case 1: *V = U; break; |
Si V est une variable libre alors : On affecter V à U. |
|
case 2: if (Arite(U)<>Arite(V)) return FAIL; if (IsMarque(V,n)) return FAIL; Marque(V,n); for(int i=0;i<Arite(V);i++){ R(V[i]); Empile(KS[i],V[i]); } b = TRUE; |
Si V est un noeud alors : |
|
} | ||
if (b) |
Si il y a plus d'un terme dans un travail supplémentaire
alors : On insére dans K la liste KS des travaux supplémentaires. |
|
else for(int i=0;i<Arite(U);i++) Libere(KS[i]); libere(KS); |
Sinon on libére les travaux supplémentaires KS[i] pour
i variant de 0 à la valeur de l'arité du noeud U, moins
1. Chaque travail est une pile. |
}
Un message contient une liste terminale-close, et représente un mot dans le langage L°cs. Par exemple, la liste terminale-close a, f(b,.) se comporte comme un opérateur de type (2,1), c'est à dire d'arité de sortie 2 et d'arité d'entré 1.
( a, f(b,.) ) (a,b) = ( a, f(b,a), b )
On peut supprimer les opérateurs point en places terminales en faisant jouer la currification :
f(b,.) = f(b) = fb
(a, f(b,.)) = (a, f(b)) = (a, fb)
fba = f(b)(a) = f(b,.)(a)= f(b,a) = fba
(a,fb)(a,b) = (a, f(b))(a,b) = (a, f(b,.))(a,b) = (a, f(b,a), b) = (a, fba, b)
Le procédé de currification, ainsi que la logique polonaise par palier, sont misent en oeuvre. Ce langage, noté L°cs, permet de construire les opérateurs dits L-emboitable avec currification et séquence finie.
Si on ajoute l'opérateur identité "." de type (1,1), alors le langage devient un langage d'opérateurs simple unitaire avec currification et séquences finies, noté L¢us. Ce langage permet de construire les opérateurs dits L-constructible-faible.
Les règles se comportent comme des opérateurs. Ils sont des opérateurs dans un langage d'opérateur d'arité fixé simple, et leurs compositions peuvent être évalué par le procédé de duplication et d'unification. La duplication des variables est nécessaire pour les rendres indépendantes entre les règles composant la composition.
Un ensemble de règles forme une grammaire et engendre un langage.
10) Les grammaires
Les règles engendrent d'autres règles grace au procédé de duplication et d'unification. Par exemple, soit les deux règles suivantes :
r1 = h(X,X) --> X
r2 = g(X,f(Y)), f(X) --> h(X,Y)
La règle r2 d'arité 2 peut se composer avec la règle r1 d'arité 1 en la règle r1(r2) d'arité 2 (voir composition d'opérateur dans un langage d'operateur d'arité simple) On duplique la règle r1 = h(X1,X1)-->X1 et la règle r2 = g(X2,f(Y2)), f(X2) --> h(X2,Y2) de tel sorte qu'elles n'ont pas de variables communes. Puis on unifit la sortie de r2 avec l'entré de r1, on unifit h(X2,Y2) et h(X1,X1), ce qui affecte les variables X1 = X2, Y2 = X2. Et on reconstruit la nouvelle règle avec l'entré de r2 et la sortie de r1 en repportant les valeurs des variables. r1(r2) = g(X2,f(X2)),f(X2) --> X2. Puis on duplique la règle en nommant la variable X. Ainsi nous avons :
r1(r2) = g(X,f(X)), f(X) --> X
r2(r1,r1) = h(g(X,f(Y)),g(X,f(Y))), h(f(X),f(X)) --> h(g(X,f(Y)),f(X))
r1(r1) = h(h(X,X),h(X,X)) --> X
...
11) Règle de simplification des termes de L°[X,Y,Z]
Un terme r de L°[X,Y,Z], désigne l'ensemble des termes de L unifiable à r. On définie une relation d'équivalence entre termes à permutation près des variables, noté abusivement par =. On dira qu'un terme r contient un terme s que l'on notera r>s, si et seulement si son ensemble contient celui de s. Cela correspond exactement au fait que l'unification après duplication, entre r et s, produit s à une permutation des variables près. On note & l'opération de duplication et d'unification donnant comme résultat un terme à permutation près de ses varianles.
r = g(X,g(Y,f(Z)))
s = g(g(X,f(Y)),g(Y,f(a)))r&s = g(g(A,f(B)),g(B,f(a))) = s
Dans une grammaire, les termes inclus dans un autre terme peuvent être supprimé sans que cela modifit le langage de la grammaire. Ainsi ne sont gardés que les termes les plus généraux.
12) Règles de simplification des règles
Une règle est sans effet si la production est présente dans l'entré. Ainsi la règle f(X), g(X) --> f(X) est nulle, et peut être enlevé de la grammaire sans modifier son langage.
Une règle possédant deux termes identiques dans la séquence d'entré, peut être simplifié en enlevant un des deux termes et en réduisant donc son arité. Ainsi la règle f(X), f(X) --> g(X,X) se simplifit en f(X) --> g(X,X).
Une règle r1 est inclus dans une autre règle r2 si elle peut être obtenue à partr de r2 par simple restriction. C'est à dire si les entrées de la règle r2 contiennent les entrés de la règle r1 et s'unifient pour produire un terme résultat qui contienne le terme résultat de la règle r1. Par exemple :
r1 = f(U) --> h(f(U),f(b),a)
r2 = X, Y --> h(X,Y,Z)
L'entré de r1, f(U) est incluse dans l'entré de r2, X et dans l'entré de r2, Y. L'unification de l'entré r2 avec autant de réplique de l'entré de r1, va produire une sortie de r2 , h(f(U1),f(U2),Z) qui contient la sortie de r1, h(f(U),f(b),a).
Les règles incluses dans une autre règle peuvent être supprimé sans que cela modifit le langage. Ainsi ne sont gardés que les règles les plus générales.
14) Les axiomatiques
On appel axiomatique un ensemble A de règles dans lequel aucune règle ne peut être produite par une combinaison des autres ni obtenu par une restriction des autres règles. Les règles de A sont appelés axiomes. On note A|-r lorsque on peut construire la règle r par composition de règles de A.
On définie deux complexitées : La taille qui est le nombre d'opérateurs présent dans l'expression de la règle. Et la A-complexité qui est le nombre minimal de règles de A dans une composition produisant la règle. (Les A-complexités des axiomes valent 1.)
La définition d'un opérateur g d'arité 2, utilise le symbole binaire --> de création d'opérateur (qui a une priorité syntaxique plus forte), et utilise le symbole = d'arité 2 qui affecte le rôle d'opérateur à un identifiant. Par exemple :
g = (X,Y)-->f(X,f(X,Y))
On donne ainsi à g le rôle d'opérateur 2-aire, de tel sorte que g(a,b) est remplacé lors de l'évaluation par f(a,f(a,b)). Mais le symbole = est superflux. En effet on peut le remplacer par une convention : le premier terme de l'opérateur --> contient l'identifiant, suivie de la liste des variables muettes, devant être affecté par ce nouvel opérateur. L'affectation précédente de g s'écrit alors simplement :
g(X,Y)-->f(X,f(X,Y))
Et cela devient une règle de définition et de transformation du nouvelle opérateur g. Plusieurs nouveaux opérateurs peuvent être créés ainsi et ajoutés au langage. Le message contient l'expression utilisant ces nouveaux opérateurs, et contient les définitions des opérateurs, dans un ordre quelconque. Par exemple :
f(g(s(a),b),g(a,h(a))), g(X,Y)-->f(X,f(X,Y)), h(X)-->s(f(X,X))
La définition d'un opérateur précise son arité à l'aide de la liste de variable muettes utilisées. Comme celle-ci n'est pas connue à l'avance, on ne peut pas appliquer la même syntaxe. L'arité du nouvel opérateur doit être transmise dans le message. La solution naturelle consiste à utiliser le symbole --> avec une syntaxe centré, ce qui permet d'évaluer l'arité du premier terme qui doit être de la forme nom-de-l'opérateur suivie par une liste de variables muettes. Le message brut est alors : fgsabgaagXY-->fXfXYhX-->sfXX et il transmet bien la création d'opérateurs g d'arité 2 et h d'arité 1.
Ce message ne peut être compris que grace à la connaissance du langage L = {a, b, s(.), f(.,.)} et du meta-opérateur (.-->.) en notation centré, qui permet de définir les nouveaux opérateurs {g(.,.), h(.)} et les nouvelles variables muettes {X, Y}, définies dans le message lui-même.
Chaque règle peut à partir des termes déja calculé produire d'autres termes. Un terme peut être considéré comme une règle particulière, une règle sans premier terme. Par exemple le terme g(a,b) correspond à la règle -->g(a,b).
On généralise les règles en les faisant appliquer sur une liste de premier terme. La règle f(X),g(X,Y)--> h(Y,X) appliqué à deux termes dans le même ordre f(a), g(a,b), produit le terme h(b,a).
On définie un opérateurs d'application d'arité 3 noté identiquement @. Cette opérateur prend en premier argument une règle et comme second et troisième argument deux termes et retourne comme terme résultat le résultat de l'application de la foncion sur les deux termes en question. Si l'unification échoue l'opérateur retourne le terme FAIL de type FAIL.
Ainsi nous avons :
f(X),Y -->g(f(Y),X) @ a,b = FAIL
f(X),X-->g(XX) @ f(a),a = g(a,a)
X,Y-->g(XY) @ f(a),b = g(f(a),b)
X,f(Y)-->(g(f(X),Y) --> h(Y,X)) @ a, f(b) = g(f(a),b) --> h(b,a)
g(X,Y),f(Y) -->h(Y,X) @ g(a,b),f(b) = h(b,a)
f(X),f(Y) -->h(Y,X) @ f(Y),f(b)) = h(b,b)
On définie les opérateurs de création d'opérateur d'arité 4,5,6... notés -->, et les opérateurs d'application d'arité 4,5,6... notés @ de la même façon. Nous avons définie des opérateurs de création d'opérateur --> d'arité diverse et des opérateurs d'application d'opérateurs @ d'arité diverse, tout en restant dans un langage d'opérateur simple à 2 types.
Les règles se comportent comme des opérateurs. Ils sont des opérateurs dans un langage d'opérateur d'arité fixé simple, et leurs compositions peuvent être évalué par le procédé de duplication et d'unification. La duplication des variables est nécessaire pour les rendres indépendantes entre les règles composant la composition.
Un ensemble de règles forme une grammaire et engendre un langage.
10) Les grammaires
Les règles engendrent d'autres règles grace au procédé de duplication et d'unification. Par exemple, soit les deux règles suivantes :
r1 = h(X,X) --> X
r2 = g(X,f(Y)), f(X) --> h(X,Y)
La règle r2 d'arité 2 peut se composer avec la règle r1 d'arité 1 en la règle r1(r2) d'arité 2 (voir composition d'opérateur dans un langage d'operateur d'arité simple) On duplique la règle r1 = h(X1,X1)-->X1 et la règle r2 = g(X2,f(Y2)), f(X2) --> h(X2,Y2) de tel sorte qu'elles n'ont pas de variables communes. Puis on unifit la sortie de r2 avec l'entré de r1, on unifit h(X2,Y2) et h(X1,X1), ce qui affecte les variables X1 = X2, Y2 = X2. Et on reconstruit la nouvelle règle avec l'entré de r2 et la sortie de r1 en repportant les valeurs des variables. r1(r2) = g(X2,f(X2)),f(X2) --> X2. Puis on duplique la règle en nommant la variable X. Ainsi nous avons :
r1(r2) = g(X,f(X)), f(X) --> X
r2(r1,r1) = h(g(X,f(Y)),g(X,f(Y))), h(f(X),f(X)) --> h(g(X,f(Y)),f(X))
r1(r1) = h(h(X,X),h(X,X)) --> X
...
11) Règle de simplification des termes de L°[X,Y,Z]
Un terme r de L°[X,Y,Z], désigne l'ensemble des termes de L unifiable à r. On définie une relation d'équivalence entre termes à permutation près des variables, noté abusivement par =. On dira qu'un terme r contient un terme s que l'on notera r>s, si et seulement si son ensemble contient celui de s. Cela correspond exactement au fait que l'unification après duplication, entre r et s, produit s à une permutation des variables près. On note & l'opération de duplication et d'unification donnant comme résultat un terme à permutation près de ses varianles.
r = g(X,g(Y,f(Z)))
s = g(g(X,f(Y)),g(Y,f(a)))r&s = g(g(A,f(B)),g(B,f(a))) = s
Dans une grammaire, les termes inclus dans un autre terme peuvent être supprimé sans que cela modifit le langage de la grammaire. Ainsi ne sont gardés que les termes les plus généraux.
12) Règles de simplification des règles
Une règle est sans effet si la production est présente dans l'entré. Ainsi la règle f(X), g(X) --> f(X) est nulle, et peut être enlevé de la grammaire sans modifier son langage.
Une règle possédant deux termes identiques dans la séquence d'entré, peut être simplifié en enlevant un des deux termes et en réduisant donc son arité. Ainsi la règle f(X), f(X) --> g(X,X) se simplifit en f(X) --> g(X,X).
Une règle r1 est inclus dans une autre règle r2 si elle peut être obtenue à partr de r2 par simple restriction. C'est à dire si les entrées de la règle r2 contiennent les entrés de la règle r1 et s'unifient pour produire un terme résultat qui contienne le terme résultat de la règle r1. Par exemple :
r1 = f(U) --> h(f(U),f(b),a)
r2 = X, Y --> h(X,Y,Z)
L'entré de r1, f(U) est incluse dans l'entré de r2, X et dans l'entré de r2, Y. L'unification de l'entré r2 avec autant de réplique de l'entré de r1, va produire une sortie de r2 , h(f(U1),f(U2),Z) qui contient la sortie de r1, h(f(U),f(b),a).
Les règles incluses dans une autre règle peuvent être supprimé sans que cela modifit le langage. Ainsi ne sont gardés que les règles les plus générales.
14) Les axiomatiques
On appel axiomatique un ensemble A de règles dans lequel aucune règle ne peut être produite par une combinaison des autres ni obtenu par une restriction des autres règles. Les règles de A sont appelés axiomes. On note A|-r lorsque on peut construire la règle r par composition de règles de A.
On définie deux complexitées : La taille qui est le nombre d'opérateurs présent dans l'expression de la règle. Et la A-complexité qui est le nombre minimal de règles de A dans une composition produisant la règle. (Les A-complexités des axiomes valent 1.)
5) L'unification simple
L'unification d'un terme de <L[X,Y]> avec un terme constant de <L> est un algorithme suivant :
Unifi1 = proc(A,B)
begin
if @A=@B returne True; end_if;
if Arite(A)#Arité(B) then return False; end_if;
if IsVariable(A) then Affecte(A,B); return true; end_if;
if Arite(A)=0 then return IsEgale(A,B); end_if;
return ET(Unifi1,A,B);
end;
U : C'est une variable contenant un terme de <L[X,Y]>.
@U : Retourne l'adresse mémoire de U.
Arite(U) : Retourne l'arité du premier opérateur du terme contenue
dans U.
IsVariable(U) : Returne True ssi U contient une variable.
Affecte(U,V) : Affecte la variable contenue dans U au terme contenue dans V.
IsEgale(U,V) : Return True ssi le terme contenu dans U est égale au terme
contenue dans V.
ET(f,U,V) : Effectue un ET sur les résultats de la fonction f appliqué
en parallèle sur les fils des termes contenue dans U et V.
L'auto réalisation consiste à compléter le langage afin que le programme d'unification précédant y soit exprimable.
Nous avons augmenté le langage. Les règles de déduction écrites dans la méta-théorie sont augmenté d'une règle complexe d'unification comme suit :
la règle de production classique, écrite dans le langage en question augmenté des variables universelles X, Y, Z...., de l'opération de production --> et de l'opérateur de création de liste noté par une virgule ",". Par exemple la règle r1 suivante :
r1 = (s(Y), f(X,Y), f(a,X)) --> f(X,Z)
Noter que les symboles "r1" et "=" ici, font partie d'un autre meta-langage utile pour la programmation. L'expression syntaxique correspond en notation lispienne à une liste pointé :
(s(Y), f(X,Y), f(a,X) · f(X,Z)) Notation lispienne.
et correspond mathematiquement, grâce au procédé de currification, à la définition d'une fonction unaire de fonction unaire de fonction unaire :
r1 = ( s(Y)--> ( f(X,Y) --> ( f(a,X) --> f(X,Z) ) ) )
C'est un opérateur binaire, opérant sur un n-uplet et un terme tel que par exemple la règle r1 suivante :
r1 = (s(Y), f(X,Y), f(a,X)) --> f(X,X)
Ces règles de production d'éléments formes une sorte de grammaire, dont la clôture et l'ensemble infini en question. Les règle de production sont simplement des exemples que l'on généralise en introduisant des variables pouvant être égalisée avec tous les éléments de <L> et dont l'hypothèse
Les fonctions d'arité diverses du langage sont les fonctions engendrés par compositions. L'ensemble de ces fonctions, noté <<L>>, est appellé la cloture par compositon de fonction de L.
<<L>> = {a, x->s(x), f(b,s(b)), (x,y)->f(s(x),f(y,x)), x->f(x,x), (x,y,z)-->s(y)....}
Noter que x,y,z... sont des variables muettes qui ne figurent donc pas dans la présentation du langage L.
LPrésentation finie du langage L. <L>Ensemble des éléments du langage L. <<L>>Ensemble des fonctions d'arité diverse du langage L.
3) Le langage propositionel
Une proposition n'est pas un élément, c'est pourquoi on crée une deuxième couche de langage au dessus du langage d'éléments pour définir un langage de propositions. Le langage propositionnel s'obtient par l'ajout de prédiats. Un prédicat n-aire est une fonction n-aire, qui prend donc en arguments n éléments atteignable par le langage d'éléments en question, et retourne une valeur booléenne True ou False.
Les premiers prédicats utilisés sont l'égalité et l'inégalité. Pour l'instant nous n'utiliserons que ces deux là. il n'y aura donc que deux sortes de proposition : les égalités et les inégalités. D'autre part nous avons volontairement omit de définir des opérateurs logiques, de tel sorte que notre langage propositionel ne permet pas pour l'instant d'écrire une alternative.
La raison pour laquel nous choississons ces deux prédicats tient dans l'étude des langages formelles. L'égalité est utilisé comme moteur pour définir un mécanisme de substitution.
Dans l'exemple en construction, le langage propositionel noté LP a comme présentation le couple suivant :
LP = ({a,b,s(.), f(.,.)}, {=(.,.), (.,.)})
Le premier ensemble désigne la présentation des éléments, et le second ensemble énumère les prédicats utilisés. Les propositions du langage LP sont :
<LP> = {a=b, bb, s(a)=a, f(a,s(b))=f(b,b), s(a)s(b)....}
Les fonctions propositionnelles d'arité diverse du langage LP sont :
<<LP>> = {a=a, x-->s(x)=b, x-->xf(x,a), (x,y)-->f(x,b)=f(x,y)....}
Noter que x,y,z... sont des variables muettes qui ne figurent donc pas dans la présentation du langage LP.
Le langage propositionel est une machine, un processus qui génère toutes les propositions, vrai ou fausse, qui peuvent être écritent dans le langage en question.
LP |
Présentation finie du langage propositionnel. |
<LP> |
Ensembles des propositions (vrai ou fausse) du langage. |
<<LP>> |
Ensemble des fonctions propositionelles d'arité diverse du langage. |
A cette étape, le sense des prédicats = et n'est pas définis, même s'ils ont été choisis pour des raisons sémantiques évidentes, ces raisons ne sont pas encore définies. La syntaxe seul est définie.
4) La théorie
Une théorie T est définie par un ensemble finie, une collection, de propositions écrites dans un langage propositionnel. L'ensemble doit être fini, afin de pouvoir l'appréhender globalement et de construire par dessus un processus d'énumération des propositions démontrables par la théorie, et évidemment exprimable dans le langage propositionel.
Une théorie comprenant une infinité de propositions énumérées par un processus, se ramène, par extension du langage, à une théorie comprenant un nombre fini de propositions. Il suffit pour cela d'étendre le langage avec le meta-langage qui a été utilisé pour écrire le processus énumérant les propositions en question.
La théorie T peut être définie par une collection minimale de propositions. Dans ce cas, cette collection est appelée une axiomatique.
La théorie T est une machine, un processus qui génère toutes les propriétés démontrables à partir de T. La description du processus, l'aspect dynamique de la théorie, n'est pas écrite dans l'axiomatique de T. Elle est implicite. Nous la rendons explicite en exhibant les règles de déduction. Ces règles constituent une méta-théorie écrites dans un meta-langage.
5) Le méta-langage
Pour écrire le processus de la théorie, son aspect dynamique, son moteur, nous avons besoin d'un langage plus riche appelé méta-langage. Par analogie à la définition d'une pile de protocoles en informatique, on décompose le langages en plusieurs couches : La première couche est le langage comprenant les deux sous-couches, langage d'éléments et langage propositionel, dans lequel sont exprimées les théories. La seconde couche est le meta-langage comprenant un mécanisme d'unification et dans lequel sont exprimées les méta-théories.
Le méta-langage comprend le symbôle de production --> qui va permettre d'écrire les règles de productions (devant transcrire les règles de déductions). C'est un opérateur binaire, opérant sur un n-uplet et un terme. Par exemple la règle (s(Y), f(X,Y), f(a,X)) --> f(X,X)
Cette règle de production fonctionne ainsi : on trouve un n-uplet de terme que l'on unifit au n-uplet si la première proposition est présente alors il y a production de la seconde proposition. On note également un opérateur --> unaire opérant sur une proposition, qui signifie la production de cette proposition sans autre forme de condition.
Le méta-langage utilisera 3 types de variables universelles :
1) Des variables universelles notées X, Y, Z..., représentant les éléments de <L>.
2) Des variables universelles notées F, G, H..., représentant les fonctions unaires appartenant à <<L>>.
3) Des variables universelles notées P, Q, R..., représentant les fonctions propositionelle unaires appartenant à <<LP>>.
L'ajout des variables universelles introduit le mécanisme d'unification. Et la description détaillée de ce mécanisme est écrite dans un meta-meta-langage.
Par abus, nous noterons également par <<L>> l'ensemble des seuls fonctions unaires, et par <<LP>> l'ensemble des seuls fonctions propositionnelles unaires.
Ce meta-langage permet de définir des moteurs suivants :
Le moteur générant les éléments de <L>:
Quelque_soit X appartenant à <L>, --> XLe moteur générant les fonctions unaires de <<L>>:
Quelque_soit F appartenant à <<L>>, --> FLe moteur générant les propositions de <LP>:
Quelque_soit P appartenant à <<LP>>, Quelque_soit X appartenant à <L>, --> P(X)Le moteur générant les fonctions propositionelles unaires de <<LP>>:
Quelque_soit P appartenant à <<LP>>, --> P
6) La méta-théorie
La meta-théorie doit préciser toutes les règles de déductions opérables sur les ensembles finis de propositions de <LP>, c'est à dire sur un ensemble fini d'égalités et d'inégalités de termes de <L>. Voici la meta-théorie que nous proposons :
Quelque_soit les éléments X,Y appartenant à <L>,
Quelque_soit une fonction unaire F appartenant à <<L>>,
Quelque_soit une fonction propositionnelle unaire P appartenant à <<LP>>,
La reflexivité de l'égalité --> X=X La symétrie de l'égalité X=Y -->Y=X La symétrie de l'inégalité XY -->YX L'implication fonctionnelle X=Y --> F(X)=F(Y) La substitution X=Y, P(X) --> P(Y) La contradiction XX --> P(Y)
Le moteur applique chacune de ces 6 règles. Pour appliquer une règles il recheche parmi ses propositions de départ et parmi celles déja produites, un n-uplet de propositions unifiables avec le n-uplet se trouvant à gauche du symbôle -->, Puis il applique la règle et produit la proposition qui est à droite du symbôle -->. Lorsque la partie droite contient une variable universelle libre (qui n'apparait donc pas dans la partie gauche), il faut la remplacer par toutes les valeurs possibles que permet le langage correspondant à la variable universelle en question, dans ce cas la production n'est pas une proposition proprement dite mais un nouveau processus générant des propositions.
Nous avons posé ces 6 règles de déduction, en essayant d'utiliser un meta-langage le plus simple possible. Les fonctions propositionelles unaires sont générées par le langage <<LP>> de la même façon que les fonctions unaires sont générés par le langage <<L>>, et donc nous pensons que leurs présences n'enrichissent pas exagérément le méta-langage.
Les 2 règles de symétrie sont intrinsèques aux prédicats = et . Elle peuvent être supprimées en prenant une représentation des données intégrant cette propriété. On écrit la déclaration des prédicats binaires avec des acolades ={.,.}, {.,.}pour rappeler la représentation symétrique des données. Noter que la représentation des données devra être décrite dans un autre meta-langage.
La présentation du langage propositionnelle devient :
LP = ({a,b,s(.), f(.,.)}, {={.,.}, {.,.}}).
Le premier ensemble désigne la présentation des éléments, et le second ensemble énumère les prédicats utilisés, avec des acolades précisant la propriété de symétrie qui leur sont propres.
La règle de contradiction peut être supprimée, en l'intégrant dans le fonctionnement du moteur : Le moteur s'arrête s'il rencontre une proposition unifiable à XX.
La règle de reflexivité de l'égalité n'est pas utilisé au cours des démonstrations. Elle l'est isolément pour produire la proposition X=X qui n'est pas utilisable par la suite, donc elle ne sert à rien et peut être supprimer, en intégrant dans le moteur cette postproduction de propositions.
La méta-théorie proposée ne contient plus que deux règles de déductions que sont l'implication fonctionnelle et la substitution :
Quelque_soit les éléments X,Y appartenant à <L>,
Quelque_soit une fonction unaire F appartenant à <<L>>,
Quelque_soit une fonction propositionnelle unaire P appartenant à <<LP>> :
L'implication fonctionnelle X=Y, --> F(X)=F(Y) La substitution X=Y, P(X) --> P(Y)
Noter que la partie du fonctionnement du moteur qui n'est pas décrite dans ces 2 règles, devra être décrite dans un meta-meta-langage.
7) La preuve statistique
La plus simple façon de vérifier si la meta-théorie contient vraiment toutes les règles de déduction, est de la mettre en oeuvre en un programme informatique. Le cas est simple puisqu'il n'y a pas de variable autre que celles mentionnées dans les règles de déduction. Les termes sont des arbres clos de Herbrand.
L'application de la règle d'implication fonctionnelle se fait en choisissant une égalité, puis en unifiant X et Y au terme gauche et droit de l'égalité, puis fournie une proposition avec un opérateur variable unaire indépendant noté F. Et cette proposition générative engendre une infinité de proposition en remplaçant F par un opérateur unaire appartenant à <<L>>.
L'application de la règle de substitution se fait en choisissant une égalité, propositionnelle unaire, puis en unifiant X et Y au terme gauche et droit de l'égalité, puis fournie une proposition en substituant chaque occurence de X par Y. Et cette proposition générative engendre une infinité de proposition en remplaçant F par un opérateur unaire appartenant à <<L>>.
.......................
Soit la théorie T = {s(a)=a, s(b)=f(b,a), f(a,s(a))=f(b,s(b)), f(a,b)=b, f(b,a)=b, f(b,b)=a}. Le moteur va produire les générateurs F(X)=F(Y) pour chaque proposition X=Y
7) L'extention naturelle du langage
On étend le langage d'élément en ajoutant des variables universelles. Par exemple, on note <L[X1, X2]> le langage <L> augmenté de deux variables universelles X1, X2 et de même on note <LP[X1, X2]> le langage <LP> augmenté de deux variables universelles X1, X2 de type <L>.
On étend le langage propositionel en ajoutant autant de variables universelles de type <L> que l'on souhaite et qui sont notées X1, X2, X3..... Les mots de <L[X1, X2, X3...]> sont appelé des termes.
La variable universelle représente un élément quelconque de <L>. Comme nous n'ajoutons qu'un seul type de variable universelle, il n'est pas nécessaire de les déclarer préalablement par un quantificateur, Quelque_soit, typé. Par convention, les variables qui apparaissent dans un terme ou une proposition, et qui ne font pas partie du langage, sont universelles de type <L> et possèdent un quantificateur Quelque_soit.
Par exemple la proposition f(X,a) = f(X,X) sous entend Quelque_soit X appartenant à <L>.
Par exemple le terme f(X,X) désigne le sous-ensemble de tous les éléments de <L> unifiables à ce terme.
Nous avons augmenté le langage. Les règles de déduction écrites dans la méta-théorie sont augmenté d'une règle complexe d'unification comme suit :
Quelque_soit les termes X,Y,A,B appartenant à <L[X1, X2, X3...]>,
Quelque_soit une fonction unaire F appartenant à <<L[X1, X2, X3...]>>,
Quelque_soit une fonction propositionnelle unaire P appartenant à <<LP[X1, X2, X3...]>> :
L'implication fonctionnelle X=Y --> F(X)=F(Y) La substitution X=Y, P(X) --> P(Y) L'unification X=A, Y=B --> (A=B)/(X unifié à Y)
Les variables universelles invoquées vont permettre d'écrire des termes désignant des ensembles et des fonctions, et vont permettre de mettre en oeuvre un procédé de raisonnement appelé unification. Pour l'instant, la meta-théorie devient :
Quelque_soit les éléments X,Y,A,B appartenant à <L[X1, X2, X3...]>,
Quelque_soit une fonction unaire F appartenant à <<L[X1, X2, X3...]>>,
Quelque_soit une fonction propositionnelle unaire P appartenant à <<LP[X1, X2, X3...]>> :
X=Y, --> F(X)=F(Y)
X=Y, P(X) --> P(Y)
X=A, Y=B --> (A=B)/(X unifié à Y)
10) La fonction caractèristique d'un ensemble de base
Soit ensemble de base, définie par le terme W appartenant à <L[X1,X2,X3...]>. Et soit un élément x de <L>. La fonction caractéristique de l'ensemble de base W est égale à :
x --> (delta ° U)(W, x).
La fonction d'unification U, appliqué à un terme W et à un élément x de <L>, retourne soit FAIL ou soit une liste dont le premier terme est l'élément x en question, suivi de la valeurs des variables universelles unifiées. L'application delta transforme FAIL en False, et tout autre réponse en True. Ainsi par exemple :
U( f(X1,X1), f(a,b) ) = FAIL (delta°U)( f(X1,X1), f(a,b) ) = False
U( f(X1,X1), f(a,a) ) = ( f(a,a), a ) (delta°U)( f(X1,X1), f(a,a) ) = True
U( f(X1,X2), f(a,s(b)) ) = ( f(a,s(b)), a, s(b) ) (delta°U)( f(X1,X2), f(a,s(b)) ) = True
(Noter l'utilisation d'une autre conception de variable écrites en bleu italique, W et x dans le texte. Ces variables sont nécessaires pour écrire un algorithme. Elles font l'objet d'une évaluation à un niveau donnée dans la pile des protocoles, et ils faut les remplacer par leur valeur.)
11) Les fonctions de base
Un terme indicé Wn, c'est à dire un mot W de <L[X1,X2,X3...]> munie d'un entier n noté en indice et désignant une arité, définit une fonction de <L>n vers E(L) à l'aide du prototype de fonction suivant : (X1,X2,X3...,Xn)-->W. Par exemple :
f(X2,X4)3 = (X1,X2,X3)-->f(X2,X4)
Dans cette exemple, la fonction appliqué à 3 mots de <L> va produire un terme qui désignera un ensemble de base.
Les fonctions de <L>n vers E(L) exprimables par un terme indicé, sont dit de base. Les termes indicés désignant la même fonction, dans le cas où la structure <L> est libre, s'obtiennent à partir de l'un d'entre eux et en permutant les variables à l'exception de celles présentes dans l'appel de la fonction.
On appel F(L) l'ensemble des fonctions de base pour le langage de présentation L. F(L) représente l'ensemble des classes d'équivalence sur (<L[X1,X2,X3...]>*N) à une permutaion près des variables universelles (X1,X2,X3...) :
F(L) = (<L[X1,X2,X3....]> * N) / Permutation(X1,X2,X3....)
Terme indicé |
Fonction de base |
Notation |
Interprétation élémentaire |
Interprétation ensembliste |
Ø1 |
X1-->Ø |
x-->Ø |
Fonction définie nulle part. |
Fonction constante retournant l'ensemble vide. |
X11 |
X1-->X1 |
x-->x |
Fonction identité. |
Fonction de x retournant le singleton {x}. |
a1 |
X1-->a |
x-->a | Fonction retournant toujours le même élément a. |
Fonction retournant toujours le même ensemble {a}. |
f(a,X1)1 |
X1-->f(a,X1) |
x-->f(a,x) |
Fonction retournant un élément. |
Fonction retournant un ensemble singleton. |
f(X1,f(a,X2))1 |
X1-->f(X1,f(a,X2)) |
x-->f(x,f(a,X)) |
Fonction retournant un terme. | Fonction retournant un ensemble de base. |
s(a)0 |
s(a) |
s(a) |
Elément. | Ensemble singleton {s(a)}. |
f(X1,X1)0 |
f(X1,X1) |
f(X,X) |
Terme. | Ensemble de base. |
s(X5)2 |
(X1,X2)-->s(X5) |
(x,y)-->s(X) |
Fonction retournant toujours le même terme. | Fonction retournant toujours le même ensemble de base. |
12) La fonction inverse d'une fonction de base
Soit une fonction de base définie par le terme indicé Wn. La fonction inverse d'une fonction de base Wn est égale à :
x --> (µ°U)(W,x)
La fonction d'unification U, appliqué à un terme W et à un élément x de <L>, retourne soit FAIL ou soit une liste dont le premier terme est l'élément x en question, suivi des valeurs des variables universelles unifiées. L'application µ transforme FAIL en Ø et tranforme une liste en la même liste dans laquel on a enlevé le premier terme. Ainsi par exemple :
U( f(X1,X1), f(a,b) ) = FAIL (µ°U)( f(X1,X1), f(a,b) ) = Ø
U( f(X1,X1), f(a,a) ) = ( f(a,a), a ) (µ°U)( f(X1,X1), f(a,a) ) = (a)
U( f(X1,X2), f(a,s(b)) ) = ( f(a,s(b)), a, s(b) ) (µ°U)( f(X1,X2), f(a,s(b)) ) = (a, s(b))
8) L'unification de n termes
L'unification de n termes n'ayant pas de variables universelles communes deux à deux, produit comme résultat, un terme qui correspond à l'ensemble intersection des ensembles correspondants aux n termes.
L'unification de deux termes ayant une variables universelles communes, produit comme résultat, un terme qui correspond
Un ensemble de base est désigné par un terme appartenant à (<L[X1,X2,X3...]> union {Ø}). Par exemple :
Un terme indicé Wn, c'est à dire un mot W de <L[X1,X2,X3...]> munie d'un entier n, noté en indice et désignant l'arité, définit une fonction de <L>n vers <L[X1,X2,X3...]> dont le prototype est (X1,X2,X3...,Xn)-->W . Par exemple :
f(X2,X4)3 = (X1,X2,X3)-->f(X2,X4)
Les fonctions de <L>n vers <L[X1,X2,X3...]> exprimables par un terme indicé, sont dit de base.
De tel fonctions s'étendent de façon unique à des fonctions de (<L[X1,X2,X3...]> union {Ø}) vers (<L[X1,X2,X3...]> union {Ø}).
Une fonction de base est désignée par un terme indicé appartenant au produit cartesien de (<L[X1,X2,X3...]> union {Ø}) et de N. Par exemple :
On remarque
1) une bijection entre le produit cartesien <L[X1,X2,X3...]> * N et <<L[X1,X2,X3...]>>
9) Algorithme de factorisation
La factorisation consiste à trouver les sous-arbres égaux et à les unifier, et en généralisant au cas des termes récurcifs, à trouver les sous-graphes égaux et à les unifier. Pour cela, on parcours les couples de noeud du graphe, on regarde s'ils sont unifiables et l'on procède à la modification physique du graphe.
Un terme est représenté par un graphe orienté possédant une racine. L'ordre canonique des noeuds du graphe consiste à parcourir le graphe en profondeur à partir de la racine et en remontant de gauche à droite chaque noeud et en ne repassant jamais par un noeud déja traversé. La profondeur d'un noeud est le plus petite nombre de liens père-fils traversés pour passer de la racine au noeud en question.
La description de l'algorithme nécessite de définir un meta-langage composé d'opérations élémentaires, soit en d'autre terme, de définir un langage de programmation. On définie la constante r0 qui désigne le noeud racine du graphe que l'on traite. On définie des variables X, Y, Z qui désignent 3 noeuds du graphes ou la valaur NIL. On définie la fonctions Frere(.) qui retourne le noeud frere suivant, et qui retourne NIL s'il n'y a plus de noeud frere. On définie la fonction Parent(.) qui retourne le noeud parent, et qui retourne NIL si il n'y a pas de parent. La racine n'a pas de parent. On définie la fonction Fils(.) qui retourne le premier noeud fils, et qui retourne NIL si il n'y a pas de noeud fils. On définie une fonction Flag(.) qui retourne 1 si le noeud à déja été parcouru, 0 sinon. Cette fonction est utille en cas de graphe et ne fonctionne qu'avec sa fonction miroire PutFlag(.,0) ou PutFlag(.,1) qui affecte le flag en question. On définie la fonction profondeur, p, qui calcul la profondeur d'un noeud. Le meta langage est donc {X, Y, Z, r0, Frere(.), Parent(.), Fils(.)}auquel on ajoute les fonctions numériques suivantes {Flag(.), PutFlag(.,0), PutFlag(.,1), p(.)}
On programme une fonction successeur, S(.), qui calcul le noeud suivant selon l'ordre canonique, et retourne NIL lorsqu'il n'y a plus de successeur. La fonction successeur va se programmer toute seule comme suit, en transcrivant pas à pas toutes les opérations qui doivent être faite :
S(X) : Si Fils(X) = NIL ou Flag(Fils(X)) = 1 Alors
Si
Frere(X) = NIL ou Flag(Frere(X)) = 1 Alors
X
= Parent(X)
Si
X = NIL Alors retourne NIL
Sinon
Si Frere(X) = NIL ou Flag(Frere(X)) = 1 Alors
X = Parent(X)
Si X = NIL Alors retourne NIL
Sinon
Si Frere(X) = NIL ou Flag(Frere(X)) = 1 Alors
.....
Sinon retourne Frere(X)
Sinon retourne Frere(X)
Sinon
retourne Frere(X)
Sinon retourne
Fils(X)
Puis nous pouvons remplacer l'elipse "..." qui reste une source d'ambiguité, par une boucle Répéter :
S(X) : Si Fils(X) = NIL ou Flag(Fils(X)) = 1 Alors
Répéter
Si
Frere(X) = NIL ou Flag(Frere(X)) = 1 Alors
X
= Parent(X)
Si
X = NIL Alors retourne NIL
Sinon
retourne Frere(X)
Fin_Répéter
Sinon retourne
Fils(X)
On n'oublira pas de marquer chaque noeud X analysé en affectuant un PutFlag(X,1), ceci pour ne pas repasser une deuxième fois par celui-ci.
On programme une fonction successeur exterieur, Sext(.), qui calcul le noeud suivant en dehors du sous-arbre, et retourne NIL lorsqu'il n'y a plus de tel successeur. Cette fonction est utile lorsque l'on unifie un sous-arbre et qu'il faut passer à l'étape suivante.
Sext(X) : Répéter
Si
Frere(X) = NIL ou Flag(Frere(X)) = 1 Alors
X
= Parent(X)
Si
X = NIL Alors retourne NIL
Sinon
retourne Frere(X)
Fin_Répéter
On remarque alors que Sext(.) est un sous programme de S(.) :
S(X) : Si Fils(X) = NIL ou Flag(Fils(X)) = 1 Alors retourne Sext(X)
Sinon retourne Fils(X)
On programme une fonction successeur, S2(.,.), qui calcul le couple de noeud suivant tel que le premier noeud soit toujours avant le second noeud selon l'ordre canonique :
S2(X,Y) : Si S(X) = Y Alors
Si S(Y) = NIL Alors retourne NIL
Sinon
retourne S(0, S(Y))
Sinon retourne (S(X),Y)
On programme une fonction successeur exterieur, S2ext, qui calcul le couple de noeud tel que le premier noeud soit en dehors du sous-arbre comme suit :
S2ext(X,Y) : Si Sext(X)=Y Alors
Si S(Y) = NIL Alors retourne NIL
Sinon retourne (0, S(Y))
Sinon retourne (Sext(X),Y)
On définie la fonction Val(.) qui retourne l'opérateur du noeud. On définie une fonction Flag2(.,.) binaires qui retourne 1 si le couple de noeud à permutation pret, à déja été annalysé, 0 sinon. Cette fonction est utille en cas de graphe et ne fonctionne qu'avec sa fonction miroire PutFlag2(.,.,0) ou PutFlag2(.,.,1) qui affecte le flag en question. On programme une fonction unification, u(.,.), qui calcule si les deux noeuds sont unifiables, et retourne 1 le cas échéant, 0 sinon :
u(X,Y) : Si Val(X) = Val(Y) Alors
PutFlag2(X,Y,1)
X=Fils(X)
Y=Fils(Y)
Si
X= NIL et Y=NIL Alors retourne 1
Si
X= NIL ou Y=NIL Alors retourne 0
Si
Flag2(X,Y) = 1 Alors retourne 1
Si
u(X,Y) = 0 Alors retourne 0
X=Frere(X)
Y=Frere(Y)
Si
X= NIL et Y=NIL Alors retourne 1
Si
X= NIL ou Y=NIL Alors retourne 0
Si
Flag2(X,Y) = 1 Alors retourne 1
Si
u(X,Y) = 0 Alors retourne 0
X=Frere(X)
Y=Frere(Y)
Si
X= NIL et Y=NIL Alors retourne 1
Si
X= NIL ou Y=NIL Alors retourne 0
Si
Flag2(X,Y) = 1 Alors retourne 1
Si
u(X,Y) = 0 Alors retourne 0
X=Frere(X)
Y=Frere(Y)
....
Sinon
retourne 0
Puis nous pouvons remplacer l'elipse "..." qui reste une source d'ambiguité, par une boucle Répéter :
u(X,Y) : Si Val(X) = Val(Y) Alors
PutFlag2(X,Y,1)
X=Fils(X)
Y=Fils(Y)
Répéter
Si
X= NIL et Y=NIL Alors retourne 1
Si
X= NIL ou Y=NIL Alors retourne 0
Si Flag2(X,Y) = 1 Alors retourne 1
Si
u(X,Y)=0 Alors retourne 0
X=Frere(X)
Y=Frere(Y)
Fin_Répéter
Sinon
retourne 0
On définie une procédure AffecterLien(X,Y) agissant sur deux noeuds X et Y et qui va modifier physiquement le noeud X en un lien de terme vers le noeud Y.
L'algorithme de factorisation est le suivant, et utilise un sous programe A(.,.) :
Si S(0) = NIL Alors Fin
Sinon A(0,S(0))
A(X,Y) : Si u(X,Y) Alors
Si
p(Y) > p(X) Alors AffecterLien(Y,X)
Sinon
AffecterLien(X,Y)
Si
S2ext(X,Y) = NIL Alors Fin.
Sinon
A(S2ext(X,Y))
Sinon
Si S2(X,Y) = NIL Alors Fin
Sinon
A(S2(X,Y))
10) La logique cachée du message
La factorisation précédente qui consiste à partager les sous-termes identiques, apporte une information intrinsèque supplémentaire au message, une connaissance sur soi, qui est utilisé ici pour réduire la taille du message. Mais une autre utilité de cette connaissances peut être faite, comme celle d'une redondance pour vérifier l'integrité du message et le corriger au cas où cette intégrité est atteinte suite à une modification non voulue du message.
Dans l'approche mathématique, cette connaissance est transcrite dans une formule qu'il faut évaluer pour obtenir le message originale. Comme on ne s'intéresse pas à la redondance pour l'instant, on privilègie les formules de petites tailles relativement à la taille du message original.
Cette information sur soi, sur le message lui-même, peut être d'avantage développée. L'étape suivante consiste à trouver non pas de simple sous-termes identiques, mais des models de sous-termes identiques avec paramètres, c'est à dire de nouveaux opérateurs.
Dans notre approche constructive, nous ne pouvons pas utiliser P(N), l'ensemble des sous-ensembles de N, puisque non dénombrable. Nous devons définir une restriction constructive de P(N). L'idée est trés simple. Nous nous intéressons qu'aux ensembles constructibles c'est à dire tel qu'il existe un procédé qui les énumère ou qui les semi-décide. Le procédé en question est une machine de Turing qui se ramène à un ensemble finie de règles de transitions d'automate. L'ensemble des Machine de Turing est énumérable, et donc l'ensemble des sous-ensembles semi-décidable de N est énumérable. On le note R(N).
Deux idées idée viennent à l'esprit, soit on ne retient que les sous-ensembles énumérables de N que l'on note R(N), soit on est encore plus exigeant et on ne retient que les ensembles décidables c'est à dire énumérable et dont le complémentaire est également énumérable, noté Décidable(N).
Il existe une surjection entre l'ensemble des machines de Turing et l'ensemble des sous-ensembles énumérables de N, noté R(N) qui associe à chaque machine de Turing, l'ensemble qu'elle semi-énumère. Le procédé de minimalisation permet de transformer une semi-énumération en une énumération, c'est à dire de transformer une machine de Turing calculable en une machine de Turing totalement calculable, en restreignant son ensemble de départ aux seuls éléments totalement calculables.
L'ensemble des machines de Turing est énumérable donc l'ensemble R(N) est énumérable.
Il est d'avantage pertinent d'utiliser le concept d'ensemble semi-décidable plutôt que d'ensemble tout court, de définir l'objet mathématique selon sa constructivité plutôt que selon le respect de règles propositionnelles qui, elles, ne peuvent pas toujours être vérifiées par un procédé constructif. Ainsi notre définition d'ensemble semi-décidable ou décidable se rattache au principe constructif et non au principe propositionnel.
2) Les structures constructives
Le fondement des mathématiques constructives est l'informatique. Mais au lieu de travailler avec une machine de Turing, nous allons travailler avec des structures constructives, c'est à dire où chaque opérateur correspond à un algorithme. Nous distinguons deux types de structures, les structures concrètes dans lesquels les générateurs sont exhibés, et les structures abstraites dans lesquels on ne connaît pas les générateurs, et que l'on utilise seulement par le biais de morphisme c'est à dire comme des catégories. En faite, il n'y a pas de différence et l'on pourra utiliser toute structure pour définire une catégorie de structure.
Dans cet esprit, la plus simple structure contenant les entiers est celle des entiers de Péano. Sa présentation comprend un élément a générateur, une fonction s unaire, et aucune condition. Une structure sans aucune condition est dite libre. Intuitivement, a est l'élément origine, l'entier zéro, et s est la fonction incrémentation :
< a , s >
L'aspect concret de la structure est son espace de Skolem ou son univers de Herbrand, c'est à dire l'ensemble de tous ce que le langage de la structure permet d'exprimer : {a, s(a), s(s(a)), s(s(s(a))),...}. L'opérateur s correspond à l'algorithme qui ajoute un. s(a) représente l'entier 1, et s(s(a)) représente l'entier 2, et ainsi de suite.
"Algèbre et théorie des nombres, Cryptographie - Primalité"
Prof Sabah AL FAKIR, Université de Lille, Edition Ellipses, 2003
4) Les structures abstraites ou catégories
La première opération binaire qui vient à l'esprit est la composition d'application notée °. La composition d'application est une opération associative qui admet comme élément neutre l'application identique notée id. On s'intéresse à la structure abstraite (M,°) / {° associatif, id est l'élément neutre}que l'on appelle la catégorie des monoïdes. Elle est abstraite car il n'y a pas d'espace de Skolem, l'ensemble sous-jacent M n'y est pas décrit, c'est une inconnue qui peut prendre toute forme à volonté. C'est une catégorie car on ne s'intéresse à cette structure que par le biais des morphismes.
5) L'emboîtement des structures
Au lieu d'emboîter les propositions comme le fait le langage Prolog (langage déclaratif de résolution de propositions logiques skolémisées du premier ordre), nous emboitons les structures. C'est à dire que nous effectuons un lien à un niveau plus élevé. Les structures se présentent alors comme des croisements composés d'entrés associés à des sorties. Une entré est caractérisé par une liste minimale d'opérateurs d'arités diverses et une liste minimale de propositions relatives à ces opérateurs qui constituent un jeu d'axiomes de la structure traduit dans un langage ne comprenant que ces seuls opérateurs d'entrés. Une sortie se présente de même, mais avec un jeu d'opérateurs beaucoup plus conséquents, maximisé, et un jeu de propositions relatives à ces opérateurs beaucoup plus importants, maximisé. La structure, quant à elle, va transmettre aux opérateurs de sortie, une implémentation que sont ses algorithmes appliqués sur les opérateurs d'entrés. Ainsi une structure qui possède 3 entrés pour une sortie, propose 3 implémentations différentes de cette sortie, faisant référence à des jeux d'opérateurs d'entrés différents.
Une tel entré avec sa sortie dévoile un morceau de structure, ou plus exactement un éclairage particulier de la structure. Ce mécanisme peut-il systématiquement se quantifier en structures bien délimitées et indépendantes les unes des autres, constituant ainsi de vrai carrefour ?. Nous recherchons la subdivision la plus fine possible. L'échec de cette subdivision dévoile l'existence de structures géantes indivisibles qui sont d'autant moins opportunes qu'elles sont grandes. En effet, nous avons besoin de petites structures et non de grandes structures car notre capacité d'analyse est limitée.
6) de la structure à l'algorithme
Une opération qui vient en premier à l'esprit est celle qui consiste à remplacer le codage des entiers en bâtons, exemple ||||| qui correspond à l'entier 5 et qui se note s(s(s(s(s(a))))) dans la structure de Péano, en le codage des entiers en binaire, dans l'exemple 101.
Il manque une étape essentielle. La seule opération définie par la structure des entiers de Péano <a, s> est l'opération d'incrémentation s. Rien n'est précisé en matière de mise en mémoire. Nous allons formaliser cette mise en mémoire sous forme d'une opération qui jusqu'a présent était implicite dans les démonstrations, pour la réintroduire dans la structure.
Nous connaissons la méthode informatique qu'est l'adressage indirect, qui s'exprime mathématiquement par la suite de variable indicée X0,X1,X2...,Xn. Nous formalisons cette mise en mémoire non borné. A chaque entier n de Peano, on associe une variable Xn pouvant contenir un autre entier de Péano.
Cela consiste à ajouter au langage, une variable existentiel X(.) d'arité 1, et d'ajouter l'opération binaire =.
D'un point de vue pratique on considére des briques de 32 bits, des cellules selon deux modes, un mode 0 ayant une taille inférieur à 2^16 briques, et un mode 1 ayant une taille comprise entre 2^16 et 2^32 briques. Dans le mode 0, la première brique de la cellule contient le type dans un octet, la taille dans deux octets, et les flags dans un octet (le flag de pointeur, le flag de passage et le flag d'occupation). Dans le mode 1, la première brique de la cellule contient le type dans un octet, les flags dans un octet (le flag de pointeur, le flag de passage et le flag d'occupation) et la taille est contenue dans la seconde brique.
Les contraintes algorithmiques nous amènent à concevoir des briques de taille B = 2b bits, c'est à dire de 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024.... bits. Et un pointeur devra être mémorisable dans une brique.
Si nous privilègions l'interopérabilité donnée-pointeur, la taille de la données contenue dans une briques devra être égale à la taille d'un pointeur afin de pouvoir convertir le pointeur en une donnée et vis-versa sans perte d'information. On réserve alors dans la brique un bit particulier appelé flag de pointeur. Le bit est à 0 si la brique contient une donnée et il est à 1 si la brique contient un pointeur. Mais si on estime au contraire que les données sont des symbôles en nombre limités, alors au lieu de réserver un bit dans chaque brique, on réserve l'usage des dernières adresses pour désigner ces données.
Un pointeur peut pointer un autre pointeur qui peut pointer encore un autre pointeur et ainsi de suite. Et le processus n'a pas forcement de fin, il peut boucler. Pour déterminer si l'on est déja passé par ce pointeur ou si l'on a déjà consulté cette données, et afin de détecter les boucles et les partages, nous utilisons un autre bit réservé pour cette seul fonctionalité qu'est le flag de passage.
D'autre bits peuvent être réservés pour d'autre fonctions. On réserve ainsi r bits dans chaque brique pour des fonctionnalités spécifiques (flag de pointeur, flag de passage, etc...). Dés lors les adresses (les pointeurs) doivent tenir sur un nombre de bits égal à B-r, et la mémoire doit être composée de 2(B-r) briques moins les éventuelles dernières adresses réservées pour désigner des symboles. Si on néglige ces dernières adresses, pour que toutes les données du pointeur soient utilisées, le nombre de briques doit être égale à 2n = 2(B - r). Nous avons :
n = B - r
n : Nombre de bits pour mémoriser une adresse.
r : Nombre de bits réservés.
B = 2b : Nombre de bits d'une brique. Appartient à {2, 4, 8, 16, 32, 64, 128, 256, 512, 1024....}
2n : Nombre de briques.
Ces systèmes sont caractérisés par le paramètre B qui est une puissance de 2, complété par un paramètre entier r librement choisie entre 0 et 2b.
Taille des
briques Nombre de
bits réservés Nombre
de briques B r 2(B-r) 2 0 4 4 0 16 1 8 2 4 8 0 256 1 128 2 64 16 0 ~ 65 000 1 ~ 16 000 2 ~ 8 000 3 ~ 4 000 4 ~ 2 000 32 0 ~ 4 000 000 000 1 ~ 2 000 000 000 2 ~ 1 000 000 000 3 ~ 500 000 000 4 ~ 250 000 000
Puis on considère plusieurs systèmes de mémoire, un par taille de brique différente.
L'arité d'un système de mémoire est le nombre de pointeurs qu'il est possible de mémoriser dans une de ses briques.
On choisie un petit ensemble de types d'arité (de cardinalité égale à une puissance de 2 afin que les types d'arité soit dénombrés par les valeurs possibles contenue dans un nombre entier de bits) et on gère autant de systèmes de mémoire qu'il y a de types d'arité distincts.
Un pointeur est une adresse globale composée d'un type d'arité et d'une adresse spécifique (ou dite relative) au système de mémoire correspondant au type d'arité en question.
On s'intéresse donc au système de mémoire dont les briques contiennent plusieurs pointeurs. On considère les cas où la brique contient exactement k pointeurs, plus a bits réservés par pointeurs pour désigner le type d'arité de l'objet pointé, plus r bits réservés par brique pour d'autre fonctionnalitées. L'arité est spécifiée dans ces a bits et fait partie de l'adresse globale. Par exemple pour a=2, on peut considérer les 2a arités distinctes (0,1,5,10) qui seront spécifier par les a bits réservés qui pourront ici être égale à 0, 1, 2, 3, et qui correspondront à 4 système de mémoire.
Soit k l'arité du système de mémoire, c'est à dire le nombre de pointeurs par brique. Soit n le nombre de bits d'un pointeur (adresse relative à un système de mémoire). Soit a le nombres de bits par pointeur réservés pour désigner le système de mémoire. Il y a 2a systèmes de mémoires, un pour chaque type d'arité distincte, possèdant chacun un même nombre de briques. Soit r le nombres de bits par brique réservés pour d'autres fonctionnalités. Soit B = 2b le nombre de bits d'une brique. Pour que toutes les données du pointeur soient utilisées, le nombre de briques d'un système de mémoire doit être égale à 2n. Et la taille d'une brique dans un système de mémoire caractérisé par les premiers paramètres k, n, a, r, b, doit respecter l'égalité suivante :
k*(n+a) + r = 2b
k : Arité du système de mémoire. Nombre de pointeurs (adresses globales) par brique.
a : Nombre de bits réservés pour déterminer l'arité de l'objet pointé.
r : Nombre de bits réservés par brique pour d'autres fonctionnalités..
n : Nombre de bits pour mémoriser une adresse relative.
n + a : Nombre de bits pour mémoriser une adresse globale.
2n : Nombre de briques dans un système de mémoire.
B = 2b : Nombre de bits d'une brique. Appartient à {2, 4, 8, 16, 32, 64, 128, 256, 512, 1024....}
2a : Nombre de systèmes de mémoire. Nombre de type d'arités distinctes
En conséquence r est choisie tel que 2b - r soit un multiple de k. Nous avons :
n + a = (2b - r)/k
Les systèmes sont caractérisés par les deux valeurs entières k, b puis par certaines valeurs de r autorisées. Le tableau suivant donne le nombre de bits des adresses globales pour les premiers systèmes de mémoires en explorant les valeurs de r comprises entre 0 et 4 inclus.
k Liste des premiers systèmes optimums avec r∈{0,1,2,3,4} 1 b 0 1 2 3 4 5 n+a 1 2 4 8 16 32 2 b 1 2 2 3 3 3 4 4 4 5 5 5 6 6 6 r 0 0 2 0 2 4 0 2 4 0 2 4 0 2 4 n+a 1 2 1 4 3 2 8 7 6 16 15 14 32 31 30 3 b 2 3 4 4 5 6 6 7 r 1 2 1 4 2 1 4 2 n+a 1 2 5 4 10 21 20 42 4 b 2 3 3 4 4 5 5 6 6 7 7 r 0 0 4 0 4 0 4 0 4 0 4 n+a 1 2 1 4 3 8 7 16 15 32 31 5 b 3 4 5 6 7 8 r 3 1 2 4 3 1 n+a 1 3 6 12 25 51 6 b 3 4 5 6 7 8 r 2 4 2 4 2 4 n+a 1 2 5 10 21 42 7 b 3 4 5 6 7 8 r 1 2 4 1 2 4 n+a 1 2 4 9 18 36 8 b 3 4 5 6 7 8 r 0 0 0 0 0 0 n+a 1 2 4 8 16 32 9 b 6 7 8 12 r 1 2 4 1 n+a 7 14 28 455 10 b 5 6 9 r 2 4 2 n+a 3 6 51 11 b 8 10 r 3 1 n+a 23 93 12 b 4 6 8 10 r 4 4 4 4 n+a 1 5 21 83 13 b 4 12 r 3 1 n+a 1 315 14 b 4 5 7 8 10 r 2 4 2 4 2 n+a 1 2 9 18 73 15 b 4 5 6 8 9 r 1 2 4 1 2 n+a 1 2 4 17 34 16 b 4 5 6 7 8 9 r 0 0 0 0 0 0 n+a 1 2 4 8 16 32 17 b 8 9 10 r 1 2 4 n+a 15 30 60 18 b 7 8 13 r 2 4 2 n+a 7 14 455 19 b 13 r 3 n+a 431 20 b 6 10 r 4 4 n+a 3 51 21 b 6 7 8 12 r 1 2 4 1 n+a 3 6 12 195 22 b 11 r 2 n+a 93 23 b 8 11 r 3 1 n+a 11 89
Les différentes conditions d'optimalité que nous avons finaliser nous dévoile une liste de systèmes denses optimums d'un point de vue mésentropique. C'est systèmes vont jouer un rôle dans la recherche d'algorithmes, et se comporte comme des embryons d'algorithme.