# Interpréteur apl optimisé

Gérard Battarel, Dimitri Tusera, M. Delbreil

► To cite this version:

Gérard Battarel, Dimitri Tusera, M. Delbreil. Interpréteur apl optimisé. [Rapport de recherche] IRIA-RR-032, IRIA. 1973, pp.92. hal-04715923

HAL Id: hal-04715923

https://inria.hal.science/hal-04715923v1

Submitted on 1 Oct 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>
IRIA
laboria

laboratoire de recherche
en informatique
et automatique

Interpréteur APL optimisé

G.Battarel

M.Delbreil

D.Tusera

<figure><img src="image_2.png" /></figure>

Institut de Recherche
d'Informatique
et d'Automatique

Domaine de Voluceau
Rocquencourt
78150 - Le Chesnay
Tél. 954.90.20

Rapport de Recherche n°32

octobre 1973
# UN INTERPRÉTEUR APL OPTIMISE

G. Battarel, M. Delbreil, D. Tusera

(conseil A. Marchal)

## RÉSUMÉ

On trouvera, dans ce papier, la description de spécifications pour un interpréteur APL utilisant la méthode définie par A. Marchal, laquelle minimise l'allocation dynamique de mémoire, et réduit le nombre de calculs.

Cet interpréteur a été conçu, et est actuellement développé, comme un outil permettant une évaluation, des extensions et des améliorations, et servira de base à la définition d'un système complet.

## ABSTRACT

The purpose of this paper is to describe the specifications of an APL interpreter based on a method defined by A. Marchal, which minimizes dynamic storage allocation and reduces the number of value computations.

The interpreter has been designed and is presently implemented as a tool which will support evaluation, extensions and improvements, and will be the basis for the design of a complete APL system.
TABLE DES MATIERES
====================

1 - Objectifs

2 - Principe de la méthode

3 - Organisation générale

A. Organisation générale du programme "INTERPRETEUR"

B. Organisation générale de la mémoire de travail

4 - Description des zones de mémoire

A. Encodage de la source

B. Table des symboles

C. Descripteur de fonction

D. Descripteur des données et des expressions

E. Représentation de données.

5 - Analyse lexicale

6 - Processus de pseudoevaluation

A. Pile d'état d'interpreteur

B. Exemple de pseudoévaluation

C. Aglrophme d'analyse syntaxique et de pseudoévaluation

7 - Processus d'évaluation (G E T V A L )

8 - Mode définition de fonction

9 - Gestion de mémoire de travail

10 - Estimation des perfomances

A. Précision de calcul

B. Volume de code de programme "INTERPRETEUR"

C. Limitation des zones de mémoire de travail

11 - Conclusion

12 - Bibliographie

Annexes : 
A- Exemple d'application de la méthode d'interprétation
B- Code de certaines procédures de l'interpréteur en LPS
C- Code interne des symboles APL
# CHAPITRE I. OBJECTIFS

Le présent rapport se propose de définir un interpréteur du langage APL d'après les travaux qui ont été menés par M.A. MARCHAL à l'Université de UTAH (USA).

Les spécifications de cet interpréteur ont été définies, en collaboration avec M. MARCHAL, par MM. G. BATTAREL, M. DELBREIL et D. TUSERA, du LABORIA.

L'interpréteur qui est défini dans les pages qui vont suivre constitue une étape préparatoire à la définition d'un système opérationnel et doit donc être considéré comme un outil, expérimental, susceptible de modifications et de développements au cours du temps. Dans cette optique, le contexte temps partagé et les problèmes relatifs à la mise sous un système déterminé n'ont pas été envisagés dans ce premier temps.

Les spécifications internes sont données pour tout ce qui concerne la partie purement interprétation du langage.

Des opérateurs fondamentaux, représentatifs de toutes les catégories d'opérateurs du langage, sont explicitement traités, mais l'interpréteur est en mesure d'accepter la totalité des opérateurs APL existant à ce jour.

En ce qui concerne les fonctions annexes, telles que mise au point, éditions, ... seules les spécifications extérieures sont fournies. Cependant l'interpréteur a été conçu pour pouvoir les admettre sans aucune modification. De plus, dans ces fonctions annexes, toutes les possibilités fournies par le système APL 360 ont été envisagées (à l'exception des fonctions de communication avec le système ou entre utilisateurs).
# CHAPITRE II - Principes de la méthode.

Les principes de la méthode suivant laquelle fonctionne l'interpréteur qui va être décrit ont été définis par A. MARCHAL [13]. Nous nous bornerons ici à en rappeler les grandes lignes.

Le mode de fonctionnement classique d'un interpréteur consiste à effectuer un calcul dès qu'un opérateur et ses opérandes ont été reconnus par l'interpréteur. Cette méthode, appliquée à un langage de manipulation de tableaux, tel APL, conduit l'interpréteur à effectuer des calculs superflus et à demander de l'espace mémoire en surabondance.

Afin de rendre plus efficace le traitement des tableaux, l'exécution n'est pas effectuée de façon immédiate ; l'interprétation se fait en deux phases, correspondant à deux processeurs indépendants.

La première phase, dite de pseudoévaluation, suit l'analyse lexicale. Elle transforme l'expression source APL en une représentation interne sous forme de liste, dans laquelle un noeud correspond à un opérande (noeud terminal) ou à un opérateur (noeud non terminal), un arc traduisant la relation "opérande de". Durant cette phase, les valeurs des opérandes sont ignorées ; seules sont prises en compte les informations concernant leur structure et la structure de l'expression (analyse syntaxique, tests de conformité des opérandes).

Les accès aux valeurs et les calculs ne sont effectués que durant la seconde phase, d'exécution.

Une procédure récursive, GETVAL, parcourt le graphe créé par la pseudo-évaluation. Un parcours de l'arbre à partir du sommet détermine quels éléments des tableaux opérandes sont nécessaires au calcul. Le parcours en sens inverse combine ces éléments par les opérateurs mémorisés aux noeuds non terminaux.

Deux options sont possibles à ce niveau : l'une minimise l'espace mémoire dynamique au prix d'un temps d'interprétation plus long ; l'autre permet de gagner non sur l'espace, mais sur le temps. Dans ce qui suit, seule la première option est développée.

Cependant, les deux options sont compatibles et pourraient coexister dans l'interpréteur ; l'utilisateur aurait alors la possibilité de choisir le facteur - temps ou espace - sur lequel il veut être performant.
Le schéma général du noyau de l'interpréteur est représenté par la figure ci-dessous :

<figure><img src="image_3.png" /></figure>

L'Annexe A présente une étude détaillée de la méthode sur un exemple concret.
# CHAPITRE III. ORGANISATION GENERALE

## A. Le programme "INTERPRETEUR"

D'une manière générale, l'entrée des instructions se fait soit depuis une console, soit depuis un périphérique quelconque (lecteur de cartes, dérouleur,...) Dans tous les cas, la source subit un premier codage qui la fait passer dans une représentation interne (cf Annexe : CØD). Dans le cas d'une ligne en provenance de la console, ce prétraitement comprend la suppression des backspaces et le traitement des redéfinitions après interruption.

Dans le cas d'une ligne de commentaires (Ier caractère = A), en cours de définition d'une fonction, le commentaire est transformé en donnée, référencée par le descripteur des codes de la fonction courante, et l'on passe à la ligne suivante (voir mode définition de fonction Ch VIII).

Lorsque les informations proviennent d'un périphérique différent, le problème des backspaces ne se pose pas ; il est remplacé par le transcodage depuis le code de représentation sur le périphérique en code interne CØD. S'il s'agit d'une ligne de commentaires, aucun transcodage n'a lieu.

La phase préliminaire conduit à charger dans un buffer BUF la représentation interne de la ligne source à interpréter.

Le sort de cette ligne dépend d'une part, du premier caractère de cette ligne, d'autre part de l'état de l'interpréteur lors de son arrivée. Cet état est indiqué par la pile d'état de l'interpréteur, dont on trouvera la description en VI-A.

Au moment où une ligne source doit être analysée, les états possibles de l'interpréteur sont :

LD : définition de ligne : cet état est l'état de repos de l'interpréteur

FD : définition de procédure

DI : définition d'une entrée de donnée sur demande de l'utilisateur ( [ ] ou [] ).

Selon cet état, et en fonction du premier caractère de la ligne on se trouvera soit dans un cas d'erreur, soit on passera dans un état correspondant à l'activation d'un module déterminé de l'interpréteur.

Le tableau 1 résume toutes les situations possibles, il donne, pour chacune d'elles, le nouvel état de l'interpréteur.

Le code 0 correspond à un cas d'erreur.
<table><thead><tr><th>ETAT<br>Premier<br>Caractère</th><th>LD</th><th>FD</th><th>DI</th></tr></thead><tbody><tr><td>)</td><td>SC</td><td>O</td><td>O</td></tr><tr><td>∇</td><td>HD</td><td>LD</td><td>D</td></tr><tr><td>[</td><td>O</td><td>FD</td><td>O</td></tr><tr><td>TΔ</td><td>TΔ</td><td>O</td><td>O</td></tr><tr><td>SΔ</td><td>SΔ</td><td>O</td><td>O</td></tr><tr><td>→</td><td>ST</td><td>FD</td><td>O</td></tr><tr><td>Autre</td><td>LE</td><td>FD</td><td>DI</td></tr></tbody></table>

Ie Caractère = ' ) '

Il s'agit d'une commande système : celle-ci n'est autorisée qu'en mode
définition de ligne (LD). Cette commande est analysée, puis exécutée par
un module particulier. Elle conduit à l'impression d'un message. L'inter-
préteur repasse ensuite en mode LD.

le Caractère = ' ∇ '

Ce caractère traduit l'ouverture ou la fermeture d'une définition de
procédure, selon que le mode courant est définition de ligne ou définition
de procédure.

Si le mode était LD, on passe au mode HD, qui correspond à la défini-
tion de l'en-tête d'une procédure. Celle-ci est analysée par un module parti-
culier défini au chapitre VIII-F.

Si le mode était FD, la définition de procédure est terminée ; ou repas-
se au mode définition de ligne, par le processus décrit en VIII-D. La
ligne doit, dans ce cas, se borner au caractère ' ∇ '.

Ier caractère = ' [ '

Il s'agit d'une commande de mise au point ; celle-ci n'est autorisé
qu'en mode définition de fonction. L'analyse et l'exécution des commandes
de mise au point est décrite au chapitre VIII.

Iers caractères = 'TΔ ou SΔ'.
Il s'agit d'une commande particulière affectant la valeur du trace vector ($TΔ$) ou du stop vector ($SΔ$) d'une fonction. On passe alors dans un mode $TΔ$ ou $SΔ$ particulier. Les actions qui sont alors prises consistent à vérifier que $TΔ$ (ou $SΔ$) est suivi du nom d'une fonction déjà définie, et de la flèche d'affectation.

Le reste de la ligne est alors analysé, puis exécuté comme en mode LD.

Après exécution, le trace (ou stop) vector de la fonction concernée est mis à jour, compte tenu du mode ($TΔ$ ou $SΔ$) ; l'interpréteur repasse ensuite à l'état définition de ligne.

### Ier caractère 'V'

Si l'état est FD, 'V' indique un branchement : on reste donc dans le mode définition de fonction.

Si l'état est LD, il s'agit d'une commande à la pile d'état : on passe alors dans l'état particulier ST, dans lequel la commande est analysé puis exécutée.

### Le caractère est autre :

Il s'agit du cas, le plus général, d'une ligne exécutable. Dans tous les cas, la ligne subit l'analyse lexicale définie au chapitre V.

Si l'état était FD (définition de fonction), à la fin de l'analyse lexicale se pose le problème de la demande de la ligne suivante, ou du repassage en mode définition de ligne, décrits au chapitre VIII, D et E.

Si le mode est LD, on passe en mode exécution de ligne (LE). Ceci comprend deux phases.

- pseudo évaluation décrite au chapitre VI.

- exécution décrite en VII.Durant la pseudo évaluation, l'appel de procédures conduit à empiler sur la pile des états des articles indiquant l'état FE (exécution de fonction). Les actions prises lors de l'appel d'une fonction et après l'exécution de cette fonction sont décrites dans le chapitre VI.

Si l'état était DI, il s'agit d'une entrée de donnée, qui est considéré comme un appel de procédure particulière. L'état DI ne se distingue de l'état FD que par le fait que, dans cet état, ou ne peut trouver qu'une expression exécutable ; les fonctions de mise au point, définitions de procédures et commande sytème sont interdites dans cet état. D'autre part, le résultat de l'exécution de cette ligne est utilisé par la ligne appelante, comme lors d'un appel de procédure.
L'ensemble de la mémoire contient des informations nécessaires à l'interpréteur lui-même, et des informations pour l'utilisateur (programme et données).

Les informations du premier type sont rangées dans les zones suivantes :

- **pile d'état de l'interpréteur** : Elle renseigne sur le mode de fonctionnement, la fonction éventuellement en cours d'exécution, l'adresse du code source correspondant à la ligne courante, les adresses des descripteurs des opérandes impliqués dans les calculs en cours, etc...

- la **table des symboles** permet de faire le lien entre le nom externe d'une variable (chaîne de caractères) et l'adresse de son descripteur.
Tout identificateur qui a été introduit dans l'espace de travail y est représenté. Le descripteur qu'elle référence peut être un **descripteur de données ou d'expression**, ou un **descripteur de fonction**, ou ne pas exister lorsque la nature de l'identificateur n'a pas encore été définie.

Les informations relatives à l'utilisateur sont les suivantes :

- les **descripteurs de fonction** (1 par fonction) qui renseignent sur le type d'une fonction, et permettent d'accéder aux variables locales de cette fonction dans la table des symboles, à ses étiquettes par l'intermédiaire d'une **table des étiquettes**, et aux lignes de code source qui la composent par l'intermédiaire de la **table des lignes** ; celle-ci contient les adresses auxquelles on trouve la **source précodée**.

- les **descripteurs de données ou d'expressions** constituent la représentation intermédiaire de la source, sur laquelle s'effectue l'évaluation ; ils contiennent essentiellement une référence vers le **vecteur taille** d'un tableau ou d'une expression, et une référence vers les **données** des tableaux calculés.

Les différentes zones de mémoire correspondant à ces différents types d'information sont décrites plus en détail au chapître IV.
Synoptique d'organisation de la mémoire

<figure><img src="image_4.png" /></figure>
# CHAPITRE IV. DESCRIPTION DES ZONES DE MEMOIRE.

Avant de décrire le processus d'interprétation, nous présentons la description des zones mémoire qui seront manipulées durant ce processus.

Celles-ci sont introduites dans l'ordre dans lequel elles apparaissent au cours de l'interprétation, depuis l'entrée d'une ligne APL jusqu'à son exécution.

On décrira successivement :

- l'encodage de la source, représentation d'une ligne après l'analyse lexicale.

- la table des symboles, son organisation, et l'algorithme d'accès à un élément.

- le descripteur de fonction, et les zones qu'il référence.

- les descripteurs des données et des expressions, qui constituent l'élément caractéristique de la méthode présentée.

- les données elles-mêmes.

## IV-A ENCODAGE DE LA SOURCE PRECODEE.

La source précodée résulte de l'analyse lexicale des expressions exécutables. Celle-ci a pour rôle de créer, en mémoire, une zone (CDS) constituée d'un article de tête qui donne certaines caractéristiques de la ligne utiles à l'enchaînement de l'exécution des lignes, et d'articles représentant l'expression proprement dite, sous une forme plus condensée et plus maniable que la source.

### L'article de tête :

Il indique la longueur effective de la ligne sous forme précodée (en demi-mots), le nombre d'étiquettes de cette ligne (LB), le fait que le trace ou le stop vecteur ont été positionnés pour la ligne ($TΔ$ et $SΔ$), le fait qu'il s'agit ou non d'une ligne de commentaires (C), d'une ligne de branchement (B), ou de la dernière ligne d'une procédure (E).

<table><thead><tr><th>0</th><th>8</th><th>16</th><th>24</th><th>32</th></tr></thead><tbody><tr><td>LG</td><td>LB</td><td></td><td>TΔ</td><td>SΔ</td></tr><tr><td></td><td></td><td></td><td>B</td><td>C</td></tr><tr><td></td><td></td><td></td><td>E</td><td></td></tr></tbody></table>

La source précodée proprement dite comporte les unités syntaxiques dans l'ordre dans lequel elles se présentent dans la source ; les étiquettes éventuellement sont donc en tête, séparées de la partie exécutable de la ligne par un article "fin d'analyse" (l'analyse syntaxique s'effectue en effet de droite à gauche).

L'ensemble de la source précodée d'une ligne se présente donc sous la
forme suivante :

<figure><img src="image_5.png" /></figure>

Les unités lexicales sont au nombre de 16, encodées sur 16 bits; à l'ex- -ception des opérateurs et littéraux qui sont sur 32 bits.

a) Littéral

