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

laboria

Institut de Recherche
d'Informatique
et d'Automatique

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

laboratoire de recherche
en informatique
et automatique

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

# FORLISP 1 :
UN LISP HYPERPORTABLE

Marc BERTHOD

Rapport de Recherche N° 174

Juin 1976
# FORLISP 1 : UN LISP HYPERPORTABLE

## M. Berthod

### Résumé :

Le but de cet article est la description d'un interprêteur Lisp, écrit en Fortran II.

Les caractéristiques essentielles de cet interprêteur sont :

- sa transportabilité, les seules modifications à faire pour le changer de machine concernant les entrées-sorties et la taille des tableaux.

- l'emploi généralisé de λ-expressions pour définir les fonctions de base récursives, ce qui permet de simplifier l'interprêteur.

- l'allocation dynamique de tableaux.

L'intérêt primordial de cette transportabilité est l'assurance qu'elle fournit de disposer sur différentes machines d'interprêteurs Lisp totalement compatibles.

### Abstract :

I want to describe here a Lisp-interpreter, written in Fortran II.

The main characteristics of this interpreter are the following :

- high portability : the only changes to be done between two different computers regard the input-output instructions, and the sizes of arrays.

- large use of λ-expressions to define recursive base-functions, which much shortens the interpreter.

- dynamic allocation of arrays.

The great interest that relies in that portability is that it provides, on different computers, totally compatible Lisp systems.
# 1. - Introduction

A l'heure actuelle, LISP est probablement le langage le plus utilisé en Intelligence Artificielle.

Depuis sa création, en 1960, par John Mac Carthy, son importance théorique est restée considérable, et son importance pratique n'a cessé de croître.

Sur le plan théorique, il coïncide avec l'utilisation du λ-calcul de Church [1] , comme modélisation du traitement de l'information sur un ordinateur.

Sur le plan pratique, on peut trouver trois raisons de l'importance grandissante de LISP :

1) La réalisation pratique du modèle fourni par le λ-calcul est très largement employée dans les problèmes de calcul formel, et de démonstration de théorèmes, qui sont des domaines de pointe de l'Intelligence Artificielle.

2) L'implémentation élégante de la récursion, et l'unification des données et du programme permettent une implémentation aisée :

- du pattern matching

- de la génération automatique de procédures.

3) L'implémentation de structures de données complexes est rendue possible par l'utilisation de structures de listes très générales.

D'autres langages de programmation présentent certains de ces avantages de LISP (Pop2[2], Sail [3] ) ; mais aucun n'est d'une aussi grande généralité, satisfaisant à la fois les besoins du théoricien et du praticien.
De ce fait, en Lisp, la structure interne des données et les fonctions de manipulation de ces données sont très générales : pour cette raison il a servi de base pour la réalisation de langages de très haut niveau, qui répondent à des besoins plus spécifiques de l'Intelligence Artificielle, tels que Micro PLANNER, [4] , CONNIVER [5] , QA4 [6] .

## 1.1. - *Les systèmes LISP existants.*

La facilité de modifier le langage, qui a permis de créer ces extensions, devient aussi un obstacle à sa portabilité. Comme il a été utilisé, jusque là, par de petites communautés de chercheurs, le besoin de créer des normes ne s'est pas fait sentir : la tendance a été, au contraire, de créer les systèmes les plus complets possibles (Interlisp [7] , Q lisp [8] , Maclisp [9]).

Seul le Lisp 1.5 [10] est parfois considéré comme une norme, pour ce qui concerne les possibilités du langage. Dans la syntaxe des réalisations ultérieures, dans le jeu des fonctions de base, et même dans leur orthographe, on trouve des différences.

Ces détails d'implémentation expliquent en partie la difficulté de disposer en France d'une bonne version d'un langage d'Intelligence Artificielle. Hormis une ancienne version d'un interprêteur LISP, distribué par l'université d'Uppsala , on ne dispose à notre connaissance que de deux systèmes LISP.

Mr. LUX, [11], a réalisé, en langage assembleur un interprêteur et un compilateur pour l'IBM 360/67 sous CP/CMS de l'université de Grenoble.

Mr. GREUSSEY, [12] a réalisé, également en langage assembleur, un interprêteur et un compilateur, sur une petite machine (Télémécanique T 1600).

Cette dernière réalisation nous semble particulièrement intéressante car elle correspond à une volonté de simplification de syntaxe, en vue d'un système facilement accessible à des étudiants.

Si elles offrent des avantages de rapidité d'exécution et de faible encombrement en mémoire, parce qu'elle sont écrites en assembleur, elles renoncent de ce fait, à la portabilité.
## 1.2. - Options fondamentales

L'écriture du système FORLISP, que nous présentons ici, a été motivée par l'utilisation croissante des techniques d'Intelligence Artificielle dans les projets de Reconnaissance des Formes. Il est également destiné à l'enseignement, ce qui nous a conduit à choisir comme objectifs :

- une syntaxe particulièrement claire

- un choix réduit des fonctions de base

- la portabilité complète du système

- l'utilisation éventuelle sur petites machines.

Pour réaliser ces quatre objectifs, nous avons adopté les caractéristiques suivantes, pour le langage et l'implémentation.

1) Le Lisp normal a deux modes d'écriture des formes :

Si F est la fonction et $A_1... A_n$ ses arguments, l'évaluation de cette fonction appliquée à ses arguments se fait en fournissant ($F A_1...A_n$), à l'évaluateur.

Par contre, à un niveau supérieur de récursion, c'est-à-dire si les $A_i$ sont eux-mêmes des formes à évaluer, ils s'écrivent alors ($F A_1... A_n$).

L'écriture particulière des formes à évaluer au niveau zéro de récursion est liée au mode de fonctionnement dit "mode EVAL QUOTÉ" de l'interprêteur.

Nous avons préféré le mode dit "mode EVAL", dans lequel toute forme à évaluer s'écrit toujours ($F A_1...A_n$).

2) L'opération de λ-conversion est en général exécutée à l'aide d'une "A liste", ce qui permet facilement le passage de contextes, mais coûte extrêmement cher en temps.

Nous avons choisi une méthode plus directe, par laquelle les variables liées se voient effectivement affecter la valeur de leurs arguments, leur valeur précédente leur étant restituée en fin d'évaluation.
De ce fait, les fonctions de base **FUNCTIØN** (et **FUNARG**)
n'existent plus : le passage d'un argument fonctionnel se fait comme
celui d'un argument normal.

3) Il est rare qu'une fonction ait une utilisation autre que fonctionnelle ; pour cette raison, nous avons supprimé les indicateurs EXPR et FEXPR : la définition de la fonction est sa valeur. Une fonction est donc reconnue à ce que sa valeur est une liste commençant par $\lambda$, $F\lambda$, $N\lambda$.

Ces choix précédents se justifient également par le fait que
nous n'avons besoin que d'un interprêteur. Un compilateur apporte seulement
une amélioration des temps d'exécution, ce qui n'est pas essentiel dans
les applications qu'on peut réaliser sur une petite machine.

Que ce système fonctionne sur petite ou grosse machine, seul le
Fortran permet actuellement une portabilité complète. Seul même le Fortran II
est réellement disponible sur à peu près tous les ordinateurs couramment
rencontrés dans l'enseignement.

Enfin l'utilisation sur un gros calculateur permet de disposer
d'une grande place mémoire, et d'envisager des extensions syntaxiques
et sémantiques du langage.

La disponibilité, sur différentes machines, de systèmes LISP aux
spécifications tant syntaxiques que sémantiques rigoureusement identiques,
répond d'ores et déjà à un besoin. Elle devrait en outre favoriser l'utilisation de LISP en France.

## 2. - La structure du système

### 2.1. - Le langage

L'élément de base du langage est la liste. Une liste est la
représentation d'un ensemble ordonné d'éléments, pouvant eux-mêmes être
des listes :

Plus précisément, le langage utilisable peut être engendré par
la grammaire suivante : ($S$, $V_T$, $V_N$, $\Phi$)

$S$ ; symbole initial

$V_T$ : vocabulaire terminal : (,), A, NIL A désigne un atome
NIL est un atome particulier

$V_N$ : vocabulaire non terminal $L, L1$

I : ensemble des productions suivantes :

$S :: = L$
$L :: = (L1)| NIL$
$L1:: = A1|AL1$
## Remarque

Sans entrer ici dans le détail de l'évaluation, rappelons que FORLISP1 travaille en mode "EVAL", par opposition au mode "EVAL QUOTE", généralement employé : l'interprêteur évalue donc une forme et non un doublet d'éléments : Fonction (arguments). Ceci permet l'unification de la syntaxe d'une expression.

### 2.1.3. - Description de $V_N$

F symbolise une forme.

Une forme non atomique (règle 2.3.) est en fait une expression polonaise préfixée.

FONC symbolise donc la fonction.

LARG est la liste de ses arguments.

ARG est un argument.

L est une liste.

A est un atome de type littéral ou une constante.

EXPR, et FEXPR, désignent des fonctions construites par l'utilisateur, sous forme d'une λ-expression, au sens de Church.

LVAR est une liste éventuellement vide dont les éléments sont des littéraux.

### 2.2. - Représentation des données

#### 2.2.1. - Les paires

Le système est implanté dans un espace mémoire banalisé, appelé "espace des paires", dont l'unité, ou élément adressable, est une paire, constituée de deux mots-mémoire.

Le premier mot d'une paire est appelé le"car", le deuxième mot le"cdr".

