Inw=02955 RR224

IRIA

laboria

Institut de Recherche
d'Informatique
et d'Automatique

Domaine de Voluceau
Rocquencourt
B. P. 105 78150 - Le Chesnay
France
Tél.: 954 90 20

laboratoire de recherche
en informatique
et automatique

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

# DÉFINITION ET IMPLANTATION
DE LISP
A L'AIDE
D'UN COMPILATEUR

Pierre DERANSART

Rapport de Recherche N° 224

Mars 1977

105 p
# DÉFINITION ET IMPLANTATION DE LISP
A L'AIDE D'UN COMPILATEUR

Pierre Deransart

## Résumé :

Ce rapport présente une méthode de définition et d'implantation d'un système Lisp à l'aide d'un compilateur défini par la méthode des attributs sémantiques. Un sous-ensemble compilable de Lisp est déterminé et le code objet est un langage intermédiaire. Un évaluateur écrit en Lisp compilable permet le boostraping du système.

## Abstract :

This paper presents a method for definition and implementation of a Lisp system, using a compiler defined by the method of semantic attributes. A compilable subset of Lisp is determined and an intermediate language is used as object code. An evaluator written in compilable Lisp permits the bootstraping of the system.

## Mots clés :

Lisp - Implementation - Compiler - Semantic attributes - Intermediate language - Bootstraping.

Lisp - Implementation - Compiler - Semantic attributes - Intermediate language - Bootstraping.
<figure><img src="image_2.png" /></figure>
TABLE DES MATIERES

SECTION 1 : Lisp compilable

I. Eléments d'un système Lisp

1. Données générales : atomes et S-graphes

1) Bigraphe

2) S-graphe et représentation

3) S-expressions.

2. Syntaxe des S-expressions

3. Valeur d'une S-expression ou forme

4. Détermination du sous-langage

1) Affectation du sous langage

2) Types de fonctions

3) Mode de passage des paramètres et effets de bord.

5. Système Lisp

1) Système

2) Sous-système choisi

II. Evaluation et définition par un compilateur

1. L'évaluateur de référence

2. Sous-ensemble compilable : syntaxe du sous-langage

3. Extensions : syntaxe de Lisp

SECTION 2 : Définition d'un compilateur Lisp à l'aide des attributs sémantiques

I. Choix d'une machine abstraite, code objet

1. Machine avec aliste

2. Machine à piles de liens

3. Autre machine

4. Code objet

5. Du code objet à une machine réelle.

II. Traduction

1. Les attributs

2. Le langage sémantique

3. Traduction
### III. Optimisations

1. Choix des optimisations

2. Optimisation des "POPn" successifs

3. Suppression de la récursion dans un cas simple.

4. Conclusion.
## Introduction

Ce rapport étudie deux aspects concernant le langage Lisp : sa définition et son implantation et propose une méthode d'implantation. La définition de la plupart des systèmes existants consiste à proposer une large liste de fonctions et à en décrire l'effet sur les arguments. Ainsi, par exemple, la fonction APPEND sera définie :

(APPEND L1, L2) L1 et L2 listes

Valeur de la forme : Liste composée des contenus concatenés. Cette définition doit être complétée par celle d'un évaluateur d'expressions du langage formées en composant des formes semblables à celle ci-dessus.

Une première constatation s'impose lorsque l'on regarde les évaluateurs de différents systèmes Lisp (Lisp 1.5 [1], V-Lisp [5], Interlisp [4]) leur descriptions sont extrêmement variées. Il n'est que de constater la disparité des fonctions ou mots-clés testées explicitement dans l'évaluateur présenté.

Ainsi : LISP 1.5 du MIT (1962) teste en priorité : QUOTE, FUNCTION, FUNARG, COND, PROG, LABEL, LAMBDA (les 5 fonctions de base sont traitées comme les autres).

LISP 1.5 présenté par D. Ribbens (1969) teste : QUOTE, FUNCTION, FUNARG, COND, LABEL, LAMBDA. D'autres fonctions telles que PROG sont introduites en dehors de l'interpréteur.

Dans les systèmes plus récents tels que Interlisp ([ 4 ]), la forme LABEL n'est plus utilisée et les seuls mots-clés testés sont : FUNARG, LAMBDA et NLAMBDA.

Cette dernière méthode de définition a l'avantage de faire sortir pratiquement de l'autodéfinition du langage, mais reste encore imprécise au niveau de l'implantation. En effet l'exposé en "langue naturelle" de l'effet d'une fonction ne prévoit pas toujours tous les cas possibles et de plus cet "effet" peut dépendre de différences d'implantations spécifiques à chaque système.

Ainsi la définition de EQ (égalité de pointeurs) et DIFFERENCE (soustraction de deux entiers) ne suffit pas à éviter une erreur de programmation consistant à écrire

(EQ 3 (DIFFERENCE 5 2))
qui est en général faux.
Par ailleurs l'évaluation d'une expression telle que

(LAMBDA(X Y) (PLUS X Y)) (SETQ X 2) X)

dépend de l'implantation. En effet, si l'on se réfère à un évaluateur avec aliste explicite (évaluateur de Lisp 1.5 par exemple) les deux arguments sont évalués avec le même contexte. Le résultat de l'expression est donc, si X vaut 1 : 2 + 1 = 3. En général il n'en est rien en raison de l'effet de bord introduit par SETQ et de l'évaluation de gauche à droite des arguments, X étant modifié par l'affectation SETQ. Le résultat est alors 4.

Une autre constatation s'impose : la plupart des systèmes utilisent les mêmes fonctions avec les mêmes noms qui sont en quelque sorte des "mots clés" du langage. Bien qu'en pratique ceux-ci soient modifiables, peu de programmeurs ou d'implanteurs s'y risquent afin de conserver un minimum de portabilité des programmes.

Ces constatations nous ont amené à penser qu'il était possible et intéressant de définir Lisp à l'aide des éléments suivants :

- une syntaxe minimale décrivant un sous-langage Lisp, implanté dans une machine abstraite, appelé "Lisp compilable".

- un évaluateur, définissant les extentions du langage (avec une nouvelle syntaxe décrivant les formes les plus générales qui peuvent être écrites). L'évaluateur lui-même peut être écrit en Lisp compilable.

- un compilateur décrivant l'implantation, dans la machine abstraite du Lisp compilable. Comme l'évaluateur peut être lui-même compilé, ceci permet de décrire l'implantation d'un système Lisp.

Ce rapport expose cette démarche en définissant un tel compilateur à l'aide des attributs sémantiques [14]. Cette démarche présente les avantages suivants :

- définition explicite, tenant compte d'une implantation.

- le code objet choisi reste à un niveau intermédiaire entre le langage lui-même et le code machine réelle. Il permet de comprendre l'effet des fonctions décrites d'une part et il peut servir de première étape de traduction pour une implantation particulière d'autre part.
- compte tenu des remarques qui précèdent et de la définition de l'évaluateur en Lisp compilable, le compilateur permet l'implantation rapide d'un système Lisp et donc sa portabilité.

- enfin la séparation entre la syntaxe et l'évaluateur met clairement en évidence les aspects syntaxiques et interprétés du langage.

Le rapport est divisé en deux sections : la première définit le sous-ensemble de Lisp compilable que nous voulons décrire. Un ensemble restreint mais significatif pour une définition du langage est sélectionné.

La seconde décrit la machine abstraite et le compilateur, puis traite des optimisations qui permettent d'envisager un bootstrapping efficace de l'évaluateur.

Les travaux exposés ici font l'objet d'une réalisation expérimentale sur CII-IRIS 80 en cours actuellement.
Définition de Lisp à l'aide d'un compilateur

Définition d'un sous-ensemble du langage.

# 1. Eléments d'un système Lisp

La plus grande variété existe dans ce domaine : chaque implanteur en fait définit un Lisp souvent adapté à ses contraintes d'implantation ou d'application. Le plus ancien (Lisp 1.5 du MIT [1] [2]) sert fréquemment de référence. D'autres (Maclisp [3] ou Interlisp [4]) introduisent de nouvelles possibilités, d'autres s'adaptent à la machine ([5] sur T1600) en introduisant un Lisp "simplifié" - dans ce cas en supprimant la distinction formelle entre contextes global et local - d'autres encore recherchent la portabilité ([6] et [7] en FORTRAN). Cette grande variété, encore compliquée par l'existence de gros systèmes constituant des sortes d'hyper-extensions de Lisp (Conniver [8], Planner [9], Reduce [10]...), entraîne la quasi impossibilité de parler d'un Lisp "standard". Une telle standardisation est encore bien loin de se faire, bien que souhaitable du point de vue de la portabilité des gros programmes d'application.

Le choix d'un Lisp relève donc de critères pratiques plus que théorique et, puisqu'il s'agit ici de décrire une implantation dans une machine abstraite, la référence au Lisp 1.5 traditionnel avec quelques modifications, nous a paru la manière la plus simple d'aborder cette description. Le langage considéré possède par rapport à Lisp 1.5 deux types de modifications :

- Simplification : pas d'argument "function" et bien sûr toutes les fonctions utilitaires ne seront pas traitées.

- Ajouts : fonctions de type F... (n'évaluant pas leurs arguments).

## 1.1 Données générales : atomes et S-graphe

Nous nous contentons de reprendre ici des notations connues dont l'essentiel est exposé dans [11], et nécessaires pour la compréhension du rapport.
### 1.1.1 Bigraphe

Un bigraphe est une classe de S-graphes définie par :

- 2 ensembles : A (Atomes) et C (Cellules)

- 2 applications de C dans A × C : car et cdr.

Exemple :

$$A = \{3\}$$

$$C = \{1,2\}$$

<figure><img src="image_3.png" /><figcaption>Fig 1. Bigraphe car, cdr</figcaption></figure>

L'ensemble des noeuds connectés à un noeud n donné est défini récursivement comme suit : ($n \in A \cup C$)

$$E(n) = \underline{\underline{\text{si } n \in A}}$$

$$\underline{\underline{\text{alors } \{n\}}}$$

$$\underline{\underline{\text{sinon } \{n\}}} \cup E(\text{car}(n)) \cup E(\text{cdr}(n))$$

$$\underline{\underline{\text{fsi}}}$$

### 1.1.2 S-graphe et représentation

Un S-graphe de racine r est défini par :

- sa racine $r \in A \cup C$

- le sous-graphe complet ayant ses noeuds dans $E(r)$.

La représentation usuelle se fait à l'aide de cellules doubles (fig. 2) :

<figure><img src="image_4.png" /><figcaption>Fig 2. Cellule</figcaption></figure>

C : désigne un pointeur sur une cellule

CAR : pointeur 'car

CDR : pointeur 'cdr'

Un atome sera représenté par un pointeur sur une chaîne (fig. 3) :

<figure><img src="image_5.png" /><figcaption>Fig 3. Atome</figcaption></figure>

Ainsi dans l'exemple ci-dessus le S-graphe de racine 1 extrait du bigraphe de la figure 1 est :
<figure><img src="image_6.png" /><figcaption>Fig 4. Représentation du S-graphe de racine 1 (fig.1)</figcaption></figure>

Exemple 2 :

<figure><img src="image_7.png" /><figcaption>Fig 5. Représentation de la liste circulaire (A B C)</figcaption></figure>

### 1.1.3 S-expressions

Certains S-graphes, les S-graphes sans circuit, peuvent être représentés par une expression linéaire — dite S-expression et noté $S-expr$ — à l'aide de **paires-pointées** :

<figure><img src="image_8.png" /><figcaption>Fig 6. Représentation de S-expressions</figcaption></figure>
La notation en paires pointées - ou dot-pair - est associative à droite pour donner une notation de liste.

Ainsi :

(C:nil) ← (C)
(B.(C:nil)) ← (B.(C)) ← (B C)
(A.(B.(C:nil))) ← (A.(B.(C))) ← (A.(B C)) ← (A B C)

Soit en général :

(A.(L)) (A L) où L est une suite quelconque d'atomes.

Dans cette notation, on voit que nil est équivalent à ( ) (liste vide).
En Lisp usuel il n'y a pas de distinction entre l'atome 'nil' et la liste
vide '( )', utilisée aussi comme valeur 'faux'.

On voit également que le passage d'un S-graphe à une S-expression n'est
pas univoque. Toutes les données étant visualisées sous forme de S-expres-
sion, ceci pose un problème puisque toutes les données internes sont sous
forme de S-graphe. Ce problème est résolu en utilisant un algorithme de
sortie éditant la S-expression la plus courte (cf. [11]).

1.1.4 Atomes

Les objets d'un système Lisp sont donc les atomes, organisés dans une
"liste d'objets" que nous considérons comme une "table des atomes", et les
S-graphes dont les atomes sont un cas particulier.

Il y a cependant plusieurs catégories d'atomes, en particulier :

- les chaînes représentant des variables, des constantes, des fonctions ou des valeurs.

- les nombres. Traités différemment en général, nous les considè-
rerons ici comme des atomes ordinaires (constantes).

- les booléens : deux atomes particuliers à valeur constante :
  nil et t (true) traités également comme des constantes.

1.2 Syntaxe des S-expressions

Telles que définies au § 1.1.3 les S-expressions ont la syntaxe suivante :

<S-expr> = Ident | ( ) | (<contenu de liste>) | (<c. de paire pointée>)
<contenu de liste> = <S-expr> | <S-expr> <contenu de liste>
<c.paire pointée> = <S-expr> . <S-expr>
Toute "phrase" du langage est écrite selon cette syntaxe qui rend compte du mélange des notations pointée et liste ainsi que de la parité des parenthèses.

### Exemples d'expression

```
(COND((EQ L NIL)NIL) (T(REVERSE L)))
((SETQ LIST X) (QUOTE(A.B)))
```

## 1.3 Valeur d'une S-expression ou forme

Toute S-expression Lisp a une **valeur** qui est le résultat de l'évaluation de cette S-expression, appelée aussi **forme**.

### Exemple :

```
la forme : (CAR(QUOTE(A.B))) a pour valeur A
```

```
la forme : (SETQ LIST X) a en général pour valeur celle de X.
```

La valeur dépend bien sûr de l'état du système. Ainsi:

(X X) n'a pas de valeur en général, mais seulement dans le cadre d'un calcul particulier (X variable) ou d'un système particulier (X fonction définie du système).

Les **valeurs des expressions simples** parmi les plus courantes en Lisp sont données en annexe 1. On y distingue:

- valeur des constantes : t, nil, lpar, blank...

- valeur des fonctions arithmétiques : (PLUS 1 2 3)

- valeur des prédicats simples : (EQUAL X Y)
ou composés : (AND (EQ X Y) (EQ Z T))

- valeur des fonctions manipulant des listes : LENGTH L)

- valeur des fonctions de base : CAR, CDR, CONS,...

- valeur des fonctions utilitaires du langage : (EVAL1, S-expr)

- valeur des fonctions **définissant** le langage : (QUOTE S-expr)

parmi lesquelles se trouvent l'atome LAMBDA (souvent noté ici $\lambda$ pour abréger l'écriture) ou FLAMBDA (respectivement $f\lambda$) dont l'expression n'a pas de valeur.

Certaines expressions n'ont pas de valeur, cela dépendant des systèmes et de l'usage, bien qu'en général l'absence de valeur correspond à une erreur détectée.
Exemples en Lisp-CMS [12] :

(CSETQ(QUOTE X)) (1) pas de réponse
(GET(QUOTE EQ) (QUOTE SUBR)) (2) pas de réponse

La réponse dépend bien sûr du système considéré.

L'ensemble de ces fonctions simples constitue la base servant à définir le langage.

## 1.4 Détermination du sous-langage

Nous allons examiner quelques aspects du langage, donc certaines fonctions Lisp, de manière à expliciter les choix effectués pour le langage à définir.

### 1.4.1 Affectation et listes de propriétés

L'affectation en Lisp 1.5 se fait à deux niveaux :

- niveau global en créant des constantes (type APVAL)
  (affectation de variables globales)

- niveau local en affectant une variable.

Les fonctions d'affectations sont : CSET et CSETQ pour affecter au niveau global et SET et SETQ au niveau local.

(SET S-expr1 S-expr2) évalue S-expr1 dont le résultat doit être un atome auquel on affecte le résultat de l'évaluation de S-expr2.

(SETQ Ident S-expr2) donne le même résultat, mais la variable à affecter est connue.

La valeur d'une constante est souvent notée sous l'indicateur APVAL de la p-liste. Celle-ci est composée d'une liste de doublets de la forme : (indicateur.valeur). Celle-ci permet d'attacher à un atome toutes sortes de propriétés.

La manipulation de la p-liste se fait par fonctions utilitaires :

GET, GETP, PUTPROP, REMPROP

**Exemple :**

(PUTPROP 'FRANCE 'CAPITALE 'PARIS) qui crée la propriété CAPITALE avec pour valeur PARIS à l'atome FRANCE.

(1) Cette forme, erronnée n'est pas rejetée par Lisp CMS mais ne produit aucun résultat.

(2) Cette forme vise à rechercher l'indicateur sans résultat éditable, d'un atome qui est une fonction compilée. L'erreur n'est pas signalée par Lisp CMS.
La liste de propriétés pouvant être manipulée par des fonctions Lisp usuelles nous nous contentons de la signaler sans la traiter par la suite.

## 1.4.2 Types de fonctions

Nous distinguerons 4 types seulement :

* EXPR : fonction définie par une S-expression pour laquelle les arguments fournis sont auparavant évalués.

* FEXPR : id mais les arguments sont passés sans évaluation.

* SUBR : id types précédents, mais les fonctions sont compilées

* FSUBR : ou écrites en code objet.

Notons qu'une fonction EXPR est normalement définie par une λ-expression ou une S-expression dont l'évaluation a pour résultat une fonction EXPR ou SUBR ou une λ-expression. De même pour FEXPR (fλ-expression ou FEXPR ou FSUBR).

## 1.4.3 Mode de passage des paramètres et effets de bord

Traditionnellement on considère que c'est un *passage par valeur*. Ceci est vrai si la fonction ne contient aucune *pseudo-fonction susceptible d'affecter les valeurs des paramètres*. Dans la pratique ces pseudo-fonctions (comme NCONC, CSETQ, DEFINE...) sont très utilisées. Il semble plus réaliste de considérer qu'il s'agit d'un passage par référence, un paramètre pointant habituellement sur des cellules parfois communes à des variables définies dans le bloc englobant. Toute modification de cette valeur entraîne dans ce cas, la même modification sur la variable externe.

**Exemple :**

<figure><img src="image_9.png" /></figure>
Cette opération de concaténation entraîne la même modification pour X et pour L1 qui ne représente plus la même liste à la 2ème utilisation.

L'argument quoté quelconque introduit un éventuel effet de bord :
il suffit que l'une des variables libres qu'il contient soit redéfinie dans un bloc plus interne à l'intérieur duquel il est utilisé.

**Exemple** : fonction donnant pour résultat la somme de ses arguments.

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

Le résultat est 8 au lieu de 6 !

Cet effet intervient aussi avec un argument fonctionnel dès que la fonction de l'argument a des variables libres. Afin d'éviter tout risque, certains systèmes ([1], [3]) proposent une fonction FUNCTION indiquant que l'on veut préserver le contexte local d'évaluation de cette fonction.

Les manières d'implanter cette fonction étant extrêmement variées nous ne la considérerons pas ici.

De plus, un argument fonctionnel ne permet en général pas de prévoir le type de la fonction. Il n'y aura donc pas d'argument fonctionnel en Lisp compilable.

## 1.5 Système Lisp

### 1.5.1 Système

Un système Lisp fonctionnant en mode interactif possède un ensemble de fonctions servant d'interface entre le système et l'utilisateur.

Ce sont en particulier :

- les fonctions d'entrée/sortie : READ, PRINT, TERPRI...

- les fonctions de manipulation et sauvegarde du système :
  OBLIST, SAVE...

- le ramasse miettes en "garbage collector" qui remet dans la mémoire disponible les cellules non utilisées chaque fois que le besoin s'en fait sentir (plus de cellule disponible par exemple).
- les aides à la mise au point de fonctions ou de programmes (EDITEUR) et les traitements d'erreur.

Par ailleurs un système Lisp contient différentes catégories de fonctions que nous pouvons classer selon leurs possibilités de représentation dans le système. Une première catégorie comprend les fonctions qui ne peuvent être décrites qu'en termes littéraux ou, méthode que nous voulons utiliser, en termes des primitives de la machine abstraite. Ce sont par exemple des fonctions telles que ATOM, CAR, CDR, CONS, EQ, COND, PROG, QUOTE, LABEL, READ, WRITE, GETP, GET... Cette catégorie comporte outre les fonctions de base d'un système toutes celles qu'il faut programmer pour implanter un système Lisp. Les fonctions de cette catégorie, par définition, sont décrites en termes de primitives ou d'appels à d'autres fonctions de cette catégorie. Certaines d'entre elles se réduisent à une primitive (ATOM, READ...), leur type est, selon le cas SUBR (ATOM, CAR, ... READ...) ou FSUBR (COND, PROG...). Les fonctions FSUBR sont en général celles qui définissent explicitement le format de leurs arguments. Du point de vue syntaxique celles-ci permettent de faire plus de contrôles à la compilation que les autres pour lesquelles, si des contrôles doivent être faits, ils ne pourront être que dynamiques.

La seconde catégorie de fonctions correspond à celles qui, exprimées par une $\lambda$-expression, peuvent être compilées ; c'est-à-dire celles qui sont soit de type EXPR (FEXPR) soit SUBR (FSUBR). L'appartenance à cette catégorie dépend du critère de compilabilité qui est adopté. Le critère très restrictif que nous définissons au paragraphe 2 permet d'introduire dans cette catégorie la plupart des fonctions usuelles, mais surtout laisse la possibilité d'écrire un évaluateur général permettant d'évaluer des expressions de la 3ème catégorie.

La troisième catégorie comprend les fonctions qui, exprimées par une $\lambda$-expression ne sont pas compilables, comme par exemple MAPLIST, le critère de compilabilité interdisant les arguments fonctionnels.

Les deux premières catégories ne sont pas disjointes, ainsi que le montre la figure 7. :

<figure><img src="image_11.png" /><figcaption>Fig 7 : catégories des fonctions d'un système Lisp.</figcaption></figure>
Sur la figure 7 apparaît en tiretés l'ensemble union des catégories 1 et 2 qui est l'ensemble des fonctions exprimables en termes de primitives et d'elles-mêmes partant ou non d'une λ-expression. Dans la mesure où il est possible de mettre un évaluateur d'expressions les plus générales dans cette catégorie, il est possible d'implanter un Lisp sur la machine abstraite considérée.

Il reste donc à définir l'ensemble des fonctions de la catégorie 1.

## 1.5.2 Sous-système

Le choix des fonctions du sous-système est obtenu avec les deux critères suivants :

1) couvrir un ensemble significatif de fonctions définissant le langage Lisp.