<figure><img src="image_6.png" /></figure>

S'applique aux constantes scalaires ou vectorielles. DS est une référence directe vers le descripteur de la constante ( zone des noeuds- descripteurs de données).

b) Identificateur

<figure><img src="image_7.png" /></figure>

TS référence le noeud terminal de la table des symboles ; c'est au niveau de ce noeud que se fait la distinction entre tableaux et fonctions.

c) Opérateurs

<figure><img src="image_8.png" /></figure>

Chaque opérateur est encodé sur 32 bits.

On distingue trois types syntaxiques d'opérateurs :

- TY = 4 : opérateurs monadiques

- TY = 5 : " diadiques

- TY = 6 : " indéfinis

L'encodage d'un opérateur contient, en plus, des informations sur la nature de cet opérateur, qui facilitent la pseudo-évaluation.
IV-B LA TABLE DES SYMBOLES.

1- <u>Organisation.</u>

La table des symboles est organisée sous forme de listes chaînées.
Cette organisation s'applique bien à APL, dont les symboles peuvent être de lon-
-gueur quelconque, mais sont en général très courts.

Il y a 27 listes indépendantes, correspondant aux caractères alpha-
-bétiques, plus le symbole 'Δ'.

Une chaîne décrit toutes les variables commençant par le même carac-
-tère.

Chaque caractère d'un symbole est représenté par un noeud dans la
chaîne. La liste est bidirectionnelle, ce qui permet d'associer une adresse à une
chaîne de caractères, ou de retrouver cette chaîne, connaissant l'adresse.

- le noeud correspondant à un caractère est dit "fils" du noeud corres-
pondant au caractère précédent dans le symbole.

- l'ensemble des noeuds correspondant aux caractères succédant à un
caractère donné est chaîné, et constitue une "chaîne de frères". Dans une chaîne
de frères, les noeuds sont classés par ordre de caractère croissant.

- chaque contient une référence vers son "père" (relation inverse de la
relation fils).

2- <u>Différents types de noeuds.</u>

On distingue trois types de noeuds :

- les noeuds non-terminaux, ou intermédiaires, constituent un chemin d'accès vers les noeuds terminaux. Pour un symbole donné, il y a autant de noeuds intermédiaires que le symbole a de caractères. Cependant, un noeud intermédiaire peut être commun à plusieurs symboles.

Le noeud intermédiaire a le découpage suivant, sur 2 mots :

<table>
  <tr>
    <td>C</td>
    <td>PE</td>
  </tr>
  <tr>
    <td>FR</td>
    <td>FI</td>
  </tr>
</table>

- C = caractère représenté par le noeud

- PE= pointeur vers le père

- FR= " " frère suivant

- FI= " " fils
- les noeuds terminaux constituent les noms internes des symboles; il y a un noeud terminal par symbole. Ils contiennent, en plus des informations précé-dentes, des informations sémantiques sur le symbole. Leur découpage est le suivi, sur 4 mots :

<table><tr><td>RC</td><td>PE</td></tr><tr><td>FR</td><td>FI</td></tr><tr><td>PP</td><td>TY</td></tr><tr><td>DP</td><td></td></tr></table>

- la partie caractère contient toujours le caractère ' ', dernier de la chaîne composant un symbole

- PE, FR, FI ont la même signification que plus haut.

- RC est un compte de références indiquant combien de fois un même symbole a été déclaré comme variable locale.

- PP est un pointeur vers le sommet de la liste des locaux de même nom (voir plus loin, noeuds des variables locales).

- TY indique le type du symbole :

TY = 0 : indéfini

TY = 1 : groupe

TY = 2 : étiquette

TY = 3 : tableau (ou expression)

TY = 4 : fonction monadique sans résultat

TY = 5 : " diadique " "

TY = 6 : " niladique " "

TY = 7 : " monadique avec " "

TY = 8 : " diadique " "

TY = 9 : " niladique " "

- DP est une référence vers le descripteur de la donnée ou de l'expression portant le nom du symbole.

- les noeuds des variables locales et étiquettes.

Durant toute l'exécution d'une procédure, les variables locales recouvrent la signification des symboles de même nom ; cette signification doit être restituée après exécution de la procédure. Ceci implique que, en cours d'exécution, à un même nom externe de symbole correspondent des objets différents. Tous les objets de même nom sont chaînés entre eux, depuis un noeud terminal. Les noeuds correspondant aux locaux et étiquettes ont le découpage suivant, sur 3 mots :

<table><tr><td>PE</td></tr><tr><td>FI</td></tr><tr><td>DP</td></tr></table>
- PE = pointeur vers le père

- FI = pointeur vers le fils

- DP = référence vers le descripteur de donnée ou d'expression de la variable locale.

### 3- Exemple.

Liste correspondant aux symboles C, CI, CIY, C2B, C2X

<figure><img src="image_9.png" /></figure>

### 4- Organisation de la table en mémoire.

- Une zone de mémoire de taille prédéterminée est allouée aux noeuds intermédiaires. Les noeuds étant tous de la même taille, il n'y a pas de problèmes de compactage de cette zone ; on tient simplement à jour la liste des espaces disponibles.

- La même solution est adoptée pour les noeuds terminaux.

- Pour les locaux et étiquettes, en raison du caractère fugitif des noeuds qui leur sont associés, et du fait que ceux-ci peuvent proliférer lors d'ap-pels récursifs de procédures, ces noeuds sont créés dans la zone mémoire destinée aux données et expressions (cf IV-D).
5- **Organigramme de recherche dans la table des symboles.**

SYMB - chaine de caractères dans le symbole

I - indice de caractère dans le symbole

N - adresse du noeud

C - caractère représenté par le noeud.

<figure><img src="image_10.png" /></figure>
IV.C Descripteur de fonction

Il est référencé dans la table des symboles dans laquelle est indiqué, en plus, le type de la fonction (monadique, diadique, niladique, avec ou sans résultat).

Ce descripteur est considéré comme une donnée et géré comme tel:

LG - longueur du descripteur

NL - nombre de variables locales dans la fonction

R - référence vers le nom interne du résultat dans la table des symboles

AG - idem pour l'argument gauche de la fonction.

AD - idem pour l'argument droit de la fonction.

ET - Pointeur vers la table d'étiquettes

CD - pointeur vers la table des lignes de code.

L1, L2...LN - références vers les noms internes (noeuds terminaux) des variables locales de la fonction dans la table des symboles.

<table><caption>Table d'étiquettes</caption><thead><tr><th></th><th></th><th></th></tr></thead><tbody><tr><td>0</td><td>15</td><td>31</td></tr><tr><td></td><td></td><td>N</td></tr><tr><td>E1</td><td></td><td>V1</td></tr><tr><td>E2</td><td></td><td>V2</td></tr><tr><td></td><td></td><td></td></tr></tbody></table>

N - nombre d'étiquettes

E1, E2...EN - références vers les noms internes (noeuds terminaux) des étiquettes dans la table des symboles.

V1, V2,...VN - les valeurs en clair des étiquettes correspondantes.

<table><caption>Table des lignes de code.</caption><thead><tr><th></th><th></th></tr></thead><tbody><tr><td></td><td>N</td></tr><tr><td></td><td>CDS1</td></tr><tr><td></td><td>CDS2</td></tr></tbody></table>

N - nombre de lignes dans la fonction

CDS1, CDS2...CDSN - les pointeurs vers les lignes source encodées dans leur forme interne.
Le descripteur de fonction est rempli lors de l'analyse lexicale de l'en-tête d'une définition de procédure (mode HD)

La table des étiquettes est remplie au fur et à mesure de la définition des lignes de la fonction (mode FD)

La table des lignes de code est remplie au fur et à mesure de la définition de la fonction (FD). Le numéro de la ligne correspond à un index dans cette table : l'introduction de lignes intercalaires implique donc une réorganisation de cette table, ainsi que la mise à jour des valeurs des étiquettes lors de la fermeture.

Pour ces deux tables on demande un espace à priori ; on peut avoir à redemander un espace plus grand; inversement, on peut rendre l'espace en trop à la fin de la définition de la fonction (rencontre de 'D' en mode FD)

Le descripteur de fonctions est utilisé dans le prologue, l'interprétation et l'épilogue d'une fonction.

Quand une fonction est initialisée, le programme prologue (FEX) est appelé. Il utilise les références dans le descripteur de fonction vers les noms internes de toutes les variables locales (résultat, arguments, variables locales proprement dites, étiquettes) pour créer (empiler d'une façon liée) les noeuds (les entrées) de la table des symboles pour elles.

Pendant l'interprétation de la fonction le descripteur de fonction, par l'intermédiaire de la table des lignes de code, permet l'accès au code, l'enchainement des lignes et le traitement de stop ou trace mode.

A la fin de traitement d'une fonction le programme épilogue depile l'article d'état d'interprétation représentant la fonction en question, remplace dans l'article précédent de cette pile l'opérande sur son sommet par le résultat explicite de la fonction et libère les noeuds de la table des symboles créés pour les variables locales.

### IV.D. Descripteurs des données et des expressions

Les descripteurs représentent les noeuds de l'arbre résultant de la pseudo-évaluation de la source.

Nous distinguons deux types de noeuds par leur position dans l'arbre et par leur signification :

- Noeuds ou descripteurs terminaux

- Noeuds ou descripteurs nonterminaux

#### Descripteur terminal

<table><thead><tr><th>0</th><th>15</th><th>31</th></tr></thead><tbody><tr><td>CT</td><td>T</td><td>RC</td><td>CRC</td></tr><tr><td colspan="4">DV</td></tr><tr><td colspan="4">DR</td></tr></tbody></table>
C1 - indique qu'il s'agit d'un noeud terminal (scalaire ou tableau)

T - Type de donnée referencée par le descripteur (booléen, entier, flottant, caractères)

RC - Compte de références

CRC - compte cumulatif de références

DV - pointeur vers le vecteur de dimension de donnée (pour les scalaires, non utilisé)

DA - pointeur vers le vecteur de donnée.

1) Un noeud terminal peut être créé par l'analyse lexicale pour un "littéral", Dans ce cas la forme interne de code référence ce noeud, qui à son tour décrit et référence la donnée définie par le "littéral".

2) Il peut aussi être affecté à une entrée de la table des symboles au cours d'interprétation de l'opérateur '→'.

3) Un noeud non terminal devient terminal si l'interpréteur effectue sur lui la procédure de calcul des valeurs (GETVAL).

L'accès à un noeud terminal pendant la pseudoevaluation est par la forme interne de code (CDS) et par la table des symboles tandis que pendant le calcul des valeurs (GETVAL) l'accès est par la structure de l'arbre objet.

Les noeuds terminaux participent pendant la pseudoévaluation à la construction des noeuds non terminaux de l'arbre objet pendant le calcul des valeurs à l'accès aux données.

### Descripteur non terminal

A) Pour rotation, concatenation, compression, expansion, reverse et tous les opérateurs scalaires monadiques et diadiques.

<table><thead><tr><th>0</th><th>15</th><th>31</th></tr></thead><tbody><tr><td>O1</td><td>K</td><td>T</td><td>RC</td><td>CRC</td></tr><tr><td colspan="5">DV</td></tr><tr><td>OPI</td><td></td><td></td><td>OP2</td><td></td></tr></tbody></table>

C1 - code d'opération (entrée dans la table d'opérateurs)

K - index d'opération si elle indexée

T - type du résultat (booléen, entier, flottant, caractère)

RC - compte de références

CRC - compte cumulatif des références

DV - pointeur vers le vecteur de dimension du résultat
OP1 - référence vers le descripteur diadiques)

OP2 - Référence vers le descripteur de l'opérande droit.

b) pour la réduction, produit externe et produit interne

<table><thead><tr><th>0</th><th>15</th><th>31</th></tr></thead><tbody><tr><td>OP1</td><td>DU'</td><td>OP2</td></tr></tbody></table>

C1 - code opérateur

C2 - code opérateur scalaire de la réduction ou du produit externe et code opérateur droit pour le produit interne.

c) noneud spécial - opérande gauche de la réduction

<table><thead><tr><th>0</th><th>31</th></tr></thead><tbody><tr><td>IM</td><td></td></tr><tr><td>K</td><td></td></tr></tbody></table>

IM - la valeur maximale de l'index sur lequel s'effectue la réduction.

K - index (composante) suivant laquelle se fait la réduction.

Les descripteurs non terminaux sont crées au cours de la pseudoévaluation de la forme interne du code et sont liés entre eux de telle façon qu'ils forment l'image transformée de l'expression source appelée l'arbre-objet.
IV.E. REPRESENTATION DES DONNEES

<figure><img src="image_11.png" /></figure>

LG - longueur d'espace de la donnée

RC - compte de références

D1, D2, .... données rangées séquentiellement

Les données référencées par les descripteurs terminaux et non terminaux sont représentées dans la mémoire sous la forme de vecteurs.
# CHAPITRE V. ANALYSE LEXICALE

L'analyse lexicale est le premier traitement que subit une expression
source exécutable.

Elle est effectuée dès que la ligne est rentrée par l'utilisateur
 mode LD ou FD).

Cette phase a pour rôle la reconnaissance des unités syntaxiques,
la mémorisation de renseignements utiles à l'interprétation prourement dite
de la ligne et la représentation de la source sous une forme plus compacte.

L'analyse lexicale est le module qui permet de passer de la chaine
source qui se trouve dans le buffer BUF à la source précodée CDS définie
au chapitre IV-A.

Dans le buffer, la source se présente sous la forme d'un octet par
caractère source. La chaine résultante est considérée comme une donnée, et
gérée comme telle. Cette donnée est référencée, en mode définition ou exécu-
tion de ligne, par la pile d'état ; les lignes de procédures déjà définies sont
référencées par les descripteurs de ces procédures.

On ne considèrera ici que l'analyse lexicale d'une ligne à exécuter ;
l'analyse lexicale des lignes de procédures en mode définition comporte,
en plus des algorithmes définis ci-après, des actions relatives à la
mise à jour des descripteurs de fonctions, et à la demande de la ligne suivante
Ces actions particulières sont définies au chapitre VIII-E.

L'analyse lexicale explore la chaine de gauche à droite. L'automate
qui effectue la reconnaissance des unités syntaxiques peut être représenté
par la table TAB 1.

Dans cette table, une colonne correspond au symbole courant, une
ligne à un état de l'analyseur, une case à l'état suivant. Le code 1 correspond à une erreur du type 'ERREUR DE SYNTAXE' Le code 0 correspond à la reconnaissance d'une unité syntaxique, laquelle s'accompagne d'actions propres à la nature de cette unité, et est suivi par une rentrée dans la table à l'état 1.