Il existe quatre types différents de paires, ayant trois structures différentes.

Atome littéral

<table><tr><td>car</td><td>cdr</td></tr><tr><td>A1</td><td>Pliste LI</td></tr></table>

A1 est la valeur de l'atome, c'est-à-dire l'adresse de son contenu.

Pliste est l'adresse de la Pliste de l'atome.

LI indique au système que c'est un atome.

La Pliste d'un atome est une liste dont le 1er élément est une constante. La valeur de cette constante est l'adresse (dans un tableau) de la chaîne de caractères du nom externe du littéral.
<table><thead><tr><th></th><th>car</th><th>cdr</th></tr></thead><tbody><tr><td>- Constante</td><td>V</td><td>C</td></tr></tbody></table>

V est la valeur numérique de la constante.

C indique au système que c'est une constante.

Remarque : par analogie avec un atome, la valeur (non numérique) d'une constante, ou adresse de son contenu est prise égale à la constante elle-même.

<table><thead><tr><th></th><th>car</th><th>cdr</th></tr></thead><tbody><tr><td>- Doublet</td><td>A<sub>1</sub></td><td>A2 D</td></tr></tbody></table>

Un doublet est en fait un couple d'adresses ou de valeurs, $A_1$ et $A_2$.

D indique un système que c'est un doublet.

<table><thead><tr><th></th><th>car</th><th>cdr</th></tr></thead><tbody><tr><td>- Tableau</td><td>L</td><td>T</td></tr></tbody></table>

Un tableau est un ensemble de paires physiquement contigües en mémoire, encadrées par deux paires de type "T".

Le "car" d'une telle paire contient la longueur utilisable du tableau.

### 2.2.2. - *Définition des listes et notations*

Une liste est un ensemble ordonné d'éléments, qui peuvent eux-mêmes être des listes. Outre la notation déjà vue, il en existe une autre autorisée, dite : notation *pointée*, correspondant à la grammaire suivante :

S : symbole initial.

$V_T$ : (,,), A, NIL (même conventions qu'auparavant).

$V_N$ : L.

$\Phi$ : S ::= L

L ::= A (A.L) NIL

### 2.2.3. - *Représentation d'une liste*

Sous la forme pointée, la représentation interne d'une liste à l'aide des divers types de paires est immédiate ; une liste est :

- soit l'atome NIL (liste vide)

- soit un doublet dont le car est l'élément situé à gauche du point, et le cdr l'élément situé à droite du point.
C'est-à-dire qu'une liste non vide est un doublet de valeur
le 1er élément, et la sous liste formée en extrayant ce 1er élément
de la liste.

Remarque :

La notation pointée est autorisée à tout moment dans l'écriture
d'une forme.

2.3. - *Définition d'une fonction*

Il existe deux catégories de fonctions. Les fonctions du
système (de type Subr ou Fsubr) sont réalisées par des modules
du système, écrits en Fortran.

Les fonctions définies par l'utilisateur sont interprêtées par
le système lors de l'évaluation d'une forme. Nous leur donnerons le
terme général de λ-expressions: elles correspondent aux symboles non-
terminaux EXPR, FEXPR, NEXPR.

Une λ-expression est donc de la forme (LAMBDA LVAR F),
FLAMBDA LVAR F) ou (NLAMBDA LVAR F), LVAR est une liste d'atomes
littéraux, qui sont les variables liées.

2.3.1. - *Application d'une fonction à ses arguments*

Lors de l'évaluation d'une forme dont la fonction est une
λ-expression, chacun des atomes de LVAR prend pour valeur l'argument
(évalué d'abord dans le cas de EXPR) de rang correspondant dans la
liste d'arguments.

Dans le cas de FEXPR (ou NLAMBDA), le 1er atome prend pour
valeur la liste formée de tous les arguments, non évalués.

Les valeurs antérieures de ces atomes sont sauvées dans une pile.
Nous noterons cette opération : BIND.

L'évaluation de la forme est alors celle de F.

Les valeurs antérieures des atomes de LVAR leur sont resti-
tuées, par une opération notée UNBIND.
### 2.3.2. - Définition de BIND

BIND peut être défini comme une fonction de deux arguments :
LVAR, LARG.

Sa définition, par une λ-expression, serait la suivante, en
appelant STACK la fonction mettant la valeur d'une forme un sommet
d'une pile P.

(LAMBDA (LVAR LARG)
(COND
((NULL LVAR)
NIL)
(TRUE
(PROG)
(STACK (CAR (CAR LVAR))
(SET (CAR LVAR) (CAR LARG))
(BIND (CDR LVAR) (CDR LARG))))))

En particulier, si LARG contient moins d'éléments que LVAR,
les atomes de LVAR qui "n'ont pas d'arguments correspondant", prennent
pour valeur NIL.

### 2.3.3. - Définition de UNBIND

UNBIND peut être défini comme une fonction d'un argument LVAR.
En appelant UNSTACK la fonction qui ramène pour valeur le sommet de la
pile P et dépile cette valeur.

(LAMBDA (LVAR)
(COND
((NULL LVAR)
NIL)
(TRUE
(PROG)
(SET (CAR LVAR) (UNSTACK))
(UNBIND (CDR LVAR)))))

Nous noterons APPLY la fonction qui, à une λ-expression et à ses
arguments, associe l'évaluation décrite ci-dessus.

La définition de APPLY par une λ-expression serait :

(LAMBDA (A1 A2)
(PROG)
(SETO A1 (CDR A1))
(BIND (CAR A1) A2)
(SETO A2 (EVAL (CONS PROG
(CDR A1)))))
(UNBIND (CAR A1))
A2))
**Remarque :**

APPLY n'est utilisé que pour décrire commodément le mécanisme de l'évaluation : ce n'est pas une fonction de FORLISP1.

## 2.4. - Evaluation d'une forme

Le coeur de l'interprêteur est l'évaluateur, réalisé par la fonction (de type SUBR) EVAL.

L'évaluation d'une forme est un élément (repéré par son adresse) de l'espace des paires : nous noterons $E(F)$ le résultat de l'évaluation d'une forme.

Le principe de l'évaluation est le suivant :

1) Si $F$ est un atome, $E(F)$ est la valeur de cet atome.

En particulier la valeur d'une constante est cette constante.

2) Si $F$ n'est pas un atome, $F$ est donc du type ($F$ONC LARG).

Alors, si FONC n'est pas une fonction, il est remplacé par $E(FONC)$.

FONC doit alors être une fonction, de type SUBR, FSUBR, EXPR, FEXPR, NEXPR.

3) Si FONC est de type SUBR, ou EXPR, les arguments doivent être évalués avant d'être passés à la fonction.

4) Si FONC est de type SUBR ou FSUBR, le module système correspondant est exécuté, sinon, on évalue (APPLY FONC LARG).

La définition, en FORLISP1 de la fonction EVAL, serait la suivante :

- SUBRP est un prédicat valant TRUE si $A1$ est une fonction de type SUBR, NIL sinon.

- FSUBP est un prédicat valant TRUE si $A1$ est une fonction de type SUBRP, NIL sinon.

- ATOM est un prédicat :

Valeur TRUE si $F$ est un littéral ou une constante
NIL sinon.
- ARRAYP est un prédicat :
  Valeur TRUE si F est un tableau
  NIL sinon.

- MATCH : (serait de type Subr)
  exécute le module système d'adresse A1, la liste des arguments
  étant à l'adresse A2.

- EVLIS : (serait de type Subr), a pour valeur une liste dont les éléments sont les évaluations des éléments de A2 (qui doit être une liste).
  Les autres fonctions sont des fonctions du système, de type Subr ou Fsubr.

**Remarque** : l'absence de la fonction APPLY est la principale différence avec le LISP classique, elle est liée à l'évaluation systématique de la forme "en position de fonction" dans une forme et à la prise en compte des λ-expressions par EVAL.

(LAMBDA (F)
(PROG (A1 A2)
(COND
  ((ATCH F)
    (RETURN F))
  ((ARRAYP F)
    (RETURN F)))
(SETG A1 (CAR F))
(SETG A2 (CDR F))
(WHILE
  (NULL (OH
    (SUBRP A1)
    (FSUBRP A1)
    (EL (CAR A1) LAMBDA)
    (EQ (CAR A1) FLAMBD)
    (EL (CAR A1) NLAMBD)))
(SETG A1 (EVAL A1)))
(COND
  ((LR
    (SUBRP A1)
    (EL (CAR A1) LAMBDA))
    (SETG A2 (EVLIS A2)))
  ((H) (CAR A1) FLAMBD)
    (SETG A2 (LIST
      A2))))
(COND
  ((LR
    (SUBRP A1)
    (FSUBRP A1))
    (RETURN (MATCH A1 A2)))))
(APPLY A1 A2)))))
3. - *Définition des fonctions du système*

3.1. - *Les fonctions de base*

Là encore, chaque fois que cela sera possible sans ambiguïté,
les fonctions seront définies par des λ-expressions.

Notons déjà que l'évaluation d'une fonction a, en général,
deux effets :

- elle calcule la valeur, résultat de la fonction ;

- parfois, en outre, elle modifie certains atomes ou certaines
listes déjà existantes : ceci s'appelle "l'effet de bord"
de la fonction.

Notons que dans le cas des *Subr*, le nom de la variable dans la
description de la fonction, désigne la valeur de cette variable.

1) CAR, (Subr), 1 argument ; (CAR X)