2) permettre la compilation de l'évaluateur de référence sans aliste(1) explicite tel que celui fourni en Annexe 2B.

On obtient le choix suivant :

**Fonctions FSUBR** (ayant un rôle "syntaxique") :

QUOTE, COND, PROG, GO, SETQ, CSETQ, OR, AND, LIST, TIMES, PLUS.

**Fonctions SUBR**

CAR, CDR, CONS, EQ, ATOM, EXEC, EXEC1, NEQ, NULL, PRINT, READ, ASSOC1, GET, GETP, NUMBERP, ZEROP, DIFFERENCE.

**Autres fonctions** :

Le sous-système doit contenir d'autres fonctions lui donnant toute sa puissance du point de vue langage, les unes étant compilables (incluant un évaluateur), les autres étant susceptibles d'être évaluées par l'évaluateur.

**Ce sont** :

EVAL, APPLY, EVLIS, PAIRLIS, ASSOC, EXEC qui servent à définir un évaluateur avec aliste explicite (cf. Annexe 2A), lequel est susceptible d'être écrit avec uniquement les fonctions ci-dessus.

<footnote>(1) cf. définition de la aliste au § 2.1.</footnote>
EVAL, APPLY1, EVLIS1, PUSH, PUSHL1, POPL1, EXEC1, PUSHL, POPL, ASSOC1 correspondent à un évaluateur sans aliste explicite.

Toutes ces fonctions sont de type SUBR.

Ce sous-système sera mis en oeuvre par une commande LISP à implanter
que nous ne considérerons pas ici, mais que nous pouvons décrire par la
fonction compilable suivante :

(PROG(U) 1 (SETQ U (READ))
(COND((EQ U (QUOTE '*FIN)))
(RETURN(QUOTE '*STOP))))
(PRINT(EVAL1 U ))
(GO 1))

READ lit un fichier non précisé ici.

Cette commande ne figure bien sûr pas dans les fonctions, mais sa
description en Lisp compilable prouve que le système est entièrement décrit
avec le compilateur introduit en section 2.

La liste complète des fonctions du sous-système est reproduite dans
la syntaxe de l'annexe 3, règles 10 à 39, 44 et 45.

Nous n'avons pas fait allusion au cas des fonctions qui traitent
leurs arguments en liste (no-spread functions de Interlisp [4]). Ces
fonctions sont admises par l'évaluateur de référence mais non par le
compilateur.

Enfin il faut signaler que ce type de description suppose que le
système fonctionne en mode eval et non en mode evalquote, c'est-à-dire
que l'on fournit des formes à évaluer et que les arguments de ces
formes seront au préalable évalués.
## 2. Evaluation et définition par un compilateur

### 2.1 L'évaluateur de référence et la grammaire associée

L'évaluateur est détaillé à l'Annexe 2-A : évaluateur avec aliste explicite. En Annexe 2-B est écrit un évaluateur équivalent sans aliste explicite. Ce dernier montre que l'on peut définir un évaluateur compilable dans le langage de commande de la machine abstraite de la section 2 et qu'un système Lisp peut donc être implanté de cette manière. Le fonctionnement de deux évaluateurs est très voisin et nous expliquons ici le fonctionnement du premier.

La aliste est une liste d'association des variables, composée de couples eux-mêmes composés du nom d'une variable et de sa valeur. Lorsqu'une variable est définie dans une λ-expression, cette aliste est incrémentée par la gauche avec le couple correspondant à cette variable et l'argument correspondant (évalué ou non). La aliste croît toujours par la gauche. Lorsque l'on recherche la valeur d'une variable dans la aliste, le premier couple rencontré en parcourant la aliste de la gauche vers la droite, (fonction ASSOC) qui a pour élément gauche cette variable, fournit la valeur de cette variable, donnée par son élément droit.

**Exemple :**

```lisp
aliste = ((X.1) (Y.(A.B)) (Z.X) (X.(A.Y)))
```

valeur de Z : X

valeur de X : 1

La aliste correspond aussi à un passage de paramètres par référence car l'élément droit est en général un pointeur sur la valeur. Ainsi, dans la aliste de l'exemple, le couple de la variable Y est composé de Y et un pointeur sur le S-graphe (A.B).

L'évaluateur fonctionne alors comme suit :

Deux fonctions, eval et apply, sont les éléments principaux de l'évaluateur : la fonction eval évalue une forme, c'est-à-dire une liste dont l'élément de tête est une fonction et le reste ses arguments, dans le contexte de la aliste et du système. La fonction apply "applique", à une fonction fournie en argument, les arguments - supposés prêts à être utilisés (évalués dans le cas d'une fonction SUBR, non dans le cas contraire) et groupés dans une liste - dans le contexte de la même aliste qui a servi à traiter les arguments.
Exemple 1 :

<table><tr><td>Forme évaluée</td><td>:</td><td>((LAMBDA(X) (X X)) (QUOTE LIST))</td></tr><tr><td>Fonction appliquée</td><td>:</td><td>(LAMBDA(X) (X X))</td></tr><tr><td>Liste d'arguments</td><td>:</td><td>(LIST) (après évaluation)</td></tr></table>

L'évaluateur auquel on a fourni en fait un S-graphe comme argument analyse ce qui est supposé être une forme et distingue les cas suivants :

a) Forme réduite à un atome : le résultat est la valeur de la constante ou la valeur associée sur la aliste.

b) Forme constituée d'une liste ayant en élément gauche un atome (exemple : (CONS X Y)). Cet atome est soit une fonction définie dans le système, soit une variable (argument fonctionnel).

Dans le premier cas, eval passe le contrôle à apply en évaluant ou non les arguments - selon le type de la fonction - et après remplacement éventuel du nom de la fonction par son expression (types EXPR, FEXPR).

Dans le second cas l'argument fonctionnel associé à la variable la remplace dans l'expression et le contrôle est à nouveau donné à éval.

c) Forme constituée d'une $\lambda$ ou $f\lambda$-expression avec ses arguments, (exemple 1 ci-dessus) le contrôle est donné à apply en évaluant ou non les arguments.

d) Forme constituée d'une label-expression avec ses arguments. Une nouvelle évaluation est faite avec la nouvelle expression formée avec la partie fonction de la label-expression (caddar), et une nouvelle aliste à laquelle on a ajouté un couple "nom de la fonction en label" (cadar) et "corps de cette fonction" (caddar). Aucune restriction n'est donnée dans cet évaluateur sur le corps de la fonction labelée (ce peut être une forme quelconque dont l'évaluation donnera une fonction).

e) Enfin si la partie fonction de la forme est une forme quelconque, il y a lieu de reprendre l'évaluation en évaluant au préalable cette forme. Un nombre quelconque d'évaluations peut avoir lieu avant que la fonction ne soit obtenue :

Exemple 2 :

((COND(T(COND(T(QUOTE LIST)))))) (QUOTE LIST))
dont le résultat est (LIST) après deux appels de l'évaluateur pour déterminer
la fonction.
L'applicateur examine deux cas :

a) la fonction est un atome représentant une fonction de type SUBR (FSUBR) et dans ce cas il lance son exécution (fonction EXEC).

b) la fonction est une $\lambda$ ou $f\lambda$-expression et dans ce cas il lie les variables aux arguments, c'est-à-dire qu'il ajoute des couples à la aliste, et appelle l'évaluation du corps de la fonction qui est une forme.

Notons qu'une restriction est apportée aux fonctions EXPR et FEXPR : celles-ci ne peuvent être définies que par une $\lambda$ ou $f\lambda$-expression ou une fonction compilée.

Cette description, conforme à la plupart des Lisp existants, montre qu'il est possible de dégager de l'évaluateur deux aspects :

1) les tests sur la structure effectués par l'évaluateur et qui peuvent être décrits par une grammaire rendant compte de la structure des formes analysées. Les catégories distinguées par l'évaluateur sont celles introduites dans la grammaire de l'annexe 3-B :

la structure `<Forme>` se compose de formes atomiques (`<Fatom>`) et de formes non atomiques (`<Fnatom>`). Les non-terminaux `<F-subr>`, `<F-expr>`, `<F-fsubr>`, `<F-fexpr>` correspondent aux 4 types de fonctions. Les non-terminaux `<Fna-subr>` et `<Fna-fsubr>` correspondent aux $\lambda$, $f\lambda$ et label expressions. Dans les fonctions décrites par `<Fna-subr>`, deux catégories de fonctions, label-expressions et formes quelconques non atomiques, se distinguent. Dans les deux cas, l'examen des formes contenant ces fonctions ne permet pas de déterminer si les arguments doivent être évalués ou non.

Exemple 3 :

Fonction(COND((EQ X NIL) (QUOTE CAR)) (T(QUOTE QUOTE)))

Le type SUBR de CAR et FSUBR de QUOTE dépend du résultat du test portant sur la variable X.

2) la fonction apply ne fait appel à l'évaluateur que pour traiter le corps d'une fonction ($\lambda$ ou $f\lambda$-expression). La récursivité de la définition de l'évaluateur est donc entièrement contenue dans la fonction eval.
Celle-ci correspond à trois cas :
a) la fonction d'une forme est une variable, ce qui correspond dans la grammaire citée à la règle 10 :

`<Fnatom> = (Ident <Listexpr>)`

où `<Listexpr>` est une liste de S-expression, ou plus généralement de S-graphes, dont on ne sait encore si elle doit être évaluée ou non (1).

b) la fonction est une label-expression. Rien n'étant connu sur le type de la fonction, un nouvel appel de l'évaluateur est nécessaire. Il y a cependant une contrainte sur la syntaxe des label-expressions (règles 19 et 20).

`<Fna-fsubr> = (LABEL Ident <Fnatom>)
            = (LABEL Ident <Fonction>)`

où, les label-expression de la forme :

`(LABEL Ident Ident)`

sont exclues.

c) la fonction est une expression quelconque non réduite à un atome, c'est-à-dire une forme non atomique, ce que traduit la règle 21 :

`<Fna-fsubr> = <Fnatom>`

Dans cette grammaire, le non-terminal `<Fna-fsubr>` correspond aux fonctions dont soit on sait que les arguments ne sont pas évalués, soit on ne peut prévoir s'ils seront ou non évalués.

La liaison entre l'évaluateur de référence et la syntaxe de l'annexe 3-B est fournie par la propriété suivante :

**Propriété 1 :** (liaison entre syntaxe et évaluateur) :

Une condition nécessaire et suffisante pour que l'évaluateur ne produise pas d'erreur et que :

a) Toute forme fournie à eval soit bien formée au sens de l'axiome
Forme de la syntaxe (Annexe 3-B).

b) Toute fonction de type `EXPR(ou FEXPR)` soit définie par une $\lambda$-($f\lambda$)-expression, bien formée au sens du nom-terminal `<Fonction>`.

c) Dans toute forme fournie à eval, tout identificateur est soit une constante (atome de type `APVAL`), soit lié dans une $\lambda(f\lambda)$-expression ou la liste fournie en argument. Tout identificateur en position de fonction (règle 10) est lié dans une $\lambda(f\lambda)$-expression ou dans la aliste fournie en argument, et est différent de `LAMBDA`, `FLAMBDA` ou `LABEL`.

d) Toute $\lambda(f\lambda)$-expression a au moins autant d'arguments que de variables.

(1) En Lisp pur (cf. Annexe 2-C) on admet que les arguments sont toujours évalués.
e) Toute fonction terminale de la grammaire est exécutable par l'évaluateur (exécutée par EXEC) et, quand elle figure dans une forme, a le nombre d'arguments requis.

La propriété 1 montre que l'évaluateur n'accepte que les formes syntaxiquement correctes, donc qu'il effectue des contrôles syntaxiques.

La correspondance entre la syntaxe et l'évaluateur s'établit aisément en associant à chaque test réalisé par l'évaluateur la reconnaissance d'un terminal ou non-terminal de la grammaire. Ainsi quand l'évaluateur test eq(caar(Forme), 'flambda) cela l'amène à reconnaître un non-terminal <Fna-fsubr> (règles 17 et 18) et à réaliser le traitement sur une forme satisfaisant les règles 17 et 18. Si ce test est positif alors que la forme ne satisfait pas l'une de ces règle (par exemple ((FLAMBDA)X) (1)) une erreur sera émise avant l'appel de eval dans apply en raison de l'échec de la recherche du caddr de (FLAMBDA).

La propriété 1 ne suffit pas à assurer que n'importe quelle forme donnée à l'évaluateur donnera un résultat, puisque d'une part tout n'étant pas analysé par l'évaluateur rien ne garantit que les conditions seront toujours satisfaites :

### Exemple 4 :

Forme : ((LAMBDA(X) (X X)) (QUOTE(A.B)));
où A n'est défini ni comme fonction ni sur la aliste.
et que d'autre part une forme peut ne pas avoir de valeur définie :

### Exemple 5 :

Forme : ((FLAMBDA(X) (X X)) (FLAMBDA(X) (XX)));
Cette fonction n'évalue pas ses arguments, la aliste va donc s'enrichir d'un doublet :
(X. (FLAMBDA(X) (XX)));
et l'évaluation de (X X) donnera à l'évaluateur la forme :
((FLAMBDA(X) (XX)) X);
la aliste s'enrichira du doublet
(X.X);
et l'évaluateur bouclera indéfiniment sur la forme
(X X);
les substitutions donnant toujours la même forme.

Ceci conduit à définir un sous-ensemble décrit syntaxiquement dans lequel il est possible de prévoir le déroulement de l'évaluation.
## 2.2 Syntaxe d'un Lisp compilable

Il est possible de décrire à l'avance le déroulement de l'évaluation si l'on respecte les conditions suivantes :

1) Il est possible de connaître le type de la fonction appliquée, c'est-à-dire si les arguments doivent ou non être évalués.

2) La forme est telle que les clauses des tests de l'évaluateur entraînant un appel récursif de eval ne sont jamais sollicitées.

3) La forme ne contient aucune fonction de type EXPR ou FEXPR.

Les conditions 2 et 3 entraînent la suppression des règles de la syntaxe précédente (Annexe 3-B) correspondant aux fonctions de types EXPR et FEXPR (règles 5, 7, 12, 14) et aux récursivités (règles 10, 19 à 27). La langage obtenu a alors une syntaxe simplifiée qui peut être étendue (règles 5 à 8, 10 à 38 et 50 à 68), de manière à satisfaire les spécifications du sous-système décrit au § 1.5.2.

Les rapports entre cette syntaxe et l'évaluateur de référence sont déterminés par la propriété 2 :

**Propriété 2 :** (liaisons entre syntaxe de Lisp compilables et évaluateur) :

Une condition suffisante pour que l'évaluateur ne donne pas d'erreur est que :

a) toute forme fournie à eval soit bien formée au sens du non- terminal <Forme> de la syntaxe (Annexe 3-A).

b) tout identificateur soit une variable définie dans la aliste ou liée dans une $λ(fλ)$-expression et soit différent de LAMBDA, FLAMBDA ou LABEL.

c) toute forme ayant une $λ(fλ)$-expression ait au moins autant d'arguments que de variables.

d) toute fonction SUBR ou FSUBR, compilée, le soit à partir d'une expression bien formée au sens de l'axiome <Fonction> de la même syntaxe.

e) toute fonction terminale de la grammaire soit exécutable par l'évaluateur.

La propriété 2 exprime simplement que la grammaire du Lisp compilable définit un sous-ensemble de Lisp. Comme d'autre part cette grammaire introduit plus de contraintes, les conditions sont simplifiées : il n'y a plus de fonctions EXPR, FEXPR ; toutes les constantes sont explicitées (pas d'atomes de type APVAL) ; le nombre d'arguments des fonctions terminales de la grammaire est défini dans celle-ci.
Un examen de la syntaxe permet de vérifier que les conditions a) à d) entraînent que les clauses de eval sont toujours vérifiées sans faire appel aux clauses correspondant à un appel récursif et que evlis et pairlis se terminent toujours. Il suffit pour cela de considérer que les fonctions figurant dans les formes du types (AND Listand) (règles 10 à 39) sont SUBR ou FSUBR selon les indications de la liste fournie au paragraphe 1.5.2.

La condition b) découle de l'appel d'eval dans apply : si une variable n'est pas définie dans la aliste d'origine, elle a dû être liée dans une $λ-(fλ)$ expression.

La condition d) garantit que la liste des fonctions SUBR et FSUBR peut être agrandie sans remettre en cause la propriété 2.

Enfin, si l'évaluation peut être entièrement prévue de manière "statique", le résultat n'est pas nécessairement acquis ainsi que le montre l'exemple 6 :

### Exemple 6 :

```
Fonction compilée : (FLAMBDA(X) (FC X)) de nom FC donne par exemple
(cf. chap. 3) : FC : LIER X ;
          PUSHV X ;
          LINK FC ;
          RETURN ;
```

L'évaluation de la forme (FC A) fait croître indéfiniment la aliste avec des couples (X.A).

La syntaxe du sous-langage ainsi défini correspond à la partie syntaxique d'un compilateur qui, en décrivant les expressions bien formées (essentiellement des fonctions) en termes de primitives, permettra une définition rigoureuse de ce sous-langage (chap. 3).

Introduisant la fonction EVAL (ou EVAL1) comme fonction SUBR, on voit que cette syntaxe, avec la description de l'évaluateur EVAL et des extensions qu'il autorise, permet de décrire entièrement le langage.

## 2.3 Extensions permises par l'évaluateur

Les extensions de la syntaxe précédente, autorisées par l'évaluateur, correspondent ainsi qu'on la vu aux règles 10, 19, 20 21, 5, 7 (et règles associées à la syntaxe de Lisp fournie en Annexe 3-B).

Elles correspondent aux écritures suivantes, qui peuvent se combiner :
- **Arguments fonctionnels**

Ex : fonction MAP

- **Label-expressions** (supprimée dans la plupart des Lisps actuels)

Ex : ((LABEL X (FLAMBDA(X) (X X))) A)

La possibilité d'une telle expression interdit le label dans un Lisp compilable uniquement en raison du fait que lorsque l'évaluateur évalue la forme (X X), la aliste a le couple (X.A) en tête, alors que le compilateur considèrera que le premier X de (X X) est un appel à X.

- **Fonctions calculées**

Ex : ((COND((EQ X NIL) (QUOTE CAR)) (T(QUOTE QUOTE))) (QUOTE(A.B)))
qui selon que X vaut nil ou non vaut A ou (QUOTE(A.B))

- **Fonctions EXPR et FEXPR** (règles 5, 7 et associées).
Définition d'un compilateur Lisp à l'aide des attributs sémantiques

Il existe deux grandes familles de compilateurs correspondant aux développements de systèmes Lisp sur IBM et sur PDP. Pour la série IBM le prototype est le compilateur Lisp pour l'IBM 7090 (Mc Carthy, Lisp 1.5) adapté pour l'IBM 360 par R.I. Berns, A.C. Hearn et J.G. Kent [17]. Pour la série PDP, la première implantation fut faite sur PDP1 par Bobrow et Murphy pour aboutir en 1967 à une version compatible sur SDS 940. Ceci a donné lieu au système MACLISP implanté au MIT sur PDP 10 [3] et au système INTERLISP (BBN-LISP) implanté sur SDS 940 [4].

Fondamentalement les deux familles de compilateurs ont une structure analogue tant par leur aspect externe (fonction Lisp prenant comme argument un S-graphe, découpage en de nombreux modules) que par leur fonction (simuler le fonctionnement d'une machine qui applique une fonction à l'ensemble des arguments sauvegardés après leur évaluation). Tous incluent des éléments analogues du langage comme les fonctions à nombre quelconque d'arguments, aucun ne traite les LABEL-expressions. Tous ont à résoudre le problème de l'accès aux variables globales, partagées entre les programmes compilés et les non compilés. Diverses solutions existent dans les deux familles de compilateurs (COMMON-variables ou P-List processing pour la famille IBM par exemple). Pourtant si l'on considère le code généré pour ces différentes machines, les instruction sont sensiblement différentes (chargement en mémoire ou sauvegarde dans une pile) incluant des optimisations adaptées au type de machine.

Ceci montre qu'une compilation "complète" et détaillée n'est pas possible si l'on veut générer du code pour les deux types de machines. Cependant il est possible de compiler jusqu'à un certain niveau dans lequel certaines options essentielles sont prises, indépendemment de la machine considérée. Le schéma de la figure 1 illustre le niveau auquel nous nous plaçons.

D'une certaine manière notre "code généré" constitue un langage intermédiaire de premier niveau (Mazaud [18]) dans lequel nous décrivons les données manipulées et les opérations effectuées en Lisp. Notre but étant de décrire les fonctions essentielles du langage, avec pour seules données des S-graphes, le code généré sera extrêmement simplifiée. Il correspond aux instructions d'une machine abstraite définie dans la section 1 de ce chapitre.

Dans la suite nous exposons le choix de la machine abstraite et donc le code objet. Les paragraphes 2 et 3 décrivent respectivement la traduction de Lisp compilable dans ce code et quelques optimisations.
<figure><img src="image_12.png" /><figcaption>fig 1. Niveau du code généré</figcaption></figure>

# 1. Choix d'une machine abstraite, code objet

## 1.1 Machine à aliste

Le premier type de machine abstraite que l'on peut proposer reproduit fidèlement le mécanisme de base de l'interpréteur Lisp avec aliste. Dans celle-ci la aliste est une pile dont chaque élément est un doublet formé du nom de la variable et d'un pointeur sur la valeur de celle-ci. Les deux éléments évoluent de manière autonome : les pointeurs constituent la pile des arguments évalués et les noms de variables correspondent aux variables liées dans une λ-expression. Après le calcul de cette λ-expression, les éléments de la pile correspondant aux arguments de celle-ci peuvent être dépilés, ainsi que le montre l'exemple de la figure 2.

<figure><img src="image_13.png" /><figcaption>fig 2. Evaluation de ((λ(X)forme) arg1 arg2) : évolution de la pile des arg.</figcaption></figure>

Dans cet exemple les deux arguments arg1 et arg2 ont été évalués et leurs valeur var1 et var2 empilées ; la variable X a été liée au premier argument et, après l'évaluation de la forme dont le résultat a été mis en sommet de pile, le doublet et l'argument (var2) ont été supprimés.
La machine abstraite est décrite à la figure 3. Elle correspond
grosso-modo à celle décrite par Lux [11]. Elle comprend :

- une zone de cellules qui sont chacune de la forme d'un doublet "pointeur car, pointeur cdr" et pour lesquelles il existe une source potentiellement infinie. Nous ne nous préoccuperons pas ici de problèmes de ramasse miettes (garbage collector) que l'on doit traiter au niveau de l'implantation de la machine. Un "élément" de cette zone est un graphe non atomique que l'on identifie par la notation 'S-graphe, où la notation quotée signifie qu'il s'agit d'une adresse de la zone atome ou cellules.

<figure><img src="image_14.png" /><figcaption>fig 3. Machine abstraite à aliste</figcaption></figure>