L'analyse commence par une demande d'espace pour CDS ; la longueur
demandée peut être fonction de la longueur de la ligne à analyser, ou
systématique. Dans tous les cas, comme on ne peut prévoir exactement la place
qu'occupera la source précodée CDS, il faut demander un espace trop grand,
dont l'exédent peut être libéré à la fin de l'analyse.
<table><thead><tr><th>Symbole</th><th>U</th><th>A/2</th><th>E</th><th>oper. sauf</th><th>/</th><th>→</th><th>0</th><th>2</th><th>-</th><th>.</th><th>1</th><th>Sémn. sauf</th><th>L</th><th>V</th><th>:</th><th>□</th><th>Fin ligne</th><th>Auto</th><th>Unité reconnue</th></tr></thead><tbody><tr><td>3</td><td>1</td><td>2</td><td>3</td><td>3</td><td>4</td><td>5</td><td>6</td><td>7</td><td>8</td><td>9</td><td>4</td><td>4</td><td>4</td><td>-1</td><td>10</td><td>0</td><td>-1</td><td></td><td>Fin de ligne</td></tr><tr><td>2</td><td>2</td><td>2</td><td>2</td><td>0</td><td>0</td><td>0</td><td>2</td><td>2</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>22</td><td>0</td><td>0</td><td>-1</td><td></td><td>Identificateur</td></tr><tr><td>32</td><td>4</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>22</td><td>0</td><td>0</td><td>-1</td><td></td><td>"</td></tr><tr><td>22</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>-1</td><td>0</td><td>0</td><td>-1</td><td></td><td>Label</td></tr><tr><td>3</td><td>0</td><td>0</td><td>0</td><td>32</td><td>0</td><td>0</td><td>0</td><td>32</td><td>0</td><td>0</td><td>33</td><td>0</td><td>0</td><td>0</td><td>0</td><td>-1</td><td></td><td>Operateur</td></tr><tr><td>36</td><td>0</td><td>0</td><td>0</td><td>-1</td><td>-1</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>36</td><td>-1</td><td>-1</td><td>0</td><td>-1</td><td>-1</td><td></td><td>Operateur de réduction</td></tr><tr><td>32</td><td>-1</td><td>-1</td><td>-1</td><td>0</td><td>-1</td><td>81</td><td>82</td><td>-1</td><td>-1</td><td>-1</td><td>-1</td><td>-1</td><td>-1</td><td>-1</td><td>-1</td><td>-1</td><td>-1</td><td></td><td>Produit interne ou extrait</td></tr><tr><td>32 / 34</td><td colspan="18">Le premier symbole suivant doit être un chiffre ou un nombre et '7' est un nombre erroné</td><td>Operateur indiqué</td></tr><tr><td>4</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>Reduction indiquée</td></tr><tr><td colspan="19">Constantes</td></tr><tr><td>5</td><td>54</td><td>-1</td><td>62</td><td>0</td><td>0</td><td>4</td><td>6</td><td>6</td><td>-1</td><td>8</td><td>-1</td><td>0</td><td>0</td><td>-1</td><td>-1</td><td>0</td><td>-1</td><td></td><td>" ou '8' ou séparant</td></tr><tr><td>52</td><td>51</td><td>0</td><td>0</td><td>0</td><td>-1</td><td>54</td><td>62</td><td>-1</td><td>8</td><td>-1</td><td>0</td><td>0</td><td>0</td><td>-1</td><td>-1</td><td>0</td><td>-1</td><td></td><td>Constante braise</td></tr><tr><td>6</td><td>61</td><td>-1</td><td>62</td><td>0</td><td>0</td><td>-1</td><td>6</td><td>6</td><td>-1</td><td>8</td><td>-1</td><td>0</td><td>0</td><td>-1</td><td>-1</td><td>0</td><td>-1</td><td></td><td>"</td></tr><tr><td>62</td><td>64</td><td>0</td><td>0</td><td>0</td><td>-1</td><td>6</td><td>6</td><td>-1</td><td>8</td><td>-1</td><td>0</td><td>0</td><td>0</td><td>-1</td><td>-1</td><td>0</td><td>-1</td><td></td><td>Élément de constante entière</td></tr><tr><td>62</td><td>-1</td><td>-1</td><td>-1</td><td>-1</td><td>-1</td><td>64</td><td>64</td><td>-1</td><td>8</td><td>-1</td><td>0</td><td>0</td><td>0</td><td>-1</td><td>-1</td><td>0</td><td>-1</td><td></td><td>"</td></tr><tr><td>63</td><td>-1</td><td>-1</td><td>-1</td><td>-1</td><td>-1</td><td>64</td><td>64</td><td>-1</td><td>-1</td><td>-1</td><td>-1</td><td>-1</td><td>-1</td><td>-1</td><td>-1</td><td>-1</td><td>-1</td><td></td><td></td></tr><tr><td>63</td><td>-1</td><td>-1</td><td>-1</td><td>-1</td><td>-1</td><td>64</td><td>64</td><td>-1</td><td>-1</td><td>-1</td><td>-1</td><td>-1</td><td>-1</td><td>-1</td><td>-1</td><td>-1</td><td>-1</td><td></td><td>Élément de constante flottante</td></tr><tr><td>64</td><td>65</td><td>-1</td><td>-1</td><td>0</td><td>0</td><td>-1</td><td>64</td><td>64</td><td>-1</td><td>-1</td><td>-1</td><td>0</td><td>0</td><td>-1</td><td>-1</td><td>0</td><td>-1</td><td></td><td>"</td></tr><tr><td>65</td><td>65</td><td>0</td><td>0</td><td>0</td><td>0</td><td>-1</td><td>6</td><td>6</td><td>-1</td><td>8</td><td>-1</td><td>0</td><td>0</td><td>-1</td><td>-1</td><td>0</td><td>-1</td><td></td><td>"</td></tr><tr><td>7</td><td>-1</td><td>-1</td><td>-1</td><td>-1</td><td>-1</td><td>6</td><td>6</td><td>-1</td><td>8</td><td>-1</td><td>-1</td><td>-1</td><td>-1</td><td>-1</td><td>-1</td><td>-1</td><td>-1</td><td></td><td></td></tr><tr><td>8</td><td>-1</td><td>-1</td><td>-1</td><td>-1</td><td>-1</td><td>81</td><td>8</td><td>-1</td><td>-1</td><td>-1</td><td>-1</td><td>-1</td><td>-1</td><td>-1</td><td>-1</td><td>-1</td><td>-1</td><td></td><td></td></tr><tr><td>81</td><td>82</td><td>-1</td><td>62</td><td>0</td><td>0</td><td>-1</td><td>8</td><td>8</td><td>-1</td><td>-1</td><td>-1</td><td>0</td><td>0</td><td>-1</td><td>-1</td><td>0</td><td>-1</td><td></td><td>Élément de constante flottante</td></tr><tr><td>82</td><td>82</td><td>0</td><td>0</td><td>0</td><td>0</td><td>-1</td><td>6</td><td>6</td><td>-1</td><td>8</td><td>-1</td><td>0</td><td>0</td><td>-1</td><td>-1</td><td>0</td><td>-1</td><td></td><td>"</td></tr><tr><td>9</td><td>9</td><td>9</td><td>9</td><td>9</td><td>9</td><td>9</td><td>9</td><td>9</td><td>9</td><td>9</td><td>9</td><td>9</td><td>9</td><td>9</td><td>9</td><td>9</td><td>9</td><td></td><td></td></tr><tr><td>94</td><td>0</td><td>0</td><td>0</td><td>0</td><td>-1</td><td>-1</td><td>-1</td><td>-1</td><td>9</td><td>0</td><td>0</td><td>0</td><td>-1</td><td>-1</td><td>0</td><td>-1</td><td></td><td>Constante caractéristique</td></tr><tr><td>40</td><td>0</td><td>0</td><td>0</td><td>0</td><td>10</td><td>-1</td><td>-1</td><td>-1</td><td>-1</td><td>-1</td><td>0</td><td>0</td><td>0</td><td>-1</td><td>0</td><td>0</td><td>-1</td><td></td><td>Entrée de données</td></tr><tr><td>401</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>-1</td><td>-1</td><td>0</td><td>-1</td><td></td><td>Sortie de données</td></tr></tbody></table>

Table de l'analyse lexicale : TAB 1

En ce qui concerne les constantes, l'analyseur dispose d'un registre dans lequel se trouve le type présumé de la constante (défini par l'analyse des éléments antérieurs). Lorsqu'un élément est reconnu, ce type est modifié ou non.
Les principales unités syntaxiques sont :

- les identificateurs

- les constantes

- les opérateurs

- les séparateurs

- les demandes d'entrée / sorties de données.

# I - Les identificateurs

Le nom externe de l'identificateur est remplacé par son nom interne, qui est une référence vers un noeud terminal de la table des symboles (Voir IV - B)

Etant donnée une chaine de caractères correspondant à un identificateur, ou explore la partie noeuds non terminaux de la table qui permet, soit de découvrir le noeud terminal correspondant, qui est alors référencé par l'article de CDS, soit de s'apercevoir que cet identificateur n'a pas encore été défini ; dans ce cas, on crée de nouveaux liens dans la partie noeuds non terminaux, qui permettent d'accéder à un nouveau noeud terminal, créé avec le type indéfini. Lorsque l'identificateur est une étiquette, le compte de références du noeud est incrémenté de 1. Ceci tient au fait qu'une variable globale et une étiquette peuvent avoir même nom externe ; la suppression de l'une ne doit pas entrainer la suppression de l'autre.

# 2 - Les constantes

Les constantes peuvent être soit scalaires, soit vectorielles. L'analyse par TAB 1 permet de déceler pour les constantes :

- leur type arithmétique (booleéen, entier, flottant, caractère)

- Leur nombre d'éléments pour les vecteurs. Le passage dans un des états désignés dans TAB 1 par 5⁺, 6⁺, 7⁺ ou 8⁺ entraine le retour à l'état 5, 6, 7 ou 8 après incrémentation de 1 du nombre d'éléments. Le type arithmétique est déterminé de façon dynamique.

Une constante ayant été reconnue, on est donc en mesure de lui créer un descripteur (voir IV-D.) qui est référencé par l'article de CDS. De plus les valeurs de cette constante sont transformées en données ; cette transformation dépend du type de la constante.

# 3 - Les opérateurs

Il y a trois types syntaxiques d'opérateurs :

- monadiques

- diadiques

- indéfinis.
Les opérateurs dits indéfinis peuvent être soit monadiques, soit diadiques, en fonction du contextedans lequel ils se trouvent. Cependant, ce contexte n'étant connu qu'au moment de l'exécution, l'indétermination ne peut être levée au niveau de l'analyse lexicale : elle le sera à la pseudo-évaluation.

L'encodage du séparateur comporte, en plus du type syntaxique, le ou les codes internes de cet opérateur (un produit interne, tel que + . x, est considéré comme un opérateur unique) et, si cet opérateur est indéxé, la valeur de l'index.

Ces informations sont obtenues par consultation de la table des encodages.

## 4 - Les séparateurs

Chacun des séparateurs constitue une unité syntaxique particulière ; il est encodé conformément au code donné en IV A.

## 5 - Les demandes d'entrée - sortie

On distingue, à l'analyse lexicale, la demande d'entrée de donnée ('[]' ou '[]') qui correspond à un appel de procédure particulier de la demande de sortie ' [] ← ' ou '[] ← ' qui est une commande d'édition.
# CHAPITRE VI PROCESSUS DE PSEUDOEVALUATION

La pseudoévaluation est la partie de l'interpréteur dont la tâche consiste en la construction de l'arbre objet.

Nous décrivons d'abord la **pile d'état d'interpréteur** - le seul organe nécessaire pour ce processus, ensuite nous présentons un exemple simple de pseudoévaluation à titre d'illustration et nous concluons le chapitre par la description complète de l'algorithme de ce processus.
## VI. Pile d'état d'interpréteur (STAT)

La pile d'état d'interpréteur STAT sert à tous les états dans lesquels se peut trouver l'interpréteur.

Les états possibles sont :

* LD - définition de ligne

* LE - exécution de ligne

* HD - définition d'en-tête de fonction

* FD - exécution de fonction

* DI - entrée de donnée

* SC - commande de système

Comme dans le chapitre actuel nous traitons la pseudoévaluation, les seuls états d'interpréteur possibles ici sont :

* LE - exécution de ligne

* FE - exécution de fonction

* DI - entrée de donnée

Les autres états d'interpréteur et le rôle de STAT dans ces états sont expliqués dans les chapitres "Organisation générale de l'interpréteur" et "Mode définition de fonction".

La pile d'état d'interpréteur est constituée par des articles chainés entre eux dans la mémoire.

Chaque article de STAT consiste en deux parties :

- partie de la taille fixe

- partie de la taille variable.

### Partie de la taille fixe d'un article STAT

Elle sert pour l'enchainement des lignes et des fonctions. Elle consiste en 4 mots.

<table><thead><tr><th></th><th></th></tr></thead><tbody><tr><td>ETAT</td><td>FC</td></tr><tr><td colspan="2">CDS</td></tr><tr><td>IX</td><td>NL</td></tr><tr><td colspan="2">BL</td></tr></tbody></table>

* ETAT - exprime l'état d'interpréteur (mentionné au-dessus)

* FC - entrée de la table des symboles pour la fonction en cours

* CDS - pointeur vers la ligne de code en cours

* IX - index du symbole en cours dans la ligne de code.

* NL - numéro de la ligne en cours dans la fonction (son index dans la table des lignes de code)

* BL - pointeurs vers l'article précédent de la pile STAT.
On demande la création d'un nouvel article de STAT lors de l'appel d'une fonction. A ce moment on mémorise dans IX de l'ancien article de STAT l'emplacement du symbole dans la ligne qu'on abandonne, on crée le lien BL dans le nouvel article de STAT vers l'ancien et on initialise la fonction appelée (les détails, voir dans FEX) : l'état d'interpreteur devient FE, le nom interne de la fonction appelée est mémorisé dans FC, l'adresse du début de la première ligne de code dans CDS du nouvel article de STAT.

L'article de la pile STAT est libéré à la fin du traitement d'une fonction. L'article précédent de STAT permet de retrouver la fonction, la ligne et le symbole où il faut continuer la pseudoévaluation.

## Partie de la taille variable d'un article STAT

En réalité cette partie est la pile d'opérandes - opérateurs (OPOS) `OP - opérande - référence directe vers le descripteur d'opérande`. (remarque : dans la ligne de code les références d'identificateurs sont vers la table des symboles et les références des litteraux sont directes vers leur descripteur) `OOS - opérateur - ce champ peut avoir deux découpages possibles :`

1) pour les opérateurs

<table><tr><td>CO1</td><td>CO2</td><td>IX</td><td>TY</td></tr></table>

La signification des champs et la même que pour l'encodage des opérateurs dans la ligne de code.

2) pour les fonctions

<table><tr><td>TS</td><td></td><td>TY</td></tr></table>

`TS - entrée dans la table des symboles pour la fonction correspondante.`

`TY - indique qu'il s'agit d'une fonction.`

La partie de taille variable d'un article de STAT (OPOS) sert à la mémorisation des opérateurs et des références vers les opérandes (c.a.d. vers les descripteurs - noeuds d'arbre - objet) au moment de leur reconnaissance par l'analyse syntaxique. Ces renseignements sont utilisés pour la construction du descripteur d'expression (noeud non terminal de l'arbre - objet) quand celle-ci a été reconnue par l'analyse syntaxique. Ensuite les anciennes références et l'opérateur sont dépilés de OPOS et remplacées par la référence vers le noeud créé.

<figure><img src="image_12.png" /></figure>
VI.B. EXEMPLE DE PSEUDOEVALUATION

Considérons l'expression :

$$A + 23 \circ B$$

La suite des actions :

1° demande d'un article STAT et remplissage de sa partie fixe
( Seuls champs remplis : ETAT = LE et CDS = référence vers la forme
interne de la ligne tapée sur la console)

$$2^\circ \ A + 23 \circ B \quad \uparrow$$

Identificateur reconnu par l'analyse syntaxique - empilement
sur OP de la pile OPOS d'une référence vers son descripteur.

$$3^\circ \ A + 23 \circ B \quad \uparrow$$

Opérateur diadique reconnu - empilement de son code sur OS

$$4^\circ \ A + 23 \circ B \quad \underbrace{\rightarrow}_{\rightarrow} \uparrow$$

'littéral' reconnu - empilement d'une référence vers son descripteur.
sur OP

$$5^\circ \ A + 23 \circ B \quad \underbrace{\rightarrow}_{\rightarrow} \uparrow$$

Expression reconnue - construction de descripteur non terminal
de cette expression, dépilement de OPOS et empilement d'une référence vers
le descripteur résultant.

<figure><img src="image_13.png" /></figure>
$$6^{\circ} A + 23\% B$$

<figure><img src="image_14.png" /></figure>

Opérateur diadique reconnu : empilement sur OS

$$7^{\circ} A + 23\% B$$

<figure><img src="image_15.png" /></figure>

Identificateur reconnu - empilement d'une référence vers son descripteur sur OP

$$8^{\circ} A + 23\% B$$

<figure><img src="image_16.png" /></figure>

Expression reconnue - construction du descripteur nonterminal de cette expression, dépilement de OPOS et empilement d'une référence vers le descripteur résultant.

$$9^{\circ} A + 23\% B$$

<figure><img src="image_17.png" /></figure>

Fin de ligne en mode 'ligne exécution' - demande d'évaluation de l'expression dont le descripteur se trouve sur le sommet de OPOS (appel de procédure GETVAL pour lui), sortie du résultat sur la console.

<figure><img src="image_18.png" /></figure>

<figure><img src="image_19.png" /></figure>

<figure><img src="image_20.png" /></figure>
## Analyseur syntaxique

Nous avons utilisé l'analyseur syntaxique de M.Chevance de la C.I.I.

C'est un analyseur qui utilise la méthode d'analyse descendante.

Il existe le programme 'CHARADE' qui à partir d'une grammaire donnée génère le programme d'analyse. Le programme 'ANALYSEUR' ensuite en utilisant le programme d'analyse effectue l'analyse syntaxique du code-source écrit dans la grammaire donnée.

Notre tâche s'est limitée à une description des règles de la grammaire du langage source (APL) et à l'insertion des appels des procédures sémantiques aux endroits où elles sont nécessaires à effectuer pour le processus de pseudoévaluation, l'enchainement des lignes de code et l'appel des fonctions.

### Grammaire APL avec les fonctions sémantiques à appeler

Formalisme adopté :

<table><tr><td>&lt;et&gt;</td><td>délimitent un nom de règle</td></tr><tr><td>(et)</td><td>délimitent un symbole syntaxique composé</td></tr><tr><td>=</td><td>définition de règle</td></tr><tr><td>;</td><td>fin de définition d'une règle</td></tr><tr><td>#</td><td>suite d'occurences</td></tr><tr><td>.</td><td>chaine vide</td></tr><tr><td>]</td><td>ou</td></tr><tr><td>'et'</td><td>délimitent un terminal de la grammaire</td></tr><tr><td>PROC</td><td>appel d'une procédure semantique de nom PROC</td></tr></table>
Les non terminaux (règles) de la grammaire sont :