- la valeur est le 1er élément de X, si X est une liste,

- la valeur de X si X est un atome.

2) CDR,(Subr),1 argument;(CDR X)

- la valeur est la sous liste de X commençant par le 2ème élément
si X est une liste.

- la valeur est le 2ème élément si X est une paire pointée.

- la valeur est la P-liste, si X est un atome.

3) CONS,(Subr), 2 arguments; (CONS X Y)

la valeur est la paire pointée, (X.Y) qui est créée

Notons que :

(CAR(CONS X Y)) vaut X.

(CDR(CONS X Y)) vaut Y.
4) EQ,(Subr), 2 arguments; (EQ X Y)

- la valeur est TRUE

si : les valeurs de X et Y sont le même atome

ou : les valeurs de X et Y sont la même liste (ou paire pointée)

ou : les valeurs de X et Y sont des constantes de même valeur numérique

elle est NIL dans le cas contraire.

5) ATØM,(Subr), 1 argument; (ATOM X)

- la valeur est TRUE si X est un atome

- la valeur est NIL sinon.

6) QUØTE,(FSubr), 1 argument; (QUØTE X)

- la valeur est X. Comme QUOTE est FSubr, l'emploi de (QUOTE X) comme argument dans un Subr permet d'empêcher l'évaluation de X.

7) SET,(Subr), 2 arguments; (SET X Y)

- la valeur est Y, mais il y a en outre un effet de bord :
  X prend pour valeur Y.

8) SETQ,(FSubr), 2 arguments; (SETQ X Y)

la λ-expression correspondante est :
(NLAMBDA (X Y) (SET X (EVAL Y))).

9) LIST,(Subr), n arguments; (LIST A₁...Aₙ)

- la valeur est la liste (A₁...Aₙ).

10) DE,(FSubr), n arguments; (DE FONC (A₁...Aₙ) F₁ F₂...Fₚ)

équivalent à :

(FLAMB)) (L)

(SET (CAR L) (CONS LAMBDA (CDR L))))
11) DF, (Fsubr), n arguments, analogue à DE, en remplaçant LAMBDA par FLAMBDA.

12) DN, (Fsubr), n arguments, analogue à DE, en remplaçant LAMBDA par NLAMBDA.

Remarque :

Les atomes LAMBDA, FLAMBDA, NLAMBDA ainsi que TRUE et NIL, ont pour valeurs eux-mêmes : nul besoin, donc, de les "QUOTER".

13) NEXTL, (FSubr), 1 argument; (NEXTL X)

X doit avoir pour valeur une liste

- la valeur est le 1er élément de cette liste, mais, en outre, l'effet de bord donné pour valeur à X (CDR X).

La définition en λ-expression serait :

(NLAMBDA (X)
(PROG (A)
(SETG A (CAR (EVAL X))))
(SET X (CDR (EVAL X))))
(RETURNA A)))

14) NUMBP, (Subr), 1 argument; (NUMBP X)

- la valeur est TRUE si X est une constante.

- la valeur est NIL sinon.

15) RPLACD (Subr), 2 arguments; (RPLACD X Y)

- la valeur est X

l'effet de bord modifie X en remplaçant physiquement le "cdr" de X par Y.

La différence avec le CONS est qu'ici aucune paire n'est créée.
16) `NULL,(Subr), 1 argument;(NULL X)`

- la valeur est `TRUE` si X est `NIL`,

- la valeur est `NIL` sinon.

17) `GØ,(FSubr), 1 argument;(GØ X)`

- la valeur est l'atome `%%TRA` (atome système);
  l'effet de bord affecte à `%%TRA` la valeur X
  soit :

(NLAMBD (X)
(SETQ %%%TR X)
(QUOTE %%%TR))

18) `GØTØ (Subr), 1 argument;(GØTØ X)`

analogue à GØ, soit :

(LAMBDA (X)
(SETQ %%%TR X)
(QUOTE %%%TR))

19) `RETURN (Subr), 1 argument;(RETURN X)`

- la valeur est `%%TRA` ;

l'effet de bord donne à `%%TRA` la valeur `%%RET` (atome du système),
et à `%%RET` la valeur X.

(LAMBDA (X)
(LAMBDA (X)
(SETQ %%%TR (QUOTE %%RET))
(SETQ %%%RE X)
(QUOTE %%TR))
Remarque : GØ, GØTØ et RETURN donnent comme valeur le même atome %%TRA.
Ces trois instructions ont pour but de provoquer un débranchement
dans la séquence d'évaluation des formes dans PROG. Cet effet est
également pris en compte par les fonctions WHILE, COND, AND, ØR
PROGN.

L'utilisateur ne doit utiliser ni %%TRA, ni %%RET : il n'est pas
censé les connaître.

20) PROGN, (Fsubr), n arguments; (PROGN A ... An).

Les $A_i$ doivent être des formes, qui sont évaluées en séquence :

- si $E (A_i) = %%TRA$, l'évaluation s'arrête, la valeur est %%TRA

- sinon la valeur est $E (A_n)$

S'il n'y a pas d'arguments, le valeur est NIL.

21) CØND (FSubr), n arguments; (COND $\overline{(C_i A_i A_l P_l)}$)

$\overline{(C_i A_i P_i)}$

$\overline{(C_n A_n P_m)}$

Chaque argument de COND est une liste de formes :

$\overline{(C_i A_i \dots A_i P_i)}$

Les $C_i$ sont évalués en séquence.

Si tous les $E (C_i)$ sont NIL, la valeur est NIL.

Sinon, soit n le premier indice tel que :

$E (C_n) \neq$ NIL, alors la valeur retournée est celle de $(PROGN A_{k_1} \dots A_{k_n P_k})$.

S'il n'y a pas d'argument, la valeur est NIL.

Si $E (C_k)$ est %%TRA, ou $E (A_{k_j})$ est %%TRA, l'évaluation s'arrête
la valeur retournée est %%TRA.
22) WHILE, (Fsubr), n arguments ; (WHILE C A₁ A₂...Aₚ tant que E (C) est NIL, les Aᵢ sont évaluées en séquence. Si E (C) ou E (Aᵢ) est %%TRA, l'évaluation s'arrête; dans tous les cas, la valeur ramenée est celle de la dernière forme évaluée (éventuellement %%TRA).

23) AND,(Fsubr),n arguments ; (AND A₁... Aₙ)
Les Aᵢ sont évalués en séquence,
- si aucun des E (Aᵢ) n'est NIL, la valeur est E (Aₙ);
- sinon, l'évaluation s'arrête au 1er Aᵢ tel que E (Aᵢ) = NIL,
la valeur ramenée étant NIL; si E (Aᵢ) = %%TRA,
la valeur ramenée est %%TRA.

24) ØR (FSubr), n arguments; (ØR A₁...Aₙ)
Les Aᵢ sont évalués en séquence,
- si tous les E (Aᵢ) sont NIL, la valeur est NIL;
- sinon la valeur est le premier E (Aᵢ) qui diffère de NIL.

25) PRØG, (Fsubr), n arguments; (PRØG LVAR A₁ A₂... Aₚ)
LVAR est une liste de littéraux et les Aᵢ sont des formes
PRØG peut être représenté par la λ-expression :

(F) λ. M.

C'est-à-dire que les variables de LVAR, dites variables locales,
sont initialisées à NIL, le corps du programme est évalué, la valeur
résultante étant donnée à X. Les variables locales sont restaurées
avec leur valeur originale, et la valeur ramenée est celle de X.
EVPRØG : L'évaluation du corps de programme se fait en évaluant successive-ment les $A_i$, avec les restrictions suivantes :

- si $A_i$ est un atome, il est considéré comme une étiquette ;

- si $E(A_i)$ est l'atome %%TRA ;

- si la valeur de TRANS est une étiquette, l'évaluation reprend à partir de la forme suivant cette étiquette ;

- si la valeur de %%TRA est %%RET, l'évaluation est arrêtée, la valeur est celle de %%RET ;

- si $A_p$ est évalué et que $E(A_p) \neq TRANS$, la valeur de (EVPRØG) est NIL.

La description en FORLISP₁, de EVPROG, est la suivante :

(LAMBDA (F)
    (PROG(A1 A2)
        (COND
            ((ATOM F)
                (RETURN F))
            ((ARRAYP F)
                (RETURN F)))
            (SETQ A1(CAR F))
            (SETQ A2 (CDR F))
            (WHILE
                (NULL (OR
                    (SUBRP A1)
                    (FSUBRP A1)
                    (EQ (CAR A1) LAMBDA)
                    (EQ (CAR A1) FLAMBD)
                    ((OR
                        (SUBRP A1)
                        (EQ (CAR A1) LAMBDA))
                        (SETQ A2 (EVLIS A2))))
                    ((EQ (CAR A1) FLAMBD)
                        (SETQ A2 (LIST
                            A2)))))
            (COND
                ((OR
                    (SUBRP A1)
                    (FSUBRP A2))
                    (RETURN (MATCH A1 A2))))
            (APPLY A1 A2))))
26) EVAL,(Subr), 1 argument;(EVAL X)
la valeur est E (X).
Comme X a déjà été évalué, EVAL permet de chaîner des évaluations.

27) LT,(Subr), 2 arguments;(LT X Y)
X et Y doivent être des constantes, de valeurs numériques $C_x, C_y$;
la valeur est TRUE si $C_x < C_y$;
la valeur est NIL sinon.

