Brevet FR2559286A1 — publié le 19850809

Machine de traitement de l1information,pour l'interprétation de langages de programmation iogique. L'invention concerne des machines de traitement de l'infor- mation, en particulier pour l'intelligence artificielle. Les machines informatiques traditionnelles sont conques pour travailler avec Les langages de programmation å caractère impératif, basés sur la notion de flu : d'instructions qui modifient explicitement des mémoires On salit que ces langages se prêtent mal à l'expression de traitements formels, dont le besoin est de plus en plus ressenti dans les applications de l'informatique : systèmes experts, conceptiona assistées, analyse et compréhension des langues naturelles et artificielles, notamment. Pour de telles applications, des langages de traitement formel ont été développés. Ces derniers se subdivisent en langages de type fonctionnel tels que LISP, basé sur le forma lisme du lambda-calcul, et en langages de type relationnel, basés sur le formalisme@de la logique des prédicats. L'un de ceux-ci est le langage PROLOG, abréviation de programmation logique. Ce langage-est décrit dans de nombreux articles et ouvrages, notamment -"A machine - oriented logic based on the resolution principale "J.A. Robinson, Journal of the ACM, Vol. 12, No 1, janvier 1965; -"Les grammaires de métamorphose",A.Colmerauer, Groupe d'intelligence Artificielle, Marseille Lumigny, Novembre 1975; -"PROLOG II",Manuel d'utilisation, M. va Caneghen, Groupe d'intelligence Artificielle, Marseille Lumigny, Janvier 1982; -"Predicate Logic as Programming Language'.'R.A. Kowalski, IFP North Holland, 1974, pp. 569 à 574. Les langages de programmation logique, telsPROLOG, ont été jusqu'à présent expérimentés sous une forme purement logicielle, dans laquelle un programme spécial est implanté dans une machine de traitement de l'information de type traditionnel. Sans relever ici les problèmes et imperfections apparus lors de ces expérimentations, il convient de noter qu'une telle mise en oeuvre purement logicielle est peu efficace, au sens du rendement et de la vitesse de travail. La présente invention a essentiellement pour objet d'aboutir au développement industriel d'une machine spécialisée, capable de supporter efficacement la mise en oeuvre, par une programmation plus simple, des langages de programmation logique. L'un des buts de l'invention est de dégager une structure de mémoire, ainsi qu'un processeur d'exécution, munie d'un jeu de commandes pour la faire évoluer, l'ensemble présentant un intérêt général pour la rédaction d'interpréteurs de langages de programmation logique. Ceux-ci seront contenus dans un organe programmable du processeur d'exécution. Il ne s'agit pas, cependant, de définir un logiciel qui réalise rait directement l'interprétation d'un langage de programmation logique particulier (dont PROLOG est un exemple). Il convient de noter que, dans le présent texte, ce qu'on appelle "l'utilisateur" n'est pas directement un utilisateur humain, mais un programme particulier destiné à se dérouler dans l'organe programmable, et qui émettra des commandes appartenant au jeu de commandes précité. Un autre but important de l'invention est de fournir, dans une telle machine, un mécanisme permanent, automatique et optimal de récupération de tout élément de mémoire qui ne participe pas à la représentation de l'information accessible à l'uti- lisateur. De manière connue, la machine de traitement de l'information proposée comprend des moyens de traitement et des moyens de mémoire vive interconnectée par un bus. Selon un premier aspect général de l'invention, cette machine est remarquable : - en ce que les moyens de mémoire vive comprennent une mémoire formant pile de géniteurs, ordonnée en fonction d'un nombre entier ou niveau, et une mémoire de désignation, constituée de cellules adressables individuellement, à deux champs au moins chacune, chaque champ étant destiné à contenir une information qui est soit un atome ou donnée, soit une référence à une autre cellule, soit une référence à l'un des géniteurs, - un géniteur constituant le point de départ d'un treillis de termes, en contenant lui-meme l'une au moins desdites informations, le treillis de termes pouvant se prolonger par des références successives entre cellules de la mémoire de dés i- gnation, - les cellules ainsi référencées étant soit de type constructeur, leurs champs contenant alors immédiatement chacun l'une desdites informations, soit de type variable, étant mises en attente d'une liaison ultérieure, lors de laquelle les deux champs d'une cellule serviront l'un à associer la variable à l'un des géniteurs, et l'autre à contenir l'une desdites informations, et - en ce que les moyens de traitement comprennent un processeur d'exécution microprogrammé, susceptible d'être associé directement ou indirectement à un organe programmable destiné à recevoir le logiciel d'interprétation, ce processeur d'exécution comprenant en outre un registre de géniteur courant, qui fait référence à l'un des géniteurs de la mémoire formant pile, l'état courant de la machine étant ainsi défini par le contenu de ce registre ainsi que par le contenu de la mémoire de désignation et de la mémoire formant pile de géniteurs. Une définition plus détaillée du jeu de commandes de base suivant lequel le processeur d'exécution est microprogrammé sera donnée plus loin. Il sera également indiqué plus loin comment peuvent être structurées d'une part la mémoire de désignation, d'autre part la mémoire formant pile de géniteurs Un avantage de l'invention réside en ce que ces deux parties des moyens de mémoire vive peuvent être construites à partir de cellules de taille identique, comprenant dans un exemple préférentiel deux parties de vingt-quatre bits chacune, séparables chacune à leur tour en un champ de quatre bits et un champ de vingt bits. Selon un autre aspect de l'invention, les moyens de traitement sont aussi agencés pour d'une part répondre à des demandes d'allocation de cellules de mémoire, en allouant des cellules de mémoire disponibles et, d'autre part, répondre à une deman de spécifique en effectuant une récupération automatique des cellules contenant des informations devenues inutiles. En pratique, ceci peut être réalisé à laide d'un processeur de gestion de mémoire séparé qui dialogue par requêtes avec le processeur d'exécution à travers un organe de communication et de synchronisation. Pour son fonctionnement, il est utile que le processeur de gestion de mémoire comprenne un certain nombre de registres affectés en permanence à des tâches particulières. Ces registres seront indiqués plus loin. Il est encore souhaitable de prévoir un mécanisme de verrou entre les deux processeurs, ce qui leur permet une exclusion mutuelle pour l'accès aux moyens de mémoire qu'ils partagent. Selon un autre aspect de liinvention, le processeur de ges tion de mémoire, (séparé ou non),efectue la recupération auto mastique de la manière suivante - exploration d'une partie au moins des treillis de cellules définis par le contenu des moyens de mémoire vive, et utiles par le processeur d'exécution3 en y marquant les cellules en fonction de conditions prédé- terminées, et - ensuite, ramassage des cellules non marquées, qui sont maintenant considérées comme libres. Selon un autre aspect particulièrement intéressant de l'invention, une mémoire de statuts d'allocation est associée au processeur de gestion de mémoire. Cette mémoire de statuts d'allocation comprend un nombre d'éléments au moins égal à celui des cellules de la mémoire de désignation, de préférence autant d'éléments qu'il y a de cellules en tout dans les moyens de mémoire vive. Chacun de ces éléments de la mémoire de statuts d'allocation est susceptible d'états différents comprenant l'état libre, et un état marqué au moins. De préférence, au lieu d'un état marqué, on prévoit un premier et un second état non libres, définissant respectivement l'affectation de la cellule correspondante des moyens de mémoire vive dans une première et une seconde fournée. Le processeur de gestion de mémoire effectue alors le marquage des cellules de la mémoire vive par une inscription dans l'élément correspondant de la mémoire de statuts d'allocation. Le ramassage peut alors consister simplement en une exploration complète de cette mémoire de statuts d'allocation, tout en faisant passer ces éléments non marqués à l'état libre. Dans la réalisation préférée où l'on opère par fournées, le processeur de gestion de mémoire effectue alternativement la récupération de mémoire sur les cellules de la première et de la seconde fournée. Le marquage consiste à inverser l'affectation de fournées des cellules, en inversant l'état non libre de l'élément associé dans la mémoire de statut d'allocation. Et le ramassage consiste alors à faire passer à l'état libre les éléments de la mémoire de statut d'allocation qui ont conservé la marque qu'elles avaient au début de cette fournée. D'autres caractéristiques et avantages de l'invention apparaitront à l'examen de la description détaillée ci-après, faite en référence aux dessins annexés, ainsi qu'à quatre annexes. Sur les dessins. annexés - la figure 1 est un schéma illustrant l'organisation générale de la machine; et - les figures 2 à 5 sont les organigrammes de mécanismes incorporés au processeur de gestion de mémoire. Sur les annexes de la description - l'annexe 1 constitue une spécification générale de la machine, comportant un certain nombre de définitions de base, la définition de l'état courant de la machine, ainsi que de son jeu de commandes de base, dans un exemple particulier - l'annexe 2 définit de manière détaillee le contenu de la mémoire des cellules, dans l'exemple où les mêmes cellules sont utilisées pour la mémoire de désignation et pour la mémoire formant pile de géniteurs, avec les conséquences qui en découlent pour la représentation de l'état de la machine; - l'annexe 3 illustre le fonctionnement du processeur d'exe- cution, et du jeu de commandes de base incorporé à celui-ci, à l'aide d'exemples ; et - l'annexe 4 illustre les synchronisations entre les deux processeurs, ainsI que le fonctionnement du processeur de gestion de mémoire, à l'aide d'exemples et de diagrammesO Les figures relevant des annexes sont asoucees comme figures 6 à 27, aux figures 1 à 5 associées à la présente description Le contenu de l'ensemble des documents annexes, y compris les dessins, est constitué pour l'essentiel d'informations dé caractère certain. A ce titre, il est incorporé à la présente description, pour contribuer avec cellesci à la définition de l'invention. Par ailleurs, il a été nécessaire d'utiliser, en particulier dans les annexes, des graphismes particuliers destinés à préserver la cohérence et la clarté des explications données, compte tenu de l'intervention d'un nombre important de"mots réservés" (ce qui s'entend également de groupes verbaux). Lorsque cela est nécessaire pour une bonne compréhension, les mots réservés sont écrits entre apostrophes ('), dans le reste de la description et dans les revendications. Il est maintenant fait référence à la figure 1. Celle-ci montre que la machine selon l'invention possède les dispositifs suivants -une mémoire des cellules 14, utilisée essentiellement pour la représentation des termes. Cette mémoire, de grande capacité, peut être construite à l'aide de circuits 4164 de la Société Intel Corp. Ce sont des mémoires à temps d'accès moyennement rapide, typiquement 150 nanosecondes. - un processeur d'exécution 10, qui réalise les instructions de base de la machine, à savoir la construction et l'accès aux termes conservés dans la mémoire des cellules. Il comporte un organe programmable, ou plus précisément microprogrammable, 16, qui permet de définir diverses utilisations de la machine, comme un interpréteur du langage PROLOG. Ce processeur peut être construit à l'aide des circuits de la famille 2900 de la société Advanced Micro Devices. Cette famille de circuits permet de constuire par tranches" des processeursmicroprogrammables dont la fréquence de l'horloge de base est motennement rapide, typiquement 150 nanosecondes. - un processeur de gestion de mémoire 12, qui réalise essentiellement le mécanisme de récupération de mémoire, et aussi l'allocation de cellules de mémoire libre sur requête du processeur d'exécution. Le processeur de gestion de mémoire fonctionne en parallèle avec le processeur d'exécution. Il peut également être construit à l'aide des circuits de la famille 2900 de Advanced Micro Ceïirns. - une mémoire des statuts d'allocation 15,- qui conserve l'information nécessaire au processeur de gestion de mémoire. Dans l'exemple détaillé décrit, cette mémoire comporte autant d'éléments que la mémoire de cellules. Mais les éléments de la mémoire des statuts d'allocation ont une largeur limitée à deux bits. Cette mémoire est construite en technologie rapide, par exemple à l'aide de boîtiers Am 9128-10 de la Société AMD (temps d'accès de l'ordre de 100 ns), - un bus mémoire 13 qui réalise et arbitre les accès concurrentiels à la mémoire des cellules de la part du processeur d'exécution et du processeur de gestion de mémoire e Le mécanisme d'arbitrage peut être classique, et réalisé à partir de circuits existant sur le marché, comme les circuits produits par la Société INTEL Corps pour la gestion de 1'arbi- trage de son bus MULTIBUS. Ur 3organe de communication et de synchronisation ou bus de rr-quetes lle qui assure entre les aeuat processeurs l'échange d'informations et la synchronisation macroscopique ayant trait à la gestion de mémoire. Cela se produit essentielle- ment par requête et acquittement de requête, ou mise en attend te de celle-ci. Le bus de requêtes ll peut consister en des liaisons entre les processeurs mentionnés plus haut, qui possèdent des moyens d'intercommunication entre processeurs. La mémoire des cellules 14 constitue les moyens de mémoire vive précitée. Elle pourrait être réalisée en deux parties physiquement séparées, éventuellement de structure différente, correspondant respectivement à la mémoire de désignation et à la mémoire formant pile de géniteurs, telles que définies plus haut. Il est préféré que cette mémoire de cellules comporte une structure unique, à partir de cellules élémentaires de taille identique, permettant aussi bien la réalisation de la mémoire de désignation que celle de la mémoire formant pile de géniteurs. Il sera indiqué plus loin comment ceci est réalisé. Dans ce cas, la mémoire des statuts d'allocation comporte des éléments qui correspondent non seulement à la mémoire de désignation, mais aussi à la mémoire formant pile de géniteurs.Une variante de l'invention consisterait à ne prévoir, dans cette mémoire des statuts d'allocation, que des éléments en nombre limité à celui des cellules de la mémoire de désignation. Il sera utile de se référer maintenant à l'Annexe 1, afin d'acquérir les notions de base et définitions utiles à la compréhension de l'invention. L'Annexe 1 précise aussi l'état de la machine, et les caractéristiques abstraites du jeu de commandes de base de son processeur d'exécution, avec là encore les définitions nécessaires. L'annexe 2 définit plus en détail la structure de la mémoire des cellules, d'abord pour la mémoire de désignation, puis pour la mémoire formant pile de géniteurs. S'y trouve également définie la notion de confJguration cohérente dans la mémoire de représentation. Cette notion de cohérence est ensuite étendue après intervention de la mémoire formant pile de géniteurs. Enfin est défini l'état de la machine, avec le registre d'affectation permanente que comporte le processeur d'exécution, la représentation de l'état de la machine par le contenu de ce registre, et par le contenu de la mémoire des cellules. Est alors brièvement notée la concordance entre la réalisation ainsi définie de la machine proposée et la spécification qui en est faite dans l'Annexe 1. L'agencement de la mémoire de cellules selon ce qui est proposé en Annexe 2 est considéré comme accessible à l'homme de l'art, sur la base des enseignements donnés. Il en est de meme pour le registre incorporé au processeur d'exécution. Le processeur d'exécution possède tout d'abord un mécanisme dé "traversée des liaisons". La réalisation de ce mécanisme est là encore considérée comme accessible à l'homme de l'art, sans qu'il soit nécessaire d'en donner une représentation algorithmique figurative. On note d'ailleurs qu'un tel mécanisme est réalisé sous forme logicielle dans les expérimen- tations d'interpréteùrs PROLOG qui ont été mentionnés plus haut. Le processeur d'exécution le réalise sous forme maté- rielle. Suivent alors les commandes également implantées sous forme matérielle, c'est-à-dire microprogrammées, dans le processeur d'exdeution. Le mécanisme de chacune de ces commandes est exposé dans l'Annexe 3 Il est, dans la plupart des cas, accompagné d'un exemple associé. Sur la base des enseignements donnés a propos de ces mécanismes dans l'Annexe 3,il est considéré comme accessible à l'homme de l'art de construire le processeur d'exécoution équipé d'un tel jeu de commandes de base, à partir des circuits inté- grés cités plus haut. Il est à noter que certaines de ces commandes sont appa- rentées à des instructions connues du langage LISP. Ainsi -'Construire'existe telle quelle dans LISP (CONS), -'accéder gauche' correspond à'CAR'de LISP, -'accéder droite'correspond à'CDR'de LISP, - les trois commandes de tests ont également leurs éoui- valents dans LISP, - il en est encore de meme pour l'instruction de 'comparaison'. Les autres commandes proposées n'ont pas leur équivalent dans LISP, elles sont particulièrement adaptées à l'interprétation des langages relationnels et sont un des traits originaux de la machine. Le fait que certaines commandes ici proposées aient pu être réalisées sous forme matérielle dans certaines machines, -"LISP Machine Progress Report", R. Greenblatt. memo 444AI, lab MIT Cambridge Mass, Aug. 1977 est à souligner. La réalisation des autres commandes, de type original, dont le mécanisme est exposé dans l'annexe 3, est microprogrammable de manière analogue. Ont été décrits pour le moment la structure de la mémoire des cellules 14 et celle du processeur d'exécution 10, leur interconnexion étant réalisée à travers le bus 13. Muni du jeu d'instructions de base qui vient d'être défini, le processeur d'exécution 10 est apte à permettre l'interprétation directe de la plupart des langages de programmation logique, sinon tous, et en particulier de celui connu sous le nom de PROLOG. Ceci constitue un premier avantage important desla présente invention. Il convient d'observer que la représentation concrète, dans la machine, du travail effectué par le processeur d'exécution comporte trois niveaux - un niveau d- qui s'intéresse uniquement au contenu de la mémoire de désignation. Voir à cet égard les définitions de 'd-terminal' ,- 'd-ultime' et 'd-représentation' dans l'annexe xe 2. - un second niveau noté t-. Ce niveau concerne les rapports entre les désignations contenues dans la mémoire de désigna tion et les rangs dans la pile (on se rappellera que toute variable liée contenue dans. la mémoire de désignation fait référence à un géniteur rangé dans la pile). A cela correspondent les définitions 't-terminal', 't-ultime' et 't-représentation' de l'Annexe 2. - Le troisième niveau, noté S-, intéresse le contenu de la mémoire-pile elle-meme. Il est explicité par les définitions 'S-ultime', 'S-correspondance' et'S-représentation' dans l'Annexe 2. Ceci permettra de mieux comprendre les enseignements donnés sur l'état courant de la machine, à la fin de l'Annexe 2. On s'attachera maintenant à une caractéristique essentielle de la présente invention, qui concerne la mise en oeuvre (o implementation) d'une récupération automatique, et opti - maie, des' éléments de mémoire qui contiennent des informations devenues inutiles au processeur d'exécution Le point de départ du mécanisme de récupération est l'instruction "réduire" déjà mentionnée. La plupart des concepteurs de langages de traitement formel ont prévu, généralement sous forme logicielle implémentée par le processeur d'exécution, une gestion de mémoire tendant à récupérer les parties de mémoire devenues inutiles. Ainsi, le langage LISP connait List processing in réal time on serial computer", H. Baker, communication of the ACM, April 1978, Vol. 21 Num 4 Pour ce qui est du langage PROLOG, différentes propositions ont été faites pour récupérer de la mémoire notamment "A note on garbage collection in PROLOG interpreters" Mr. Bruynoeghe, Proceedings of the first International logic programming conference, Sept. 14-t7th 1982, Marseille, France".Aucune de ces propositions n'a donné entière satisfaction, notamment aucune proposition de récupération,en parallèle de l'interprétation,n'a été faite. Le premier pas vers la solution selon l'invention consiste à prévoir un processeur séparé de gestion-de mémoire 12, qui dialogue par requêtes avec le processeur d'exécution, à travers l'organe de communication et de synchronisation schématisé en -il. Sauf en cas d:invalidation des requêtes, comme on le verra plus loin, le processeur de gestion de mémoire 12 répond à une requête d'allocation de cellule de mémoire formulée par le processeur d'exécufion en allouant chaque fois à ce dernier une cellule de mémoire déterminée. Le processeur d'exécution 10 va donc ainsi disposer, de façon pratiquement permanente, des cellules de mémoire dont il a besoin pour ses opérations. Pendant l'intervalle de temps qui-va s'écouler entre une opération "invalidation des requêtes" et l'opération ulté rieure "validation des requêtes", le processeur de gestion" de mémoire 12 va se trouver alors dans le "niveau requête" décrit aussitôt après le niveau de fond. Une requête émanant du processeur d'exécution 10 est alors différée, c'est-à dire qu'elle est mémorisée et qu'elle ne sera prise en compte que lorsque le processeur de gestion de mémoire repassera au niveau de fond. En bref, le niveau de fond consiste donc en l'exécution par le processeur de gestion de mémoire des opérations qui lui sont propres, et que l'on examinera plus loin. En présence d'une'requête',ou bien d'une'invalidation des requêtes pour une autre raison, le processeur de qestion de mémoire atinterrompt pour passer au niveau requête". En cette situation, toute nouvelle requête émanant du processeur d'exécution est différée. Pendant le traitement d'une requête, la fin de requête" ramène le processeur de gestion. de mémoire à son niveau de fond, où il continue les activités interrompues par la requête. Au contraire, l'opération de "forçage" fait repasser le processeur de gestion de mémoire à son niveau de fond, en abandonnant l'activité interrompue par la requete, au profit d'une activité indiquée par l'opération de forçage (voir Annexe 4, page 13). Il convient maintenant de retourner brièvement à la définie tion des instructions 'réduire' et ereprendret dans l'Annexe 3. Ces instructions provoquent une requête de "démarrer une fournée", adressée par le processeur d'exécution au processeur de gestion de mémoire, avec pour paramètre le contenudu registre géniteur courant, et trois noms zlR n2 n3, déterminés par le processeur d'exécution comme étant respectivement "ultime valeur11 des noms nn1' nn2' 3 initialement associés à l'instruction'réduire'. ou bien définir au cours de 1 t instruction 'reprendre', suivant le cas. C'est donc dans le mode de réalisation décrit l'une des instructions 'réduire' et 'reprendre' qui va provoquer les opérations de récupération automatiques de cellules par le processeur de gestion de mémoire 12. A cet effet, le processeur de gestion de mémoire 12 est associé à la mémoire des statuts d'allocations 15, dont la nature a déjà été exposée et se prouve précisée dans l X annexe 4. Le processeur de gestion de mémoire 12 contient en outre une série de registres également exposés dans la meme annexe Le processeur de gestion de mémoire 12 est microprogrammé selon deux mécanismes très simples, également explicités dans l'annexe 4 - décider si une cellule est marquée, - marquer une cellule. Schématiquement, la récupération automatique se déroule alors de la manière suivante - le processeur de gestion de mémoire 12 explore une partie au moins des treillis de termes définis par le contenu des moyens de mémoire vive, c'est-à-dire de la mémoire de cellules qui réunit ici la mémoire de désignation et la mémoirepile de géniteurs. Dans le cas présent, la partie concernée est définie par l'identification de la fournée en cours" et par les indications accompagnant la requete démarrer une fournée" telle que fournie par le processeur d'exécution. Comme on le verra plus loin, cette requête est accompagnée de quatre paramètres, consistant en la référence d'un géniteur et en trois noms. Lors de cette exploration, les cellules sont marquées en fonction de conditions prédéterminées que l'on explicitera en détail ci-après. Dans le mode de réalisation préféré, ce marquage consiste en une inversion de l'indication de fournée dans l'emplacement de la mémoire 15 des statuts d'allocations qui correspond à la cellule à marquer. Enfin est effectué un ramassage des cellules non marquées, qui vont donc maintenant etre considérées comme libres. Ce ramassage consiste ici à faire passer à l'état libre les éléments de la mémoire de statut d'allocation qui ont conservé la marque qu'elles avaient au début de cette fournée. Il est rappelé que, dans l'exemple préféré décrit, la mémoire de statuts d'allocations comporte, en correspondance bi-univoque, autant d'éléments qu'il y a de cellules dans les moyens de mémoire vive. En d'autres termes, pourront etre marquées non seulement les cellules de la mémoire de désignation, mais aussi celles de la pile de géniteurs. On va maintenant décrire en référence à l'Annexe 4, ainsi qu'aux figures 2 à 5, l'ensemble des conditions prédéterminées qui permettent une récupération très efficace des cellules de mémoire. Ces mécanismes sont décrits de manière formelle dans i'Annexe 4. Les figures 2 à 5 en donnent une représentation algorithmique correspondante. La description qui va être donnée maintenant se fonde en même temps sur les annexes et sur les figures 2 à 5, en cherchant à refléter les cheminements du pro cesseur de gestion de mémoire 12. Un autre aspect est à souligner. Jusqu'd présent, les mécanismes de récupération de mémoire connus se sont intéressés essentiellement aux cellules de type constructeurs, sans pouvoir résoudre correctement le cas des cellules variables, et encore moins celui de la pile de géniteurs.La présente invention offre l'avantage de poudre, d'une manière complète, le problème de la récupération destcellules de variables, lorsqu'elle est possible En plus, elle permet également d'effectuer des opérations de récupération dans la pile de géniteurs. La liste de registres du processeur de gestion de mémoire 12; telle que donnée dans l'annexe 46 tient compte de cette situation. En présence d'une requête 'démarrage-fournée2, le processeur d'exécution va (annexe 4, page 10) ç - inverser la marque, c'est-d-dire l'indication de fournée, contenue dans le registre "fournée courante", - ranger la référence du géniteur accompagnant la requête comme paramètre dans le registre géniteur sommet", - ranger le ou les "noms" (ici trois nomsr accompagnant la requête comme paramètre, dans le registre "nom:sous marquage", - ranger le niveau du nouveau géniteur sommet dans le registre "niveau sous marquage". Il est avantageux d'effectuer aussi la recherche immédiate du géniteur qui représente ce géniteur sommet, le mécanisme impliqué étant décrit plus loin. La suite est alors le mécanisme dit récupération (annexe 4, page 1), qui se décompose en trois phases successives, à savoir: marquage; ramassage; attente-fournée. La structure générale du mécanisme de marquage (annexe 4, page 2) est illustrée sur la figure 2. Elle fait appel à différents mécanismes auxiliaires, illustrés sur les figures 3, 3A, 3B, 3C et 4. Sur la figure 2, le mécanisme général de marquage commence à l'étape 200. La première étape active est un test 201 qui détermine si le niveau de marquage est supérieur ou égal à zéro. (Il est rappelé qu'en informatique, le niveau zéro a un sens actif.} Tant que le niveau de marquage n'est pas devenu négatif, ce qui indique que le marquage est terminé, l'étape 202 appelle le mécanisme de "marquage terme", que l'on décrira à propos de la figure 3. Ce marquage de terme est effectué avec le ou les noms, ici nom 1, nom 2, nom 3,que contient le registre de noms. Ensuite, l'étape 203 invalide les requêtes. L'étape 205 appelle le mécanisme de décrémentation du niveau de marquage qui sera décrit à propos de la figure 4. Après cela, l'étape 207 consiste à mettre "disjoint" dans le registre "situation exécution". Enfin, l'étape 209 produit une revalidation des requêtes, et l'on retourne immédiatement en amont du test 201. Ces opérations seront répétées jusqu'à ce qu'on arrive à un niveau négatif, indiquant la fin d'une phase complète de marquage. Lorsque cette condition est vérifiée,la sortie non du test 201 passe au mécanisme de ramassage 500, qui sera décrit à propos de la figure 5. Il est maintenant fait référence à la figure 3, pour la description du mécanisme 'marquage terme', qui possède pour paramètre un champ noté maintenant f, champ qui contient le nom n faisant l'objet du marquage de terme Un test 310 détermine tout d'abord de quel type est llinclica- teur du nom n. S'il s'agit d'un atome, on passe immédiatement à l'étape de fin 326. S'il s'agit d'un géniteur, on passe à une étape 370. Cette étape consiste en un mélanisme de normalisation de niveau sur le champ f, et sera décrite à propos de la figure 3C Après cette étape 370, on obtient à nouveau la fin à 12 étape 328. Enfin, si le test effectué en 310 indique que le nom n est une variable ou un constructeu un nouveau test 312 intervient. Ce test examine si la marque d'allocation de la cellule référencée par le champ information du nom n est marquée ou non marquée. Si elle est déjà marquée, on passe à la fin 326. Si elle n'est pas marquée, un troisième test 314 détermine maintenant quel est le type d1indicateur de n, entre les deux cas restant possibles, à savoir celui d'un constructeur c ou d'une variable v. S'il s'agit d'un constructeur c, l'étape 301 refait un marquage de terme avec les deux parties de ce constructeur notées 'gauche de c' et 'droite de c'. Après exécution complète de tous ces marquages, étape 322 consistera à marquer la cellule, ici un constructeur c, initialement examinée après quoi on passe à la fin 324. Si le test 314 a déterminé que l'on était en présence dU une variable v, l'étape 330 appelle le mécanisme de normalisation de liaison avec cette variable. Ce mécanisme est illustré à la figure 3A. Après cela, un test 318 détermine si, le -résultat de la normalisation qui aura été faite entre temps, sur la va:riable est ou non libre. Si oui, on retrouve étape 322. Sinon, on refait le marquage de terme avec la liaison de v, à l'étape 303, après quoi on retourne encore une fois pour terminer à l'étape 322. Le mécanisme marquage de terme 300 de la figure 3 comporte des bouclages sur lui-même. L'homme de l'art comprendra qu'une mémorisation estllnécessaire pour la bonne exécution de ce mécanisme La page 3 de l'annexe 4 décrit comment réaliser une telle mémorisation à l'aide d'une mémoire auxiliaire en pile. Par ailleurs, la rubrique 11 de la page 4 de l'annexe 4, en référence à la figure 21, explique comment, lorsque l'on rencontre une cellule déjà marquée, il n'est pas nécessaire de parcourir les cellules auxquelles elle donne accès dans le cadre du niveau sous marquage, car elles sont certainement déjà marquées. Il s'agit là d'un avantage important des mécanismes selon l'invention. Il est maintenant fait référence à la figure 3B, qui décrit un mécanisme de recherche du 'représentant' d'un géniteur g. Ce mécanisme est désigné dans son ensemble par 350. Il commence par une étape 351 consistant à prendre pour géniteur courant le géniteur g défini au départ. Ensuite, un test 353 détermine si la nature du géniteur courant est celle d'un géniteur coupé. S'il s'agit bien d'un géniteur coupé, l'étape 355 remplace le géniteur courant par celui désigné dans le champ 'précédent' du géniteur courant en vigueur jusqu'à présent, et on recommence le test 353. Lorsque la sortie du test 353 est non, c'est qu'il s'agit d'un géniteur actif. C'est alors la fin en L'étape 357, et le géniteur 'représentant' est le géniteur courant qui vient d'etre détermine. Ce mécanisme est décrit plus formellement à la page 6 de l'annexe 4. On pourra se référer à la figure 25. Le mécanisme de marquage de terme 300 faisait aussi appel, dans le cas d'une variable, à un mécanisme auxiliaire dit 'normalisation-liaison. Ce mécanisme auxiliaire 330 est illustré sur la figure 3A. Il commence par un test 332, déterminant Si le statut de la va tle v concerne est libre ou indécis. S'il est libre, l'étape 334 établit oue le résultat de la normalisation est 'LIBRE' et lior passe à la fin en 335. Si ce statut est indécis, un nouveau test 336 détermine la nature du géniteur de la variable v. Si ce géniteur est mort, on passe à l'étape 338, qui consiste à mettre le statut de la variable g à libre, après quoi l'étape 339 établit à 'LIBRE' le résultat de la normalisation, et l'on passe à la fin en 340. Le géniteur de la variable v étant coupé ou actif, l'étape 342 va rechercher le géniteur 'représentant', noté gr, du géniteur g considéré. Après que ce représentant a été trouvé par le mécanisme de la figure 3B, l'étape 344 consiste à mettre la référence de ce géniteur représentant gr dans le champ 'géniteur' de la variable v. Si oui, l'étape 346 établit que le résultat de la normalisa tion est 'LIBRE' et c'est la fin 347. Sinon l'étape 347 établit que le résultat de la normalisation est 'LIEE' et c'est la fin 349. Le mécanisme de la figure 3A est décrit de manière plus détaillée et plus formelle à alpage 5 de l'annexe 4, dont les explications font référence aux figures 23 et 24. La figure 23 illustre ce qui se passe pour un géniteur mort, c'est-à-dire lorsque la sortie du test 336 va directement sur l'étape 338. La figure 24 illustre le second cas de figure, dans l'hypothèse où la sortie du test 342 est non. Ce qui précède permet un nettoyage convenable de la mémoire pour tout ce qui concerne les cellules constructeur et variable. Il a été précédemment indiqué que l'invention prévoit aussi un tel nettoyage dans le cas des géniteurs. Il est par ailleurs nécessaire d'effectuer la normalisation de niveaux prévue à I'étape 370. Cette normalisation de niveaux concerne le champ f qui contient la référence au géniteur g. La première étape 372 est la recherche du géniteur 'représentant', noté gr, du géniteur g. Ce mécanisme est déjà décrit à propos de la figure 3B. Le géniteur représentant gr ainsi déterminé est alors mis dans le champ f, à la place du géniteur g qui s'y trouvait précédemment, ce à l'étape 373, après quoi on passe à l'étape de fin 375. Tout ce qui vient d'être décrit à propos des figures 3, 3A, 3B et 3C constitue des sous-mécanismes de l'étape 202 de la figure 2. Leur exécution est donc nécessairement suivie d'une décrémentation du niveau de marquage à l'étape 205. Ce mécanisme noté 400 dans son ensemble sera maintenant décrit à propos Ha la figure 4. L'homme de l'art pourra se référer aux pages 6 et 7 de l'annexe 4, ainsi qu'à la figure 22. La première étape 401 consiste à examiner si la nature du géniteur sommet est ou non 'coupée'. Si oui, l'étape 403 consiste en une mise à 'mort' de ce géniteur sommet. Le géniteur défini par son chars 1précédent' devient le nouveau géniteur sommet. fait retourne ensuite immédiatement en amont du test 401. Il est maintenant possible, aqprès les traitements décrits plus haut, de mettre z more le géniteur coupé De cette manière, on va rencontrer tôt ou tard un géniteur actif. La sortie non dn test 401 mène alors à l'étape 405. Cell-ci consiste @ mearquer la on les cellules occupées par le géniteur sommet. Après, l'étape 407 consiste à décrémenter le niveau de marquage d'une unité, dens le registre prévu à cet effet. Si le niveau de marquage n'est pas négatif, on continue. S'il est devenu négetil marquant la fin du marquage, c'est alors l'étape de fin 410 qui intervient. On sortira par l'étape de ramassage 500. Dans le cas contraire, l'étepe 411 vaq chager de géniteur sommet, tout en gardant la trace du géniteur sommet précédent En d'autres terme cette étape réserve tout d'abord le géniteur sommet en cours. Elle prend le géniteur défini par son champ 'précédent' et en fait le nouveau géniteur sommet. L'étape 413 détermine alors le géniteur gr qui va être le représentant' du souveau géniteur sowr' Ce mécanisme a déjà été décrit propos de la figure 33 Ensuite, l'étape @15 zange la rérférence de ce géniteur repré sentant gr dans le champ ' 1précédent1 du géniteur réservé, c'est-ä-dire du géniteur sommet qui était en vigueur jusqu'à l'étape 411. Ensuite, l'étape 417 consiste à prendre les trois noms qui sont contenus dans le géniteur gr, et à ranger ces noms dans les registres nom 1, nom 2, nom 3. On termine alors à l'étape de fin 420. Cette étape retourne à l'étape 207 de la figure 2. La figure 22 montre, sur un exemple, comment ce mécanisme 400 permet la réorganisation des géniteurs d'une strate. Le mécanisme de marquage est maintenant complètement décrit. Il est suivi du mécanisme de ramassage 500 illustré sur la figure 5. Ce mécanisme recombine deux éléments qui sont séparés dans l'annexe 4. L'un, le ramassage proprement dit, est décrit à la page 7 de l'annexe 4, tandis que l'autre, la 'révisionstatut-cellule' est décrit à la page il de l'annexe 4. Ce ramassage consiste en une exploration de l'ensemble des cellules de la mémoire des statuts d'allocation, avec un indice i qui va explorer toutes les adresses possibles danscette mémoire (de même que dans la mémoire de désignation). A l'étape 501, lFindice i est initialement mise zéro. Le test 503 détermine ensuite si i a atteint l'adresse maximale possible en mémoire. Si oui, c'est la fin en 504. Sinon, l'étape 505 réalise une invalidation, des requêtes. Le test 507 détermine alors si le-statut d'allocation de la cellule d'adresse i est la marque de la fournée précédente. Si oui, on met cette cellule à 'disponible', à l'étape 509. A ce niveau intervient un perfectionnement de l'invention, qui consiste à allouer immédiatement la cellule qui vient d'être libérée. Pour cela, le test 511 détermine s'il y a attente d'une allocation de cellule. Si oui, l'étape 513 alloue immédiatement la cellule qui vient d'être libérée et acquitte la requête correspondante. Dans tous les autres cas, y compris celui où la sortie du test 507 était non, on passe à l'étape 515, consistant à revalider les requêtes, et suivie d'une étape 517 incrémentant l'indice i d'une unité. On boucle alors sur l'étape 503, jusqu'à exploration de toutes les adresses de mémoire. Intervenant uniquement sur le contenu de la mémoire de statuts d'allocation, le mécanisme 500 se déroulera de façon tros rapide, puisqu'il s'agit d'une mémoire rapide dont chaque élément ne possède que deux bits. Après tout cela, le processeur de gestion de mémoire se place en situation d'attente de fournée, jusqu'à nouvelle exécution du mécanisme de récupération. On notera maintenant qu'avec ces deux bits par élément, la mémoire de statuts d'allocation 15 possède un quatrième état, non encore utilisé jusqu'à présent. Ce quatrième état peut servir à soustraire certaines cellules de la mémoire 14 à l'action de récupération du processeur de gestion de mémoire 12. Cela est utile notamment si l'on désire stocker des informations de programme du processeur d'exécution 10 dans cette mémoire. Dans la variante simplifiée où la récupération de cellules ne se fait que dans la partie mémoire de désignation de la mémoire 14, les cellules définissant la pile des géniteurs sont alors mises elles aussi dans ce quatrième état, de façon à échapper à la récupération et au nettoyage qui sont effectués périodiquement par le processeur de gestion de mémoire 12. Seul le processeur d'exécution 10 peut alors libérer ces cellules, sur une requête explicite à cet effet, qui s'adresse au processeur de gestion de mémoire 12. Dans ce-qui précède, le mécanisme de récupération de mémoire est mis en fonction par la commande 'réduire1. Il est avantageux,comme cela est décrit dans l'annexe 4, qu'il soit également initié par l'instruction 'reprendre'. A la fin de l'annexe 4 se trouve encore décrit le détail des synchronisations par requête intervenant dans le mode de réalisation à deux processeurs de la présente invention. De cette manière, avec un processeur d'exécution et un processeur de gestion de mémoire susoeptibles de fonctionner de manière totalement parallèle, on assure que la gestion de mémoire s'effectue non seulement de manière optimale, mais aussi de manière très rapide. Une variante de l'invention consisterait à utiliser un seul processeur qui fut spécialement microprogrammé, et ce processeur constituerait à lui seul les moyens de traitement de l'invention. Il n'y a bien sûr plus de problèmes d'intercommunication comme précédemment. En revanche, ce processeur microprogrammé unique devra fonctionner en temps partagé, d'une part pour l'exécution, d'autre part pour la gestion de mémoire. Le Demandeur estime qu'il conviendra alors d'implanter le logiciel d'interprétation (prolog ou autre) dans un processeur classique, séparé, qui sera connecté de manière habituelle au processeur unique microprogrammé constituant à lui seul les moyens de traitement. - ANNEXE 1 SPECIFICATION NOTION DE BASE: ESPACE DE TERMES Un triptet @TERMES. FEUILLES, CONSTRUCTEUSS@ est un ospace~de~iermes si I CONSTRUCTEURS est une partie finie de (TERMESXTERMBS) - TERMES I- FEUILLES C TERMES I V l1, d1, g2, d2 e TERMES V cons1.cons2 e CONSTRUCTEURS consl (g1,d1) = cons2(g2.d2) # (cons1=cons2 st g1=g2 et d1=d2) I Vte TERMES t# FEUILLES # @ g.d e TERMES @ CONS E constructeurs @=cons(g.d) Commentaire: Les TERMES sont des arbres binaires.Hs ont été préférés aux termes n-aires pour ieur @ustiché adaptée au degré de matérialtté de la mise-en-oeuvre projetée et pour leur souplesse. Ils ont le mme Qouvoir expressit que les termes n-aires et it peuvent servir de composants élémentaires pour une grande variété de structures, en particulier les listes de longueur variable. Leur morphologie homogène se prele bien m l'allocation dynamique d'un réservoir de cellules de mémoire toutes identiques et interchangeables. Il est prévu plusieurs constructeurs, en pratique un petit nombre. Grâce à eux, les applications disposent d'arguments de discrimination basés sur le type des termes construits, plutôt que sur un codage employant des feuilles réservées. On espère ainsi une plus grande efficacité. Si la définition donnée ici est tres générale et tolère en particulier les termes infinis, les contraintes d'utilisation énoncées au sein de la spécification limitent le domaine représentable dans la machine aux termes finis arborescents. NOTIONS DERIVEES: TERMESCONSTRUlTS, SOUS TERMES. REMPLACEMENT FVt t e TERMES~CONSTRUITS # f cons 6 Constructeurs F TG.LD E te%rmes t-cons(tg.td) F SOUS~TERMES E TERMES - parties de TERMES FVie TERMES (te FEUILLes et SOUS~ TERMES(t) = (l) ou J cons e CONSTRUCTEURS i tg.td E TERMES t=cons(tg.td) et SOUS~TERMES(t) = {tg} U {td} u SOUS TERMES[tg] u SOUS~ TERMES[td] @ REMPLACEMENT de ... par ... dans E (TERMESxTERMESxTERMES) - TERMES @ @ t1 t2, TERMES t=t1 # REMPLACEMENT de t1 par t2 dans t = t et (#t1 et t # FEUILLES) # REMPLACEMENT de t1 par t2 dans t = t et (# t1 et t # FEUILLES) # @ cons e CONSTRUCTEURS @ ig.id e TERMES T=cons(tg.td) et REMPLACEMENT de il par t2 dans t = cons(REMPLACEMENT de tl par t2 dans tg REMPLACEMENT de tl par t2 dans td) Commentaire:: Les TERMES~CONSTRUITS et les FEUILLES sont des ensembles disjoints et dont la réunion constitue les termes SOUS~TERMES donne l'ensemble des sous-termes d'un terme. non compris lut-même. REMPLACEMENT remplace toute occurence d'un terme par un autre terme au sein d'un certain terme. NOTION DE BASE: ESPACE DE LISTES Un quintuplet LISTES, ELEMENTS, EN~LISTE, LISTE~VIDE, TAILLE~LISTE# est un espace~de~listes si I- EN~LISTE E (ELEMENTSXLISTES)#LISTES # LISTE~VIDE E LISTES 1-# e1.e2 e ELEMENTS #17.12 e LISTES EN~LISTE(e1.17) = EN~LISTE(e2.17) # [e1=e2 et 11=12) 1-#1 e LISTES 1#LISTE~VIDE # #e1 e ELEMENTS # 17 e LISTES 1 = eN+LISTE (e1.17) # TAILLE~LISTE e LISTES - entiers # tAILLE~LISTE)LISTE~VIDE) = O # Ve e ELEMENTS VI E LISTES TAILLE~LISTE(EN-LISTE(e.1)) = TAILLE~LISTE(1) + 1 I E LISTES + n E entiers TAILLE~LISTE(I) = n Commentaire: Une LISTE est une collection ordonnée d'éléments. La fonction EN LISTE rajoute un élément en tète. TAILLE~LISTE donne le nombre d'éléments d'une liste. NOTION DEAIVEE: SOUS~LISTES # SOUS~LISTES E LISTES -? parties de LISTES ### e LISTES ( I = LISTE~VIDE e' SOUS~LISTES(1) = = J ) oti } e E ELEMENTS # 17 E LISTES 1 = EN-LISTE(e.11) et SOUS~LISTES(1) = {17} U SOUS~LISTES(17) Commentaire: Les SOUS~LISTES d'une liste sont les listes obtenues en enlevant progressivement les éléments de tete. DOMAINES UTILISES POUR LA DEFINITION DE LA MACHINE données. données1. données2. noms, marques~de~nature, marques de comparaison i- données. données2 sont des ensembles finis disjoints F données = données u données2 i- noms est un ensemble dénombrable @ marques~de~nature = {c1, c2, v1, v2, d1, d2 niv} @ marques~de~compariaison = {égal. différent, non~décidé} Commentaire: Cette rubrique spécifie les informations qui s'échangent entre la machine et l'utilisateur lors des commandes. -en plus du code de la commande. En ce qui concerne les données. la compétence de la machine se limite à pouvoir les mémoriser et les comparer. Par contre. l'utilisateur disposera en général de mécanismes leur conférant une signification particulière. par exemple arithmétique ou textuelle Pour plus de commodité. deux formats sont prévus: les données et les données2. En ce qui concerne les noms. ils sont sous la maitrise de la machine: elle décide de l'évolution dynamique de leur signification. et elle seule peut les Interpréter réellement. L'utilisateur ne peut rien faire des noms que la machine lui révèle. sinon les mémoriser. et les re-citer tot ou tard lors d'une commande, ou les oublier. Les diverses marques servent dans le cadre de conventions communes entre la machine et l'utilisateur. pour discriminer un cas parmi plusieurs possibles dans certaines situations. varlabies1. yariables2. variables. niveaux. atomes, cons. cons2. constructeurs. termes. sous termes. remplacement. construitsl. construits2 @ niveaux = entiers i- variablesl variables2 sont des ensembles dénombrables disjoints i- variables = variablesl U variables2 i- variables. données. niveaux sont disjoints i- atomes = données u niveaux @ constructeurs = {cons1. cons2} @ @termes. variables @ atomes constructeurs @ est un espace~de~termes avec termes~construits. sous~termes. remplacement en tant que notions dérivées TERMES~CONSTRUITS, SOUS~TERMES.REMPLACEMENT tant (t E construitsl i tg,td E termes t=conslCtg.td) ) @@t ( t E construits2 i tg.td E termes t=cons2ttg.td) ) Commentaire: Cette rubrique spécifie la sorte d'information conservée par la machine. Parmi les termes. seules les données peuvent etre échangées avec j utilisateur. Les autres termes restent confinés dans la machine et ne sont accessibles à l'utilisateur qu'indirectement en pratiquant les commandes répertoriées et des noms décidés par la machine elle-meme. Les variables constituent une sorte particulière de feuilles. Elles servent à introduire une relation supplémentaire entre termes. la relation "être une instance". Un terme est une instance d'un autre terme s'il s'obtient en remplaçant certaines des variables de ce dernier par d'autres termes. Dans la littérature, on emploie également les expressions "t2 subsume t1- ou ^t2 shématise ti" en place de -t1 est une instance de t2-. Pour faciliter l'interprétation aie notions propres å certains langages logiques, et éviter des codages peu performants de la part de l'utilisateur. la machine offre deux classes de variables: les variables et les variables2. Les niveaux sont des atomes particuliers qui peuvent etre captés et conservés par l'utilisateur et qui iui permettent d'effectuer certains contrées sur l'état de sauvegarde. La figure 6 illustre comment se répartissent les diverses classes de termes. .L ,&num; termes Commentaire : 1 est un élément utilise dans la spécification pour ;ouer le rôle d'"indéfini", Définition : désignations désignations est l'ensemble ainsi défini:: De désignations # D e noms # (termesu{@}) et V n s noms 3 cons s constructeurs 3 tg,td E termes D(n) = cons(tg t@) 1 i ng.nd E noms C D(ng)=tg et D(nd=td ) Commentaire: Une désignation est tee que si un terme est désignable. c'est-a-dire s'il existe un nom qui désigne ce terme. tous ses sous-termes le sont aussi. Une des composantes de l'état de la machine est une designation et sert a exprimer quels sont. a tout moment. les termes accessibles à l'utilisateur. et via quels noms. L'utilisateur dispose de commandes pour faire évoluer cet état de désignation. sauvegardes, sous sauvegardes, sauve. sauvegardeuide. taille sauvegardes, termesxtermesxtermes. sauve. sauvegardeuide. taille > est un espace~de~listes avec sous~sauvegardes en tant que notion dérivée SOUS~LISTES Commentaire: Une sauvegarde est une pile de triplets de termes. Chaque triplet constitue une strate de la pile. Le nombre de termes dans une strate a été choisi égal a trois pour obtenir une bonne souplesse d'utilisation. Une des composante de l'état de la machine est une sauvegarde, l'utilisateur dispose de certaines commandes pour modifier cette sauvegade, c'est a dire. empiler une strate, dépiler une strate, capter l'état de sauvegarde courant sous forme d'un niveau et le recycler plus tard en tant que paramètre d'une commande de modification de l'état de sauvegarde a ce moment a. NATURE DE LA MACHINE: COMMANDES. PARAMETRES. RESULTATS. ETAT. L'utilisateur soumet des commandes a la machine séquentiellement au cours du temps. Toute commande a pour composantes un code de commande et en général des composantes complémentaires qui appartiennent à des domaines divers selon la commande, et qui sont précisées sous la rubrique 'entrées" dans la spécification de la commande. Le résultat rendu par la machine en réponse å une commande a ses composantes dans des domaines qui dépendent aussi de la commande considérée, et qui sont précisées sous la rubrique 'sorties" dans la spécification. Entre deux soumissions de commandes la machine a un état qui est un élément de désignations x sauvegardes. La soumission d'une commande fait passer l'état de à . Entre Davant, Savant. les entrées de la soumission. Après. Sapres et les sorties de la soumission, il y a la relation CONTRAINTE = > EVOLUTION où CONTRAINTE et EVOLUTION sont les relations postes respectivement sous les rubriques "contrainte" et 'évolution' dans la spécification de la commance. Commentaire: Les deux composants d'un état peuvent se comprendre de la façon suivante. - D constitue l'"état de désignation des termes". Une famille de commandes le concerne et fait changer la signification des noms. - S constitue l'"état de sauvegarde". Des commandes spécifiques permettent de le faire évoluer a' la manière d'une pile. Ces commandes ont aussi l'effet annexe d'affecter ou consulter l'état de désignation. Quand l'utilisateur ne respecte pas la contrainte associée à une commande, l'effet est indéfini. Si l'utilisateur est mal conçu. et risque par exemple de citer lors d'une commande un nom ne signifiant rien. ou signifiant un terme par hasard. le concepteur est dans l'impossibilité de prouver que la relation de la rubrique "contraintes" est toujours vraie. REPERTOIRE DES COMMANDES Les commandes peuvent entre regroupées selon les familles suivantes: Manipulation de la désignation des termes: construire, créer~variable, substituer, accéder~gauche, accéder-droite créer~donnéel, créer-donnée2, accéder~donnéel, accéder~donnée2 tester~nature, comparer Manipulation des sauvegardes: sauvegarder, reprendre, obtenir~niveau~courant. couper ération de mémoire : réduire Initialisation: initlaliser Commande construire Entrées: ng.nd E noms m E (ci.c2j Sorties: nt E noms Contrainte: Davant Evolution: ( m=cl et Daprès (n@ = consl (Davant(ng).Davant(nd) ) ou ( m=c2 et Daprès(nt)=cons2(Davant(ng), Davant(nd)) ) et V n E noms ( Davantin)zi # Daprès(n)=Davant(n) ) et SaNés=Savant Commentaire: La commande construire crée la représentation d'un terme construit, accessible ensuite par le nom rendu en résultat. Commande créer~variable Entrfss: m E (v.v2) Sorties: nv E noms Evolution: ( m=vl et Daprès(nv) E variables i ) ou ( m=v2 et Dapres(nv) E variables2 ) et Davant(nv)=l et V n e noms Davant(n)#@ # (Daprès(n)=Davant(n) et Daprès(nv)#Davant(n)) et Saprès=Savant Commentaire: La commande créer~variable crée une nouvelle variable. accessible ensuite par le nom rendu en résultat.La variable est nouvelle en ce sens qu'elle n'était pas accessible auparavant par désignation, Commande substituer Entrées: nv.nt E noms Contrainte: Davant(nv) e variables et Davant(nt)#@ et Davant(nv) ,&num; sous~termes(Davant(nt)) Evolution: V n e noms Davant(n)#@ # Daprès(n) = remplacement de Davant(nv) par Davant(nt) dans Davant(n) et Saprés=Savant Commentaire: La commande substituer modifie tous les termes accessibles par la désignation courante, en y remplaçant toute occurence d'une variable donnée par un terme donné. Par contre les termes sauvegardés dans la pile ne sont pas affectés. La machine ne permet de représenter que des termes finis non bouclés. c'est à dire qui ne sont pas sous-termes d'eux-meme. L'utilisateur est responsable du respect de cette limitation. la machine ne faisant pas de vérifications pour des raisons d'efficacité. Commande créer donnéel Entrées: d E données Sorties: nd E noms Evolution: Daprès (nd)=d et V n E noms ( Davant (n) # 1 = > Doprès(n)=Darant(n) ) et SaprEs=Savant Commande créer donnée2 Entrées: d E données2 Sorties: nd E noms Evolution: Deptès(no)=d et V n E noms ( Davant(n)#1 = > Daprès(n)=davant(n)) et Saprès=Sarant Commentaire: Les commandes créer~donncel et créer~donnée2 permettent d'obtenir une désignation pour une donnée de type i ou 2. k'utilisateur peut alors la faire intervenir dans des constructions de termes grace aux commandes telles que construire ou substituer. Commande accéder~donnéel Entrées: nd E noms Sorties: d E données Contrainte: Davant(nd) e données1 Evoiution: d=Davant(nd) et Daprés=Davant et SaprEs=Savant Commande accéder~donnée2 Entrées: nd E noms Sorties: d E données2 Contrainte: Davant(nd) s données2 Evolution: d=davant(nd) et Daprès=Davant et Saprès=Savant Commentaire: Les commandes accéder~donnée1 et accéder~donnée2 restituent la donnée de type 1 ou 2 désignée. Commande accéder~gauche Entrées: n E noms Sorties: ng E noms Contrainte: Davant(n) E termes~construits Evolution: # cons E constructeurs + td E termes Davant(n)=cons(Davant(ng),(d) et Daprès=Davant et Saprès=savant Commande accéder droite Entrées: n E noms Sorties: nd E noms Contrainte: Davant(n) etermes~construits Evolution: + cons E constructeurs # tg E termes Davant(n)=consCtg,Davant(nd)) et Daprès=Davant et Saprès=savant Commentaire: Les commandes accéder-gauche et accéder~droite permettent d'accéder aux sous-termes des termes couramment accessibles. Commande tester~nature Entrées: n enoms Sorties: m E marques~de~nature Contrainte: Davant(n)/1 Evolution: ( Davant(n) E construitsl et m=c1 ) ou ( Davant(n) E construits2 et m=c2 ) ou ( Davant(n) E variablesi et m=vl ) ou ( Davant(n) E variables2 et m=v2 ) ou ( Davant(n) E données1 et m=dl ) ou ( Davant(n) E données2 et m=d2 ) ou ( Davant(n) e niveaux et m=niv ) et Daprbs=Davant et Saprbs=Savant Commentaire: La commande tester~nature révèle la nature du terme désigné parmi les diverses classes ultimes de termes illustrées sur la figure 6. Commande comparer Entrées: nl.n2 E noms Sorties : m e marques~de~comparaison Contrainte: Davanf(ni)/1 et Davant(n2)## Evolution: Daprès=Davant et m=égal # Davant(n1)=Davant(n2) et m=diff6rent = > Davant(n1)#Davant(n2) et m=non~décidé C Davant n1) # termes~construits et Davant(n2) # termes~construits ) et Saprès=Savant Commentaire: La commande comparer ne permet pas de comparer de façon systématiquement décisive deux termes construits quelconques.Dans le cas de deux termes construits, cette opération, nécessite généralement un parcours des deux termes qui ferait double emploi. dans les applications visées, avec les parcours commandés par l'utilisateur pour ses propres raisons. Si deux termes construits sont égaux, la machine répond en général non-décidé, mais il se peut qu'elle réponde égal si la méthode de réalisation fait qu'elle parvient à cette décision de façon directe. commande sauvegarder Entrées: n1,n2,n3 E noms Contrainte: Davant(nl);l et Davant(n2)# et Davant(n3)/1 Evolution: Dapréa= Devant et Après = sauve( , Savant) Commentaire: La commande sauvegarder permet à l'utilisateur de conserver un vecteur d'état constitué de trois termes. tout en poursuivant le processus de transformation de la collection des termes couramment désignables. Le vecteur d'état peut Outre récupéré par la suite tel qu'il a été sauvegardé, en pratiquant la commande reprendre. Il n'est pas affecté par les opérations qui se déroulent entre sa sauvegarde et sa reprise: en particulier. les commandes substituer n'effectuent pas de remplacements de variables dans les termes sauvegardés. L'ordre des sauvegardes et des reprises se fait selon le principe que le dernier sauvegardé est le premier repris: la mémoire de sauvegarde fonctionne donc en pile. Commande reprendre Sorties: n'.,r'.2.n3 E noms Contrainte: Savant t sauvegardevlde Evolution: Savant = sauve( . Saprs ) Commentaire: La commande reprendre. dans le cas où la pile de sauvegarde n'est pas vide. rend à nouveau accessible un vecteur d'état constitue de trois termes. Seuls ces termes et leurs sous-termes deviennent alors couramment désignables. Le processus de transformation en cours avant la commande est donc abandonné et remplacé par la reprise du processus de transformation figuré par le vecteur d'état récupéré. Commande obtenir niveau courant Sorties: np E noms Evolution: Daprt(np)=taille(Savanl) et V ni E noms ( Davant(ni)ti = > Dapr(nl)=Davant(nl) ) et Saprèa=Savant Commentaire: Les commandes obtenir~niveau~courant et couper sont à la disposition de l'utilisateur pour lui permettre d'effectuer un controle complexe de la gestion des sauvegardes. La commande obtenir~niveau~courant rend la taille de la pile courante. désignable en tant que niveau. Comme pour n'importe quel atome, l'utilisateur peut conserver des niveaux de piles. les comparer et construire des termes les contenant. Cependant. bien que les niveaux soient des entiers. l'utilisateur ne dispose pas de commandes arithmétiques pour les manipuler; la seule commande susceptible de les interpréter est couper. Par propriétés des commandes du répertoire. les niveaux couramment dèsignables sont toujours inférieurs ou égaux à la taille de la pile de sauvegarde courante. De plus, les niveaux conservés dans les éléments d'une pile de sauvegarde quelconque sont toujours strictement inférieurs à la taille de cette pile. Commande couper Entrées: np e noms Contrainte: Davant(np) E niveaux Evolution: #n1 e noms Davant(n1)## # Daprès(n1)=coupé(Davant(np)) et Saprès E SOUS~sauvegardes(Savant) et tailIe(Sapré)=Davant{np) Commentaire: La commande couper permet de supprimer au sommet de la pile de sauvegarde un certain nombres de vecteurs d'état. La nouvelle pile de sauvegarde est la sous-pile de la pile courante dont la taille est égale au niveau donné en paramètre de la commande. Afin de conserver la propriété mentionnée, les niveaux qui sont accessibles depuis les termes désignables et qui sont supérieurs à la taille de la nouvelle pile sont diminués et rendus égaux à la taille de la nouvelle pile. Définition: coupé coupé e (termes x niveaux) # termes et V t E termes V n E niveaux (1 # niveaux et t # termes~construits et coupé(t.n.)=t) ou C t E niveaux et 1#n et coupé(t.n)=t ) ou ( t e niveaux et t > n et coupé(t,n)=n ) ou p cons E constructeurs 3 lg ,td X termes t=cons (tg .td) et coupé Commentaire: coupé(t,n) donne le terme déduit de t en remplaçant dans ce dernier tout niveau supérieur à n par n. Commande réduire Entrées: ni,n2.n3 E noms Sorties : nn1, nn2, nn3 e noms Contrainte: Davant(ni)t1 et Davanl(n2)ti et Davant(n3)/1 Evolution: Daprès (nn1 )=Davant(n 1) et Daprâa(nn2)=Davant(n2) et Daprbs (n n3) =Davant(n3 > et Sapra=Savanr Commentaire: Après une commande réduire, les termes couramment accessibles sont réduits à trois termes et leurs sous-termes. Cette commande concerne la gestion automatique des ressources de mémoire. Elle se situe donc sur un autre plan que les autres commandes du point de vue strict des possibilités de calcul. Cette commande est rendue nécessaire par la nature, délibérément choisie, de la relation entre la machine et son utilisateur. L'utilisateur est extérieur à la machine, en ce sens qu'il a son propre contrôle et ses propres mémoires Inconnus de la machine. Toute information créée pour i'utilisateur peut donc à priori etre utilisée dans le futur. La commande réduire permet à l'utilisateur de faire connaitre les informations, restreintes à trois termes, qui l'intéressent pour la suite. La machine peut alors en déduire que l'information portée par certaines ressources de mémoire n'est plus utile à la représentation de l'état abstrait, parce- que devenue inaccessible à l'utilisateur. Elle peut récupérer ces ressources et les recycler pour une nouvelle utilisation. La commande reprendre provoque également le meme mécanisme de récupération: ceci est possible car la désignation est alors réduite aux trois noms rendus en résultat. Cependant, sans la commande réduire. les séquences Ininterrompues de manipulations de la désignation entraineraient l'occupation d'une quantité croissante de mémoire, conduisant Inéluctabîement à la saturation du système comme celà se produit dans les interpréteurs PROLOG existants. Commande Initialiser Evolution: Saprêa=sauvegardevide Commentaire: La commande initlaliser fait passer la machine dans un état sain. La pile de sauvegarde est vide et aucun terme n'est conservé par la machine. - ANNE > :E 2 STRUCTURES DE DONNEES ET REPRESENTATION STRUCTURES DE DONNEES TYPES DES INFORMATIONS marque~de~nature AVEC L'UTILISATEUR donnée 1 donnée2 ECHANGEES a pour valeurs possibles (ci,c2,v1,v2.dl,d2,nlv3 marque~de~comparaison a pour valeurs possibles {éga@ différent,non~décidé} nom est une structure à plusieurs champs indicateur : marque~de~nature Information @référence ou donnée Commentaire: Les types d'information donnée. donnée2. marque~de~nature. marque~de~comparaison et nom correspondent respectivement aux ensembles @@nnées1. données2. marques~de~nature. marques~de~comparaison et noms. '%t' type référence est d'usage purement interne bla machine. Le codage de ces divers types d'informatiofl est illustré sur la figure 7. TYPES D'INFORMATION D'USAGE INTERNE référence niveau {11bre,indécis} {actif. coupé, mort} Commentaire: Le type d'information référence permet d'adresser la mémoire des cellules. Le type niveau correspond b l'ensemble des niveaux flibre.lndécis sont des marques qui servent à indiquer le statut particulier des cellules au format variable décrit ci-après. (actif.coupé.mort} sont des marques qui servent à indiquer le statut particulier des cellules au format géniteur décrit ci-aprés. FORMATS DE CELLULE constructeur est un format à plusieurs champs gauche nom droite :nom variable est un format à plusieurs champs statut : {11bre, indécis} géniteur référence liaison :noo :{actif, coupé, mort} un format à un seul champ :donnée2 géniteur est un format à plusieurs variantes discriminées par un champ nature valeur~d2 est parmi géniteur~actif si nature=actif qui comporte les autres champs niveau niveau précédent référence ni nom n2 nom n3 :nom géniteurcoupé si nature=coupé qui comporte les autres champs niveau :niveau précédent : référence géniteur~mort si nature=mort Commentaire: Une cellule peut être considérée selon quatre formats dIfférents, constructeur. variable, valeur~d2 et géniteur. La figure 8 illustre la répartition des champs de ces divers formats sur des mots de taille fixe. Les formats constructeur, variable et valeur~d2 servent à la représentation des termes. Ces trois formats sont de taIlle fixe et occupent un mot. Le format géniteur sert à la représentation de l'état de sauvegarde. Il regroupe trois formats de tailles différentes, géniteur~actif. géniteurcoupé ou géniteurmort discernés par le contenu d'un champ commun nature. Les formats 4niteur~coup et géniteur~mort occupent un seul mot. Le format géniteur~actif occupe quatre mots chai nés comme l'indique la figure 8: ces quatres mots sont considérés comme une seule cellule. référencée par l'adresse du premier mot. L'éclatement de ce format sur quatre mots chaînés plutôt que sur des mots consécutifs à été choisi pour que le mécanisme d'allocation de mémoire gère des entités de taille fixe. MEMOIRE DES CELLULES La machine comporte une collection de cellules, référencées par une information de type référence. Chaque cellule peut être considérée indifféremment sous un quelconque des divers formats pr6-cités. Les mécanismes qul sont décrits dans ce document exploitent des fonctions d'accès prédéfinies aux champs des cellules car ces champs ne sont pas accessible toujours isolément. Dans la description des mécanismes. les fonctions d'accès aux cellules sont notées d'une façon qui implique sous quel format la cellule référencée est considérée. Ces fonctions d'accès sont les suivantes, r étant la référence de la cellule: gauche(rl champ gauche droitetr ] champ droite état~Haison['] champs statut, géniteur liaison ['] champs liaison valeur~d2['] valeur~d2 état~géniteur['] champs nature, niveau précedent [ r ] champ précédent nom~1~2~3['] champs n1, n2, n3, Chaque fonction d'accès peut être exploitée soit en lecture ce qui est noté: fonction d'accès soit en écriture, ce qui est noté: fonction d'accès Commentaire:: Les cellules sont Identique et accessibles sous n'importe quel format parce que le propre de la machine est précisément d'étre un système d'allocation de mémoire pour des besoins divers et changeants. Mais, pour être logiquement corrects, les mécanismes décrits doivent accéder eux cellules sous un format correct. Pour ne pas entrer dans les détails inintéressants de la gestion des accès aux variantes du format géniteur, ces détails sont supposés réalisés par les primitives d'accès éttgéniteur, précédent e-s nom~1~2~3 : ces accès testent le champ nature pour décider des mesures a prendre pour adresser la mémoire. En particulier dans les accés état~génlteur la composante niveau est non signifiante si nature=mort L'écriture avec nature=coupé, si l'état antérieur est nature=actif, provoque automatiquement la recopie du champ précédent dans le premier mot. de sorte à assurer la cohérence désirée, REGISTRE GENITEUR COURANT géniteurcourant référence Commentaire: Le registre géniteur~c.ourant contient la référence d'une cellule considérée sous le format géniteur. Il repère la tète de la liste des géniteurs qui représente l'état de sauvegarde courant. METHODES DE REPRESENTATION NOTIONS DE BASE références # références est fini # données i = références H noms = marques~de~naturexréférences DéfInition: indicateur. information indicateur E noms - marques de~nature information E noms - références et # m e marques~de~nature # r e références indicateur ( )=m et information( )=r états~de~cellule. gauche. droite. statut géniteur. liaison, valeur~d2. nature. niveau, précédent, nî, n2, n3 # états~de~cellule est fin@ # gauche, droite E états~de~cellule - noms ##g.d e noms # c e élat~de~cellule (guche(c)=g et droite (c)=d) # statut e états~de~cellule # {libre indécis} #géniteur e états~de~cellule # rétérences #llaison e états~de~cellule # noms # # s e { libre. indécis} # g e références # l e états~de~ceilule statut(c)=s et géniteur(c)=g et liaison(c)=1 # valeur~d2 e états~de~cellule # données2 # # d e données2 # c e états~de~cellule valeur~d2(c)=d H nature E états~de~cellule - {actif, coupé. mort} # niveau E etats~de~cellule - niveaux # précédent e états~de~cellule # références H nl,n2,n3 E otats~de~cellule - noms # # i e niveaux # p E références # n1.n2.n3 e noms # c e états~de~cellule nature(c)=actif et niveau(c)=i et précedent(c)=p et nl(c)=nl et n2(c)=n2 et n3(c)=n3 # # i e niveaux # p e réferences # c e états~de~cellule nature(c)=coupé et niveau(c)=i et précédent(c)=p F i c E états~de~cellule nature(c)=mort Définition: configurations configurations = références - états~de~ceilule Commentaire: données est assimilé à références. indicateur et information sont les fonctions de sélection de champ de la structure nom. Les états~de~cellule sont les informations brutes que la mémoire est capable de conserver dans une cellule. Les diverses fonctions posées traduisent la capacité des cellules et les sélections de champs des divers formats sous lesquels une cellule peut être considérée. Les configuratlons sont les états possible de la mémoire des cellules. REPRESENTATION D'UNE DESIGNATION DE TERMES Définition: d variable liée n est d~variable~liée dans M si n E noms M E configurations et indicateur(n)=vl ou Indicateur(n)=v2 et statut (M (information(n)))=indécis et nature (géniteur(M (information mort Définition: d terminal n est d terminal dans M si n e noms M e configurations et non C n est d~variable~liée dans M ) Définition: d ultime nu est d~ultime de n dans M si n,nu E noms M E configurations et # Sn E sentiers ^ noms) 3 i E entiers Sn(O)=n et # @ e entiers j Sn(j) est d~variable~liée dans M et Sn(j+1) = liaison (M (Information (Sn(j)))) et Sn(l) est d~terminal dans M et indicateur(Sn(i))/niv et nu=Sn(i) ou Indicateur (Sn(i)]=niv et indicateur (nu)=niv et Information(nu) est ultime de information(Sn(l)) dans M Définition:: dregrésentatIon M est dreprésentation de D si M e configurations D e désignations et 9 n e noms D(n) # # # # nu e noms nu est d~ultime de n dans M et indicateur(nu)=c1 # # ng.nd e noms ng est ultime de gauche(M(information(nu))) dans M et nd est d~ultime de drolte(M (Information (nu))) dans M et D(n) = consl(D(ng),D(nd)) et indicateur(nu)=c2 i ng.nd E noms ng est d~ultime de gauche(M(information(nu))) dans M et nd est d~ultime de drolte(M(information(nu))) dans M et D(n) = cons2(D(ng),D(nd)) et indicateur (nu)=v1 # D(n) e var1 etvnn.nnu e noms D(nn)=D(n) et nnu est d~ultime de nn dans M # nnu=nu et indicateur(nu)=v2 # D(n) e var2 etVnn,nnu é noms D(nn)=D(n) et nnu est d~ultime de nn dans M # nnu=nu et indicateur(nu)=d1 # D(n)=information(nu) et indicateur(nu)=d2 # D(n)=valeur~d2(M(information(nu))) et lndlcateur(nu)=niv = > D (n)=niveau(M (information(n u))) Commentaire: Une cellule de référence r considérée sous le format constructeur représente un terme construit. Les champs gauche et droite de la cellule contiennent les noms de deux termes tg et td. Un nom de la forme cl:r ou c2:r est un nom direct de consl(tg.td) ou cons2(tg.td). Une cellule considérée sous le format variable admet deux interprétations différentes selon l'état des champs statut et géniteur. Une telle cellule est appelée variable libre si son champ statut contient libre ou si son champ géniteur contient la référence d'un géniteur mort Sinon. c'est à dire si son champ statut contient Indécis et si son champ géniteur contient la référence d'un géniteur actif ou coupé. elle est appelée variable liée. Une variable libre de référence, représente un élément v des variables. Un nom de la forme vlz ou v2:r est un nom direct de v. De plus cette cellule est l'unique représentante de v: elle est citée depuis toutes les représentations des occurences de v dans les termes, de sorte que son remplacement par un terme à l'occasion d'une commande substituer est simplement réalisé par une modification de cette cellule. Une variable liée est un renvoi au terme cité dans son champ liaison. Le remplacement de v par t à l'occasion d'une commande substituer est réalisé en rangeant un nom de t dans le champ liaison de la variable libre qui représente v et en la changeant en variable liée. Le rôle des géniteurs dans la définition du statut libre/liée des variables sera explicité à propos de la représentation de la sauvegarde. Une variable libre est initialement créée avec son champ statut valant libre; lors d'un remplacement, la marque indécis est rangée dans son champ statut et la référence du géniteur courant du moment, contenue dans le registre géniteur~courant, est rangée dans son champ géniteur. Le géniteur courant est toujours actif ou coupé, de sorte que la variable est alors considérée comme liée; elle demeure liée jusqu'à 'exécution d'une commande reprendre qui. pour restaurer l'état de d isignation des termes du moment de la sauvegarde, peut nécessiter de rétablir un statut libre pour cette variable. Pour cela. lors de l'exécution d'une commande reprendre, le géniteur courant du moment est transformé en géniteur mort, de sorte que toutes les variables qui ont été liées depuis la dernière sauvegarde redeviennent libres. Dans ce cas le statut libre d'une variable est code indirectement par le fait que son champ géniteur contient la référence d'un géniteur mort. Les géniteurs jouent donc un rôle similaire à la gtrainbsa utilIsée dans la plupart des interpréteurs PROLOG. Une cellule de référence, r considérée sous le format aieurd2 contient un élément d des données2. Un nom de la forme J'2:r est un nom direct de d. Une cellule de référence r considérée sous le format géniteur~actif contient dans son champ niveau un élément i des niveaux Un nom de la forme niv.r est un nom direct de s. La représentation d'un élément d des données1, ne nécessite aucune cellule. Un nom de la forme d1:d est un nom direct de d. On remarquere que, à l'exception des noms directs des données1, tous les noms sont de la forme m:r, où r est la référence d'une cellule et m est une marque qui indique le type de cette cellule. c'est 3 dire sous quel format elle doit être considérée. La méthode choisie consiste donc à noter le type d'une cellule à chaque occurence de sa référence, plutot que de la noter sur la cellule eile-meme. Bien que cette méthode soit légèrement plus coûteuse en taille de mémoire. elle a pour avantages que les données i n'occupent aucune cellule et que le test de la nature du terme désigné par un nom est plus rapide. Ce dernier critère est prépondérant dans les applications visées. En plus des noms directs précédemment énumérés, un nom peut a un moment donné désigner indirectement un terme. Un premier cas concerne les noms de la forme v1:r ou v2:r où r est la référence d'une variable liée. Un tel nom. qualifié de ci~variable~liée dans la configuration de mémoire considérée. peut être le départ d'une chaine de noms de longueur finie. le champ liaison de la varlable liée citée par un nom étant le nom suivant de la chaine. Le dernier nom de la chaine ne cite pas une variable liée et tous les noms de la chaine désignent le même terme que lui. Un autre cas de noms indirects concerne les noms de la forme niv:r où r est la référence d'un géniteur coupé. Un tel nom cite une strate autrefois sauvegardée qui a été détruite par une commande couper. La chai ne de références issue du champ précédent de ce géniteur coupé se termine par la référence d'un géniteur sotif qui représente l'élément des niveaux actuellement désigné par ce nom. Ce mécanisme de désignation indirecte est décrit par la relation d~ultime qui associe à un nom un nom direct désignant le même terme. Tous les noms qui participent internement à la représentations des termes ne sont pas nécessairement du domaine connu de l'utilisateur. Le domaine de définition de la désignation D comporte essentiellement des noms directs. plus éventuellement une collection de noms indirects qui dépend de l'historique des commandes. Après une commande réduire. ou une commande reprendre, la désignation D offerte à l'utilisateur ne comporte que des noms directs. Ce sont les trois noms rendus en résultat par la commande, ainsi que les noms directs des représentations des sous-termes accessibles par ces trois noms. Cette restriction de la désignation, invisible à s'utilisateur, se manifeste lors de l'exécution des commandes d'accès aux termes accéderauche et accéder~droite, qui ne rendent en résultat que des noms directs.Par contre, entre deux exécutions de réduire. c'est à dire pendant que l'utilisateur est en phase d'élaboration de résultats intermédiaires. la désignation D peut comporter temporairement des noms indirects: ce sont les noms qui citent des variables récemment créées puis liées par une commande substituer, ou des strates récemment sauvegardées puis détruites par une commande couper. Pendant ces phases l'utilisateur peut en effet conserver de tels noms pour accéder aux termes. Cette réduction de la désignation est en accord avec la spécification de la machine qui laisse en fait un choix encore plus vaste à la réalisation. Elle est importante pour le mécanisme de récupération de mémoire: l'invisibilité des géniteurs coupés permet leur récupération après avoir remplacé les occurences de leurs références par les références des géniteurs actifs équivalents; l'invisibilité des variablesw es permettrait de remplacer certaines occurences de leurs références. mais pas toutes à cause du partage avec la sauvegarde décrit au paragraphe suivant. par les noms directs équivalents. Ceci accélérerait les accès aux termes en supprimant la traversée de ces variables liées qui ont servi d'intermédiaires de construction et qui ne servent plus désormais. Ceci permettrait également de récupérer certaines de ces variables. Ce mécanisme n'est cependant pas réalisé dans la version de la machine présentée dans ce document La relation dreprésentation relie la composante D de l'état abstrait et l'état concret de la mémoire. Cette relation est encore indéterministe: pour un élément M des configurations. de nombreux éléments D des désignations la satisfont. Le complément de détermination dépend en effet de l'historique des commandes et ne peut être pris en charge par une relation faisant intervenir seulement l'état de la mémoire des cellules. La figure 9 est un exemple de d~représentation. On remarquera que plusieurs noms différents. bien que directs. peuvent désigner le même terme, par exemple D(c1:C1)=D)c1:C3) La représentation permet le partage classique des représentations de sous-termes,. par exemple la cellule C7 qui participe à la représentation des termes D(ci:C7), D(cl:C6), D(cl:C3) et D(cl:Cl). La cellule C9 est une variable liée. les cellules C5 et C8 sont des variables libres qui représentent deux éléments x et y des variablesl. REPRESENTATION D'UNE SAUVEGARDE Définition: 1 variable liée n est t~variable~liée pour k dans M si n e noms k E niveaux M E configurations et indicateur(n)=v1 ou indicateur(n)=v2 et statut(M (Information(n)))=indUcis et nature(M(génieur(M(information(n)))) t mort et niveau(M(géniteur(M(intormation(n)))) Définition: t terminal n est ~terminal pour k dans M si n e noms k E niveaux M E conflguraticns et non( n est t~variable~ liée pour k dans M ) Définition:: t ultIme nu est t~ultime de n pour k dans M si nnu é noms k É niveaux M e configurations et # Sn e (entiers # noms) # i e entiers Sn(O)=n et # j e entiers j Sn(j) est t~variable~liée pour k dans M et Sn(1+1)=llaison(M(information(Sn(J)))) et Sn(i) est t~terminal pour k dans M et indicateur(Sn(i))#niv et nu=sn(i) ou indicateur(Sn(i))=niv et indicateur(nu)=niv et indormation(nu) est s~ultime de Jnformation(Sn(i)) dans M Définition:: t représentation M,k est t~représentation de D si M s configurations k e niveaux D e désignations et V n e noms D(n)## # # nu # noms nu est ultime de n pour k dans M et indicateur(nu)=c1 # # ng.nd # noms ng est t~ultime de gauche(M(information(nu))) pour k dans M et nd est t~ultime de droite(M(information(nu))) pour k dans M et D(n)=consl(D(ng).D(nd)) et indicateur(nu)=c2 # # ng.nd e noms ng est t~ultime de gauche(M(information(nu))) pour k dans M et nd est t~ultime de droite(M(informatîon(nu))) pour k dans M et D(n)=cons2(D(ng).D(nd)) et indicateur(nu)=v1 # D(n) e var1 etVnn.nnu E noms D(nn)=D(n) et nnu est l~ultime de nn pour k dans M nnu=nu et indicateur(nu)=v2 # D(n) e var2 et V nn,nnu e noms D(nn)=D(n) et nnu est t~ultime de nn pour k dans M # nnu=nu et indicateur(nu)=d1 = > D(n)=information(nu) et lndlcateur(nu)=d2 = > D(n)=valeur~ds(M(information(nu))) et indlcateur(nu)=niv = > D (n)=niveau(M (information(n u))) Définition:: ultime gu est s~ultime de g dans M si g,gu E références M e configurations et + Sr e (entiers - références) + i e entiers Sr(O)=n et V j E entiers j nature(M(Sr(j)))=coupé et niveau(M(Sr(J)))=niveau(M(gu)) et Sr(J+1)=précédent(M(Sr(j))) et gu=Sr(i) et nature(M(gu))=actif Définition : s~correspondances s~correspondances = références # (sauvegardesU(1)) Définition : s~représentation M est s~représentation de SC si M e configurations SC E 5~correspondances et V g e références SC(g) # 1 # # gu e références gu est ultime de g dans M et niveau (M (gu))=O # SC(g) = sauvegards~vide et niveau(M(gu))#O # # ggu e références # D e désignations gu est s~uitime de précédeni(Migy)) dans M et niveau(M(ggu)) = et M.niveau (M(ggu)) est t~représeniation de D et SC(g) = sauvei . SC(ggu)) Commentaire; La sauvegarde S esi une liste de triplets de termes.Une telle liste es1 représentée par des cellules au format géniteur~actif ou géniteur~coupé chainées par leurs champs précedent le premier géniteur de la chaine. appelé géniteur courant, est à tout moment repéré par le registre géniteur~courant. Une cellule au format géniteur~coupé contient dans son champ précédent un revoi à un autre géniteur. Elle est le vestige d'une strate sauvegardés puis détruite par une commande couper. La chaine de références issue de son champ précédent est composée d'un nombre fini de références de géniteurs coupés et se termine par la référence d'un géniteur actif qui lui est équivalent Ce mécanisme de renvoi est décrit par ta relation s~ultime qui associe à une référence de géniteur la référence du géniteur actif équivalent Une cellule au format géniteur~actif dont le champ niveau contient o représente la sauvegarde~vide, Par comportement de la machine, cette cellule est unique dans la mémoire: elle ast créée m l'initiatisation. Une cellule au format géniteur~actif dent le champ niveau contient / différent de o représente une sauvegarde de teille L Son champ précédent contient la référence d'un géniteur dont l'équivalent actif représente la sous-sauvegarde de taille i-I et contient dans ses champs sll, n2 et n3 des noms qui désignent les trois termes de tête de la sauvegarde de taille j. Ces mécanismes sonts décrits pa, la relation s~représentation. Les termes sauvegardés ne sont pas représentés par recopie. c'est à dire par des ressources de mémoire propres. mais par partage de ressources entre eux et avec les termes de la désignation D. En effet. la plupart des termes représentés au niveau k sont des instances de termes représentés au niveau k-l, c'est à dire n'en diffère' que par des remplacements de variables. Lors d'une commande sauvegarder les termes paramètres de la commande sont dejà représentés et l'exécution de la commande consiste à ranger dans les champs ni. n2 et n3 du géniteur courant des noms directs qui désignent ces termes. Cependant la désignation D continue par la suite d'évoluer. notamment par les commandes substituer qui ont un effet de bord sur les termes accessibles par la désignation D. effet qui ne doit pas perturber les termes sauvegardés. Pour cela les variables liées contlennent dans leur champ géniteur la référence d'un géniteur qui indique à partir de quel niveau de sauvegarde cette variable doit être considérée comme liée. En dessous de ce- niveau, cette variable. si elle est rencontrée dans la représentation d'un terme sauvegardé. doit être considérée comme libre. A chaque niveau X est associé une désignation DA qui fait correspondre aux trois noms ni, n2 et n3 les trois termes sauvegardés à ce niveau. La relation trepr8sentation décrit comment sont reliés l'état de la mémoire des cellules, un niveau k et une désignation DA propre a ce niveau. Cette relation est analogue à dreprésentation. la différence étant localisée dans la relation Lvariable~liée qui prend en compte le niveau pour décider du statut libre/liée des variables. Le champ niveau des géniteurs n'est pas utilisé lors de l'exécution des commandes de manipulation de la désignation D. Lors d'une commande reprendre. tous les géniteurs équivalents au géniteur courant du moment sont transformés en géniteurs morts. Ceci supprime toutes les occurences d'un niveau et rend ce niveau réutiîisable pour une sauvegarde ultérieure. Pour l'exécution des commandes, seul le champ nature des géniteurs intervient pour déterminer le statut libre/liée d'une variable. Le champ niveau est utilisé par le mécanisme de récupératIon de mémoire pour connaitre les accès exacts lors du marquage des cellules utiles. La figure 10 est un exemple de sreprésentaflon. La sauvegarde représentée par le géniteur C16 est de taille 4. A chaque niveau 0. 1. 2, et 3 correspond une désignation DO, Dl, D2 et D3. Ces désignations font correspondre des termes aux noms inscrits dans les champs ni. n2 et n3 des géniteurs actifs du niveau correspondant. C15 et C14 sont des géniteurs coupés équivalents au géniteur actif C12. On remarquera le partage dans les représentations des termes sauvegardés à divers niveaux: par exemple les représentations de Di(cl:Ci) et D2(c1:Ci) ont en commun les cellules Cl. C2. C5. C6 et C7. Les variables C2.C6 et C7 sont considérées comme liées dans le niveau 2 alors qu'elles sont considérées comme libres dans le niveau 1. REPRESENTATION DE L'ETAT ABSTRAIT Définition: règles rôles = références - [ ci,c2,vi.v2.d2.niv,disp} Définition : nom~cohérent n est nom~cohérent avec R si n e noms. R e rôles et C indicateur (n)=d1 ou indicateur(n)=R(information(n)) ) Définition : configuration~cohérente M est confIguratIon~cohérente avec R si M e configurations, R e roles et V r e références R(r)=cl ou R(r)=c2 gauche(M(r)) est nom~cohérent avec R et droite(M(r)) est nom~cohérent avec R et C R(r)=vl ou R(r)=v2 ) et statut(M(r))=indécis R(génîteur(M(r))) = niv et nature(M(géniteur(M(r)))) t mort iiaison(M(r)) est nom~cohérent avec R et R(r)=niv et nature(M(r))=coupé R(précêdent(M(r)))=niv et R(r)=niv et nature(M(r))=actif et niveaU(M(r))rO R(précédent(M(r))) = niv et i ru e références ru est s~ultime de précédent (M(r)) dans M et n1 (M(ru)) est nom~cohérent avec R et n2(M(ru)) est nom~cohérent avec R et n3(M(ru)) est nom~cohérent avec R Définition: représentation M,R,g est représentation de D,S Si M e configurations R e roles g e références De e désignations S e sauvegardes et M est configuration~cohérente avec R et # n e noms C D(n)## = > n est nom~cohérent avec R ) et M est d~représentation de D et R(g)=niv et nature et V r s références R(r)=niv et nature(M(r))#mort # S s sentiers - références) i i e entiers S(O)=g etvj e entiers C j S(j+1)=précédent(M(S(j))) ) et S(i)=r et i SC s scorrespondances M est sreprésentation de SC et SC(g)=S et M,niveau(M(g)) est t-représentation de D Commentaire: Un élément des rôles est un statut d'allocation de la mémoire des cellules. La marque disp qualifie les cellule disponibles, Les autres marques qualifient les cellules occupées et indiquent le rôle qu'elles jouent. Un nom qui cite une cellule est nom,coh8rent si cette cellule est occupée et si son rôle est en accord avec ce nom. Un état de mémoire est qualifié de configuratIon~cohérente si toutes les références rencontrées dans les cellules occupées sont des références de cellules occupées et dont le rôle est en accord avec le role induit par l'endroit qui fait référence. La relation représentation relie l'état concret constitué de l'état de la mémoire des cellules et du registre géniteur~courant. un état d'allocation et l'état abstralt constitué de la désignation D et de la sauvegarde S. L'état d'allocation concret résulte du mécanisme d'allocation et de récupération de mémoire et dépend de l'état de ses mémoires propres: il est figuré ici par un role P. La mémoire est internement cohérente. Les noms confiés à l'utilisateur au titre de la désignation D sont cohérents. li n'y a qu'une seule sauvegarde S, et ses sous~sauvegardes, dans le système et tous les géniteurs actifs ou coupés participent à sa représentatIon: tous ces géniteurs sont accessibles par la chaine de références issue du registre géniteurcourant. De plus. la désignation D. qui est en relation de d,repr8sentation avec l'état de la mémoire, est également en relation de t~representation avec le champ niveau du géniteur courant. En effet, la référence du géniteur courant est systématiquement inscrite dans le champ géniteur des variables lors de l'exécution des commandes substituer. Ainsi la représentation d'un terme quelconque accessible par la désignation D est déjà sous une forme prête à être sauvegardée. - ANNEXE 3 LES MECANISMES DU PROCESSUS D'EXECUTION mécanisme recherche~représentant( nn nom ) nom nn - n boucle tantque n.indicateur ç (vl.v2J I m 1 état~liaison [n.information] # e1 si el.statut = indécis alors état~géniteur [n.information] # eg si el.statut = libre alors sortie I Si eg.nature = mort alors sortie I m I I liaison [n.information] # n I Si n.indicateur = niv alors I I I recherche~gén renrésentant(n.information) - n.Information) n e résultat Si nn fait référence à une variable lIée, la valeur de liaison est inspectée. jusqu'à rencontre d'autre chose qu'une variable liée. De plus. si le nom alors obtenu est celui d'un niveau le géniteur actif représentant du géniteur cité par ce nom est recherché. C'est le nom finalement obtenu qu'on appelle représentant de SI la mémoire est internement cohérente et sl le nom nn est cohérent. le mécanisme se termine et ie résultat est ultime de nn. mécanisme recherche~gén~représentant (g : référence) : référence g 2 g1 m étant~géniteur[g1] -étatgén boucle tantque étatgén nature = coupe 1 m précédent[g1] # g1 1 m état~géniteur [g1] # étagén g1 # résultat Etant donné une référence à un géniteur. ce mécanisme rend la référence du premier géniteur actif dans la chaine commençant à ce géniteur, et de même niveau que lui. SI la mémoire est cohérente et si g est la référence d'un géniteur non mort, le mécanisme se termine et le résultat est ultime de g. mécanisme construire( ng.nd nom. mc :(cl,c2j ) nom allocation~celluie ~ref rnc.ref ^ résultat recherche~représentant(ng) ^ rg m rg # gauche [ ref ] recherche~représentant(nd) e rd m rd # droite [ref] Une cellule est allouée. Elle est considérée sous le format constructeur. Deux noms sont rangés dans les champs gauche et droite. qui sont les noms représentants respectifs de ng et nd. Le résultat consiste -en la marque de nature du constructeur et la référence de la cellule.Sur la figure il, le nom représentant de vl:Cl est c1:C2 parce que la varlabie en Ci est liée, son statut étant Indécis et le géniteur correspondant non mort. Le rôle de la cellule référencée par ret passe de disp à ci ( ou c2. selon la marque mo ). La désignatIon D est augmentée du nom cl:ret ( ou c2:r.f ). mécanisme créer~variable mv :(vi,v2) ) nom allocation~cellule ^ ref mv.ref | résultat m llbre,D - état~liaison[ref] Une cellule est allouée. Elle est considérée sous le format variable. Son champ statut est initialisé à libre. Le résultat comporte la marque de nature mv et la référence de la cellule. Ceci est illustré sur la figure 12. Le rôle de la cellule référencée par ref passe de disp à vl ( ou v2, selon la marque mv ). La désignation D est augmentée du nom vi:ref ( Ou v2:ret ). Cette cellule représente une nouvel élément des variables car elle n'est encore référencée depuis nullepart. mécanisme substituer( nv,nt nom ) recherche~représentant(nv) ^ rv recherchereprésentant(nt) - rt m I indécis, géniteur~courant # état-liaison [rv. information] I rt # liaison [rv. information] Le nom représentant de nv cite une cellule qui. vue sous le format variable, est une variable libre. Cette variable subit une liaison, c'est-àdire que sont rangés dans ses champs statut géniteur et liaison respectivement la marque Indécis. la référence du géniteur courant et le nom représentant de nt. Sur la figure 13, le paramètre vi:Ci contient la référence d'une variable liée; son nom représentant cl:C2 est rangé comme valeur de liaison de la variable située en C4. Le nom nv désigne, avant l'exécution de la commande, un élément v des variables. Le nom rw, ultime de nv, est un nom direct de v. Il cite donc la variable libre sur laquelle convergent toutes les représentations d'occurences de v. Par transformation de cette cellule en variable liée, toutes les occurences de v sont remplacées par des occurences du terme désigné par nt. Ce remplacement est effectif dans tous les termes accessibles par la désignation D.Cependant. le champ géniteur de la cellule contient la référence du géniteur courant dont le niveau est supérieur à tous les niveaux couramment sauvegardés, Les désignations propres à chaque niveau. en relation de t~représentation avec l'état de la mémoire. demeurent inchangées et le remplacement est donc Inaffectif dans les termes sauvegardés. mécanisme créer~donnée1( d donnée ) nom dl,d - résultat La création d'une donnée i consiste simplement à adjoindre la marque de nature à l'information passée en paramètre. Les données ne consomment pas de ressource de mémoire. mécanisme créer~donnée2 (d :donnée2) : nom allocation~celluie - ref d2.ref résultat m d # valeur~d2 [ref] Une cellule est allouée pour contenir la donnée. Le résultat comporte la référence de cette cellule. Ceci est Illustré sur la figure 14. Le rôle de la cellule référencée par ret passe de disp à d2. La désignation D est augmentée du nom d2:ret. mécanisme accéder~donnéel( nd nom ) données recherche~représentant(nd) # n n.information # résultat Le résultat est obtenu en retirant au nom représentant de nd sa marque de nature. Le nom nd désigne un liement d des donnéesi. Le nom n, d~ultime de nd. est un nom direct de d. Le nom n est donc de la forme d1:d et son champ Information rendu et résultat vaut d. mécanisme accéder~donnée2 (nd :nom) :donnée2 recherche-représentant(nd) # n m valeur~d2 [n.information] # résultat Le contenu de la cellule référencée par le nom représentant de nd est rendu en résultat. Le nom nd désigne un élément d des données2. Le nom n, d~ultime de nd, est un nom direct de d. Il cite donc une cellule au format valeur~d2 dont le contenu, rendu en résultat. vaut d. mécanisme accéder~gauche( nc nom ) nom recherchereprésentant(nc) ^ rc m gauche [ rc.informationj ^ n recherchereprésentant(n) - résultat Le résultat est le nom représentant du nom trouvé dans le champ gauche de la cellule référencée par le nom représentant de nc. Le nom nc désigne un terme construit cona(tg,td). Le nom rc, d~ultime de nc, est un nom direct de cons(tg.td), il cite donc une cellule au format constructeur. Le résultat. ultime du nom n contenu dans le champ gauche de cette cellule. désigne tg. De plus ce nom est. un nom direct de ig. ce qui permet d'affirmer que après une commande réduire ou reprendre la désignation D ne comporte que des noms directs. mécanisme accéder~droite( nc nom ) nom recherche~représentant(nc) m droite [rc.information] - n recherche~représentant(n) $ résultat Le fonctionnement est identique à celul de la commande accéder~gauche. Il est Illustré sur la figure 15. mécanisme tester nature( n nom ) :marquedenature recherche~représentant(n) # rn rn.Indicateur # résultat Le nom n désigne un terme t. Le nom rn. d~ultime de n, est un nom direct de t. Son champ indicateur, rendu en résultat. donne la nature de t. mécanisme comparer( ni.n2 nom ) :marque~de~comparaison recherche~représentant(ni) rnl recherche~représentant (n2) # rn2 si rnl = rn2 alors égal - résultat sinonsi rn1. indicateur t rn2.1ndicateur alors différent - résultat sinon I cas rn1,indicateur I d2 alors I m valeur~d2[rn1.information] #d1 I m valeur-d2[rn2.information[ #d2 I i si dl=d2 alors égal ^ résultat sinon différent - résultat I niv alors I m état~géniteur [rn1. information m I ni étaLgéniteur [ rn2.informationJ - eg2 I I s .niveau = eg2.niveau alors égal ^ résultat sinon différent - résultat I cl.c2 alors indécis - résultat I vl.v2.di alors différent - résultat Les noms n1 et n2 désignent deux termes ti et t2. Les noms rnl et rn2. dultimes de n1 et ns, sont des noms directs de ti et ts. Si rn1 est égal à rn2. ti est égal à t2 car un nom désigne au plus un terme. Les marques de rnl et rn2 sont sIgnificatives de la nature des termes ti et t2.Si ces marques sont différentes les termes sont donc nécessairement différents. Si les marques sont égales à d2. les termes sont des données2 dont les valeurs sont Inscrites dans les cellules au format valeur~d2 citées par rn1 et rn2. Le résultat est celui de la comparaison de ces valeurs. Si les marques sont égales à niv, les termes sont des niveaux dont les valeurs sont inscrites dans les champs niveau des cellules au format géniteur citées par rn1 et rn2. Le résultat est celui de la comparaison de ces valeurs. SI les marques sont égales à cl ou c2. les termes sont des termes construits dont la comparaison nécessiterait un parcours de cellules couteux et non désiré dans les applications visées. La machine répond non~décidé dans ce cas. Enfin les seuls cas restants pour les marques sont v1, v2 et dl: dans les cas vl ou v2, rnl et rn2 sont deux noms directs différents de variables et les variables sont différentes car un élément des variables n'est représenté que par une seule cellule. Dans le cas d1, rnl et rn2 sont deux noms directs différents de données et ces données sont différents car leurs valeurs sont les champs Informatlon de rnl et rn2. mécanisme sauvegarder( nl,n2.n3 nom ) recherche~représentant(n1) # nn1 recherche~représentant(n2) - nn2 recherche~représentant(n3) # nn3 recherche~gen~représentant(géniteur~courant) # g1 m nni,nn2.nn3 &num;; nom~1~2~3[g1] allocation~call~géniteur # g2 m état~géniteur [g1] # eg1 actif. (eg1. niveau+1) # eg2 m eg2 # état~géniteur [g2] m géniteur~courant # précédent [g2] g2 - géniteur~courant Les noms représentants de n'i,n2,n3 sont sauvegardés dans le géniteur actif représentant de géniteur~courant. Sur la figure 16. il est en C12. Un nouveau géniteur est créé, son niveau est supérieur d'une unité à l'ancien c'est lui que repère ensuite géniteur~courant. Avant l'exécution de la commande. le registre géniteur~courant contient la référence gc1 d'un géniteur qui correspond à la sauvegarde Savant. Après exécution, le registre géniteur~courant contient la référence g2 d'un géniteur actif. ce génituer actif est nouveau, le rôle de gt est passé de disp à Ive La référence g2 correspond à la nouvelle sauvegarde Saprès, En effet, son champ précédent contient gc1. quI correspond à Sovon'. et g1. qui est S~uitime de gal, contient dans ses champs ni. n2 ei n3 trois noms ni, nn2 et nn3 qui sont des noms directs des termes à sauvegarder. Ces noms, qui désignent ces termes dans la ilésignation D. les désignent également dans une désignation Dh. ou k est le niveau de gc1. La désignation De est compatible avec l'état de la mémoire selon la relation t-représentation grace à l'inscription systématique de la référence du géniteur courant dans le champ géniteur des variables lors des commandes substItuer. La nouvelle sauvegarde est donc déduite de l'ancienne par ajout en tête du triplet de termes désignés par les paramètres de la commande. Sa taille. k+l. est inscrite dans le champ niveau du nouveau géniteur courant référencé par sz. On remarquera que les noms inscrits dans les géniteurs sont des noms directs. ce qui permet d'affirmer que les désignations Dk propres à chaque niveau ne comportent que des noms directs. mécanisme reprendre : état~géniteur [géniteur~courant[ # étatg 1 recalage,sucreprise(Atatg .niveau-l) 2 i géniteur~courant # g I boucle tantque étatg.nature = coupé I I m précédenttgj ~ ng I I m mort,# # état~géniteur [g] I I m ng # g I I m état~géniteur [g] # étatg I m précédent [ g3 | géniteur~courant I m mort,# - étaLgéniteur(gJ recherche~gén~représentant (géniteur~courant) # gr m nom~1~2~3 [ gr ] - ni.n2.n3 3 d8marrage,fourn8e(g8niteurcourant. nl.n2.n3) - géniteur~courant ni,n2.n3 - résultat La strate précédente doit être reprise, pour effectuer un retour en arrière et récupérer les trois termes sauvegardés sous forme de trois noms. Sur la figure 17. ces noms sont dans le géniteur situé en C12. Un recalage est demandé en 1 pour tenir à jour les positions respectives du processus d'exécution et du processus de récupération. Ce dernier, qui traite les strates par niveaux décroissants, risque en effet d'être rattrapé par le processus d'exécution à l'occasion de reprendre. Une opération de forcage au niveau inférIeur est alors prise à son égard. En 2, tous les géniteurs de la strate en sommet de pile, c'est-à-dire d'éventuels géniteurs coupés et un actif. situés sur la figure en C10 et C18, sont mis à mort. Ceci a l'effet indirect de rendre à nouveau libres les variables qui avaient été liées pendant la strate qu'on vient d'abandonner. En effet. leur champ géniteur pointe sur ces géniteurs désormais morts, ce qui équivaut à être libre. Le processus de récupération s'occupera de son côté de normalIser la situation en notant l'indication de liberté dans la variable eile-meme. permettant ainsi, en différé, de détruire les géniteurs morts et de récupérer la place qu'ils occupent. En 3 il est tiré parti du fait que la désignation est réduite aux trois noms rendus en résultat pour déclencher éventuellement un cycle de récupération de mémoire. Ceci est identique à ce qui est réalisé par une commande réduire. Avant l'exécution de la commande, géniteur~courant contient la référence gci d'un géniteur qui correspond à la sauvegarde Savant de taille k. Savant étant différente de la sauvegardevide. le champ précédent du géniteur actif gcrl équivalent à gcl contient la référence gc2 d'un géniteur qui correspond à la soussauvegarde de Savant de taille k-1, Après exécution, le registre géniteur~courant contient gc2 et la nouvelle sauvegarde Après est donc déduite de Savant par retrait de son élément de tête.La nouvelle désignation D est la désignation Dk-l qui associe aux trols noms rendus en résultat les termes sauvegardés par le niveau k-1, Cette désignation k-i. compatible avec l'état de la mémoire selon la relation t~représentation, est rendue compatible selon la relation d~représentation en transformant tous les géniteur de niveau k en géniteurs morts. mécanisme obtenir~niveau~courant : nom niv.géniteur~courant # résultat Le résultat est la référence du géniteur courant. avec l'indicateur niv. Ceci est Illustré sur la figure 18. Ce nom désigne en effet la taille de la sauvegarde S. directement si le géniteur courant est actif, indirectement s'il est coupé. mécanisme couper( n nom ) m état~géniteur [n.information] - eg~cible m état~géniteur [géniteur~courant] -eg si eg~cible.niveau I i recalage~sur~coupure (eg~ci ble. niveau) 1 2 I I géniteur~courant # g I I boucle tantque eg.niveau > eg~cible.niveuau I I I m coupé. eg~cible niveau # état~géniteur [g] I I I m précédent[g] ≈g g I I I m état~géniteur[g] # eg Le nom n désigne un niveau, c'est-à-dire qu'il comporte la référence d'un géniteur non mort. il faut détruire les strates en haut de la pile de sauvegarde qui sont postérieures à la strate du géniteur cité.Sur la figure 19, ce géniteur est en Cii. 1 a pour rôle de traiter la situation du processus de récupération, pour le cas où il serait en cours de marquage d'une strate destinée à être détruite. En 2, le processus d'exécution met à coupé tous les géniteurs jusqu'au niveau visé exclu. et réajuste leur niveau à celui visé, qui vaut ì dans l'exemple de la figure 19. mécanisme réduire (n1, n2, n3 : nom) : recherche~représentant(n1) # nn1 recherchereprésentant(n2) - n n2 nn2 recherche~représentant(n3) # nn3 nn1,nn2,nn3 # résultat 1 démarrage~fournée (géniteur~courant,nn1,nn2,nn3) # géniteur~courant Les représentants des trois noms passés en paramètre sont rendus en résultat. Ainsi sur la figure 20 les noms cl:C3. niv:C10 et di:a sont respectivement des équlvallents directs des noms v1:CO, niv:Cl i et dl:a. Ces trois noms résument les accès dont l'utilIsateur dispose désormais dans le cadre de la désignation. Ces InformatIons sont confiées à une tentative de démarrage de fournée en 1. qui sera effective si le processus de récupération est en attente à ce moment-là Après exécution de cette commande la désignation offerte à l'utilisateur ne comporte que les trois noms directs rendus en résultat ainsi que des noms directs désignant les sous termes des termes accessibles par ces trois noms. Ceci est du à la propriété des commandes d'accès aux termes accédergaucbe et accéder~droite qui ne rendent en résultat que des noms directs. Ainsi sur la flgure 20 les noms vi:C9 et vi:C8 ont disparu de la désignation bien que les cellules C8 et C9 participent toujours à la représentation des termes désignables après exécution de la commande. D'autre part les noms tels que cl:Cl et c2:C2 qui ne participent pas à la représentation des termes désignables après exécution de la commande. ont également disparu de la désignation. mécanisme Initialiser Inítialisation~gestion~mémoire allocation~cell~géniteur - g m actif,O # état~géniteur [g] g # géniteur~courant Un géniteur est créé. il sera toujours actif et restera le plus bas dans la pile -de sauvegarde. Son niveau est O et son champ précédent est sans signification. - ANNEXE 4 RECUPERATION DE CELLULES. SYNCHRONSATION ET MISE EN OEUVRE PROCESSUS DE RECUPERATION STRUCTURE DE DONNEES LA MEMOIRE DES STATUTS D'ALLOCATION Le type d'information statut~d'allocation a pour valeurs possibles {fournée1, fournée2. disponible 1. Le processus de récupération utilise un tableau statut~alloc de mémoire de type statut~d'allocation. Ce tableau est indicé par une référence. Commentaire: A chaque cellule est associe un statut d'allocation, Si celui-ci est disponible alors la cellule est considérée comme étant inutilisées par le processus d'exécution. Les deux valeurs fournée1 et fournée2 sont les statuts d'allocation des cellules utilisées. II y a deux valeurs afin de permetire le parallélisme entre le processus d'exécution, consommateur de cellules, et le processus de récupération, productsur de cellules dispenibles. LES REGISTRES registre niveau~marquage : niveau registre géniteur~sommat : référence registre nom1, nom2, nom3 : nom registre fornées~courante : {fournée1, fournée2} Commentaire: Les registres niveau~marquage et géniteur~sommet définissent la position de la strate couramment sous marquage dans la pile do sauvegarde. Les registres nomi, nom2, nom3 définissent les trois termes conservés dans la strate. Une cellule est marquée si le contenu de son statut~d'allocation" égale celui du registre fournée~courante : On marque' une cellule en rangeant dans son statut~d'allocatIon le contenu du registre fournée~courante. RECUPERATION. PRINCIPE DES FOURNEES mécanisme récupératIon marquage : ramassage : attente~founée La récupération de mémoire se fait selon le principe des fournées. Dans le cadre d'une fournée, le processus de récupération marque les cellules accessibles puis ramasse les cellules non marquées, c'est à dire les rend disponibles à nouveau. Le principe des fournées peut être brièvement décrit ainsi: la requête demarrage~fournXe décrite plus loin découpe le temps en fournées successives. A tout Instant l'espace des cellules allouées est partîtionné en deux espaces. L'espace confirmé contient les cellules allouées depuis le début de la fournée et les cellules visitées par le marquage en cours. L'espace non confirme contient les autres cellules. En fin de marquage. toutes les cellules de l'espace non confirmé sont rendues disponibles. C'est le ramassage. Après ramassage. l'espace non confirmé est alors vide. Une nouvelle fournée de récupératIon peut commencer avec un nouvel espace confirmé vide et avec un nouvel espace non confirmé égal à l'ancien espace confirmé, il y a basculement de fournée. Le registre fournée~courante permet l'identification de l'espace confirmé. alternativement par fournée et fournée2. Parfois, le processus de récupération est interrompu en cours de marquage et forcé par le processus d'exécution à recommencer son activité après que les registres qui définIssent son travail aient été réajustés, sans qu Il y ait changement de fournée. MARQUAGE mécanisme marquage boucle tantque niveau~marquage # 0 I il marquage~terme(nom1) ; marquagejerme(nom2); marquagejerme(nom3) I sauv 12 I I d8cr8mentation,niveau,marquage I disjoint # situation~exécution Ce mécanisme a pour tache de marquer les cellules utiles à la représentatIon de l'état défini par génîteur~sommet, niveau~marquage, nomi, nom2. nom3 au moment de son lancement. Ce mécanisme traite les niveaux de la pile de sauvegarde l'un après l'autre. à partir de celui détermIné par génituer~sommet, dans l'ordre décroissant. On profite aInsi de la façon dont l'ensemble des cellules qui participent à la représentatIon des termes d'une strate recouvre partiellement l'ensemble des cellules qui participent à la reprFsentatlon- des termes des strates de niveau Inférieur, pour limiter le parcours aux cellules non déjà marquées, comme il sera précisé à l'occasIon de l'exposé du mécanisme marquage~terme. En 11 sont marquées les cellules servant à la représentatIon des termes mémorisés par le niveau. En 12 il y a passage au niveau Inférieur. Le processus d'exécution devient certainement disjolnt. mécanisme marquage~terme( nn nom ) nn # n : nulle~part # sorte~endroit ; init~pile~parcours boucle parcours I boucle 1 descente tantque n,indicateur e{v1,v2,c1,c2] I I n.information # rcell I I test~si~marquée (rcell) # m si si m = vrai alors 11 ; sortie descente I cas n.indicateur I I vi,v2 alors I I I 121 I I I I normalisation~liaison(rcell) # statut I I si statut = libre alors sortie descente I 122 I I I I liais # sorte~endroit ; rcell # rcel~endroit I I I I m liaison [rcell] # n I I I I empile (remonter, rcell) I I c1,c2 alors I I 13 I I I g~cons # sorte~endroit ; rcell # rcell~endroit I I I m gauche[rcell] ^ n I I I I empile (descendre-droite, rceit) I 2 I I cas n.indicateur I I v1, v2 alors marquage~cellule(rcell) I I d2 alors marquage~cellule(n.information) I I niv alors 20 normalisation~atome~niv(n.information. I I sorte~endroit,rcell~endroit) I boucle remontée I I dépile # drapeau,quel~faire, rcell I I si drapeau ~ pile~vide alors sortle parcours I I si quoi~faire # remonter alors sortie remontée I I marquage~cellule(rcell) I 4 I I d~cons # sorte~endroit : rceil # rcell~endroit I I m droite[rcell] ~ n I I empile (remonter rcell) Ce mécanisme parcourt les cellules qui participent à la représentation du terme désigné par nn afin de Bss marquer.Ceci consiste à parcourir un arbre. dcn: les noeuds sont constitués par les cellules portant des variables libres ou des constructeurs, et les feuilles sont constituées par les variables libres et les atomes. Le parcours est effectué en descendant prioritairement à gauche. Pour gérer ce parcours, il ost utillsé une mémoire auxiliaire fonctionnant en plle associée aux mécanismes init~pile~parcours qui inltlalise la pile et l'état vide, empile( : {remonter, descendre~droite}, :référence) qui empile les paramètres, dépile : qui rend en résultat les informations dépilées sauf si la pile est vide, auquel cas le résultat est pllel~vide. La descente à travers un noeud consiste à empiler la référence du noeud, avec l'indication de ce qu'il faudra faire à la remontée, lorsqu'on aura dépilé cette référence. Le marquage des noeuds se fait lors de la remontée. de sorte que si une cellule est marquée, alors toutes les cellules accessibles depuis cette cellule sont marquées. Cette propriété est nécessaire pour que les abandons de marquage provoqués par les mécanismes recalagesurreprlse et recalagesurcoupure puissent s'effectuer en laIssant une situation de marquage cohérente. 1 Seuls les noms de variables ou de termes construits peuvent conduire le parcours à descendre, avec empilement de la référence de la cellule correspondante. Pour ces noms, Il n'a servi å rien de se souvenir de l'endroit où se trouvait leur occurence, car elle n'aura pas à être mise à jour. il Le parcours tombe sur une cellule déjà marquée. Il ne descendra pas davantage. En effet, si une cellule est accessible dans le cadre de deux niveaux i et i tels que i Donc, à condition de parcourir les strates par niveaux décroIssants, lorsqu'on rencontre une cellule qui a déjà été marquée lors du parcours, on peut faire l'économie du parcours des cellules auxquelles elle donne accès dans le cadre du niveau sous marquage, car elles sont certainement déjà marquées. Ce phénomène est Illustré sur la figure 21. Les ensembles de cellules E1 et EO représentent respectivement les termes des strates de niveau 1 et O conservées dans les géniteurs Cil et Ci3. L'intersection de El et EO contient les cellules C5, C6 et C7 qui représentent pour le niveau 1 les termes cons1 (cons1 (b. cons1 (b,c)),a), a, cons1 (b,cons1 (b,c)), et qui représentent pour le niveau O les termes cons1 (x,y), x, y. Pour chacune de ces cellules, le terme représenté par elle au niveau 1 est une Instance du terme qu'elle représente au niveau 0. Il se peut que le processus rencontre une cellule qul est marquée non pas parce que lui-même l'a déjà marquée lors de son parcours des strates, mais parce qu'elle a été allouée récemment, c'est-a-dire au cours de la fournée courante, au processus d'exécution. Le principe de ne pas parcourir les cellules auxquelles elle donne accès reste valable. car elle conduit à des cellules dont chacune est solt nouvellement allouée, donc automatiquement marquée, solt accessible au début de la fournée, et donc destInée à subir le marquage par ailleurs. 121 Le parcours a rencontré une cellule non encore marquée, portant une variable. PrIse de décIsion s'il faut la considérer comme llbre vue du niveau sous marquage, auquel cas il faut cesser de descendre, ou bien comme liée, auquel cas le parcours traverse la liaison et continue à descendre. 122 Traversée de la liaison. Le parcours s'attaque à la valeur de liaison de la variable et descend. Ceci se traduit par l'empilement de la référence à la variable. On doit aussi mémoriser à court terme l'endroit d'occurence du nom attaqué, c'est-à-dire la référence à la variable et l'IndIcatIon qu'il s'agit d'une valeur de lIaison, pour le cas où le nom serait de type niveau, ce qui ne sera découvert qu'au tour de boucle suivant. Dans ce cas. on devra rectifier le contenu de l'endroit où le nom apparaissait, en y mettant un nouveau nom qui court-circuite les géniteurs coupés. 13 Le parcours a rencontré une cellule non encore marquée, portant un constructeur. Le parcours va descendre dans sa partie gauche, d'où l'empilement de la référence de la cellule, avec une directive qui servira, quand le parcours atteindra à nouveau cette cellule lors de la remontée, à décider de l'action à entreprendre. à savoir redescendre à droite piutôt que remonter encore. On mémorise aussi à court terme l'endroit d'occurence du nom dans la partie gauche du constructeur. pour la même raison qu'en 122, 2 Diverses actions sont entreprises, correspondant å diverses sortes de feuilles du parcours. 23 Pour un atome niveau. il faut peut-être modifier le contenu de l'endroit où il apparaît pour lui faire citer le géniteur actif représentant un géniteur coupe. Ainsi. å la fin du marquage. il ne subsistera pas de références à des géniteurs coupés non marqués. 4 Préparation pour redescendre å droite. mécanisme normalisation~liaison ref réfé-rence ) : (lia,liéaj m état~liaison [ref] - el si e1, statut=libre alors libre - résultat : sortie état~géniteur [e1.géniteur] # étatgén Si étatgén nature - mort alors I 11 m libre, # # état~liaison [ref] I libre # résultat : sortie Si étatgén, niveau > niveau~marquage alors 111 ; I libre # résultat ; sortie 2 I liée # résultat I Si étatgén, nature = coupé alors 21 I I recherche~gén~représentant(e1.génitout) I I m indécis.g2 # état~liaison [ref] Ce mécanisme décide si la variable portée par la cellule do référence roE est vue comme libre ou comme liée depuis le niveau~marquage. A cette occasion. il rectifie certaines informations dans le but de faire disparaitre les références à des géniteurs morts ou coupés pour pouvoir ensuite récupérer la mémoire qu'ils occupent. li La variable est libre dans l'absolu. On normalise la situation en ramenant cette indication dans la cellule de la variable elle-même. Ceci permet de ramasser par la suite les cellules occupées par des géniteurs morts, puisqu'il n'y aura plus de références à eux. Ceci est Illustré sur la figure 23. 111 La variable est liée. mais dans le cadre d'un niveau supérieur au niveau sous marquage: elle est donc considérée comme libre vue de ce niveau. Sa valeur de liaison n'est pas prise en consIdération. et le géniteur responsable de sa liaison n'est pas inspecté. 2 La variable est certainement liée vue du niveau sous marquage. 21 Normalisation de la référence depuis la variable au géniteur responsable de la liaison: cette référence est installée pour indiquer directement le géniteur actif correspondant au géniteur coupé. Ceci est illustré sur la figure 24. Grace à cela. au fur et à mesure que le marqueur attaque les niveaux dans l'ordre décroissant, la disparition des références aux géniteurs coupés ayant un niveau inférieur au niveau attaque permet, à la fin du traitement du niveau. de mettre à mort tous ses géniteurs coupés, et ultérieurement de les ramasser. mécanisme normalIsation~atome~niv( refg :référence, sorte~endroit : {g~cons,d~cons,liais}, rcell~endroit :référence) état~géniteur [refg] # étatgén Si étatgén.nature = coupé alors I recherche~gén~représentant (refg) # gr I cas sorte ~ endroit I g~cons alors niv.gr # gauche [rcell~endroit] I d~cons alors niv.gr # droite [rcell~endroit] I liais alors niv.gr. # liaison [rcell~endroit] rerg est la référence d'un géniteur. sorte~endroit et.rceil~endroit déterminent l'endroit ou le mécanisme range la référence du premier géniteur actif antérieur à celui qui a rerg pour référence. L'effet est Illustré sur la figure 25. mécanisme recherche~gén~représentant ( g : référence) : référence g # g1 m état~géniteur [g1] # étatgén boucle tantque étatgbn.nature = coupé I m précédent [g1] # gi I m état-géniteur [g1] - étatgén g1 # résultat Ce mécanisme rend la référence du premier géniteur actif dans la chaine de géniteurs qui débute par le géniteur passé en paramètre. mécanisme décrémentation~niveau~marquage 1 I m état~géniteur [géniteur~sommet] # étatg1 I boucle tantque étatg 1 .nature = Coupé I I m précédent [géniteur~sommet] # g1 I I m mort,# # état~géniteur [géniteur~sommet] I I g1 - géniteur~sommet I I m état~géniteur [géniteur~sommet] # étatg1 2 marquage~génituer (géniteur-sommet) 3 I niveau~marquage - 1 # niveau-marquage I si niveau~marquage # 0 alors I I 31 I I I géniteur~sommet - anté~g I I I m précédent [anté~g] # géniteur~sommet I I I recherche-gén~représentant(géniteur~sommet) # g I I 32 I I I m g # précédent [ant-g] I I I m g nom~1~2~3[g] # nom1,nom2,nom3 La figure 22 illustre la réorganisation d chainage des géniteurs et l'installation des registres qui définissent la nouvelle strate à marquer, lors du passage à un niveau Inférieur. t Mise à mort des éventuels géniteurs coupés qui participent au niveau qui vient d'être marqué, jusqu'à rencontre du premier génteur actif, et marquage de ce dernier. Sur la figure. il est en C15. 3 Passage au niveau inférieur. A cette occasion, on peut détecter que la pile est épuisée. 31 Recherche du premier géniteur actif du niveau Inférieur. Sur la figure, il est en C 18 32 Décrochage de la chaîne des éventuels géniteurs coupés qui aboutît su géniteur actif trouve. RAMASSAGE mécanisme ramassage O # ref boucle tantque ref I révision~statut~cellule (ref) I ref+1 # ref Ce mécanisme parcourt toutes ies cellules pour rendre disponibles celles qui portent encore la marque de la fournée précédente, ce qui est le signe qu'elles sont devenues inaccessibles à l'utilisateur et donc récupérables. MECANISMES CRITIQUES ET SYNCHRONISATIONS Dans cette partle sont décrits les mécanismes qui accèdent aux mémoires partagées par les deux processus. Les phases critiques sont protégées par des verrous d'exclusion. déclarés sous les rubriques verrou. Les interactions se font par l'intermédIaire de conditions. déclarées sous les rubriques condition. MODIFICATIONS DE LA PILE DE SAUVEGARDE PAR LE PROCESSUS D'EXECUTION registre situation~exécution : {tangent, disjoint} verrou sauv Le registre sItuatIon~exécutIon sert à décider entre l'abandon ou la poursuite du marquage d'une strate détruite par une coupure. Lorsque la strate en cours de marquage a été, à un moment de son marquage, de même nIveau que le géniteur courant, les processus sont dits tangents. Sinon Ils sont dits 'disjoints' Dans le cas tangent, le processus de récupération ne peut pas abandonner, sous l'effet d'une coupure. le marquage de la strate en cours. En effet. dans ce cas, toutes les cellules accessibles depuis la strate sous marquage peuvent, au moment du passage à tangent, éventuellement partIciper à la désIgnatIon courante. En conséquence elles doivent toutes être marquées. mécanisme recalage~sur~reprise (niv~visé :niveau) sauv I si niv~visé # niveau~marquage alors 1 I I si niv~visé I I I suspension récupération I I I décrémentation~niveau~marquage recommencement récupératIon I I 12 tangent e sItuation~exécutIon Ce mécanisme est Illustré par la figure 26. 1 Le recalage n'est effectlf que si le niveau repris est Inférieur ou égal au nIveau en cours de marquage. Dans ce cas des mesures sont à prendre pour assurer la cohérence des vlslons de la représentatIon de la part des deux processus. 11 Si le niveau cible de la reprise est strictement Inférieur au nlveau sous marquage. la strate en cours de marquage est détruite pour le processus d'exécutIon. Le processus de récupératIon est forcé à abandonner le marquage en cours et à entreprendre le marquage du niveau Inférieur. 12 Dans le cas précédent ainsi que dans le cas où le nIveau clble de la reprise est simplement égal au niveau sous marquage les deux processus deviennent tangents. En effet la strate qui est maintenant marquée est dans les deux cas reprlse au titre de la désignation. mécanisme recalage~sur~coupure (niv~cible :niveau sauv si niveau~marquage > niv~cible alors i I T suspension récupération I cas situation~exécution I disjoint alors il I I boucle tantque niveau~marquage # niv~cible I I I décrémentation~niveau~marquage I I recommencement récupération I tangent alors 12 I I géniteur~sommet # g ; m état~géniteur [g] # egg I I I si egg.nature = actif alors vide e indic~liste~décrochée sinon sinon I I I non~vide # indic~liste~décrochée I I I I boucle tantque egg.nature = coupé I I I I rn coupé,niv~cible I I I I I g # anté~décroché I I I I I m précédent [g] > g ; m état~géniteur [g] # egg I I I marquage~cell~géniteur(g) : g # I I I boucle tantque, egg. niveau > niv~cible I I I I I I I I m précédent[g] # g ; m état~génigeur [g] # egg I I I I sI -egg.nature = coupé alors I I I I I cas indic~liste~décrochée I I I I I vide alors I I I I I I g + géniteur~sommet I I I I I I non~vide # indic~ilste~décrochée I I I I I non~vide alors m g # précédent [anté~décroché] I I I I I boucle lantque egg.nature = coupé I I I I I I m coupé,niv~cible # état~géniteur [g] I I I I I I g - anté~décroché I I I I I I m précédent [g] # g ; m êtat~géniteur [g] - egg I I I I m g # précédent [anté~g] I I I I marquage~cell~génlteur(g) : g # anté~g I I I niv~cible # niveau~marquage I I I continuation récupération Ce mécanisme est Illustré par la figure 27. 1 Des mesures sont A prendre si la coupure détruit la strate en cours de marquage et éventuellement des strates non encore marquées. 11 Dans le cas où les processus sont dIsjoInts. le marquage en cours est abandonné et le processus de récupération est forcé à entreprendre le marquage de la strate juste Inférieure à celles détruItes par la coupure. 12 Dans le cas où les processus sont tangents. le marquage de la strate en cours ne peut pas être abandonné. Cependant pour donner au processus d'exécutIon une vislon réelle de la liste des géniteurs cohérente avec sa vision logique, les géniteurs coupés de la niveau supérieur ou égal au niveau cible de la coupure et datant d'avant le début de la fournée sont décrochés de cette liste. SYNCHRONISATION POUR LE FONCTIONNEMENT PAR FOURNEES registre récupération~en~attente : {vrai faux} verrou fournée condition proposition~fournée mécanisme diemarrago~fournsee( g1 référence, ni ,n2,n3 nom ) ::référence fournée I cas récupération~en~attente I faux alors 1 g1 - résultat I vrai alors 2 I I 21 I I I cas fournée~courante I I I fournée1 alors fournée2 # fournée~courante I I I fournée2 alors fournée - fournée~courante I I m état~géniteur [g1] # egg) I I 22 I I I g1 # géniteur~sommet I I I egg1,niveau # niveau~marquage I I I ni , noml: n2 t nom2: n3 - nom3 I I 23 I I I recherche~gén~représentant (g1) # g2 I I I g2 , résultat I 24 I I I tangent # situation~exécution I I I recommencement récupération 1 Si le processus de récupération n'est pas en attente, le mécanisme est ineffectif. 2 Si le processus de récupération est en attente. le démarrage d'une nouvelle fournée est effectif. 21 Inversion de la marque de fournée. 22 InitialisatIon des registres définissant le premier niveau à marquer. 23 La référence du géniteur actif représentant de si est rendue en résultat. En effet les géniteurs coupés présents dans la pile de sauvegarde au début d'une fournée seront mis à mort et les cellules qu'ils occupaient récupérées à la fln de cette fournée. Logiquement. vue du processus d'exécution, la liste des géniteurs ne comporte plus que les géniteurs actifs. La chaine d'éventuels géniteurs coupés qui appartiennent à la strate qui va subir le marquage n'est plus connue que du marqueur, par le registre géniteur~sommet. 24 Lancement du processus de récupération au début de son mécanisme. il y a tangence car la liste des sauvegardes vues par ce processus contient des informations utiles à la représentation de la désignation par le processus d'exécution. mécanIsme attentejournée fournée I vrai e récupération~en~attente I attente proposition~fournée GESTION DE L'ALLOCATION DES CELLULES registre consommateur~attend~cellute : {vral verrou alloc condition cellule~disponible mécanisme allocation~cellule :référence alloc I boucle # # recherche~cellute # r.m # # si m # trouvé alors 12 # # # vral # consommateur~attend~cellul # # # attente cellute~disponible # # sinon faux # consommateur~attend~cellule : sortie # 2 fournée~coruante 3 statut~alloc[r] I r . résultat recherche~cellule est un mécanisme non décrit qui permet d'obtenir la référence d'uno cellule disponible s'il en existe, ou la marque non~trouvé s'll n'en existe pas. 12 S'll n'existe pas de cellule au statut dIsponIble. le processus d'exécution attend. Le prochain ramassage pourra le libérer de son attente. 2 La cellule rendue en résultat est marquée. niéeanisme révlsion~statut~collulet r :référene ). alloc # statut~alloc[r] # a # s# a # fournée~courante et a 3 disponible alors # # restitution~cellale(a) # # disponible # statut~alloc[r] # # si consommatour~atend~cellule = vrai alors signal collule~dispenible restitution~cellule est un mécanisme non décrit qui met à jour la gestion du stock des cellules disponibles: il est le symétrique de rcherche~cellule. mécanisme marquage~cellule( r :réiérence ) alloc fournée~courant # statut~alloc[r] mécanisme marquage~cell~géniteur( r :référeaoe ) Ce mécanisme, analogue à marquage~celluls n'est pas décrit, pour ne pas entrer dans les détails sur la façon dont un génlieur est réparti sur plusieurs cellules. mécanisme test~si~marquée( r :référence ) :{vral,faun} alloc # statut~alloc[r] # a # si a = fournée~courante alors vrai # résultat # sinon faux # résultat MISE EN OEUVRE A BASE DE DEUX PROCESSEURS La machine est mise en oeuvre sur un système comportant deux processeurs: -le "processeur d'exécution' supporte les mécanismes non critiques du processus d'exécutIon, ainsi que le processus utilisateur qui sollicite les commandes, -le 'processeur de gestion de mémoire" supporte la totalité des mécanismes du processus de récupératlon, ainsi que les mécanismes critiques du processus d'exécution:: allocatIon~cellule, démarrage~fournée, recalagesurreprIse et recalagesurcoupuoe. STRUCTURE DE LA MACHINE L'architecture de la machine est Illustrée sur la figure 2. La "mémoire princIpale" est le réservoir des cellules de mémoire allouées dynamlquement. L'accès se fait au niveau de la demi-cellule, unité dans laquelle se cadrent bien les divers types d'information à conserver. Le nombre de cellules. peut attendre un million. une configuration normale étant de l'ordre de 128K. Leur largeur est de 48 blts. Le temps d'accès à une deml-cellule est de l'ordre de 400 ns. Elle peut être construite à base de circuits 4164 de la société Intel. Le 'processeur d'exécution", en Interaction avec le processeur de gestion de mémoIre. Interprète les commandes du répertoIre. Pour obtenir da bonnes performances, c'est un processeur micro-programmé. Une utilisation partIculIère de la machine, par exemple pour réalIser un interpréteur PROLOG, est réalisée par l'adlonction de micro-programmes complémentaîres et de mémoires spécIalIsées, locales au processeur. Ce processeur peut être construit à l'alde de microprocesseurs en tranches de la série 2900 fournis par la socIété Advanced MIcro Device. Le temps d'exécution d'une micro-instruction est de l'ordre de 150 ns. Le "processeur de gestion de mémoire' assure la récupération des cellules de mémoire devenues Inaccessibles à l'utIlIsateur. Ce processeur est responsable de la gestion du statut courant d'allocation des cellules conservé dans la mémoire des statuts d'allocation, à laquelle lul-seul accède. Il traite les requêtes émises par le processeur d'exécution, Ce processeur est de même technologie que le processeur d'exécutIon. Il dispose d'une mémoire privée de 16K mots pour contenir une pile, nécessaire à sa logique de fonctionnement La 'mémoIre des statuts d'allocatIon' comporte autant d'éléments que la mémoire principale a de cellules. Chaque élément code sur deux bits le statut d'allocation courant de la cellule qui lui correspond. Le temps d'accès à cette mémoire est de l'ordre de 100 ns. Elle pourra être construite à base de boîtiers Am9128-10 de la société Advanced MIcro Device. Le "bus mémoire' réalise et arbitre, les accès des deux processeurs à la mémolre prlncipale. Ce mécanisme est classIque et peut être réalisé à l'aide des circuits développés par la socIété Intel pour le controle de son bus standard MULTIBUS. Le "bus de requêtes' assure l'échange d'information et la synchronisation entre les deux processeurs lors de certaines phases de leur activité afin que l'information contenue dans la machine reste globalement cohérente. Il consiste en quelques registres et des moyens d'échange de signaux. REALISATION DES SYNCHRONISATIONS Deux dispositifs matériels permettent de réaliser les synchronisations mentionnées dans les mécanismes précédemment décrits; ce sont - un système de requêtes mis en oeuvre grace au bus de requêtes. - l'accès exclusif à la mémoire des cellules mis en oeuvre par le bus mémoire. LE SYSTEME DE REQUETES Le système de requêtes est un dispositif asymétrique qui permet au processeur d'exécution de forcer le processeur de gestion de mémoire à exécuter un mécanisme indiqué. Ceci permet d'une part d'accéder aux registres qui sont localisés sur le processeur de gestion de mémoire, et d'autre part assure l'exclusIon avec le processus de récupération qui est interrompu le temps de l'exécution de la requête. Le processeur d'exécution émet une requête en af-ichant sur le bus de requêtes l'identIfIcation du mécanisme à exgouter, accompagnée de ses paramètres. Le processeur d'exécution attend alors l'acquIttement de la requête, accompagné des résultats affichées sur le bus de requêtes. Le processeur de gestion de mémoire dispose de deux niveau; d'exécution des Instructions: le niveau "de fonda et le niveau requête'. Dourt opérations permettent de passer explicitement d'un niveau à l'autre: -I'opération d"Invalidation" des requêtes pour passer au niveau requête. -l'opération de "validation' des requêtes pour passer au niveau do fond. Quand le processeur est au niveau de fond, lors de la réception d'une requête, il sauvegarde son état de contrôle, passe automatiquement au niveau requête et exécute le mécanisme Indiqué par la requête avec les paramAtres lournis. Quand le processeur est au niveau requête, si une requête est reçue, elle n'est pas prise en compte immédiatement. Elle est mémorisée et sera prise en compte dès que le processeur repassera au niveau de fond. Lors du traitement d'une requête, l'opératIon d"acquittement" débloque le processeur d'exécution en affichant les résultats sur le bus de requêtes. l'opération fin de requête" rétablît l'état de contrôle sauvegardé à la réception de la requête et fait repasser au niveau de fond, l'opération de 'forçage détruit l'état de contrôle sauvegardé et provoque la poursuite de l'exécution en niveau de fond en un point de contrôle indiqué. ACCES EXCLUSIF A LA MEMOIRE Les deux processeurs accèdent à la mémoire de façon identique. Il n'y a qu'un seul bus d'accès à la mémoire et tous les accès sont donc séquentiels. Si un processeur demande un accès pendant que le bus est Occupé à servir l'autre processeur. le premier processeur attend la fin du service en cours pour réaliser son accès. En cas de demandes simultanées, ce qui est assez probable car les deux processeurs sont finement synchrones pour des raisons de rapidIté des échanges, le système de priorité cablé favorise le processeur d'exécution. Le service exclusif du bus mémoire peut être demandé pour un accès élémentaire unique ou pour une séquence quelconque d'accès. Dans ce dernier cas. le premier accès de la séquence est accompagné d'un- ordre au bus mémolre de maintenir l'exclusion entre les accès ultérieurs. et le dernier accès de la séquence est accompagné d'un ordre de relacher l'exclusion après cet accès. Pour assurer l'exclusion d'accès à la mémoire de la part du processus de récupération, le processeur de gestion de mémoire réalise automatiquement l'invalidatIon des requêtes pendant qu'il est dans une séquence d'accès exclusif à la mémoire. Pour éviter les Interblocages, le processeur d'exécution ne doit pas émettre de requête alors qu'il détient l'accès exclusif du bus mémoire, On constate que les mécanismes décrits respectent cette contrainte. MISE EN OEUVRE DES DIVERSES SYNCHRONISATIONS LOGIQUES Les interactions entre le processus d'exécution et le processus de récupération ont été décrites à l'aide de dIsposItifs de synchronisation purement logiques: - verrous d'exclusion: m, seul. attoc, fournie - conditions d'attente: cellule~diaponib/e, propoeifion,fourn8e - actions sur un processus: suspension, continuation. recommencement. Ces dispositifs logiques ont permis de décrire la réalisation en limitant le moins possible la dIversité des architectures matérielles possibles. Dans le cas de l'architecture présentée la tache de fond du processeur de gestion de mémoire correspond au processus de récupératIon. Les dispositifs logiques de synchronlsation sont réalisés comme suit à l'aide des dispositifs matériels dont disposent les processeurs. Le verrou m est directement réalisé par le maintient et le relachement de l'exclusion d'accès à la mémoire. Les verrous sauv, alloc et fournée sont réalisés par le sytème de requêtes. Ces verrous sont sollicites à l'occasion de certains mécanismes du processus d'exécutIon: recaIagesurreprise, recaiagesurcoupure. allocationcellule, démarragefournée. Ces mécanismes sont exécutés par requêtes sur le processeur de gestion de mémoire. Ceci permet, outre l'exclusion naturellement offerte par le système de requêtes. de profiter de la localité d'accès aux registres et à la mémoire des statuts d'allocation nécessaires à l'exécution de ces mécanismes. La pratique de ces verrous par le processus de récupération est simplement réalisée par les opérations d'invalidation et de validation des requêtes sur le processeur de gestion de mémoire. La réalisation se comporte donc comme si ces trois verrous étaient le même. On salit que du point de vue logique on peut toujours transformer plusieurs verrous d'exclusion en un seul. Cependant. pour des raison d efficacité. il serait préférable que le verrou avec, qui est sollIcIté à chaque allocation de cellule, soit différencié. Cela serait possible avec un système de requêtes à plusieurs niveaux. le niveau le plus prioritaire étant utilisé pour les allocations de cellule. La condition cellule~disponible est attendue par le processus d'exécution, à l'occasion du mécanisme aIlocationcellule qui est exécuté par requête sur le processeur de gestion de mémoire. Cette attente est réalisée en terminant la requête d'allocation par une simple fin de requête, sans acquittement de la requête. Le signalement de cette condition par le processus de récupération a lieu lorsqu il est en -phase de ramassage et se traduit par un acquittement retardé de cette requête. La condition proposition~fournée est attendue par le processus de récupération. Cette attente est réalisée par une boucle vide exécutée au niveau de fond sur le processeur de gestion de mémoire. Les actions de suspension, continuation et recommencement ne portent que sur le processus do récupéraqtion. Elles sont causées par les mécanismes rocalage~sur~reprice et recalage~sur~coupure qui sont exécutés au niveau requête sur le processeur de gestion de mémoire. La suspension est automatiquement réalisée par la prise en compte de la requête. La cOntinuatiOn est réalisée par l'opération de fin de requête qui restaure l'état de contrôle @auvegardé au début de la requête. Le recommencement est réalisé par une o,seraiion de forçage avec pour point de contrôle le début du mécantsme do récupération, Revendications. 1. Machine de traitement de l'information, destinée à recevoir un logiciel propre à l'interprétation d'un langage de programmation logique, et comprenant des moyens de traitement (10) et des moyens de mémoire vive (12) interconnectés par un bus (13), caractérisée - en ce que les moyens de mémoire vive (12) comprennent une mémoire formant pile de géniteurs, ordonnée en fonction d'un nombre entier ou niveau, et une mémoire de désignation, constituée de cellules adressables individuellement, à deux champs au moins chacune, chaque champ étant destiné à contenir une information qui est soit un atome ou donnée, soit une référence à une autre cellule, soit une référence à l'un des géniteurs, - un géniteur constituant le point de départ d'un treillis de termes, en contenant lui-même l'une au moins desdites informations, le treillis de termes pouvant se prolonger par des références successives entre cellules de la mémoire de désignation, - les cellules ainsi référencées étant soit de type constructeur, leurs champs contenant alors immédiatement chacun l'une desdites informations, soit de type variable, étant mises en attente d'une liaison ultérieure, lors de laquelle les deux champs d'une cellule serviront l'un à associer la variable à l'un des géniteurs, et l'autre à contenir l'une desdites informations, et - en ce que les moyens de traitement (10) comprennent un processeur d'exécution microprogrammé (10) susceptible d'etre associé directement ou indirectement à un organe programmable destiné à recevoir le logiciel d'interprétation, ce proces seur d'exécution comprenant en outre un registre de géniteur courant, qui fait référence à l'un des géniteurs de la méi moire formant pile, l'état courant de la machine étant ainsi défini par le contenu de ce registre ainsi que par le contenu de la mémoire de désignation et de la mémoire formant pile de géniteurs. 2. Machine selon la revendication 1, caractérisée en ce que le processeur d ' exécution (10) est microprogrammé avec un jeu d'instructions comprenant - la construction d'un terme à partir de deux autres, - la création d'une variable, - la substitution d'un terme 8 une variable, - l'accès à la partie droite d'un terme construit; - 3. 'acce's à la parti gauche d'un terme construit, - des tests pour de terminer Si un terme est un atome, un terme construit ou une variable, - la comparaison de deux termes autres que construits, - la sauvegarde d'un terme, la reprise d'un terme, et - 1' initialisation 3.Machine selon la revendication 2, caractérisée en ce que le processeur d'exécution (10) est microprogrammé pour effectuer aussi les instructions suivantes - obtenir le niveau courant, - exécuter une coupure. 4. Machine selon l'une des revendications 1 à 3, caractérisée en ce que, dans la mémoire de désignation (14), une cellule de type constructeur comporte un champ de gauche et un champ de droite, utilisés de la meme manière, et comprenant chacun une zone d'indicateur et une zone dtin- formation, cette dernière étant propre à contenir une information de l'un des types précités, tandis que la zone dindi- cateur associée précise s'il s'agit d'un atome,d'une référence à une cellule-constructeur, d'une référence à une cellule-variable ou d'une référence à un géniteur, une cellule de type variable comporte une zone de statut de liaison, propre à contenir 'libre' tant que la variable demeure libre, ou 'indécis' lorsque la variable est devenue liée, une zone de référence à un géniteur associé, et une zone de liaison propre à définir une liaison de cette variable, en recevant une information de l'un des types précités ainsi qu'une indication correspondante, comme définie cidessus. 5. Machine selon l'une des revendications 1 à 4, caractérisée en ce que la mémoire formant pile de géniteurs (14) est agencée pour permettre trois formats différents quant aux éléments de la pile, ces trois formats comprenant tous un champ 'nature' en tête, avec pour un format dit géniteur actif', un champ 'nature' contenant la marque 'actif', un champ 'niveau' qui contient un nombre entier, un champ 'précédent' qui contient une référence à un autre géniteur défini par son rang et au moins un champ 'nom' qui contient un nom, qui contient l'une desdites informations, pour un format dit 'géniteur coupé', le champ 'nature' qui contient la marque 'coupé', ainsi qu'un champ 'niveau' et un champ 'précédent' définis comme pour un géniteur actif, et pour un format dit 'géniteur mort, le seul champ 'nature' qui contient la marque 'mort'. 6. Machine selon l'une des revendications 1 à 5, caractérisée en ce que la mémoire formant pile de géniteurs (14) est construite à partir de cellules de taille identique à celle de la mémoire de désignation, les formats 'géniteur coupé' et 'géniteur mort' occupant une seule cellule de mémoire, tandis que le format 'géniteur actif' est obtenu par enchainement de plusieurs cellules de mémoire. 7. Machine selon la revendication 6, caractérisée en ce que les cellules de la mémoire vive comprennent deux parties de 24 bits chacune, séparables chacune en un champ de 4 bits et un champ de 20 bits. 8. Machine selon l'une des revendications 1 à 7, caractérisée en ce que le processeur d'exécution (10) est microprogrammé avec une instruction 'réduire', destinée à permettre la récupération, dans les moyens de mémoire vive, des parties de celleci qui contiennent des informations devenues inutiles. 9. Machine selon la revendication 8, caractérisée en ce que les moyens de traitement sont aussi agencés pourra'une part répondre à des demandes d'allocation de cellules-de mémoire, en allouant des cellules de mémoire disponibles, et d'autre part répondre à une demande spécifique consécutive à la commande 'réduire' en effectuant une récupération automatique des cellules contenant des informations devenues inutiles. 10. Machine selon la revendication 9, caractérisée en ce que les moyens de traitement comprennent un processeur de gestion de mémoire (12) séparé qui possède un registre 'attente cellule', propre à contenir une marque 'vrai' ou 'faux', et un registre 'situation de l'exécuteur' qui contient l'une des deux marques 'tangent' ou 'disjoint' suivant l'état du processeur d'exécution relativement au processeur de gestion de mémoire, les deux processeurs dialoguant par requêtes, et en ce que la machine comporte un mécanisme d'accès exclusif à la mémoire permettant une exclusion mutuelle entre les deux processeurs. 11. Machine selon l'une des revendications 9 et 10, caractérisée en ce que les moyens de traitement (32) effectuent la récupération automatique de la manière suivante - exploration d'une partie au moins des treillis de cellules définis par le contenu des moyens de mémoire vive, et utiles au processseur d'exécution, en y marquant les cellules en fonction de conditions prédéterminées, - et ensuite ramassage des cellules non marquées, qui sont maintenant considérées comme libres. 12. Machine selon la revendication 11, caractérisée en ce qu'une mémoire de statuts d'allocation (15) est associée au processeur de gestion de mémoire (12), cette mémoire de statuts d'allocation (15) comprenant un nombre d'éléments au moins égal à celui des cellules de la mémoire de désignation (14), chacun de ces éléments étant susceptible d'états différents comprenant un état libre, et un état marqué au moins, en ce que le processeur de gestion de mémoire (12) effectue le marquage des cellules de la mémoire (14) par une inscription dans l'élément correspondant de cette mémoire de statuts d'allocation, et en ce que le processeur de gestion de mémoire (12) effectue le ramassage par une exploration complète de cette mémoire de statuts d'allocation (lus), tout en faisant passer ses éléments non marqués à l'état libre. 13. Machine selon la revendication 12, caractérisée en ce que chaque élément de la mémoire de statuts d'allocation (15) comporte trois états différents, c'est-à-dire l'état libre, ainsi qu'un premier et un second états non libres, définissant respectivement l'affectation de la cellule correspondante des moyens de mémoire vive dans une première et une seconde fournées, et en ce que le processeur de gestion de mémoire (12) effectue alternativement la récupération de mémoires sur les cellules de la première. et de la seconde fournées, le marquage consistant à inverser l'affectation de fournée des cellules, on inversant l'état non libre de L'éLément associé dans la mémoire de statuts d'allocation, et le ramassage consistant à faire passer à l'état libre les éléments de la mémoire de statuts d'allocation qui ont conservé la marque qu'elles avaient au début de cette fournée. 14. Machine selon la revendication 13, caractérisée en ce que la mémoire de statuts d'allocation (15) comporte, en correspondance bi-univoque, autant d'éléments qu'il y a de cellules dans les moyens de mémoire vive. 15. Machine selon la revendication 14, caractérisée en ce que le processeur de gestion de mémoire possède en outre les registres suivants j géniteur sommet' qui contient une 'référence', 'fournée courante' qui contient une des deux marques 'allouée première fournée' ou 'allouée seconde fournée', 'niveau sous marquage' qui contient un nombre entier, 'nom sous marquage' qui contient au moins un nom, et en ce que le processeur de gestion est propre à répondre à une requête 'démarrer une fournée' émanant du processeur d'exécution à la suite d'une instruction 'réduire', ladite requête étant accompagnée de la référence d'un 'géniteur' et de celle d'au moins un 'nom', représentant l'état courant du.processeur d'exécution, en effectuant les opérations suivantes - ranger la référence de ce géniteur dans le registre 'géniteur sommet', - inverser la marque contenue dans le registre 'fournée courante', - ranger le niveau du nouveau 'géniteur sommet' dans le registre 'niveau sous marquage', - ranger le nom dans le registre 'nom sous marquage', - puis en procédant au marquage du terme défini par le registre 'nom sous marquage', ledit marquage concernant, pour un terme construit, non seulement la cellule 'constructeur' de ce terme, mais aussi les cellules désignées par celle-ci, répétitivement s'il s'agit à nouveau de termes construits. 16. Machine selon l'une des revendications 13 à 15, caractérisée en ce que ledit marquage comporte, pour une cellule du genre variable liée, une normalisation de la liaison,avec: - un test pour déterminer si la variable est libre ou si le géniteur de la variable est mort, auquel cas la variable est mise au statut 'libre', et le résultat de la normalisation est 'libre', - sinon, le remplacement du géniteur de la variable par son géniteur représentant, la comparaison du niveau de ce géni teur représentant maintenant associé à cette variable au contenu du registre 'niveau sous marquage', en cas de supérioriorité du premier, la normalisation de la liaison de la variable à 'libre'. en cas d'infériorité ou d'égalité, la normalisation de la liaison de la variable à 'liée' et la réitération du marquage avec le résultat de la liaison ainsi normalisée de la variable. 17. Machine selon la revendication 16, caractérisée en ce que la recherche du géniteur représentant comprend la recherche du premier géniteur actif rencontré à partir du champ 'précédent' du géniteur en cours d'examen, le géni teur représentant étant ce géniteur actif. 18. Machine selon l'une des revendications 13 à 17, caracté risée en ce qu'après achèvement des marquages précités, les moyens de traitement (12) produisent - une exploration de la pile des géniteurs à partir du géni teur sommet, .jusqu'au premier géniteur actif, en transformant en géniteurs morts les géniteurs coupés rencontrés en cours de route, et un marquage dudit premier géniteur actif rencontré, lequel est maintenant réservé, - l'inscription de ce champ 'précédent' dans le registre 'géniteur sommet', en remplacement du contenu antérieur de celui-ci, - la continuation de l'exploration de la pile des géniteurs jusqu'au second géniteur actif, représentant le nouveau géniteur sommet, - l'inscription de la référence du géniteur représentant ,dans le champ 'précédent' du premier géniteur actif qui vient d'être marqué, et - l'inscription de son ou ses champs 'nom' dans le registre 'nom sous marquage'. 19. Machine selon l'une des revendications 13 à 18, caractérisée en ce qu'en présence d'une requête d'allocation de cellules lors du ramassage, le processeur de gestion de mémoire (12) alloue une cellule ayant conservé la marque de la fournée en cours, tout en inversant cette marque, au lieu de faire passer cette cellule à l'état libre. 20. Machine selon l'une des revendications 11 à 19, caractérisée en ce que le quatrième état de la mémoire des statuts d'allocation (15) identifie des cellules non soumises à l'action du processeur de gestion de mémoire (12).