<AXIOME> symbole distingué de la grammaire

<EX> expression ALP

<OPD> opérande

<IE> expression indexée

<‡X> expression indexante

<PR> expression parenthesée

Les terminaux de la grammaire :

Ce sont toutes les unités lexicales déterminées dans l'analyse lexicales
(sauf étiquette).

<table><tr><td>'lit'</td><td>littéral</td><td>'mon'</td><td>opérateur monadique</td></tr><tr><td>'id'</td><td>identificateur</td><td>'dop'</td><td>opérateur diadique</td></tr><tr><td>'J'</td><td>crochet fermant</td><td>'bop'</td><td>opérateur indéfini</td></tr><tr><td>'C'</td><td>crochet ouvrant</td><td>';'</td><td>point virgule</td></tr><tr><td>')'</td><td>parenthèse fermante</td><td>'□'</td><td>quote</td></tr><tr><td>'('</td><td>parenthèse ouvrante</td><td>'fin'</td><td>fin de la ligne</td></tr><tr><td>'←'</td><td>assignation</td><td></td><td></td></tr><tr><td>'→'</td><td>branchement</td><td></td><td></td></tr></table>

Règles de grammaire

<AXIOME> = LBEG (<EX3 AIG(')'<PR>|']' TKET <IE> |<OPD> DFEX | .)
| I' -> ' BRANCH |.) 'fin' LEND: ERR;
<EX> = (')'<PR> |']' TKET<IE> |'id' IDT1|<OPD> : ERR)
('bop' TSEX | 'mon' T MOP | '←' 'ASG' (' ]' TKET <IE> TDOP
| 'id' ASEX : ERR) | 'dop'4 DOP <EX> TDOP | 'id' IDT2 |.);

<OPD> = 'lit' TLIT | '□' DCAL | 'id' IDTO ;

<IE> = #(<LIX>)';' TPVG) <IX> '[ ' TPVG (<OPD> |')' <PR> ) INDX;

<IX> = <EX> | . EIX ;

<PR> = <EX> '(' ;
- si 'id' est de type 'non défini' :

1) inscrire son type 'tableau'

Effectuer les actions 2,3,4 du cas précédent

- si 'id' a un autre type - erreur

### ASG - Rencontre de l'assign

Inscrire le code de l'assign sur OS de OPOS

### BRANCH - Traitement de branchement

Tester l'opérande sur le sommet de OPOS :

- Si c'est un noeud non terminal appeler GETVAL

Remplacer l'ancienne valeur NL (numéro de ligne) dans la pile STAT par la première valeur des données du descripteur qui se trouve sur le sommet OPOS.

Dépiler OPOS

Remplacer l'ancienne valeur CDS (adresse au code) dans la pile STAT par la nouvelle (trouvée par la table des lignes de la fonction et par la valeur NL). Si cette valeur est 'O' on incremente NL de 1. Initialiser l'index des symboles pour l'analyse syntaxique. Appeler ANALYSE SYNTAXIQUE.

- S'il n'y a rien, appeler EPILOG d'une fonction

### DFEX - Exécution d'une fonction diadique

Tester si l'opérande sur le sommet de OPOS est un noeud terminal

- si non appeler GETVAL

Tester si l'opérande sur le sous sommet de OPOS est un noeud terminal

- si non appeler GETVAL

Appeler FEX

### DOP - Rencontre d'un opérateur diadique

Si le programme est arrivé à ce point par l'analyse syntaxique - inscrire l'opérateur sur le sommet de OPOS.

Si le programme y est arrivé par l'action sémantique - rien.

### EIX - Traitement de l'indexant vide

Empiler 'zéro' comme opérande sur la pile OPOS
Consultation de la table des symboles (test du type 'id')

- si 'id' = tableau, empiler l'adresse du descripteur du tableau comme opérande sur OPOS

- si 'id' = fonction niladique avec le résultat, empiler la référence vers son entrée de la table des symboles comme opérateur sur le sommet de OPOS
Appeler FEX

- sinon - erreur

## IDT1 - Rencontre 'id' cas 1

Consultation de la table des symboles (test de type 'id')

- si 'id' = niladique fonction sans résultat, empiler la référence vers son entrée de la table des symboles comme opérateur sur le sommet de OPOS
Appeler FEX

Se brancher dans l'analyse à point 2

- sinon erreur.

## IDT2 - Rencontre 'id', cas 2

Consultation de la table des symboles (test de type 'id')

- si 'id' = fonction monadique avec le résultat, inscrire la référence vers son entrée de la table des symboles comme opérateur sur le sommet de OPOS
Test d'opérande sur le sommet de OPOS

- si c'est un noeud non terminal, appeler GETVAL
Appeler FEX.

- si 'id' = fonction monadique sans résultat, inscrire la référence vers son entrée de la table des symboles comme opérateur sur le sommet de OPOS.
Aller à point 3 dans l'analyse syntaxique.

- si 'id' = fonction diadique avec résultat, inscrire la référence vers son entrée de la table des symboles comme opérateur sur le sommet de OPOS
Aller à point 4 dans l'analyse syntaxique

- si 'id' = fonction diadique sans résultat, inscrire la référence vers son entrée de la table des symboles comme opérateur sur le sommet de OPOS
Aller à point 3 dans l'analyse syntaxique.

## INDX-Traitement de l'expression indexée

O) si l'opérateur qui se trouve dans OPOS à -(n+3) sous le sommet est '>' vérifie que l'opérande sur le sommet de la pile OPOS est un noeud terminal, sinon, erreure (n = longueur du vecteur de dimension d'opérande sur le sommet OPOS).

1) demande de la place pour un descripteur d'expression

2) Inscire dans ce descripteur :

a) référence vers le descripteur dont l'adresse se trouve sur le sommet de OPOS (dans le champ OP1 de descripteur)
Augmenter son RC de 1

b) Copier le type dans le champ TY

c) Remplir le champs CO1 par le code d'opération - indexation

3. Comparer la longueur du vecteur de dimension d'opérande dont la référence
est sur le sommet de OPOS avec le nombre sur le sous-sommet de OPOS dans
le champ d'opérateur.

S'ils ne sont pas égaux - erreur

4) demande de la place en mémoire pour :

a) opérande droit de l'indexation (longueur n = longueur du vecteur de dimension d'opérande OPl - gauche)

b) vecteur de dimension du résultat (longueur = longueur des vecteurs de dimension des n opérandes qui se trouvent dans OPOS au-dessous du sommet)

5) Descendre article par article dans OPOS (n articles) et faire pour chaque opérande les actions suivantes :

a) inscrire l'opérande de OPOS dans l'espace de donnée réservé à l'opérande droit de l'indexation.

S'il est vide, inscrire '0'.

b) copier le vecteur de dimension de l'opérande dans l'espace de donnée
vecteur de dimension du résultat. Si l'opérande est vide, inscrire la dimension
correspondante de l'opérande gauche de l'indexation.

c) Augmenter RC d'opérande de 1.

6) Dépiler OPOS de n + 2 articles

7) Empiler sur OPOS dans le champ opérande la référence vers le noeud créé.

Exemple C = A[X1 ; ; X2]

Situation avant traitement :

Après:

<table><tr><td>A</td><td></td></tr><tr><td>X1</td><td>3</td></tr><tr><td>0</td><td>2</td></tr><tr><td>X2</td><td>1</td></tr><tr><td></td><td>0</td></tr></table>

OPOS

<figure><img src="image_21.png" /></figure>

OPOS

LBEG - Action sur début de ligne

Test de positionnement de stop vecteur pour la ligne

- s'il est positionné, imprimer le nom de la fonction et le numéro de la ligne, suspendre son execution, demander un nouvel article de la pile STAT, y mémoriser le lien vers l'article précédent, positionner l'état d'interpréteur en 'définition de ligne' (LD) Attendre l'entrée d'une nouvelle ligne de la console.

- s'il n'est pas positionné, commencer analyse syntaxique et pseudoévaluation de la ligne.
## LEND - Traitement de fin de ligne

Test de positionnement du trace vecteur pour la ligne.

- s'il est positionné, imprimer le nom de la fonction et le numéro de la ligne, et repasser en mode LD.

Test d'opérande sur le sommet de OPOS

- si c'est un noeud non terminal, appeler GETVAL, imprimer le resultat sur la console.

- si c'est un noeud terminal, imprimer sa donnée sur la console.

- s'il n'y a rien, aucune impression.

Test de mode d'état d'interpreteur :

- s'il est LE (exécution de ligne) - fin d'exécution, retour de l'interpreteur à l'état de repos (LD - définition de ligne)

- s'il est FE (exécution de fonction)

Test s'il s'agit de la dernière ligne

si oui, appeler EPILOG d'une fonction.

si non, incrémenter NL (numéro de la ligne) de STAT, remplacer l'ancienne valeur CDS de STAT par la nouvelle (trouvée par la table des lignes et la fonction et par la valeur NL). Initialiser l'index des symboles pour l'analyse syntaxique. Appeler ANALYSE SYNTAXIQUE.

## TDOP Reconnaissance d'une expression avec opérateur diadique

Test de type d'opérateur sur le sous-sommet de OPOS.

- si c'est une fonction, appeler DFEX

- si c'est un opérateur, se brancher au sousprogramme donné par le code d'opérateur.

Dépiler OPOS de deux articles.

Empiler sur OP de OPOS la référence vers le noeud créé par le sousprogramme d'opérateur

**Nota :** 'les algorithmes de pseudoévaluation des opérateurs diadiques ne sont pas inclus dans ce chapitre. On peut voir la plupart d'eux sous la forme programmée en LPS en annexe.

## TKET - Traitement du séparateur 'J'

Empiler sur OPOS un article '0'.

## TLIT - Traitement du 'litteral'

Empiler sur la partie opérande (OP) de OPOS l'adresse du descripteur pointée par la source précodée CDS.

## TMOP - Reconnaissance et traitement d'un opérateur monadique

- si le programme est arrivé à ce point par l'analyse syntaxique inscrire le code d'opérateur dans OS sur le sommet de OPOS

Se brancher au sous-programme donné par le code d'opérateur

Dépiler OPOS d'un article
Empiler sur OP de OPOS la référence vers le noeud créé par le sous programme
d'opérateur.

**NOTA** : les algorithmes de pseudoevaluation des opérateurs monadiques ne sont
pas inclus dans ce chapitre.

TPVG - Traitement des séparateurs ';' et '['

Inscrire dans OS sur le sommet de OPOS le chiffre $n + 1$ ou $n$ est le chiffre
qui se trouve dans OS, en sous sommet,

TSEX - Determination du sexe d'un opérateur

Test du symbole suivant dans la chaine d'entrée d'analyse syntaxique.

- si c'est un 'id' dont le type dans la table des symboles est : fonction
niladique ou tableau,

- ou si c'est un 'lit' inscrire l'opérateur sur OP de sommet de OPOS comme
diadique, se brancher à point 4 dans l'analyse syntaxique.

- sinon, l'opérateur est monadique et il faut inscrire le code correspondant
sur OP du sommet de OPOS

Appeler TMOP

FEX - Prologue de traitement d'une fonction

1. Demander de la place pour nn nouvel article de la pile d'état STAT et son
remplissage :

a) état = FE (execution fonction)

b) FC = adresse du nom de la fonction - il est donné par le sous-sommet de
OPOS, dans OS.

c) CDS = adresse de la première ligne de code de la fonction (trouver à partir
du descripteur de la fonction)

d) NL = numéro de la ligne: mettre à 1.

