Brevet FR2439432A1 — publié le 19800516

L'invention concerne une structure de machine APL (A Programming Languagej. Un programme écrit en APL se caractérise par sa concision et sa clarté. Cela tient, d'une part, à la puissance des opérateurs de traitement de tableaux et, d'autre part, à la mise en valeur des principes de l'algorithme programmé. Cela confère à l'APL un caractère universel et le support conversationnel du langage APL rend très simple et très rapide l'écriture, la mise au point d'un programme et sa mémorisation. Cependant, l'inconvénient de 1'APL réside dans le fait que son exécution, dans tous les ordinateurs actuels où il est réalisé, est très lente, ce qui limite son domaine dtapplir cation, notamment dans le cas de gestion conversationnelle. La présente invention a notamment pour but de remédier à ces inconvénients et concerne, à cet effet, une structure de machine APL tA Programming Language) comportant un traducteur pour traduire en un langage intermédiaire compact le programme APL créé par l'utilisateur ; un interpréteur pour lire et analyser le langage intermédiaire par un analyseur syntaxique et l'exécuter par un exécuteur, structure caractérisée en ce que l'interpréteur est réalisé en mettant en oeuvre une seule table de variable locale par fonction APL et que les tables des fonctions appelantes ne sont pas accessibles dans les fonctions appelées et en ce que la traduction remplace toute référence à une variable APL créée par l'utilisateur par une syllabe de langage intermédiaire comportant l'indication de ce qu'elle est locale ou globale et l'indice de cette variable soit dans la table des globales, soit dans la table des locales de la fonction où figure cette variable APL. Suivant une autre caractéristique de l'invention, le codage des syllabes de langage intermédiaire est effectué par le traducteur sur deux octets au maximum. Suivant une autre caractéristique de l'invention, l'analyseur syntaxique de l'interpréteur est constitué par un automate à trois états. L'invention est représentée, à titre d'exemple non limitatif, sur les dessins ci-joints, dans lesquels - la figure 1 représente l'état de la structure de contrôle après interprétation de Moy K, - la figure 2 représente le diagramme de transitions d'états de l'analyseur syntaxique de l'interpréteur. L'objectif étant de réaliser une machine la plus rapide possible à l'exécution, on a été amené à charger la phase de "traduction" (qui produit le langage intermédiaire) et à utiliser une structure mémoire adaptée, de façon à ce qu'aucune recherche de symboles en table ne soit plus nécessaire au moment de l'exécution. Ce choix différencie l'objet de l'invention de la plupart des réalisations APL existantes (qui, par exemple, à chaque référence à un identificateur lors de ltexécutions nécessite la recherche séquentielle en table de ce symbole). Par ailleurs, on a voulu faire un interpréteur assez simple à réaliser, donc utilisant des structures simples (cette machine n'utilisera que deux piles, l'une pour l'interprétation des expressions APL, l'autre pour l'enchainement de l'appel et du retour d'une fonction). Cet interpréteur nécessite une mémoire secondaire à accès direct (disquette). La machine APL comprendra donc deux parties - l'une sans impératif de vitesse : le traducteur, mis en oeuvre à chaque fois qu'une fonction APL ou qu'une ligne APL en mode "calculateur" est créée, ou bien encore par l'opérateur "exécution" f . Le traducteur transforme les constantes en représentation interne, crée les tables de symboles et de fonction et réalise la traduction des lignes APL en langage intermédiaire en effectuant certaines simplifications liées au regroupement des opérateurs (fonctions cumul, produits internes et externes). - l'autre qui doit être aussi rapide que possible l'interpréteur avec deux étapes successives, l'analyseur syntaxique qui reconnatt la nature syntaxique des identificateurs, variable ou fonction', traduit les expressions et appelle 1' "exécuteur" ; celui-ci exécute effectivement les opérations reconnues et empilées par l'analyseur syntaxique. L'implémentation d'APL suivant l'invention est caractérisée par la suppression de toute recherche (séquentielle ou dichotomique) dans des tables de symboles dans la phase interprétation. Une variable globale ou fonction (reconnue par le traducteur parce que le symbole ne figure pas dans la liste des variables locales) est traduit en une syllabe "globale" du LI (langage intermédiaire) avec un index dans la table des symboles globaux. De même, une variable locale reconnue par le traducteur est traduite en une syllabe "locale" avec un index dans la table des symboles de la fonction. Pour accéder, à l'exécution, une variable locale, on utilise le pointeur vers le début de la table des symboles locaux de la fonction en cours et cet index. On obtient ainsi l'adresse du descripteur de la variable. L'adresse d'un descripteur local, global ou d'un paramètre est donc obtenue avec seulement un décalage (indexation) et une addition virgule fixe. La contrepartie de cette accélération de l'exécution est l'alourdissement de la phase traduction, mais qui est non critique. La figure 1 illustre la structure de contrôle. On observera plus particulièrement le pointeur vers le paramètre formel Y de la fonction MOY, établi par l'interpréteur au moyen de cette structure - obtention du pointeur vers la table des symboles locaux de MOY par indexation de la table des globales, - sauvegarde de celui-ci dans le champ "t TABLE DES SYMBOLES LOCAUX de la fonction appelée" de l'entrée courant de la PAL pointée par PPAL, - adressage du champ Y par indexation de la table des symboles locaux de MOY et valorisation avec un pointeur vers le paramètre droit (qui vaut K). Ce même pointeur est copié dans le champ "t DESCRIPTEUR PARAMETRE DROIT" de l'entrée courant de la PAL pointée par PPAL. Les conséquences de la structure adoptée sur les performances de la machine APL sont les suivantes Modification de la première ligne d'une fonction Il faut explorer le LI de la fonction, pour vérifier s'il nty a pas de variables globales devenues locales et réciproquement et modifier les index des syllabes en conséquence. Copie d'une fonction d'un autre espace de travail Cette fonction stockée sous forme de LI, doit etre "décompilée" pour reconstituer le texte source en utilisant les tables de l'ES origine, puis retraduite en utilisant les tables de l'ES destination. Effacement d'une fonction de l'ES L'ensemble du LI de la fonction doit être parcouru pour reconnaltre toutes les références à des variables globales et pour chacune diminuer de 1 le compteur de référence dans la table des symboles globaux, Ce compteur était incrémenté de 1 par le traducteur pour toute référence à l'intérieur d'une fonction (la référence à une globale en mode calculateur ne modifie pas ce compteur). Ce compteur est utilisé, pour l'effacement d'une variable. Si le compteur n'est pas Or seul le champ DESCRIPTEUR dans la table des symboles globaux est mis à zéro, occasionnant une VALEUR ERREUR en cas de référence. Si ce compteur est à 0, l'entrée dans la table des symboles (gérées par "trous") est remise à disposition. Création d'une fonction Toute globale, considérée comme telle par le traducteur, parce qu'elle ne figure pas dans la liste des locales, est considérée à priori comme ayant le type "variable", si elle n'existe pas déjà avec le type "fonction" dans la table des symboles globaux. Quand une fonction est créée et si son nom figure déjà dans la table des globales, le type est modifié en fonction. Le tableau de la figure 1 do a structure mémoire correspondant à deux fonctions APL, au moment où vient de se terminer la traduction de MOY K et où l'interprétation a été déclenchée et a réalisé l'empilage des paramètres. Cinématique d'appel des fonctions La cinématique d'appel des fonctions est repérée par une pile d'appels de fonctions (PAL) qui contient les pointeurs vers les paramètres de la fonction appelée, un pointeur vers la dernière syllabe interprétée dans la fonction appelante, le pointeur vers la table des symboles locaux de la fonction appelée et le numéro de ligne de la fonction appelant. Décompilation du langage intermédiaire Les identificateurs du texte source ne figurent pas dans la représentation en LI : en effet, ceux-ci ne sont nécessaires que pour l'instruction O SI donnant la liste des appels de fonctions empilées, et pour éditer une fonction. Dans l'implémentation suivant l'invention, les identificateurs stockés dans la table globale et dans autant que nécessaire de tables locales ne sont pas en mémoire principale, mais sur mémoire à disque. Laide sert à accéder un identificateur dans une table donnée. Domaine des variables locales Les variables locales d'une fonction, repérées par un index propre à cette fonction, ne sont accessibles que dans cette fonction et pas dans les fonctions appelées, sauf si, la fonction s'appelle elle-meme. L'implémentation adaptée permet les appels récursifs. Les variables locales sont purgées au retour de la fonction où elles étaient définies. Traitement des appels et des retours de fonction La solution adoptée permet de ne pas avoir de différence syntaxique au niveau du LI entre un paramètre formel et une variable locale (qui sont adressés par un index dans la table des symboles locaux). La possibilité offerte de récursivité, c'est-à-dire que F1-- > F2 ou bien F1-- F3-- > F1, nécessite d'avoir les champs # DESCRIPTEUR PARAMETRE DROIT et GAUCHE dans le PAL, ainsi qu'un traitement approprié des appels et retours de fonction. Lors de l'appel d'une fonction les pointeurs vers les paramètres gauche et droit de la table des symboles locaux doivent être valorisés et copiés dans la PAL. Lors d'un retour de fonction, les pointeurs doivent être restaurés à partir des t DESCRIPTEUR PARAMETRE de la PAL qui servaient de sauvegarde. Ceci pour traiter le cas pour F1 F2#F1, du retour au premier appel de F1 dont les pointeurs de paramètres pointent alors vers ceux du deuxième appel de F1. Gestion mémoire de la machine APL Une place fixe sera allouée pour une table de symboles globaux puisqu'il existe une fonction système dans l'APL SV qui permet de la modifier. Par contre, toutes les autres tables pourront être implantées dans un endroit quelconque. Des champs "chaînage avant" et "chaînage arrière" devront être ajoutés aux différentes lignes de la PAL de façon à pouvoir éventuellement utiliser tout l'espace disponible. Etiquettes Les étiquettes sont des éléments syntaxiques considérés comme des variables locales. Pour chacune, le traducteur crée un descripteur. Ceci entrain qu'il n'y a aucune différence de traitement entre une variable locale numérique et une étiquette (en particulier E2#2,3l est valide mais l'exécution de iE2 causerait une erreur ; ceci diffère dans d'autres implémentations). Nous générons une syllabe de LI pour une étiquette dans le seul but de pouvoir recompiler le texte source. Concernant l'analyseur syntaxique de LI de l'interpréteur, on assigne à cet analyseur syntaxique, en plus de sa fonction d'analyse du LIS le rôle de préparer les actions sémantiques, c'est-à-dire l'exécution des opérateurs, de façon à ce que leur interface soit identique quelle que soit l'origine des opérandes (variable, constante, résultat). Au début de l'action sémantique, l'opérateur ou l'index de la fonction se trouve dans un registre OPR, et les opérandes éventuels dans le Registre Droit (RD) et le Registre Gauche (RG). Le fonctionnement complet de l'analyseur syntaxique est décrit ci-dessous par un diagramme de transition à quatre états. Il est nécessaire de considérer quatre états si l'on veut que chaque action sémantique ne dépende que des opérandes et de l'opérateur Etat O initial Etat 1 opérande trouvé et celui-ci n'est pas le résultat d'une affectation (AF = 1) Etat 1' opérande trouvé et celui-ci est le résul tat d'une affectation (AF = 0) Etat 2 opérateur ou fonction trouvé La séparation de l'état "opérande trouvé" en deux est nécessaire pour le traitement "context-free" de l'opération fin de ligne (FL) ou l'étiquette (s) qui déclenche ou non l'impression du registre RD, suivant que celui-ci n'est pas ou est le résultat d'une affection. On peut remarquer qu'il n'est pas possible avec cet analyseur syntaxique d'interpréter les opérateurs du type / RV) ] ou \li311 . En effet, cela nécessiterait une complexité accrue de l'analyseur avec quatre états en plus. Cette restriction n'est pas gênante en gestion où la plupart des matrices n'ont que deux dimensions et peuvent etre traitées avec les opérateurs / ou 8 opérant sur la première et la dernière coordonnée. Il est à noter que le partage entre fonctions réalisées par l'analyseur et fonctions réalisées par l'action sémantique des opérateurs est arbitraire. Nous avons choisi de charger davantage l'analyseur syntaxique car cela amène une économie de programmes et une plus grande standardisation des interfaces des opérateurs. Concernant l'analyse de l'expression algébrique, la machine APL comprend 1 registre opérateur ou index fonction ..,., OPR 1 registre opérande droit .s RD 1 registre opérande gauche o. RG Les deux registres contiennent l'adresse d'un descripteur (scalaire, vecteur, matrice, variable indicée). - RG contient 0, si l'opérateur ou la fonction est monadique. - RG et RD contiennent 0, si l'opération est niladique. 1 pile opérande-opérateur contenant des opérandes (adresse du descripteur) ou des opérateurs. L'analyse syntaxique crée l'expression en notation polonaise inverse. L'exemple ci-dessous explique son fonctionnement : NOP est l'opérateur "nul" correspondant à l'initialisation de OPR et O est l'opérande nul correspondant à l'initialisation de RD et RG. Concernant le diagramme de transition d'états, l'analyseur syntaxique de l'interpréteur (voir figure 2), il convient de noter les explications ci-après qui sont nécessaires pour en comprendre le fonctionnement Action RANGE Se reportant à la définition d'un opérande, on voit qu'il peut avoir les types : variables, constantes, fonction niladique ou variable système. Pour les deux premiers types, l'action RANGE consiste à ranger l'adresse du descripteur dans RD ou RG suivant le cas. Pour une variable système, l'opération RANGE fait appel à la fonction système et range le pointeur vers le résultat (scalaire, vecteur ou matrice) dans RD ou RG suivant le cas. Pour une fonction niladique, l'opération RANGE l'exécute et met l'adresse de son résultat dans RD ou RG suivant le cas. Cette fonction de l'analyseur syntaxique permet de traiter tous les types d'opérandes d'une façon homogène. Erreurs L'exécution d'une fonction monadique ou dyadique retourne dans l'état 1. Si la fonction nta pas de résultat, alors RD sera à O et toute expression utilisant ce résultat occasionne une VALEUR ERREUR. Certains contrôles syntaxiques sont laissés au niveau de l'exécution des opérateurs. Par exemple, l'opérateur D'autres controles (pas de parenthèse ouvrante, pas de constante) peuvent être faits au niveau du traducteur. Exécution des fonctions Dans le cas d'une fonction monadique ou dyadique, lté,tat de retour est toujours l'état 1 et lors du lancement d!une telle fonction, il n'est pas besoin de préserver le contenu des registres OPR, RD ou RG. REVENDICATIONS 1) Structure de machine APL tA Programming Language) comportant . un traducteur pour traduire en un langage intermédiaire compact le programme APL créé par l'utilisateur ; un interpréteur pour lire et analyser le langage intermédiaire par un analyseur syntaxique et l'exécuter par un exécuteur, structure caractérisée en ce que l'înterpréteur est réalisé en mettant en oeuvre une seule table de variable locale par fonction APL et que les tables des fonctions appelantes ne sont pas accessibles dans les fonctions appelées et en ce que le traducteur remplace toute référence à une variable APL créée par l'utilisateur par une syllabe de langage intermédiaire comportant l'indication de ce qu'elle est locale ou globale et l'indice de cette variable soit dans la table des globales soit dans la table des locales de la fonction où figure cette variable APL. 2) Structure conforme à la revendication I, caractérisée en ce que le codage des syllabes de langage intermédiaire est effectué par le traducteur sur deux octets au maximum. 3) Structure conforme à la revendication 1, caractérisée en ce que l'analyseur syntaxique de l'interpréteur est constitué par un automate à trois états.