28) GT,(Subr), 2 arguments;(GT X Y)
X et Y doivent être des constantes, de valeurs numériques $C_x, C_y$;
la valeur est TRUE si $C_x > C_y$;
la valeur est NIL sinon.

29) DIFFER,(Subr), 2 arguments;(DIFFER X Y)
X et Y doivent être des constantes $C_x, C_y$;
une constante Z est créée, de valeur numérique $C_x - C_y$;
la valeur retournée est Z.

30) QUØ,(Subr), 2 arguments;(QUØ X Y)
X et Y doivent être des constantes, de valeur numérique $C_x, C_y$;
une constante Z est créée, de valeur numérique $C_x / C_y$;
la valeur retournée est Z.

31) TIMES,(Subr), n arguments;(TIMES $A_1...A_n$)
$A_1...A_n$ doivent être des constantes, de valeur numérique $C_{A1}, C_{A2}, C_{An}$;
une constante Z est créée, de valeur numérique $C_{A1} * C_{A2} * C_{An}$.
32) PLUS, (Subr), n arguments; (PLUS $A_1...A_n$)

$A_1...A_n$, doivent être des constantes, de valeur numérique $C_{A_1}...C_{A_n}$;
une constante Z est créée, de valeur numérique $C_{A_1} + C_{A_2}...+ C_{A_n}$;
la valeur retournée est Z.

33) INITR, (Fsubr), O argument; (INITR)

provoque en lecture, le passage au début de la ligne suivante,
la valeur retournée est NIL.

34) TERPRI, (FSubr), O argument; (TERPRI)

provoque l'impression de la ligne en cours d'écriture, et le passage
en début de la ligne suivante.

35) LECT, (FSubr), O argument; (LECT)

provoque la lecture, sur la ligne de lecture en cours, de la chaîne
de caractères qui s'arrête au prochain caractère séparateur.

Si le $l^{er}$ caractère est séparateur, l'atome dont le nom externe est
constitué de ce caractère, est retourné.

La lecture d'un / n'est pas prise en compte, mais le caractère suivant est alors considéré comme non numérique et non séparateur.

Si le $l^{er}$ caractère est numérique, ou est + ou -, le reste doit être
numérique, une constante est créée dont la valeur numérique est celle
représentée par la chaîne.
Si le 1er caractère n'est pas numérique, le nom externe constitué par cette chaîne est recherché dans la table des noms externes : s'il n'est pas trouvé, un nouveau littéral est créé avec ce nom externe, qui est rajouté à la table.

La valeur de (LECT) est la constante créée, ou le littéral créé ou trouvé.

36) ECR,(Subr), 1 argument;(ECR X)
X doit être un atome ;
provoque l'écriture (sur la ligne d'écriture) d'une chaîne de caractères représentant - le nom externe si X est un littéral ;
- la valeur numérique si X est une constante ;
la valeur retournée est X.

37) READCH,(FSubr), 0 argument; (READCH)
provoque la lecture du caractère suivant sur la ligne,
une constante Z de valeur numérique ce caractère (format $A_1$) est créée.

38) PRINCH,(Subr), 1 argument;(PRINCH X)
X doit être une constante ;
provoque l'écriture sur la ligne courante, de X, en Format $A_1$.
Remarque : L'arrivée en fin de ligne, en lecture comme en écriture,
provoque un passage automatique au début de la ligne suivante.

39) TTAB,(Subr), 1 argument; (TTAB N)
provoque le positionnement en n<sup>ième</sup> colonne sur la ligne courante
d'impression.

40) ERRØR,(Subr), 1 argument;(ERRØR X)
X doit être une constante numérique ;
provoque l'écriture, sur une ligne à part, du libellé "ERREUR UTILISATEUR"
ainsi que la valeur numérique de X.
L'interprêteur repart ensuite au niveau de récursion 0.
41) **REMPAI**, (Fsubr), 0 argument ; (REMPAI)
crée une constante dont la valeur numérique est le nombre de paires
encore disponibles dans la liste libre.

42) **GENSYM**, (Fsubr), 0 argument ; (GENSYM)
crée un littéral interne dont le nom externe, inaccessible en lecture
est de la forme *n*, où n est l'adresse physique du littéral.

43) **ERASE**, (Subr), 1 argument ; (ERASE ZZZ)
où ZZZ est un littéral, supprime le nom externe ZZZ de la table des
noms externes, et transforme ZZZ en un atome interne.

44) ØBLIST, (Fsubr), 0 argument ; (ØBLIST)
crée la liste de tous les littéraux dont les noms se trouvent dans
la table des noms externes excepté %%TRA et retourne cette liste
comme valeur.

45) ERRLEC, (Fsubr), 0 argument ; (ERRLEC)
provoque l'impression, sur une ligne à part, d'un signe en dessous
du caractère courant en lecture, et du message"erreur de la lecture".

46) ESCAPE, (Fsubr), n arguments ; (ESCAPE ETI NØM₁ .. NØMₚ)

Evalue en séquence NØM₁ ... NØMₚ.

Si, dans la portée du ESCAPE, est évalué

ETI E₁... Eₚ

Les Eᵢ sont évalués en séquence, et l'évaluation de (ESCAPE...)
est terminée, ramenant la valeur E (Eᵢ).
Toutefois, dans la version actuelle les atomes qui auraient été liés ne sont pas déliés, il est donc prudent d'évaluer le ESCAPE à l'intérieur d'un PROG et de déclarer "locaux" tous les paramètres formels utilisés.

47) GARB, (Fsubr), 0 arguments ; (GARB)
déclenche un passage du "garbage collector"
La valeur ramenée est NIL.

48) SETSEP, (Fsubr), 2 arguments (SETSEP C N)
- Si N est différent de 0, transforme le $1^{er}$ caractère du nom externe.
C en un séparateur.
- Si N vaut 0, le transforme en un caractère ordinaire.
Le $1^{er}$ caractère de C ne doit pas être numérique, ni appartenir à
{ - , blanc, ( ), ' .
La valeur ramenée est C.

49) INPUT, (Subr), 1 argument ; (INPUT N)
Permet de fixer le n° logique de l'unité de lecture :
N = 5 : télétype
N = 23 : fichier
La valeur ramenée est N.

50) ØUTPUT, (Subr), 1 argument, (ØUTPUT N)
Permet de fixer le n° logique de l'unité d'écriture
N = 6 : télétype
N = 24 fichier
La valeur ramenée est N.

Remarque : les n° logiques d'unités de lecture et d'écriture peuvent
changer suivant l'installation.
51) **ISSUBR, (Subr), 1 argument, (ISSUBR X)**
Prédicat valant TRUE si X est une fonction de type "Subr" ou "Fsubr" et NIL dans tous les autres cas.

52) **SUBFØ, (Subr), n arguments, (SUBFØ NSUB ARG₁... ARGn)**
Permet d'appeler un sous programme défini par l'utilisateur (en Fortran par exemple).

- NSUB est le n° du sous programme dans la liste des sous programmes définis par l'utilisateur.

- ARG₁... ARGn sont les arguments passés au sous programme.

53) **ARRAY, (Subr), 1 argument, (ARRAY L)**
crée un tableau, zone de L paires contigües, encadrées par deux paires de type "tableau".
La valeur retournée est l'adresse du début de cette zone.

54) **ARRAYP, (Subr), 1 argument, (ARRAYP X)**
prédicat valant TRUE si X est un tableau, NIL sinon.

55) **GETA, (Subr), 2 arguments, (GETA X I)**
suppose que X est un tableau (erreur non détectée dans la version actuelle) ;
a pour valeur la lère paire de tableau X.

56) **SETA, (Subr), 3 arguments, (SETA X I Y)**
suppose, comme GETA, que X est un tableau,
rend la lère paire du tableau X identique à Y ;
la valeur retournée est Y.
Si Y est un doublet, SETA est donc défini par :
(LAMBDA (X I Y)
   (SET (GETA X I) (CAR Y))
   (RPLACD (GETA X I) (CDR Y))
   Y)
## 3.2. - Les formes du système

Pour pouvoir communiquer avec l'utilisateur, le système doit pouvoir lire et écrire des formes et des listes.

Ceci est réalisé par l'évaluation de formes particulières, créées à l'initialisation du système.

### 1) `READ`, `READ1`, `%READ`

La fonction `READ`, sans arguments, lit une liste (éventuellement en notation pointée) et en crée la représentation interne sous forme d'atomes et de doublets. `READ` utilise deux autres fonctions système, `READ1` et `%READ`.

Les contenus des atomes `READ`, `READ1` et `%READ` sont donnés ci-dessous :

**%READ**

(FLAMBD (%L)
(SETQ %X ERRLEC)
(WHILE
(EG %X ERRLEC)
(SETQ %X (READ1))
(SETQ %X (EVAL (CONS PROG
%L)))))

**READ**

(NLAMBD (; %X)
(INIT)
(%READ) (COND
((OR
(LQ %X RPAR)
(EG %X PERIOD))
(LRRLEC))
(TRUL
%X))))
READ1