2. Créer les noeuds de type variables locales pour le résultat et les arguments
de la fonction. Dans ceux des arguments mettre les références vers leur
descripteur de données (elles se trouvent en sous-sommet et sous-sous-sommet
de OPOS, dans OS.

3. Créer les noeuds des variables locales pour toutes les locales et étiquettes.
Pour les étiquettes créer aussi les descripteurs de leurs valeurs et les
valeurs.

4. Appeler le programme ANALYSE SYNTAXIQUE.

EPILOG - Epilogue de traitement d'une fonction.

Test de type de la fonction dont on sort :

- si elle est sans résultat explicite

1. trouver l'article précédent de la pile d'état d'interpréteur (STAT) par
le lien BL
2. libérer tous les noeuds introduits pour les variables locales et pour les étiquettes de la fonction.

3. libérer le dernier article de la pile STAT.

4. reprendre le programme ANALYSE SYNTAXIQUE à l'endroit mémorisé par l'article de la pile STAT qui est devenu dernier (l'article de la fonction ou de la ligne appelante).

- si la fonction a un résultat explicite

1. trouver l'article précédent de la pile d'interpréteur par le lien BL.

2. remplacer dans sa partie OPOS sur le sommet l'opérande (dans le cas d'une fonction monadique ou niladique) ou les deux opérandes (dans le cas d'une fonction diadique) par le résultat de la fonction appelée. La référence de celui-ci se trouve sur le sommet de OPOS de l'article de STATde la fonction terminée.

3. libérer tous les noeuds introduits pour les variables locales et pour les étiquettes de la fonction.

4. Libérer le dernier article de la pile STAT

5. Reprendre le programme ANALYSE SYNTAXIQUE à l'endroit mémorisé par l'article de la pile STAT qui est devenu le dernier (l'article de la fonction ou de la ligne appelante).
# CHAPITRE 7 - L'EVALUATEUR

Dans ce chapitre on trouvera une description du processus GETVAL qui calcule
le résultat d'une structure arborescente.

GETVAL peut fonctionner suivant deux modes, Le premier, mode 1, est équivalent à une interprétation classique. L'arbre est parcouru une fois et pour chaque noeud, le résultat intermédiaire est calculé.

Par contre dans le, mode 2, un parcours de l'arbre correspond au calcul d'un seul élément du résultat. Ce mode permet d'économiser de l'espace mémoire au prix d'une augmentation du temps de calcul.

## 1) DESCRIPTION DE L'ARBRE

### 1. Noeud terminal

<figure><img src="image_22.png" /></figure>

T : type : Entier, flottant, boolean caractère

RC : référence count

CRC : cumulative référence count.

PI : pointeur vers vecteur des valeurs maximales d'indices

### 2. Opérateurs scáaires

<figure><img src="image_23.png" /></figure>

OP code 1 à 40 (voir liste)

T type : Entier, boolean, carectère, flottant

RC référence count

CRC cumulative référence count

PI pointeur vers vecteur des valeurs maximales d'indices

ALPHA index du noeud opérande gauche

BETA index du noeud opérande droit.
3. opérateur_de_selection : take, drop, transpose

<figure><img src="image_24.png" /></figure>

OP = 41 take

42 drop

43 transposition.

ALPHA est un index vers le noeud terminal qui représente le vecteur opérande gauche.

4. Opérateur reverse

<figure><img src="image_25.png" /></figure>

Il n'y a pas d'opérande gauche.

5. produit extérieur

<figure><img src="image_26.png" /></figure>

6. produit intérieur

<figure><img src="image_27.png" /></figure>

OP2 opérateur produit
## 7. Réduction

<figure><img src="image_28.png" /></figure>

OP1 opérateur

K numéro de la composante.

## 8. Indexation

<figure><img src="image_29.png" /></figure>

ALPHA pointe vers un noeud terminal.

Ce noeud terminal représente un vecteur qui contient les index dans l'article TR des expressions indexantes. Le secteur a le format.

<figure><img src="image_30.png" /></figure>

L nombre d'indexant

I1 index ds TR du noeud du premier indexant

BETA pointe vers le noeud du segment indexé.

## 2. META MACHINE GETVAL (mode 2)

- GETVAL est une procédure **récursive**. En effet, à chaque noeud elle est active jusqu'à ce que l'on rencontre un noeud terminal.

Les paramètres de GETVAL, en mode 2, sont :

- la valeur du vecteur d'indice

- Le numéro du noeud appelant

- et l'adresse de retour

Les paramètres sont rangés dans la pile SS. Cette pile a le format suivant :
<table><tr><td>0</td><td></td><td>31</td></tr><tr><td></td><td>N</td><td></td></tr><tr><td></td><td>K1</td><td></td></tr><tr><td></td><td>LAB</td><td></td></tr></table>

N est l'adresse du vecteur d'indice

K1 est l'index dans la table TR du noeud appelant

LAB est l'adresse du retour.

Le format d'un vecteur d'indice est le suivant :

<table><tr><td>0</td><td>7</td><td>31</td></tr><tr><td>RC</td><td>L</td><td></td></tr><tr><td colspan="3">valeur 1° indice</td></tr><tr><td colspan="3">valeur 2° indice</td></tr><tr><td colspan="3">valeur 3°</td></tr></table>

### La pile accumulateur AQ

La pile accumulateur est une zone de mémoire dans laquelle sont rangées les valeurs des résultats intermédiaires.

### FONCTIONNEMENT DE GETVAL EN MODE 2

Les paramètres d'entrée de GETVAL en mode 2 sont :

- K 1'index du noeud dans l'arbre TR

<table><tr><td>0</td><td></td><td>31</td></tr><tr><td></td><td>K</td><td></td></tr></table>

- IX 1'adresse du vecteur d'indices de ce noeud

<table><tr><td>0</td><td></td><td>31</td></tr><tr><td></td><td>IX</td><td></td></tr></table>

- RET 1'adresse de retour

<table><tr><td>0</td><td></td><td>31</td></tr><tr><td></td><td>RET</td><td></td></tr></table>

GETVAL s'exécute en deux phases

a) une phase descendante au cours de laquelle GETVAL s'appelle de façon récursive pour atteindre les noeuds terminaux.

Avant un activation de GETVAL la procédure SAVE sauvegarde les paramètres au
sommet de la pile SS et on détermine les nouveaux paramètres en fonction de l'opérateur et des opérandes.

Au retour d'une activation de GETVAL la procédure OLDARG restitue les anciens paramètres.

B) La phase de calcul.

Quand un noeud terminal est atteint la procédure FETCH dépose au sommet de la pile des valeurs AQ l'élément et l'on retourne à l'activation précédente de GETVAL.

Quand les opérandes sont disponibles sur la pile AQ alors on effectue
grace au programme correspondant l'oppération relative au noeud et l'on donne le con-
trole à l'activation précédente.

On trouvera sur le tableau ci-dessous la liste des programmes pour
chaque opérateur.
LISTE DES PROGRAMMES DE TRAITEMENT DES OPERATEURS APL

<table><thead><tr><th>Opérateurs</th><th>monadique</th><th>diadique</th><th>calcul d'indice</th></tr></thead><tbody><tr><td>+</td><td>PLM</td><td>PLD</td><td>IDENT</td></tr><tr><td>=</td><td>MSM</td><td>MSD</td><td>IDENT</td></tr><tr><td>×</td><td>SIG</td><td>MUL</td><td>IDENT</td></tr><tr><td>‡</td><td>INV</td><td>DIV</td><td>IDENT</td></tr><tr><td>Γ</td><td>HAT</td><td>MAX</td><td>IDENT</td></tr><tr><td>Λ</td><td>BAS</td><td>MIN</td><td>IDENT</td></tr><tr><td>|</td><td>ABS</td><td>RES</td><td>IDENT</td></tr><tr><td>~</td><td>NOT</td><td></td><td>IDENT</td></tr><tr><td>V</td><td></td><td>OU</td><td>IDENT</td></tr><tr><td>Λ</td><td></td><td>ET</td><td>IDENT</td></tr><tr><td>Ψ</td><td></td><td>NOU</td><td>IDENT</td></tr><tr><td>Λ</td><td></td><td>NET</td><td>IDENT</td></tr><tr><td>&lt;</td><td></td><td>INF</td><td>IDENT</td></tr><tr><td>&gt;</td><td></td><td>SUP</td><td>IDENT</td></tr><tr><td>≤</td><td></td><td>EINF</td><td>IDENT</td></tr><tr><td>≥</td><td></td><td>ESUP</td><td>IDENT</td></tr><tr><td>=</td><td></td><td>EQU</td><td>IDENT</td></tr><tr><td>≠</td><td></td><td>NEQ</td><td>IDENT</td></tr><tr><td>↑</td><td></td><td>SELECT</td><td></td></tr><tr><td>↓</td><td></td><td>SELECT</td><td></td></tr><tr><td>Φ</td><td>IREV</td><td>ROT</td><td></td></tr><tr><td>°.</td><td></td><td></td><td>EXTL EXTR</td></tr><tr><td>V</td><td></td><td>CINT</td><td></td></tr><tr><td>Φ</td><td></td><td>SELECT</td><td></td></tr><tr><td>[ ]</td><td></td><td>IND</td><td></td></tr><tr><td>/</td><td></td><td>COMP</td><td></td></tr><tr><td>\</td><td></td><td>EXPD</td><td></td></tr><tr><td>op/</td><td></td><td>CRED</td><td></td></tr></tbody></table>
<figure><img src="image_31.png" /><figcaption>EVALUATION EN MODE 2 - PROCEDURE GETVAL</figcaption></figure>
## PROCEDURE SELECT

Cette procédure calcule le vecteur d'indice de l'opérande droit d'une opération take, drap et transpose.

Les paramètres de la transformation d'indice sont fournis par l'opérande gauche.

Cet opérande est un vecteur d'entiers :

<figure><img src="image_32.png" /></figure>

SELECT reserve de la place pour le nouveau vecteur d'indice dont la longueur est égale au rang de l'opérande droit :

<figure><img src="image_33.png" /></figure>

Ensuite par GEVTAL on va lire la valeur des éléments du vecteur opérande gauche qui permettent de calculer les valeurs $J_1, J_2, \dots$ des nouveaux indices.

Pour l'opérateur TAKE on aura :

$$J_i = J_i \text{ si } A_i > 0$$

sinon $J_i = \text{MAX}_i = I_i - I_{i-1}$

où $I_i$ est la valeur de l'indice i du vecteur d'indice actuel pointé par IX

et $TMAX_i$ la valeur de l'élément i du vecteur des valeurs maximales d'indices de l'opérande droit.

Pour l'opération DROP on aura :

$$J_i = I_i \text{ si } A_i < 0$$

$$J_i = I_i + A_i \text{ si } A_i \ge 0$$

où $I_i$ est la valeur de l'indice i du vecteur d'indice pointé par IX.

Pour une opération de transposition on aura :

$$J_i = I_{i-1} \text{ si } A_{i-1} \ge 0$$
<figure><img src="image_34.png" /></figure>

ORGANIGRAMME POUR LE TRAITEMENT DES OPERATEURS
DE SELECTION
### Procédure IREV

Cette procédure crée le vecteur d'indice :

<table><thead><tr><th>0</th><th>7</th><th>31</th></tr></thead><tbody><tr><td>0</td><td>1</td><td></td></tr><tr><td></td><td>J</td><td></td></tr></tbody></table>

avec $J = IMAX - I + 1$

où I est la valeur de l'indice pointé par IX et IMAX la valeur du vecteur de indices maximales de l'opérande droit.

Ensuite elle active GETVAL pour l'opérande droit.

<figure><img src="image_35.png" /></figure>
<figure><img src="image_36.png" /></figure>

CONVERT traite le débordement de capacité Ø V 2 qui concerne les calculs en arithmétique entière.

Les paramètres de OV2 sont :

- l'index du noeud de l'arbre

- l'adresse du vecteur de valeur

- la longueur du vecteur de valeur

- l'indice dans le vecteur de valeur de l'élément sur lequel s'est produit le débordement.

CONVERT initialise une nouvelle zone de données pour ranger les valeurs sous leur représentation flottante.

Elle effectue la transformation en flottant des éléments déjà calculés et les range dans la zone.

## Procédure CRED

CRED effectue le calcul d'une réduction. Elle procède en deux étapes.

1. Calcul de la composante sur laquelle s'effectue la réduction. Le résultat est en vecteur.

2. Calcul du réduit.

Pour éviter le calcul de la composante sur laquelle s'effectue la réduction, il est possible, quand l'opération accepte un élément neutre, d'effectuer le calcul du réduit en même temps que celui de l'élément courant de l'expression réduite.
Cependant, nous avons préféré, dans une première étape, implémenter une méthode générale, quitte à perdre en espace mémoire.

### PROCEDURE EXTR

Cette procédure calcule le vecteur d'indice de l'opérande droit de l'opération produit extérieur.

Si K est le rang de cet opérande, alors le nouveau vecteur d'indice est obtenu en prenant les K derniers indices du vecteur d'indices courant.

### PROCEDURE EXTL

Cette procédure calcule le vecteur d'indice de l'opérande gauche d'une opération produit extérieur.

Si K est le rang de cet opérande, alors le nouveau vecteur d'indice s'obtient en prenant les K premiers indices du vecteur d'indices courant.

### PROCEDURE CEXT

Cette procédure effectue le calcul du produire extérieur.

En fraction du code complémentaire qui indique la nature de l'opération scolaire, elle aiguille vers le programme correspondant.

### PROCEDURE SAVE

SAVE sauvegarde dans SS le paramètre du noeud courant, à savoir :
K numéro du noeud, IX adresse du vecteur d'indice et RET l'adresse de retour.

### PROCEDURE OLDARG

OLDARG restitue les anciens paramètres.

### CINT

Cette procédure effectue le calcul d'un produit extérieur en deux phases :

a) calcul de la composante qui correspond à l'opération produit

b) calcul del'élément réduit selon l'opérateur somme. Cette dernière partie est commune à la procédure CRED.

### FETCH :

Cette procédure dépose sur la pile AQ la valeur de l'élément correspondant au vecteur d'indice. L'adresse de cet élément dépend du type du tableau.
<figure><img src="image_37.png" /><figcaption>ORGANIGRAMME POUR LE TRAITEMENT DE LA REDUCTION</figcaption></figure>
<figure><img src="image_38.png" /></figure>

PRODUIT INTERIEUR-ORGANIGRAMME
<figure><img src="image_39.png" /></figure>

TRAITEMENT DE L'INDEXATION

ORGANAGRAMME
Cette procédure effectue les opérations scalaires, pour les opérations arithmétiques elle gère le dépassement de capacité et effectue autant de matiquement les conversions de types.

Il existe deux types de débordements :

1. débordement Entier Flottant indiqué par la flag OV2. Dans ce cas la mise à jour du type du résultat est effectuée.

2. débordement de capacité flottant. Dans ce cas il se produit un déroutement vers le programme de traitement des erreurs.

<figure><img src="image_40.png" /><figcaption>### TRAITEMENT DES OPERATEURS SCALAIRES</figcaption></figure>
# CHAPITRE VIII-LE MODE DEFINITION DE FONCTION

## A - Généralités sur le système de mise au point

Le système de mise au point proposé permet toutes les possibilités du système APL / 360, lesquelles constituent un des atouts majeurs de ce système. L'aspect mise au point, dans un système conversationnel, est en effet primordial ; c'est pourquoi il sera développé ici.

On distinguera, dans la mise au point de procédure, la définition d'une nouvelle ligne, et le redéfinition, complète ou partielle, d'une ligne déjà introduite. La distinction entre redéfinition complète et partielle sera faite plus bas.

L'analyse de cette commande permet de connaître

- le type de la commande

- le numéro de la ligne à laquelle celle-ci se rapporte, et, éventuellement, une valeur de pointeur dans la ligne.

En ce qui concerne le numéro de la ligne, il peut être

- nul (0)

- entier (n)

- décimal (n.m)

- S'il est nul, il s'agit d'une redéfinition de l'en-tête de procédure : on opère alors comme il est indiqué au chapitre : Analyse d'une en-tête de procédure. (VIII-F).

- S'il est entier, deux cas peuvent se produire :

1) la ligne a déjà été définie ; il lui correspond une entrée dans CDD : cette ligne doit être écrasée, ce qui correspond à libérer la source précodée, et à supprimer ses étiquettes éventuelles.

S'il s'agit d'une redéfinition partielle, la ligne est préalablement éditée.

2) La ligne n'a pas encore été définie. Ce cas rejoint celui d'un numéro de ligne décimal ; il s'agit d'introduire une nouvelle ligne.

- S'il est décimal, si la partie décimale est nulle, tout se passe comme s'il était entier. Sinon, il s'agit d'introduire une nouvelle ligne.
La zone de mise au point MAP

En dehors de la mise à point, on a vu que le numéro d'une ligne de procédure constituait un index dans la table des descripteurs de codes CDD. Au cours d'une mise au point, cette correspondance n'existe plus, car on peut introduire des lignes intercalaires dans la fonction dans un ordre absolument quelconque.

Lorsqu'on voudra, par une commande de mise au point, introduire de nouvelles lignes pour une procédure, deux possibilités se présenteront.

- s'il s'agit de rédéfinir une ligne existant déjà dans CDD (n° de ligne entier, ≤ nombre de lignes de la fonction) on réutilisera l'article de CDD existant.

- s'il s'agit de définir ou de rédéfinir une nouvelle ligne, on passera par la zone de mise au point MAP. Cependant, si cette nouvelle ligne suit l'ordre naturel de définition des lignes d'une procédure, on créera directement un article dans CDD, à la suite du dernier créé ; en cas de débordement de la zone CDD, on demandera une zone plus grande.

Pour la zone MAP, on peut envisager de demander de l'espace a priori pour cette zone, lorsqu'elle est nécessaire ; en cas de débordement on peut envisager 2 politiques.

- demande d'une zone plus grande.

- réorganisation provisoire de CDD, avec message à l'utilisateur.

La zone MAP est organisée de façon à faciliter la réorganisation de la table CDD consécutive aux mises au point. Celle-ci se fait, en principe, lors de la fermeture du mode définition pour la fonction qui a été mise au point ; les différentes lignes, qu'elles soient concernées par CDD ou par MAP, sont réintroduites dans une nouvelle table CDD, par ordre de numéro croissant ; ainsi est rétablie la correspondance entre numéro de ligne et index dans la table CDD, qui est de rigueur en dehors des mises au point (elle facilite considérablement l'enchainement des lignes en mode exécution).

Les articles de la zone MAP sont liés de façon à faciliter le programme de tri nécessaire à la réorganisation de CDD.

On distingue, dans l'ensemble des lignes à introduire dans cette réorganisation les sous-ensembles à partie entière égale ; ces sous-ensembles sont chainés entre eux dans l'ordre des parties entières croissantes ; à l'intérieur de ces sous-ensembles, le chainage se fait dans l'ordre des parties décimales croissantes : l'algorithme de réorganisation est alors élémentaire ; de plus, l'accès à un élément déterminé est plus rapide que dans le cas où MAP ne serait pas structurée, et où tout le poids des algorithmes reposerait sur le tri, la zone MAP ayant alors une organisation séquentielle.

Ex : la fonction F avait, au départ, 6 lignes ; après mise au point, il faut introduire les lignes de numéros 1.1, 1.2, 2.1, 4.1, 1.3,
définies dans cet ordre. La zone MAP a alors le dessin suivant :

<table><tr><td>PE</td><td>NS</td><td></td></tr><tr><td>PD</td><td>NA</td><td>ST</td></tr><tr><td>PD</td><td>NA</td><td>ST</td></tr><tr><td>PE</td><td>NS</td><td></td></tr></table>

PE = partie entière

NS = lien vers le sous-ensemble suivant

PD = partie décimale

NA = lien vers l'article suivant

Liens entre articles

Liens entre sous-ensembles

<figure><img src="image_41.png" /></figure>

La zone MAP ne sera demandée que si elle est nécessaire ; ausi, dans le mode de définition usuel des procédures, elle n'a pas à intervenir, les numéros de ligne se succédant dans l'ordre des entiers naturels.

## B - Analyse des instructions de mise au point (par TAB 3)

Les instructions de mise au point APL permettent, en plus de la redéfinition partielle d'une procédure, des commandes d'édition. On s'intéressera surtout au premier aspect ; on montrera comment sont détectées les instructions s'adressant à l'éditeur de texte et leur nature, sans développer le fonctionnement de celui-ci.

Les commandes de mise au point peuvent être accédées par TAB2, ou directement par TAB3.

Accès par TAB2 : l'analyseur d'en-tête de procédure a reconnu une chaine du type : `id['];` à l'identificateur id correspond une entrée dans la table des symboles ; cette entrée doit être de type fonction, sinon erreur. On passe alors en mode FD, et on inscrit au sommet de la pile d'état l'adresse de la fonction dans la table des symbole ; on est alors ramené à
à l'analyse directe par TAB3 qui correspond à la mise au point d'une fonction
au cours de sa définition

TAB3 : le caractère '[' a été reconnu.