- une zone d'atomes, également potentiellement non limitée.
L'algorithme de recherche d'un atome de nom donné est évoqué par la
notation 'X qui dénote que si X est dans la table, 'X est l'adresse
de cet atome et que sinon un nouvel atome est créé ayant pour nom X et 'X
est l'adresse de cet atome.
- une zone de piles comprenant la pile "aliste" repérée par :

- un pointeur de sommet de pile : sp

- deux accès au contenu du doublet : C1(nom de la variable si elle existe, nil sinon), C2 valeur de l'argument.

La procédure de recherche du rang d'une variable donnée, dans la pile, est search(X) où X est la variable et où search fournit le rang du premier doublet rencontré en partant du sommet, c'est-à-dire :

search(X) = i tel que

    C1(i) = 'X, 1 ≤ i ≤ sp
    C1(j) ≠ 'X i < j ≤ sp

La zone de piles contient également la pile des adresses de retour des sous-programmes.

- une zone de programmes compilés, i.e. écrits sous forme d'instructions de la machine abstraite.

- un compteur ordinal.

La machine abstraite fonctionne de la manière suivante : l'instruction désignée dans le compteur ordinal est exécutée, celle-ci modifie le compteur et les instructions sont exécutées tant que le compteur contient un numéro d'instruction.

Les choix essentiels concernant la machine abstraite portant sur la pile des arguments, nous détaillons ici les instructions opérant sur celle-ci. Les autres instructions sont détaillées à l'annexe 4-A et ne sont pas modifiées par les choix indiqués ci-dessous.

La première instruction correspond à la fonction ASSOC, la seconde QUOTE et la cinquième SETQ de Lisp. Cette correspondance quasi directe rend les instructions assez lisibles. Les instructions POP (3 et 4) servent à la gestion de la pile. La possibilité de dépilement rend cette implantation moins coûteuse en place mémoire qu'une aliste implantée dans la zone des cellules.

Cependant, la nécessité de faire une recherche séquentielle dans la aliste, comme dans la pile, rend l'accès aux variables peu performant. L'introduction d'une petite pile attachée à chaque variable et dans laquelle sont empilées les valeurs successives de la variable permet d'éviter de faire une telle recherche chaque fois qu'il est fait référence à cette variable. Il reste toutefois, dans les deux cas, le temps d'accès à l'emplacement de l'atome dans la table des atomes (recherche et éventuellement, introduction).
Description

1. PUSHV 'X
sp := sp + 1
Cl(sp) := 'nil
C2(sp) := C2(search(X))
co := co + 1

2. PUSHQ 'S-graphe
sp := sp + 1
Cl(sp) := nil
C2(sp) := 'S-graphe
co := co + 1

3. POP
sp := sp - 1
co := co + 1

4. POP n
C2(sp - n) := C2(sp)
Cl(sp - n) := nil
sp := sp - n
co := co + 1

5. SET 'X
C2(search(X)) := C2(sp)
co := co + 1

Explication

1. PUSHV 'X
: Instruction qui met en sommet de pile la valeur de la variable X. Une recherche de la dernière définition de X est nécessaire (procédure search) qui est équivalente à la recherche de la valeur X dans une aliste.

2. PUSHQ 'S-graphe: Un pointeur donné ('S-graphe) est empilé en sommet de pile.

3. POP : Dépilement du sommet

4. POP n : "Dépilement" de n éléments en dessous du sommet, celui-ci étant conservé, "abaissé" de n rangs.

5. SET 'X : Affectation à la variable X de la valeur située en sommet de pile (la portée de cette affectation s'étend au bloc dans lequel X a été définie).

Tableau 1 : Instructions concernant la pile des arguments.
## 1.2 Machines à piles de liens et pile d'arguments

La "aliste" de la machine précédente est éclatée d'une part dans les piles de liens attachées à chaque atome défini, d'autre part dans la pile des arguments. Ceci est illustré par la figure 4.

<figure><img src="image_15.png" /><figcaption>fig 4 : Machine abstraite à piles de liens</figcaption></figure>

Cette machine diffère de la précédente uniquement par la zone de piles. La pile des arguments est repérée par :

* un pointeur de sommet de pile sp

* un accès au contenu d'un élément de rang r : c(r).

La pile de liens associée à l'atome X est repérée par le pointeur assoc(X) et le rang du sommet dans la pile. Nous synthétiserons ces indications par le symbole spX dénotant le "pointeur sommet de pile des liens associée à l'atome X". Le contenu d'un élément de la pile de liens de rang r sera noté comme ci-dessus c(r), le contexte des instructions permettant de lever l'ambiguïté.

Les instructions de la machine correspondant à ces deux piles sont celles du tableau 2.

La valeur du contenu du sommet de pile, dans l'instruction l, est cette fois obtenue par deux accès aux contenus de spX d'une part et c(c(spX)), contenu de l'élément de la pile d'arguments de rang c(spX) d'autre part.
1. PUSHV 'X
sp := sp + 1
c(sp) := c(c(spX))
co := co + 1

2. PUSHQ 'S-graphe
sp := sp + 1
c(sp) := 'S-graphe
co := co + 1

3. POP inchangée

4. POP n inchangée

5. SET 'X
c(c(spX)) := c(sp)
co := co + 1

6. PUSHL 'X n
spX := spX + 1
c(spX) := c(sp - n)
co := co + 1

7. POPL 'X
spX := spX - 1
co := co + 1

Tableau 2 : Instructions concernant les piles de liens et d'arguments

Il en est de même pour l'instruction 5 ou un accès c(spX) permet d'obtenir le rang de l'élément à réaffecter dans la pile des arguments.

Enfin deux nouvelles instructions concernent les piles de liens :
PUSHL qui consiste à empiler au sommet de la pile associée à l'atome X la n-ième valeur en dessous du sommet de la pile des arguments. Si n est nul, c'est la valeur du sommet de cette pile qui est empilée.

POPL (instruction 7) sert à dépiler la pile des liens associée à l'atome X. Cette instruction est sans effet sur la pile des arguments.

L'instruction 6 (PUSHL) traduit donc dans cette machine le rôle de la fonction pairlis de Lisp. On trouvera ces instructions (6 et 7) dans le code généré à chaque ouverture de bloc prog ou λ-expression (instructions d'empilement) et la fermeture des mêmes blocs (instructions de dépilement).
## 1.3 Autre machine

Il est possible de développer cette machine en diminuant la pile des arguments et introduisant des registres utilisés pour les calculs.

On remarque en effet que les piles de liens peuvent être complètement dissociées de la pile des arguments. Il suffit pour cela d'empiler non des pointeurs sur la pile des arguments, mais les valeurs elles-mêmes, dans la pile de liens. Ceci ne pose aucun problème puisque toutes les modifications des valeurs empilées se font par l'intermédiaire des piles de liens et que toute référence à un élément autre que le sommet de la pile des arguments (instruction 6) se fait à l'ouverture d'un bloc alors qu'il n'y a en sommet de pile que des arguments non encore liés.

On voit donc qu'il serait possible de dissocier les deux piles en empilant directement les valeurs dans les piles de liens :

Les instructions 1 et 5 contiennent alors : $c(sp) := c(spX)$
$c(spX) := c(sp)$

et en supprimant de la pile des arguments les éléments liés (ceci aurait l'avantage d'économiser de la place en éliminant de suite l'information inutile). Cette dernière manipulation cependant est coûteuse car, du fait que les arguments sont évalués de gauche à droite, l'argument empilé le plus profondément est le premier argument. Celui-ci étant recouvert au moment de sa liaison avec une variable, - si une λ-expression a plus de un argument - par d'autres arguments évalués, son élimination exige un tassement de la pile, ainsi que l'illustre la figure 5.

<figure><img src="image_16.png" /><figcaption>fig 5. Evolution de la pile des arguments au cours de l'ouverture du bloc λ de l'expression, en cas de suppression des arguments liées.

((λ(X Y Z)forme)'a₁'a₂'a₃'a₄'a₅)</figcaption></figure>
Il est cependant possible d'éviter ces dépilements successifs en
dépilant tous les arguments immédiatement après avoir établi les liaisons
des variables d'une λ-expression. Cette forme d'implantation atteint ainsi son
minimum de place et son maximum d'efficacité.

Deux raisons nous feront cependant conserver intégralement les
piles de liens et la pile des arguments :

1) Les piles de liens sont nécessaires de manière à préserver la
lisibilité du langage intermédiaire où les variables conservent leur
nom symbolique.

2) La suppression des arguments dans la pile constitue déjà un choix
d'implantation que nous voulons laisser ouvert au niveau de description que
nous nous sommes fixés. En effet la pile des arguments correspond grosso-modo
à une pile ou zone de sauvegarde telle qu'elle est utilisée dans les
implantations sur PDP (London [19]) ou sur 360 (Lux [11]). La pile
des liens est une méthode de sauvegarder plus spécifique.

En ce qui concerne l'introduction des registres, les choix sont
variés et très dépendants de la machine. L'implantation sur 360 [10] utilise
16 registres et celle sur T1600 [5] utilise 4 registres. La pile des
des arguments déjà évalués et sert également de registres de calcul. Ces
deux fonctions pourraient être dissociées, mais compte tenu de la remarque
précédente il y aurait déjà un choix de machine réelle à faire.

Notre implantation se fera donc sur la machine abstraite décrite
en 1.2 qui permet de définir le langage Lisp sans inclure trop de choix
d'implantation mais en utilisant, comme le montre la section 1.5, un
langage assez proche d'une implantation réelle.
## 1.4 Code objet

Les 36 instructions du code objet sont décrites à l'annexe 5-A.
Elles permettent de décrire le sous-ensemble de fonction Lisp défini
au chapitre 1. Il y a 6 groupe d'instructions :

1. Instructions concernant la pile des arguments.

2. Instructions concernant les piles de liens.

3. Instructions concernant les atomes.

4. Instructions concernant les fonctions de base.

5. Tests de sommet de pile des arguments.

6. Instructions de branchement.

Les groupes d'instruction 1 et 2 ont déjà été décrits. Il faut y
inclure également des instructions dynamiques telles POPR, SETT,
PUSHLT, qui trouvent leurs paramètres dans la pile elle-même au cours
de l'exécution. Le troisième groupe correspond aux manipulations liées
aux atomes. La figure 6 montre l'organisation d'un atome :

<figure><img src="image_17.png" /><figcaption>fig 6. Organisation d'un atome</figcaption></figure>

Chaque accès peut être construit ou modifié par des instructions
appropriées :

SETA 'X Mise à jour du pointeur apval avec la valeur calculée en sommet de pile des arguments (qui n'est pas dépilée).

SETFT EXPR } Mise à jour du pointeur expr(fexpr) avec la valeur
SETFT FEXPR } calculée en sommet de pile.

PUSHR Mise au sommet de la pile des arguments de la valeur asso-
ciée correspondant à l'atome calculé en sommet de pile
des arguments.
PUSHG indic Mise au sommet de pile de la valeur associée à l'indicateur ou pointeur indic, pour l'atome se trouvant en sommet de pile des arguments (fonction get calculée).

PUSHGP indic Comme la précédente, mais le résultat est booléen, indiquant si l'indicateur correspondant a une valeur ou non dans l'atome ou s'il figure sur sa p-liste.

La p-liste n'est pas détaillée ici (fonctions PUTPROP, REMPROP...), considérant que celle-ci peut être traitée par des fonctions écrites en Lisp et que, à partir du moment où l'on connait la valeur du pointeur pliste, il est possible par ces fonctions d'accéder à tous les éléments de la p-liste.

Le groupe des instructions concernant les fonctions de base est particulier. Considérant que ces fonctions sont très fréquentes et qu'elles peuvent être traduites en général par une instruction machine, elles agissent directement sur le sommet de pile. Ainsi CAR est rendue par :

```
CAR      c(sp) := CAR(c(sp))
co       := co + 1
```

Ainsi, dans la plupart des implantations, le CAR ou CDR se traduisent par une troncature de mots.

Les tests de sommet de pile sont les tests d'égalité ou non à nil et à zéro, d'élément atomique (ATOM), de valeur numérique ou d'égalité ou non des éléments en sommet de pile. Ces tests remplacent la valeur en sommet de pile par un "booléen" 't ou 'nil.

Les instructions de branchement enfin agissent sur le compteur ordinal. Elles comportent les branchements conditionnels, inconditionnels et les appels de sous-programmes. L'instruction LINK est supposée trouver ses arguments dans la pile et LINKT trouve les arguments et la fonction (SUBR ou FSUBR) en sommet de pile. LINK et RETURN empile et dépile les adresses de retour (trouvées dans co) dans la pile des retours, laquelle n'est pas décrite ici.

## 1.5 Du code objet à une machine réelle

Afin de montrer la possibilité de passage aisé du code objet MA à un code machine, nous donnons ici un exemple de traduction d'une fonction; d'une part en code objet de la machine abstraite, d'autre part en code objet d'un PDP 10, tel qu'il est présenté dans [19].
Le PDP 10 cité a 16 registres généraux utilisés comme accumulateurs, registres d'index et registres de mémoire. Les instructions nécessaires à la traduction de la fonction donnée en exemple sont :

<table><tr><td>(PUSH P i)</td><td>empiler dans P le contenu du registre i</td></tr><tr><td>(MOVEI i S-expr)</td><td>mettre dans le registre i 'S-expr</td></tr><tr><td>(MOVE i -r P)</td><td>mettre dans le registre i le contenu de l'élément de P décalé de r par rapport au sommet.</td></tr><tr><td>(SUB P(C O O N N))</td><td>"effacer" les n éléments en sommet de pile P.</td></tr><tr><td>(CALL n(E F))</td><td>appel de la fonction F à n arguments.</td></tr><tr><td>(POPJ P)</td><td>retour d'un sous-programme.</td></tr></table>

La fonction compilée est :

$$ (\lambda(X Y) (FONC3((\lambda(Y Z) (FONC1 Z)) 'CAR Y) X Y)) \uparrow a_1 \quad \uparrow a'_1 \quad \uparrow a'_1 \quad \uparrow a'_2 \quad a_2 a_3 $$

où, pour faciliter la lecture, on a numéroté les arguments :

ceux de FONC3 sont $a_1$, $a_2$ et $a_3$, celui de FONC1 $a'_1$ et ceux de la $\lambda$-expression en argument $a'_1$ et $a'_2$.

Une fonction à n arguments est appelée dès que ses arguments ont été changés à partir de la pile de sauvegarde P dans les accumulateurs 1 à n.

Le code objet en LAP PDP 10 est donné au tableau 3 avec parallèlement le code objet de la machine abstraite.

Aucun des deux codes n'est optimisé sur cet exemple et cela permet d'établir plus clairement la correspondance : ouverture et fermeture de bloc se traduisent dans le code PDP 10 par des sauvegarde et dépilement. Calcul d'une valeur (obtenue dans l'accumulateur 1) et sauvegarde dans P, correspondent dans le code MA à l'empilement d'une valeur. L'appel de fonction est analogue dans les deux cas, à ceci près qu'il est possible de dépiler P avant l'appel de la fonction dans le cas du code PDP 10.

Dans le code MA enfin les noms symboliques des variables sont conservés, ceci du fait que la valeur associée à un atome X se retrouve par l'intermédiaire de son nom. Les liaisons existantes entre les piles de liens et la pile des arguments permettent cependant d'assigner à chaque valeur de X dans la pile des liens une place fixe dans la pile des arguments, ceci jusqu'à effacement du lien correspondant. Ceci est illustré sur la figure 7.
<table><caption>Tableau 3. Compilation dans les deux codes de :</caption><thead><tr><th>Code PDP 10</th><th colspan="2">Signification</th><th>Code MA</th></tr></thead><tbody><tr><td>(LAB ESSAI SUBR)</td><td></td><td></td><td></td></tr><tr><td>(PUSH P 1)</td><td rowspan="2">sauvegarde</td><td rowspan="2"></td><td rowspan="2">PUSHL 'X 1</td></tr><tr><td>(PUSH P 2)</td></tr><tr><td>(MOVEI 1 CAR)</td><td rowspan="2">Calcul de a'<sub>1</sub></td><td rowspan="2"></td><td rowspan="2">PUSHL 'Y O</td></tr><tr><td>(PUSH P 1)</td></tr><tr><td>(MOVE 1 -1 P)</td><td rowspan="2">sauvegarde</td><td rowspan="2"></td><td rowspan="2">PUSHQ 'CAR</td></tr><tr><td>(PUSH P 1)</td></tr><tr><td>(MOVE 1 0 P)</td><td rowspan="2">Calcul de a'<sub>2</sub></td><td rowspan="2"></td><td rowspan="2">PUSHV 'Y</td></tr><tr><td>(PUSH P 1)</td></tr><tr><td>(MOVE 1 0 P)</td><td rowspan="2">sauvegarde</td><td rowspan="2"></td><td rowspan="2">PUSHL 'Y 1</td></tr><tr><td>(PUSH P 1)</td></tr><tr><td>(MOVE 1 0 P)</td><td rowspan="2">Calcul de a''<sub>1</sub></td><td rowspan="2"></td><td rowspan="2">PUSHL 'Z O</td></tr><tr><td>(PUSH P 1)</td></tr><tr><td>(MOVE 1 0 P)</td><td rowspan="2">Chargement de a''<sub>1</sub></td><td rowspan="2"></td><td rowspan="2">PUSHV 'Z</td></tr><tr><td>(SUB P(C 0 0 1 1))</td></tr><tr><td>(CALL 1(E FONC1))</td><td>Dépilement de P</td><td></td><td>LINK 1 FONC1</td></tr><tr><td>(SUB P(C 0 0 2 2))</td><td>exécution de FONC1</td><td></td><td>POP 1</td></tr><tr><td>(PUSH P 1)</td><td>Dépilement des arguments de la -expr sauvegardés</td><td>sauvegarde</td><td>POPL 'Y<br>POPL 'Z<br>POP 2</td></tr><tr><td>(MOVE 1 -2 P)</td><td rowspan="2">Calcul de a<sub>2</sub></td><td rowspan="2"></td><td rowspan="2">PUSHV 'X</td></tr><tr><td>(PUSH P 1)</td></tr><tr><td>(MOVE 1 -2 P)</td><td rowspan="2">sauvegarde</td><td rowspan="2"></td><td rowspan="2">PUSHV 'Y</td></tr><tr><td>(PUSH P 1)</td></tr><tr><td>(MOVE 1 -2 P)</td><td rowspan="2">Calcul de a<sub>3</sub></td><td rowspan="2"></td><td rowspan="2"></td></tr><tr><td>(MOVE 2 -1 P)</td></tr><tr><td>(MOVE 3 0 P)</td><td rowspan="2">Chargement des arguments a<sub>2</sub></td><td rowspan="2"></td><td rowspan="2"></td></tr><tr><td>(SUB P(C 0 0 3 3))</td></tr><tr><td>(CALL 3 (E FONC3))</td><td rowspan="2">à a<sub>3</sub></td><td rowspan="2"></td><td rowspan="2">LINK 3 FONC3</td></tr><tr><td>(SUB P (C 0 0 2 2))</td></tr><tr><td>(POPJ P)</td><td>Dépilement des arguments sauvegardés</td><td>ts</td><td>POPL 'X<br>POPL 'Y</td></tr></tbody></table>

((λ(X Y) (FONC3((λ(Y Z) (FONC1 Z)) 'CAR Y) X Y)))
<figure><img src="image_18.png" /></figure>

Les rangs $r_o, r_l$ où les deux dernières valeurs de X sont empilées ne sont pas modifiées pendant toute la durée de vie de ces liens, c'est-à-dire dans le bloc $\lambda$ où ils ont été définis.

**fig 7.** Conservation du rang des liens dans la pile des arguments

Il est donc possible de générer un code sans conserver le nom symbolique des atomes (et alors sans pile de liens) qui n'utilise que la pile des arguments. Il suffit de noter que les déclarations PUSHL 'X n' permettent de localiser les valeurs de variables dans la pile et que l'utilisation de registres oblige à charger les arguments avant tout appel de fonction et à sauvegarder (empiler) les résultats obtenus. La traduction du code MA au code PDP nécessite de noter les modifications de la localisation des variables suivant l'ajout d'éléments à la pile. La pile des arguments et la pile de sauvegarde des arguments du PDP évoluent en effet de la même manière.

## 2. Traduction

### 2.1 Les attributs sémantiques

Il y a 8 groupes d'attributs :

1) **CEVAL** : attribut unique synthétisé contenant l'ensemble des instructions du code généré. Pour cette description il n'a pas été nécessaire de structurer la description d'une instruction. On considère par la suite qu'une instruction est une chaîne de caractères telle que certains éléments numériques (étiquette par exemple) sont aussi considérés comme maillons de cette chaîne. Le but de la traduction est de calculer l'attribut CEVAL(Fonction) dans les règles 1 et 2.
2) LBOUND, PBOUND : attributs calculés dans les règles 48 et 49 représentant les portions de code généré où l'on empile et dépile les piles de liens.

3) LAB, LAB1, LAB2, LAB3 : attributs incrémentés lors de la génération des instructions. LAB représente l'adresse courante de la prochaine instruction à générer. Les LABi sont utilisées pour étiqueter les instructions générées dans LBOUND et PBOUND.

4) NB : compteur d'arguments ou de variables (règles 48, 49, 64 et 66) utile pour la génération de certaines instructions (règles 1, 40, 46 par exemple).

5) LABTAB, TAB : deux attributs tables d'étiquettes dans les formes PROG. TAB est un attribut circulant (H et S) qui relève les étiquettes, c'est-à-dire les formes atomiques d'un PROG et leur fait correspondre une adresse, celle de la première instruction du code généré de la forme suivante. LABTAB est le "parachutage" (attribut hérité) de cette table, initialisée dans la règle 12 (cf. 2.3) dans les différentes formes non atomiques de PROG de manière à générer les branchements correspondants aux formes : (GO<Forme>). Ce "parachutage" s'étend aux formes conditionnelles (règles 50, 51).

6) BPROG, BCOND, GOFORM sont des attributs booléens hérités pour les deux premiers, synthétisés pour le dernier. Ils indiquent respectivement qu'une forme est argument d'un PROG, qu'une forme fait partie d'une clause conditionnelle et qu'une forme est une forme GO ou RETURN. Ces informations sont nécessaires en particulier dans la règle 9 où il est aisé de déterminer de quelle manière l'influence de PROG et de COND interfère pour la signification des formes atomiques.

7) OUTC, OUTO, OUTA, OUTP sont des adresses héritées, initialisées dans les règles 11, 16, 17 et 12, et représentent l'adresse de branchement dès qu'une condition, un or, un and ou un prog sont jugés terminés (respectivement : clause satisfaite, un non nil obtenu, un nil obtenu, un return exécuté). Elles permettent de générer complètement les instructions de branchement à la "sortie" de ces formes (COND, OR, AND et PROG).