(NLAMBD (; %X %Z %J)
(WHILE
(EQ (SETQ %X (LFCT)) BLANK))
(COND
((EQ %X LPAR)
(PROG NIL
(WHILE
TRUE
(SETQ %X (READ1))
(COND
((EQ RPAR %X)
(RETURN %J))
((LO %X PERIOD)
(READ (COND
((OR
(EQ %X RPAR)
(EQ %X PERIOD))
(ERRLEC))
(%J
(RPLACD %Z %X))
(TRUE
(SETU %J (CONS NIL %X)))))
(READ (COND
((NEQ RPAR %X)
(ERRLEC))
(TRUE
(RETURN %J)))))
(TRUE

(COND
(%)
(RPLACD %Z (CONS %))
(SETQ %Z (CTR %Z)))
(TRUE
(SETQ %J (CONS %))
(SETQ %Z %J)))))
((EQ (CADR %X) (JUSTE MACRO))
(%X))
(TRUŁ
%X)))
## 2) PRINT, PRIN1

La fonction PRINT admet un argument, atome ou liste, dont elle écrit, sur l'organe de sortie, la représentation externe, en utilisant la notation pointée lorsque la liste est mal formée.

Exemple : (A B . C)

PRINT utilise la fonction système PRIN1.

Les contenus des atomes PRINT et PRIN1 sont les suivants :

PRINT :

(LAMBDA (%X)
(PRINT %X)
(TLRPRI)
%X)

PRIN1 :

(LAMBDA (%X)
(PROG (%J)
(COND
((ATON %X)
(ECR %X)
(RETURN %X))
((ARRAYP %X)
(EUR (QUOTE **))
(RETURN %X))
(SETO %J %X)
(EUR LEAK)
%A (PRIN1 (NEATL %J))
(COND
(%
(COND
((ATOM %J)
(EUR PERIOD)
(EUR %J))
((ARRAYP %J)
(EUR PERIOD)
(EUR (QUOTE **)))
(TRUE
(EUR BLANK)
(GU %A)))))
(EUR REAR)
(RETURN %X)
NIL ))

3) On trouvera en annexe la liste d'un certain nombre de λ-expressions courantes, qui se trouvent dans le système, ainsi que leur utilisation.
### 3.3. - L'interprêteur

Il évalue la forme suivante :

(WHILE (NULL (EQ (QUØTE %%%%%TRA
(PRINT (EVAL (READ)))))

C'est-à-dire qu'il évalue les formes fournies par l'utilisateur en
imprimant le résultat entre chaque lecture de forme.

L'évaluation au niveau 0 d'une forme (GØ) provoque la fin de travail, avec
sauvegarde de la mémoire, celle d'une forme (RETURN), la sortie "en catastrophe"

## 4. - Gestion de l'espace des paires

### 4.1. - La pile de récursion

Elle est constituée d'un tableau (4 x MAXP), où MAXP est la profondeur maximum de récursion autorisée.

A chaque entrée dans l'évaluateur le point d'appel de l'évaluateur est empilé, les 3 autres variables de la pile sont des adresses de paires qui doivent être conservées jusqu'à la fin de l'évaluation à ce niveau.

### 4.2. - La liste libre

A un instant donné, l'espace des paires est formé de 3 sous-ensembles complémentaires :

- les paires de la liste libre

- les paires inutilisées

- les paires utilisées.

Pour définir ce qu'on appelle une paire utilisée, définissons d'abord
la notion de "descendant" :

Soient $P_1$ et $P_2$, 2 paires

$P_2$ est dite "descendant" de $P_1$, si :

3 $P_3$ ($P_3$ = $P_1$ ou $P_3$ descendant de $P_1$)

tel que :

$P_2$ = "CAR" ($P_3$)

ou

$P_2$ = "CDR" ($P_3$)

ou $P_3$ est un idem de tableau de longueur L

et $0 < P_2 - P_3 < L$

Une paire utilisée est un littéral ou une paire dont l'adresse se trouve
dans la pile de récursion ou un descendant d'un littéral un descendant d'une
telle paire.
Il n'est pas possible pour le système de connaître à tout instant
l'ensemble des paires utilisées.

Par contre, les paires dont il est sûr qu'elles ne sont pas
utilisées sont disposées en une liste, organisée de la façon suivante :

si $L_{i+1}$ et $L_i$ sont 2 paires libres successives de cette liste :

$L_{i+1} = (\text{CAR } L_i)$.

La lère paire de cette liste est connue du système.

Lorsqu'une paire est"rendue par le système", elle est insérée en
tête de cette liste ; lorsqu'une paire est "réclamée" par le système, elle
est prise en tête de cette liste : son fonctionnement est donc celui d'une
pile.

Lorsque cette liste est vide, il devient nécessaire de la
reconstituer, à l'aide des paires inutilisées ; ceci est réalisé par
l'algorithme de "garbage collector".
### 4.3. - Le "garbage collector"

La récupération des paires libres peut se faire de deux manières différentes, suivant que les paires utilisées sont ou non tassées en bas de la mémoire.

A l'initialisation, les paires de la liste libre sont marquées d'un bit de marquage M1.

#### A) Algorithme GO

1) La $1^{ère}$ phase (P1) consiste à démarquer les paires se trouvant encore dans la liste libre.

2) La $2^{ème}$ phase (P2) consiste à marquer, à l'aide de M1, toutes les paires descendant :

- des littéraux (obtenus par la table des noms externes)

- des paires sur lesquelles pointent les éléments de la pile de récursion.

3) La $3^{ème}$ phase (P3), est la récupération proprement dite des paires, l'espace des paires est parcouru du haut vers le bas :

- une paire marquée est démarquée ;

- une paire non marquée est marquée et insérée en tête de la liste libre.

Le nombre de paires libres contigües disponibles à droite d'une telle paire est stocké dans le "CAR" de cette paire.

Les phases P1, P2, P3, constituent le "garbage" proprement dit GO.

GO est effectué - par appel de la fonction GARB

- lorsque la liste libre est vide.
## B) Algorithme G1

Pour permettre l'allocation dynamique de tableaux (fonction ARRAY), un tassement des paires utilisées s'avère indispensable : il est réalisé par l'algorithme G1.

G1 est constitué de l'exécution préalable de P1, P2, P3.

4) La 4ème phase (P4), est le recopiage. La mémoire est parcourue du haut vers le bas : la paire non marquée, (donc utilisée) est :

- recopiée en tête de la liste libre

- puis marquée

- l'adresse où elle est a été recopiée, est stockée dans le "car".

Il y a là cependant une restriction : les paires d'un tableau ne sont recopiées que si, en tête de la liste libre, se trouvent assez de paires contigües pour stocker tout le tableau.

5) La 5ème phase (P5) est la mise à jour : l'espace des paires est parcouru, pour toute paire non marquée (donc utilisée) et qui n'est pas une constante ou un élément de tableau :

on met à jour le "CAR" et le "CDR".

La mise à jour d'une adresse consiste à la remplacer, si la paire correspondante est marquée (donc a été recopiée) par la nouvelle adresse, qui se trouve dans le "CAR".

Ancienne adresse : AA

<table><tr><td>NA</td><td>M1</td></tr></table>

Nouvelle adresse : NA

<table><tr><td></td><td></td></tr></table>

6) La 6ème phase est P3, modifiée de façon à ne plus changer le marquage :

- les paires marquées sont insérées dans la liste libre.

G1 est appliqué :

- lorsque la création d'un tableau a été impossible

- en fin de travail, avant la sauvegarde sur fichier de l'espace des paires.
C) L'algorithme de marquage

L'algorithme choisi n'utilise pas de pile, ce qui lui permet de marquer n'importe quel graphe, sa description en LISP serait la suivante :

(LAMBDA (A)
  (PROG (A1 PERE TAB)
    D (COND
      ((M1P A)
        (GO R)))
      (M1 A)
      (COND
        ((NUMBP A)
          (GO R)))
      (COND
        ((ARRAYP A)
          (COND
            (TAB
              (SETJ TAB NIL)
              (GO R)))
            (TRUE
              (SETJ TAB TRUE)
              (SETJ A (PLUS
                A
              1)))
              (GO D))))
      (TRUE
        (M2 A)
        (COND
          (TAB
            (M3 A)))
          (SETJ A1 (CAR A))
          (SET A PERE)
          (SETQ PERE A)
          (GO D)))
    R (COND
      ((NULL PERE)
      (RETURN))
      ((M2P PERE)
        (UNM2 PERE)
        (SETQ A1 (CAR PERE))
        (SET PERE A)
        (SETQ A (CDR PERE))
        (REPLACD PERE A1)
        (GO D)))
      (TRUE
        (SETJ A1 (CDR PERE))
        (REPLACD PERE A)
        (SETQ A PERE)
        (SETQ PERE A1)
        (COND
          ((M3P A)
            (UNM3 A)
            (SETQ A (PLUS
              A
            1)))
          (SETJ TAB TRUE)
          (GO)))
      (TRUE
        (GO R))))))}
M1, M2, M3 sont des fonctions positionnant chacune un indicateur de marquage dans les paires.

UNM1, UNM2, UNM3, sont des fonctions remettant ces indicateurs à 0.
M1P, M2P, M3P, sont des prédicats portant sur ces indicateurs.

## 5. - Détails d'implémentation

### 5.1. - Noms externes

La correspondance entre la chaîne de caractère représentant le nom externe d'un identificateur ou "littéral", peut être réalisée de deux manières différentes :

- par une recherche systématique dans une table

- par une recherche accélérée à l'aide d'un hash-coding.

Dans un système conversationnel, tant que la taille de la table est raisonnable, le temps de recherche nécessaire est négligeable devant les délais d'entrée-sortie : c'est pourquoi la $1ère$ méthode, de programmation plus simple, donc plus courte, a été préférée.

a) Les caractères autorisés sont ceux du tableau ALP, de longueur LALP. Le tableau SEP doit toujours être de longueur < LALP. Dans la version standard, LALP = 56.