<table><thead><tr><th>Etat</th><th>chiffre</th><th>Échelle</th><th>Échelle</th><th>Échelle</th><th>Échelle</th><th>Échelle</th><th>Ajuster</th><th>Action à prendre</th></tr></thead><tbody><tr><td>Entre</td><td>-1</td><td>1</td><td>-1</td><td>2</td><td>-1</td><td>-1</td><td>-1</td><td>-1</td></tr><tr><td>1</td><td>-1</td><td>1</td><td>3</td><td>4</td><td>5</td><td>-1</td><td>-1</td><td>-1</td></tr><tr><td>2</td><td>-1</td><td>-1</td><td>-1</td><td>-1</td><td>6</td><td>-1</td><td>-1</td><td>-1</td></tr><tr><td>3</td><td>-1</td><td>7</td><td>-1</td><td>-1</td><td>-1</td><td>-1</td><td>-1</td><td>-1</td></tr><tr><td>4</td><td>-1</td><td>8</td><td>-1</td><td>-1</td><td>9</td><td>-1</td><td>-1</td><td>-1</td></tr><tr><td>5</td><td>5</td><td>0</td><td>0</td><td>0</td><td>-1</td><td>0</td><td>0</td><td>0</td></tr><tr><td>6</td><td>6</td><td>-1</td><td>-1</td><td>-1</td><td>-1</td><td>0</td><td>0</td><td>0</td></tr><tr><td>7</td><td>-1</td><td>7</td><td>-1</td><td>4</td><td>5</td><td>-1</td><td>-1</td><td>-1</td></tr><tr><td>8</td><td>-1</td><td>8</td><td>-1</td><td>-1</td><td>10</td><td>-1</td><td>-1</td><td>-1</td></tr><tr><td>9</td><td>9</td><td>-1</td><td>-1</td><td>-1</td><td>-1</td><td>0</td><td>0</td><td>-1</td></tr><tr><td>10</td><td>10</td><td>-1</td><td>-1</td><td>-1</td><td>-1</td><td>0</td><td>0</td><td>-1</td></tr></tbody></table>

- 1 - erreur

0 = reconnaissance d'une commande correcte.

Remarques :

1) les états entourés de traits forts correspondent à la possibilité de spécifier, derrière la commande de définition de ligne, la nature de la nouvelle ligne : suivant le numéro de la ligne (0 ou ≠ 0), l'analyse se fait par TAB1 (analyse lexicale) ou TAB2 (analyse d'en tête de procédure)

2) les commandes de redéfinition ne sont valables que pour les fonctions dont l'exécution n'a pas été interrompue. C'est-à-dire qu'il est interdit de rédéfinir une fonction référencée par la pile STAT, à l'exception de celle qui est référencée par le sous-sommet de STAT (qui est celle de niveau le plus interne qui ait été interrompue), à condition qu'elle ne soit pas référencée plus bas dans la pile STAT (procédure récursive).
3) suivant la nature du dernier caractère de la ligne (caractère ' ∨ ', ou non), le mode restera FD, ou repassera à LD (voir plus loin la fermeture de définition de fonction).

A la fin de cette analyse, on dispose des informations suivantes :

NLE : partie entière du numéro de ligne

NLD : partie décimale

ND : nombre de décimales

CH : pointeur dans la ligne (pour les redéfinitions partielles).

Les informations concernant le numéro de ligne sont mises sous forme interne, et écrites au sommet de la pile STAT.

### (Re)définition complète d'une ligne (DCL)

Si le caractère suivant la commande est ' ∨ ', il n'y a rien à définir : on repasse en mode définition par la procédure FDTØLD.

Sinon, N étant le nombre de lignes donné par CDD, l'algorithme est le suivant :

<figure><img src="image_42.png" /></figure>
## Commentaires :

- l'écrasement d'une ligne se traduit par la libération de la zone CDS (source précodée) de la ligne. De plus, si cette ligne était étiquetée il faut invalider les entrées correspondantes dans la zone étiquette LBD, et décrémenter le compte de références de ces variables dans la table des symboles.

Enfin, on invalide l'article correspondant à cette ligne dans MAP ou CDS, avec mise à jour des liens dans le cas de MAP.

- La recherche dans MAP se fait d'abord au niveau des sous-ensembles ; si la ligne à introduire correspond à un nouveau sous-ensemble, celui-ci est introduit et lié aux autres. Si le sous-ensemble existe, la recherche se fait sur les articles de ce sous-ensemble ; si l'article existait déjà, il s'agit d'un écrasement ; sinon, il faut le créer et le lier aux autres.

## Redéfiniton partielle d'une ligne (RPL)

1. accès à la source précodée de la ligne, qui peut être référencée par CDD (si le numéro de ligne est entier, $\le N$) ou par MAP.

2. Si la ligne existe, elle est éditée, et la console est positionnée conformément à CH. L'utilisateur spécifie alors les mises au point qu'il veut effectuer ; celles-ci sont prises en compte dans une analyse particulière qui construit la nouvelle chaîne source. L'ancienne est détruite comme dans DCL, et on est ramené au cas d'une définition complète de ligne, simplifiée par le fait que le pointeur dans CDD ou dans MAP est connu.

## Edition d'une ligne (EDL)

L'édition d'une ligne s'appuie sur la source précodée et sur la table des symboles.

Les algorithmes ne sont pas spécifiés ici. Après édition d'une ligne, si le dernier symbole n'est pas ' ∇ ', le mode est celui de la ligne qui vient d'être éditée.

On peut éditer indifféremment des ligues référencées par MAP ou CDD.

## Edition complète de procédure ECP

Elle suppose que les lignes de la procédure ont été réordonnées ; ceci se fait par les même algorithmes que FDTOLD qui, en particulier, libèrent la zone MAP après constitution de la nouvelle table CDD.

L'édition a lieu ensuite. Si le caractère suivant la commande n'est pas ' ∇ ', le mode reste FD, et le numéro de ligne est $1 + N$.
### D. Passage au mode LD : FDTØLD

Ceci est commun à toutes les commandes précédentes, lorsque les mises au point d'une fonction prennent fin.

Il faut alors créer une nouvelle zone CDD qui tienne compte de l'ancienne zone et la zone MAP. Cependant, la demande d'une nouvelle zone CDD n'est nécessaire que si on a eu à introduire une zone MAP.

Dans le cas contraire, la mise à jour se borne à supprimer les lignes invalidées.

Le nouveau mode est LD.

On réorganise ensuite la zone des étiquettes, dont les valeurs ont pu être modifiées par des lignes intercalaires. Si MAP n'a pas été utilisée, cette réorganisation est un simple compactage ; dans le cas contraire, le plus simple est de détruire l'ancienne zone LBD, et de recréer la nouvelle en consultant successivement les lignes de la fonction ; le flag indiquant le nombre d'étiquettes en tête de la source précodée permet d'accélerer cette mise à jour.

Les espaces excédentaires éventuels des zones CDD et LBD sont rendus, et les en-têtes de ces zones sont mises à jour.

Enfin, le flag "fin de procédure" est positionné dans la dernière ligne de la procédure.

### E. L'analyse lexicale en mode définition de fonction

Les algorithmes sont pratiquement les mêmes qu'en mode définition de ligne : elle se fait par la table TAB 1. Les différences résident au début et à la fin de la ligue :

1) au début : le symbole ' → ' est ici considéré comme l'opérateur de branchement, alors qu'en mode LD c'est une commande pour la pile d'état.

- La présence d'étiquettes dans la ligne conduit à créer de nouveaux articles dans la zone LBD, après avoir vérifié que ces étiquettes n'ont pas été déjà utilisées dans la fonction en cours (parcours séquentiel de LBD). De plus, le nombre d'étiquettes est indiqué dans l'en-tête de la source précodée.

**Remarque :**

La création d'une étiquette dans LBD implique que l'on augmente le compte de références de la cellule correspondante dans la table des symboles (comme pour les locaux), de façon à pouvoir détruire cette cellule lorsqu'on détruira la fonction en cours de définition.

2) **à la fin** : c'est le problème de l'enchainement des lignes en mode FD ; il a été vu lorsque le dernier symbole dans la ligne (avant le symbole fin) est 'V'.

Dans les autres cas, deux possibilités se présentent :

- après une commande d'édition, le nouveau numéro de ligne est le
numéro courant de ligne pour une édition partielle, le numéro de la dernière ligne définie, plus 1, pour une édition complète.

- après une (re)définition de ligne, le numéro de ligne est incrémenté, compte tenu du nombre de décimales dans le numéro courant :

Ex : après 1.53, 1.54
après 2, 3
après 1.9, 2.

- l'analyse lexicale commence toujours par une demande d'espace mémoire pour la source précodée ; le pointeur vers cette zone est rangé dans STAT et, suivant les cas, dans CDD ou dans MAP (voir système de mise au point).

## F. Analyse d'une en-tête de procédure (TAB2)

'V' a été reconnu en mode LD ; on passe donc en mode HD.

<table><thead><tr><th>État</th><th>Symbol</th><th>lettre</th><th>chiffre</th><th></th><th>:</th><th>V</th><th>[</th><th>]</th><th>□</th><th>Fin</th><th>Autre</th><th>Unité syntaxique</th></tr></thead><tbody><tr><td>1</td><td></td><td>1</td><td>2</td><td>-1</td><td>-1</td><td>-1</td><td>0</td><td>-1</td><td>-1</td><td>-1</td><td>0</td><td>-1</td><td>Fin</td></tr><tr><td>2</td><td></td><td>21</td><td>2</td><td>2</td><td>23</td><td>22</td><td>0</td><td>TAB3</td><td>-1</td><td>-1</td><td>0</td><td>-1</td><td>Paramètre</td></tr><tr><td>31</td><td></td><td>21</td><td>0</td><td>1</td><td>23</td><td>cc</td><td>-1</td><td>-1</td><td>-1</td><td>-1</td><td>0</td><td>-1</td><td>"</td></tr><tr><td>22</td><td></td><td>0</td><td>0</td><td>"1</td><td>-1</td><td>-1</td><td>-1</td><td>-1</td><td>-1</td><td>"1</td><td>0</td><td></td><td>Local</td></tr><tr><td>23</td><td></td><td>0</td><td>0</td><td>"1</td><td>-1</td><td>-1</td><td>-1</td><td>-1</td><td>-1</td><td>"1</td><td>-1</td><td></td><td>Résultat</td></tr></tbody></table>

0 = reconnaissance d'une unité : retour à l'état 1

-1 = erreur.

Lorsqu'une unité est reconnue, elle est encodée ; l'encodage contient le type de l'identificateur et une référence vers la table des symboles ; il peut être fait dans un buffer *BUF2* de taille fixe.

Le contenu de *BUF2* est ensuite analysé : les configurations possibles sont :

(R|.)# P # L(V|.)

On peut avoir un nombre quelconque de locaux, éventuellement nul, et un nombre de paramètres compris entre 1 et 3, bornés comprises; toute autre configuration est un cas d'erreur.

On vérifie d'abord que la configuration appartient à une configuration permise: R = 1 si la fonction rend un résultat

P = nombre de paramètres (y compris le nom de la fonction).

L = nombre de locaux
Au début R = P = L = 0 ; on vérifie que la source est dans une configuration
permise.

<figure><img src="image_43.png" /></figure>

Si on sort par out, la ligne est correcte si P ≤ 3

La cellule de la table des symboles correspondant à la fonction
est référencée par :

BUF2[R + 2] si P = 3

BUF2[R + 1] si P = 1 ou 2

On va donc regarder quel est le type de cette cellule;

- si le type est indéfini, il s'agit d'une première définition

- si c'est une fonction, il s'agit d'une redéfinition de la
tête de procédure : le mode doit alors être FD (c'est à dire que l'on est
passé par une commande de mise au point pour redéfinir cette ligne) sinon,
erreur.

- si le type est autre, erreur.

Nous allons considérer successivement le cas d'une première
définition et celui d'une redéfinition

1) Première définition :

- la référence à la fonction en cours de définition est mémorisée dans la pile d'état STAT, ainsi que le numéro de ligne (ici, 0)

- Il faut indiquer dans la table des symboles, le type de la fonction (monadique, diadique, niladique avec ou sans résultat), qui est donnée par R et P.
- Demander de l'espace pour le descripteur de fonction (sa taille est connue exactement, et fonction de R, P, et L) et le remplir en examinant BUF2 (recopier des références vers la table des symboles).

- Demander de l'espace pour le descripteur de codes CDD et pour la zone de labels. Le remplissage de la zone des locaux s'accompagne de l'incrémentation du compte de références des noeuds correspondants dans la table des symboles LBD; La taille de ces zones est choisie a priori, aucune hypothèse ne pouvant être faite sur la longueur définitive de ces zones.

Cependant, si le dernier caractère de la ligne est ' ∇ ', ces tables se limiteront à l'article de tête.

Dans ce cas, le mode repasse à LD; dans l'autre, le nouveau mode est FD, et le numéro de ligne est mis à 1 dans la pile STAT.

## 2) Rédéfinition :

- La référence à la fonction est déjà mémorisée dans la pile d'état. Il faut noter que seules peuvent être mises au point les fonctions dont l'exécution n'a pas été interrompue, c'est-à-dire celles qui en sont pas référencées par la pile d'état STAT, à l'exception de la dernière empilée.

- Le nouveau type est indiqué dans la table des symboles, en fonction de R et P.

- On demande un nouvel espace pour le descripteur de fonction et on opère comme dans le cas d'une première définition; cependant, le nouveau descripteur de fonction référence le même descripteur de code et la même zone d'étiquettes que précédemment.

Ceci suppose que les cellules correspondant aux anciens locaux ont été libérées de la table des symboles : voir fonctions de mise au point.

- si le dernier caractère de la ligne est ' ∇ ', on retourne au mode LD (voir récupération sur fonction de mise au point), sinon le système demande la définition de la ligne suivante, comme dans le cas d'une première définition; on reste alors en mode FD.
# CHAPITRE IX - GESTION DE MEMOIRE

On distingue trois zones dans l'espace de la mémoire de travail (voi le schéma de la mémoire de travail).

## I. Zone de taille fixe pour les noeuds intermédiaires et terminaux de la table des symboles.

Comme il s'agit d' objets de même taille, il n'y a pas de gestion à faire. Les espaces vides sont chaînés entre elles et forment ainsi une liste. Si l'interpreteur libère un noeud, celui-ci est ajouté à la liste des espaces vides (et au contraire).

Le remplissage complet de la zone produit un message à l'utilisateur qui peut demander l'agrandissement de la zone par le système.

<figure><img src="image_44.png" /></figure>

## 2 - Zone non compactable pour les descripteurs des données et des expressions et aussi pour les noeuds de la table des symboles pour les variables locales.
Les objets de cette zone sont tous de même taille (3 mots) et la gestion de mémoire est aussi simple comme dans le cas précédent. Elle se réduit à la gestion de la liste des espaces libres.

Seulement la frontière de cette zone est mobile et se déplace dans le cas nécessaire. L'appel de demande de mémoire au système se produit seulement dans le cas ou toutes les deux zones voisines (compactable et non compactable) sont pleines.
<table><caption>Schéma de la mémoire de travail</caption><tr><td>Table des symboles : noeuds intermédiaires<br/>noeuds terminaux</td><td>TAILLE FIXE</td></tr><tr><td>1. Descripteurs des données et des expressions<br/>2. Noeuds de table des symboles pour les<br/>variables locales</td><td>ZONE NON COMPACTABLE</td></tr><tr><td></td><td>FRONTIERE DES ZONES<br/>MOBILE</td></tr><tr><td>8. Lignes de code sous la forme interne<br/>7. Tables d'étiquettes<br/>6; Tables des lignes<br/>5. Descripteurs des fonctions<br/>4. Pile de recursion pour GETVAL<br/>3. Pile d'état d'interpréteur<br/>(articles liés)<br/>2. Vecteurs des tailles des données<br/>1. Vecteurs des données</td><td>ZONE COMPACTABLE</td></tr></table>

1

2

3
### 3. Zone compactable

pour les vecteurs des données

vecteurs de taille des données

descripteurs des fonctions

tables des lignes de code

tables des étiquettes

articles de la pile d'état d'interpréteur

pile de récursion pour la procédure GETVAL

lignes de code sous la forme interne.

Cette zone est soumise à l'algorithme de gestion de mémoire qui :

a) cherche pour les demandes de mémoire par l'interpréteur des
emplacements convenables

b) s'il n'en trouve pas il fait le compactage des espaces utilisés

c) traite le débordement des objets susceptibles de déborder

Pour le fonctionnement de l'algorithme de gestion de mémoire tous les
objets dans la zone compactable ont des en têtes suivantes :

Espaces occupés :

<table><thead><tr><th>O</th><th>15</th><th>31</th></tr></thead><tbody><tr><td>LG</td><td>B</td><td>TY</td><td>RC</td></tr><tr><td colspan="4">BL</td></tr></tbody></table>

LG = longueur d'objet en mots

B = bit positionné s'il s'agit d'un espace occupé

RC = compte de références vers l'objet

TY = type d'objet (vecteur des données, vecteur de taille, descr. des fonctions, tables de ligne etc...)

BL = back link - pointeur vers l'objet qui pointe l'objet en question.

Espaces libres :

<table><thead><tr><th>O</th><th>15</th><th>31</th></tr></thead><tbody><tr><td>LB</td><td>B</td><td></td></tr><tr><td colspan="3">LB</td></tr><tr><td colspan="3">LF</td></tr></tbody></table>

LG = longueur d'espace libre en mots

B = bit positionné à 0 signifie qu'il s'agit d'un espace libre