8) TEXT attribut standard donnant le texte associé à un terminal de la grammaire.
La description des attributs doit respecter deux contraintes :
d'une part être cohérente, c'est-à-dire qu'aucune définition ne doit
"boucler" à travers le jeu des dépendances entre attributs ; d'autre
part un attribut doit toujours avoir une valeur lorsqu'il est suscepti-
ble d'être utilisé, même si cette valeur est inutile. Ainsi dans la
règle 1 H-TAB(Forme) est initialisé avec la valeur "indéfini". Suposons
que l'on ait alors une fonction :

$(\lambda(X)X)$

dans la règle 9 le calcul de S-TAB(Fatom) sollicitera la valeur de
H-TAB(Forme). Si celle-ci n'est pas définie ce calcul n'est pas défini.
Il est donc nécessaire d'initialiser dans toutes les règles divers
attributs avec cette valeur "bidon". On peut objecter que dans une phase
d'optimisation des attributs - incluse dans le système DELTA (Lorho [14])
que nous utilisons, avec l'élimination des impasses - ces calculs "bidons"
seraient éliminés et que de toutes manières ils ne servent pas au calcul
de l'attribut CEVAL(Fonction). Il n'en reste pas moins que pour ne pas
lier la description faite ici à un système particulier (tel DELTA) ou un
langage d'attributs particulier, nous maintiendrons ces initialisations
à "indéfini".

## 2.2 Le langage sémantique

Le langage sémantique est le langage dans lequel sont décrits les
calculs sur les attributs.