b) La longueur des noms externes est, du maximum, LNØM2, caractères. Toute chaîne de longueur supérieure est tronquée. Ces caractères (complétés à LNØM2 par des blancs à droite) sont stockés sur LNØM mots (LNØM2 = 2 x LNØM) : chaque mot contient un nombre de la forme $100 \times C1 + C2$, où C1 et C2 sont les rangs, dans ALP, des deux caractères stockés.

Les tableaux NØM, dans le programme principal, et dans le sous programme ZLECT, ont pour longueur LNØM.

Le tableau NEXT a pour deuxième dimension LNØM.

c) Le nombre de noms externes est MAXNØ.

Le tableau NEXT a pour première dimension MAXNØ.

Le tableau NINT a pour dimension MAXNØ + 3.
### d) Séparateurs :

Les caractères ( ) . ' . sont définis comme séparateurs à l'initialisation. Tout caractère non numérique autre que - , + , 0 , peut être défini ou non comme séparateur à l'aide de la fonction SETSEP.

Tout séparateur est pris à lui tout seul pour un nom externe.

Le "/" permet cependant de considérer tout caractère comme non numérique, non séparateur :

/(././+// représente donc le nom externe (./+/

Il n'est pas imprimé en sortie.

### e) Notation

L notation 'L, où L est une liste quelconque, est interprétée à la lecture, par la fonction (READ), comme (QUOTÉ L). C'est un exemple d'utilisation de la λ-expression MACRØ.

## 5.2. - Pile de récursion

La longueur est MAX1. Les tableaux P1, P2, P3, P4 doivent avoir pour longueur MAX1. Le tableau ITAB, du sous programme GARB, doit avoir pour première dimension MAX1.

## 5.3. - Entrée-sorties

Sur la version standard, IREAD = 5
INRIT = 6
IREAD = 101
INRØT = 102

## 5.4. - Codes d'erreurs

Un certain nombre d'erreurs peuvent être détectées par le système : l'utilisateur en est averti par l'impression (sur le fichier INRIT) d'un libellé : ERREUR-n, où n est une étiquette du programme FORTRAN de l'interprêteur.
Toute évaluation en cours est arrêtée : le système revient du niveau 0 de récursion ; les variables liées n'étant pas déliées, afin de faciliter le debugging.

La liste des codes erreurs de la version actuelle est donnée en annexe.

## 6. - Utilisation

Une session de travail de l'interprêteur se fait normalement avec un fichier utilisateur en entrée, sauvegarde en fin de session. La création de ce fichier de travail courant, SYSC, se fait par "bootstrap", lors d'une phase d'initialisation.

### 6.1. - Initialisation

La création du système de travail se fait à l'aide de l'interprêteur. Dans la version standard, à la question :

"Frapper 1 si fichier utilisateur", l'utilisateur frappe 0, signalant ainsi que le fichier système en entrée est le fichier d'initialisation SYSINI.

SYSINI contient principalement le début de l'espace des paires : à savoir les SUBR et FSUBR, et une version simplifiée des λ-expressions READ, READ1, PRINT, PRIN1.

### 6.2. - Génération

Un certain nombre de fonction standard sont également fournies à l'utilisateur sous forme de λ-expressions trouvant dans le fichier SYSLIS.

La lecture de ce fichier par l'interprêteur est déclenchée par l'évaluation de (INPUT n), où n est l'unité logique de SYSLIP.

La dernière λ-expression de SYSLIS est (INPUT 5), qui "donne la main" à l'utilisateur.
### 6.3. - Sauvegarde

La fin d'une session peut se dérouler avec ou sans sauvegarde en vue d'une continuation à la session suivante.

- L'évaluation (au niveau 0 de récursion) de (GØ) provoque la sauvegarde, sur un fichier d'étiquette logique IWRØT, du système de travail, après "garbage" et tassement.

- L'évaluation de (RETURN) termine la session sans sauvegarde.

### 6.4. - Session normale

Pour commencer une session normale, à partir d'un fichier utilisateur, il suffit de répondre "1", à la question :

"Frapper1, si fichier utilisateur"

Le fichier système utilisateur est alors lu, avec l'étiquette logique IREDD.
ANNEXE 1

λ-expressions standard du système

ADD1

(LAMBDA (%X)
(PLUS
%X
1))

SUB1

(LAMBDA (%X)
(DIFFER %X 1))

NEQ

(LAMBDA (%X %Z)
(NULL (EQ %X %Z))))

ZEROP

(LAMBDA (%X)
(EQ %X 0))

CAAR

(LAMBDA (%X)
(CAR (CAR %X))))

CADR

(LAMBDA (%X)
(CAR (CDR %X))))

CDAR

(LAMBDA (%X)
(CDR (CAR %X))))

CADDR

(LAMBDA (%X)
(CAR (CDR (CDR %X)))))

EQUAL

(LAMBDA (%X %Z)
(COND
((ATOM %X)
(EQ %X %Z))
((ATOM %Z))
((EQUAL (NEXTL %X) (NEXTL %Z))
(EQUAL %X %Z)))))

predicat valant TRUE si %X et %Z ont pour valeur des atomes égale
des listes égales.
## MEMQ

(LAMBDA (%X %L)
    (PROG NIL
        (WHILE
            %L
            (COND
                ((EQ (CAR %L) %X)
                   (RETURN %L))
                (TRUE
                    (SETQ %L (CDR %L)))))
        )
    )
)

%L est une liste ;

%Y est un atome ;