LB = lien vers l'espace libre précédent

LF = lien vers l'espace libre suivant
<figure><img src="image_45.png" /><figcaption>Schéma de la liste des espaces libres de la mémoire compactable.</figcaption></figure>

## Algorithme de libération de la place

Dès que l'interpreteur détecte que le compte de références d'un objet dans la mémoire passe à 0, il demande que la gestion de mémoire ajoute son espace à la liste des espaces libres.

L'algorithme est très simple.

* PO - pointeur vers l'espace à être libérer

* Q - registre de travail

l'algorithme consiste en : $Q \leftarrow LF (TETE)$

$LF (PO) \leftarrow Q$

$LB (PO) \leftarrow TETE$

$LB (Q) \leftarrow PO$

$LF (TETE) \leftarrow PO$

$T (PO) \leftarrow 'O'$

## Algorithme de la recherche de la place

Pour la recherche de la place l'algorithme modifié de "first fit" est proposé.

Les symboles utilisés dans l'organigramme :

* P,PI - registres de travail

* F : bit de controle de déroulement de l'algorithme

* C = (3 mots) montant de l'espace mémoire consécutive le plus petit possible.

* N = longueur demandée

* L = adresse de l'espace trouvé correspondant à la demande

* RO = adresse d'espace libre où l'algorithme s'est arrêté dans son déroulement précédent.
<figure><img src="image_46.png" /></figure>
Organigramme de compactage

A - premier mot de la mémoire

B - dernier mot de la mémoire

P, P1 - registre de travail

<figure><img src="image_47.png" /></figure>
# CHAPITRE X - ESTIMATION DES PERFORMANCES

## A. Précision de calcul de l'interpréteur

La donnée de type entier est représentée par 32 bits dans la mémoire de travail de l'interpréteur (31 bits significatifs). La donnée de type flottant occupe 64 bits. Sa représentation est celle des nombres en virgule flottante format long.

Cette représentation permet la précision suivante :

a) La valeur absolue des nombres est comprise entre $10^{-77}$ et $10^{77}$ environ

b) Précision 15 chiffres décimaux significatifs exacts.

La donnée de type entier occupe 32 bits. Si pendant le calcul sa valeur déborde cette taille, le débordement est traité (voir processus GETVAL), il se produit la conversion de type entier en type flottant et la précision citée au dessus est toujours atteinte.

## B. Volume de code de programme 'INTERPRETEUR' (1 mot = 32 bits)

L'estimation est approximative et basée sur les essais de programmation des routines principales de l'interpréteur.

<table><tr><td colspan="2">Boucle centrale du programme 'INTERPRETEUR'</td></tr><tr><td></td><td>Environ 200</td></tr><tr><td>Analyse lexicale</td><td>Environ 1500</td></tr><tr><td>Analyse syntaxique</td><td>2000</td></tr><tr><td>Pseudoévaluation</td><td>3000</td></tr><tr><td>Evaluation (GETVAL)</td><td>2000</td></tr><tr><td>Routines de mode de définition</td><td>3000</td></tr><tr><td>Gestion de mémoire</td><td>250</td></tr><tr><td>ENSEMBLE</td><td>II950</td></tr></table>

## C. Limitation des zones de mémoire

Table des symboles est limitée à 4096 mots ce qui représente à peu près 400 symboles, (le nombre maximal des symboles dépend de leur longueur) tandis que APL/360 IBM travaille avec une table de 256 symboles.

### Descripteurs des données et des expressions.

La zone est limitée à 60K mots ce qui nous paraît largement suffisant.

### Zone des données

Elle recouvre toute la mémoire virtuelle accordée à l'utilisateur par le système d'ordinateur en question.

Nota : les zones de mémoire voir 'gestion de mémoire'.
# CHAPITRE XI. CONCLUSION

L'analyse détaillée présentée dans ce document et complétée par les tests d'algorithmes qui figurent en annexe, permet de confirmer un certain nombre d'avantages de l'interpréteur que nous proposons par rapport aux interpréteurs classiques.

1) L'optimisation dans l'analyse des expressions ne fait pas intervenir un plus grand nombre d'algorithmes mais est essentiellement le résultat d'une nouvelle architecture de l'interpréteur et d'une nouvelle définition des structures de données (tableaux). La taille du code de l'interpréteur est estimée à 12 K mots de 32 bits environ.

2) Dans le cas des expressions pour lesquelles la méthode classique d'interprétation (évaluation immédiate) est la plus efficace, la différation de l'évaluation est inhibée. Il en résulte qu'en moyenne les performances sont au moins égales à celles des interprétateurs classiques.

3) De nombreuses applications pour lesquelles le langage APL est particulièrement adapté parce qu'il offre des opérateurs sur tableaux très évolués et surtout des opérateurs de sélection, pourront être réalisées avec plus d'efficacité. La manipulation de grands tableaux et l'utilisation des opérateurs les plus puissants tels que le produit extérieur et l'indexation généralisée font souvent échoer les interpréteurs classiques qui attribuent de l'espace mémoire et du temps unité centrale pour des résultats intermédiaires inutiles.

4) Les extensions au langage APL pourront être facilement incluses dans le système proposé qui pourra ainsi servir d'outil de recherche.

Les applications graphiques font intervenir des manipulations de tableaux de grande taille. Un ensemble d'objets ou une structure complexe peut être décomposé en un vecteur d'objets élémentaires. Chaque objet élémentaire est généralement décrit par une liste de points dans un espace à 3 dimensions, c'est-à-dire par une matrice à 3 colonnes. En outre les faces qui constituent cet objet sont définies par une liste de points de l'objet la matrice des faces. Les changements de coordonnées, les déplacements, la perspective font intervenir des produits matriciels. Non seulement
la description des objets, mais aussi la production des images (la sortie sur écran ou sur papier) peut être simplement programmée en APL.

Enfin, comme le langage est interprétatif et que sa syntaxe est très simple et concise, les applications graphiques en mode conversationnel pourraient être un des objectifs d'utilisation du système proposé.

Ce document d'analyse marque la fin de la première étape du projet de système APL. La deuxième étape, en cours, consiste à réaliser un système expérimental fondé sur ces spécifications et destiné à être utilisé comme outil de recherches.
# CHAPITRE XII- BIBLIOGRAPHIE

Chaque référence est précédée d'une lettre indiquant à quelle catégorie appartient l'ouvrage ou article cité.

L = Langage

A = Application

R = Réalisation

E = Extension

O = Optimisation

O [1] ABRAMS, Philip S. (1970) AN APL MACHINE
Ph.D. Thesis. Stanford University. Rpt n° SLAC-114

O [2] ABRAMS, Philip S. (1971) A FORMAL APPROACH TO APL SEMANTICS
Colloque APL. Publication IRIA pp. 159-180

O [3] BATTAREL, Gérard. (1973)
Thèse de Docteur-Ingénieur. Université de Toulouse

E [4] BREED, Lawrence M. (1971) DESIGN OF THE APL+PLUS FILE SUBSYSTEM
Colloque APL. Publication IRIA pp. 489-496

O [5] DELBREIL, Michel. (1973)
Thèse de Docteur-Ingénieur. Université de Toulouse

E [6] FALKOFF, A.D. (1971) A SURVEY OF EXPERIMENTAL APL FILE AND I/O
SYSTEMS IN IBM
Colloque APL. Publication IRIA pp. 365-374

E [7] HARRIS, Larry R. (1973) A LOGICAL CONTROL STRUCTURE FOR APL
APL-Congress 73 (Copenhagen)

O [8] HASSITT, A. et LYON, L.E. (1972) EFFICIENT EVALUATION OF ARRAY
SUBSCRIPTS OF ARRAYS
CACM Jan. 1972

L [9] IVERSON, K.E. (1962) A PROGRAMMING LANGUAGE
Wiley, New-York

L [10] KATZAN, Harry. (1970) PROGRAMMING AND COMPUTER TECHNIQUES
Van Nostrand

L [11] LATHWELL, R.H. et MEZEI, J.E. (1971) A FORMAL DESCRIPTION OF APL
Colloque APL. Publication IRIA pp. 181-216

E [12] LATHWELL, R.H. (1973) FILE PROCESSING IN TERMS OF CONCURRENT
PROCESSORS WITH SHARED VARIABLE INTERFACES
APL-Congress 73 (Copenhagen)

O [13] MARCHAL, A. et KEIR, R. (1972)
Ph.D; Thesis. University of Utah

R [14] MARTIN, M. (1972) APL CII/10070
Université de Toulouse. (Contrat CRI-70.007)
A [16] POSDAMER, J.L. et RIESENFELD, R. (1973) *THE APPLICATION OF APL IN GRAPHICS COMPUTATION*
APL Congress 73 (Copenhegue)

L [16] RAULT, J.C., DEMARS, G. et RUGGIU, G. (1973) *LE LANGAGE ET LES SYSTEMES APL*

R [17] ZAKS, Rodnay. (1971) *A MICROPROGRAMMED APL IMPLEMENTATION*
University of Berkeley

R [18] (1971) *LLL-APL AN APL INTERPRETER*
Lawrence Livermore Laboratory. University of California
ANNEXE A - EXEMPLE D'APPLICATION DE LA METHODE D'INTERPRETATION

Pour une description simple de la méthode d'interprétation, considérons l'expression suivante :

$$R \leftarrow \begin{array}{c@{\hspace{0.5em}} c} 2 & 2 \\ \top & \rightarrow \end{array} A+B$$

où A et B sont deux matrices de dimensions n,m avec n et m ≥ 2.

La méthode d'interprétation dite naïve, avec exécution immédiate des opérations, consisterait à réserver n×m emplacements mémoire pour les valeurs du résultat intermédiaire $A+B$, et à effectuer $2×m×n$ chargements et $n×m$ additions et rangements. L'application de l'opération de sélection montre que $(n×m-2×2)$ valeurs ont été calculées inutilement.

Nous proposons de construire le graphe de l'expression avant toute évaluation :

<figure><img src="image_48.png" /></figure>

Grâce à une nouvelle définition de la structure des données pour un tableau ([13]), ceci conduit à interpréter l'expression sans calculer explicitement l'ensemble des valeurs associées aux noeuds non-terminaux du graphe.

Connaissant en tout point du graphe le vecteur dimension, et en particulier en $R$, le calcul des valeurs peut être différé à volonté, et surtout se limite aux seuls éléments des opérandes qui participent à la définition du résultat.

L'évaluation devient alors un processus indépendant et récursif comportant deux phases :

- accès aux éléments utiles des opérandes, partant de la définition du résultat

- combinaison des éléments sélectionnés.

Ainsi, dans cet exemple, $R$ étant un tableau de dimension $2×2$, seuls $2×2$ éléments de $A$ seront combinés à $2×2$ éléments de $B$.

Ce gain en temps et en place qui est obtenu par une transformation de l'expression dans la méthode d'ABRAMS ([1]) est ici inhérent à la méthode. De plus, la différation du calcul des valeurs peut se généraliser à des fonctions entières, ce qui permet d'envisager la compilation de fonctions APL.

Des outils de contrôle du graphe objet ont été étudiés et seront développés dans le cadre de ce projet.
TRAITEMENT DES OPERATEURS DIADIQUET AU COURI DE LA PLEUDQEVALUATION

1

LPS A4.83 3/4/73 14:12:03 Jim

LPS

0001 MODULE ESSAI;

0002 GLOBAL;

0003 EXTER AL EXIT;

0004 CONSTANT RH9 I=6;

0005 CONSTANT TAKE I=7;

0006 CONSTANT TRANS I=8;

0007 DCL TR (5) A (3) I;

0008 DCL A8S (5) I (3) I;

0009 DCL STK A (8);

0010 DCL T.3 (12) L A INITIAL=(PLUS,LOGDIA,COMDIA,EQUAL,MUL,RHBDIA,RHBDIA,

0011 R49E1,1,RHBDIA,CUMP,CAT,SGT);

0012 CONSTANT TYPEK C=ITYP ERROR;

0013 CONSTANT RKEX C=THANK ERROR;

0014 FORM APS SJAL STK HP ORGX(4))

0015 FORM C2 B I 8458;

0016 FORM IX B I ORGX;

0017 FORM TY B I 8459(5);

0018 FORM C81 I ORGX;

0019 FORM 31 WP A ORGX;

0020 FORM 111 I V ORGX;

0021 DCL ALM (20) A I;

0022 FERN A1 I I;

0023 DCL T A1 A;

0024 FORM F14 QUAL I 4 W I;

0025 FORM 3C B I 8458 (3);

0026 FORM ALPH A1 H ORGX (2);

0027 FORM BETA A1 H ORGX (3);

0028 FORM C1 I R;

0029 FORM TY B I 8459 (2);

0030 DCL 11 A1 I;

0031 FORM 3P A1 H;

0032 FORM EFD A P A ORGX (2);

0033 DCL SYS A (2);

0034 FORM DATA QUAL GYS WP A;

0035 FORM LS I ORGX;

0036 FORM DA (1000) A I;

0037 FORM DB (100) SIT;

0038 END;

C

0039 /**/

0040 /**/

0041 PROGRAM TEST;

0042 STARTED;

0043 TACE;

0044 DLOGLIST ALL;

0045 CALL (LINK) IN;

/* DECLARATIONS GLOBALES */

OPERATEURS DIADIQUES TRAITES:

+ - x < 5 = 2 > = A
V A X P O Q , T A /

VOLUME en mémoire occupé par
le code effectif du programme:
ENVIRON . 820 mot en mémoire

/* PROGRAMME TEST QUI REMPLACE LA BOUCLE CENTRALE */
0044 CALL (LINK) TD8P)

0047 G0 T9 E=IT)

0048 END TEST)

0049 /**/

0050 /**/

/* INITIALIZATION D'EXEMPLE */

0051 PROCEDURE INI;

0052 DCL RET L M;

0054 SAVE (LI)*RET)

0055 IT=C*LENGTH(TR);

0056 TME*C*LENGTH(4FM);

0057 TR(IT)*F=(A(MEM(0)),

0058 MEM(0)*H1=3;

0059 MEM(0)*RC=1;

0060 MEM(1:3)=5,3,4,1

0061 MEM(4)*H1=3;

0062 MEM(4)*RC=1;

0063 MEM(5:3)=2,2,3;

0064 MEM(8)*H1=1;

0065 MEM(8)*RC=1;

0066 MEM(9)=3;

0067 TR(IT)*RC=0;

0068 TR(IT)*TY=1;

0069 TR(IT)*PI=IA(MEM(0));

0070 BP8S(0),OP=IT;

0071 BP8S(0),C91=R=9;

0072 BP8S(0),BTY=0;

0073 OFS=HA(POS(1));

0074 DISPLAY DATA (IT,14,MEM(0:1),TR(0:3),BP8S(0:2),STK))

0075 IT=IT+LENGTH(TR);

0076 BP8S=FP=IT;

0077 TR(IT)*FD=HA(EM(4));

0078 TR(IT)*I=IA(EM(8)),

0079 TR(IT)*L1=1;

0080 TR(IT)*TY=1;

0081 TR(IT)*C=0;

0082 DISPLAY DATA (IT,14,MEM(0:1),TR(0:3),BP8S(0:2),STK))

0083 IT=IT+LENGTH(TR);

0084 30 TA RET;

0085 END INI;

0086 /**/

0087 /**/

/* OPERATEURS DIADRIJVES */

0087 PROCEDJE TD8P;

0088 DCL RET L 4J
0091 REGISTER TY1 (6) I W
0092 REGISTER TY2 (7) I W
0093 SAVE (LINK=RET)
0094 IF (OPS=LENGTH(OPS)) -> 8TY=-1 THEN CALL (LINK) DPFX
0095 ELSE BEGIN (TY1,TY2)
0096 TY1=TR(OPS->OP).TY;
0097 TY2=TR(OPS=LENGTH(OPS)) -> 6P).TY;
0098 CALL (LINK) TAR(OPS=LENGTH(OPS)) -> C61)
0099 END;
1000 OPS=OPS=LENGTH(OPS);
1001 OPS->8P=IT;
1002 I1=IT+LENGTH(TR);
1003 DISPLAY DATA (IT,14,MEM(0:1),TR(0:3),OPS(0:2),STK);
1004 GO TO RET;
1005 END TLP);
1006 /**/

C

1007 /**/ /* DECLARATIONS DES REGISTRES POUR LEUR OPTIMIZATION */

C
0108 PERCEJURE (8PDIA)
0109 REGISTER LIEN (8) L)
0110 DCL R,T,L W;
0111 REGISTER J (6) I W
0112 REGISTER K (5) I W
0113 REGISTER K9 (5) WP W;
0114 REGISTER DV1 (9) WP W;
0115 REGISTER DV2 (10) WP W;
0116 REGISTER DV3 (6) WP W;
0117 REGISTER I (7) I W;
0118 REGISTER D1 (9) I +1;
0119 REGISTER D2 (10) I W;
0120 REGISTER TY1 (6) I W;
0121 REGISTER TY2 (7) I W;
0122 /**/ 0123 /**/ /* TRATTEMENT DE PLUS ET MOINS */