Nous utilisons une notation simplifiée à l'extrême. Dans chaque
règle, les attributs calculés apparaissent à gauche du signe "=".
A droite de ce signe apparaissent les calculs comportant des opérations
sur des attributs (ceux-ci sont identifiés par leur nom en lettres
majuscules avec le nom d'un non-terminal entre parenthèses), des
constantes correspondant à des initialisations (0, indéfini, true,
false), des incrémentations (+1, +2) ou du code généré (:PUSHQ').

Une instruction est constituée d'une chaîne de caractères comportant tous
les caractères soulignés, (le signe "^" représente un espace) et incluant
des étiquettes numériques.
Dans la mesure où ceci n'introduisait pas d'ambiguïté, on n'a pas structuré la représentation des instructions générées et l'on a mélangé les types d'attributs. Ainsi dans la règle 51 (annexe 4-C) on a :

```
CEVAL(Listcond) = CEVAL(Forme)
    if BPROG(Listcond) and GOFORM(Forme')
    then S-LAB(Forme) :BRN OUTC(Listcond) ;
        S-LAB(Forme)+1 :POP ;
        CEVAL(Forme')
    else S-LAB(Forme) :BRN OUTC(Listcond) ;
        CEVAL(Forme')
        S-LAB(Forme') :POP 1 ;
    fi
```

Sont implicites dans cette notation : l'union des instructions, la concaténation de chaînes pour une instruction, le fait que les valeurs numériques (étiquettes) font partie de la chaîne d'une instruction.

Les structures de contrôle du type "if then else fi" sont en ALGOL 68.

La valeur de `CEVAL(Listcond)` est donc obtenue de la manière suivante :

```
ensemble des instructions de CEVAL(Forme), union :
si BPROG(Listcond) et GOFORM(Listcond) sont vrais
  alors {Deux instructions et un ensemble}
  sinon {Deux autres instructions et un autre ensemble}
fsi
```

Dans le premier groupe les deux instructions sont séquentielles (étiquettes : S-LAB(Forme) et S-LAB(Forme) + 1). Dans le deuxième groupe elles encadrent l'ensemble `CEVAL(Forme')`. Avec cette notation, il aurait été possible d'écrire ces instructions dans n'importe quel ordre. Dans cette traduction on s'est efforcé de conserver l'ordre séquentiel des instructions afin de faciliter la lecture.
## 2.3 Traduction

La traduction se lit d'elle-même (annexe 4-C) et a pour but de
décrire l'effet de chaque forme Lisp sur la machine abstraite. Ainsi,
dans la règle 14 :

<Fnatom> = (SETQ Ident<Forme>)
CEVAL(Fnatom) = CEVAL(Forme)
S-LAB(Forme) : SET 'TEXT(Ident) ;

on voit que, après avoir évalué la forme fournie en argument, la valeur
associée à l'atome TEXT(Ident) sera mise à jour avec la valeur obtenue
en sommet de pile, l'hypothèse étant que toute évaluation de forme
aboutit à mettre en sommet de pile la valeur de l'expression évaluée.
On en conclut que la valeur de cette expression Lisp est la valeur de
forme après évaluation puisque le sommet de la pile n'est pas modifié.
C'est bien ce que l'on recherchait.

Nous donnons ici la signification de la traduction de la règle 12 :

<Fnatom> = (PROG(<Listvar>)<Listprog>)

Cette forme PROG comporte une liste de variables, éventuellement vide,
et une suite de formes, éventuellement atomiques. La valeur de cette
forme est la valeur des formes fournies en argument d'un RETURN ou, à
défaut, la dernière forme évaluée de la suite. Le traitement consiste
à initialiser toutes les variables locales du PROG à NIL. Il faut
évidemment supprimer ces variables en fin de PROG, et également éliminer
au fur et à mesure les valeurs des formes qui sont évaluées, sauf la
dernière, mais qui sont chaque fois en sommet de pile. Ceci est fait
dans les règles 52 et 53.

CEVAL(Fnatom) = PBOUND(Listvar)
CEVAL(Listprop)
S-LAB(Listprog) + NB(Listvar) : POP NB(Listvar) ;

L'évaluation de la forme comporte l'empilement de NB(Listvar) valeurs
'nil, la création d'un nouveau lien d'association pour toutes les varia-
bles définies dans Listvar (ceci est fait par PBOUND détaillé dans les
règles 48 et 49), les instructions du corps de PROG et les instructions
de suppressions des liens (générées dans PBOUND à partir de l'adresse LAB2)
et enfin l'instruction de dépilement des variables locales, à l'adresse
S-LAB(Listprog) + un nombre d'instructions de dépilement de liens égal
à NB(Listvar) (nombre de variables dont les liens ont été dépilés).
S-LAB(Fnatom) = S-LAB(Listprog) + NB(Listvar) + 1

La première instruction a être générée après la forme PROG aura
l'étiquette S-LAB(Listprog) + le nombre d'instructions générées pour
les dépilements.

H-LAB(Listprog) = H-LAB(Fnatom) + 2 * NB(Listvar)

La première instruction du corps de PROG aura l'étiquette H-LAB(Forme) + le nombre d'instructions générées pour empiler les 'nil et associer les variables.

LAB1(Listvar) = indef.

Etiquette définie seulement dans les λ-expressions (règles 46, 47)

LAB2(Listvar) = S-LAB(Listprog) + NB(Listvar) - 1

Etiquette de début de dépilement des liens des variables locales.

Si NB(Listvar) est nul (pas de variable) aucune instruction ne sera générée.
Aucun test n'est donc nécessaire sur NB(Listvar) - 1.

LAB3(Listvar) = H-LAB(Fnatom)

La première instruction générée est une instruction d'empilement des
constantes 'nil.

GOFORM(Fnatom) = false

Evidemment.

H-TAB(Listprog) = tablevide

Initialisation du relevé de la table des étiquettes du PROG.

LABTAB(Listprog) = S-TAB(Listprog)

Initialisation du "parachutage" de la table complète des étiquettes
du PROG.

OUTP(Listprog) = S-LAB(Listprog)

La sortie du PROG se fait sur l'instruction de dépilement des
variables.

Ainsi, venant d'un RETURN ou de la dernière forme évaluée (cf. règle 53)
la valeur souhaitée est conservée en sommet de pile, même après les
dépilements.

Cette description permet de suivre dans tous les cas de figures
déterminées par la syntaxe le résultat produit par une expression Lisp.

Une réserve doit être faite pour l'introduction de fonctions telles
que PUSHL1, POPL1, PUSH qui manipulent explicitement la pile et qui ne
sont décrites ici que pour les besoins de l'auto-définition de l'évalua-
teur (annexe 2). Leur introduction dans des expressions Lisp condui-
rait généralement à des résultats incohérents.
# 3. Optimisations

## 3.1 Choix des optimisations

Notre objectif est de montrer que, ayant défini une première traduction à l'aide des attributs sémantiques, il est aisé d'introduire des optimisations supplémentaires. Il est évident que la facilité de cette introduction dépend de la perturbation apportée au code généré. Il est plus aisé d'optimiser deux POP successifs (POPn1 ; eti : POPn2 ;) en $POP\ n_1 + n_2$ ; ou d'éviter des branchements successifs du type BR eti ; eti : GO eti' que d'éliminer la récursivité dans la fonction factorielle. En raison du caractère algorithmique de la description par attributs, il est possible certainement de faire toutes les optimisations possibles. Cependant l'introduction d'une optimisation dans une telle description n'a d'intérêt que dans la mesure où le découpage syntaxique facilite sa résolution et où les différentes phases de l'optimisation utilisent largement la circulation des attributs. Il faut en effet que le code puisse être optimisé au cours de sa synthèse, en tenant compte de l'ensemble des optimisations possibles. Dans le cas contraire il se pourrait qu'une optimisation (suppression d'une récursivité par exemple) en nécessite d'autres déjà faites auparavant (celles citées ci-dessus), ce qui imposerait de faire plusieurs "passes" d'optimisation sur le code généré, qui seraient sans doute aussi complexes à gérer "par attributs" que par une méthode traditionnelle.

Ceci nous conduit à choisir parmi les diverses optimisations celles dont il est possible de tenir compte en une seule passe de génération de code ; c'est-à-dire telles qu'il soit possible de trancher, dans le contexte de la règle où elle est générée, s'il faut ou non - ou comment - générer une instruction donnée. Ainsi, avant de générer un POP n (règles 12, 23, 24, 28, 35, 36, 39, 40, 50, 51, 58, 59, 60) on se demandera si les instructions précédentes ou suivantes sont POP n' (ce qu'il est possible de faire avec des attributs appropriés).

Un autre aspect concernant les optimisations, non lié cette fois aux attributs, relève du code généré. Une optimisation sur le code de la machine abstraite n'a d'intérêt que si en quelque sorte elle est pertinente pour le code machine réel. Ainsi l'élimination d'une récursivité, dans la mesure où on considère qu'elle est intéressante (Lux [11]), est pertinente pour le code généré, de même que l'élimina-
tion d'expressions redondantes. En d'autres termes, toute optimisation correspondant à des transformations du programme source jugée intéressante est certainement pertinente. Par contre toute optimisation qui met en cause les instructions de la machine abstraite n'est pertinente que si elle peut être admise pour générer, à partir du code MA, du code machine réelle.

Enfin, on ne peut pas rattacher ces considérations aux traitements usuellement faits dans les compilateurs Lisp. Déjà Mc Carthy (London [19]) introduisait dans les premiers compilateurs les optimisations suivantes (se référer au code objet section 1.5).

1) Suppression de la sauvegarde d'un argument unique lorsque celui-ci est l'argument d'une chaîne de CADR.

2) Si un argument est une variable, ou 'S-expr ou une chaîne de CADR avec une variable, il peut n'être compilé qu'au moment du chargement en raison de 1.

3) Optimisation des JUMP1 dans les expressions OR et AND, en particulier les JUMP finaux (BR dans le code MA).

Ces optimisations, comme les autres citées dépendent d'un code particulier, mais on peut dire que dans la description de Lisp de la section 2.3 il est déjà tenu compte au moins des optimisations 1 et 3. Tenir compte de l'optimisation 2 nécessiterait de générer des portions de code, correspondant au non terminal <Forme> , à des emplacements ne suivant pas l'ordre d'évaluation des arguments (H-ETI(Forme) de la règle considérée = S-ETI(Listarg) de la première règle concernant la liste des arguments).

Notre objectif étant de montrer les perturbations apportées à la description de la section précédente par l'introduction de quelques optimisations et compte tenu des remarques précédentes, nous traiterons seulement deux cas d'optimisation : la réduction des POPn successifs et l'élimination de la récursivité dans un cas simple.
## 3.2 Suppression des POP successifs

Cette optimisation est liée au code objet.

Nous introduisons deux attributs supplémentaires :

1) BPOPID attribut circulant, indicateur de la présence d'un "POP n" "en amont" du code généré. C'est un booléen alertant sur le fait qu'il n'y a pas lieu de générer l'instruction "POP n" suivante. Ses valeurs sont donc :

$$ BPOPID(NT) = \begin{cases} \text{true ssi } H-\text{LAB}(NT)-1 \text{ est un "POP n"} \\ \text{false sinon} \end{cases} $$

2) APOPID attribut circulant, compteur du nombre d'éléments à dépiler dans les "POP n" situés "en aval" du code généré. C'est un entier qui vaut :

$$ APOPID(NT) = \begin{cases} n \text{ ssi } S-\text{LAB}(NT)+i \ (i=1,p) \text{ sont des POP } n_i \\ \text{avec } n = \sum_{i=1}^{p} n_i \\ 0 \text{ sinon} \end{cases} $$

La liaison entre les deux attributs est explicitée dans la figure 7. Cette figure suppose une règle dans laquelle trois groupes d'instructions se suivent séquentiellement dans l'ordre indiqué et où le premier groupe se termine par "POP 1", le 2ème comprend exclusivement "POP 2" et le troisième débute par "POP 3". La "circulation" engendrée par les deux attributs conduit à "remonter" les "POP n" et à ne plus générer ceux qui ont été ainsi "remontés".

<figure><img src="image_19.png" /><figcaption>Fig 8. "remontée" des "POP n" successifs.</figcaption></figure>
Ces attributs doivent être définis dans toutes les règles. Nous allons les définir uniquement dans les règles où apparaissent des POP n, en montrant les modifications apportées aux calculs d'attributs.

Règle 23 : `<Fnatom> = (CONS<Forme> <Forme'>)` (cf. Annexe 5-C)

H-APOPID(Forme) = S-APOPID(Forme')

S-APOPID(Fnatom) = H-APOPID(Forme)

H-BPOPID(Forme) = H-BPOPID(Fnatom)

H-BPOPID(Forme') = S-BPOPID(Forme)

<u>co</u> circulation normale inversée des deux attributs puisque `CEVAL(Forme)` et `CEVAL(Forme')` sont générés dans cet ordre sans introduire de nouvelles instructions <u>co</u>

S-BPOPID(Fnatom) = true

<u>co</u> `CEVAL(Fnatom)` se termine par un "POP 1" <u>co</u>

H-APOPID(Forme') = 0

<u>co</u> 1'instruction suivante est `S-LAB(Forme')`: `CONS; co`
<u>co</u> enfin `CEVAL(Fnatom)` est modifiée avec :

S-LAB(Forme')+1 : POP H-APOPID(Fnatom)+1 ;
rien d'autre n'est modifié dans cette règle <u>co</u>

Règles 24, 28, 39, 40, 58, 59, 60, 61.

Traitées de manière analogue à la règle 23.

Règle 12 : `<Fnatom> = (PROG<<Listvar>> <Listprog>)`

H-BPOPID(Listprog) = if NB(Listvar) = 0
then H-BPOPID(Fnatom)
else false
fi

<u>co</u> s'il n'y a aucune variable locale aucun empilement n'est fait et H-BPOP est simplement transmis <u>co</u>

S-BPOPID(Fnatom) = if NB(Listvar) = 0
then S-BPOPID(Listprog)
else true
fi

<u>co</u> s'il n'y a aucune variable c'est le dernier "POP n" de Listprog qui est testé <u>co</u>
H-APOPID(Listprog) = H-APOPID(Fnatom) + NB(Listvar)

<u>co</u> le nombre d'éléments à dépiler en fin de PROG est
 incrémenté du nombre de variables <u>co</u>

S-APOPID(Fnatom) = if NB(Listvar) = 0
then S-APOPID(Listprog)
else 0
fi

<u>co</u> s'il y a des variables, le code de PROG ne commence
pas par une instruction "POP n" <u>co</u>

CEVAL(Fnatom) = PBOUND(Listvar)
CEVAL(Listprog)
if S-BPOP(Listprog) or NB(Listvar) = 0
then
else S-LAB(Listprog) + NB(Listvar) : POP
NB(Listvar) + H-APOPID(Fnatom) ;
fi

S-LAB(Fnatom) = S-LAB(Listprog) + NB(Listvar)
+ if S-BPOP(Listprog) or NB(Listvar) = 0
then 0
else 1
fi

<u>co</u> CEVAL et S-LAB(Fnatom) sont modifiés de manière à
tenir compte de la génération ou non de l'instruction
"POP n" <u>co</u>

<u>Règle 50</u> : &lt;Listcond&gt; = (&lt;Forme&gt; &lt;Forme'&gt;) &lt;Listcond&gt;

H-BPOPID(Forme) = H-BPOPID(Listcond)

<u>co</u> la première instruction de CEVAL(Forme) étant
H-LAB(Listcond) <u>co</u>

H-BPOPID(Forme') = false

<u>co</u> avec CEVAL(Listcond) et H-LAB(Forme'), on voit que
CEVAL(Forme') est précédé soit d'un "POP" soit d'un
"BRN", mais non d'un "POP n" <u>co</u>

H-BPOPID(Listcond') = false

S-BPOPID(Listcond) = S-BPOPID(Listcond')

H-APOPID(Listcond') = H-APOPID(Listcond)

H-APOPID(Forme') = if BPROG(Listcond) and GOFORM(Forme')
then 0
else 1
fi
`_co` dans le 2ème cas (cf. `CEVAL(Listcond)`) `CEVAL(Forme')`

est suivi de `"POP 1" _co`

H-APOPID(Forme) = 0

S-APOPID(Listcond) = S-APOPID(Forme)

enfin :

H-LAB(Listond') = if BPROG(Listcond) and GOFORM(Forme')
then S-LAB(Forme') + 1
else S-LAB(Forme')+2+if S-BPOPID(Forme')=false
then 1
else 0
fi

et la 2ème alternance de `CEVAL(Listcond)` est modifiée :

else S-LAB(Forme) : BRN S-LAB(Forme') + if S-BPOPID(Forme') = false
then 2
else 1
fi;

CEVAL(Forme')

if S-BPOPID(Forme') = false

then S-LAB(Forme') : POP 1;

S-LAB(Forme')+1 : BR OUTC(Listcond);

S-LAB(Forme')+2 : POP ;

else S-LAB(Forme') : BR OUTC(Listcond);

S-LAB(Forme')+1 : POP ;

fi

Règle 51 : analogue.

On remarque que si l'on prend soin de définir les nouveaux attributs dans toutes les règles, on est sûr alors d'avoir par cette méthode examiné tous les cas possibles. En particulier, il ressort de cet examen que, dans la règle 46 par exemple, les attributs ne se contentent pas de "circuler" : il faut tenir compte de la génération ou non de dépilements de liens.

Enfin, on est sûr que ces attributs, sauf erreur d'écriture, n'introduisent pas de bouclage puisque leur valeur est déterminée uniquement à l'aide des règles syntaxiques (contexte local) ou d'attributs qui ne les incluent à aucun moment dans leur propre définition.

Sur le plan pratique, le fait d'écrire les ensembles d'instructions générées dans l'ordre séquentiel où les instructions correspondantes sont exécutées est une aide pour calculer ces nouveaux attributs. L'ordre de
génération cependant n'intervient pas dans l'exactitude du résultat, l'ordre d'exécution étant exclusivement déterminé par les étiquettes LAB.

## 3.3 Suppression de la récursion dans un cas simple

Cette optimisation est limitée à la compilation de fonctions récursives que l'on transforme en programmes itératifs, dans un cas simple qui exige peu de transformation de programme et, en particulier, pas de manipulation de pile.

Le cas envisagé est celui où une fonction récursive est une suite de clauses conditionnelles dont certaines sont un appel de la fonction elle-même.

Exemple : Member(elmt, liste)

```
if liste = 'nil then 'nil
elif elmt = car(liste) then 't
then member(elmt, cdr(liste))
```

Plus généralement, une telle fonction revêt la forme, où X représente l'ensemble des paramètres :

$F(X)$ :

```
if Cond₀(X) then P₀(X)
elif Condᵢ(X) then Pᵢ(X)
then Pₙ(X)
fi
```

où les $Pᵢ(X)$ $1 ≤ i ≤ n$ sont soit un programme ne comportant aucun appel de $F$, soit

$Pᵢ(X) = F(fᵢ(X))$.

La transformation consiste alors simplement à transformer $F(fᵢ(X))$ en $X := fᵢ(X)$ et générer un branchement à la première instruction effective de la fonction. On se contentera ici du cas général où le calcul de $X := fᵢ(X)$ nécessite des variables intermédiaires, soit :

$U := fᵢ(X) ; X := U ; go début ; (t₁)$

Afin de ne pas augmenter exagérément la longueur du code généré, s'il y a plusieurs appels récursifs, on générera en fait :

$U := fᵢ(X) ; go extra ;$ (t₂)
...

$extra : X := U ; go debut ;$
L'implantation d'une telle fonction, dans le cas où il n'y a pas d'optimisation est celle de la figure 9 (règles 1 et 2) :

<figure><img src="image_20.png" /><figcaption>Fig 9. Implantation sans transformation</figcaption></figure>

L'implantation avec transformation est celle proposée à la figure 10. On constitue un vecteur U comme dans une forme PROG. Le reste se traite comme une forme PROG particulière dans laquelle il n'y aurait qu'une forme (règle 12).

<figure><img src="image_21.png" /><figcaption>Fig 10. Implantation avec transformation</figcaption></figure>

Chaque portion de code ajoutée a une longueur déterminée dans la règle 1 (ou 2).

Deux catégories d'attributs doivent être introduites : les attributs détectant les conditions dans lesquelles la transformation s'applique et les attributs transportant les informations nécessaires à la transformation.
a) Attributs détectant la transformation

NAME Attribut hérité de type chaîne contenant le nom de la fonction compilée.

RECUR Attribut hérité booléen ayant les valeurs :

RECUR() = {
  true ssi la forme analysée peut faire l'objet de cette transformation
  false sinon

NBRECUR Attribut synthétisé entier comptant le nombre de récursivités à modifier. Si NBRECUR = 1, il n'y a qu'une récursivité à supprimer et il n'est pas nécessaire de générer à part un branchement à extra (cr.t₁ ci-dessus).

BEXTRA Attribut hérité booléen indiquant (true) si la transformation appliquée est t₁ ou (false) t₂.

b) Attributs de transport d'information

LABEXT Attribut hérité entier comportant l'étiquette de branchement après transformation. Il vaut "début" si t₁ ou s'il n'y a pas de variable et "extra" si t₂.

LAB 4 Attribut hérité entier : initialisation des variables locales (équivalent de LAB 3 dans PROG)

LAB 5 id. : dépilement des variables locales (équivalent de LAB 2 dans PROG)

LAB 6 Attribut hérité entier : début des affectations X := U.

LAB 7 Attribut hérité entier : début de dépilement des liens.

LABOP Attribut synthétisé : adresse de début des affectations dans le cas (t₁) valeur initiale de LAB 6 dans ce cas (cf. figure 11).

RBOUND Attribut synthétisé : ensemble des instructions d'empilement et dépilement dans le cas de transformation.

NBI Attribut hérité : nombre d'instructions générées à l'adresse LABOP.

La signification de ces attributs est illustrée sur les figures 11 et 12, dans le cas des transformations t₁ ou t₂ :
<figure><img src="image_22.png" /><figcaption>Fig 11. Initialisation des attributs dans la règle 1 pour le cas $t_1$.</figcaption></figure>

<figure><img src="image_23.png" /><figcaption>Fig 12. Initialisation des attributs dans la règle 1 pour le cas $t_2$.</figcaption></figure>

Comme précédemment ces attributs doivent être définis dans toutes les règles où les non-terminaux auxquels ils sont attachés apparaissent. Nous nous contenterons de les définir dans les règles essentielles pour cette transformation.
Règle 1 <Fonction>
NAME(Forme)
RECUR(Forme)
BEXTRA(Forme)
= (LAMBDA(<Listvar>) <Forme>)
= nom de la fonction
= true
= if NBRECUR(Forme) = 1 or NB(<Listvar>) = 0
  then true
  else false
  fi
LABEXT(Forme)
= if NBRECUR(Forme) = 1 or NB(<Listvar>) = 0
  then H-LAB(Forme)
  else S-LAB(Forme)
fi

<Forme> et "extra" est la première instruction après le code de <Forme> donc
co "début" est H-LAB(Forme), première instruction du code de
S-LAB(Forme) co

LAB4(<Listvar>) = NB(<Listvar>) + 1
LAB5(<Listvar>) = if BEXTRA(Forme)
  then S-LAB(Forme) + NB(<Listvar>) - 1
  else S-LAB(Forme) + 2 * NB(<Listvar>)
fi

co le dépilement se faisant dans l'ordre inverse, il faut ajouter
NB(<Listvar>) - 1 co

LAB6(<Listvar>) = if BEXTRA(Forme)
  then LABOP(Forme)
  else S-LAB(Forme)
fi

LAB7(<Listvar>) = if BEXTRA(Forme)
  then S-LAB(Forme) + 2 * NB(<Listvar>)
  else S-LAB(Forme) + 3 * NB(<Listvar>) + 1
fi

NBI(Forme) = NB(<Listvar>)

LAB1
LAB2
LAB3
BPROG { inchangés
BCOND
LABTAB
H-TAB
H-LAB(Forme) = 1 + 3 * NB(Listvar)
S-LAB(Fonction) = if NB(Listvar) = 0
then S-LAB(Forme)
elif NBRECUR(Forme) = 1
then S-LAB(Forme) + 2 * NB(Listvar) + 1
else S-LAB(Forme) + 3 * NB(Listvar) + 2
fi

co il faut distinguer trois cas, car s'il n'y a pas de variable,
il n'y a pas lieu de générer le dépilement de U co

CEVAL(Fonction) = if NBRECUR(Forme) = 0
then LBOUND(Listvar)
CEVAL(Forme)
S-LAB(Fonction) : RETURN ;

co si aucune transformation n'est faite co
else RBOUND(Listvar)
if NB(Listvar) ≠ 0
then LAB5(Listvar) + 1 : POP NB(Listvar) ;
LAB6(Listvar) + NB(Listvar)
: BR H-LAB(Forme) ;
fi
CEVAL(Forme)
S-LAB(Fonction) : RETURN ;

co dans RBOUND(Listvar) il y a toutes les instructions d'empile-
ment et dépilement dans le cas de transformation ainsi que les affectations
X := U (t<sub>2</sub>), mais il reste à générer le dépilement des valeurs finales
des variables locale U et, dans le cas t<sub>2</sub>, un branchement à "Début"
(fig 12.) co

L'attribut RECUR, indiquant qu'une fonction atomique de nom NAME peut
faire l'objet d'une transformation, est hérité dans toutes les règles
avec la valeur "false". Ainsi dans la règle 14 :

<Fnatom> = (SETQ Ident <Forme>)
RECUR(Forme) = false

La règle 11 fait exception où : RECUR(Listcond) = RECUR(Fnatom)
Si la forme de la fonction compilée est une forme conditionnelle, alors
les transformations y sont possibles.
Règle 50 : `<Listcond>` = `<Forme> <Forme>'> <Listcond>'

RECUR(Forme) = false

RECUR(Forme') = RECUR(Listcond)

RECUR(Listcond') = RECUR(Listcond)

NAME transmis à tous les non-terminaux.

NBRECUR(Listcond) = if RECUR(Listcond)
then NBRECUR(Forme') + NBRECUR(Listcond')
else 0
fi

### co Comptage des transformations co

BEXTRA } sont transmis à Forme' et Listcond'

LABEXT

LABOP(Listcond) = if NBRECUR(Forme') = 0
then LABOP(Listcond')
else LABOP(Forme')
fi

### co la valeur de LABOP est l'adresse de début d'affectation X := U dans la première forme à transformer, indéfinie sinon co

Dans CEVAL(Listcond), il faut introduire le cas où `<Forme'>` fait l'objet d'une transformation. Ceci n'est possible que dans la clause else... (hors d'une forme PROG ou si `<Forme'>` n'est pas une forme GO). De plus la valeur de `<Forme'>` n'est pas à empiler. On a donc, au lieu de "else...." :

```pascal
elif NBRECUR(Forme') = 1
```

```pascal
then S-LAB(Forme) : BRN S-LAB(Forme');
```

```pascal
S-LAB(Forme) + 1 : POP ;
```

```pascal
CEVAL(Forme')
```

```pascal
S-LAB(Forme') : POP ;
```

```pascal
else ... comme précédemment
```

H-LAB(Forme) = H-LAB(Listcond)
= if BPROG(Listcond) and GOFORM(Forme') or
NBRECUR(Forme') = 1
then S-LAB(Forme) + 2
else S-LAB(Forme) + 1
fi

H-LAB(Listcond') = if BPROG(Listcond) and GOFORM(Forme') or
NBRECUR(Forme') = 1
then S-LAB(Forme') + 1
else S-LAB(Forme') + 3

reste inchangé.
La génération des empilements et dépilement se fait dans la règle 48 :

Règle 48 : <Listvar> = Ident <Listvar>

Les calculs suivants sont ajoutés :

RBOUND(Listvar) = RBOUND(Listvar')
LAB1(Listvar) : PUSHL^'TEXT(Ident)\^NB(Listvar') ;
LAB4(Listvar) : PUSHQ^'nil ;
LAB4(Listvar)+1 : PUSHL^'U NB(Listvar)\^O ;
LAB5(Listvar) : POPL^'U NB(Listvar) ;
LAB7(Listvar) : POPL^'TEXT(Ident) ;
LAB6(Listvar) : AFB^'TEXT(Ident)\^'U NB(Listvar) ;
LAB4(Listvar') = LAB4(Listvar) + 2
LAB5(Listvar') = LAB5(Listvar) - 1
LAB7(Listvar'') = LAB7(Listvar) - 1
LAB6(Listvar') = LAB6(Listvar) + 1

Ces calculs génèrent les instructions d'empilement et dépilement dans l'ordre inverse, les affectations X := U se font dans l'ordre inverse des paramètres puisque ceux-ci sont traduits de gauche à droite dans la liste et que NB(Listvar) est incrémenté quand synthétisé. Ainsi pour la liste de variables (VI V2 V3) on génèrera :

LAB6 : AFB 'V1 'U3 ;
LAB6 + 1 : AFB 'V2 'U2 ;
LAB6 + 2 : AFB 'V3 'U1 ;

où AFB 'X 'Y est l'affectation entre liens qui remplace la serie de trois instructions :

1: PUSHV 'Y ;
2: SET 'X ;
3: POP ;

Il reste à examiner la transformation dans le cas où <Forme> est du type (NOM< Listarg>). Le calcul se fait selon le schéma suivant, sachant que, au cours du calcul de <Listarg>, on effectue, s'il y a lieu, U := f(X) (cf. règle 64) :

si $t_1$ branchement à "début"
si $t_2$ et NBI > 0 branchement à "extra"
si $t_2$ et NBI = 0 branchement à "début"

Dans tous les cas LABEXT (calculé dans la règle 1) contient la bonne adresse.
Règle 40 : <Fnatom>
CEVAL(Fnatom)
= (<Fsubr> <Listarg>)
= CEVAL(Listarg)
if NBRECUR(Fnatom) = 1
then S-LAB(Forme)+NBI(Fnatom) : BR LABEXT(Fnatom);
else... comme précédemment

co on peut, par sécurité, introduire un test comparant NBI et NB(Listarg) qui doivent être égaux afin de ne pas générer d'affectations parasites dans la règle 64 co

H-LAB(Listarg)
S-LAB(Fnatom)
= H-LAB(Fnatom)
= if NBRECUR(Fnatom) = 1
then if BEXTRA(Fnatom) = false co cas t₂ co
then S-LAB(Listarg) + 1
else S-LAB(Listarg) + NBI(Listvar) + 1
fi
else S-LAB(Listarg) + 2
fi

LABOP(Fnatom) = S-LAB(Listarg)

co utile uniquement dans le cas t₁ et NBI > 0. Dans ce cas en effet X := U est généré immédiatement après U := f(X) (règle 1, LAB6) co

NBRECUR(Fnatom)
= if RECUR(Fnatom) and TEXT(Fsubr) = NAME(Fnatom)
then 1
else 0
fi

RECUR(Listarg)
= if RECUR(Fnatom) and TEXT(Fsubr) = NAME(Fnatom)
then true
else false
fi

reste comme précédemment.

Règle 64 : <Listarg>
CEVAL(Listarg)
= <Forme> <Listarg>'
= CEVAL(Forme)
if RECUR(Listarg)
then S-LAB(Forme) : SET 'U NB(Listarg) ;
S-LAB(Forme) + 1 : POP ;
fi
CEVAL(Listarg')

co dans le cas de transformation, les arguments ne sont pas empilés co
$$
\begin{align*}
\texttt{H-LAB(Forme)} &\quad = \texttt{H-LAB(Listarg)} \\
\texttt{H-LAB(Listarg')} &\quad = \begin{cases}
\texttt{if RECUR(Listarg)} & \\
\quad \texttt{then } \texttt{S-LAB(Forme)} + 2 & \\
\quad \texttt{else } \texttt{S-LAB(Forme)} & \\
\quad \texttt{fi}
\end{cases}
\end{align*}
$$

reste comme précédemment.

Dans le cas où une transformation a lieu, des affectations à U sont
générées dès qu'un argument est évalué, sans que celui-ci soit conservé
sur la pile.

3.4 Conclusion

Les deux optimisations ont été décrites indépendemment. Or la première dépend de la seconde : la contraction des "POP n" successifs dépend des modifications apportées au code par la transformation. En particulier le calcul des attributs BPOPID et APOPID est modifié et dépend de l'attribut NBRECUR (1). Cette dépendance n'introduit pas de bouclage puisque les valeurs de ces derniers sont fixées indépendamment. A titre d'exemple nous donnons à l'annexe 4-D la traduction complète de la règle 50 (Listcond) tenant compte des deux optimisations.

On remarque que si l'on prend soin de traiter les optimisations
dans l'ordre où elles dépendent les unes des autres et si celles-ci
utilisent des attributs indépendants ou liés par le même ordre de
dépendance, on a ici une méthode assez fiable de description des optimi-
sations. Leur intégration peut se faire par affinements successifs
de la première traduction. Ainsi les attributs se révèlent-ils un
moyen assez simple pour décrire certains algorithmes d'optimisation
ainsi que le note D. Néel ([21]), bien que la description obtenue
soit assez volumineuse (38 définitions sémantiques pour la règle 50,
cf. Annexe 4-C).

<footnote>(1) Il se trouve que dans ce cas, bien qu'utilisé explicitement pour la clarté de la définition, cet attribut n'apporte en fait aucune modification effective aux valeurs déjà calculées.</footnote>
## Conclusion

La démarche de ce rapport vise à obtenir une définition de Lisp et une implantation, ou tout au moins réaliser une première étape vers l'implantation. Ces deux objectifs ont des aspects contradictoires. Ainsi on demande à une définition d'être aussi lisible, claire et concise que possible alors que l'implantation doit être efficace. La méthode des attributs utilisée nous paraît lisible dans la mesure où un nombre pas trop grand d'attributs interviennent dans la description du code généré et où les concepts portés par chaque attribut sont assez simples. Par contre il est certain que dès qu'un grand nombre d'optimisations est introduit le nombre d'attributs augmente sensiblement et la lisibilité en souffre. Il reste qu'un des avantages de la méthode utilisée est d'avoir une bonne fiabilité, tous les calculs et les variables utilisés (les attributs) étant définis ou regroupés au sein de chaque règle où leur "présence" s'avère pertinente.

Dans un premier temps la description fournie en annexe 4 (A, B, C) constitue la définition recherchée. L'introduction d'optimisations peut se faire progressivement dans la mesure où elles ne remettent pas toute la description en question. C'est le cas des optimisations essentielles. L'introduction de ces optimisations augmente le nombre des attributs sans cependant nuire à la fiabilité (cf. Annexe 4-D). Cette deuxième description est plus opérationnelle mais plus laborieuse pour une définition du langage. La technique de preuve introduite dans le rapport [20] montre qu'il est possible d'introduire des vérifications de la description finale.
Remerciements

Je tiens à remercier Messieurs Pair et Lorho ainsi
que Mesdames Gaudel et Mazaud pour l'aide efficace
qu'ils m'ont apportée dans ce travail.

---
Bibliographie

[1] Mc CARTHY & al. LISP 1.5 Programmer Manual, The MIT Press, Cambridge, Mass.
1962.

[2] D. RIBBENS - Programmation non numérique LISP 1.5, Dunod, Paris, 1969 (French)

[3] MACLISP Reference Manual. MIT Projet MAC - Cambridge, December 1975.

[4] W. TEITELMAN - Interlisp Reference Manual - Xerox Palo Alto Research Center - 1974.

[5] P. GREUSSAY. Descriptions compactes d'interprètes implémentables. Une application au langage conniver. 2ème colloque international sur la Programmation Paris - Avril 1976 (French)

[6] M. BERTHOD. FORLISP1 : Un Lisp hyperportable - Rapport Laboria n° 174
Juin 1976 (French)

[7] M. NORDSTROM & al. - LISP FI : a FORTRAN implementation of Lisp 1.5,
Uppsala University, 1971.

[8] Mc DERMOTT D.V., SUSSMAN G.J., The conniver Reference Manual, MIT Artificial Intelligence Memo n° 259 a, January 1974.

[9] C. HEWITT. Description and theoretical canalysis (using schemas)
of PLANNER : A language for proving theorems and manipulating models
in a robot. Doctoral dissertation - MIT - 1971.

[10] REDUCE - Manuel d'utilisation.

[11] A. LUX - Etude d'un modèle abstrait pour une machine Lisp et de son implémentation - Thèse, Université Scientifique et Médicale de Grenoble, 19 mars 1975 (French)

[12] CP/CMS - Manuel LISP sous CMS. Grenoble - IMAG - 1974

[13] D.C. SMITH. MLISP - Artificial Intelligence Project Memo AIM-135.
Stanford University, 1970.
[14] B. LORHO - De la définition à la traduction des langages de programmation : méthode des attributs sémantiques. Thèse, Université Paul Sabatier, Toulouse, 29 novembre 1974 (French)

[15] C. PAIR, M. AMIRCHAHY, D. NEEL - Preuves de descriptions de traitements de textes par Attributs. IRIA-LABORIA Avril 1976 (French).

[16] J. Mc CARTHY. Recursive functions of symbolic expressions and their computation by machine. CACM Vol 3, pp. 184-195, avril 1960.

[17] A.C. HEARN - Standard Lisp in Borbrow D.G.(ed.) : LISP Bulletin, ACM SIGPLAN Notice, Vol 4 n° 9 (Sept. 1969) pp 25-45.

[18] M. MAZAUD. Un langage Intermédiaire pour la traduction des langages algorithmiques - Rapport de Recherche n° 178 IRIA-LABORIA - Juillet 1976, (French)

[19] R.L. LONDON - Correctness of two compilers for a Lisp subset, Report CS240, University of Stanford, October 1971.

[20] P. DERANSART - Description par attributs sémantiques de Lisp pur et preuve de l'équivalence de la définition traductive et de l'évaluateur - Rapport de Recherche n° 220 - IRIA-LABORIA - Mars 1977. (French).

[21] D. NEEL - Contribution à la formalisation de l'amélioration de code par attributs sémantiques. Thèse - Université de Paris 6 - 4 Février 1975 (French)

[22] E. LEWIS - An introduction to ITS for the MACSYMA User. Mathlab Memo 3 - MIT - Cambridge, April 1976.

[23] J. MOSES - The function of FUNCTION in LISP, MIT Artificial Intelligence Laboratory. Report 199, June 1970.

[24] E. SANDEWALL - A proposed solution to the FUNARG problem, Uppsala University - Report n° 29, November 1970.

[25] M.C. NEWEY - Formal semantic of Lisp with applications to program correctness. Stanford University - California, Dept. of Computer Science, January 1975.
# ANNEXE 1

## Expressions usuelles et valeur

Le type associé à une expression est APVAL si c'est une constante, SUBR, FSUBR, EXPR ou FEXPR sinon, le type étant alors le type de la fonction.

<table><thead><tr><th>Expression</th><th>Type</th><th>Valeur</th></tr></thead><tbody><tr><td>nombre</td><td>(1)</td><td>nombre</td></tr><tr><td>T</td><td>APVAL</td><td>T</td></tr><tr><td>NIL</td><td>APVAL</td><td>NIL</td></tr><tr><td>LPAR</td><td>APVAL</td><td>(</td></tr><tr><td>RPAR</td><td>APVAL</td><td>)</td></tr><tr><td>BLANK</td><td>APVAL</td><td>blanc</td></tr><tr><td>Chaîne</td><td>APVAL<br>variable <sup>(2)</sup></td><td>valeur de la constante<br>valeur associée</td></tr></tbody></table>

## FONCTIONS ARITHMETIQUES :

<table><tr><td>(PLUS X Y...Z)</td><td>SUBR</td><td>somme des arguments évalués <sup>(3)</sup></td></tr><tr><td>(DIFFERENCE X Y)</td><td>SUBR</td><td>différence des arguments</td></tr><tr><td>(MINUS X)</td><td>SUBR</td><td>changement de signe</td></tr><tr><td>(DIVIDE X Y)</td><td>SUBR</td><td>division de X par Y</td></tr><tr><td>(TIMES X Y...Z)</td><td>SUBR</td><td>produit des arguments évalués</td></tr></table>

## FONCTIONS PREDICAT (résultat T ou NIL) :

<table><tr><td>(NULL X)</td><td>SUBR</td><td>teste l'égalité à NIL</td></tr><tr><td>(NOT X)</td><td>SUBR</td><td>inversion d'une valeur logique<br>(MACLISP)</td></tr><tr><td>(EQUAL X Y)</td><td>SUBR</td><td>teste l'égalité des S-expressions<br>après évaluation</td></tr><tr><td>(NUMBERP X)</td><td>SUBR</td><td>teste si l'argument est une<br>valeur numérique</td></tr><tr><td>(GREATERP X Y)</td><td>SUBR</td><td>teste X > Y (arguments numériques)</td></tr><tr><td>(LESSP X Y)</td><td>SUBR</td><td>teste X < Y</td></tr><tr><td>(MEMBER X Y)</td><td>SUBR</td><td>teste si l'adresse 'X appartient à<br>la liste d'atomes Y</td></tr><tr><td>(AND X Y... Z)</td><td>FSUBR</td><td>teste si tous les arguments ont<br>une valeur différente de NIL.</td></tr></table>

<footnote>(1) Assimilé au type AVAL.</footnote>

<footnote>(2) Test par défaut.</footnote>

<footnote>(3) Dans le cas des fonctions SUBR ou EXPR la précision "arguments évalués" est toujours vraie et est implicite.</footnote>
(OR X Y ... Z) FSUBR teste si l'un des arguments a une valeur différente de NIL.

MANIPULATION DE LISTES

(LIST X Y ... Z) SUBR rend la liste des arguments évalués
(LENGTH X) SUBR longueur de la liste X
(REVERSE X) SUBR rend la liste inverse
(APPEND X Y) SUBR concaténation des deux listes avec duplication
(NCONC X Y) SUBR concaténation de deux par chaînage (1er argument modifié)

MANIPULATION DE S-GRAPHE'S

(CAR X) SUBR pointeur gauche de la cellule
(CDR X) SUBR pointeur droit de la cellule
(CONS X Y) SUBR nouvelle cellule avec pointeurs X et Y évalués
(EQ X Y) SUBR inégalité de deux pointeurs
(ATOM X) SUBR teste si l'argument est un atome
(RPLACA X Y) SUBR met le pointeur Y dans le CAR de X
(RPLACD X Y) SUBR met le pointeur Y dans le CDR de X

UTILITAIRES DU LANGAGE

(GET atome type) (4) SUBR teste le type de l'atome
(PUTPROP atome type valeur) SUBR valeur conventionnelle : NIL
(REMPROP atome type) SUBR valeur conventionnelle : NIL
(EVAL S-expr aliste) SUBR résultat de l'évaluation en utilisant une aliste
(EVAL S-expr) SUBR id. sans aliste explicite
(APPLY S-expr listvarg aliste) SUBR résultat de l'application d'une fonction (S-expr) à une liste de valeurs d'arguments en utilisant une aliste
(APPLY S-expr listvar) SUBR id. sans aliste explicite
(COMPILE nom) SUBR nom (après compilation et rangement de la fonction compilée en LAP).
(PRINT X) SUBR écriture d'une S-expression
(READ F) SUBR lecture d'une S-expression sur le fichier F
## FONCTIONS DEFINISSANT LE LANGAGE

<table><tr><td>(QUOTE S-expr)</td><td>FSUBR</td><td>S-expression</td></tr><tr><td>(COND liste de clauses)</td><td>FSUBR</td><td>résultat de l'évaluation des clauses (evcon)</td></tr><tr><td>(LABEL nom fonction)</td><td>FSUBR</td><td>cf. évaluateur</td></tr><tr><td>(PROG(listvar) liste de S-expr)</td><td>FSUBR</td><td>argument évalué de RETURN</td></tr><tr><td>(PROGN(listvar)liste de S-expr)</td><td>FSUBR</td><td>dernier argument évalué</td></tr><tr><td>(GO atome)</td><td>FSUBR</td><td>non définie</td></tr><tr><td>(SETQ variable Y)</td><td>FSUBR</td><td>Y (variable := valeur de Y)</td></tr><tr><td>(CSETQ X Y)</td><td>FSUBR</td><td>Y (la constante X a la valeur Y évalué)</td></tr><tr><td>(DEFINE nom fonction)</td><td>SUBR</td><td>nom (après création de la fonction : EXPR)</td></tr><tr><td>(SET variable Y)</td><td>SUBR</td><td>Y</td></tr><tr><td>(CSET variable Y)</td><td>SUBR</td><td>Y (la constante obtenue à la valeur du 2ème argument)</td></tr><tr><td>(LAMBDA(listvar) S-expr)</td><td>non défini<sup>(5)</sup></td><td>valeur du 2ème argument (après liaisons des variables et évaluation d'autres arguments).</td></tr><tr><td>(FLAMBDA(listvar) S-expr)</td><td>non défini</td><td>id. sans évaluation des autres arguments.</td></tr></table>

Remarque : Cette liste de 57 fonctions est extrêmement partielle. Lisp 1.5 du MIT avait au moins 147 fonctions [1] et Maclisp en a au moins 200 [3].

(4) La nature des arguments n'est indiquée que pour faciliter la compréhension. Il s'agit ici de la nature des arguments après évaluation.

(5) Ces expressions n'existent qu'en partie gauche d'une liste dont les autres éléments sont les arguments.
# ANNEXE 2

## A - Evaluateur de référence avec aliste explicite :

Cet évaluateur ne traite que les aspects récursifs du langage et n'émet pas de message d'erreur (on suppose que l'évaluation se termine). Il est écrit en simili ALGOL 68.

### eval (forme, aliste)

if atom(form)

then if getp(forme, 'apval) co type APVAL co

then get(forme, 'apval) co le résultat est la valeur de la constante co
elif asocp(forme, aliste) co valeur associée à l'atome dans la liste co
then assoc(forme, aliste) else error fi

elif atom(car(forme)) co fonction réduite à un atome co

then if getp(car(form), 'expr) co fonction de type EXPR co

then apply(get(car(forme), 'expr), evlis(cdr(forme), aliste), aliste)

co appel de apply après évaluation de la liste d'arguments co

elif getp(car(forme), 'subr) co fonction de type SUBR co

then apply(car(forme), evlis(cdr(forme), aliste), aliste)

co id co

elif getp(car(forme), 'fexpr) co fonction de type FEXPR co

then apply(get(car(forme), 'fexpr), cdr(forme), aliste)

co appel de apply sans évaluation de la liste d'arguments co

elif getp(car(forme), 'fsubr) co fonction de type SUBR co

then apply(car(forme), cdr(forme), aliste) co id. co

elif asocp(car(forme), aliste)

then eval(cons(assoc(car(forme), aliste), cdr(forme)), aliste)

co évaluation d'une nouvelle S-expression formée avec la valeur associée de l'atome en position de fonction et les arguments co

else error

fi

elif eq(caar(forme), 'flambda) co fλ-expression rencontrée co

then apply(car(forme), cdr(forme), aliste)

co application de la fonction avec la liste des arguments inchangée co

elif eq(caar(forme), 'lambda) co -expression rencontrée co

then apply(car(forme), evlis(cdr(forme), aliste), aliste)

co id. mais les arguments sont évalués co

elif eq(caar(forme), 'label) co un label est rencontré co

then eval(cons(cadar(forme), cdr(forme)),
  cons(cons( cadar(forme, cadar(forme)), aliste)
co évaluation de la nouvelle forme avec adjonction du
corps de la fonction dans la aliste co

else co la fonction est une forme co
eval(cons.eval(car(forme), aliste), cdr(forme)), aliste)

fi

apply(fonction, listvarg, aliste)

if atom(fonction)

then if or(getp(fonction, 'subr), getp(fonction, 'fsubr))
co teste si la fonction est un atome du type SUBR ou FSUBR co
then push(listvarg) ; execl(fonction, length(listvarg))
else error fi

else co la fonction est une λ ou fλ-expression co
eval(caddr(fonction), pairlis(cadr(fonction), listvarg, aliste))
co le corps de la fonction est évalué après liaisons effectuées
sur la aliste co

fi

evlis(listarg, aliste)

if eq(listarg, nil) co teste la liste des argument vide co
then nil
else cons.eval(car(listarg), aliste), evlis(cdr(listarg), aliste))
co formation d'une nouvelle liste avec termes évalués
de gauche à droite co

fi

pairlis(listvar, listvarg, aliste)

if eq(listvar, nil)

then aliste
co si la liste des variables est nil alors la aliste est inchangée co
elif atom(listvar)
then cons(cons(listvar, listvarg), aliste)
co dans une λ-expression du type ((λ X ...) listarg) la variable X
est liée à la liste des arguments co

elif null(listvarg) then error

else cons(cons(car(listvar), car(listvarg)),
pairlis(cdr(listvar), cdr(listvarg), aliste))
co dans une λ-expression avec une liste de variables, chaque variable
est liée à un argument sur la aliste co

fi
## B - Evaluateur de référence sans aliste explicite

Les commentaires, lorsqu'ils sont omis, correspondent à ceux de l'annexe 2A. Le point virgule correspond à une exécution séquentielle.

### `evall(form)`
*   `if` `atom(forme)`
*   `then` `if` `getp(forme, 'apval')`
    *   `then` `get(forme, 'apval')`
    *   `else` `assoc1(forme)`
*   `fi`
*   `elif` `atom(car(forme))`
*   `then` `if` `getp(car(forme), 'expr')`
    *   `then` `apply1(get(car(forme), 'expr), evlis1(cdr(forme)))`
    *   `elif` `getp(car(forme), 'subr')`
    *   `then` `apply1(get(car(forme), 'subr), evlis1(cdr(forme)))`
    *   `elif` `getp(car(forme, 'fexpr')`
    *   `then` `apply1(get(car(forme), 'fexpr), cdr(forme))`
    *   `elif` `getp(car(forme), 'fsubr')`
    *   `then` `apply1(get(car(forme), 'fsubr), cdr(forme))`
    *   `else` `evall(cons(assoc1(car(forme)), cdr(forme)))`
*   `fi`
*   `elif` `eq(caar(forme), 'flambda')`
*   `then` `if` `null(cadar(forme))`
    *   `then` `apply1(car(forme), 'nil')`
    *   `else` `apply1(car(forme), cdr(forme)`
*   `fi`
*   `elif` `eq(caar(forme), 'lambda')`
*   `then` `if` `null(cadar(forme))`
    *   `then` `apply1(car(forme), 'nil')`
    *   `else` `apply1(car(forme), evlis1(cdr(forme)))`
*   `fi`
*   `elif` `eq(caar(forme), 'label')`
*   `then` `push11(cadar(forme), caddar(forme)) ; evall(cons(caddar(forme),
    `cdr(forme))) ; pop11(cadar(forme))`
*   `else` `evall(cons(evall(car(forme)), cdr(forme)))`
*   `fi`
**applyl**(*fonction*, *listvarg*)

*co* les arguments de la fonction appliquée par *applyl* sont supposés être en sommet de "pile des arguments" et toujours en nombre suffisant *co*.

*if* *atom*(*fonction*)

*then* *if* or (*getp*(*fonction*, *'subr**), *getp*(*fonction*, *'fsubr*))
*then* *push*(*listvarg*) ; *exec1*(*fonction*, *length*(*listvarg*))
*fi*

*else* *push1*(*cadr*(*fonction*)) ; *evall*(*caddr*(*fonction*)) ; *pop1*(*cadr*(*fonction*))
*fi*

**evlisl**(*listarg*)

*if* *eq*(*listarg*, *'nil') *then* *'nil*
*else* *cons*(*evall*(*car*(*listarg*)) , *evlisl*(*cdr*(*listarg*))
*fi*

**pushl**(*listvar*, *listarg*)

*co* fonction créant les liaisons variable-argument *co*
*if* *eq*(*listvar*, *'nil')
*then* *'nil*
*elif* *atom*(*listvar*)
*then* *pushl*(*listvar*, *listarg*)
*else* *pushl*(*car*(*listvar*), *cdr*(*listarg*)) ; *pushl*(*cdr*(*listvar*), *cdr*(*listarg*))
*fi*

**popl**(*listvar*)

*co* fonction éliminant les liaisons créées *co*
*if* *eq*(*listvar*, *'nil')
*then* *'nil*
*elif* *atom*(*listvar*)
*then* *popl*(*listvar*)
*else* *popl*(*car*(*listvar*)) ; *popl*(*cdr*(*listvar*))
*fi*

Les fonctions *pushl*, *popl*, *push*, *exec1* et *length* sont définies à l'annexe 2-C.
## C - Evaluateur de référence sans aliste explicite, défini en Lisp

Cet évaluateur prend en compte les expressions écrites selon la grammaire Lisp la plus générale (Annexe 3-B). Il est écrit en Lisp compilable (grammaire de l'annexe 3-A) et constitue donc une extension de celui-ci. Il est possible de le compiler et donc d'implanter, à l'aide de ce compilateur, le sous-système Lisp décrit au chapitre 1.

Ce "bootstraping" nécessite d'introduire quelques fonctions manipulant la pile des arguments et lançant l'exécution de sous-programmes. Ce sont :

*   `PUSH(Listarg)`
    Expansion d'une liste d'arguments en sommet de pile (règle 27)

*   `PUSHL1(var, arg)`
    Empilement sur la pile de liens de var de la valeur arg, sans que celle-ci soit empilée sur la pile des arguments (règle 35) var et arg sont dépilés.

*   `POPL1(var)`
    Dépilement de la pile de liens de la variable fournie en arguments ; var est dépilée.

*   `EXEC1(Fonction, n)`
    Exécute la fonction, dépile les n arguments, le résultat étant au sommet.
eval1 (Forme)
(LAMBDA (F)
COND ((ATOM F)
COND ((GETP F 'APVAL)
      (GET F 'APVAL) )
      (T(ASSOC1 F)) )
((ATOM(CAR F))
COND ((GETP(CAR F) 'EXPR)
      (APPLY1 (GET(CAR F) 'EXPR)
              (EVLIS1(CDR F)) ) )
      ((GETP(CAR F) 'FEXPR)
       (APPLY1 (GET(CAR F) 'FEXPR)
               (CDR F) ) )
      ((GETP(CAR F) 'SUBR)
       (APPLY1 (GET(CAR F) 'SUBR)
               (EVLIS1(CDR F)) ) )
      ((GETPITT(CAR F) 'FSUBR)
       (APPLY1 (GET(CAR F) 'FSUBR)
               (CDR F) ) )
      (T(EVAL1(CONS(ASSOC1(CAR F))
                      (CDR F) ))) )
((EQ(CAR(CAR F)) 'LAMBDA)
COND ((NULL(CAR(CDR(CAR F)))))
      (APPLY1(CAR F) NIL) )
      (T(APPLY1(CAR F)(EVLIS1(CDR F)) ) )
((EQ(CAR(CAR F)) 'FLAMBDA)
COND ((NULL(CAR(CDR(CAR F)))))
      (APPLY1(CAR F) NIL) )
      (T(APPLY1(CAR F)(CDR F))) ) )
((EQ(CAR(CAR F)) 'LABEL)
PROG (U) (PUSHL1 (CAR(CDR(CAR F))))
      (CAR(CDR(CDR(CAR F))))) )
      (SETQ U(EVAL1(CONS(CAR(CDR(CAR F)))))
           (CDR F) )))
      (POPL1(CAR(CDR(CAR F)))))
      (RETURN U) ) )
      (T(EVAL1(CONS(EVAL1(CAR F))
                      (CDR F) ))) ) )
apply1(Fonction, Listvarg)
(LAMBDA(F L)
(COND((ATOM F)
(COND((NULL L)
(EXEC1 F O) )
(T(PROG() (PUSH L )
(EXEC1 F(LENGTH L)))))
(NULL L)
(EVAL1(CAR(CDR(CDR F))) ) )
(T(PROG(U) (PUSHL (CAR(CDR F))L)
(SETQ U(EVAL1(CAR(CDR(CDR F)))))
(POPL(CAR(CDR F)))
(RETURN U))) ) )

evlis1 (Listarg)
(LAMBDA(L)
(COND((NULL L)NIL)
(T(CONS(EVAL1(CAR L))
(EVLIS1(CDR L)) ) ) )

push1 (Listvar, Listarg)
(LAMBDA(V L)
(COND((NULL V)NIL)
((ATOM V)(PROG() (PUSHL1 V L)
(RETURN NIL) ) )
(T(PROG() (PUSHL1 (CAR V) (CAR L))
(PUSHL(CDR V)(CDR L)) ) ) )

pop1 (Listvar)
(LAMBDA(V)
(COND((NULL V)NIL)
((ATOM V)(PROG() (POPL1 V)
(RETURN NIL) ) )
(T(PROG() (POPL1 (CAR V))
(POPL(CDR V)) ) ) )

length (Liste)
(LAMBDA(L)
(COND((NULL L)O)
(T(PLUS 1(LENGTH(CDR L))))) ) )
# ANNEXE 3

## A - Syntaxe du sous-langage Lisp

Notation proche de la BNF, utilisée dans le système DELTA [14].

<table><tr><td>1</td><td>&lt;Fonction&gt;</td><td>= (LAMBDA(&lt;Listvar&gt;&lt;Forme&gt;)</td></tr><tr><td>2</td><td></td><td>= (FLAMBDA(&lt;Listvar&gt;&lt;Forme&gt;)</td></tr><tr><td>3</td><td>&lt;Forme&gt;</td><td>= &lt;Fatom&gt; <u>co</u> forme atomique <u>co</u></td></tr><tr><td>4</td><td></td><td>= &lt;Fnatom&gt; <u>co</u> forme non atomique <u>co</u></td></tr><tr><td>5</td><td>&lt;Fatom&gt;</td><td>= nombre</td></tr><tr><td>6</td><td></td><td>= T</td></tr><tr><td>7</td><td></td><td>= NIL</td></tr><tr><td>8</td><td></td><td>= ( )</td></tr><tr><td>9</td><td></td><td>= Ident</td></tr><tr><td>10</td><td>&lt;Fnatom&gt;</td><td>= (QUOTE S-expr)<br/><u>co</u> syntaxe de S-expr fournie au chapitre 1, 1.2 ;<br/>assimilé ici à un terminal <u>co</u></td></tr><tr><td>11</td><td></td><td>= (COND &lt;Listcond&gt;)</td></tr><tr><td>12</td><td></td><td>= (PROG (&lt;Listvar&gt;) &lt;Listprog&gt;)</td></tr><tr><td>13</td><td></td><td>= (GO Ident)<br/><u>co</u> seul le GO non calculé est examiné ici <u>co</u></td></tr><tr><td>14</td><td></td><td>= (SETQ Ident &lt;Forme&gt;)</td></tr><tr><td>15</td><td></td><td>= (CSETQ Ident &lt;Forme&gt;)</td></tr><tr><td>16</td><td></td><td>= (OR &lt;Listar&gt;)</td></tr><tr><td>17</td><td></td><td>= (AND &lt;Listand&gt;)</td></tr><tr><td>18</td><td></td><td>= (LIST &lt;Listlist&gt;)</td></tr><tr><td>19</td><td></td><td>= (TIMES &lt;Listtimes&gt;)</td></tr><tr><td>20</td><td></td><td>= (PLUS &lt;Listplus&gt;)<br/><u>co</u> à partir d'ici les fonctions SUBR ont pour arguments un nombre déterminé de formes <u>co</u></td></tr><tr><td>21</td><td></td><td>= (CAR &lt;Forme&gt;)</td></tr><tr><td>22</td><td></td><td>= (CDR &lt;Forme&gt;)</td></tr><tr><td>23</td><td></td><td>= (CONS &lt;Forme&gt; &lt;Forme&gt;)</td></tr><tr><td>24</td><td></td><td>= (EQ &lt;Forme&gt; &lt;Forme&gt;)</td></tr><tr><td>25</td><td></td><td>= (ATOM &lt;Forme&gt;)</td></tr><tr><td>26</td><td></td><td>= (EXEC &lt;Forme&gt; &lt;Forme&gt;)</td></tr><tr><td>27</td><td></td><td>= (EXEC1 &lt;Forme&gt;&lt;Forme&gt;)</td></tr><tr><td>28</td><td></td><td>= (NEQ &lt;Forme&gt; &lt;Forme&gt;)</td></tr></table>
29 = (NULL <Forme>)

30 = (PRINT <Forme>)

31 = (READ)

32 = (ASSOC1 <Forme>)

33 = (GET <Forme> <Forme>)

34 = (GETP <Forme> <Forme>)

35 = (PUSHL1 <Forme> <Forme>)

36 = (POPL1 <Forme>)

37 = (NUMBERP <Forme>)

38 = (ZEROP <Forme>)

39 = (DIFFERENCE <Forme> <Forme>)

40 = (<Fsubr> <Listarg>)

<sub>co</sub> fonction compilée SUBR quelconque <sub>co</sub>

41 = (<Fnasubr> <Listarg>)

<sub>co</sub> fonction décrite par λ ou label-expression <sub>co</sub>

42 = (<Ffsubr> <Listexpr>)

<sub>co</sub> fonction compilée FSUBR quelconque <sub>co</sub>

43 = (<Fnafsubr> <Listexpr>)

<sub>co</sub> fonction décrite pour fλ ou label contenant une
fonction n'évaluant pas ses arguments <sub>co</sub>

44 <Fsubr>
et suiv.
= <sub>co</sub> liste fournie dans le système de fonctions SUBR de
catégorie 1 et non de 1. En particulier : <sub>co</sub>

45 <Ffsubr>
et suiv.
= <sub>co</sub> liste fournie dans le système de fonctions FSUBR. Dans
ce sous-système il n'y en a pas. Nous nous con-
tentons d'une fonction bidon appelée FSUBR <sub>co</sub> FSUBR

46 <Fnasubr> = (LAMBDA(<Listvar>)/<Forme>)

47 <Fnafsubr> = (FLAMBDA(<Listvar>)/<Forme>)

48 <Listvar> = Ident <Listvar>

49 = empty

50 <Listcond> = ((<Forme> <Forme>)/<Listond>)

51 = (<Forme> <Forme>)

52 <Listprog> = <Forme> <Listprog>

53 = <Forme>

<sub>co</sub> on suppose qu'une forme PROG n'est pas vide <sub>co</sub>

54 <Listor> = <Forme> <Listor>

55 = <Forme> <Forme>
<table><tr><td>56</td><td>&lt;Listand&gt;</td><td>= &lt;Forme&gt; &lt;Listand&gt;</td></tr><tr><td>57</td><td></td><td>= &lt;Forme&gt; &lt;Forme&gt;</td></tr><tr><td>58</td><td>&lt;Listlist&gt;</td><td>= &lt;Forme&gt; &lt;Listlist&gt;</td></tr><tr><td>59</td><td></td><td>= &lt;Forme&gt;</td></tr><tr><td>60</td><td>&lt;Listtimes&gt;</td><td>= &lt;Forme&gt; &lt;Listtimes&gt;</td></tr><tr><td>61</td><td></td><td>= &lt;Forme&gt; &lt;Forme&gt;</td></tr><tr><td>62</td><td>&lt;Listplus&gt;</td><td>= &lt;Forme&gt; &lt;Listplus&gt;</td></tr><tr><td>63</td><td></td><td>= &lt;Forme&gt; &lt;Forme&gt;</td></tr><tr><td>64</td><td>&lt;Listarg&gt;</td><td>= &lt;Forme&gt; &lt;Listarg&gt;</td></tr><tr><td>65</td><td></td><td>= empty</td></tr><tr><td>66</td><td>&lt;Listexpr&gt;</td><td>= S-expr &lt;Listexpr&gt;</td></tr><tr><td>67</td><td></td><td>= empty</td></tr><tr><td>68</td><td>&lt;Fnatom&gt;</td><td>= (PUSH &lt;Forme&gt;)</td></tr></table>

Nota : les fonctions EXEC1, PUSH, POPL, PUSHL1 servent exclusivement à écrire l'évaluateur de Lisp compilable.

La fonction CSETQ modifie le contexte global.

Les fonctions SETQ, LABEL (cf. l'évaluateur) modifient le contexte local.
B - Syntaxe de Lisp

Cette syntaxe correspond aux expressions susceptibles d'être fournies
à l'évaluateur de référence et d'être évaluées sans provoquer d'erreur. Ceci
suppose évidemment que si au cours de l'évaluation des expressions sont
construites et évaluées, celles-ci restent "bien formées". Ceci suppose
également qu'aucune fonction nouvelle n'est créée.

1. `<Forme>` = `<Fatom>`

2. = `<Fnatom>`

3. `<Fatom>` = Ident

4. * `<Fnatom>` = `<F-subr> <Listarg>`
= `<F-expr> <Listarg>`

6. = `<F-fsubr> <Listexpr>`

7. = `<F-fexpr> <Listexpr>`
`_` ces quatre règles correspondent aux types de
fonctions principaux `_`

8. = `<Fna-subr> <Listarg>`

9. = `<Fna-fsubr> <Listexpr>`

_ ces deux règles correspondent aux fonctions
définies dans le texte _

10. = (Ident <Listexpr>)

_ Ident correspond à une variable fonctionnelle,
aucune hypothèse n'est faite sur l'évaluation
des arguments _

11. `<F-subr>` et suiv. = `CAR` | `CDR` | `CONS` | `RPLACA` | `READ` | ...

_ toutes les fonctions fondamentales ou compilées
de type `SUBR co`

12. `<F-expr>` et suiv. = `ASSOC` | `LENGTH` | `MAP` | ...

_ toutes les fonctions non compilées ou non compi-
lables de type `EXPR co`

13. `<F-fsubr>` et suiv. = `QUOTE` | `COND` | `PROG` | `PROGN` | `LIST` | ...

_ toutes les fonctions fondamentales ou compilées
de type `FSUBR co`

14. `<F-fexpr>` = `CONC` | `SELECT` | ...

_ toutes les fonctions non compilées ou non compi-
lables de type `FEXPR co`

15. `<Fna-subr>` = (LAMBDA (<Listvar>) <Forme>)

16. = (LAMBDA Ident <Forme>)

_ pas de label expression du fait que le type
de la fonction peut ne pas être connu _
17. `<Fna-fsubr>` = `(FLAMBDA(<Listvar>)<Forme>)`

18. = `(FLAMBDA Ident <Forme>)`

19. = `(LABEL Ident <Fnatom>)`

20. = `(LABEL Ident <Fonction>)`

`co` 1'évaluateur de référence accepte n'importe quelle forme ou fonction dans un label expression (c

21. = `<Fnatom>`

`co` une forme quelconque peut être en position de fonction (cf. règle 10). `co`

22. `<Fonction>` = `<F-subr>`

23. = `<F-expr>`

24. = `<F-fsubr>`

25. = `<F-fexpr>`

26. = `<Fna-subr>`

27. = `<Fna-fsubr>`

28. `<Listarg>` = `<Forme> <Listarg>`

29. = empty

30. `<Listexpr>` = `S-expr <Listexpr>`

31. = empty

32. `<Listvar>` = `Ident <Listvar>`

33. = empty

<footnote>* Les numéros de règles entourés d'un carré correspondent aux règles qui déterminent les extensions de Lisp compilable à Lisp.</footnote>
## A - Code objet

sp est le rang du sommet de la pile des arguments

spX est le rang du sommet de la pile de liens associée à l'atome X.

c(r) dénote le contenu de l'élément de rang r dans une pile. c(spX) est donc la valeur du lien "assoc" de l'atome X.

Le quote dans PUSHQ'S-expr signifie que la S-expression est implantée dans la zone des cellules et que c'est l'adresse correspondante qui est empilée. Dans PUSHQ'X le quote traduit une recherche dans la table des atomes. Si cette recherche n'aboutit pas, un nouvel atome est créé et son adresse est empilée sur la pile des arguments.

## Instructions de manipulations sur la pile des arguments :

<table><tr><td>PUSHQ'S-graphe</td><td>sp := sp + 1</td></tr><tr><td>co ajout, en sommet de pile,<br>d'un élément co</td><td>c(sp) := 'S-graphe<br>co := co + 1</td></tr><tr><td>PUSHV'X</td><td>sp := sp + 1</td></tr><tr><td>co ajout, en sommet de pile, de<br>la valeur associée à X co</td><td>c(sp) := c(c(spX))<br>co := co + 1</td></tr><tr><td>READF</td><td>sp := sp + 1</td></tr><tr><td>co ajout, en sommet de pile, d'une<br>valeur lue co</td><td>c(sp) := adresse de la S-expression lue<br>co := co + 1</td></tr><tr><td>POP</td><td>sp := sp - 1</td></tr><tr><td>co dépilement co</td><td>co := co + 1</td></tr><tr><td>POP n</td><td>c(sp - n) := c(sp)</td></tr><tr><td>co dépilement de n éléments en<br>dessous du sommet co</td><td>sp := sp - n<br>co := co + 1</td></tr><tr><td>POPT</td><td>c(sp - c(sp) - 1) := c(sp - 1)</td></tr><tr><td>co dépilement d'un nombre d'éléments<br>calculés, en dessous du sommet co</td><td>sp := sp - c(sp) - 1<br>co := co + 1</td></tr><tr><td>SET'X</td><td>c(c(spX)) := c(sp)</td></tr><tr><td>co changement de la valeur associée<br>à X co</td><td>co := co + 1</td></tr><tr><td>POPLT</td><td>spc(sp) := spc(sp) - 1</td></tr><tr><td>co dépilement de la pile de lien<br>de l'élément en sommet de pile co</td><td>sp := sp - 1<br>co := co + 1</td></tr></table>
PUSHT

sp := sp + longueur de liste de c(sp)
co := co + 1

__cf. Annexe 2-C__

SETT

co := co + 1

__id. mais la variable est évaluée__

Instructions de manipulation des piles de liens :

PUSHL 'X n

spX := spX + 1

__nouvelle valeur associée__

POPL 'X

spX := spX - 1

__co := co + 1__

PUSHLT

spc(sp - 1) := spc(sp - 1) + 1

__nouvelle valeur associée de la variable calculée c(sp - 1)__

Instructions concernant les atomes

SETA'X

__mise à jour du pointeur apval__

PUSHR

__assoc(spc(sp))__

PUSHG indic

__c(sp) := get(c(sp), indic)__

PUSHGP indic

__c(sp) := getp(c(sp), indic)__

Instructions de base

CAR

__c(sp) := CAR(c(sp))__

CDR

__c(sp) := CDR(c(sp))__
CONS
    c(sp) := CONS(c(sp - 1), c(sp))
    co := co + 1

DIF
    c(sp) := DIF(c(sp - 1), c(sp))
    co := co + 1

NULT
    c(sp) := NULT(c(sp), c(sp - 1))
    co := co + 1

ADD
    c(sp) := ADD(c(sp - 1), c(sp))
    co := co + 1

### Test de sommet de pile des arguments :

RN
    c(sp) := if c(sp) = nil
              then 't
              else 'nil
              fi
    co := co + 1

NUM
    c(sp) := if c(sp) est un nombre
              then 't
              else 'nil
              fi
    co := co + 1

RZ
    c(sp) := if c(sp) = P
              then 't
              else 'nil
              fi
    co := co + 2

ATOM
    c(sp) := if c(sp) est atomique
              then 't
              else 'nil
              fi
    co := co + 1

NRN
    c(sp) := if c(sp) = 'nil
              then 'nil
              else 't
              fi
    co := co + 1
EQ

c(sp) := if c(sp) = c(sp - 1)
        then 't
        else 'nil
        fi

co := co + 1

NEQ

c(sp) := if c(sp) = c(sp - 1)
        then 'nil
        else 't
        fi

co := co + 1

## Instructions de branchement

BR eti

co := eti

BRN eti

co := if c(sp) = nil
        then eti
        else co + 1
        fi

BRT eti

co := if c(sp) ≠ nil
        then eti
        else co + 1
        fi

LINK 'X n

sp := sp + 1

c(sp) := X appliquée aux arguments
        c(sp - 1) à c(sp - n)

co := co + 1

LINKT

c(sp - n - 1) := c(sp) appliquée à
c(sp - 2)... c(sp - n - 1)

où n est le nombre d'arguments.
n = c(sp)

co c(sp) est la fonction recherchée
appliquée à sa liste d'arguments

RETURN

Agit sur la pile de retours. Non étudié ici.

## Instruction de sortie

FORMAT

Sortie de la S-expr. en sommet de pile

co := co + 1
B - Attributs

<table><thead><tr><th>Nom</th><th>Circulation</th><th>Type</th><th>Concept</th></tr></thead><tbody><tr><td>CEVAL</td><td>S</td><td>Ensemble d'instructions</td><td>Code généré</td></tr><tr><td>LBOUND</td><td>S</td><td>Ensemble d'instructions</td><td>Code généré correspondant aux empilements et dépillements de liens dans les λ-expressions</td></tr><tr><td>PBOUND</td><td>S</td><td>Ensemble d'instructions</td><td>id. dans les formes prog.</td></tr><tr><td>LAB</td><td>H,S</td><td>Entier</td><td>Etiquettes d'instruction = numéro de la prochaine instruction</td></tr><tr><td>LAB1</td><td>H</td><td>Entier</td><td>Etiquette de la prochaine instruction de LBOUND</td></tr><tr><td>LAB2</td><td>H</td><td>Entier</td><td>id. mais pour les instructions de dépillement</td></tr><tr><td>LAB3</td><td>H</td><td>Entier</td><td>id. LAB1 mais pour PBOUND</td></tr><tr><td>NB</td><td>S</td><td>Entier</td><td>Compteur d'occurrences</td></tr><tr><td>LABTAB</td><td>H</td><td>Table d'étiquettes</td><td>Table des étiquettes dans une forme prog.</td></tr><tr><td>TAB</td><td>H,S</td><td>Table d'étiquettes</td><td>Relevé des étiquettes dans une forme prog.</td></tr><tr><td>BPROG</td><td>H</td><td>Boolean</td><td>Teste le niveau compatible avec GO et RETURN d'une forme</td></tr><tr><td>BCOND</td><td>H</td><td>Boolean</td><td>Teste si une forme est en deuxième place d'une clause de cond.</td></tr><tr><td>GOFORM</td><td>S</td><td>Boolean</td><td>Teste si une forme est un GO ou un RETURN</td></tr><tr><td>OUTC</td><td>H</td><td>Entier</td><td>Adresse de retour d'un COND</td></tr><tr><td>OUTO</td><td>H</td><td>Entier</td><td>Adresse de retour d'un OR</td></tr><tr><td>OUTA</td><td>H</td><td>Entier</td><td>Adresse de retour d'un AND</td></tr><tr><td>OUTP</td><td>H</td><td>Entier</td><td>Adresse de retour d'un PROG</td></tr><tr><td>TEXT</td><td>standard</td><td>Chaîne</td><td>Attribut standard qui restitue le texte d'un terminal.</td></tr></tbody></table>
## C - Traduction

Pour simplifier l'écriture, l'attribut `CEVAL` est calculé avec une `"union" implicite des ensembles d'instructions ou une "insertion" implicite d'une ou plusieurs instructions décrites sous la forme :

`eti : instruction ;`

Le code généré est souligné.

Les occurrences d'attributs sont notées en lettres majuscules avec le du non-terminal en minuscules et entre parenthèses.

Tout ce qui n'est ni attribut, ni code généré, représente les calculs de l'attribut figurant à gauche du signe `=`.

Ces calculs sont écrits en simili ALGOL 68 ; `"^"` désigne un espace.

1 `<Fonction> = (LAMBDA(<Listvar>)<Forme>)`

<table><tr><td>CEVAL(Fonction)</td><td>= LBOUND(Listvar)</td></tr><tr><td></td><td>CEVAL(Forme)</td></tr><tr><td></td><td>S-LAB(Fonction) :<u>RETURN;</u></td></tr><tr><td>LAB1(Listvar)</td><td>= 1</td></tr><tr><td>LAB2(Listvar)</td><td>= S-LAB(Forme) + NB(Listvar) - 1</td></tr></table>

`<u>co</u>` le dépilement se fait dans l'ordre inverse `<u>co</u>`

<table><tr><td>S-LAB(Fonction)</td><td>= S-LAB(Forme) + NB(Listvar)</td></tr><tr><td>H-LAB(Forme)</td><td>= NB(Listvar) + 1</td></tr><tr><td>BPROG(Forme)</td><td>= false</td></tr><tr><td>BCOND(Forme)</td><td>= false</td></tr><tr><td>LABTAB(Forme)</td><td>= indef</td></tr><tr><td>H-TAB(Forme)</td><td>= indef</td></tr></table>

`<u>co</u>` valeurs introduites pour la cohérence du calcul des attributs `<u>co</u>`

2 `<Fonction> = (FLAMBDA(<Listvar>)<Forme>)`
`id.`

3 `<Forme> = <Fatom>`

<table><tr><td>CEVAL(Forme)</td><td>= CEVAL(Fatom)</td></tr><tr><td>H-LAB(Fatom)</td><td>= H-LAB(Forme)</td></tr><tr><td>S-LAB(Forme)</td><td>= S-LAB(Fatom)</td></tr><tr><td>GOFORM(Forme)</td><td>= false</td></tr><tr><td>BPROG(Fatom)</td><td>= BPROG(Forme)</td></tr><tr><td>BCOND(Fatom)</td><td>= BCOND(Forme)</td></tr><tr><td>H-TAB(Fatom)</td><td>= H-TAB(Forme)</td></tr><tr><td>S-TAB(Forme)</td><td>= S-TAB(Fatom)</td></tr></table>
4 <Forme> = <Fnatom>

CEVAL(Forme) = CEVAL(Fnatom)

H-LAB(Fnatom) = H-LAB(Forme)

S-LAB(Forme) = S-LAB(Fnatom)

BPROG(Fnatom) = BPROG(Forme)

GOFORM(Forme) = GOFORM(Fnatom)

LABTAB(Fnatom) = LABTAB(Forme)

H-TAB(Fnatom) = H-TAB(Forme)

S-TAB(Forme) = S-TAB(Fnatom)

5 <Fatom> = nombre

CEVAL(Fatom) = H-LAB(Fatom) :PUSHQ'TEXT(Nombre) ;

S-LAB(Fatom) = H-LAB(Fatom) + 1

S-TAB(Fatom) = H-TAB(Fatom)

6 <Fatom> = T

CEVAL(Fatom) = H-LAB(Fatom) :PUSHQ't ;

S-LAB(Fatom) = H-LAB(Fatom) + 1

S-TAB(Fatom) = H-TAB(Fatom)

7 <Fatom> = NIL

id. avec :PUSHQ'nil ;

8 <Fatom> = ( )

id. 7

9 <Fatom> = Ident

CEVAL(Fatom) =
if BPROG(Fatom) = false or BCOND(Fatom)

then H-LAB(Fatom) :PUSHV'TEXT(Ident) ;

else vide

fi

S-TAB(Fatom) =
if BPROG(Fatom) and BCOND(Fatom) = false

then inclure TEXT(Ident) dans H-TAB(Fatom) avec l'adresse

H-LAB(Fatom)

else H-TAB(Fatom)

fi

S-LAB(Fatom) =
if BPROG(Fatom) and BCOND(Fatom) = false

then H-LAB(Fatom) + 1

else H-LAB(Fatom)

fi
10 <Fnatom> = (QUOTE S-expr)
CEVAL(Fnatom) = H-ETI(Fnatom) :PUSHQ'TEXT(S-expr) ;
GOFORM(Fnatom) = false
S-TAB(Fnatom) = H-TAB(Fnatom)
S-LAB(Fnatom) = H-LAB(Fnatom) + 1

11 <Fnatom> = (COND< Listcond >)
CEVAL(Fnatom) = CEVAL(Listcond)
BPROG(Listcond) = BPROG(Fnatom)
GOFORM(Fnatom) = false
LABTAB(Listcond) = LABTAB(Fnatom)
S-TAB(Fnatom) = H-TAB(Fnatom)
OUTC(Listcond) = S-LAB(Listcond)
OUTP(Listcond) = OUTP(Fnatom)

12 <Fnatom> = (PROG(<Listvar>)<Listprog>)
CEVAL(Fnatom) = PBOUND(Listvar)
               CEVAL(Listprog)
               S-LAB(Listprog) + NB(Listvar) : POP^NB(Listvar);
S-LAB(Fnatom) = S-LAB(Listprog) + NB(Listvar) + 1
H-LAB(Listprog) = H-LAB(Fnatom) + 2 * NB(Listvar)

<u>co</u> pour chaque variable on empile nil qu'on lie à la variable soit
2 instructions <u>co</u>
LAB 3(Listvar) = H-LAB(Fnatom)
LAB 2(Listvar) = S-LAB(Listprog) + NB(Listvar) - 1
LAB 1(Listvar) = indef
GOFORM(Fnatom) = false
LABTAB(Listprog) = S-TAB(Listprog)
H-TAB(Listprog) = tablevide
OUTP(Listprog) = S-LAB(Listprog)

13 <Fnatom> = (GO Ident)
CEVAL(Fnatom) =
  if BPROG(Fnatom) = false
  then error('forme GO non autorisée')
  elif TEXT(Ident ∈ LABTAB(Fnatom)
  then H-LAB(Fnatom) :BR^étiquette de TEXT(Ident) dans LABTAB(Fnatom);
  else error('référence non satisfaite dans forme prog').
fi
GOFORM(Fnatom) = true
S-TAB(Fnatom) = H-TAB(Fnatom)
13 bis <Fnatom> = (RETURN<Forme>)

CEVAL(Fnatom) =
  if BPROG(Fnatom) = false
  then error('forme RETURN non autorisée')
  else CEVAL(Forme)

S-LAB(Forme) : BR^OUTP(Fnatom) ;

fi

H-LAB(Forme) = H-LAB(Fnatom)

S-LAB(Fnatom) = S-LAB(Forme) + 1

GOFORM(Fnatom) = true

BPROG(Forme) = false

BCOND(Forme) = false

LABTAB(Forme) = indef

H-TAB(Forme) = indef

S-TAB(Fnatom) = H-TAB(Fnatom)

14 <Fnatom> = (SETQ Ident<Forme>)

CEVAL(Fnatom) = CEVAL(Forme)

S-LAB(Forme) : SET'TEXT(Ident) ;

S-LAB(Fnatom) = S-LAB(Forme) + 1

H-LAB(Forme) = H-LAB(Fnatom)

BPROG(Forme) = false

BCOND(Forme) = false

GOFORM(Fnatom) = false

H-TAB(Forme) = indef

S-TAB(Fnatom) = H-TAB(Fnatom)

15 <Fnatom> = (CSETQ Ident<Forme>)

id. à 14 avec :SETA'TEXT(Ident) ;

16 <Fnatom> = (OR<Listor>)

CEVAL(Fnatom) = CEVAL(Listor)

H-LAB(Listor) = H-LAB(Fnatom)

S-LAB(Fnatom) = S-LAB(Listor)

GOFORM(Fnatom) = false

S-TAB(Fnatom) = H-TAB(Fnatom)

OUTO(Listor) = S-LAB(Listor)
17 <Fnatom> = (AND<Listand>)

<table><tr><td>CEVAL(Fnatom)</td><td>= CEVAL(Listand)</td></tr><tr><td>H-LAB(Listand)</td><td>= H-LAB(Fnatom)</td></tr><tr><td>S-LAB(Fnatom)</td><td>= S-LAB(Listand)</td></tr><tr><td>GOFORM(Fnatom)</td><td>= false</td></tr><tr><td>S-TAB(Fnatom)</td><td>= H-TAB(Fnatom)</td></tr><tr><td>OUTA(Listand)</td><td>= S-LAB(Listand)</td></tr></table>

18 Fnatom = (LIST<Listlist>)

<table><tr><td>CEVAL(Fnatom)</td><td>= CEVAL(Listlist)</td></tr><tr><td>H-LAB(Listlist)</td><td>= H-LAB(Fnatom)</td></tr><tr><td>S-LAB(Fnatom)</td><td>= S-LAB(Listlist)</td></tr><tr><td>GOFORM(Fnatom)</td><td>= false</td></tr><tr><td>S-TAB(Fnatom)</td><td>= H-TAB(Fnatom)</td></tr></table>

19 <Fnatom> = (TIMES< Listtimes>)

<table><tr><td>CEVAL(Fnatom)</td><td>= CEVAL(Listtimes)</td></tr><tr><td>H-LAB( Listtimes)</td><td>= H-LAB(Fnatom)</td></tr><tr><td>S-LAB(Fnatom)</td><td>= S-LAB( Listtimes)</td></tr><tr><td>GOFORM(Fnatom)</td><td>= false</td></tr><tr><td>S-TAB(Fnatom)</td><td>= H-TAB(Fnatom)</td></tr></table>

20 <Fnatom> = (PLUS< Listplus>)

id 19 avec Listplus au lieu de Listtimes

21 <Fnatom> = (CAR<Forme>)

<table><tr><td>CEVAL(Fnatom)</td><td>= CEVAL(Forme)<br>S-ETI(Forme) : CAR ;</td></tr><tr><td>H-LAB(Forme)</td><td>= H-LAB(Fnatom)</td></tr><tr><td>S-LAB(Fnatom)</td><td>= S-LAB(Forme) + 1</td></tr><tr><td>BPROG(Forme)</td><td>= false</td></tr><tr><td>BCOND(Forme)</td><td>= false</td></tr><tr><td>GOFORM(Fnatom)</td><td>= false</td></tr><tr><td>H-TAB(Forme)</td><td>= indef</td></tr><tr><td>S-TAB(Fnatom)</td><td>= H-TAB(Fnatom)</td></tr></table>
22 <Fnatom> = (CDR<Forme>)

id. à 22 avec CDR au lieu de CAR

23 <Fnatom> = (CONS<Forme><Forme>)

CEVAL(Fnatom) = CEVAL(Forme)
CEVAL(Forme')
S-LAB(Forme') : CONS;
S-LAB(Forme') + 1 : POP^1;

H-LAB(Forme) = H-LAB(Fnatom)
H-LAB(Forme') = S-LAB(Forme)
S-LAB(Fnatom) = S-LAB(Forme') + 2
BPROG(Forme) = false
BPROG(Forme') = false
GOFORM(Fnatom) = false
BCOND(Forme) = false
BCOND(Forme') = false
S-TAB(Fnatom) = H-TAB(Fnatom)
H-TAB(Forme) = indef
H-TAB(Forme') = indef

24 <Fnatom> = (EQ<Forme><Forme>)

CEVAL(Fnatom) = CEVAL(Forme)
CEVAL(Forme')
S-LAB(Forme') : EQ;
S-LAB(Forme') + 1 : POP^1;

H-LAB(Forme) = H-LAB(Fnatom)
H-LAB(Forme') = S-LAB(Forme)
S-LAB(Fnatom) = S-LAB(Forme') + 2
BPROG(Forme) = false
BPROG(Forme') = false
GOFORM(Fnatom) = false
BCOND(Forme) = false
BCOND(Forme') = false
S-TAB(Fnatom) = H-TAB(Fnatom)
H-TAB(Forme) = indef
H-TAB(Forme') = indef
25 <Fnatom> = (ATOM<Forme>)

CEVAL(Fnatom) = CEVAL(Forme)

H-LAB(Forme) : ATOM ;

H-LAB(Forme) = H-LAB(Fnatom)

S-LAB(Fnatom) = S-LAB(Forme) + 1

BPROG(Forme) = false

GOFORM(Fnatom) = false

BCOND(Forme) = false

S-TAB(Fnatom) = H-TAB(Fnatom)

H-TAB(Forme) = indef

26 <Fnatom> = (EXEC1<Forme> <Forme>)

CEVAL(Fnatom) = CEVAL(Forme) CEVAL(Forme')

S-LAB(Forme') : LINKT ;

H-LAB(Forme) = H-LAB(Fnatom)

H-LAB(Forme') = S-LAB(Forme)

S-LAB(Fnatom) = S-LAB(Forme') + 1

BPROG(Forme) = false

BPROG(Forme') = false

GOFORM(Fnatom) = false

BCOND(Forme) = false

BCOND(Forme') = false

S-TAB(Fnatom) = H-TAB(Fnatom)

H-TAB(Forme) = indef

27 Fnatom = (PUSH <Forme>)

CEVAL(Fnatom) = CEVAL(Forme)

S-LAB(Forme) : PUSHT ;

H-LAB(Forme) = H-LAB(Fnatom)

S-LAB(Fnatom) = S-LAB(Forme) + 1

BPROG(Forme) = false

GOFORM(Fnatom) = false

BCOND(Forme) = false

S-TAB(Fnatom) = H-TAB(Fnatom)

H-TAB(Forme) = indef.
28 <Fnatom> = (NEQ<Forme><Forme'>)

CEVAL(Fnatom) = CEVAL(Forme)
               CEVAL(Forme')
               S-LAB(Forme') : NEQ;
               S-LAB(Forme') + 1 : POP^1;

H-LAB(Forme) = H-LAB(Fnatom)

H-LAB(Forme') = S-LAB(Forme)

S-LAB(Fnatom) = S-LAB(Forme') + 2

BPROG(Forme) = false

BPROG(Forme') = false

GOFORM(Fnatom) = false

BCOND(Forme) = false

BCOND(Forme') = false

S-TAB(Fnatom) = H-TAB(Fnatom)

H-TAB(Forme) = indef.

29 <Fnatom> = (NULL <Forme>)

CEVAL(Fnatom) = CEVAL(Forme)
               S-LAB(Forme) : RN;

H-LAB(Forme) = H-LAB(Fnatom)

S-LAB(Fnatom) = S-LAB(Forme) + 1

BPROG(Forme) = false

GOFORM(Fnatom) = false

BCOND(Forme) = false

S-TAB(Fnatom) = H-TAB(Fnatom)

H-TAB(Forme) = Indef.

30 <Fnatom> = (PRINT <Forme>)

CEVAL(Fnatom) = CEVAL(Forme)
               S-LAB(Forme) : PRINTF;

H-LAB(Fnatom) = H-LAB(Fnatom)

S-LAB(Fnatom) = S-LAB(Forme) + 1

BCOND(Forme) = false

BPROG(Forme) = false

GOFORM(Fnatom) = false

S-TAB(Fnatom) = H-TAB(Fnatom)

H-TAB(Forme) = indef.
31 <Fnatom> = (READ)

<table><tr><td>CEVAL(Fnatom)</td><td>= H-LAB(Fnatom) : READF ;</td></tr><tr><td>S-LAB(Fnatom)</td><td>= H-LAB(Fnatom) + 1</td></tr><tr><td>GOFORM(Fnatom)</td><td>= false</td></tr><tr><td>S-TAB(Fnatom)</td><td>= H-TAB(Fnatom)</td></tr></table>

32 <Fnatom> = (ASSOC1<Forme>)

<u>co</u> met en sommet de pile l'adresse de la valeur associée de l'atome en sommet de pile <u>co</u>

<table><tr><td>CEVAL(Fnatom)</td><td>= CEVAL(Forme)<br>S-LAB(Forme) : PUSHR ;</td></tr><tr><td>H-LAB(Forme)</td><td>= H-LAB(Fnatom)</td></tr><tr><td>S-LAB(Fnatom)</td><td>= S-LAB(Forme) + 1</td></tr><tr><td>BPROG(Forme)</td><td>= false</td></tr><tr><td>GOFORM(Fnatom)</td><td>= false</td></tr><tr><td>BCOND(Forme)</td><td>= false</td></tr><tr><td>S-TAB(Fnatom)</td><td>= H-TAB(Fnatom)</td></tr><tr><td>H-TAB(Forme)</td><td>= indef.</td></tr></table>

33 <Fnatom> = (GET <Forme> (QUOTE Ident))

<table><tr><td>CEVAL(Fnatom)</td><td>= CEVAL(Forme)<br>S-LAB(Forme) : PUSHG<sub>IDENT</sub> ;</td></tr><tr><td>H-LAB(Forme)</td><td>= H-LAB(Fnatom)</td></tr><tr><td>S-LAB(Fnatom)</td><td>= S-LAB(Forme) + 1</td></tr><tr><td>BPROG(Forme)</td><td>= false</td></tr><tr><td>GOFORM(Fnatom)</td><td>= false</td></tr><tr><td>BCOND(Forme)</td><td>= false</td></tr><tr><td>S-TAB(Fnatom)</td><td>= H-TAB(Fnatom)</td></tr><tr><td>H-TAB(Forme)</td><td>= indef</td></tr></table>

34 <Fnatom> = (GETP <Forme> (QUOTE Ident))

<table><tr><td>CEVAL(Fnatom)</td><td>= CEVAL(Forme)<br>S-LAB(Forme) : PUSHG<sub>IDENT</sub> ;</td></tr><tr><td>H-LAB(Forme)</td><td>= H-LAB(Fnatom)</td></tr><tr><td>S-LAB(Fnatom)</td><td>= S-LAB(Forme) + 1</td></tr><tr><td>BPROG(Forme)</td><td>= false</td></tr><tr><td>GOFORM(Fnatom)</td><td>= false</td></tr><tr><td>BCOND(Forme)</td><td>= false</td></tr><tr><td>S-TAB(Fnatom)</td><td>= H-TAB(Fnatom)</td></tr><tr><td>H-TAB(Forme)</td><td>= indef.</td></tr></table>
35 <Fnatom> = (PUSHL1 <Forme> <Forme>)
CEVAL(Fnatom) = CEVAL(Forme)
               CEVAL(Forme')
               S-LAB(Forme') : PUSHLT;
H-LAB(Forme)   = H-LAB(Fnatom)
H-LAB(Forme')  = S-LAB(Forme)
S-LAB(Fnatom)   = S-LAB(Forme') + 1
BPROG(Forme)    = false
BPROG(Forme')   = false
GOFORM(Fnatom)   = false
BCOND(Forme)    = false
BCOND(Forme')   = false
S-TAB(Fnatom)    = H-TAB(Fnatom)
H-TAB(Forme)    = indef.
H-TAB(Forme')   = indef.

36 <Fnatom> = (POPL1 <Forme>)
CEVAL(Fnatom) = CEVAL(Forme)
               H-LAB(Forme) : POPLT;
reste identique à 34.

37 <Fnatom> = (NUMBERP<Forme>)
CEVAL(Fnatom) = CEVAL(Forme)
               S-LAB(Forme) : NUM;
reste identique à 33

38 <Fnatom> = (ZEROP<Forme>)
identique à avec S-LAB(Forme) : RZ;

39 <Fnatom> = (DIFFERENCE<Forme><Forme>)
CEVAL(Fnatom) = CEVAL(Forme')
               CEVAL(Forme)
               S-LAB(Forme) : DIF;
               S-LAB(Forme) + 1 : POP^1;
reste identique à 35.
40 <Fnatom> = (<Fsubr><Listarg>)
CEVAL(Fnatom) = CEVAL(Listarg)
S-LAB(Listarg) : LINK TEXT(Fsubr)*^NB(Listarg)
S-LAB(Listarg) + 1 : POP^NB(Listarg) ;
H-LAB(Listarg) = H-LAB(Fnatom)
S-LAB(Fnatom) = S-LAB(Listarg) + 2
GOFORM(Fnatom) = false

41 <Fnatom> = (<Fnasubr><Listarg>)
CEVAL(Fnatom) = CEVAL(Listarg)
CEVAL(Fnasubr)
H-LAB(Fnasubr) = S-LAB(Listarg)
H-LAB(Listarg) = H-LAB(Fnatom)
S-LAB(Fnatom) = S-LAB(Fnasubr)
GOFORM(Fnatom) = false

42 <Fnatom> = (<Ffsubr><Listexpr>)
id. à 40 avec "Listexpr" au lieu de "Listarg".

43 <Fnatom> = (<Fnafsubr><Listexpr>)
id. à 41 avec "Listexpr" au lieu de "Listarg".

44 et 45 : sans attribut.

46 <Fnasubr> = (LAMBDA(<Listvar>)<Forme>)
CEVAL(Fnasubr) = LBOUND(Listvar)
CEVAL(Forme)
LAB1(Listvar) = H-LAB(Fnasubr)
LAB2(Listvar) = S-LAB(Forme) + NB(Listvar) - 1
LAB3(Listvar) = indef.
S-LAB(Fnasubr) = S-LAB(Forme) + NB(Listvar)
H-LAB(Forme) = H-LAB(Fnasubr) + NB(Listvar)
BPROG(Forme) = false
BCOND(Forme) = false
LABTAB(Forme) = indef.
H-TAB(Forme) = indef.

<footnote>* simplification de la description par attribut où TEXT est hérité du non-terminal <Fsubr>.</footnote>
47 <Fnafsubr> = (FLAMBDA(<Listvar>)/<Forme>)
id. à 46

48 <Listvar> = Ident<Listvar>
LBOUND(Listvar) = LBOUND(Listvar')
LAB1(Listvar) : PUSHL'TEXT(Ident)\NB(Listvar');
LAB2(Listvar) : POPL'TEXT(Ident) ;
LAB1(Listvar') = LAB1(Listvar) + 1
LAB2(Listvar') = LAB2(Listvar) - 1
NB(Listvar) = NB(Listvar') + 1
PBOUND(Listvar) = PBOUND(Listvar')
LAB3(Listvar) : PUSHQ'nil ;
LAB3(Listvar)+1 : PUSHL'TEXT(Ident)NB(Listvar');
LAB2(Listvar) : POPL'TEXT(Ident) ;
LAB3(Listvar') = LAB3(Listvar) + 2

49 <Listvar> = empty
LBOUND(Listvar) = vide
PBOUND(Listvar) = vide
NB(Listvar) = 0

50 <Listcond> = (<Forme><Forme>)/<Listcond>
CEVAL(Listcond) =
CEVAL(Forme)
if BPROG(Listcond) and GOFORM(Forme')
then S-LAB(Forme) : BRN\S-LAB(Forme') ;
S-LAB(Forme) + 1 : POP ;
CEVAL(Forme')
S-LAB(Forme') : POP ;
else S-LAB(Forme) : BRN\S-LAB(Forme') + 2 ;
CEVAL(Forme')
S-LAB(Forme') : POP\1 ;
S-LAB(Forme') + 1 : BR\OUTC(Listcond) ;
S-LAB(Forme') + 2 : POP ;
fi
CEVAL(Listcond')
H-LAB(Forme) = H-LAB(Listcond)
H-LAB(Forme') =
if BPROG(Listcond) and GOFORM(Forme')
then S-LAB(Forme) + 2
else S-LAB(Forme) + 1
fi

H-LAB(Listcond) =
if BPROG(Listcond) and GOFORM(Forme')
then S-LAB(Forme') + 1
else S-LAB(Forme') + 3
fi

S-LAB(Listcond) = S-LAB(Listcond')

BPROG(Forme) = false

BPROG(Forme') = BPROG(Listcond)

BPROG(Listcond') = BPROG(Listcond)

BCOND(Forme) = true

BCOND(Forme') = true

LABTAB(Forme') = LABTAB(Listcond)

LABTAB(Listcond') = LABTAB(Listcond)

H-TAB(Forme') = indef.

H-TAB(Forme) = indef.

51 <Listcond> = <Forme><Forme>

CEVAL(Listcond) =

CEVAL(Forme)

if BPROG(Listcond) and GOFORM(Forme')

then S-LAB(Forme) : BRN^OUTC(Listcond) ; co résultat = 'nil co
S-LAB(Forme) + 1 : POP ;
CEVAL(Forme')

else S-LAB(Forme) : BRN^OUTC(Listcond) ;
CEVAL(Forme')
S-LAB(Forme') : POP^1 ;

fi

H-LAB(Forme) = H-LAB(Listcond)

H-LAB(Forme') =

if BPROG(Listcond) and GOFORM(Forme')

then S-LAB(Forme) + 2

else S-LAB(Forme) + 1

fi
S-LAB(Listcond) =
    if BPROG(Listcond) and GOFORM(Forme')
    then S-LAB(Forme')
    else S-LAB(Forme') + 1
fi

BPROG(Forme) = false

BPROG(Forme') = BPROG(Listcond)

BCOND(Forme) = true

BCOND(Forme') = true

LABTAB(Forme') = LABTAB(Listcond)

H-TAB(Forme) = indef.

H-TAB(Forme') = indef.

52 <Listprog> = <Forme><Listprog>

CEVAL(Listprog) =
    CEVAL(Forme)
    if GOFORM(Forme) = false
    then S-LAB(Forme) : POP ;
    fi

co si on atteint cette instruction, la forme a donné un résultat qu'il
faut dépiler co

H-LAB(Forme) = H-LAB(Listprog)

H-LAB(Listprog') =
    if GOFORM(Forme) = false
    then S-LAB(Forme) + 1
    else S-LAB(Forme)
fi

S-LAB(Listprog) = S-LAB(Listprog')

BPROG(Forme) = true

BCOND(Forme) = false

LABTAB(Forme) = LABTAB(Listprog)

LABTAB(Listprog') = LABTAB(Listprog)

H-TAB(Forme) = H-TAB(Listprog)

H-TAB(Listprog') = S-TAB(Forme)

S-TAB(Listprog) = S-TAB(Listprog')

OUTP(Listprog') = OUTP(Listprog)

OUTP(Forme) = OUTP(Listprog)
53 <Listprog> = <Forme>

<table><tr><td>CEVAL(Listprog)</td><td>= CEVAL(Forme)</td></tr><tr><td>co si la dernière forme n'est pas un go ou un return, on admet que c'est un return implicite co</td><td></td></tr><tr><td>H-LAB(Forme)</td><td>= H-LAB(Listprog)</td></tr><tr><td>S-LAB(Listprog)</td><td>= S-LAB(Forme)</td></tr><tr><td>BPROG(Forme)</td><td>= true</td></tr><tr><td>BCOND(Forme)</td><td>= false</td></tr><tr><td>LABTAB(Forme)</td><td>= LABTAB(Listprog)</td></tr><tr><td>H-TAB(Forme)</td><td>= H-TAB(Listprog)</td></tr><tr><td>S-TAB(Listprog)</td><td>= S-TAB(Forme)</td></tr><tr><td>OUTP(Forme)</td><td>= OUTP(Listprog)</td></tr></table>

54 <Listor> = <Forme><Listor>

<table><tr><td>CEVAL(Listor)</td><td>= CEVAL(Forme)<br>S-LAB(Forme) : NRN ;<br>S-LAB(Forme) + 1 : BRT OUTO(Listor) ;<br>S-LAB(Forme) + 2 : POP ;<br>CEVAL(Listor)</td></tr><tr><td>H-LAB(Forme)</td><td>= H-LAB(Listor)</td></tr><tr><td>H-LAB(Listor')</td><td>= S-LAB(Forme) + 3</td></tr><tr><td>S-LAB(Listor)</td><td>= S-LAB(Listor')</td></tr><tr><td>BPROG(Forme)</td><td>= false</td></tr><tr><td>BCOND(Forme)</td><td>= false</td></tr><tr><td>LABTAB(Forme)</td><td>= indef</td></tr><tr><td>H-TAB(Forme)</td><td>= indef</td></tr><tr><td>OUTO(Listor')</td><td>= OUTO(Listor)</td></tr></table>

55 <Listor> = <Forme>

<table><tr><td>CEVAL(Listor)</td><td>= CEVAL(Forme)<br>S-LAB(Forme) : NRN ;</td></tr><tr><td>H-LAB(Forme)</td><td>= H-LAB(Listor)</td></tr><tr><td>S-LAB(Listor)</td><td>= S-LAB(Forme) + 1</td></tr><tr><td>BPROG(Forme)</td><td>= false</td></tr><tr><td>BCOND(Forme)</td><td>= false</td></tr><tr><td>LABTAB(Forme)</td><td>= indef</td></tr><tr><td>H-TAB(Forme)</td><td>= indef</td></tr></table>
56 `<Listand>` = `<Forme><Listand>`

CEVAL(Listand) = CEVAL(Forme)
S-LAB(Forme) : NRN ;
S-LAB(Forme) + 1 : BRN OUTA(Listand) ;
S-LAB(Forme) + 2 : POP ;
CEVAL(Listand)

reste identique à 54 en changeant Listor en Listand et OUTO en OUTA.

57 `<Listand>` = `<Forme>`
identique à 55 en remplaçant Listor par Listand

58 `<Listlist>` = `<Forme><Listlist>`

CEVAL(Listlist) = CEVAL(Forme)
CEVAL(Listlist')
S-LAB(Listlist') : CONS ;
S-LAB(Listlist') + 1 : POP 1 ;

H-LAB(Forme) = H-LAB(Listlist)
H-LAB(Listlist') = S-LAB(Forme)
S-LAB(Listlist) = S-LAB(Listlist') + 2
BPROG(Forme) = false
BCOND(Forme) = false
LABTAB(Forme) = indef
H-TAB(Forme) = indef

59 `<Listlist>` = `<Forme>`

CEVAL(Listlist) = CEVAL(Forme)
S-LAB(Forme) : PUSHQ'nil ;
S-LAB(Forme) + 1 : CONS ;
S-LAB(Forme) + 2 : POP 1 ;

H-LAB(Forme) = H-LAB(Listlist)
S-LAB(Listlist) = S-LAB(Forme) + 3
BPROG(Forme) = false
BCOND(Forme) = false
LABTAB(Forme) = indef
H-TAB(Forme) = indef
60 `<Listtimes> = <Listtimes><Forme>`

<table><tr><td>CEVAL(Listtimes)</td><td>= CEVAL(Listtimes')<br/>CEVAL(Forme)<br/>S-LAB(Forme) : MULT;<br/>S-LAB(Forme) + 1 : POP 1;</td></tr><tr><td>H-LAB(Listtimes')</td><td>= H-LAB(Listtimes)</td></tr><tr><td>H-LAB(Forme)</td><td>= S-LAB(Listtimes')</td></tr><tr><td>S-LAB(Listtimes)</td><td>= S-LAB(Forme) + 2</td></tr><tr><td>BPROG(Forme)</td><td>= false</td></tr><tr><td>BCOND(Forme)</td><td>= false</td></tr><tr><td>LABTAB(Forme)</td><td>= indef.</td></tr><tr><td>H-TAB(Forme)</td><td>= indef.</td></tr></table>

61 `<Listtimes> = <Forme><Forme>`

<table><tr><td>id. à 60 en remplaçant "listtimes" par "forme" et "forme" par "forme""</td></tr><tr><td>et en ajoutant :</td></tr><tr><td>BPROG(Forme)</td><td>= false</td></tr><tr><td>BCOND(Forme)</td><td>= false</td></tr><tr><td>LABTAB(Forme)</td><td>= indef</td></tr><tr><td>H-TAB(Forme)</td><td>= indef</td></tr></table>

62 `<Listplus> = <Listplus><Forme>`

id. 60 en remplaçant MULT par ADD

63 `<Listplus> = <Forme><Forme>`

id. 61 en remplaçant MULT par ADD

64 `<Listarg> = <Forme><Listarg>`

<table><tr><td>CEVAL(Listarg)</td><td>= CEVAL(Forme)<br/>CEVAL(Listarg')</td></tr><tr><td>H-LAB(Forme)</td><td>= H-LAB(Listarg)</td></tr><tr><td>H-LAB(Listarg')</td><td>= S-LAB(Forme)</td></tr><tr><td>S-LAB(Listarg)</td><td>= S-LAB(Listarg')</td></tr><tr><td>NB(Listarg)</td><td>= NB(Listarg') + 1</td></tr><tr><td>BPROG(Forme)</td><td>= false</td></tr><tr><td>BCOND(Forme)</td><td>= false</td></tr><tr><td>LABTAB(Forme)</td><td>= indef.</td></tr><tr><td>H-TAB(Forme)</td><td>= indef.</td></tr></table>
65 `<Listarg>` = empty

CEVAL(Listarg) = vide

S-LAB(Listarg) = H-LAB(Listarg)

NB(Listarg) = 0

66 `<Listexpr>` = S-expr `<Listexpr'>`)

CEVAL(Listexpr) = H-LAB(Listexpr) : PUSHQ'TEXT(S-expr) ;
CEVAL(Listexpr')

H-LAB(Listexpr') = H-LAB(Listexpr) + 1

S-LAB(Listexpr) = S-LAB(Listexpr')

NB(Listexpr) = NB(Listexpr') + 1

67 `<Listexpr>` = empty

id. avec "Listexpr" au lieu de "Listarg".
## D - Introduction des optimisations

Nous indiquons ici la traduction de la règle 50 en incluant les deux optimisations décrites à la section 2, sections 3.2 et 3.3, transformation récursif, iteratif et élimination des "POP n" redondants.

Règle 50 : `<Listcond> = (<Forme> <Forme>’) <Listcond>`

```
CEVAL(Listcond) = CEVAL(Forme)

    if BPROG(Listcond) and GOFORM(Forme') or NBRECUR(Forme') = 1
    then S-LAB(Forme) : BRN S-LAB(Forme') ;
        S-LAB(Forme) + 1 : POP ;
        CEVAL(Forme')
        S-LAB(Forme') : POP ;
    else S-LAB(Forme) : BRN S-LAB(Forme')+if S-BPOPID(Forme') =
                                                false
                                                then 2
                                                else 1
                                                fi ;

        CEVAL(Forme')
        if S-BPOPID(Forme') = false
        then S-LAB(Forme') : POP 1 ;
            S-LAB(Forme') + 1 : BR OUTC(Listcond) ;
            S-LAB(Forme') + 2 : POP ;
        else S-LAB(Forme') : BR OUTC(Listcond) ;
            S-LAB(Forme') + 1 : POP ;
        fi
        fi
        CEVAL(Listcond')

RECUR(Forme) = false
RECUR(Forme') = RECUR(Listcond)
RECUR(Listcond') = RECUR(Listcond)

NAME transmis (hérités) aux trois non terminaux
NBI idem.
```
NBRECUR(Listcond) = if RECUR(Listcond)
then NBRECUR(Forme') + NBRECUR(Listcond')
else 0
fi

BEXTRA transmis (hérité) aux trois non terminaux

LABEXT idem

LABOP(Listcond) = if NBRECUR(Forme') = 0
then LABOP(Listcond')
else LABOP(Forme')
fi

H-BPOPID(Forme) = H-BPOPID(Listcond)

H-BPOPID(Forme') = false

H-BPOPID(Listcond) = false _co_ y compris si NBRECUR(Forme') = 1 _co_

S-BPOPID(Listcond) = S-BPOPID(Listcond')

H-APOPID(Listcond') = H-APOPID(Listcond)

H-APOPID(Forme') = if BPROG(Listcond) and GOFORM(Forme') or NBRECUR(Forme') = 1
then 0
else 1
fi

H-APOPID(Forme) = 0

S-APOPID(Listcond) = S-APOPID(Forme)

H-LAB(Forme) = H-LAB(Listcond)

H-LAB(Forme') = if BPROG(Listcond) and GOFORM(Forme') or NBRECUR(Forme') = 1
then S-LAB(Forme') + 2
else S-LAB(Forme') + 1
fi

_co_ si NBRECUR(Forme') = 1 c'est le 2ème cas également _co_

S-LAB(Listcond') = if BPROG(Listcond) and GOFORM(Forme') or NBRECUR(Forme') = 1
then S-LAB(Forme') + 1
else S-LAB(Forme') + 2 + if S-BPOPID(Forme') = false
then 1
else 0
fi
<table><tr><td>S-LAB(Listcond)</td><td>= S-LAB(Listcond')</td></tr><tr><td>bPROG(Forme)</td><td>= false</td></tr><tr><td>BPROG(Forme')</td><td>= BPROG(Listcond)</td></tr><tr><td>BPROG(Listcond')</td><td>= BPROG(Listcond)</td></tr><tr><td>BCOND(Forme)</td><td>= true</td></tr><tr><td>BCOND(Forme')</td><td>= true</td></tr><tr><td>LABTAB(Forme')</td><td>= LABTAB(Listcond)</td></tr><tr><td>LABTAB(Listcond')</td><td>= LABTAB(Listcond)</td></tr><tr><td>H-TAB(Forme')</td><td>= indef</td></tr><tr><td>H-TAB(Forme)</td><td>= indef</td></tr></table>

Soit 38 définitions d'attributs.