la valeur de MEMQ est la partie de L% commençant par %X (NIL si %X n'appartient pas à %L).

## LENGTH

(LAMBDA (%X %Z)
    (SETQ %Z 0)
    (WHILE
        %X
        (NEXTL %X)
        (SETQ %Z (ADD1 %Z)))
    %Z)

%X est une liste ;

la valeur est la longueur de la liste %X.

## NTH

(LAMBDA (%X %Z)
    (WHILE
        (NULL (LT %X 2))
        (SETQ %X (SUB1 %X))
        (NEXTL %Z))
    %Z)

%X est un nombre ;

%Z est une liste ;

la valeur est la partie de la liste %Z commençant par le %X<sup>ième</sup> élément.

## ITEM

(LAMBDA (%X %Z)
    (CAR (NTH %X %Z)))

%X est un nombre ;

%Z est une liste ;

la valeur est le %X<sup>ième</sup> élément de %Z.
### RANG

(LAMBDA (%X %L)
(PROG (%Z)
(SETQ %Z 0)
(WHILE
%L
(SETQ %Z (ADD1 %Z))
(COND
((EQ %X (NEXTL %L))
la valeur est le rang de l'atome %X dans la liste %L ;
(0 si %X n'appartient pas à %Z).

### REVERS

(LAMBDA (%L %X)
(WHILE
%L
(SFTQ %X (CONS (NEXTL %L) %X)))))
%L est une liste ;

la valeur est la liste inverse.

### NCONC

(LAMBDA (%X %Z ; %L)
(SETQ %L %X)
(WHILE
(CDR %L)
(NEXTL %L))
(RPLACD %L %Z)
%X)

%X et %Z sont des listes ;

l'effet de bord les concatène physiquement ;

la valeur ramenée est la liste résultat.
### NCONC1

(LAMBDA (%X %Z)
(NCONC %X (LIST
    %Z)))

%X est une liste ;

l'effet de bord insère physiquement ;

%Z en queue de %X ;

la valeur retournée est %X.

### REMOVE

(LAMBDA (%X %L %Z)
(COND
  ((NULL %L))
  (TRUE
    (SETQ %Z (REMOVE %X (CDR %L)))
    (COND
      ((EQ (CAR %L) %X)
        %Z)
      (TRUE
        (CONS (CAR %L) %Z)))))

%L est une liste ;

%X un atome ;

la valeur retournée est une liste dont toutes les occurences de %X ont été supprimées.

### APPEND

(LAMBDA (%L %X)
(COND
  ((NULL %L)
    %X)
  (TRUE
    (CONS (NEXTL %L) (APPEND %L %X)))))

identique à NCONC mais les arguments ne sont pas modifiés : une nouvelle liste est créée.
### COPY

(LAMBDA (%L %X %Z)
(COND
((EQUAL %L %X)
  %Z)
((ATOM %L)
  %L)
TRUE
(CONS (COPY (NEXTL %L) %X %Z) (COPY %L %X %Z)))))

La valeur est une liste déduite de %L en remplaçant toute sous liste
de %L égale à %X par %Z.

### EVLIS

(LAMBDA (*4741)
(COND
((NULL *4741))
TRUE
(CONS (EVAL (NEXTL *4741)) (EVLIS *4741)))))

%X est une liste.

La valeur est la liste des évaluations des éléments de %X.

### MAP

(LAMBDA (*5559 *5580)
(WHILE
  *5559
(*5580 *5559)
(NEXTL *5559)))

%X est une liste ;

%Z est une fonction ;

%Z est appliquée successivement aux "cdr" de %X.

La valeur est la dernière de ces évaluations.
### MAPC

(LAMBDA (*5054 *5075)
(WHILE
  *5054
  (*5075 (NEXTL *5054)))))

%%X est une liste;

%%Z est une fonction;

%%Z est appliquée successivement aux éléments de %%X.

La valeur retournée est la dernière de ces évaluations.

### MAPLIS

(LAMBDA (*353 *374)
(COND
  ((NULL *353))
  (TRUE
    (CONS (*374 (NEXTL *353)) (MAPLIS
      *353
      *374)))))

%%X est une liste ;

%%Z est une fonction.

La valeur retournée est une liste dont chaque élément est l'évaluation
de %%Z appliquée à l'élément correspondant de %%X.

### MAPTOT

(LAMBDA (%X %Z)
ESPACE LIBRE : 3268
ESPACE TOTAL : 6000
(COND
  ((NULL %X))
  ((ATOM %X)
    (%Z %X))
  (TRUE
    (CONS (MAP* (NEXTL %X) %Z) (MAP* %X %Z)))))

analogue à MAPLIS, mais %%X est considéré comme un arbre,
%%Z est appliquée à chaque feuille.

La valeur retournée est l'arbre correspondant.
## SPACES

(LAMBDA (%X)
(WHILE
(GT %X 0)
(SETQ %X (SUB1 %X))
(ECR BLANK)))

écrit %X blancs.

La valeur retournée est BLANK.

## TRACE

(FLAMRD (%L : %J %LARG %Z %FONC *4691 %FORME)
(DE
%FORME
(%Z %J)
(COND
  ((NULL %Z))
  (TRUE
    (CONS (%J (NEXTL %Z)) (%FORME %Z %J)))))
(WHILE
%L
(SETQ %FONC (NEXTL %L))
(SETQ %J (CAR %FONC))
(SETQ %Z (GENSYM))
(SET %FONC (LIST
  (NEXTL %J)
  (SETQ %LARG (NEXTL %J))
  (QUOTE (ECR (QUOTE :----->)))
  (QUOTE (SPACES 3))
  (LIST
    ECR
    (LIST
      QUOTE
      %FONC))
    (QUOTE (TTAB 20))
    (CONS PROGN
      (%FORME %LARG (QUOTE (LAMBDA (*4691)
        (LIST
          PROGN
          (LIST
            (QUOTE PRIN1)
            *4691)
            (QUOTE (SPACES 3)))))
      (QUOTE (TERPRI))
      (LIST
        SETQ
        %Z
        (CONS PROGN
          (%J))
        (QUOTE (ECR (QUOTE <----:)))
        (QUOTE (SPACES 3))
        (LIST
          ECR
          (LIST
            QUOTE
            %FONC))
          (QUOTE (TTAB 20))
          (LIST
            (QUOTE PRINT)
            %Z))))
      %TRACE))
    %TRACE))
(TRACE F1 F2... F_n), où F_1...F_n sont des fonctions définies par des
λ-expressions, transforme les fonctions de telle façon que l'évaluation
de (F_i...) est précédée de :

l'impression de

...> F_i A_1...A_n

où A_1, ... A_n sont les arguments (évalués) de F_i et suivie de l'impression

de :

<... : F_i V

où V est la valeur retournée.

UNTRAC

(FLAMBD (%L : %X %FONC)
(WHILE
%L
(SETQ %FONC (NEXTL %L))
(SETQ %X (CAR %FONC))
(SFT %FONC (CONS (NEXTL %X) (CONS (NEXTL %X) (CDR (CAR (CDR
(CDR (CAR (CDR (CDR (CDR (CDR (CDR (CDR %X)))))))))
NIL)

(UNTRACE F₁...Fₙ), où F₁...Fₙ sont des fonctions "tracées", leur redonne leur forme originelle.
## DUMP

(LAMBDA (%X % L)
  (MAPC
    %X
    (QUOTE (LAMBDA (%Z)
      (TERPRI)
      (TERPRI)
      (SETQ %L (CAR %Z))
      (COND
        ((OR
          (EQ (CAR %L) LAMBDA)
          (EQ (CAR %L) FLAMBD)
          (EQ (CAR %L) NLAMBD))
          (ECR LPAR)
          (ECR SETQ)
          (SPACES 40)
          (ECR %Z)
          (SPACES 5)
          (ECR CQUOTE)
          (PRETTY %L)
          (PRINT RPAR))
        (TRUE
          (ECR %Z)
          (TTAB 10)
          (ECR (QUOTE :))
          (SPACES 5)
          (PRINT %L))))))
    )
  )
)

%X doit avoir pour valeur une liste d'atomes.

Le nom de ces atomes est imprimé avec leur valeur (en PRETTY PRINT si ce sont des fonctions).

Utilisé surtout pour connaître le contenu de la mémoire grâce à (DUMP(ØBLIST)),

## PRETTY

(LAMBDA (%X % J LESCAP XPRTTY ENDLIN)
  (DN
    XPRTTY
    NIL
    (SETQ %J (ADD1 %J))
    (MAPC
      %X
      (QUOTE (LAMBDA (%X)
        (ENDLIN)
        (SUPERP %X))))
      (SETQ %J (SUB1 %J))
      (ECR RPAR))
    (DN
      ENDLIN
      NIL
      (TERPRI)
      (TTAB (TIMES
        %J
        2)))
      (TERPRI)
      (TTAB (SETQ %J 2))
      (SUPERP %X)))

utilise SUPERPRINT

%X a pour valeur une liste définissant une fonction.

La liste est imprimée, avec des indentations, pour permettre une meilleure lisibilité.

La valeur ramenée est RPAR.
SUPERP

(LAMBDA (%X; %L)
    (PROG NIL
        (COND
            ((ATOM %X)
             (PRIN1 %X))
            ((ECR LPAR)
             (WHILE
                %X
                (SETQ %L (NEXTL %X))
                (COND
                    ((NULL %X))
                    ((OR
                        (MEMQ %L LESCAP)
                        (MEMQ %L (QUOTE (OR
                            AND
                            LIST
                            PLUS
                            TIMES
                            WHILE
                            DE
                            DF
                            DN
                            FREACH
                            PROGN
                            MAP
                            MAPC
                            MAPLIS
                            MAPTOT)))))
                        (ECR %L)
                        (RETURN (XPRTTY)))
                        ((EQ %L (QUOTE ESCAPE))
                         (ECR %L)
                         (SETQ LESCAP (CONS (CAR %X) LESCAP))
                         (RETURN (PROGN
                             (XPRTTY)
                             (NEXTL LESCAP)))))
                    ((OR
                        (EQ %L LAMBDA)
                        (EQ %L FLAMBD)
                        (EQ %L NLAMBD)
                        (ECR %L)
                        (SPACES 1)
                        (SUPERP (NEXTL %X))
                        (RETURN (XPRTTY)))
                    ((EQ %L COND)
                        (ECR %L)
                        (SETQ %J (ADD1 %J))
                        (MAPC
                            %X
                            (QUOTE (LAMBDA (%X)
                                (ENDLIN)
                                (ECR LPAR)
                                (SUPERP (NEXTL %X))
                                (XPRTTY)))))
                        (SETQ %J (SUB1 %J))
                        (RETURN (ECR RPAR)))
                    ((EQ %L PROG)
                        (ECR %L)
                        (SPACES 1)
                        (SUPERP (NEXTL %X))
                        (SETQ %J (ADD1 %J))
                        (WHILE
                            %X
                            (ENDLIN)
                            (COND
                                ((ATOM (CAR %X))
                                 (PRIN1 (NEXTL %X))
                                 (TTAB (TIMES
                                     2
                                     (PLUS
                                         %J
                                     -2))))
                                ((SPACES 4)))
                                (SETQ %J (PLUS
                                    %J
                                    2)))
                            (COND
                                (%X
                                (SUPERP (NEXTL %X)))))
(SETQ %J (DIFFER %J 2)))
(SETQ %J (SUB1 %J)))
(RETURN (ECR RPAR))))
(SUPERP %L)
(AND
%X
(SPACES 1)))
(ECR RPAR)))))

## LPRETT

(FLAMRD (%L %X)
(MAPC
%L
(QUOTE (LAMRDA (%L)
(TERPRI)
(PRINT %L)
(PRETTY (CAR %L)))))

(LPRETT F₁...Fₙ), où F₁...Fₙ sont des fonctions définies par des λ-expressions, imprime, pour chaque Fᵢ le nom et la valeur, en PRETTY PRINT, de la fonction.

## EDIT

(NLAMRD (%L %X %Z)
(SET %L (COPY (EVAL %L) (EVAL %X) (EVAL %Z))))
%L)

(EDIT F E₁ E₂)
remplace dans F toutes les occurences de la sous liste E₁ par E₂.
(une nouvelle liste est créée dont la valeur est affectée à F).
### ADVISE

(FLAMBD (%L ; %X)
(SETQ %X (CAAR %L))
(SET (CAR %L) (CONS (CAR %X) (CONS (CADR %X) (CONS (CONS PROGN
(CDR %L)) (CDDR %X)))))

(ADVISE F E₁...Eₙ)

F est une fonction

E₁... Eₙ sont des formes à évaluer

insère en tête de F les formes E₁... Eₙ.

### UNADVI

(NLAMBD (%L))

(SET %L (CONS (CAAR %L) (CONS (CAR (CDAR %L)) (CDDR (CDAR %L)))))

retourne à F sa forme originelle.

### PAUSE

(LAMBDA (.%X)
(WHILE
IPAUSE
(PRIN1 (LIST
(QUOTE PAUSE)
%X))
(PRINT ??)
(PRINT (EVAL (READ)))))
TRUE)

Si IPAUSE ne vaut pas NIL : boucle sur les évaluations suivantes :

- imprimer "PAUSE" %X ??

où %X est le "nom" de la pause.

- évaluer la λ-expression suivante.

Dans la version actuelle on peut sortir de la boucle en faisant évaluer

(RETURN), ou (GØ) ou (GØ TØ ...).

### TRSET

(LAMBDA (*4937 *4968)
(SET *4937 *4968)
(PRIN1 *4937)
(TTAR 20)
(PRINT (CAR *4937)))))