C

0124 ENTRY PLUS;
0125 BEGIN (TY1,TY2);
0126 SAVE (LINK=RET);
0127 IF (TY1=4) (TY2=4) THEN GO TO ERTYP;
0128 IF (TY1=3) (TY2=3) THEN TR(IT).TY=3;
0129 ELSE TR(IT).TY=1;
0130 DISPLAY DATA (IT,14,MEM(0:1),TR(0:3),OPS(0:2),STK);
0131 GO TO L1;
0132 END;
0133 /**/ 0134 /**/ 0135
/* TRAITEMENT DES OPERATEURS DIADIGUES LAGIQUES */

ENTRY LOGDIA;

BEGIN (TY1,TY2);

SAVE (LINK=RET);

IF (TY1#=2) (TY2#=2) THEN GB TO ERTYP;

TR(IT).TY=2;

GB TO L1;

END;

C 0144 **/

C 0145 **/

/* TRAITEMENT DES OPERATEURS DE COMPARATION */

ENTRY CONDIA;

BEGIN (TY1,TY2);

SAVE (LINK=RET);

IF (TY1=4) (TY2=4) THEN GB TO ERTYP;

C 0151 **/

C 0152 **/

ENTRY EQUAL;

TR(IT).TY=2;

GB TO L1;

END;

C 0157 **/

C 0159 **/

/* TRAITEMENT DE MULTIPLICATION */

ENTRY MUL;

SAVE (LINK=RET);

CALL (LIEN) TTEST1;

GB TO L1;

C 0164 **/

C 0165 **/

/* TRAITEMENT DE RHO DIADIQUE */

ENTRY RHODIA;

BEGIN (TY1,TY2);

SAVE (LINK=RET);

IF TY1#=1 THEN GB TO ERTYP;

ELSE TH(IT).TY=2;

END;

C 0172 IF (A(TR(O))+EPS->DP)->PI->%1#1=1 THEN GB TO ERRK;

C 0174 IF (EPS=LENGTH(GPOS)) ->C91#RHO THEN GB TO L3;

C 0175 IF TR(GPS->DP):C1>=0 THEN CALL (LINK) GETVAL,PARAM->A(TR(O))+EPS->6PI;

C 0176 TR(IT).PI=TR(GPS->DP).PFD;

C 0177 (A(TR(O))+IT)->PI->RC=(A(TR(O))+IT)->PI->RC+1);

GB TO L2;

C 0179 **/

C 0180 **/
C 0181: /* TRAITEMENT DE TAKE ET DROP */
C 0182: BEGIN (DV1,DV2);
C 0183: L3:DV1=TR(OPS->OP).PFDJ
C 0184: DV2=TR((OPS->LE3TH(OPS))=>OP).PIJ
C 0185: IF DV1->MH1#DV2->MH1 THEN GO TO ERRKJ
C 0186: IF TR(OPS->OP).CI>0 THEN CALL (LINK) GETVAL,PARAM=WA(TR(0))+OPS->OPJ
C 0187: IF (OPS-LENGTH(OPS))=>C81=TRANS THEN GO TO TRANSPJ
C 0188: GMS=LO=DV1->MH1;
C 0189: CALL (LINK) GETDATA,PARAM=WA(GMS);
C 0190: Tr(1).PI=DATAJ
C 0191: /* */
C 0192: /**/      /* RESULTAT POUR TAKE */
C 0193: BEGIN (DV3,1);
C 0194: DV3=TR(1T).PIJ
C 0195: I=0J
C 0196: IF (OPS-LENGTH(OPS))=>C81=TAKE THEN GO TO L5J
C 0197: L4: I=I+1J
C 0198: DV3->JA(I)=ABS(DV1->DA(I));
C 0199: IF I<SV1->MH1 THEN GO TO L4J
C 0200: GO TO L2J
C 0201: /* */
C 0202: /**/      /* RESULTAT POUR DROP */
C 0203: C
C 0204: L5:=I+1J
C 0205: DV3->DA(I)=DV2->DA(I)=ABS(DV1->DA(I));
C 0206: IF I<SV1->MH1 THEN GO TO L5J
C 0207: GO TO L2J
C 0208: ENDJ
C 0209: /* */
C 0210: /**/      /* TRAITEMENT DE TRANSPOSITION DIADIQUE */
C 0211: C
C 0212: PROCEDURE TRANSPJ;
C 0213: DLL V J;
C 0214: REGISTER K (8) N J;
C 0215: BEGJ (DV3,1,K)J
C 0216: I=0J
C 0217: <=1J
C 0218: A1:=I+1J
C 0219: IF (DV1->MH1 THEN GO TO A2J
C 0220: ELSJ IF K=DV1->DA(I) THEN K=DV1->DA(I);
C 0221: GO TO A1J
C 0222: A2:=JG=L3EKJ
C 0223: CALL (LINK) GETDATA,PARAM=WA(GMS);
C 0224: DV3=DATAJ
C 0225: END
0226 I=0J
0227 A3:A=0:
0228 I=I+1;
0229 IF I>GM5.LG THEN GO TO A5.
0230 K=01
0231 A4:K=+1;
0232 IF K>DV1>MH1 THEN
0233 BEGIN
0234 IF A=0 THEN
0235 BEGIN
0236 CALL (LINK) FREEDATA,PARAM=W(A(GMS))
0237 GO TO ERRKJ
0238 ENDJ
0239 ELSE DV3->DA(I)=A1
0240 GO TO A3)
0241 END;
0242 IF I=DV1->DA(K) THEN
0243 BEGIN
0244 IF A= THEN A=DV2->DA(K)
0245 ELSE IF A>DV2->DA(K) THEN A=DV2->DA(K)
0246 ENDJ
0247 GO TO A4J
0248 A5:TR(IT).PI=DV3)
0249 ENDJ
0250 END TRANSPJ
0251 END;
0252 GO TO L2J
0253 /**/ 
0254 /**/ 
0255 
0256 ENTRY RGTJ
0257 SAVE (LINK=RET);
0258 BEGIN (TY1,TY2);
0259 IF TY1=1 THEN GO TO ERTYPJ
0260 ELSE I(R(IT).TY=TY2)
0261 ENDJ
0262 BEGIN (DV1,DV2);
0263 BEGIN (I,DI,02,J,K)
0264 DV1=T (UPS->GP).PI;
0265 DV2=T (GPS=LENGTH(GPSS))->GP).PI;
0266 I=(GP).LENGTH(GPSS)->IXJ
0267 IF DP=0 THEN GO TO ERRKJ
0268 IF I=0 THEN I=DV2>MH1)
0269 IF D1=0 THEN GO TO L6J
0270 IF DV1>MH1#=DV2->MH1-1 THEN GO TO ERRKJ
0271

J=0J

0272

K=0J

0273

L8:J=J+1;

0274

L7:K=+1;

0275

IF K>DV2->MH1 THEN G9 TO L6J

0276

IF K=1 THEN G8 TO L7J

0277

ELSE IF DV1->DA(J)=DV2->DA(K) THEN G8 TO ERR<;

0278

G8 TO L6J

0279

L6:TR(IT).C2=I

0280

ENDJ

0281

TK(IT).PI=DV2J

0282

DV2->C=DV2->RC+1J

0283

G8 TO L2J

0284

ENDJ

0285

**/ /

0286

**/ /

C

0287

ENTRY CATJ
SAVE (LINK=RET);
0288
0290
CALL (LJEN) TTFST1J
0291
BEGIN (DV1,DV2,D1,D2,I,K0);
0292
D1=TR(8DS->8P).PIJ
0293
DV2=TR((8PS-LENGTH(8POS))->8P).PIJ
0294
0295
I=(8PS-LENGTH(8POS))->IXJ
0296
IF (D1=0J)(D2=0J) THEN
BEGIN;
0297
IF (D1=0J)(DV2->MH1#=1) THEN G8 TO ERRKJ
0298
IF (D2=0J)(DV1->MH1#=1) THEN G8 TO ERRKJ
0299
G=S.LH=1J
0300
CALL (LINK) GETDATAJ PARAM=MA(GMS)J
0301
K5=DATAJ
0302
IF (D1=0J)(D2=0J) THEN K9->DA(1)=2J
0303
ELSE IF D1=0 THEN K9->DA(1)=1+DV2->DA(1)
0304
ELSE K9->DA(1)=1+DV1->DA(1)
0305
TK(IT).PI=K0J
0306
G8 TO L9J
0307
ENDJ
0308
IF DV1->MH1#=DV2->MH1 THEN G8 TO ERRKJ
0309
IF I=0 THEN I=DV2->MH1J
0310
BEGIN (K)J
0311
K=0J
0312
L1=K=K+1J
0313
IF DV1->DA(K)=DV2->DA(K) THEN G8 TO ERRKJ
0314
IF K=DV1->MH1 THEN G8 TO L10J
0315
ENDJ

0316

ENDJ
C

0361

BEGIN (DV1, DVP1D1,D2);

0362 L1:DV1:=TR(OPS->OP).PI;

0363 DV2:=TR((OPS=LENGTH(OPS))=>OP).PI;

0364 IF (D1=0) (D2=0) THEN TR(IT).PI1=0;

0365 ELSE BEGIN;

0366 IF D1=0 THEN TR(IT).PI:=DV2;

0367 ELSE IF D2=0 THEN TR(IT).PI:=DV1;

0368 ELSE IF DV1->M41=DV2->M41 THEN TR(IT).PI:=DV1;

0369 ELSE IF ERRK;

0370 (44/TR(O))+IT);>PI->RC=(A/TR(O))+IT);>PI->RC+1;

0371 DISPLAY DATA (IT,IM,MEM(0:1),TR(0:3),OPBS(0:2),STK);

0372 END;

0373 END;

0374 END;

0375 /**/

C

0376 C377 /* REMPLISSAGE DU NIVEAU DE L'ARRETE */

0378 L2:TR(OPS->OP).RC:=TR(OPS->OP).RC+1;

0379 TR((OPS=LENGTH(OPS))=>OP).RC:=TR((OPS=LENGTH(OPS))=>OP).RC+1;

0380 TR(IT).ALPH=OPS->OP;

0381 TR(IT).GETA=(OPS=LENGTH(OPS))=>OP;

0382 TR(IT).C1=(OPS=LENGTH(OPS))=>C91;

0383 DISPLAY DATA (IT,IM,MEM(0:1),TR(0:3),OPBS(0:2),STK);

0384 GO TO RET;

0385 END MEDIA;

0386 PROCEDURE TEST1;

0387 REGISTER LIEN (8) L WJ;

0388 REGISTER TY1 (9) I WJ;

0389 REGISTER TY2 (10) I WJ;

0390 BEGIN (TY1,TY2,LIEN);

0391 IF (TY1=4) (TY2=4) THEN TR(IT).TY=4;

0392 ELSE BEGIN;

0393 IF (TY1=2) (TY2=2) THEN TR(IT).TY=2;

0394 ELSE BEGIN;

0395 IF (TY1=4) (TY2=4) THEN GO TO ERTYP;

0396 ELSE IF (TY1=3) (TY2=3) THEN TR(IT).TY=3;

0397 ELSE TR(IT).TY=1;

0398 END;

0399 GO TO LIEN;

0400 END;

0401 END TEST1;

0402 /**/

0403 /**/
0.0A REGISTER LIEN (8) LJ
0.07 REGISTER I (7) I WJ
0.08 REGISTER J (6) I WJ
0.09 REGISTER K (5) I WJ
0.10 REGISTER DV1 (9) W P WJ
0.11 DCL FC MP A
0.12 BEGIN (I,J,K,DV1,LIEN);
0.13 FD=TR(8PS->8P).PFD+LENGTH(MEM);
0.14 J=0;
0.15 K=1;
0.16 L1:=K+1;
0.17 IF FD->DB(K)=X11' THEN J:=J+1;
0.18 IF (K+1)#=DV1->0A(1) THEN G6 TO L1;
0.19 GO TO LIEN;
0.20 END;
0.21 END T9TE1;
0.22 **/;
0.23 **/;
0.24 PROCEDURE TITI;
0.25 REGISTER LIEN (8) LJ
0.26 REGISTER DV2 (10) W P A;
0.27 BEGIN (L1=0,DV2);
0.28 IF TR(8PS->8P).C1>0 THEN CALL (LINK) GETVAL,PARAM=WA(TR(8PS->8P));
0.29 GNS.LG=DV2>MH1;
0.30 CALL (LINK) GETDATA,PARAM=WA(JMS);
0.31 MOVE RIGHT (DV8+LENGTH(MEM),DATA+LENGTH(MEM),(DV2>MH1)*LENGTH(MEM));
0.32 GO TO LIEN;
0.33 END;
0.34 END TITI;
0.35 **/;
0.36 **/;
0.37 **/;
0.38 PROCEDURE DFEA;
0.39 END DFEA;
0.40 PROCEDURE FARN;
0.41 END E4RJ;
0.42 PROCEDURE FRTYP;
0.43 END EBTYP;
0.44 PROCEDURE GETVAL;
0.45 END GETVAL;
0.46 **/;
0.47 **/;
0.48 **/;
0.49 PROCEDURE GETDATA;
0.50 DCL RET L A;

/* SOUSPROGRAMME UTILISE DANS TRAITEMENT DE COMPRESS */

/* PROCEDURES QUI NE SONT PAS ENCORE PROGRAMMEES */

/* PROCEDURE DE GESTION DE MEMORE */
C451 DCL AGG WP *1
C452 FERI DATA *P:
C453 SAVE (LINE=RET,PARAM=ARG)
C454 NEW(I)*.RC=1
C455 NEW(J)*.HMI=ARG>LG
C456 AVG->ATA=4(NEW(I4))
C457 F1=M+1+ARG>LG;
C458 G9 TB RT;
C459 END GTDATA;
C601 /*/ PRGDURE FREEDATA;
C602 END FREEDATA;
C603 END ESSAI;

/* PROCEDURE NON PROGRAMMÉE */
ANNEXE C- CODE INTERNE DES SYMBOLES APL

Pour les caractères alphabétiques et numériques, le code est le code EBCDIC.
Le code interne des autres symboles est donné ici :

<table><thead><tr><th>Caractère APL</th><th>Code</th><th>Caractère APL</th><th>Code</th></tr></thead><tbody><tr><td>'</td><td>39</td><td>=</td><td>80</td></tr><tr><td></td><td></td><td>‡</td><td>81</td></tr><tr><td></td><td>40</td><td>&gt;</td><td>82</td></tr><tr><td>←</td><td>41</td><td>≥</td><td>83</td></tr><tr><td>→</td><td>42</td><td>&lt;</td><td>84</td></tr><tr><td>-</td><td>43</td><td>≤</td><td>85</td></tr><tr><td>.</td><td>44</td><td>V</td><td>86</td></tr><tr><td>□</td><td>45</td><td>¶</td><td>87</td></tr><tr><td>□</td><td>46</td><td>^</td><td>88</td></tr><tr><td>:</td><td>47</td><td>¶</td><td>89</td></tr><tr><td>o</td><td>48</td><td>~</td><td>8A</td></tr><tr><td>∇</td><td>49</td><td></td><td></td></tr><tr><td>I</td><td>4A</td><td>p</td><td>90</td></tr><tr><td></td><td></td><td>θ</td><td>91</td></tr><tr><td>;</td><td>50</td><td>,</td><td>92</td></tr><tr><td>(</td><td>52</td><td>¶</td><td>93</td></tr><tr><td>)</td><td>53</td><td>Φ</td><td>94</td></tr><tr><td>[</td><td>58</td><td>/</td><td>95</td></tr><tr><td>]</td><td>59</td><td>\</td><td>96</td></tr><tr><td>+</td><td>70</td><td>↑</td><td>97</td></tr><tr><td>-</td><td>71</td><td>↓</td><td>98</td></tr><tr><td>×</td><td>72</td><td>✓</td><td>99</td></tr><tr><td>÷</td><td>73</td><td>×</td><td>9A</td></tr><tr><td>*</td><td>74</td><td>l</td><td>A0</td></tr><tr><td>L</td><td>75</td><td>ε</td><td>A1</td></tr><tr><td>Γ</td><td>76</td><td>□</td><td>A2</td></tr><tr><td>|</td><td>77</td><td>?</td><td>A3</td></tr><tr><td>o</td><td>78</td><td>▲</td><td>A4</td></tr><tr><td>⊗</td><td>79</td><td>Ψ</td><td>A5</td></tr><tr><td></td><td></td><td>⊥</td><td>A6</td></tr><tr><td></td><td></td><td>⊤</td><td>A7</td></tr></tbody></table>