analogue à SET mais imprime en plus les valeurs des arguments.
### TRSETQ

(NLAMRD (*3534 *3569)
(SET *3534 (EVAL *3569))
(PRIN1 *3534)
(TTAR 20)
(PRINT (CAR *3534)))

analogue à SETQ mais imprime en plus le premier argument.

### MACRO

(NLAMRD (%X %L)

(SETSEP %X 1)
(RPLACD %X (QUOTE (MACRO)))
(SET %X %L)
%X)

%X doit être un atome dont le nom externe ne comporte qu'un caractère
%L est une fonction sans arguments

%X prend pour valeur %L (et devient de ce fait une fonction).

En outre, l'indicateur MACRØ est placé sur la P-liste de %X, avec

la valeur 1, et le caractère du nom externe de %X devient séparateur.

Désormais la lecture de ce caractère déclenchera l'évaluation de cette
fonction appliquée à 0 arguments.

### GETP

(LAMBDA (%X %Z : %L)
(COND
((SETQ %L (MEMQ %Z (CDR %X))))
(CADR %L)))))

a pour valeur la propriété (ou la liste de propriétés) de l'atome %X sous
l'indicateur %Z.

### PUTP

(LAMBDA (%X %Z %J : %L)
(COND
((SETQ %L (MEMQ %Z (CDR %X))))
(RPLACD %L (CONS %J (CDDR %L))))
%X)
(TRUE
(RPLACD %X (CONS %Z (CONS %J (CDR %X))))))))

donne à l'atome %X la propriété %J sous l'indicateur %Z, (et crée ce
dernier s'il est absent) la valeur retournée est %X.
### ADDP

(LAMBDA (%X %Z %L %J)
(COND
((SETQ %J (MEMQ %Z (CDR %X))))
(COND
((MEMQ %L (CADR %J))))
(TRUE
(SET (CDR %J) (CONS %L (CADR %J)))))
(TRUE
(RPLACD %X (CONS %Z (CONS (LIST
%L) (CDR %X)))))
))
))

ajoute %L à la liste de propriétés de l'atome %X sous l'indicateur %Z (et crée ce dernier s'il est absent).
La valeur retournée est %X.

### REMP

(LAMBDA (%X %Z %L %J)
(SETQ %J %X)
(WHILE
%J
(COND
((EQ (CADR %J) %Z)
(COND
((SETQ %L (REMOVE %L (CADDR %J))))
(SET (CDDR %J) %L))
(TRUE
(RPLACD %J (CDR (CDDR %J)))))
(RETURN))))
%X)
))

enlève à l'atome %X la propriété %L sous l'indicateur %Z.
S'il ne reste plus de propriété l'indicateur est également enlevé.
La valeur retournée est %Y.

### REMPIN

(LAMBDA (%X %Z %J)
(SETQ %J %X)
(WHILE
%J
(COND
((EQ (CADR %J) %Z)
(RPLACD %J (CDR (CDDR %J))))
(RETURN))
(TRUE
(NEXTL %J)
(NEXTL %J))))
%X)
))

enlève à l'atome %X l'indicateur %Z et la ou les propriétés sous cet
indicateur.
La valeur retournée est %X.
DEFAR

(LAMBDA (%X %L ; %Z)
(SETQ %Z (GENSYM))
(SET %Z (ARRAY %L))
(SET %X (LIST
LAMBDA
(QUOTE (%X))
(LIST
GETA
%Z
(QUOTE %X)))))

crée un tableau de longueur %L ;

la valeur de %X devient une fonction de un argument :

(F N) a pour valeur le N<sup>ième</sup> élément du tableau.
ANNEXE 2

Liste des noms réservés

Les littéraux dont la liste suit ne doivent pas voir leur valeur modifiée par l'utilisateur.

%%TRA et %%RET ne doivent pas être utilisés du tout.

<table><tr><td>AND</td><td>Fsubr</td><td>NUMBD</td><td>Subr</td></tr><tr><td>ATØM</td><td>Subr</td><td>NULL</td><td>Subr</td></tr><tr><td>CAR</td><td>Subr</td><td>ØR</td><td>Fsubr</td></tr><tr><td>CDR</td><td>Subr</td><td>PLUS</td><td>Subr</td></tr><tr><td>COND</td><td>Fsubr</td><td>PRIN1</td><td>λ-expression</td></tr><tr><td>CONS</td><td>Subr</td><td>PRINCH</td><td>Subr</td></tr><tr><td>DE</td><td>Fsubr</td><td>PRINT</td><td>λ-expression</td></tr><tr><td>DF</td><td>Fsubr</td><td>PRØG</td><td>Fsubr</td></tr><tr><td>DIFFER</td><td>Subr</td><td>QUØ</td><td>Subr</td></tr><tr><td>ECR</td><td>Subr</td><td>QUØTE</td><td>Fsubr</td></tr><tr><td>EQ</td><td>Subr</td><td>READ</td><td>λ-expression</td></tr><tr><td>ERRØR</td><td>Fsubr</td><td>READ1</td><td>λ-expression</td></tr><tr><td>EVAL</td><td>Subr</td><td>READCH</td><td>Fsubr</td></tr><tr><td>FLAMBD vaut FLAMBD</td><td></td><td>REMPAI</td><td>Fsubr</td></tr><tr><td>GØ</td><td>Fsubr</td><td>%%RET</td><td>interdit à l'utilisateur</td></tr><tr><td>GØTØ</td><td>Subr</td><td>RETURN</td><td>Subr</td></tr><tr><td>GT</td><td>Subr</td><td>RPLCD</td><td>Subr</td></tr><tr><td>INITR</td><td>Fsubr</td><td>SET</td><td>Subr</td></tr><tr><td>LAMBD vaut LAMBD</td><td></td><td>SETQ</td><td>Fsubr</td></tr><tr><td>LECT</td><td>Fsubr</td><td>TERPRI</td><td>Fsubr</td></tr><tr><td>LIST</td><td>Subr</td><td>TIMES</td><td>Subr</td></tr><tr><td>LT</td><td>Subr</td><td>%%TRA</td><td>interdit à l'utilisateur</td></tr><tr><td>NEXTL</td><td>Fsubr</td><td>TRUE</td><td>vaut TRUE</td></tr><tr><td>NIL vaut NIL</td><td></td><td>TTAB</td><td>Subr</td></tr><tr><td></td><td></td><td>WHILE</td><td>Fsubr</td></tr></table>
ANNEXE 3

Liste des codes erreurs

100 Profondeur maximale de récursion atteinte.

123 Constante ou tableau en position de fonction.

124 Bouclage dans la recherche d'une fonction (en général : NIL en position de fonction).

1313 Etiquette inconnue, dans un Prog.

2000 Ecriture d'un élément non atomique à l'aide de ECR.

2130 Débordement de la table des noms externes.

2300 Application de NEXTL à un élément non atomique.

2305 Application de NEXTL à un atome dont la valeur n'est pas une liste.

3800 Application de RPLACD à une constante ou à un tableau.

5200 Demande d'allocation d'un tableau impossible à satisfaire (fonction ARRAY).
BIBLIOGRAPHIE

[1] CHURCH A.
The Calculi of Lambda-conversion.
Princeton, University Press (1941).

[2] BURSTALL R.M., COLLINS J.S., POPPLESTONE P.J.
Programming in POP-2.
Edinburgh, University Press (1971).

[3] VAN LEHN K.A.
Sail User Manual.
Memo AIM-204
Stanford University, A.I Lab.

[4] SUSSMAN G., WINOGRAD T., CHARNIAK E.
Micro-Planner Reference Manual.
A.I.M. 203 A, M.I.T. Cambridge, Mass.

[5] MAC DERMOTT P., SUSSMAN J.
The Conniver Reference Manual.
A.I.M. n° 259A, M.I.T. Cambridge, Mass
A.D. - 773-555.

[6] RULIFSON J.F., DERKSEN Q.A., WALDINGER R.J.
Q.A4 : A Procedural Calculus for intuitive reasoning.
Technical note 73, S.R.I., A.I. center, Nov. 1973.

[7] TEITELMAN W.
Interlisp Reference Manual.
XEROX Palo Alto center, 1974.

[8] REBOH R., SACERDOTI E.
A Preliminary Q-Lisp Manual.
Technical Note 81
S.R.I. A.I. center (Project 8721), Aug. 1973

[9] GASCON J.
Maclisp 1360 User's Guide.
Communication 286, Mental Health Research Institute University of
Michigan, Ann Harbor, Aug. 1971.

[10] MAC CARTHY J., ABRAHAMS PW., EDWARDS D.J., HART J.P., LEVIN M.I.
Lisp 1.5. Programmer's Manual.
M.I.T. Press, M.I.T., Cambridge, Mass, Dec. 1969.
[11] LUX A.
Etude d'un modèle abstrait pour une machine LISP et de son implémentation.
Thèse de 3ème cycle USMG-INPG, Grenoble 19 Mars 1975.

[12] GREUSSEY P.
Descriptions compactes d'interprètes implémentables : une application
au langage Conniver.
2ème Colloque international sur la programmation
13-15 Avril 1976, PARIS.