Embed Size (px)
Citation preview
P R E M I E R M I N I S T R E C E A - R 3040
C O M M I S S A R I A T AL'ÉNERGIE ATOMIQUE
LE TRAITEMENT DE LISTES EN PROGRAMMATION
S L I P : Langage de listes symétrique
Applications
par
Yvon BROUDIN
Rapport C E A - R 3040
. * C E N T R E D ' E T U D E SN U C L É A I R E S D E S A C L A Y
CEA-R 3040 - BROUDIN Yvon
LE TRAITEMENT DE LISTES EN PROGRAMMATIONSLIP : Langage de listes symétrique - Applications
Sommaire. - La programmation moderne ne se satisfait plus des méthodesclassiques de traitement séquentiel ni des tableaux à positions de mémoirecontiguës. Elle tend à généraliser les méthodes de listes où les cellulesd'un groupe n'ont pas .de relation de voisinage, mais sont enchaînées enlistes, l'une donnant l'adresse machine de l'autre. Ces méthodes sont in-dispensables en "partage de temps" et* dans les traitements en "tempsréel". De plus, elles permettent de traiter des problèmes nouveaux etd'optimiser le temps de traitement de nombreux ai.tres.
De nombreux exemples sont traités, après un résumé des langagesles plus utilisés et une étude plus précise d'un langage de listes : SLIP.Parmi les exemples traités signalons la recherche lexicographique, letraitement de symboles alphanumériques, la dérivation formelle.
Problème traité en FORTRAN II sur IBM 7094. Les sous-program-mes constitutifs du langage sont fournis en annexe.
1966 - Commissariat à l'Energie Atomique - France 152p.
CEA-R 3040 - BROUDIN Yvon
PROGRAMMING LIST PROCESSESSLIP : Symétrie list processor - Applications
Summary. - Modern aspects of programming languages are essentiallyturned towards list processing. The ordinary methods of sequential treatmentbecome inadequate and we must substitute list processes for them, wherethe cells of a group have no neighbourhood connection, bu\ where the addressof one cell is contained in the preceding one. These methods are requiredin "time sharing" solving problems. They also allow us to treat new pro-blems and to solve others in the shortest time.
Many examples are presented after an abstract of the most usuallist languages and a detailed study of one of them : SLIP. Among theseexamples one should note : locating of words in a dictionary or in a cardindex, treatment of non numerical symbols, formal derivation.
The problems are treated in FORTRAN II on an IBM 7094 machine.The subroutimes which make up the language are presented in an appendix.
1966 - Commissariat à l'Energie Atomique - France 15 2 P-
- Rapport CEA-R 3040 -
Services Scientifiques
LE TRAITEMENT DE LISTES EN PROGRAMMATION
SLIP : Langage de listes symétrique
Applications
par
Les rapports du COMMISSARIAT A L'ENERGIE ATOMIQUE sont, à partir du n<> 2200,en vente à la Documentation Française, Secrétariat Général du Gouvernement, Direction dela Documentation, 16, rue Lord Byron, PARIS VlUème,
The C*E,A, reports starting with n° 2200 are available at the Documentation Française,Secrétariat Général du Gouvernement, Direction de la Documentation, 16, rue Lord Byron,PARIS VlUème.
Yvon BROUDIN
(Thèse présentée à la Faculté des Sciences de Paris,Centre d'Orsay,
pour obtenir le titre de Docteur de Sème cycle,spécialité : Electronique)
- Juin 1966 -
Avant de présenter ce travail, Je tiens à remercier Monsieurle Professeur BLAQUIERE d'avoir bien voulu accepter de présider ce Jury.
Je tiens aussi à remercier Monsieur le Professeur BERNARD qui, en dépit
de ses nombreuses occupations a bien voulu accepter d'être membre du Jury,
Je tiens à exprimer ma profonde reconnaissance à Monsieur
DEBRAINE qui a dirigé mes travaux, et qui, à tout moment, a su me prodi-
guer ses conseils et orienter mes recherches. Les conditions matérielles
qu'il a mises à ma disposition à Saclay m'ont permis de travailler dans
les meilleures conditions et de mener à bien mes travaux.
Je dois beaucoup à Monsieur GAUGENOT du Service de Calcul
Electronique de Saclay, chargé de l'assistance FORTRAN, dont j'ai beau-
coup apprécié les conseils techniques lors de mes fréquentes erreurs de
programmation.
Je tiens aussi à remercier tous ceux qui m'ont permis de pré-
senter cette thèse à la date prévue, et en particulier Mademoiselle
BOURGEOIS, Madame COHEN et le personnel du Service de Documentation
de Saclay qui ont, en un temps record réalisé le travail de présentation
matérielle.
TABLE DES MATIERES
INTRODUCTION Pages
1 - Représentation des informations sur ordinateur 4
- Mode habituel de traitement. Tableaux de données
Caractère séquentiel des informations
- Structures séquentielles. Structures enchaînées.Graphes
2 - Historique critique des langages de listes 8
- IPL V Information Processing Language V 9
- LISP - LISP 1.5 - LISP ALGOL 16
I - SLIP - Symétrie List Processor - Langage de listes 20symétrique
1-1 - Caractéristiques fondamentales de SLIP
- Différents types de cellules 21
- Construction de listes - Suiveur 22
- Marques 25
- Réserve - Renvoi des listes en réserve 26
1-2 - Description du système
1-2-1 - Fonctions primitives 29
1-2-2 - Création de la réserve 31
1-2-3 - Création de listes 33
1-2-4 - Substitutions 34
1-2-5 - Renvoi de cellules en réserve 35
1-2-6 - Mécanisme du suiveur 38
1-2-7 - La récursivité en SLIP 40
1-2-8 - Les données en SLIP 42
1-2-9 - Ecriture du langage 45
Conclusion - Le langage SLIP 46
II - REALISATIONS
II-l « Optimisation de la taille de la réserve 48
II-2 - Différentes présentations des listes
II-2-1 - Sous-programme IMPLST 49
II-2-2 - Passage de la liste de symboles à la 50liste SLIP
II.2-3 - Passage de la liste SLIP à la liste 51de symboles avec parenthèses
Pages
II-3 - Logement de données longues et de symboles
II-3-1 - Fonctions WAGON, TABLEAU
II-3-2 - Manipulation des symboles
II-4 - Dictionnaires
II-5 - Calcul de la valeur d'une fonction représentéepar une liste
II-6 - Dérivation formelle
CONCLUSION
51
52
5358
6l
64
- 1 -
INTRODUCTION
Le concept qui prévalait en ant que fil conducteur en
programmation était la notion de séquence. En ce qui concerne les
langages ordinaires et généraux tels les "ALGOL", les "FORTRAN",...
le travail se fait instruction après instruction donc en séquence.
Par ailleurs, la disposition de tableaux de valeurs, à une ou N
dimensions se fait aussi dans des suites de mémoires à adresses
contiguës. Les directions dans lesquelles s1oriente la programma-
tion moderne tendent à bousculer quelque peu cette idée de séquence,
tant dans le temps que dans l'espace machine, par deux voies qui,
nous le verrons, se rejoignent : la programmation en temps réel et
les langages de listes. La première définit des priorités et des
ordres de passage de programmes ou d'éléments de programme, soit
pour économiser du temps machine, soit pour utiliser immédiatement
des données se présentant de façon aléatoire dans le temps. La
seconde conduit à un enchaînement non séquentiel de termes, de données
ou d'instructions, voire de symboles, qui seront traités par et pour
leur structure, qui tient plus du graphe ou de l'organigramme que du
tableau ou de la matrice. C'est essentiellement ce second aspect du
problème que nous nous proposons d'étudier dans ce travail.
Un certain nombre de langages de listes ont vu le jour ces
cinq dernières années, essentiellement aux Etats-Unis, particulière-
ment au MIT sous l'impulsion d'équipes dirigées par Me Carthy (LISP),
Gelerntner (PLPL), Newell (IPL V), Weizenbaum (SLIP), Yngve (COMIT).
Chaque langage s'inspire de ses prédécesseurs, améliore leurs
performances, retient leurs qualités et élimine leurs défauts. Le
langage que nous nous proposons d'étudier plus spécialement est le
- 2 -
"Symétrie List Processor" ou SLIP qui a été mis au point aux
alentours de I9&3> puis amélioré par la suite, par J. Weizenbaum
à la General Electric et au Massassuchets Institute of Technology*
La caractéristique principale de ce langage est son enchaînement
symétrique et sa "réserve de cellules disponibles" (free storage)
enchaînée.
Il existe deux possibilités principales pour rendre un
langage pratiquement utilisable : créer un compilateur spécialement
adapté au langage ce qui a été maintes fois réalisé pour IPL V,
LISP, COMIT, ou l'exprimer en un autre langage (imbedding) qui peut
être un langage machine (première version de SLIP) ou un langage
plus évolué, FORTRAN ou ALGOL (réalisé en FORTRAN pour SLIP et en
ALGOL pour LISP).
L'étude que nous avons faite de SLIP a été réalisée sur
IBM 7094 disposant d'un compilateur FORTRAN. Les programmes et
sous-programmes seront donc écrits en FORTRAN ou en son langage
machine FAP. Un avantage important de cette écriture est de pouvoir
appeler des sous-programmes du type fonction en chaîne :
L2 = LSG (CONT (LCRTCH (LA) - l)
Un inconvénient important est, parallèlement, le manque de
souplesse du procédé qui utilise le général pour le particulier,
annihilant de ce fait un grand nombre de mémoires auxiliaires utilisées
par le compilateur et le chargeur ainsi que par les sous-programmes de
service, tous chargés à la suite du programme principal. Cet incon-
vénient est minime lorsque l'on dispose d'une machine à nombre de
mémoires important, mais est particulièrement gênant sur les petites
machines où l'on peut être amené à étudier une version simplifiée du
langage. Si la place dont on dispose est insuffisante on peut toute-
fois loger sur bandes une partie des données, ou des structures figées,
ce qui dans notre cas est particulièrement facile grâce aux mécanismes
d'entrée - sortie du FORTRAN. Cette façon de procéder à des mises
en mémoire auxiliaires (auxiliary storage) a été étudiée plus en détail
pour d'autres langages (LISP en particulier) où le problème est plus
aigu du fait de la non récupération des cellules devenues inutiles
(unneeded) dans le cours du traitement, ou de la nécessité de procéder
à leur récupération et éventuellement à un tassement en tête de la ré-
serve. On peut être alors amené à de longues études de rentabilité et
de fréquence d'utilisation des mémoires auxiliaires.
Cependant exprimer un langage de listes en un autre langage
plus général comporte un certain nombre d'avantages : possibilités de
le comprendre et de l'utiliser plus rapidement, possibilité de travail-
ler sur des machines courantes, à usage multiple, dont l'accès au com-
pilateur n'est pas possible, plus grande facilité d'introduction de
données et de sortie de résultats, d'une manière générale utilisation
des possibilités du système d'exploitation lié à ce langage plus général.
- 5 -
L'exploration des structures est foncièrement différente.
Dans les deux cas on doit connaître ou l'origine du tableau, ou celle
de la liste. Dans le cas du tableau, la valeur d'un ou plusieurs
index, ajoutée (FORTRAN IV), ou soustraite (FORTRAN II) à l'adresse
absolue de l'origine A donne la position de la cellule, manipulation
longue d'indices nombreux, qui limite les dimensions. Dans le second
cas, l'exploration se fait au moyen de sous-programmes ou d'instructions
reconnues par le compilateur, et nous transporte successivement d'une
position de mémoire a. l'autre, positions non contigu'ës dans la machine.
On peut ainsi en rajouter à volonté (données supplémentaires - nouvelles
valeurs...) ce qui est impossible dans le cas classique du tableau, où
les valeurs, les positions, leur nombre, sont fixés à l'avance.
Ceci permet de penser que la reconnaissance de structures,
la démonstration de théorèmes, le travail sur données littérales...
passe par le traitement de listes, plutôt que par la programmation
de type classique séquentiel.
Il est vraisemblable que l'une des idées qui ont conduit
à l'étude des listes, est la possibilité, offerte par ces dernières,
d'augmenter au cours du traitement la taille d'un tableau, autant qu'il
s'avère nécessaire de le faire, dans des limites très grandes, seulement
bornées par la taille de la mémoire centrale de la machine. Ceci évite
d'avoir à fixer les limites a priori, avant traitement ou entrée des
informations. Le tableau en liste grandit au fur et à mesure de l'arri-
vée des données c'est-à-dire au cours du traitement proprement dit.
Un graphe représente les relations d'un système. Il relie
par des liaisons orientées un certain nombre de noeuds. Ce graphe
peut être cyclique ou non. On définit en théorie des graphes la notion
d'arbre, qui est l'ensemble maximal des graphes terminaux ne contenantUUU UC UCJ.AUJ.CO ww.U«.i.wii«.«<.".«» ••»Pas de cellule vide
Pig. I.1.1
3
P
Mm
m
•&,
L'exploration des structures est foncièrement différente.
Dans les deux cas on doit connaître ou l'origine du tableau, ou celle
de la liste. Dans le cas du tableau, la valeur d'un ou plusieurs
index, ajoutée (FORTRAN IV), ou soustraite (FORTRAN II) à l'adresse
absolue de l'origine A donne la position de la cellule, manipulation
longue d'indices nombreux, qui limite les dimensions. Dans le second
cas, l'exploration se fait au moyen de sous-programmes ou d'instructions
reconnues par le compilateur, et nous transporte successivement d'une
position de mémoire à l'autre, positions non contigu'ës dans la machine.
On peut ainsi en rajouter à volonté (données supplémentaires - nouvelles
valeurs...) ce qui est impossible dans le cas classique du tableau, où
les valeurs, les positions, leur nombre, sont fixés à l'avance.
Ceci permet de penser que la reconnaissance de structures,
la démonstration de théorèmes, le travail sur données littérales...
passe par le traitement de listes, plutôt que par la programmation
de type classique séquentiel.
Il est vraisemblable que l'une des idées qui ont conduit
à l'étude des listes, est la possibilité, offerte par ces dernières,
d'augmenter au cours du traitement la taille d'un tableau, autant qu'il
s'avère nécessaire de le faire, dans des limites très grandes, seulement
bornées par la taille de la mémoire centrale de la machine. Ceci évite
d'avoir à fixer les limites a priori, avant traitement ou entrée des
informations. Le tableau en liste grandit au fur et à mesure de l'arri-
vée des données c'est-à-dire au cours du traitement proprement dit.
Un graphe représente les relations d'un système. Il relie
par des liaisons orientées un certain nombre de noeuds. Ce graphe
peut être cyclique ou non. On définit en théorie des graphes la notion
d'arbre, qui est l'ensemble maximal des graphes terminaux ne contenant
pas de maille (fig. I.1.2)
»™ÎB«
- 6 - - 7 -
•* 7X
^
^
en pointillé lescordes restantes
fig. I.1.2
graphe arbre 1 arbre 2
Ceci permet une analogie simple avec les listes, car un
noeud peut être lié à plusieurs autres par une structure de liste
arborescente, mais nous verrons qu'il n'est pas interdit de faire
des listes cycliques. Si nous représentons les noeuds par une liste,
il est très possible de représenter les graphes terminaux des compo-
sants par des relations de liste à sous-liste, auxquelles peuvent
être associées la variable à travers, la variable aux bornes et la
relation entre ces variables.
liste propriétésnoeud e
liaison avecnoeud e
liste depropriétés
de a
liste noeud e
Liste noeud b
1liaison avecnœud a
liaison avecnoeud e
liaison avecnœud c
liât® de propriétésde b
. 1.1,3
Les relations aux bornes - à travers - leur relation interne - doivent
être liées aux liaisons d'accrochage, aux sous-listes, ce qui nécessite
une structure spéciale, permettant de stocker des données relatives à
chaque liaison (p. ex. chaque liaison suivie de 2 données la caracté-
risant) .
Les liaisons sont biunivoques, mais elles sont orientées, ce
qui permet de supprimer la moitié des liaisons pour représenter des
graphes orientés, ou de laisser subsister les deux liaisons ce qui
donne des graphes non orientés.
- Liste noeud A pointe vers Liste noeud B
- Liste noeud B pointe vers Liste noeud A
Cette représentation des graphes est la seule accessible
simplement au traitement digital, car elle permet les liaisons cycli-
ques et permet de rajouter ou de supprimer des graphes terminaux.
- 8 -
2 - HISTORIQUE CRITIQUE DES LANGAGES DE LISTES
Les principales sources de SLIP sont quatre langages et
procédés de traitement de listes antérieurs : FLPL ( FORTRAN compiler
list-processing language) par A. Gelerntner - IPL V (Information
processing language V) par A. Newell - Threaded lists par A.J. Perlis -
et un langage du même auteur : -J. Weizenbaum, KLS datant de 1962.
Un certain nombre de perfectionnements ont été par la suite apportés,
dont plusieurs sous l'influence directe de LISP. L'idée de "liste
d'espace disponible" vient essentiellement de IPL V comme d'ailleurs
certains sous-programmes ou fonctions sont analogues à des "J processes"
du même IPL V. Comme dans tous les systèmes de traitement de listes,
les positions de mémoires pour loger les données ne sont pas pré-
assignées. Elles sont fournies au cours du traitement du programme,
et non au moment de la compilation et du chargement. De plus, deux
cellules appelées consécutivement, pour loger deux données, ne sont
pas obligatoirement voisines. Comme la plupart des autres langages
de listes, SLIP permet l'exécution d'opérations récursives, c'est-à-
dire de fonctions s'appelant elles-mêmes. Ceci est possible grâce
à l'emploi de piles ou de listes auto-allongeables dont seule la tête
est accessible. Le but recherché n'apparaît pas toujours clairement,
à l'étude, car on se rend compte que SLIP étant un des derniers langages
à avoir été créés, il regroupe de nombreux perfectionnements, qui con-
courent à des buts différents. Une étude succincte des autres langages
de listes permettra de mieux se rendre compte de l'utilité de chaque
particularité.
- 9 -
2-1 - IPL V
IPL V paraît actuellement être un des langages les plus utilisés
aux U.S.A. Cfest vraisemblablement parce qu'il est l'un des plus anciens
langages de listes. Il est dâ essentiellement aux travaux de A. NEWELL,
TONGE, FEIŒIEBAtJM, GKEEN, MEALY, SHAW, SIMON.
Son expression par instructions directement interprétées par la machine,
est assez simple, car les fonctions de base ne sont pas très éloignées du
langage machine. Il gère les mémoires au moyen de piles et listes. Utilisé sur
IBM 7044, il conduit à une structure de mots du type :
Q LIEN SÏMB
Espace libre
Chargeur
structure identique à celle que nous utilisons pour SLIP sur 7094.
Lorsqu'un programme est chargé en machine, il reflète la structure suivante :
L'interpréteur chargé avant le programme,
comprend un interprète proprement dit,
qui reconnaît les expressions et les
exprime en fonctions de base en langage
machine, le stock de fonctions de
base, le moniteur, qui donne des rensei-
gnements sur le déroulement du programme
et les incidents, et le chargeur, qui
emmagasine le programme et les pro-
cédures utilisées qui ne sont pas
fonctions de base. Le reste est espace
libre, qui sera utilisé au cours du
traitement, ces mémoires étant allouées
uniquement à ce moment.
Interpréteur -, Moniteur
Ponctions de base
Interprète
La machine lit des instructions en liste qui sont, d'une part, le
programme écrit sous forme de liste, d'autre part des données sous forme
de listes à traiter. Les symboles figurant sur ces listes sont de trois
types :
- 10 - - 11 -
Symboles régionaux (R 3496 à la disposition du programme
Symboles internes à la disposition de la machine
Symboles locaux (9-1 ) servant aux connections éphémères.
P est le préfixe d' opération - Q le préfixe de désignation.
SYJffi contient un symbole ou un lien avec
LIEN contient l'adresse de la cellule
Exemple
de liste
de données
L1 '
S1
Nom
L1
9-1
S5
PQ
-*•
J177
Exemple
d'instructions
SYflB
S1
S5
S12
9-1
S7
A5
A12
S12
PQ10
20
11
20
• **
9-1
SXMB
L1
R1
WO
WO
R1W1
une sous-liste.
suivante ou une "fin".
LIEN
-*
0
0
A5
L'absence de lien est
un bien pour l'instruction
suivante
_, 7"* /
> /^ /A12
LIEN
0
L1 étant la liste
précédente
P et Q caractérisent les opérations à effectuer.
Le programmeur a accès à un registre de communication HO qui est
agencé en pile, c'est à dire où on n'a accès qu'au sommet. Les portions de pro-
gramme sont appelées procédures et agencées en listes, (fig. I.1.2.2.)
ProcédureJ77
9-2
9-1
PQ40
20
70
12
11
70
30
30
SYMB
wovo
J60
9-1
HO
WO
J2
9-2
WO
HO
Cette procédure teste si lesymbole (o) est sur la liste (l)
0 Fig. IJ.2.2.
Contrairement à LISP pur, IPL renvoie en "mémoire disponible" les
symboles (mémoires dont le programme n'a plus besoin. Ceci se fait par des
procédures (J71) qui renvoient les cellules en question dans la liste
d'espace disponible (H2). Le programmeur a la totale responsabilité de l'ef-
facement des listes devenues inutiles. Le renvoi de listes entières d'une
seule opération est possible. L'oubli de renvoyer des cellules inutiles
conduit à une diminution de l'espace libre potentiel restant.
Le rangement en mémoires auxiliaires est possible quand l'espace libre
est complètement utilisé. L'appel d'une liste déjà rangée déclenche son rappel
automatique.
Une particularité d'IPL est qu'il accepte les structures bouclées,
cycliques. Lorsque l'on veut toutes les adresses des mémoires de la structure
on utilise des marques, logées en tête de liste, qui préservent les symboles
locaux (têtes de sous-listes) et on les loge dans des piles, évitant ainsi
de passer plusieurs fois dans la même liste :
Seul
9-5 est ainsi autorisé.
9-1 est interdit. (— = transfert de contrôle).
Si le programme utilise des données, on les loge dans des termes de
données dont la zone P contient une valeur 0,1,2,3 suivant le type de donnée.
""& A-a"
- 12 -
Si la donnée est longue, on en fait une liste, de longueur quelconque dont on•4*OO"4* V»Q T *} "f*"! Y .testera la un !
s'écrira :PQ
Liste T1
9-1 21
9-2 21
9-3 21
se différencient par
TERME DE DON NEE
1 2 3
SITCB LIEN
0
IPL n'est pas un langage prévu9-2 ' pour le calcul numérique, aussi9-»3 0 interprète- t-il les symboles,TERME avant de leur affecter uneDE DON ;, ... .valeur, qu'il trouvera dans une
liste en correspondance avec les
symboles. Les termes de données
les contenus des zones P et Q (entier - flottant -
octal - alphanumérique) ce qui fait que la zone contenant la donnée elle-même
est tronquée et doit donc être d'un type spécial, uniquement traitable par
IPL. Ceci est évidemment plus long qu'en SLIP où les données peuvent très
facilement être des nombres. Les opérations numériques en IPL ne se feront
qu'après interprétation des symboles d'opération, et procédure de calcul,
car on ne dispose pas du support FORTRAN, analysant ces symboles et réalisant
automatiquement les opérations arithmétiques, grâce à son compilateur.
En IPL, pour représenter l'information, on la lie à un symbole en
utilisant les têtes de liste. On crée une liste de propriétés, un peu
analogue a celle de LISP et à la "liste descriptive" de SLIP.
Par exemple une distribution de bridge P A D 10 4
G R 6 3
K D V 10 3
T A 2
peut être représentée en liste, liste à laquelle on attache une liste de
propriétés donnant le compte de points, la place, la vulnérabilité.
(Fig. I.1.2.4.)
'ii*îs
1
9_"'";
*.*
ï/
|
3
1ia
*""?''y-
}-.^a'iJ
p*i
$S
1
I1;1
iiiî1i1ïi
iin.S
i-&
1&iÉît2mba
XI 9-1 9-1 0 fig. I.1.2.4
P A VOMB
P D N16P 10 VD13 Cette liste de propriétés est bien
P 4 NI liée a la tête de liste de cartes.
C R VPLA " sxiste des fonctions (procédu-
C 6 NSUD res * pour rechercher la valeur des
C 3 VUL
K D NON
K V
K 10
K 3
T AT 2 0
Les listes de
attributs de la liste. Le nombre
Q de points (16) est la valeur de
l'attribut VOMB de la liste XI.
La liste descriptive est elle-
même descriptible (tête de liste :
vide). Ceci est très proche de SLIP
données peuvent être bâties en structures, mais
ces structures ne peuvent pas être circulaires. Elles sont composées de
termes de données et de symboles locaux de sous-listes.
Les différents types de mémoires sont :
Tête de liste XI
Mémoire de liste 9-1
Mémoire de terminaison
Mémoire de rangement
Listes piles : ce sont
NOM SYMB LIENXI 0 9-29-2 S 2 9-3
9-3 S3 0
000 000 000 000
vide Al 0 0
contient B3 Al B3 0
des piles associées aux mémoires de rangement où
on vient emmagasiner en pile les symboles successifs, en ayant uniquement
accès à la tête de pile, c'est-à-dire la mémoire de rangement. On préserv*
par descente de toute la pile d'un cran. On restaure par remontée de tout<
la pile d'un cran. (fig. 1.1.9.5.)
NOM PQ
1) W3 vide
2) W3 — S5
2) Préserver
4) Bl — W3
5) Préserver
6) 01 — W3
7) Restaurer
VT3
SYMB
0
S5
35S5
BlS5BlBlS5GlBl35
Bl35
LIEN
0
0
0
0
0
0
0
fig. 1.1,2.5
Lors de l'exécution, 1!ordre normal des instructions est la
séquence, tant que l'on rencontre des symboles en partie SYMB. Si le
SYMB est le nom d'une procédure, on transfère le contrôle à cette pro-
cédure qui peut en faire autant et ainsi de suite jusqu'à ce que l'on
soit revenu au point de départ. On s'arrête seulement à une mémoire
de terminaison du programme principal. Cependant aucune différence
n'existe entre Programme Principal et Sous-programmes au point de vue
de la présentation.
Pour communiquer les arguments d'un programme à un sous-pror
gramme ou d'un sous-programme à un autre, le programmeur doit les mettre
dans des cellules de communication agencées en piles, dont l'utilité
est analogue à celle du commun en FORTRAN.
La récursivité est aisée, car au moment des appels de sous-
programmes les adresses de retour sont logées dans des piles et on ne
revient au programme principal que quand les piles sont vides. Les
programmes sont automodifiables, car des symboles peuvent être extraits
de données et placés dans la liste programme, permettant ainsi un aiguil-
lage en cours de traitement, car la structure des données et des program-
mes est similaire.
- 15 -
IPL apparaît donc comme un système très complet, rapide,
efficace car il utilise son propre interpréteur, permet des procédures
récursives, dispose d'une réserve constituée en liste qu'on peut res-
taurer et gérer au mieux. Il est le plus près des "listes" car les
programmes chargés sont agencés en listes, les symboles sont agencés en
listes, les données sont agencées en listes. Il est sûr, car la majo-
rité des zones mémoires sont agencées en piles ou listes. Il paraît
donc particulièrement adpaté à la manipulation des symboles, à la
recherche lexicographique, à l'apprentissage. Nous verrons que SLIP
s'est inspiré de plusieurs de ses mécanismes. On peut reprocher à
IPL l'absence de noms de procédures mnémoniques.
- 16 -
2-2 - LISP
Le langage de programmation LISP a été mis au point aux
alentours de I960 par l'équipe de Mac Carthy au MIT. Il a pour base
la description de calculs par des expressions symboliques. L'idée
primitive de listes, qui a permis son écriture repose sur des travaux
antérieurs de Newell, Simon et Shaw relatifs au langage IPL (Information
Processing language). Il a été utilisé à des travaux de manipulation
d'expressions algébriques : differentiation, intégration...
Il repose sur la notion d' "atomes1,1 analogues aux variables
définies en ALGOL, et sur celle de "S expression". Il représente com-
munément une liste par la forme avec parenthèses (A (B C) D) . Ses
fonctions de base sont car(x) et cdr(x) qui extraient d'une part l'atome
de gauche d'une S expression (x) qui n'est autre chose qu'une liste, et
d'autre part tout ce qui n'est pas l'atome de gauche.
Si X = (SI S2 SJ S4)
car(X) = SI et cdr(X) = (S2 S? S4)
cons(x,y) où x et y sont des S expressions x = fsi)et y = (S2 S3 S4)
cons(x,y) = (SI 32 S3 S4)
II repose aussi sur des prédicats
atom(x) qui est vrai si x est un atome,
faux dans l'autre cas.
eq(x,y) qui est vrai si x et y sont des atomes égaux«
faux dans l'autre cas.
Avec ces bases on construit des fonctions plus compliquées :
Par exemple : append (x, y) qui réalise (SI S2 S3 S4 S5)
avec x = (SI S2) et y = (S3 S4 S5)
qui s'écrira :
si x = null alors append = y
sinon cons (car (x), append (cdr(x),y))
ce qui est une fonction recursive et nécessite un compilateur adapté.
9.
it-1
mM
sS
mf
- 17 -
La représentation machine de ce langage se traduit par des struc-
tures de la forme
Ul D
B
(adresse) (A (B c) D)
où A, B, C, D sont des pointeurs vers les mémoires qui pour la machine
représentent A, B, C, D. Ces cellules contiennent donc des adresses machines,
qui sont extraites de la réserve. La réserve (free storage) est un tableau
de mémoires consécutives où on connaît l'adresse de la première non utilisée.
Ce sera elle qui sera appelée, ce qui fait qu'en LISP comme dans les autres
langages les mémoires voisines d'une liste ne sont pas consécutives en
mémoire.
Quand une mémoire n'est plus utile, on la renvoie mais elle ne
devient pas liée au reste de la réserve comme en SLIP. Ainsi quand la tota-
lité des mémoires sera épuisée-, on devra procéder à un ramassage des cellules
inutiles (garbage collection) pour récupérer toutes les mémoires disponibles
ramassage généralement suivi d'un tassement des mémoires utilisées.
Chaque atome est muni d'une liste de propriétés qui permet de loger
des renseignements et dont le pointeur est logé à la place du symbole. Une
extension de ce langage a été faite en ALGOL, ce qui a donné le LISP ALGOL.
Dans cette application, la réserve est constituée d'un double tableau
TCAR TCDR
-1 1 dont TCAR (l) + TCDR (l) formeront
un atome X :
car (X) —* TCAR —*• P1
élément XP1 P2P1 peut être une adresse
(pointeur) ou un symbole.
P2 pointe vers le prochain élément de la liste d'éléments.
- 18 -
Une fin de liote ou de sous liste se caractérisera par le fait que
son pointeur P2 qui pointera vers la mémoire 1
Une liste de propriétés se caractérisera par sa partie P1 égale
à -1. Si BC est un atome, sa liste de propriétés sera :
I >1 >
PCDir^teur vers l'atome BCr
-1—
^ B -J r 1 S.* *-> .jj u | ^t .La liste (A(BC,D)E)
se représentera
atomereprésentant A
atomereprésentant E
sous liste (BC,D)
atome représentant D
B
On commence l'exécution d'un programme par une procédure "préparer"
qui crée la liste de l'espace disponible, reliant entre elles les mémoires
libres, qui au départ sont contigues. Lorsque la place manque, par une
procédure "libérer" on peut raccrocher à cette liste disponible une ou
plusieurs listes devenues inutiles, ce qui a pour effet de les effacer mais
aussi de libérer les listes de propriétés et sous listes. Ceci correspond au
**••_
- 19 -
mécanisme de ramassage de cellules inutiles (garbage collection) de LISP 1.5
LISP ALGOL permet une évaluation aisée des formules symboliques ce qui lui
confère une supériorité certaine sur plusieurs autres langages. En
LISP 1.5 la liste de propriétés peut contenir la valeur numérique de la
variable. En LISP ALGOL on crée un tableau TREEL pouvant contenir les valeurs
numériques d'un certain nombre de symboles, directement lié au symbole. On
évalue la valeur d'une expression par un programme interprétatif, qui teste
les opérateurs et opère sur les valeurs TREEL liées aux symboles. Ceci est
réalisable en tous langages. La procédure est une proécédure recursive.
- 20 -
I - SLIP SÏMETRIC LIST PROCESSOR Langage de listes symétrique
SLIP est un langage de traitement de listes essentiellement symétrique
SLIP est un jeu de sous programmes permettant de traiter des mots machine de
façon à leur donner une structure de liste. La version initiale de ce langage,
mise au point en 1963 par J. WEIZENBAUM au M.I.T. et à la General Electric,
était un jeu de sous programmes en langage machine FAP, travaillant sur un
ordinateur équipé d'un compilateur FORTRAN. De manière à rendre ce langage
plus clair, et plus didactique, il .fut par la suite exprimé sous la forme
de sous programmes FORTRAN. Mais si ce mode d'expression, exprimé dans un lan-
gage hôte, est commode, il présente un nombre certain d'inconvénients, tels
pertes de temps et difficultés d'interprétation de données externes en COUTE
de traitement. On est donc logiquement conduit à penser qu'il est rentable
de construire un "interpréteur" SLIP, ce qui a été fait au U.S.A«, inter-
préteur qui traduit directement les instructions SLIP classiques en opé-
rations machine, et permet de manipuler concurremment symboles et nombres,
d'introduire des données, ou de traiter numériquement des formules calculées
symboliquement, ce qui était difficile avec SLIP FORTRAN.
1-1 - CARACTERISTIQUES FONDAMENTALES DE SLIP
La version la plus courante de SLIP, celle sur laquelle nous
avons travaillé, utilise un certain nombre de fonctions de base :
les "primitives". Ces fonctions primitives travaillent au niveau du
découpage machine des mots. Suivant que la machine utilise des mots
de 36 ou de 48 digits, que les mots sont découpés ou non, seules les
fonctions de base varieront.
L'ordinateur que nous avons utilisé, un IBM 7094, utilise des
mots de 36 digits binaires, découpés suivant le modèle suivant :
3 A 181921
digit designe AGD
- 21 -
Une zone d'identification ID digits de 1 à 3 avec ou sans digit de signe
Une zone décrément DEC digits de 4 à 18
Une zone index RX digits de 19 à 21
Une zone adresse ADD digits de 22 à 36
Ces zones ont été utilisées surtout les 2 premières et la 4ème
dans les fonctions primitives.
LSG (LNKL) liaison gauche (link left) est un pointeur vers la cellule
précédente
LSD (LNKR) liaison droite (link right) est un pointeur vers la cellule
suivante
ID identification est une marque donnant le type
de cellule.
Un mot SLIP est composé de deux cellules (un doublet) dont la
première contient en zone ID une marque, en zone LSG l'adresse de la
cellule précédente, en zone LSD l'adresse de la cellule suivante. La
seconde cellule est une cellule de donnée ou contient un compteur de
niveau, ou l'adresse d'une liste descriptive ou l'adresse de la tête
de liste dans le cas du suiveur (reader),
Différents types de cellules
Cellule normale
ID = 0
0 LSG LSD
Donnée
LSG pointeur gauche (précédente)
LSD pointeur droit (suivante)
Cellule de tête
ID _ 2
2
M
DERN
D L
SOMMET
CN
DERN pointeur gauche (précédente =dernière)
SOMMET pointeur droit (suivante =sommet)
M : marque de la liste ou des listes
DL : pointeur vers la liste descriptive
CN : compteur de niveau (accrochage de SL.
- 22 -
Cellule d1accro-chage
ID = 1
1 LSG
TETE
LSD
TETE
LSG-LSD pointeurs gauche et droit
TETE pointeur vers la sous liste SL
sous forme de nom de liste
Cellule desuiveur
ID = 3
3ADD.COUR
5ETB
PUT SUI
CN
ADD. COUR pointeur vers la celluleétudiée
PUT SUI adresse du mot suivant duchercheur
TETE pointeur vers la tôte de la listecourante
CN compteur de niveau (n° de l'étagede SL)
Nom d'une cellule ROM
Cellule de nomde liste
TETE TETE
NOM pointeur vers la cellule deliste NOM
TETE pointeur vers la tôte de liste
Cette cellule est le nom ou unpseudonyme
Construction de listes
SLIP permet de réaliser des listes symétriques en ce sens que
d'une cellule on peut se déplacer vers la cellule précédente jusqu'au
sommet, ou vers la cellule suivante jusqu'à la queue. Une liste se
présentera donc suivant la fig. 3
L(2)
L(3)
L(4)
i
3f
1
I ^
12 L(4) L(2)-
10 I L L(3>
i
0 1(2) L(4)-
10 L(3) T. •-JJ
6-
*J
fr-1
LA
Fig. 3
Une sous liste ne diffère en rien d'une liste. Elle est elle même
une liste. Tant qu'elle n'est pas accrochée à la liste principale,
ses différentes zones sont identiques. Une structure de liste, après
accrochage aura la forse suivante : (Pig. 4).
Une liste descriptive peut être accrochée à une liste (ou à une
sous liste) de façon à fournir un certain nombre de caractéristiques
(valeurs dépendant de certains symboles ou attributs. Une liste
descriptive peut contenir par exemple le symbole AGE et sa valeur 25,
le symbole FILS et le nombre 2. Elle est accrochée à la tête de liste,
de façon spéciale, qui permet do xffî pas la confondre avec les autres
listes, ce que sa structure ne permet pas, car c'est celle d'une
liste ordinaire (fig. 5).
Liste L
L2
L3
ACC
Liste L
- 24 -
2 14 L2 -
0 L 1 L3>t_
0 L2 ACC•—
TETE Sous liste LA
SOMMET
1 12
LA, — — t,
14 *-
,LA
2 LM LA2-
1
0 LA LA3..
0 LA2
compteur deniveau à 1(1 accrochage)
LA2
ACC QUEUE
LAS LA •
LA3
Chaîne SL peut avoir d'autresSL
Fig. 4
cellule L1
2 QUEUE
DL PI
^
SOMMET*
if•
^
,liti
Liste des
2 DL5 DL2 -
0 D _
ACE
LN J
. 5
- 25 -
Suiveur
Un suiveur (ou chercheur ou "reader") est une liste spéciale,
capable de suivre une structure, en descendant dans les différentes
sous listes, mais toujours capable d'en remonter, car le suiveur met
en réserve les adresses de retour. Le suiveur LCH pointant vers la
cellule LA (3) de la structure de la fig. 4 aura la structure
suivante : L liste principale LP
LA sous liste SL
LCH | . | .1 1
LA tête de S]L
T LA3
LA
LCPNT.
1
ACCL tête de LP
3 ACC
L
LCPNT 0
0
LCH2 pointeur vers la2èm8 cellule
CN = 1 : on est descendude 1 niveau
LCPNT = 0 pas de celluleaprès
CN = 0 liste principale
Utilisation des marques
II est possible de marquer une liste ou une liste et toutes ses
sous listes par un nombre de 1 à 7 en partie ID de la 2eo8 cellule du
doublet. Cela penset de reconnaître les sous listes accrochées à une
liste prJJicipale donnée, ou bien d'éviter de décrire indéfiniment
une structure bouclée
Sommet
2
H
QUEUE
DL
SOMMET.
i
H s Marque
- 26 -
La réserve
Un des avantages principaux, du traitement de listes est la post
désignation de l'adresse d'une cellule, en ce sens que la cellule N de
la liste L n'est connue que par le nom H$ l'adresse véritable d@
la cellule (doublet) n'est fixée que quand on l'utilise pour la
première fois, à sa création. N contient alors son adresse. Il faut
donc disposer d'un certain nombre de doublets disponibles, ce qui est
réalisé par ce que l'on appelle "Liste d'espace disponible" (List
of available space. LAVS). C'est une zone réservée en début de pro-
gramme, agencée en liste simple, non symétrique de telle façon que
toutes ces cellules de la réserve soient liées entre elles. On peut y
accéder par une cellule mise en "coaaun" CHEF "cellule de référence"
AVSL (Available space link) qui contient l1'adresse de la première et
de la dernière cellule de la réserve
c(D 0(2} C(H)
CHEF
Lorsqtffl l'on désire utiliser une cellule, o'est à dire la prendre
à la réserve, on "décroche" la première cellule de LAVS et on donne à
CREF l'adresse de la suivante C(2) au lieu die C(l). Ainsi CHEF pointe
toujours vers les extrémités de la réserve. Cette réserve doit avoir
des dimensions suffisantes sous peina d'arrêt du traitement, ce qui se
fait avec impression d'un diagnostic. Toutes les cellules (tête de
liste - accrochages - cellules courantes — suiveur - description list)
y étant ainsi prélevées.
i
3
1%
i. w
Pour pallier cet inconvénient, on renvoie en réserve les cellules
dont on n'a plus l'usage : listes devenues inutiles, listes des-
criptives sans symboles j suiveur dont le travail est terminé, cellule
d'accrochage dont la liste a été renvoyée .... Pour réaliser ceci, on
accroche en queue de réserve la cellule en question (ou les cellules
en liste) et on eodifie le pointeur gauche de CREF. On remarque en
effet que le LSD des cellules de la réserve contient l'adresse de la
cellule suivante, de même que celui d'une cellule d'une liste contient
l'adresse de la cellule suivante. On peut ainsi renvoyer en réserve
en une seule fois une liste entière dont les cellules seront liées. Il
suffit que la précédente queue de réserve pointe vers le sommet, et que
CHEF pointe vers la queue de liste dont on aura précédemment annulé
le LSD. On obtient facilement les adresses de la queue et du sommet
qui sont toutes deux en LSG et ju,J) de la tête de liste.
Renvoi des sous listes entières
Nous avons vu qu'il existait dans la cellule donnée des têtes de
listes, une zone intitulée compteur de niveau (Level counter). Cette
zone garde trace du nombre d'accrochages de chaque liete, c'est à
dire du nombre de fois qu'une liste donnée est faite sous liste d'une
autre liste. Ce compteur de niveau croît de 0 à N. Il sert essentiel-
lement à savoir si une liste (sous liste) est utilisée à l'instant
considéré. Puisqu'il faut disposer du plus grand espace disponible
possible, on a intérêt, si une liste n'est plus utile (c'est à dire si
son compteur est à zéro (O)) à la renvoyer en réserve0 A chaque fois
qu'une sous liste d'une liste devient inutile, on la renvoie en ré-
serve par un sous programme appelé IEFLST qui diminue son compteur
de 1 et renvoie la liste si le compteur est à zéro, renvoyant aussi
la tête de "liste descriptive" si elle existe. Il est possible de
renvoyer uniquement le corps de liste par un sous programme MTLIST
ainsi que de renvoyer la "liste descriptive" par une fonction IRADLS.
- 28 -
II n'existe pas de sous programme standard permettant de ren-
voyer -une structure entière en réserva, mais ceci est aisément pro-
grammable. Cependant ce problème se pose rarement, car il est plus
souvent question d'augmenter la taille d'une liste ou d'une structure,
que de l'effacer. Cependant, quand une structure devient globalement
inutile on renvoie le corps de la liste principale en réserve (par
IEPLST) on renvoie la tête de liste descriptive si elle existe, et
on renvoie la tête de liste (car liste principale —£ compteur de
niveau = C-). Les cellules d'accrochage se trouvent donc dans la réserve.
Quand on a besoin de nouvelles cellules on les teste au cours de
l'appel par RCELL. Si la cellule contient le nom d'une sous liste, on
applique à ce moment la procédure IEPLST à la sous liste en question
et ainsi de suite.... ce qui résout le problème de l'effacement d'une
structure»
1-2 * DESCRIPTION DU SÏSIEHB - LES PROCEDURES
SLIP FORTRAN offre la possibilité de faire des fonctions ou des
sous programmes qui utilisent les fonctions de base, puis qui utilisent
les fonctions déjà écrites, ce qui simplifie considérablement le travail
de l'opérateur, qui par une simple instruction d*™* le programme
principal peut réaliser une suite très compliquée d'opérations plus
simples.
1-2-1 - Fonctions primitives
Permettent d'extraire une partie du contenu d'une cellule
ou de loger cette partie dans une cellule
L = LSG (A) : contenu de la partie décrément de la cellule A
placé en partie décrément de L
L « LSD (A) : contenu de la partie adresse de la cellule A
placé en partie décrément de L
L = ID (A) : contenu de la partie préfixe de la cellule A
placé en partie décrément de L
Z = CONT (L) : contenu de la cellule dont l'adresse est en partie
décrément de la cellule L placé dans la cellule Z
LA « INHALT (L) :même fonction, mais de type entier au lieu de
flottant
INTRDD (NAfL) place le contenu de la cellule NA dans la cellule L
INTRDI (NA,A) place le contenu de la cellule NA dana la cellule
dont l'adresse est en partie décrément de A
INSDIR (D,N,M,CELL) loge D en partie préfixe (iD)
N en partie décrément (LSG)
H en partie adressa (LSD)
de la cellule CELL
INSIND (D,N,M,A) loge les mêmes quantités dans la cellule dont
l'adresse est en partie décrément de la cellule A.
Pig. I.2.1
L » ID (CELL)
H « LSG (CELL)
H B LSD (CELL)
A
B « COHT (A)
A
(Cf Dy B, A)
Appel IKSDIR (C, D, B, CELL)
B
CELL > t A
Fig. 1*2,1.Appel IHTRDD (B, CELL)
Appel INTRDI (B, A)
Dans ces deux derniers sous-programmes, le fait de remplacer
une des données par -1, laisse intacte la partie correspondante.
INSIND (-1, -1, M, A) ne modifie que la partie adresse.
Ces particularités d'écriture sont dues au langage FORTRAN et à la
méthode des listes. Lorsque l'on fait INTRDD (NA, L) NA représente
la donnée logée dans la cellule que le compilateur a attribuée au
symbole NA. D'autre part, une liste dont on connaît la structure
n'est localisée que par son nom, ou le nom de ses cellules, qui ne
sont pas des cellules de la liste. (Fig. I.2.2)
- 31 -
Les ordres LA = LISTE (9)
LB = NVQU (Dl, LA)
réalisent L Add LA-...-I ...
LA.,..!
^ 2
0
1I
1
ID1
Pig. 1.2.2,
où LA est une cellule connue, identifiée à la compilation qui
contient l'adresse de la tête de liste sous forme de nom de liste^
adresse inconnue du programmeur, car fournie au cours du traitement.
De même pour LB qui contient l'adresse de la cellule accrochée à la
tête de liste, dont la cellule"donnée"contient Dl.
>2-2 - Création de la réserve. Liste d'espace disponible
On dispose au départ de la procédure d'un bloc de mémoi-
res contenant zéro, dont on connaît les adresses extreœas.
Sans modifier l'implantation de ces cellules (ce qui est
physiquement impossible) on va les lier entre elles, en une
liste non symétrique par groupes de 2.
Etat Initial
I l
II AddfTT 1
AddA
1 * J v iL | OOOOOC] | | || |Ad4 F |
P IB o
| Add | | II Add CC B A,
1
jàdd B
t
CHEFPic I.2J2.1,
Jtë£:~&&LJsï&&i™s^
et on crée une cellule spéciale CHEF (cellule de référence) qui
contiendra les adresses des deux extrémités de la réserve (premier et
dernier doublet). C'est au sous-programme INITED qu'échoit ce travail,
Ce sous-programme crée en plus 100"listes publiques"vides, (100
doublets de la forme2 1 ! T
qui pointent vers leur propre adresse, mais dont les noms
AddA Jpointent vers les cellules créées et se trouvent dans la partie
commune de la machine (COMMUN) référencés de X(l) à X(lOO)). Ces
listes spéciales sont celles qui plus tard serviront à loger et
récupérer adresses et paramètres dans les traitements récursifs.
Appel d'un doublet - utilisation de la réserve
Quand le programme a besoin d'un doublet, il le demande à la réser-
ve, qui lui fournira l'adresse de la queue de réserve.
Soit N = NUCELL(Z) N prend comme valeur l'adresse de la der-
nière cellule de la réserve, connue grâce à CHEF soit A
\AddA [—_»_.±, — . J f«La réserve doit alors remonter d'un cran, et c'est CREF qui prendra
en partie adresse l'adresse contenue dans A soit celle de B. A est
ainsi utilisable et on connaît son implantation en machine. NUCELL
n'est pas appelé directement, mais par l'intermédiaire des fonctions
LISTE, IMMDRT, IMMGCH.
Création de listes (Têtes de listes)
Quand on veut créer une liste, on appelle une cellule par la fonction
LISTE : LA * LISTE(9)
LISTE appelle une cellule par NUCELL et donne son adresse à la fonc-
tion. Cette adresse est mise sous forme de nom de liste dans IA
LA AddA AddA
et la cellule A devient tête de liste vide.
S$
1
*ta®
- 33 -
Si on appelle LISTE (IB) au lieu de LISTE(9) la liste sera
ineffaçable c'est-à-dire qu'on ne pourra pas par la suite la ren-
voyer en réserve car elle contiendra en partie adresse de la cel-
lule de donnée un 1. Son compteur de niveau sera al. De plus
IB sera aussi nom de la liste (pseudonyme). On aura alors
IB M—t-
2 i l *
fig. I.2.2.2
-2-3 - Création de listes - introduction des données
IMMGCH - IMMDRT
Ces fonctions rajoutent à droite ou à gauche d'une cellule
d'une liste, ou de la tête de liste (vide ou non) une cellule, dans
la donnée de laquelle on peut mettre un nombre, une adresse ou un
symbole. Ceci soulève tout de suite le problème de l'uniformité des
données. Toutes les données doivent appartenir à la même catégorie,
sous peine d'avoir à identifier chaque cellule. Soit la liste LA
comprenant deux cellules LA(2), IA(3). Rajouter une cellule entre
LA(2) et LA(3) se fera par appel de :
IMMDRT(D, LA (2)) : immédiatement à droite de LA(2) ou
IMMGCH(D, IA(3)) : immédiatement à gauche de LA(3)
avec D « donnée. On aura donc
* IA3 IA2*LA
LA(2)
IA(3) * LA2
9 IA
XLA3*.
LA
IA(2)
0 LA3 LA2 *i
IA
LA Nouvel IA2 LA3
LA O; NOUVB LA
Fig. I.2.3.
X -i Ws.Uw s- ^ i' E-r" ^ 1'- -' ™' ^ !-'1'"; M'X&.-l.^tvlffhnls- wii.iBiB îîrùi,. »!1!,» » ™,*, 4 »«**V" '™J*"'*'*Ï^ ..rtl aV *; ;*, !»™''"' ^ *rt'™™™A ,i*!.fflJ|lj»s..' ' .ï-jW •-••nj- ..s...-^ ..
Des fonctions NVTT, NVQU (nouvelle tête, nouvelle queue) réalisent
la même opération en tête ou en queue de la liste.
1-2-4 - Substitutions
SUBST, SUBSTT, SUBSQU permettent de substituer à la donnée
existant dans une cellule, une nouvelle donnée, la fonction prenant
comme valeur l'ancienne donnée.
Ex. : NV = SUBOTT (Dl, LA(2))
Si l'ancienne donnée était D on aurait NV = D et Dl serait la donnée
de la cellule LA(2).
Insertion d'un corps de liste dans une liste
Des fonctions INLSTD, INLSTG insèrent dans la liste dont A est une
cellule, à droite ou à gauche de A, le corps de la liste M, rendant
M vide - la fonction prend comme valeur M. La liste de A est donc
rallongée de la longueur de M.
Division d'une liste - détachement d'un groupe de cellules
Les fonctions NULSTG, NULSTD enlèvent à la liste L toutes les cellules
à gauche ou à droite de la cellule A (tête non comprise) et en font
une nouvelle liste dont le nom est donné par la valeur de la fonction
Avant
NV
NV
NULSTD(A,L)
NOUV
Apres
NOUV
Fig. I.2.4,
Ces fonctions prennent comme valeur le nom de la nouvelle
liste des cellules détachées.
i*i E ^ kài v .i!LW ^-t^^^^ffi^^.;^ j-y pi • v j»f ' - ri ''-^r: ''' s-1.- -- - ^ : S ^ ^ i i
Changement de mode
Le FORTRAN entraîne un certain nombre de contraintes, dues à la
dénomination des symboles, flottant en entier. Les fonctions com-
mensant par une lettre de I à N sont du type entier. Les autres
du type flottant. On ne peut donc réaliser :
NV = CONT(LA(2))
CH = LSG(LA(2))
On a créé pour cela deux fonctions REEL(R) et INTGER(l) qui sont
des pseudo opérations, n'affectant en rien la valeur de leur para-
mètre qui devient valeur de la fonction. On peut ainsi écrire
NV = INTGER(CONT(LA(2)))et
CH = REEL(LSG(LA(2)))
INTGER prenant la valeur CONT(LA(2)) et REEL celle de LSG(LA(2)).
1-2-5 - Renvoi de cellules en réserve
C'est le processus inverse de l'appel d'une cellule par
NUŒLL. L'ordre des cellules dans la liste d'espace disponible a
été modifié car de nombreuses cellules ont été appelées et sont donc
liées les unes aux autres, de façon assez complexe, mais ont toujours
les mêmes emplacements en machine. La réserve n'est pas vide.
CHEF pointe toujours vers F
rT-VrS [
OOOJ
I I
,L_L_l
H
I I I LU
I I I LUh-F
première collule disponible
CHEF
""Ô'srf f4 , i™ak
Supposons que l'on veuille renvoyer la cellule K, connue par son
nom NK | Add K On écrira Appel RCELL(NK). Cette
fonction va faire de K la dernière cellule de la réserve se substi-
tiant à F. Pour cela on va mettre 0 dans K (annuler ses liens) et
faire pointer F vers K (car on connaît l'adresse de F par CREF)
K
Add K | CREF va être modifié et pointer vers K lui aussi
fig. I.2.6.00000 CREF Add K •—
K a donc bien été détaché de la liste où il figurait, et accroché
en queue de réserve. Mais la fonction RCELL est peu utilisée direc-
tement; par contre elle est très utilisée indirectement :
ELIM, EJTT, EJQU réalisent cette opération mais préservent
la continuité de la liste, en liant les deux cellules voisines de NA.
De plus, elles prennent comme valeur la donnée de la cellule renvoyée.
Elles testent aussi NA pour voir si ce n'est pas une cellule de tête,
ne la touchant alors pas.
Appel ELIM(NA)NVNANT
r .
p
0 N H
N A
NAHéserve
£1
NVNT
1,1
b t
I 0
Pig. I.2.7.
La fonction MTIZST renvoie à la réserve le corps de la liste
si la liste n'est pas vide. Elle prend comme valeur le nom de la
liste. Si la liste est vide MTLIST prend la valeur zéro.
La fonction IEFLST que nous avons déjà partiellement étudiée,
utilise MTLIST pour éliminer le corps de liste. Si le compteur de
niveau de la liste descriptive est à zéro, elle élimine aussi la
tête de la liste descriptive puis la tête de liste LA si son compteur
est aussi à zéro. Le corps de liste descriptive sera éliminé ultérieu-
rement.
La fonction IEFCH efface la totalité du compteur de niveau.
La fonction IRADLS efface la liste descriptive L et met
son pointeur à zéro, grâce à la fonction MTDLST qui élimine le corps
de la liste descriptive. .
Dans cette procédure de renvoi de listes en réserve nous
n'avons pas parlé des sous-listes. Lorsqu'on renvoie en réserve
une liste principale (dont le compteur est à zéro sauf si elle a
été faite indestructible) celle-ci peut avoir de nombreuses sous-
listes, qui lui sont accrochées grâce à des cellules d'embranche-
ment, ppi nLÎT: H" LBf
1 1— Sous liste LBCes cellules sont aussi renvoyées avec les autres. Mais dans la
fonction NUCELL existe un processus de renvoi des sous-listes :
Lorsqu'on appelle pour l'utiliser, une cellule qui a été renvoyée,
et qui soit une cellule d'embranchement, on applique la fonction
IEFLST à la sous-liste dont le nom est dans cette cellule. La
sous-liste sera donc renvoyée elle aussi à ce moment, si son comp-
teur de niveau n'est pas supérieur à 1 et ainsi de suite. Pour
éliminer le corps de liste descriptive on utilise aussi cette pro-
priété, en créant une cellule d'accrochage qu'on renvoie en réser-
ve, avec en nom de liste l'adresse de la première cellule de la
liste descriptive.ai
ID
II existe donc de nombreuses fonctions permettant de ren-
voyer des cellules à la réserve, évitant ainsi son épuisement, qui
serait détecté lors d'un appel de cellule et signalé par un message.
Ceci est une des supériorités de SLIP sur beaucoup d'autres langages
qui nécessitent un ramassage volontaire des cellules inutiles, recher-
chant toutes les cellules non utilisées à ce moment. Cette opération
est en général suivie d'un tassement des cellules utilisées en tête
de réserve. Ces opérations coûteuses en temps machine nécessitent
une interruption gênante du processus en cours. De plus SLIP est
un des rares langages permettant de renvoyer un corps de liste entier
en réserve en une seule opération. Par ailleurs, il est possible
d'utiliser au maximum les dimensions de la machine en utilisant
un programme particulier de création de la réserve qui lie toutes
les mémoires disponibles après chargement, que nous étudierons dans
un prochain chapitre.
- 38 -
1-2-6 - Le mécanisBta du suiveur
Le suiveur/, ainsi que nous l'avons vu, permet de descendre
et de reiBonter dans une structure donnée, de rechercher dans l'une
quelconque des branches une certaine donnée, de s'arrêter dans une
structure connue à une place bien déterminée.... Il est créé par
une fonction LCETCH qui en fait un doublet chercheur vide positionné
en tête de liste. LCH » LCRTCH (L)
On peut le faire avancer de différentes manières, à droite
ou à gauche, chaque fonction ayant l'une ou l'autre option, linéai-
rement ou structurelleraent, pas à pas, niveau par niveau.
L'avance structurelle permet de se rendre compte de la forme
du graphe représentant la structure. En effet, un arrêt à chaque
embranchement permet de connaître les résultats de l'exploration :
La valeur de la fonction est le contenu de la cellule explorée
(adresse de la sous-liste suivante). Le contenu du compteur de
niveau du suiveur penset de connaître le niveau exploré. La valeur
d'un des deux paramètre de la fonction, A, permet de savoir si la
structure est terminés. Grâce à une boucle et à quelques impressions
intermédiaires, on peut donc décrire la structure que l'on aura par-
courue de la façon suivante : EMB - AVSND (LCH,A)
L DEBUT
LA
1) LCH pointé sur L niveau 0 A « 0 3oùn-llst« néant
2) "
3) "
4) "
5) "6) n
7) "8) n
n
n
tt
n
n
n
n
n 2
« 5« 4H 5n 6» F
n
n
n
n
tt
n
n
0 A
1 A
2 A
1 A
0 A
1 A
0 A
0
0
0
0
0
0
n
n
n
n
n
n
- 39 -
L'avance structurelle pas à pas (en sautant les cellules d'embranche-
ment, AVSED, ou en ne les sautant pas, AVSMD) permet de rechercher une
donnée ou un symbole dans une structure, car la fonction prend comme
valeur la donnée de la cellule où elle s'arrête.
Au cours de l'avance linéaire, un mécanisme exactement analo-
gue est mis en jeu, à la différence près que l'on reste dans une liste
donnée sans descendre dans ses sous-listes, ce qui ne justifie pas
l'existence d'un suiveur*
Les critères d'arrêt du suiveur sont fournis dans les deux
cas par des paramètres que l'on donne à la fonction : AVS (LCH, PI, P2)
1-1 : pour arrêt sur les embranchements
0-0 : pour arrêt sur toutes les cellules sauf embranchements
1-0 : pour arrêt sur toutes les cellules
Le suiveur peut être remis à l'état initial par la fonction
INITCH qui le renvoie en tête de la liste courante dans laquelle
il est arrêté. Le suiveur augmente d'une cellule à chaque fois qu'il
descend d'un niveau dans la structure. On lui rajoute une cellule
en tête, toutes les autres descendant d'un cran : il est analogue
à une pile car on ne connaît que l'adresse de la dernière cellule
appelée.
Etat A *
niveau
LP : L
2
3 UB
LB
« —
2
3 NA
LA•
1
é-i
L SL1: LASL2 :
T LA SL3 :i . , ,
LBLC
3 NL 0
^
I I »
Cellule S2
' Cellule S3
I
Etat B
HA LB
MB
(A)NC
(B)
LC
5 NCLC
*•—
3
k KBLB
» .-.. '
2
5 HALA
« —
1
5 NL 0
JsC€
^
nivelleîllule
17SD (LCH,JtK)
Entré»
£ = contenu du cuiveurLCT = adressa couranteCAHD m contenu cellule courante
ID (CARD) i 1
LCP » adresse cellule suivanteCAKD = contenu cellule LCPMettre LCP en déc. de D
ID (CAM)
ID (CAHD; : » j
ID (CAND) t K
ID (CAMD) :
Appel Nuoell > MMettre le contenu de D en MContenu de LCH-1 en K-1En LCH-1 nettre l'adresse do latête de la sous liste etaugmenter le niveau de 1En D mettre l'adresse de lanouvelle cellule en partie add.CAND = contenu de la tête de SL
1LK = adresse de la cellulesuivante du auiveurD = son contenuMettre le contenu de LK-1dans LCH-1CAND » contimu de l'eabran-cheœnt précédentrenvoyer LK
Compteur niveaudu suiveur : 0
AVSD * -1.
AVSD
LCH = contenu de D
PUT . I 2
PRESENTATION DES FONCTIONS D8 AVANCE ET BU MECANISE DU SUIVEUR
PROGRAMME PRINCIPALPONCTION AVLD (LCH,JfK) AVANCE LINEAIRE DROITE
CREATION DU SUIVEUR LCH
Entrée
CLCH = Contenu du suiveur
LK *= adresse de la cellulesuivant la cellule courante
CAND = son contenu
CLCH pointe vers cette celluleLK en LS6 de CLCH
ID (cette cellule) : 2
v /ID (cette cellule) : J
II) (cette cellule) : K
\ /
AVLD = 0. AVLD s -1.
Suiveur = CLCH
ÎTN
KLg. I 2 3 2
PRESENTATION DES FONCTIONS D'AVANCE
DIMENSION X(100 ) ,LAVS(2 ) ,LETTRE(36 ) ,MOTC216)COMMUN C R E F , X , L A V SAPPEL INITEDLIRE 122tBLLIRE 1,LETTREIMPRIMER 2tLETTREAPPEL SFPARE(LETTRE,MnT)APPEL FLSTP(MCT,LA)APPEL IMPLST(LA»AtAtA,A)LCH=LCRTCH(LA>IMPRIMER 14
8 SYMB=AVSEO(LCH,A)IMPRIMER 11,SYMBSï«A)7,8,7
7 LCH=LCRTCH(LA)IMPRIMER 15
10 EMB=AVSND(LCHtA)IMPRIMER 13,EMBSI(A)3,10t3
C RENVOIE LE SUIVEUR EN TETE DE LISTE3 LCH=LCRTCH(LA)
IMPRIMER 126 EMB=AVLND(LCH,A)
IMPRIMER 13tEMBSI(A)5,6,5
5 APPEL INITCH(LCH)IMPRIMER 100
4 SYMB=AVLED(LCH,A)IMPRIMER lltSYMBSICA)9,4f9
9 APPEL EXIT1 MODELEU2A6)2 MODELE(lHl,5Xf21HSTRUCTURE DE LA LISTE,///»4(5X,1lA6t//))100 MODELE(lHl,5X,5HAVLÊDf11 MODELE(5X,9HSYMBGLE= ,12 MODELE(1H1,5X,5HAVLND)13 MOOELEUHOt 5X,25HN(1M DE LA LISTE SUI VANTE=,012)14 MODELEClHl ,5X f5HAVSED,/ / )15 MODELE(!Hl,5X,5HAVSNDt//)122 MODELECQ12)
v l t O , C,0,0,1,0,0,1.07Ct0,0,0)
Pig I 2.3.3
STRUCTURE DE LA LISTE
IMPRESSION DE LA STRUCTURE SOUS LA FORME EN ARBRE
(A l ,B l ,CHA2,B2(AMI ,MOT(ANTOINfE»NUU02)El<NOELtFIN))
LA=077315077315 LB=000000000000 LC=000000000000 LD=000000000000 L£=000000000000
2772*5077313
077315077311
077313077307
077311077303
177307077251
000000000000
210160606060
220160606060
230160606060
077305077305
AI
B1
CI
277253077301
077305077277
077301077273
177277077253
000000000001
210260606060 A2
220260606060 B2
077275077275
277255077271
077275077267
077271077263
177267077255
077273077305
077303077245
177251077315
250160606060 El
C77247077247
277241077243
077247077241
077243077247
077263077275
240260606060 D2
000000000001
454625436060 HOEL
263145606060 FBI
000000000001
214431606060 iKL
444663606060 MOT
077265077265
277257077261
077265077257
077261077265
456443606060 HDL
000000000001
214563463145 AHTOIH
256060606060E
Fig I 2.3.4
RESULTATS DU TRAITEMENT
FONCTION AVSED (LCK,A) FONCTION AVSND (LCH.A)
SYMBOLE*
SYMBOLE- Bl
SYMBOLE* Cl
SYMBOLE* A2
SYMBOLE* B2
SYMBOLE* AMI NOM DE LA LISTE SUIVANTE=077305077305
SYMBOLE* MOT NOM DE LA LISTE SUIVANTE=077275077275
SYMBOLE* ANTOIN NOM DE LA LISTE SUIVANTE=077265077265
SYMBOLE* Ë NOM DE LA LISTE SUIVANTE=077247077247
SYMBOLE* NUL NOM DE LA LISTE SUIVÂNTE=601400000000
SYMBOLE* 02
SYMBOLE* El
SYMBOLE* NOËL
SYMBOLE* FIN
SYMBOLE* 0000
FONCTION AVLED (LCH,A) FONCTION AVLND(LCH,A)
SYMBOLE* Al
SYMBOLE* Bl NOM DE LA LISTE SUIVANTE*077305077305
SYMBOLE* Cl NOM DE LA LISTE SUIVÂNTE=077?.470772A7
SYMBOLE* El NOM DE LA LISTE SUIVANTE=601400000000
SYMBOLE* "0000
Fig I 2.3.5
jjjLiu".i ^
- 40 -
La rencontre d'une fin de liste (ID de la cellule suivante = 2)
est un critère d'arrêt si le compteur est à zéro. Sinon, le sommet
de la pile est renvoyé en réserve et l'on remonte d'un niveau dans la
structure.
Exemple de fonctionnement : fig. 1.2.33 - 1.2.34 - 1.2.35 -
Organigrammes, listings fig. 1.2.31 - 1.2.3.2
1-2-7 - La récursivité en SLIP
SLIP FORTRAN possède une faiblesse en rapport avec sa plus
grande généralité : la difficulté de traitement de fonctions ou de
sous-programmes récursifs. En effet FORTRAN, de par ses règles
propres ne permet pas qu'un sous-programme s'appelle lui-même.
Le programme doit donc tourner cette difficulté en utilisant un sous-
programme intermédiaire qui est une pseudo-opérâtion, seulement des-
tinée k appeler le sous-programme de base. Un exemple nous facilitera
la compréhension du problème. Soit à calculer : N !
Comme N ! = N.(N-l)! avec 1 ! = 1. c'est un exemple typique de trai-
tement récursif bien que c'en soit seulement un exemple restreint,
l'appel récursif se faisant seulement au premier degré. Le sous-
programme de calcul de factorielle N calculera donc factorielle (N-l)
et la multipliera par N, ceci Jusqu'à ce que N-l = 1, dont la facto-
rielle est 1. Le schéma du traitement sera donc le suivant pour
N =:4
Programme principal i > Fonction FACT(N),
ïZ = FACT(4)—
FIN
APPEL FACT(N-l)
FACT = NxAUX
AUXJ
avec un intermédiaire dans la boucle supérieure : la pseudo-fonction
FAC(N). L'appel du sous-programme se fait par l'instruction FAP
TSX $FAC,4 qui transfère le contrôle à FAC et met en réserve en RX4
le contenu du compteur ordinal, c'est-à-dire la position de mémoire
que l'on quitte. Dans les boucles, ces opérations étant faites plu-
sieurs fois, il faut garder en mémoire dans une structure spéciale,
toutes ces adresses de retour. La première boucle se fait par un
- 4l -
appel indirect du sous-programme FACT et ceci Jusqu'à ce que le
test sur N fonctionne.
PP
TSX $FACT,4
TSX N
SOR Z
rFACT SXA m, 4 «f
Appel PARMT3 rt FAC SXA MGA,4
Si N> 1 TSX $FACT,4
TSX $FAC,4 Ezz-* TSX N-l
TSX N-l SOR 1BX _<_ TRA 2,4 =
SOR AUX fE -
Appel RESTR3
Sinon FACT(N) = N x FACT(N-l)
TRA 2,4 transfert en (gg) + 2
Transfert en (HGA) + 2
La seconde boucle est plus compliquée à réaliser. Si l'on ne met
pas (RX4) en réserve, elle se fera indéfiniment car la dernière valeur
de RX4 dans FACT est l'adresse de FAO, et celle de RX4 dans FAC est
l'adresse d'appel de FAC par FACT. Il faut donc, dans FACE mettre
les différentes valeurs de RX4 en réserve et les récupérer ensuite,
de façon à trouver au bon moment l'adresse de l'appel par le programme
principal, ce qui permet de suivre les flèches dans le bon ordre.
Il faut de plus mettre en réserve les valeurs de N et de N-l
de façon à pouvoir appeler FACT (N-l) et faire 1*opération
FACT(N) = N x FACT(N-l)
Cette mise en réserve se fait dans des listes spéciales,
ineffaçables que l'on peut appeler en tout point, car leur adresse
est mise dans le "COMMUN". Ces mises en réserve se font par les
sous-prograssnes PARMTn (A,B N) qui ajoutent en tête des listes
W(l), W(2) W(N) les paramètres à conserver (ces listes sont en
quelque sorte des piles). La récupération des paramètres se fait de
la même façon, en renvoyant en réserve les têtes de liste, après avoir
récupéré les données de ces têtes de liste, par le sous-programme
KESTRn (A, B N). L'exemple traité permettra de suivre aisé-
ment cette opération. Fig. 1.5.1 - 1.5.2 - 1.5.3 - 1.5.4
£^
CALCUL DE PACTOKIELLBS
PROGRAMME PRINCIPAL
C A L F A C CALCUL DE FACTORIELLE N
DIMENSION XdOOl ,LAVS(2ICOMMUN C R E F , X , L A V S FACAPPEL INITED
3 LIRE ItNIMPRIMER 10, NZ = F A C « N )IMPRIMER 2,N,ZALLER A 3
1 MDDELEU3)2 MODELE < 1HO, 10X, 1 2HFAC TORI ELLE (,I 2, 2H1-.1 4, / / /)10 MODELE(1H1,23H CALCUL DE FACTORI ELLE< ,12 ,1H1 ,/f /l
F IN(1, 1,0,0,0,0, 1,0,0,1,0,0,0,0,0)
AA
Fig. I. 5. 1
AE
SOUS PROGRAMME FACT
SQL'S PROGRAMMÉ F A C T ( N ) MG
SOUS PROGRAMME F A C T ( N ) UNAPPEL F/VC(N) AUX
IMPRIMER. 1 AUXN1 MODELE (1 OH INTERLUDE? .^VMI
RETOUK AUXM1
f ïN ( l , l tO tO»0 ,0 , l , n ,0 , l , 0 ,0 ,O tOtO)
Fig. I.5.2
?
•
SOUS PROGRAMME PAC ;
COMPTENTREESXARADcnRO w 1 \
RADSRARADSORRADSORSSTSORTEDTSXTSXTSXTSXRADTZETSXTSXTSXTSXT S XTSXEMQMONDAGSORTEDRADEEX•** r~\ ATRAOCTBCSBCSU \v \i*r
BCSFIN
Fig.
40FAC
5( IMP) ;7 lc.
1 » A
AA !
UN :
AUX##AUXNUNAUXMl=HAUXM1$ P A R M T 3 » 4MGAUXNAUXMlAUXMlAE$ F A C T » 4AUXMl$RESTR3»4MGAUXNAUXMlAUXNf \ V^ f\ ' '
AUX17AUX= HAUXAUX
2à
>400000100000011JL1
1.5.3
CALCUL DE FACTORIELLES
AUXMl ( 01*000004000000* 0.00229588E-38077400465264 000005000000 000004000000 AUXMl (077400473512 000004000000 000003000000
AUXMl ( 01*000002000000* 0.001 14794E-38077400473512 000003000000 000002000000 AUXMl 107740047351? 000002000000 000001000000
AUXMl ( 01=000000000000= 0.077400473512 000001000000 000000000000077400473512 000001000000 000000000000 AUX f
INTERLUDE07740047351? 000002000000 000001000000
AUX ( 01-000002000000* 0.001 14794E-38INTERLUDE
077400473512 000003000000 000002000000 AUX CINTERLUDE
077400473512 000004000000 000003000000
AUX ( 01*000030000000= 0.01377532E-38INTERLUDE
077400465264 000005000000 000004000000 AUX (
FACTORIELLFf 51* 120
A'IXMl ( 01=000005000000= 0.00286985E-38077400465264 000006000000 000005000000 AUXMl <077400473512 000005000000 000004000000
AUXMl ( 01*000003000000* O.C/01T2191E-38077400473512 000004000000 000003000000 AUXMl (077400473512 000003000000 000002000000
AUXMl ( 01*000001000000* 0.00057397Î--38077400473512 000002000000 00000 > 000000 AUXMl 1077400473512 000001000000 000000000000077400473512 000001000000 000000000000
AUX ( 01*000001000000* 0.00057397E-38INTERLUDE
077400473512 000002000000 000001000000 AUX 1INTERLUDE
077400473512 000003000000 000002000000
AUX ( 01-000006000000* 0. 003443 83F-38INTERLUDE
077400473512 000004000000 000003000000 AUX (INTERLUDE
077400473512 000005000000 000004000000
AUX 1 01*000170000000» 0.06887662E-38INTERLUDE
077400465P64 000006000000 000005000000 AUX (
FACTORIELLE( 6l" 720
01*000003000000*
01*000001000000*
01-000001000000*
01*000006000000*
01*000170000000-
01-000004000000=
01-000002000000*
01*000000000000»
01-000002000000-
01-000030000000*
01-001320000000*
0.00172191E-38
0.00057397E-38
0.00057397E-38
0. 003443 83E-38
0.06887662E-38
0.00229588E-38
0.00114794E-38
0.
0.00114794E-38
0.01377532E-38
0.23877229E-38
Fig I 5.4
- 42 -
Cependant il faut remarquer que cet exemple est le plus
simple de ceux que l'on peut rencontrer : en effet, l'appel récur-
,-;if ne l'est qu'au premier niveau, le sous-programme s'appelant lui-
*••**.(&.* par un seul intermédiaire alors qu'il est possible que ce ne
; OH. qu'après deux eu trois appels de sous-programmes que le sous-
p.x ranBae origine soit appelé. De plus, dans le cours du sous-
pv-ngramme on ne rencontre qu'une fois la séquence d'appel récursif,
alors qu'on le verra dans le calcul de la VALEUR ou de la DERIVEE
d'une fonction, il est très possible de la rencontrer de 2 à 14 fois.
Dans ce cas, le sous-programme intermédiaire (FACT) doit aussi être
équipé pour traitement récursif.
1-2-8 - Les données en SLIP
Comme nous l'avons vu, les données se logent dans la seconde
cellule des doublets des cellules qui ne sont ni des cellules de tête
ni des embranchements. La première réflexion que nous inspire ceci
est que la place est peu importante. En effet, un mot machine est
court pour loger des données. Pour pallier ceci on peut utiliser
deux stratagèmes i loger non une donnée numérique, mais un syrobole
alphanumérique, ou loger l'adresse d'un tableau de nombres ou d'un
autre groupe de données.
Adresse d'un tableau de nombres
Pour reconnaître la structure de la donnée, on peut utiliser la
zone index de la première cellule (l ou 2) ou la zone préfixe de
l'une des cellules, en y mettant 4, 5 ou 6. Les fonctions WAGON
et TAB pointant sur un tableau de N isémoires, ou sur une suite de
données utilisent la zone index. Pour le tableau (zone index * 2),
la donnée contient le nombre de cellules et l'adresse de la tête
de tableau
NA B LSGH
2 LSD ]Add «j
1 .
TAB(N)
» TAB(l) 1
Appel Î.HSIN2 (G, LSG, 2f LSD, NA)
- 43 -
Pour la suite de cellules, la donnée contient l'adresse
d'un autre doublet, et ainsi de suite, ce qui constitue une liste
non symétrique.
Elle peut contenir
des symboles SI SN
et une donnée.
I1
0 *LSG i LSD .ADD1, tu
1
*
mO S1 i 32
S3 ADD2*
c.1 fH 1j Don
> £5iSe
Addl "Donnée 1Donnée 2
Symboles
II est possible aussi de constituer des listes de symboles au lieu
de constituer des listes de nombres. Cette technique est utilisée
par les interpréteurs LISP ou IPL V, chaque symbole pouvant, après
traitement prendre une ou plusieurs valeurs. Par exemple chaque
symbole est un tableau de trois SYMB1 Addl T* Cellule
cellules dont les deux dernières
contiennent une donnée.
Ce traitement de liste de symboles permet de traiter une
liste facilement écrite, grâce à des parenthèses de séparation de
niveau (sous-programme PLSTP). La ligne ' I Tête
(SI, S2 (331, 332 (3331, S??2)S34)S4)
correspond à la structure suivante,
chaque niveau étant déterminé par
compte de parenthèses.
S2m332
S34
Tête
—tfôte
Une autre méthode d'utilisation des symboles est celle des
listes descriptives, l'enchaînement des cellules ne servant qu'à
bâtir la structure, les symboles étant contenus dans les listes
descriptives qui contiennent et les symboles, et leur valeur.
La structure suivante (fig. 1.2.6} correspond à la liste
(SYMBQL1(SYMBOL3(SÏM30IA) ) (SYMBOLS) )
Une fois la liste traitée, on dispose des valeurs des diffé-
rents symboles. Le passage de l'une de ces formes d*expression de
listes à l'autre, permet le traitement des symboles par la structure
de la liste, telle la dérivation formelle.
- 44 -
Fig. 1.2.6
DL1
DL1
0SYKJOL 1=fi
DL2
DL2
ol} VALÏ
DL5
DI4
0SÏKBI
—
aYAI 3
DL4
Cela peut être très utile que de passer de la notation
(X 4- (B x Y) + (SIN(C x Z))) à la liste
}"— - ' • » - - » I
4.
' i — -^Lv -4— *f° F Hfr- — TT^^^TB
•!•* ,.. II. ,• ir
(ÏT Tl 1 gf«n i L
*4-
C
-4(SI
f1-»
ÏÏ— A
1 \I
oj1T
«B
"1!*
II-m
-*
•i*•r
n., ., j2
•m
- 45 -
1-2-9 - Ecriture du langage
II existe plusieurs moyens de créer un langage de listes, ainsi
que nous l'avons vu dans les premiers paragraphes. Pour SLIP, cela
pouvait être un langage spécial, reprenant par exemple les fonctions
existantes, et passant directement aux opérations machine, par l'inter-
médiaire d'un interpréteur SLIP, câblé ou non , mais n'utilisant pas
les compilateurs classiques des machines (FORTRAN ou autres). Cela
pouvait aussi être l'écriture en FORTRAN, telle celle qui a servi à
la présentation du système. Mais dans cet ordre d'idées, la présen-
tation la plus économique, la plus rigoureuse, est évidemment l'écriture
en langage machine FAP, MAP.... L'écriture en FAP est facile, car
elle s'inspire très directement des sous-programmes FORTRAN, compilés.
L'écriture en MAP s'avère plus difficile à optimiser du fait de l'exis-
tence de macro-opérâtions, de parties communes à certaines fonctions,
ce qui fait d'ailleurs la supériorité de MAP sur FAP.
Nous avons écrit la très grande majorité des fonctions en FAP,
ce qui avait été aussi la solution adoptée par l'équipe qui au MIT
avait mis au point SLIP. Cette présentation permet, au traitement,
un gain de temps appréciable, car FORTRAN, comme tout langage général,
prend un grand nombre de précautions, avant d'écrire le corps du sous-
programme, précautions en général superflues, car il n'est pas adapté
aux opérations qu'il a, ici, à effectuer. D'autre part, la définition
des types de variables est un obstacle qui n'existe pas en FAP. Ainsi
un sous-programme écrit en FAP, occupe environ 30 % de mémoires de
moins que le même sous-programme écrit en FORTRAN. Comme, au char-
gement, les sous-programmes et fonctions, occupent environ 10 000
mémoires et que le reste est consacré à la réserve, 50 % de place en
plus , fait 3 000 positions de mémoire de plus pour la réserve, ce
qui n'est pas négligeable.
Il est évident que la réalisation d'un compilateur, d'un
interpréteur, en SLIP sans le fardeau de FORTRAN est la meilleure
solution et cela sans aucun doute, du point de vue du temps machine,*
puisque ceci a été réalisé en LISP et en IPL, et est en cours de
réalisation pour SLIP au MIT, mais on peut se demander si cela est
la voie de l'avenir, car il existe maintenant aussi une version de
LISP en ALGOL, et que le nouveau langage d'IBM, le PL 1, en cours de
réalisation, langage qui utilise les listes, est écrit en un langage
universel.
CONCLUSION - Le langage SLIP
3LIP est donc un langage complet, et par bien des cotés supérieur à
bien d'autres langages, par sa symétrie essentiellement, par sa réserve
toujours de capacité maximale et son auto-gestion, par sa facilité à trai-
ter des problèmes numériques, par l'accès aux dispositifs d'entrée - sor-
tie de FORTRAN, par ses facilités d'utilisation sur de nombreuses machines
à compilateur du type FORTRAN grâce à ses fonctions bien distinctes. On
peut même grâce à lui réaliser les procédures de LISP et IPL : CAR, CDR,
CONS par exemple.
Cependant, il n'est pas toujours utile d'utiliser un langage aussi
élaboré. Si un traitement peut se faire par les piles, point n'est besoin
de charger un dispositif complet de traitement de listes. Lorsque l'on a
un certain nombre de données à relier qui arrivent chacune à son tour, la
façon la plus logique de les emmagasiner est le tableau de nombres à condi-
tion de connaître l'adresse du premier mot disponible. Ceci a été le point
de départ de l'utilisation des "piles" qui ne sont rien d'autre qu'un ta-
bleau dont l'adresse de la tête varie, ce qui est analogue à un décalage
global vers le bas où toutes les données changeraient de mémoire pour aller
dans la mémoire suivante du tableau, la tête restant fixée
L'utilisation des piles est plus courante que celle des listes, mais
ces deux entités, lites et piles, ont un point commun : les différentes
données sont reliées entre elles par des liens qui bien que de types diffé-
rents - l'un par mémoires consécutives, l'autre par l'adresse absolue de la
cellule - n'en expriment pas moins une idée de suite.
Les listes communes que nous avons étudiées dans le traitement récur-
sif n'ont qu'une utilité de piles. Il ne serait pas nécessaire d'utiliser
un support aussi complexe que SLIP pour cette opération, mais cela procède
d'une rationalisation des traitements.
On peut donc dans certaines circonstances ne charger en machine que
les fonctions qui seront réellement utilisées (ce qui est utile sur les
petites machines) et éviter de se servir du suiveur lorsque ce n'est pas
strictement nécessaire, car les fonctions AVS... AVL... sont nombreuses
et relativement compliquées, ce qui occupe de nombreuses positions de
mémoire.
SLIP a aussi de nombreux inconvénients, telle la difficulté de passer
du traitement des symboles aux opérations algébriques, difficulté due à
l'inexistence d'un interpréteur complet, l'impossibilité ou la difficulté
d'écrire des programmes autoraodifiables, car ils ne sont pas écrits en
liste. Mais il ne faut pas demander de performances au-dessus de ses pos-
sibilités à un quelconque langage, et ses performances au point de vue
rapidité sont à SLIP un atout majeur. A chaque type de travail correspond
un langage adapté, et mieux vaut connaître plusieurs langages plutôt que
d'en vouloir un universel. Nous allons voir que SLIP permet des réalisa-
tions intéressantes.
- 48 -
II - REALISATIONS
II-l - OPTIMISATION DE LA TAILLE DE LA RESERVE
Une faiblesse de plusieurs langages de listes résulte du fait
que la réserve est créée en dimension par le programmeur, qui ne con-
naît pas les dimensions de l'espace qui restera disponible après char-
gement du programme et des sous-programmes. Cet écueil est aisément
levable en IPL où l1interpréteur est un interpréteur IPL comprenant
le chargeur. Mais en SLIP, ceci n'est pas possible, car les dimen-
sions de l'espace disponible ne sont connues qu'une fois la compila-
tion et le chargement terminés et qu'à ce moment, le compilateur
FORTRAN ne donne pas accès aux mémoires libres. Il a donc été néces-
saire de tourner ces règles et de mesurer l'espace disponible au
cours du traitement. Ceci a été résolu grâce à la connaissance des
règles du chargeur, qui permettent d'avoir accès au nom du sous-
programme de moniteur chargé en queue de table. Grâce à cette adresse
on peut connaître celle de la première mémoire libre. L'autre écueil
est qu'en FORTRAN sur IBM 7094 des mémoires COMMUN sont chargées en
queue et en remontant, ce qui fait que la première mémoire de la réserve
doit être la dernière du commun. On doit
donc dimensionner à un nombre quelconque
la variable représentant la liste d'espace
disponible, et mettre cette variable à la
On
MoniteurPPSPMoniteurEspace libre
j COKMJN suite des autres dans le commun.
fera donc une liste d'espace disponible commençant à cette mémoire,
et finissant à la première mémoire libre après les sous-programmes
de contrôle du moniteur. C'est ce que réalise la nouvelle version
du sous-programme INITED (INITfiS) associé à la fonction KFINAL dont
les listings et organigrammes sont ci-après. Fig. A.8
II-2 - DIFFERENTES PRESENTATIONS DES LISTES
II existe deux façons essentielles de se représenter une liste :
la première est de représenter les mémoires reliées les unes aux autres
- 49 -
et leurs contenus, comme nous l'avons fait quand nous avons étudié
le mécanisme de SLIP.1 • ~ . 1li)^ DL 0
t»^u . — 1 — , — __
—A |
r 1>0
1B
"»-J"
1 »
G Jl 1
C'est ce que visualise le sous-programme IMPLST qui imprime le contenu
des différentes mémcires des listes d'une structure (liens et symboles
ou données) jusqu'au niveau 4.
Le second moyen consiste à représenter la liste linéairement
par ses symboles en faisant abstraction des liens, qui sont implicites.
Ceci a l'avantage de ne pas être attaché à un langage de liste parti-
culier et de mettre en évidence l'essentiel, c'est-à-dire les symboles
ou les données, les signes de niveau différent étant les parenthèses
(1) (A, 3, C) (2) (A, B(C, D) E(F(G, H))I)
II est évidemment très commode de passer d'une structure à l'autre,
de mettre sous la forme de liste SLIP, exprimable sous la forme
IMPLST une liste de symboles parenthèses, et de rendre plus concise,
plus expressive, une structure SLIP. C'est ce que réalisent deux
programmes que nous analyserons : LISSYM et FLSTP.
II-2-1 - Sous-programme IMPLST
C'est un sous-programme dont un paramètre est le nom
de la tête de liste principale, qui imprime en octal (012) le
contenu de toutes les mémoires de la structure (liens et données)
suivant une forme arborescente, séparant les différents niveaux.
Il ne permet pas de représenter les structures bouclées (ce que
ne permet pas non plus la notation parenthésée). Comme il n'est
pas récursif, il n'a été conçu que pour imprimer 4 niveaux (le
maximum avec la place dont on dispose sur une feuille de pro-
grammation). Il est entièrement en octal, ce qui est utile pour
représenter les adresses machine, mais peu pratique en ce qui
concerne la manipulation de symboles. Néanmoins il donne une
image très claire de la structure.
Appel IMPLST (LIST2, C, F, G, I)
La liste (2) se représenterait :
6
0
2001
0
*6/u
01 i G
0 , cX
000000000021000022
000000000000000000
« £ t£
A000025V
;000031
200
AB
A£
000000ï)201
Xfc.
00000000002302 A
0000010
0
E
-rt
000000
Tl000000000026
P
cr
£*I
000001000000P200
o< £CD rapr
adrefiéao
21 -p sont
A, B
r wP t G
- P H
' If ....
éeentent lesssss desires
î-<~ « i . .les syoboles
cxxxx>o000027000030
00000'D0 i
Exemple et listing fig. II.2.1 et II.2.2
II-2-2 - Passage de la. liste de symboles à la liste SLIP
C'est la réalisation la plus difficile, car on part
dfune suite de symboles qu!il faut analyser. Ceci est fait par
le compilateur ou l'interpréteur en LISP mais doit être program-
mé en SLIP. Il faut tenir compte des critères de séparation que
peuvent constituer les parenthèses gauche et droite, les virgules,
les blancs. Chaque parenthèse exprime le passage à un niveau
différent : ( —& niveau + 1 ; ) —» niveau - 1. La virgule
ou les blancs séparent deux symboles, dont la longueur ne peut
excéder 6 lettres. Cette analyse et la mise de chaque symbole
et parenthèse dans un mot est exécutée par SEPARE, fig. II.2.3,
II.2.4. La recherche du niveau par le compte de parenthèses est
effectué par CPAR (fig. II.2.6) qui compte les parenthèses d'ou-
verture et de fertoeture. C'est en effet \m problème épineux que»*•.
celui de la séparation de caractères, car il procède de la
- 51 -
reconnaissance de structures. C'est un travail analogue à
celui d'un compilateur qui est réalisé ici : reconnaître les
symboles, et suivant leur signification, faire des opérations
nécessaires. Les critères de séparation de mots sont : les
virgules, les blancs, les parenthèses. Un travail de même
nature est exécuté dans la fonction VALEUR, qui utilise d'ail-
leurs ces sous-programmes pour confectionner ses listes, mais
travail plus complet, en ce sens qu'elle exécute elle-même les
opérations arithmétiques après reconnaissance des symboles opé-
rations comme un véritable compilateur. La confection de la
liste SLIP est faite par FLSTP. Les résultats seront imprimés
suivant le modèle IMPLST. (FLSTP II.2.5 - Organigramme II.2.7 -résultats II.2.8).
II-2-3 - Passage de 1& liste SLIP à la liste de symboles avec
parenthèses
Ce travail, l'inverse du précédent, est considérablement
plus aisé à programmer, car il peut utiliser les fonctions d'ex-
ploration des structures (AVSED) pour progresser. Il doit sim-
plement tenir compte du niveau auquel il est pour intercaler entre
les symboles les parenthèses gauche ou droite, et savoir quand il
a atteint l'extrémité de la structure. La fonction LISSYM
réalisa ce travail (Listing figJI.2.9 - Organigramme fig. 11.2.10)
II-3 - LOGERENT DE DONNEES LONGUES ET DE SYMBOLES
II-3-1 - Fonction WAGONS, TABLEAU
Nous avons expliqué dans l'étude des fonctions SLIP le
mécanisme choisi pour introduire de nouvelles possibilités de
logement de données par accrochage à la suite de nouvelles
cellules de données, ou par la référence à un tableau. Nous
reproduisons ici le programme d'exploitation, les sous-
programmes LWAGON (fig. II.3.1), MITAB (fig. II.3.2), MIL (fig.
II.5.3), INSIN2 (fig. II.3.4), ROELL (fig. II.3.5). Il est à
remarquer que la fonction RCELL ici est une fonction recursive,
mais particulièrement siaple car si elle se rappelle elle-F«me,
elle ne nécessite pas un processus analogue à celui étudié pour
le calcul d'une factorieIle, ou la valeur d'une fonction.
Il faut simplement conserver l'adresse de retour au programme
principavl.
II-3-2 - Manipulation des symboles
La manipulation des symboles est aisée en SLIP, bien
que le langage soit mieux adapté au traitement numérique, mais
lorsque l'on veut associer une ou plusieurs valeurs à un
symbole, on est bien souvent conduit à des manipulations diffi-
ciles et trop spécifiques. Il existe une méthode de généraliser
cette opération ; faire la table des symboles et associer à
chaque symbole une ou plusieurs valeurs, dans un tableau. Ceci
est très possible, car au cours du traitement d'une structure
on n'introduit pas de nouveaux symboles.
Soit la structure (A(B, C(C,E) X) C(H, X))
La liste des symboles sera A B C D E X H
Si elle est logée dans un tableau:A,Valeur de A, B,Valeur de B...
on peut avoir accès aisément aux valeurs des symboles, en ayant
uniquement à reconnaître le symbole en question .
Quel que soit le traitement que l'on ait à faire subir
aux symboles (dérivation manipulation), on n'introduit aucun
symbole nouveau donc la table de symboles est invariable et on
peut encore s'en :.*v±r après ce traitement. Ceci est évidem-
ment préférable à une liste, où, en correspondance avec chaque
symbole, dans la liste elle-même, on doit avoir une liste de
propriétés, ou une cellule de données supplémentaires qui
contienne la valeur, et que l'on doit introduire au moment de
la construction de la liste elle-même et ceci dans toutes les
positions de tous les symboles. Le tableau de symboles est
obtenu par : Appel TABSYM (LA, TAB), (fig. III.5. - III.6.). Les
valeurs numériques sont chargées dans TAB (l) pour I pair, par
lecture de cartes, avec en tête celles qui seront introduites par
la fonction DERIVE (ZER, UN, UîJM).
SOUS PROGRAMME IMPLST
CIMPLSTSOUS PROGRAMME IMPLST(LA,LB9LC,LD,LE)1=0IMPRIMER 13,LA,LB,LC,LD,LEZU=CONT(LA)ZU1=CONT(LA-1)IMPRIMER 11,ZU,ZU1
4 JU=LSD(ZU)ZU=CONT(JU)ZU1=CONT(JU-1)
72
SI ( 1-80)7*3,3SI ( ID(ZU)-2)2»3,2IMPRIMER il,ZU,ZUlSI ( ID(ZU)-1 )4,5,4MA=LSD(ZU1)ZA=CONT(MA)ZA1=CONT (MA-1 )IMPRIMER 17,ZA,ZA1J = 0JA=LSD(ZA)ZA=CONT( JA)ZA1=CONT( JA-1 )
810
SI ( J-80)8,4,4SI ( ID(ZA)-2 )10,4,10IMPRIMER 17,ZA,ZA1SI ( ID(ZA)-1 )6,14,6MI=LSD(ZA1)ZI=CONT(MI )ZI1=CONT (MI-1 )IMPRIMER 62, II ,ZI1K = 0JI=LSD(ZI )20
ZI=CONT(JI)ZI1=CONT(JI-1)SI(K-80)21,6,6
21 SI(ID(ZI)-2)22,6,2222 IMPRIMER 62,ZI ,ZI1
SI ( ID(ZI)-l)20,23,2023 ALLER A 2011 MODELE(2(6X,012),//)13 MODELEt1H1,5H LA=,012,5H
1012,///)17 MODELE(36X,2(6X,012),//)62 MODELE(72X,2(6X,012),//)3 RETOUR
FIN
LB=,012,5H LC=,012$5H LD=,012»5H LE=
II 2.1
FONCTION IMPLST Exemple d1 impression de liste
(4<*f )(*,B(CO(+(*,C ,
l . / » = 0 7 7 3 1 ï ( m 3 1 5 L B = O O O O C ) O O C O O < 5 0 LC=000000000000 LE = C O C C C C C C O C O C
mM3 ooooooooonoo
0 7 7 3 1 * O T < ^ 0 7 2 0 É O i ( 6 0 f 0 6 0
1T/313017Z65 077311071311
277277077305 O O n o C O O O O D O l
077311Q773C3 54606060606p
0773C5077277 216060606060
177303077311 077301077301
1V/307077315 077267017267
277255077263
C77267077261
C77263077255
000000000001
546060606060
226060606060
177261Q77267 077257077257
277271077P75 O C O O C C . Q O O O O 1
077301077273 5 4 5 4 £ C é C É C 6 0 «-
077275077271 6 7 6 C É C É C 6 C 6 0 x
077273077301 242564676C60 DEUX
*
B
277247077253 "OCCCCCCOCCC1
077257077247 2 3 4 É É C É 0 6 C É C Coa
Î77253077257 C 7 7 2 E 1 C 7 7 2 5 1
277231077245 CC0000000001
C77251077241 206060606060
177245077231 077243077243
C77241077251 246060606060
SYMB
II 2.2
9
FONCTION SEPARE
***
LISTEIDENTIFIFAP
CATION
*SEPARE
SEPARE
AB
ADA
ADB
AA
TT
TR
AG
TON
ADC
COMPTENTREESXASXASXARADSORRADSRARADSRASRASRASRAEEXEEXRADSORRALSRLRALOEATZETRASXDTRARADADDSRDSORRALETASPI-RALRALDLOSRLTXATXITXATXIEEXEEXEEXRALSRLTXITRATXARALOEA
300SEPAREENDI.lENDI+1»2ENDI+2,4$(IMP)21,4AB2 » 4AMBABBBC0,10,2UNMNA**»!AUX1AUX1BLBLADAADBTON, 2TRNASIXTTNAAUX1MAXMU,2MU, 2AUX16AUX1*+l»2»lA A » 2 »***-H,l,lAB,1 ,350,10,20,4MUtlMOTADC»1,**ENDI*+l,l,lMOTBLANC
BC
AO
AP
AE
AL
AH
BA
AF
TZERALOEATZERALOEATZERALOEATZERALEMQDLOSRLTXARADSORTXIRALSRLTXAEEXRADSORTRARALSRLTRARALSRLTRASXDRADTZERADSSTPDXSXDEEXRALDLOADDSRLTXATXIRADSOREEXRALSRLTXASXDRADTZERAD
AGMOTVIRGAEMOTPARGAOMOTPARDAPAUX2MOT6AUX2*+l»2» 1UNPAG,2,5AUX2**»4*+l,4, 10,2ZEROPAGPOUVMOTAFPFERMOTAFAUX3-2PAGCINQAUX30,2AH, 20,2AUX26BLAUX2*+l»2» 1AL,2»**ZEROP0 ,2AUX2**,4AG,4,1AUX3,2PTVCINQ
AV
AR
AM
TVBB
ENDI
PAUX3UNMNABLBLCINQAUX1ZEROMAX
MUMOTBLANCUNVIRGPOUVPFERPARGPARDAUX2SIXBL
SSTPDXSXDEEXRALDLOADDSRLTXATXIRADSOREEXRALSRLTXARALSRLTXAEEXEEXEEXRADSORTRABCSBCSOCTBCSOCTOCTBCSOCTOCTBCSBCSBCSOCTOCTOCTOCTOCTOCTOCTBCSOCTOCTFIN
AUX30,2AR,20,2AUX26BLAUX2
AV,2,**ZEROP0,2AUX2**,4
MOT**,4AG,^,!**,!**,2**,4ZERO'P3,41140000100000016060606060600000050000001000000000000770000000000216116000000000000000010000007300000000007460606060603460606060607400000000003400000000001000006000000000000000060
Fig II 2.3
PODCTIOI
(RX2) signifiecontenu d» RX2
dTON signifieparti* dioHnrnt de TOH
/ JOUI t BLHL
2 di«it» AUX1Décaler ai. 6 à gauche(EX2) + 1 __>.RX2
(RX4) + 1 —> RX4AUX2 —> H - RX4
(RX2) + 1 —». RX2SRL AIK2ADD BLDLO 6
EX1 i dTON~"N>5 - AUX3 —^ dAH
(nxi ) + 1 —> rai
S MOT l PARG
5-K33 —É-4AR
(AUX2) —>.K - (RX4)(RX4) + 1 _».HX4
a(EI2) + t _*-EC2
JQX2 —(Œ4) +'1 —».EI4HOT —*.H -(RX4)KZ4 + 1 —»RX4
~«
SOUS PROGRAMME FLSTP (MOT.LA)
SOUS PROGRAMME F.LSTP ( TSYMB ,LPARAM )DIMENSION TSYMB(l)»NPILE(40)LC = 0J = l1 = 1
30 TRAV=TSYMB(J)P=lINDIC=ICPAR(TRAV,P)SI ( INDIC-1)4,3,4
4 P = 0INDIC=ICPAR(TRAV,P)SI( INDIC-1)2,1,2
1 LA=LISTE(9)SI(LC)10,11,12
10 IMPRIMER 100ALLER A 25
11 LPARAM=LAALLER A 13
12 I = L CLK = NPILE( I )APPEL N V Q U ( L A , L K )
13 LC=LC+1I = L CN P I L E ( I ) = L A
ALLER A 202 I=LC
L T = N P I L E ( I )
APPEL NVQU(TRAV,LT)ALLER A 18
3 LC=LC-1SI (LC)10,25,20
20 J=J+1ALLER A 30
18 SI(J-60)20,19,1919 IMPRIMER 10125 RETOUR100 MODELE(1H1»24H ERREUR SUR PARENTHESES )101 MODELE(1H1»26H ERREUR LIGNE TROP LONGUE )
FIN
FONCTION CPAR
Fig II 2.5
*CPAR
ICPAR
P
AB
AC
AFSOR
ZEROAUXUNCPFERCPOUV
COMPTENTREESXARADSRARAD -SRARADTZERALSRLTRARALSRLRALOEATZERADTRARADEEXTRAOCTBCSOCTOCTOCTFIN
25ICPAR.SOR, 41,4AC2,4P##ABCPFERAUXACCPOUVAUX##AUXAFZEROSORUN**»43,40000000000001000001000000346060606060746060606060
Fig II 2.6
ÏLSTP
PONCTION FLSTP Exemple de réalisation
Ent
•LC
Loc'buroTHAV - TS1HB (j)
Reoonter1 niveau F
oui 1
TSAV t
LC : eospteur de niveau
: cellule logeant le aynbolo lu
J > EBQY (TRAY,ajouter unscontenant 1
SHREUR< OU1Ç L1«ne w
FIS
•<f
LAÎT" Creation de> oillulo tôte de listo u
HAY
u.ï c^ C<^ T^ t n X?^ yia ^—5— NIVEAUmin^ \ l 1 '^ «AViwvu
,_ 1 (LA) .PARA50011 , , 1 — ~-ZI »LCLK » NPILE (l)BVQY (LA,LK)Accrochags as LÀ a laxiate oouyantc ii
LF
|ttc) + i _*.» | *ÏÏS±-
1 1| (LC) -_*ï
> r
| (LA) __*KPILE (i) ]
>l
STRUCTURE OE LA LISTE
IAI,81,C11A2,B21ANI,MOTIANT01N,E)NUL)D2)EI (NOËL,F IN))
LA=077315077315 LB=000000000000 LC=000000000000 LD=OOOOOOOÛOOOO LE=000000000000
2772*5077313
077315077311
077313077307
077311077303
177307077251
000000000000
210160606060
220160606060
230160606060
077305077305
0773030772*5 250160606060
177251077315 0772*70772*7
277253077301
077305077277
077301077273
177277077253
000000000001
210260606060
220260606060
077275077275
077273077305 2*0260606060
2772*10772*3
0772*70772*1
0772*3077247
OOOO00000001
*5*625*36060
2631*5606060
277255077271
077275077267
077271077263
177267077255
OOOQ00000001
21*431606060
4*4663606060
077265077265
277257077261
077265077257
077261077265
000000000001
21*563*631*5
256060606060
077263077275 4564*3606060
:. H a 7
Fig. II. 2 .8
CC
23
C8610
30
2620
21
25
14
SOUS PROGRAMME LISSYM (LAfSYKB)
LISTE DE SYMBOLESLOGE LA LISTE DES SYMBOLES
SOUS PROGRAMME LISSYM(LA,SYMB)CREATION DE LA LISTE DES SYMBOLES UTILISES SOUS FORME PARENTHESEEDIMENSION SYMB(ioO),LlEN(20)»N(20)LA EST LA LISTE DONT ON CREE LASYMB EST LE BLOC DANS LEQUEL ONPARD=3H)PARG=3H(LCH=LCRTCH(LA)APREM=AVSED(LCH,A)NIV=LCNVCH(LCH)S I ( N I V ) 1 , 1 » 2F A I R E 3 1 = 1 , N I VS Y M B ( I ) = P A R GJ = N I V + 1SYMB(J)=APREMJ=J+1ALLER A 4SYMB=PARGSYMB(2)=APREM
DON=AVSEDUCH,A)S I ( A ) 9 , 8 , 9TEST DE CHANGEMENT DE NIVEAUSKNIV-LCNVCH(LCH) )5 ,6»7SI ( I N D ) 2 1 , 1 Ù , 2 1LÏNK=LSG(CONT(LCH-1))SI ( L I N K - L I E N U ) ) 30,21,30FAIRE 26 I=2 ,NÏVOSKLINK-LIEN(I) )26,2l,26CONTINUERS Y M B ( J ) = P A R DJ=J+1SYMB(J )=PARG
SYMB(J)=DONIND=0
LIEN(1)=LSG(CONT(LCH-1) )N(1)=LSD(CONT(LCH-1) )FAIRE 25 1=2, NIVK-l-lLIEN(I)=LSG<CONT<N(M)-1))N( I)=LSD(CONT(N(M)) )NIVO=NIVALLER A 4SYMB( J)=PARD
NIV=NIV-1ALLER A 8SYMB(J)=PARGIND=1J=J+1NIV=NIV+1ALLER A 8FAIRE 14 1=1, NIV
SYMB( J)sPARDJ=J+1RETOURFIN
2.9
essFONCTION LISSÏM
LCH = Suiveur
APREM = AVSEDNIV B niveau 1er symb
<i
TJTV » n/
SÏMB (J) = PARGautant de fois que NIV 0
J = NIV + 1SÏMB (J) = APREM
J = J + 1
LIENCD. »
SÏMB f 1 ) a PARCSÏMB (2) = APREM
J =3
DON = AVSED
A : 0
•*\rNIV t LCNVCH
SYMB (J) « PARDJ B J + 1
NIV B NIV - 1
IIND : 0
=
LINK=adresse tête de liste courante
SYJTO (J) = PARGJ = J-1
NIV = NIV + 1IND B 1
(J) = PARDautant de foisque NIV
FIN
LINK : LIEN (1)
iLINE : LIEN (I)
I de 2 à NIVO
SÏMB (J) = PARDJ «= J + 1SÏMB (j) = PARCJ = J + 1
*
reste-t-on dans la mène liste
la tête de liste courantea-t-elle déjà été rencontrée?
SÏMB (J) « DOMJ = J + 1
IND
A et B ont le3 BÔma niveau
alors 20
LIEN (1 ) = adresse tÔtede liste courante
1LIEN l) s adresses de toutesles têtes de listes
I de 2 à NIV
NITO s m
Fi«. II. 2.10
c
c
cc
MIL
AA
MG
AUX
FONCTION LWAGON (A,B,C,NA)
FONCTION LWAGON(LA»N1»N2»N3)ACCROCHAGE D'UNE CELLULE DE DONNEE SUPPLEMENTAIRE A LA DONNEE LANT=NUCELL(Z)SE CARACTERISE PAR UN 1 EN COLONNE INDEXAPPEL -lNSIN2(-l»-l»lt-l»LAiAPPEL INSIND(-1»-1»NT»LA-1)Nl,N2»N3 SONT DES NOMBRES DONNEES SUPPLEMENTAIRESAPPEL INSIND(6»N1»N2»NT)APPEL INSIND(0»N3»-1»NT-1)LWAGON=NTRETOURFIN Fig II 3.1
FONCTION 1CLTAB (AD,N,NA)
SOUS PROGRAMME MITAB(TAB,N,LA)ACCROCHAGE U « UN TABLEAU A UNE CELLULE DE DONiNEELE NOMBRE DE CELLULES DU TABLEAU ET SON ADRESSE SONT EN DONNEEAPPEL INSIND.(-1»MADD(TAB) ,N»LA-1)SE C A R A C T E R I S E PAR UN 2 EN COLONNE INDEXAPPEL INSIN2(-1,-1»2,»1,LA)RETOURFIN Fig II 3.2
FONCTION MIL (NA)
COMPTENTREESXARADSRARALDAGSRPRADDADEEXTRABCSFIN
MIL
AA
18AUXAUX15
DONNE LE CONTENU DE LA ZONE INDEX
Fig II 3.3
Presentation de données supplémentaires sous forme de cellules en chaîne
ou de tableau de données»
FONCTION INSIN2(A,B,C,D,NA) FONCTION RCELL (NA)
»INSIN2
1NSIN2
KA
SK
OL
BM
TI
AC
AD
TOI
BA
BC
BD
COMPTENTREESXARADSRARADDADSRASRASRASRASRARADSRASRARADADCTZERADDADSZITRARMÛSZIRADSRASRARADADDTZERADDAGERPTRARADSRPRADSRASRARADADDTZERADPDX
70INS1N2MG»<t5,4KA«»18TDITPGTDDDBBM3.4OKGLt »UNMBM**3AUXTI» *AUX1,4ACAD«*UNMTOIft»
15AUXBAft *AUX2.4BCBDw*UNMTDG* *u,l
CRCELL
FONCTION INDENT]QUE A 1NLIND MAIS AVEC UNPARAMETRE SUPPLEMENTAIRE EN ZONE INDEX
TDG
ÇA
ce
CD
TDD
DADB
MG
UN"AUX
SXDTRARADPDXSXDRADSRASRARADADDTZERADPDXSXATRARADPAXSXARADSOREEXTRAorTRTSFIN
AUX.lÇA* *c.lAUX.l4,4ceCD« «UNMTDDft »0,1AUX.lDAft*0,1AUX,1AUXft «*• ,46><t0000010000001 10
11
1213
SOUS PROGRAMME RCELL(A)N = 0APPEL INTRDD(A.NB)SIMILICONTINBI 1-1)7,9,8IMPRIMER 10SKMIL(CONTINB) 1-1)1,3,1NB = LSD(CONT(NB-1MN = N*1IMPRIMER 12.NSI (N-l)<t.5,<tLTCH=NUCELL(Z)APPPL INS!ND(3,MB,0,LTCH)APPFL INSINDIO,NB.O,LTCH-i)ALLER A 2
CAND-CONT(LTCH)D=CONT(LTCH-1)APPEL INSIND(-l.NB.LSUI.LTCH)APPEL INSINDI-1 ,-l,LCNVCH(LTCH)+l,LTCH-l )APPEL INTRDKCAND.LSUI )APPEL INTRDI tOiLSUI-1)ALLER A 2APPEL R2CELLII SG(CONTILTrH) ) ISI (LCNVCH(LTCH) 16,7,6M=LSn(CONT(LTCH) IAPPEL R2CELLILTCH)TU=CONT(LTCH)IMPRIMER 13>TULTCH=MALLER A 1APPEL R2CELLIA)RETOURLTAB = LSG(CONT(NB-1) 1LNB=LSD(CONT(NB-11 1IMPRIMER ll.LTAB.LNBRETOURMODELE! 34H ELIMINATION DiUNE T.UITE DE WAGONS)MODELEI37H ELIMINATION DiUNE SOURCE DE TABLEAU1LULES)MODELE! 16)MOnrLFI5X,3HTU=,012,//lFIN
17,4H DE , U.BHCEL
CR2CELLSOUô PROGRAMME R2CELLIA)COMM'JN CREFAPPEL INSINDI-1,-l,A,LSG(CREF)IAPPEL INSDIR( - I .A . - I .CREF)APPFL !NSIND(-1,-1,0,AlPF.TOUR
F I N
Fi* II 3.5 Fig II 3.4
C1
213579111315C1817
20
226810
SOUS PROGRAM!® TABSÏM (lA,TAB) TABSIH (LI, TABLE)
Entree
SOUS PROGRAMME TABSYM ( LA, TABLE)DIMENSION TABLE(50) »TAB(50)INTRODUCTION DES OPERANDESPLUS=2H++FOINS=1H-PROD=1H*DIV=1H/SINU=2HSNCOSI=2HCOPUIS«=2H**LES SYMBOLES UN»ZER,UNM SERVANT APRES DERIVATION SON? CHARGES EN TETETABLE=3HZERTABLE(3)=2HUNTABLE(5)«3HUNMJ=lLCH=LCRTCH(LA)EXPLORATION DE LA LISTETAB(J)^AVSED(LCH»A)IMPRIMER 10»TAB(J)
BAoonnaiss&nsoa dasdlTora operataura+.-.*,/f»tsnrtoos
La tata de liai»TABLE ^ tàbloau das
ayobolea
_ » ~—?Creation du suiveur LSI 9
J T A B (J) » AVŒD (LCH.A) Tableau auxiliaire de tousles syabolea et opérateurs
J « J + 1
A t 0 Fin da la structure
K - 1> I
j TO - J J.I |
S!(A)2»1»2NO-JIMPRIMER 6tNO
SI(TAB(J)-PLUS)3,4,3SI(TAB( J)-FOINS)5»4,5SI (TAB( J)-PROD)7,4»7
SI(TAB(J)-SINU)11,4,11SI(TAB( J)-COSI )13»4,13SI(TAB(J)-PUIS)15,4,151 = 1RANGEMENT DES SYMBOLESSI (TAB( J)-TABLE(I))17f4,171=1+2SI (I-K)18»20,20TABLEtK)sTAB(J)IMPRIMER 8»K,TABLE(K)
J=J+1SI (J-NO)21»22,22RETOURMODELE(5X»3HJ= »I39//)MODELE(5X,6HTABLE(,I2,2H)»,A6,//)MODELE(5X»7HTAB(J)=»A6)FIN
III 5
1X TAB (J) I +\.
TAB (J) t -
TAB (J) I *
TAB (J) t /
TAB (J) >**
"WT
TAB (J 003
- TAB (I) I 0
TABLE (K) - TAB (JT
• K + 2
Synbole differentdasopérateurs
Sysbolo déjà rencontré
Chargement da la tablades syssboles toutes lesdeux ώaoiros
J - J + 1
\Fis. ni 6
- 53 -
II-4 - DICTIONNAIBES
Le problème d'optimisation du temps de recherche d'une fiche
dans un fichier ou d'un mot dans un dictionnaire est un problème
important et souvent rencontré. Un fichier est un ensemble de données
disposées en séquence (à la suite l'une de l'autre) dont on doit
extraire l'une d'entre elles après avoir défini son contenu. C'est
donc dans le cas général une recherche séquentielle, en testant la
valeur de toutes les données l'une après l'autre, jusqu'à ce qu'on
trouve la valeur cherchée, ou bien que l'on trouve la fin de fichier
ce qui imprime un diagnostic.
On peut améliorer cette méthode en procédant suivant une tech-
nique directive , par test de valeur supérieure ou inférieure, ce
qui divise le temps par un facteur logarithmique. Cependant le temps
de recherche est ici directement fonction et fonction croissante du
nombre de données. L'avantage est que l'encombrement du programme
est très réduit, et que l'on peut donc charger un grand nombre de
données dans l'espace disponible qui est maximal.
Cependant, le temps de passage machine n'est pas suffisamment
rapide dans de nombreuses applications, et on a été conduit à chercher
d'autres méthodes plus rapides, et moins dépendantes du nombre de
termes. L'une d'entre elles nous a semblé la plus valable : ne pas
composer des noms entiers, ce qui peut amener à N comparaisons (si N
mots - ou N/2, si on fait une comparaison pondérée) mais, comparer des
lettres ce qui ne fait que 25 possibilités (ou 12 si on pondère) donc
un nombre maximum de 25 N comparaisons si le mot a N lettres. Nous
allons donc étudier le détail de ce procédé, qui dans toute recherche
de fichier, de dictionnaire , de bibliographie, se révèle très intéres-
sant.
On ne peut loger un nombre très grand de,mots en machine pour
un traitement. La capacité de la machine, après chargement des pro-
grammes, permet de loger environ 500 mots et leurs traductions. Comme
on a en général affaire à un plus grand nombre de termes, de mots, de
fiches on doit donc les mettre en mémoire auxiliaire, - pour
l'exemple traité, des bandes magnétiques. Ceci pose des problèmes
très complexes car les adresses figurant sur les pointeurs des listes
sont des adresses absolues et qu'il faut s'assurer de la concordance
des positions des cellules lors de la lecture des bandes avec la
position précédemment occupée. La structure que nous avons adoptée
pour la constitution des listes est la suivante
- 55 -
Cette structure correspond à un niveau par lettre, chaque
lettre pouvant avoir 26 sous-listes (toutes les lettres) au maximum.
Les roots sont séparés en lettres par la fonction MOTLU (fig. IV.1.1 -
fig. IV.1.2 ). L'adresse de tête est donnée par une cellule inaliéna-
ble, qui pointe vers le premier embranchement vers la 1ère lettre....
Chaque lettre peut donc servir à plusieurs roots. Par exemple :
ABRI et ABAT divergent au R et A, ayant AB en commun,
FIIET et FIIER divergent à la dernière lettre. Lorsque l'on veut
retrouver un mot, on teste donc lettre par lettre, en commençant par
la première, avec 26 possibilités au maximum à chaque fois, plus le
critère de fin de mot (blanc). Dans cette fin de mot, on loge
l'adresse de la traduction correspondante (ordre dans un tableau,
adresse du mot traduit, adresse d'une liste de propriétés). Nous
avons choisi un numéro dans un tableau.
Lors de la constitution des listes, on doit se préoccuper de
la place dont on dispose en liste d'espace disponible. On peut se
fixer des critères au départ, on ne se préoccupe que de l'épuisement
de la réserve, mais ceci aurait l'inconvénient de faire plusieurs
listes distinctes, et au moment de la recherche d'un mot, on devrait
chercher successivement dans ces différentes listes. Nous avons donc
préféré utiliser à priori un critère permettant de loger certains
mots dans une liste (sur bande I), d'autres sur une seconde liste
(sur bande II) etc.... (Fig. IV.1 , IV.2 ) en se fixant le
nombre de divisions a priori, suivant le nombre total de mots à loger.
Lf inconvénient de ce système est que les structures sont figées, mais
l'avantage est que le nombre de mots maximum n'est pas atteint dans
chacune des structures, ce qui fait que l'on peut, dans des limites
raisonnables, compléter la liste.
En consultation, on utilise le même critère de sélection pour
n'appeler que la liste dont on aura besoin, cette liste sur bande est
mise en mémoire centrale et on travaille alors comme sur une structure
que l'on vient de créer, (Fig. IV.3 - IV.4 , organigramme), que
l'on attaque par la tête de liste principale, seule adresse à trans-
mettre.
- 56 -
/Bien que le temps df accès d!un mot soit dépendant du nonibre
de mots, il n'est pas proportionnel à ce nombre. Le temps d'entrée -
sortie est évidemment nettement supérieur au temps d'accès d'un mot,
ce qui fait que la courbe tr^(N) est de la forme t = a ISJt to
droite de pente très faible
Pour pouvoir Juger de l'intérêt que présente une telle classi-
fication nous avons jugé utile de présenter parallèlement un traitement
de structure séquentielle avec les mêmes nombres de mots. Le temps
d'entrée - sortie est aussi supérieur au temps d'accès, mais dans
de moins grandes proportions, ce qui fait que la courbe t -§(N)
est aussi une droite, mais de pente supérieure. Ces deux courbes
sont sécantes pour 400 mo^s' ( ig» IV.201.)
Des corrections sont cependant à apporter à cette comparaison,
car le nombre de mémoires occupées par le programme de traitement
séquentiel est de beaucoup inférieur à celui que prennent le programme
de traitement en liste accompagné de son jeu de sous-programmes. Avec
les méthodes adoptées, on peut loger en mémoire 1 500 mots, en séquence
contre 500 mots seulement en liste. Lorsque l'on appelle deux mots
successivement, on doit tenir compte de la probabilité qu'ils soient
dans le même bloc, probabilité de ne pas avoir à entrer en mémoire
rapide des informations contenues en memoir® auxiliaire. Elle dépend
d'une part du nombre total de mots (pour r» 500 en liste ou
h 1 500 en séquence, il est inutile d'avoir un stockage auxi-
liaire) et d'autre part de la probabilité de présence de la première
lettre, qui dépend de la fréquence de cette lettre dans le vocabulaire
utilisé. Pour un dictionnaire français, elle est : . (fig. IV.2.2.)
Exemples d'utilisation donnant la liste et les résultats : fig. IV, 5 et
fig. IV.6.
100
50
30
20
10
0
Temps mari en
Temps moyen en séquence
Temps mari en liste
TTemps moyen en liste
100 200 300
Courbes donnant le temps d1accès aux mots pourun nombre de mots inférieur à 300 avec les impressions
Tm = Ta + ta
Tb + ta
- "lin liste
En séquence
sans impression intermédiaire
X) 3000 4500 6000 N
- 57 -
A B C D B P G H I J K L M N 0 P Q R S T U V W X I Z
fig. IV.2.2.
Pour n petit, la probabilité est non négligeable (5-» , £••••)
Pour n grand, elle devient négligeable.
On pourrait donc être conduit à faire une mise en mémoire
auxiliaire sélective, avec conservation en mémoire rapide des mots
correspondant aux premières lettre C et P (et AESMRT accessoirement),
si le nombre total de ces mots à grande fréquence n'excède pas la
moitié de la capacité soit 250 mots environ. Ceci nécessite un calcul
de probabilités assez important, qui est fondamental si on veut opti-
miser le temps de réponse du système j par exemple en cas de travail
direct : appel par les différents usagers du fichier - gestion inter-
médiaire des priorités d'appel - résultats à fournir dans le plus
bref délai pour éviter des encombrements. On peut aussi loger les
mots les plus fréquemment appelés sur disques, et les autres sur bande,
à rythme de transmission inférieur. Ceci est cependant cas d'espèce.
CREATION DBS LISTES DE DICTIONNAIRE
MISE SUR BANDE
DIMENSION LAVS<2)»X<100),M(18ï »LETTRE(3) tA<4500)COMMUN CREF»X»LAVSAPPEL INITEDL=LISTE<9)MT=48
APPEL PLACER (700t32+NA)LIRE 110.N1.N2MN=12*N1-11NM=12*N2LIRE 101.CAU) »I=MN,NM)FAIRE 1 I=N1»N2LIRE 1 0 » « L E T T R E < I ) f I = l * 3 ) » N OIMPRIMER 11«<LETTRE(I )» I=1*3)J«lAPPEL MOTLU(LETTRE»M)SI(M-3Ô)100»1»1
100^ LCH*LCRTCH(L)5 EMB«AVLND(LCH,A)
M1*LSG(CONT(LSG(EMB)-1) )SI (LSG(EMBi-LSD(EMB))6»7,6
7 S I ( M ( J ) - M T ) 1 4 t 3 t l 414 SKMl-M(J) )3 .4»34 SI (M(J) )30tl.30 ^30 CC=AVSND(LCH,A)
J=J+1MlsLSG(CONT(LSG(CC)- l> )ALLER A 7
3 S I ( A î 6 » 5 , 66 LT*LSG(CONT(LCH-l î )
APPEL I N S D I R ( 0 » L T t L T f L T )8 LIC=LISTE(9)
NV*NVQU(LK»LT)LT«LKAPPEL INSlND(-ltM(J)t-ltLK-l)SI(M(J)-MT)9.1t9
9 J«J+1ALLER A 8
1 APPEL INSIND(-1»MT9NO»LK-1)APPEL IMPLST(LoLAtLB,LC,LD)FAIRE 51 1=1*6LIREBANOENA
51 IMPRIMER 77INSCRBANDENA»CREF»(LAVS(I ) *I«1»450Q)INSCRBANDENA,L»(X(I)»I»1,10Û)INSCRBANDENA,', A< I )»I»1»4500)REBOBINERNAAPPEL EXIT
10 MODELE C 3A6,6X* 13)11 HODELE(3(5X«A6)o//)77 MODELEC14H LECTURE BANDEî101 MODELE! 12A6>110 MOOELE(I3«9R«I3)
FIN Pi. IV-1
FONCTION MOTLU
OOC02 ENTREE MOTLU
MAILLON DIRECTEUR00000 00000000000000001 444663436460
000020000300004000050000600007000100001100012000130001400015000160001700020000210002200023000240002500026000270003000031000320003300034000350003600037000400004100042
0634 00 4 000320634 00 1 000330634 00 2 000340500 CO 4 000010621 00 0 000130500 CO 4 000020621 00 0 000220774 00 1 000000774 CO 2 00000
-0500 00 1 000000602 00 0 000420500 00 1 000400622 00 0 00027
-0500 CO 0 00042-0320 00 0 00041-0765 00 0 000140602 00 2 00000-0500 00 0 00042-0763 00 0 000060602 00 0 000421 00001 2 00027
-3 00000 2 000171 00001 1 00031
-3 00002 1 000130774 CO 4 000000774 00 1 000000774 00 2 00000OC20 00 4 00003+000021000000+000013000000+000005000000-370000000000
MQTLU SXASXASXARADSRARADSRAEEXEEX
AE RALSRLRADSRD
AA RALETAOLQ
KE SRLRALDLOSRLTXA
AD TXITXATXI
MG EEXEEXEEXTRAOCTOCT
NA OCTMAX OCTAUX1 8CS
FIN
RESULTATS
ARBREOOAOOO00 00000 000ANTIDOOOAOOOOOTOOO00 000PERIGROOPOOO001000OONOOOMUNICIOOMOOOOOPOOO00 000CONFESOCCOOOCOSOOOOOLOOOREVOLUOOROOOOOTOOO001 000
OOROOO00 00000 000TESOONOOOOOEOOO00 000INATIOOOEOOOOONOOO00 000PALOOUOOOOOAOOO00 000SIONNA00000000100000 000TIONNAOOEOOO001000OOROOO
OOBOOO00 00000 000
OCTOOOOOSOOO00 000NOOROOOOOAOOO00 000
OONOOOOOLOOO00 000LOONOOO00000000 0001RESOOVOOO000000OOEOOO
OOROOO00 00000 000
00100000 00000 000
001000OOTOOO00 000
00100000 00000 000
OOFOOOOONOOO00 000
000000OONOOOoosooo
M G T 4PG+1,1M G + 2 , 21,4AE2,4KE0,10,2**,!AUX1NA,1ADAUX1MAX12
AUX16AUX1* + l t 2 f lAA,2,*«
AE,1 ,2
**!l
3,400002100000000001300000000000500COOO77000000000C1
Pig IV 1.1
OOEOOO00 00000 000
OODOOO00 00000 000
OOGOOO00100000 000
oocooo00 00000 000
OOEOOOOONOOO00 000
OOLOOOOONOOO00 000
00 00000 00000 000
00000000 00000 000
OOROOO00000000 000
00100000 00000 000
oosoooOOAOOO00 000
oouoooOOAOOO00 000 Pig IV 1.2
il
mÉ
SI
1
1
DICTTOmiEE TES MOTS DE A à L
CREATION DE LA LISTE
Placer Wsnde
Ij L » Liste (9)I
Lire le n* des cartes
Fin quand plusaucune donnéeMiae sur bandeMettre dano la oollulecréée le syabole blanc
Lire lea'données correspondanteslea placer dan» le tableau
ï
en place destraduction»
Lire le act et son nunéro
Appel MOH.ÏÏ >Tableau des lettres K (l)
Séparation en lettres
TTXM (1 ) t L
Créer le suiveur
KMB « AVLND (LCH,A) descente linéaire dans laliste d'-.me cellule
Ml » Symbole de latôte de liste inférieure
EMB t nom de listenon
rui
M (J) t blanc
aon
MI i M
pot tcraini 7
Lattre courant» « Ht T
Fin da lalist* linéaire
[ CC - AYSHD (LCH,A)
J - J + 1
1 ïM1 - Symbole de la
tôte de liste inférieure
deocante structurelledans la liste d'1
LT a adrmuede la tôt» deListé oeonnte
LT m de liste
LuréVir uns
marelle liste IX.
la rattacher a.U list* HT
Rtttr» la lettre H (j) dcaala tâtfl te lista créés
cal H (J) t blanc
172 y™J » J + 1
LE
100
5054
5158
5652
57
5
86
910
231112
CONSULTATION DES LISTES
DIMENSION L A V S ( 2 ) » X ( 1 0 0 ) , M ( 1 8 ) , L E T T R E ( 3 ) » A (4-500 >COMMUN C R E F , X , L A V 5NA = 5APPEL PLACER (700,32+NA)
N=lLIRE 2, (LETTRE( I ) ,1 = 1 ,3)IMPRIMER 3,(LETTREtî) ,1 = 1,3)APPEL MOTLU(LETTRE,M)SI (M-36)50,51 ,51SI(N)54,57,54N = 0NOS = 6ALLER A 56SI (N-l)58,57,58N=lNOS = 9ALLER A 56FAIRE 52 1=1,NOSLIREBANDENALiREBANDENA,CREF,(LAVS(I),1=1,4500)LIREBANDENA,L,(X(I),1=1*100)LIREBANDÊNA,(A(I),1=1,4500)REBOBINERNAJ=lL C H = L C R T C H ( L )E M B = A V L N D ( L C H , A )M 1 = L S G ( C O N T ( L S G ( E M B ) - 1 ) )SI (M1-M(J) ) 5 , 8 , 5SI ( M ( J î - M T ) 6 , 1 0 , 6C C = A V S N D ( L C H , A )
M 1 = L S G ( C O N T ( L S G ( C C ) - 1 ) )SI (M1-M( J) ) 5 , 9 , 5SI ( M ( J ) ~ M T ) 6 , 1 0 » 6N O = L S D ( C O N T ( L S G ( C C ) - 1 ) )IMPRIMER 11, NON I = 1 2 * N O - 1 1M=12*NOIMPRIMER 12, ( A ( I ) ,I=NI ,M)APPEL HEUREALLER A 100M O D E L E ( 3 A 6 )M O D E L E ( 5 X , 3 A 6 )MODELE (5X»16HNUMERO DE CARTE =M O D E L E ( 5 X , 1 2 A 6 , / / )FIN
I 5 , / / )
Fig. IV-3
DICTIONMEHE
LECTUEE DES MOTS DE A à Z
Entrée
1
Lire le oot à traduire
Lo décomposer en lettres M (j)
H(î).lL ^—,
Appeler la bande correspondante!
de A à L ou de L à Z
enregistrements = suivantla 1 ère lettre
Suiveur LCH pointe en tôte j
EMB = AVLND (LCH,A) recherche embranchement suivantde la liste courante
M1 «= symbole du correspondant
M1 t M (J)
(J) t Blanc
1CC = AVSND (LCH^Sj
J = J + 1
j Ml = synbole correspondant
^ Mî î H (J)
I< M ( J ) t KT -
?
descendre de 1 niveauarrêt au 1er embranchement
Lecture de 1*adressede la traduction
si on est en fin de mot(blanc) le symbole blancdonne l'adresse traduction
! Itqjrossion
~TÏIH
. IV 4
LISTE DE DICTIONHAUffi Mots commençant par H
LA-077315077315 L3-000000000000 LC-000000000000 LO-OOOOOOOOOrOO LE-000000000000•
273507077307 000000000000
177315077163 077311077311
272651077303 0000*1.000001 |
1773110772*7 077305077305
272527077277 000031000001
177305077205 0773010773pl
177277075657 077207077207
177205072527 075661075661
175657077305 '072531072531
177303076701 077251077251
1772*7076625 076703076703
17670107*01} 076627076627
176625072651 07*01507*015
17*013077311 07265307265J
2772*30772*3 000070000001
177251077251 0772*50772*5
2765*5076675 0000*6000001
1767030765*5 076677076677
176675076703 0765*70765*7
273005076621 000021000001
176627076573 076623076623
1766*1075615 076575076575
176573073077 073617073617
173615073005 073101073101
173077076627 073007073007
27*00707*007 000025000001
17*01907*015 07*01107*011
2725710726*5 00006*000001
172653072571 0726*70726*7
1726*5072651 072573072)73
277273077273
177301077301
277201077201
177207077207
2727*5075653
1756610727*5
175653075661
272523072523
172531072531
277237077237
1772*50772*5
273655076671
176677073655
176671076677
2765*10765*1
1765*70765*7
2730*7076615
17662307*317
1766150730*7
17*317076623
276567076567
176575076575
273611073611
173617073617
27)073073073
173101073101
273001073001
173007073007
27*00307*003
17401107*011
2726*10726*1
1726*70726*7
000051000001 i
077275077275
000063000001 j
077203077203
000023000001 c
075655075655
0727*70727*7
000062000001 g
072525072525
000062000001 3
0772*10772*1
0000*5000001 j
076673076673
073657073657
00006*000001 „
0765*30765*3
000063000001 T
076617076617
07*32107*321
073051073051
000051000001 j
076571076271
0000*5000001 f
073613073613
0000**OD0001 H
073075073075
000023000001 g
073003073003
00002*000001 ,
07*00507*005
0000*5000001 I
0726*39726*3
27156507J565 000062000001 I
Fig IV 5
3$.*(
tm
•»
DE RECHERCHE DE TRADUCTIONS
Impression du mot à traduire,de son numéro,de la traduction et de l'heure
B A T E A UNUPERO DE CARTE= 3
B A T E A U = QUI FLOTTE PLUS OU MOINS
HEURE = 02963334 SOIXANTIEMES DE SEC = 082315 CENTIEMES DE PINAEROPLANENUMERO DE CARTE= 15
A E R O P L A N E = AVIONfPLUS LOURD OL'E L 'A IR
HEURE = C2963338 SOIXANTIEMES DE SEC = 082315 CENTIEMES DE PINCRAVATENUPERO DE C A R T E = 10
CR/ IVACKE = OUI FA IT MAL MAIS CCNNE DE BONS RESULTANTS
HEURE = 02963242 SOIXANTIEMES DE SEC = 082316 CENTIEMES DE PINT A R T A R ENUMERO DE CARTE= 56
082316 CENTIEMES DE PIN
T A P T A R E = COMME UN STEAK,ASIAT IQUE
HEURE = 02963346 SOIXANTIEMES DE SEC =T R C U V E RNUMERO DE CARTE= 51
T R C U V E R = LA FIN Pf LA RECHERCHE
HEURE- =-0246.3350 SOIXANTIEMES OE SEC = 082316 CENTIEMES DE P.ÏNZOENL'PERQ DE C A R T E = 54
082316 C E N T I E M E S DE PIN
082316 CENTIEMES DE MN
ZCE = PILE
HEURE = 02963354 SOIXANTIEMES DE SECORCUENLPEPO DE CARTE= 60
INSTRUMENT DE ML'SIOUE EN EGL1ÏF
HEURE = 0296335P SOIXANTIEMES DE SECZEPHYRNUPERO DE CARTE= 53
ZEPFYR = V f N T OUI P L I E "
HEURE = C2963262 SOIXANTIEMES DE SEC = 082316 CENTIEMES DE PINCALMENUPERC DE CARTt= 9
CALME = PAS BRUYANT
HEURE = C2963366 SOIXANTIEMES DE SEC = 082316 CENTIEMES DE PINODE3296NUPEflO DE CARTE= 65
082316 CENTIEMES DE PIN
C A T t - E R I N E C R I S E L
HEURE = C2963370 SOIXANTIEMES DE SECNI/GIRANUHERO DE CARTE= 118
ENDROIT DES CHUTES
HEURE = 02963374 SOIXANTIEMES DE SEC = 082316 CENTIEMES DE PINGENERALNUPERO DE CARTE= 95.
GEKERAL = GRAND CHEFtAOJECTIF
HEURE = 02963378 SOIXANTIEMES DE SEC = 082317 CENTIEMES DE PINChENILLENUPERO DE CARTE= 108
C h E N I L L E x A V A N T P A P I L L O N
HEUkt = 02963382 SOIXANTIEMES DE SECBROUDINYVONNUPERO OE CARTE= 123
082317 CENTIEMES DE PIN
25 A V E N U E R E I L L E P A R I S 14 ..951 80 00 P 3O 08
HEURE = C2963386 SOIXANTIEMES OE SECPAS7520NUPERO OE CARTE= 139
COLETTE L E P E R R I E R
HEURE = C2963390 SOIXANTIEMES DE SECVENTNUMERO DE CARTE* 131
MOUVEMENT OE L'AIR .
082317 CENTIEMES OE MIN
082317 CENTIEMES DE MIN
Fig
- 58 -
II-5 - CALCUL DE LA VALEUR D'UNE FONCTION REPRESENTEE PAR UNE LISTE
Ce problème est directement lié à l'étude des listes de symboles
faite à un chapitre précédent dont nous avons donné le principe et
aussi au calcul de la dérivée formelle d'une fonction, dont c'est la
suite logique. Cependant, ce problème est plus simple, et sera utilisé
dans le cas de calcul de la dérivée, c'est pourquoi nous l'étudions le
premier.
Pour pouvoir travailler aisément sur des listes de symboles
représentant des fonctions, il est commode - voire indispensable -
d'exprimer ces fonctions sous forme "polonaise préfixée". C'est-à-
dire que la fonction ;
AX^ + B Cos(Cx + D)+ E s'écrit en notation polonaise
(+ (*. A(**, X, 2)) (+ (*,B (Cos (+ (*,C,X) D))) E))
2Ï2lT~~'> iï2f11212
2 1
farI
21211 « C.X
21212 = D
2121 = C.X + D
12 = X2
11 = A
II = A.X2
212 = Cos(C,X + D)
211 = B
21 = B.Cos(C.X + D)
22 = E
1 2 = B.Cos(C.X + D) + E
I = A.X2 + B.Cos(CX + D) E
Exprimée sous cette forme, une expression ne relie que 2 termes
à chaque niveau, c'est-à-dire que A + B + C s'écrit (+A(+B, C)).
Ceci s'applique donc parfaitement à une procédure de listes de deux
sous-listes au maximum, en plus de l'opérateur, et suggère un traite-
ment récursif. VAIEUR (+(+A, B) C)
se calculerait : VALEUR (VALEUR (A + B) + VALEUR (C)) .... etc
- 59 -
Le programme de calcul de valeur ne s'arrêtant que quand il trouve
un terme simple, terme dont il extrait la valeur numérique, puis
remontant de niveau en niveau, calcule la valeur du second terme,
remonte ainsi jusqu'au niveau zéro et sort. Le programme VALEUR
réalisant ce travail a d'abord été écrit en FAP (où il a donné les
résultats attendus - fig. V.8) accompagné du sous-programme de
service VAL - fig. V.4 - qui sert d'intermédiaire pour l'appel
récursif, puis a été écrit en FORTRAN, en tournant, par un artifice,
l'impossibilité de connaître l'adresse d'où une fonction a été
appelée, de façon à la mettre en réserve dans la pile. Cette façon
de procéder est plus courte à programmer, mais plus longue à mettre
au point et demande un temps machine plus conséquent (fig. V.2 -
organigramme fig. V.3>). Les résultats sont cependant intéressants
dans les deux cas.
Dans le cas du sous-programme en FORTRAN, la fonction FLSTP
a été utilisée, de façon à standardiser la présentation et à simpli-
fier le programme principal. L'accès aux valeurs numériques se fait,
comme on l'a vu, lorsque l'on a étudié les symboles, grâce à la fonction
VALO (Fig V Q] explorant une table des symboles de la liste, obtenue
par TABSYM dans laquelle on a inclu les valeurs numériques en corres-
pondance avec les symboles eux-mêmes. Quand la fonction rencontre
le symbole qu'elle cherche (qu'elle a extrait de la liste), elle prend
sa valeur et la communique à VALO puis à VALEUR, et le traitement
continue. Programme Principal fig. V.7 - Résultats fig. V.6.
La fonction Valeur étant rappelée plusieurs fois, avant d'être arrivée
à sa dernière instruction, on doit donc conserver les valeurs non encore
utilisées, les résultats partiels et les adresses de retour, donnant
1»adresse machine d'où la fonction a été appelée, afin de permettre la
fin du traitement. L'adresse de retour est donnée par l'index 4 qui est
logé en tête de programme. Pour l'extraire, on a dû créer la fonction LADDRE,
Las quantités à mettre en réserve dans les listes piles communes (x(l))
sont : le symbole d'opération SYMB les 2 adresses des sous listes ou des
- 60 -
paramètres IS1, IS2, l'adresse de retour CONT (LN) et le résultat inter-
médiaire du premier appel récursif ST01.
Quand on revient à la fonction après l1avoir quitée par appel
récursif, on récupère dans les listes piles tous ces symboles, pour les
utiliser avec leur valeurs correctes à ce stade de travail. La mise en
réserve est faite par PARMT6 PAKKTf. La récupération par RESTR6, RESTE?.
On retourne au programme principal quand les listes piles sont vides et
on a ainsi le résultat.
I
A•is
1
5
fe
»
CALCUL DE LA VALEUR D'UNE PONCTION
Programme principal
CVALTAB VALEUR D'UNE EXPRESSION PAR TABLEAU DE SYMBOLESDIMENSION X(100)»LAVS(2),LETTRE<36) .MOT (2 16) » TABLE (50)COMMUN CREF,X,LAVSAPPEL INITEDLIRE 1. LETTREIMPRIMER 1. LETTREAPPEL SEPARE(LETTRE.MOT)APPEL FLSTP(MOT-AA)APPEL IMPLST(LA»D,D,D,D)L=LISTE(9)APPEL INSIND(-1,LA,LA,L-1)APPEL TABSYMl LA, TABLE)FAIRE 10 1=2,10,2LIRE 11,TABLE(I )IMPRIMER 14, TABLEV=VALEUR(L, TABLE)IMPRIMER 13, VAPPEL E X I TMODELE(1X,11A6)MODELECF6.3)MODELE (5X,2HV=,E12. 4)MODELE(5(5X,012))FIN
10
11113
Fig. V. 1
100102103104105106C101C
C
C
12
3456C8
10
11
12
15
13
14
C717
20110111112113
PONCTION VALEUR
FONCTION VALEUR (LA, T)D I M E N S I O N MG(2)INTRODUCTION DES SYMBOLES OPERAI IONPLUS=2H++FOINS=1H-PROD=1H*DIV=1H/SINU=2HSNCOSI=2HCOPU1S=2H*«RECHERCHE DE LA MEMOIRE OU EST STOCKEE L'ADRESSE DE RETOJRL N = L A D D R E ( L A )IMPRIMER 110, LNSB=CONT(LA-1)IDD=LSG(CONT(LA-1 ) )RECHERCHE DU SYMBOLE OPERA I EuR ,DEo ADREooEo DEo oOuo L I o i E iSYMB=CONT(LSD(CONT( IDD) )-l)APPEL INTRDD(SYMB.LYMB)APPEL INTRDD(PLUS.LUS)APPEL INTRDDIFOINS, MOINS)APPEL INTRDD(PROD.MROD)APPEL I N T R D D ( D I V » N I V )APPEL INTRDD(SINU»INU)APPEL INTRDDICOSI «LOSI )APPEL INTRDD(PUIS»MUIS)IS1=LSD(CONT(LSD<CONT(IDD) M )IS2=LSD(CONT( IS1) )I M P R I M E R 20»PLUS»FOINS»DIV,PROD,SINU,CObI ,PuIb»brMBSI (LYMB-LUS 1100,101,100SI (LYMB-MOlNS) 102»101,102SI C.YMB-NI V)103»101,103SI (LYMB-MROD>104»101»104SI (LYMB-INU)105»101,105SI (LYMB-LOSI 1106,101,106SI (LYMB-MUIS)7,l01 ,7MISE EN RESERVEAPPFL P A R M T 4 I C O N T I L N ) » ISl, IS2»i>YMB)APPEL RECURSIFST01=VAL(IS1,T)IMPRIMER lll.STOlRECUPERATION DE LA PREMIERE MISE EN RESERVEAPPEL RESTR4(MG»IS1,IS2»SYMB)APPEL INTRDI(MG,LN)SECONDE MISE EN RESERVE DANS LES PILESAPPEL PARMT5(CONT<LN),IS1»IS2.SYMB,ST01)DEUXIEME APPEL RECURSIFST02=VAL(IS2,T)IMPRIMER 112.ST02RECUPERATION DANS LES L I S I E b PILEsAPPEL RESTR5<MG»IS1,IS2»LYMB»ST01)APPEL INTRDI(MG»LN)A I G U I L L A G ESI (LYMB-LUSll.8,1SI (LYMB-MOINS)2,10»2SI ( L Y M B - N I V » 3 » 1 1 » 3
SI (LYMB-MROD)4»12»4SI(LYMB-INU)5,15»5SI (LYMB-LOSI)6,13,6SI <LYMB-MUIS)7,14»7OPERATIONS ET RECHERCHE DE LA vALEuR PARiIELLEVA=ST01+ST02ALLER A 17VA=ST01-ST02ALLER A 17VA=ST01/ST02ALLER A 17VA=ST01*5T02ALLER A 17VA=SINF(ST01)ALLER A 17VA=COSF(ST01)ALLER A 17VA=ST01**ST02IMPRIMER 114»ST01»ST02ALLER A 17RECHERCHE DE LA VALEUR D,UN SYMBOLEVA=VALO(SB,T)V A L E U R = V AIMPRIMER 113, VARETOUR 'MODELE(7(1X,012),3X,5HSYMB=,O12)MODELE! 5>H LN= ,012)MODELE16H ST01= ,012 »/ / )MODELE(6H ST02= ,012 , // )MODELEI5H VA=,012,//1MODELE ( 5X,5HSTO1=»F8.4»5HST02=»F8.5)FIN
FONCTION VALEUR (L, TABLE)
SÏHB = opérateur SB = Symboledu niveau considéré
151 « adressa 1er terne
152 « adressa 2e terra
I
Pig. V»2
SWB t +
_=/ STUB j -Mise en réserveST01 = Valeur (lS1)RécupérationMise en réserveST02 = Valeur (lS2)RécupérationVA = ST01 + STO2
>
Mise en réserveST01 = Valeur (IS1)RécupérationMise en réserveST02 = Valeur (lS2)RécupérationVA = ST01 - ST02
SYJΠi *
SYHB i /
SYKB i SIN
SÏMB : COS
SÏMB i * *
Mise en réserveST01 = VALEUR (IS1 )RécupérationMise en réserveST02 = VALEUR (lS2)RécupérationVA a ST01 * ST02
Mise en réserveST01 = VALEUR (lS1)RécupérationMise en réserveST02 = VALEUR (lS2)RécupérationVA = ST01 / ST02
Mise en réserveST01 = VALEUR (lS1 )!RécupérationVA = SINP (STOI)
Mise en réservaSTOI = VALEUR (lS1)RécupérationVA = COSF (ST01)
Mise en réserveST01 « VALEUR (lS1 )RécupérationMise en réserveST02 = VALEUR (lS2)RécupérationVA = ST01 ** STO2
VA = VALO (SB) TABLEValeur numérique dusjrmbole considéré
VALEUR = VA
VSortie
. V 3
FONCTION LADDRE
*VAL
VAL
AAAB
MGB
AUX
COMPTENTREESXATEDRADSORRADSRATEDRADSRATSXTSXTSXTSXTSXSORTEDTSXTSXRADEEXTRABCSFIN
18VALMGB»4=HENTVAL$( IMP)21,4AA=HAAVAL2.4.ABSPÂRMT8»MGBSVALEUR?***#AUX=HAUXVALSRESTR8»MGBAUX** »43,41
PONCTION VAL
*LADDRECOMPTENTREE
LADDRE SXARADSRARADDAGSSTTRA
MG EEXAUX BCSDEUX OCT
F I N
12LADDRE
ÎVALEURAUXAUX18DEUX
Pig. V-4
000002000000Pig. V-5
PONCTION VALO (SÏMB, TABLE)
Entrée
_L1 = 1 .
SYMB - TABLE
V1 = 1 + 1 VALO = TABLE CI + D]
PIN
Extrait de la table des symboles : TABLE (N) la valeur du symbolequi lui est adjacent
Pig. V 6
31
FONCTION V A L O I L B f N )DIMENSION N ( 5 0 )1 = 1SI ( L B - N U ) ) 1 * 2 , 11 = 1+2ALLER A 3NALO=N(1+1)APPEL INTRDD(NALO,VALO)IMPRIMER 5 » L B , N ( I ) , V A L ORETOURM O D E L E ( 5 X » 3 H L B = , A 6 , 5 X , 2 H N = 9 0 1 2 , 5 H V A L O = , F 5 . 2 , / / )FIN
Pig V7
RESULTATS Z = 7
«OCRE ( 0)-C11313CCOOCC- 0.1C146730E-19 «00 01-077313000000- 0.10746730E-19
SYMB ( OI -CC2CCCOOCQCC- O.OOOCOOOOE-38077AOC463374 C713C7COOOOO C77305000000
«00 (
«UX3A8I
0)-0021COOOOCCO- 0.14693679E-38
OI-OM574CCCOCC- 0. 89337571E-35
ADDPE ( 01-002100014574- 0.14699353E-38
SYHi! ( 01-060000000000- O.OOOCGCCCE-24
VAS ( 01-202600000000» 0.30000CCCE Cl
077400463314 C71307COOOOO 077305000000C114CC't3314 C173C7CCOOOC C77305000000 202600000000
ADORE ( OI-077311C71311- C.106474C6E-19
SYMB ( 01-CC2CCCCCCCCO C.CCOCCOOCE-38C77400473332 C77277000000 077303000000
AOO ( OI-0773C1CCCOCC- 0.10217334E-1907740C473332 C11275COCCOO C77271000000
«DORE ( OI-OC22C0014Ï71- 0.293S3C69E-38
SYHB ( 0) -OS646CCCCOCO- 0.12278461E-24
VAS C 0)»2024COOCCGCO C.200COOOOE 01
ADD I
ADORE <
SYHB (
•DO C
AUX3A8I
AUXVAL' .
Ot"0773110000CO- 0.10640C51E-19
0»-077301077301-
0)-005400000000-
01-002200000000
01-014571000000-
01-202400000000
ST01A3I O-2C24CCOCCOCG- C.2CCCOOCOE 01C77«OC473332 C7727500COOO 077271000000
C77400473332 077275COOOOO 077271000000 AOOPEOI400001-077273077273-
AOO ( OI-C11273CCOOOO- C.09899697E-190774CC473332 C77265CCOCGC 077265000000
ADORE ( OI-C77267071267- C.OS6944ÎCE-19
SYHB ( 0)-OC2CCOOOCCCO- C. OOOOOOOOE-38C77400473322 C17261CCOOCC 077257000000
ADO I C)-CTi263CCCCCC« 0.0941618CE-19C7740C473332 C77255COOOOO 077253000000
SYM6 ( 01-002346000000-
«00 I 01-077267000000
ADORE • OI-077263C772O-
SYKE I OJ-005400000000-
0.1Q223CC8E-19
0.47C19774E-37
0.293C73Ï9E-38
0.86632274E-35
0.20CCOCCCE Cl
0.09906249E-19
0.528C5410E-38
O.C9667939E-1S
O.OÎ4Ï273ÎE-1Ç
0.47C1S174E-37
ADORE ( CI-CC23CCG14Ï66- 0.44C66747E-38
SYHB I OI-05COOCOOCCCC- O.OOOOOOOOE-26
VA8 >T 0)-2C2C2C7in4> C.3141590CE 01
AOO ( OI-0023000000CO
AUX3A8C 01-014566000000
A U X V A L I 01-202622077174
ST01A3I GI-2C2622C77174- 0.3141Î900E 010774CC473332 C 7 7 2 Ï 5 C C C C C C 077253COCOOO
C77400473332 07725500COOO 077253000000 »OOPEO(62200)-007000014534-
ADO ( OI-CG7CCCOOCGCC- O.OOOOOOOOE-36
AUX3A8J Q!-0!4Ï34CCCCCC» O.S18144C7E-35
âUXVALC OI-177S25252525- 0.33333333E-00077400473332 C772SSGOCOCO C77253GOOOOO
VA3 ( 0)-2014140!2122- C.1C471966E 01
SYHB (
VAS !
STC2*3<202622077174
«UXV/LI
01-001400000000-
OÎ=Ï77525252S25»
0)-177525252525-
C.44C81C38E-38
0.87926917E-35
C.3141ÏÇCCE Cl
0.00001819E-36
0.29381359E-3B
0.33333333E-CC
0.33333333E-OC
0)-201414052122- 0.10471966E 01
ST01AK OI-2C1414052122* 0.1C471966E 01C7740C473232 C77261CCOOOO C77257COOOOO
077400473332 077261000000 077257000000 AOOPEO(414001-002400014563-
ADO I OI-CC24CGOCGOCC- 0.58774718E-38l
AUX368t 0)-014Ï63CCCCCC- 0.67221681E-35
4UXVAK 01-201414052122- 0.10471966E 01077400473332 C77261COOOOO 077257000000
VAl OI-2C2414052122- 0.20943933E 01
ST01A61 OI-2C2414052122- C.2C943933E 01C77400473332 077265CCOOOC 077265000000
SYHB (
V A S I
STC2AK201414052122
*UXV«L(
VA6 (
0)-062100000000"
0)-201414052122«
01-201414052122-
0.58780424E-38
0.04135ÇC3E-23
0.10471966E 01
0.1C471966E 01
«UXVAU 01-517777777133 — C.49999843E-00 STC2A3I077400473332 C77275000000 077271000000 202400000000
VA3 I OI-6CC777777133 —C.S9999686E 00 *UXV«U
0)-202414052122- 0.20943933E Cl
OM577777777133— 0.49^9e43E-CC
01-577777777133— 0.49999843E-CC
01-600777777133— 0.99999teÉE CO
ST01AK OJ-6CC777777133—C.99999686E 00C77400473332 C77277COOCOC C77303000000
177400413332 0772770COOOO 077303000000 AOOPEfl(777701-002500014561
«DO ( O-CC2ÎOCOCCOCO- 0.734âC397E-38 SYHB (
AUX3A8( OI-C14Î610CCOOC- 0.66751483E-35 V«B (
AUXVALI OI-2C3ÎOOOOOOCC- C.4SSSS999E 01 STC2A1I077400473332 C77277COOOOO 077303000000 60077777713;!
01-000067000000-
01-203500000000-
01-203500000000-
0.73474ÎCIS=38
0.03156845E-38
0.499SS999E Cl
0.49999SS9E 01
VJ1 ( CI-2G34CCOOOG64- 0.4C00003UE 01
ST02«1( O-2C34CCOCCC64- 0.4COC003CE 01077400463374 C773C7COOOOC 0773C5CCOOOO
*UXV*l(
20260V«1000(
01-203400000064
01-203700000064
0.40000C30E Cl
0.1CCOCC3CE Cl
VALEUR DE LA FONCTION
Z - 7.00CC Fig. V. 9
- 61 -
II -6 - DERIVATION FORMELLE
Les calculateurs digitaux ne travaillent en général que sur
des nombres, aussi, si l'on veut calculer la dérivée d'une fonction
au voisinage d'un point, on calcule la valeur de cette fonction
au voisinage du point en question et on évalue le rapport des accrois-
sements de la fonction à ceux de la variable :r* f (X 4- A X) - f (X)y _ -_ -
û x
calcul s'effectuant sur des nombres, donc accessible au traitement
automatique, et donnant un résultat y1 numérique.
Le calcul de la valeur d'une fonction tel que nous l'avons
développé au chapitre précédent, laisse entrevoir la possibilité d'un
traitement quelque peu similaire, au point de vue de la reconnaissance
des symboles, permettant de calculer, grâce aux listes, la dérivée
formelle d'une fonction. En effet, dériver une fonction est une
opération complexe, difficile sinon impossible sans le concours des
soit y = W(x) + U(x) x V(x) + T(x)
la dérivée sera y'= W + (U'V + V'U) + T'
formule bien plus longue que celle de y. Ajouter des lettres, des
symboles dans une fonction linéaire, représente un travail très com-
pliqué, Mais si l'on travaille sur des listes, il n'est Jamais diffi-
cile d'accrocher une sous-liste en un point quelconque d'une liste.
Il suffit d'être à même de calculer la dérivée de chaque groupe de
symboles, et d'intercaler cette dérivée dans l'ensemble. Nous avons
pour cela choisi la notation polonaise préfixée, définie au chapitre
précédent, ce qui nous permettra aussi de calculer la valeur de la
fonction dérivée.
Le programme mis au point n'est qu'un exemple, mais son
fonctionnement satisfaisant montre qu'il est possible de le géné-
raliser et de dériver des formules plus compliquées. Nous n'avons
traité que les fonctions Addition - Soustraction - Produit - Division -
Puissance - Sinus - Cosinus relatives à des constantes, à la variable x
ou à des fonctions de x. Tout le raisonnement est relatif au cas le
plus général : les fonctions de x
62
(U +
(U - V)1
(U.V)!
(uA)1
(Sn U)
(Co U)
U' + V'
u! - VU'V -f V'Uu'v - v'u
U'.Co U
- U' Sn U
(+, U, V)
(-, U, V)
(*, U, V)
(A u, v)(Sn,U)
(Co,U)
(+. u1, V)(-, U', V)(+(,*, U1, V) (*, U, V1))
(/(-(*,Uf, V)(*,U,V'))(**,V,DEUX)
(*,U'(Co U))
(*, MUN(*, U' (Sn (U))))
La procédure sera une procédure recursive. Pour calculer la
dérivée de UxV on fera «dérivée (U * V) = dérivée (U) * V+ U * dérivée(V)
dérivée(u) = = D1 - dérivée(v) = = D2
etdérivée (U * V) = Dl * V + U * D2
On s'arrêtera lorsque l'on arrivera à "dérivée d'une constante"
ou dérivée (X) en fournissant dérivée (C ) = 0 , dérivée (X) = 1.
Ce procédé est assez lourd, mais la possibilité du travail
récursif fait que le programmeur n'a plus à s'en soucier. Cependant,
de par le mode même de traitement, on ne s'arrête qu'en fournissant
ZERO ou UN, ce qui fait que subsisteront de nombreuses cellules inutilesl
(A.X) = (x, A, X) —*• (+ (*, ZERO, X) (*, A, UN)) ce qui une fois
simplifié pourrait s'écrire (A). On peut concevoir un programme acces-
soire de nettoyage, travaillant à la suite du programme de dérivation,
aboutissant à éliminer toutes les cellules superflues. Cependant, ces
cellules ne nuisent pas à l'exactitude du résultat et ne constituent pas
un obstacle à l'évaluation de la VALEUR de la formule dérivée pour une
valeur déterminée des constantes et de la variable X.
Le sous-programme de dérivation s'appelle DERIVE. Il appelle
le sous-programme DERI qui sert uniquement d'intermédiaire à l'appel
récursif. Ce procédé de traitement est tout à fait analogue à celui de
VALEUR .. Ponction DERIVE fig. VI.2 Programme de calcul et fonction DERI
fig. VT.1 Calculs fig. VI.3 à fig. VI.\\ .
Le procédé de calcul est voisin de celui de VALEUR. La structure
de la liste est la même. Pour dériver U.V.W qui s'écrit en notation
polonaise (*,U(*V,¥) on calculera dérivée (ïï) puis dérivée (V W)
dérivée (v.W) nécessite dfabord dérivée (v) et dérivée (w) ces deux
dernières obtenues, on bâtira la structure
(+(*(dérivée (U))V) (*,V (dérivée (w)))
dont le nom de liste sera la valeur de la fonction DERIVE et ainsi de
suite.
Le mécanisme de récursivité est le même que celui de Valeur. Mise
en réserve et récupération :
du symbole opération SYMB
des adresses des sous listes ou paramètres IS1 IS2
symboles ou paramètres SIMB 1 SÏMB 2
adresse de retour MG (?66)
valeur intermédiaire STO 1
Quand on remonte les adresses de retour* on bâtit la structure
grâce aux structures partielles déjà bâties. Quand les piles sont vides,
on revient au programme principal.
CALCUL DE LA DERIVEE D'UNE FONCTION
PROGRAMME PRINCIPAL
CCADERIVEE D'UNE FONCTIONDIMENSION X ( 1 0 0 ) « L A V S ( 2 ) » L E T T R E C 3 6 ) » M O T ( 2 1 6 ) « T A B L E ( 1 0 0 )COMMUN C R E F » X , L A V SAPPEL INITEDLIRE ILLETTREIMPRIMER ILLETTREAPPEL S E P A R E ( L E T T R E * M O T )APPEL F L S T P ( M O T , L A )APPEL I M P L S T ( L A » L 5 L , L , L )L = L I S T E ( 9 )APPEL INSIND(-1,LA,LA»L-1)D = D E R I V E ( L )IMPRIMER 13»DAPPEL I M P L S T ( D » L » L , L » L )APPEL L I S S Y M ( D » T A B L E )IMPRIMER 20 ,TABLE
1 MODELE(5X ,11A6)13 M O D E L E ( 5 X » 5 H D E R I = » 0 1 2 » / / Ï20 MODELEt1HO,12A6)
APPEL E X I TFIN
FONCTION DERI
*DERI
DERI
AA
MGB
AUX
COMPTENTREESXARADSORRADSRATEDTSXTSXTSXTSXSORTEDTSXTSXRADEEXTRABCSFIN
20DERIMGB, 4$(IMP)21,4AA=HAADERI$PARMT8*4MGBSDERIVE,4#iV
AUX=HAUXDER$RESTR8»4MGBAUX**,4.2 *41
Fig. VI. 1
os
FONCTION DERIVE(L) 'DIMENSION MG(2)PLUS=2H++ 10FOINS=1H-PROD=1H*DIV=1H/SINU=2HSNCOSI=2HCO 11PUIS=2H«*XX=1HXUN=2HUNDEUX=3HDEU2ERO=3HZERUNM=3HUNMAPPEL INTROD(PLUS.LUS)APPEL INTROD(FOINS,MOINS)APPEL INTRDD(PROD.MROD)APPEL INTRDD(DIV.NW)APPEL INTRDD(SINU.INU)APPEL INTRDD(COSI»LOSI)APPEL INTRDD(PUIStMUIS) 12IDD=LSG(CONT(L-1))VAR=CONT(L-1)SYMB=CONT(LSD(CONT(IDD))-l)APPEL INTRDOtSYMB,LYMB)IMPRIMER 30.SYMBIS1=LSD<CONT(LSD(CONT(IDD))))IS2*LSD(CONT(IS1»SYMB1=CONT(IS1-1)SYMB2=CONT(IS2-1)SI<LYMB-LUS)100f101»100
100 SI(LYMB-MOINS)102.101,102102 SI <LYMB-NIV)103»101»10?x103 SI(LYMB-MROD)104,101*104104 SI(LYMB-INU)105,101*105105 SI (LYMB-LOSD106,101*106106 SI(LYMB-MUIS)7,101,7101 APPEL PARMT6(MG(766)>IS1.IS2,SYMB1»SYMB2»SYMB)
ST01=DERI(IS1)IMPRIMER 31»ST01APPEL RESTR6(MG(766),IS1,IS2,SYMB1.SYMB2 »SYMB)APPEL PARMT7(MG(766),IS1,IS2.SYMB1»SYMB2,SYMB»ST01) 13ST02=DERI(IS2)IMPRIMER 32»ST02APPEL RESTR7(MG(766)*IS1,IS2,SYMB1»SYMB2»LYMB»ST01)SI(LYMB-LUS»1»8,1
1 SI(LYMB-MOINS)2.10»22 SI(LYMB-NIV)39l2»33 SI<LYMB-MR04)4,11.44 SI(LYMB-INU>5»13»5 145 SI<LYMB-LOSI)6,14»66 SI<LYMB-MUIS)7,15»78 LA=LISTE(9)
APPEL NVQU(PLUS»LA)APPEL NVQU(STOl.LA)
APPEL NVQU(ST02»LA)ALLER A 17LA=LISTE(9)APPEL NVQU(FOINS.LA)APPEL NVQU(ST01»LA)APPEL NVQU(ST02»LA)ALLER A 17L2=LISTE(9)L1=LISTE(9)LA=LISTE(9)APPEL NVOU(PROD»L1)
NVQU(ST01»L1)NVQU<SYMB2»L1)NVQU(PROD»L2)NVOU(SYMB1»L2)NVQU(ST02»L2)NVQU(PLUS»LA)NVQU(L1,LA)NVQU(L2,LA)A 17
NVQU{PROD,L1)NVGUCL2.L1)NVQU(ST01,L1)NVOU(SINU»L2)NVQU(SYMB1»L2)A 17
APPELAPPELAPPELAPPELAPPELAPPELAPPELAPPELALLERLA=LISTE(9JL1=LISTE(9)L2=LISTE(9)L3=LISTE(9)L4=LISTE(9)APPEL NVQU(PUIS,L2)APPEL NVQU(FOINS»L1)APPEL NVQU(L3,L1)APPEL NVQU(L4,L1>APPEL NVQU(DIV.LA)APPEL NVQIMPROD.L3)APPEL NVQU(PRODtL4JAPPEL NVQU(SYMB1»L4)APPEL NVQU(ST02,L4)APPEL NVQU(STO1»L3)APPEL NVQU(SYMB2,L3)APPEL NVQU{SYMB2.L2)APPEL NVQU(DEUX»L2)APPEL NVQIMU.LA)APPEL NVQU(L2»LA)ALLER A 17LA=LISTE(9)L2=LISTE(9)APPEL NVQIHCOSI »L2)APPEL NVQU(SYMB1»L2)APPEL NVQU(PROD.LA)APPEL NVQU(ST01»LA)APPEL NVQU(L2,LA>ALLER A 17LA=LISTE(9)L1=LISTE(9)L2=LISTE(9)APPEL NVQU(PROD.LA)APPEL NVQU(UNM-LA)APPEL NVQU(H,LA)
APPELAPPELAPPELAPPELAPPELALLER
15 LA=LISTE(9)L1=LISTE(9)L2=LISTE(9)L3=LISTE(9)APPEL NVQU(PROD.LA)APPEL NVQIMSYMB2.LA)APPEL NVQU<L1,LA)APPEL NVQU(PROD.Ll)APPEL NVQU(L2.L1>APPEL NVQU(STOl.Ll)APPEL NVOU(PUIS.L2)APPEL NVQU(SYMB1»LZ)APPEL NVQU(L3,L2)APPEL NVQU(FOINS»L3)APPEL NVQU(SYMB2»L3)APPEL NVQU(UN,L3)ALLER A 17
7 SI<VAR-XX)20,21,2021 DER=UN
APPEL INTRDD(DER»LA)ALLER A 17
20 DER=ZEROAPPEL INTRDD(DER»LA)
17 APPEL INTRDDILA,DERIVE)IMPRIMER 33.LARETOUR
30 MODELE(5X»A6,5H=SYMB.//)31 MODELE(5X,5HST01=,012»//)32 MODELE(5X,5HST02=.012.//)33 MODELE(5H LA=,012,//)
FIN
to
s:
r?"
Sia
mmSsfiip!
DERIVEE D»UKE FOlSCTION
Fonction dérivée sous foiae de liste
.= C ? 7 2 2 7 C 7 7 2 2 7 LÛ=C77227077227 L t=077227077227
i'tti 1 7 C ' i < 2 2 3 C U C C C t U C C C
1 'It i < '• C 7 ( < 1 7 C 7 < 1 7 7 L 7 1 « 7 7
; ; t ï i £C- |é£ t l C C C C C C C C C C L 2
l U 5 7 7 C 7 t b 5 7 2 C 2 C t C 6 C b C 6 0
ntït i i ï t î i t ciefacuifctu
276571C76575 OCC000000001
C766C1C76573 ÏA606C6C6060 *
C76575076571 7125516C6060 ZER
176573C76601 C773C1C77301
277271C7727£ C C I C C C C C C C C *
0773C1077273 5 4 Ï 4 6 C 6 C 6 C 6 C **
0 7 7 2 7 5 C 7 7 2 7 1 6 7 4 C 6 C 6 C 6 C 6 C x
077273C773C1 2<25i<
C 7 6 6 C 3 C 7 6 É C 3
276563C76567 OOOOCC000001
C766C3C76565 5^606C6C6060 *
C76567C76563 21606C606060 A
176565C76603 C76dA3076643
276627076633 C C C C C C C C C C C 1
076t^307t t31 £ ' (ÉC6CtC6C6C »
C 7 6 6 3 3 C 7 6 6 2 7 2 1 2 Î 6 A 6 7 6 C 6 C DEUX
176É31076643
C C C C C C C C C C C 1
2 C 2 C 6 C e C 6 C 6 C
276243C76247 OûCCCCOOÛOOl
C762Ï3076245 516C6C6C6060 *
C76247076243 712551606060 ^ER
1762^5076253 077257077257
2 7 7 2 4 7 C 7 7 2 5 3 C C C C C C C O C O O A
177253077257 C 7 7 2 5 1 C 7 7 2 5 1 .
276235076241 000000000001
C7É255C76237 54606C6C6060 *
C762A1076235 226C6C606060 B
176237076255 0763C3076303
27627107627Î C C C C C C C C C C C 1
0763C3C76273 E « e C 6 C é C 6 C 6 C *
076275076271 « 4 4 5 4 4 6 C 6 C 6 C uj
176J73C763Û3 C763C1C76301 ..
Pig VI 6
VADEVA C A L C U L DE LA VALEUR D'UNE FONCTION,DE SA DERIVE!:' ET DE LA V A L E U R
10
20
17
211
1315100101
DIMENSION X( 100), LA V S ( 2 ) , LETTRE (36) ,MOT (216) ,T ABLE(200 ) ,T AB< 200 )COMMUN CREF,X,LAV$APPEL INITEDIMPRIMER 2LIRE 1,LE11REIMPRIMER 1, LETTREAPPEL 5EPARE(LE11RE,^G1)APPEL FLSTP(MCT,LA)APPEL I*PLSTUA,L,L,l,l)L=LIS1E(«)APPEL INSIND(-1,LA,LA,L-1)APPEL TABSYMLA, TABLE)FAIRE 1C I*2tlC,2LIRE 11,1ABLE(I)IMPRIMER 1A, TABLEV = V A L E L R ( L , T A B L E )IMPRIMER 13, VC*DERIVE(L)IMPRIMER 15, CAPPEL IMPL5T(D tL ,L ,L ,L )L V = L I 5 T E ( S )APPEL INSINO(- l fD,D,LV- l )APPEL T A B S \ M ( D t 7 A B )FA IRE 2C 1 = 2, 2C, 2LIRE 1 1 , 7 A R ( I )IMPRIMER 14, T A BV = V A L E L R ( L V , T A B )IMPRIMER 13, VLIRE 1CC,BLF A I R E 17 Î = 1 , 2 C CT A e ( I ) = B LAPPEL L I S S Y M C C , TABLE)IMPRIMER ICI, TABLEAPPEL E X I TM O C E L E ( 5 X , 1 1 A 6 )M O C E L E ( 1 H , 5 X , J 6 H F C N C T Î C N A DERIVER,/ / / )MCOELE(F lC. l )M O O E L E ( 5 ( 5 X , C 1 2 ) )MODELE(1H,5X,21HVALELR DtË LA F C ^ C T I C ^ ,5 X ,F10 .6 ,/// 1M.ODELE(1HÎ,5X,«HOERI\EE= ,C12)M,OOELE(012)M O D E L E ( Î H 1 , 5 X , 1 6 A 6 , / / )F1N( 1,1,C, C , C , C , l t C , C , l , C , C , . C , 0 , C )
Fig. VI. 7
CALCUL DE LA VALEUR DE LA FONCTION AVANT DERIVATION
UUL1S FK. lhSI lS tt LA V É L f c l P C E LA FCNCUCN A V A N T DERUAUCN
0 < i C 6 C t C t t £ C 6 C £ 1 £ C 6 U C 6 C 6 C i 4 6 C 6 C t C 6 C 6 C 624560606C60 2346606C6060 5<t546C606060L 7 3 7 C 1 C C O C C C ( 7 7 3 C 7 I C L C C C C 7 7 2 6 5 C C C L C C 202C6C606C6C
= 2C2C6C6C6C60
A A V A L { C )=OC74GCOC7547= 3840, 3943
F A H M 4 C 6 b 7 t * C C C C C C
bM\i<F/HM t ( 7 7 « C C 4 7 C £ î I
irv= tco i6toi,otij
t2456C6C6C60 23^.660606060 54546C606060 S Y M B = 5 < i 6 C 6 C £ C 6 C £ Cl 7 7 3 t 3 C C O C C C C77277GCOOOC 5460606C6C6C
A A V A L ( CJ=CC7400007547= 3810, 3943
£ 1 £ ( £ C £ U C 6 C= 3 .CC
6 2 4 5 6 C 6 C 6 C 6 C 23466C6C6C60 S4546C606060 S Y H E = C C C C C C C C C C C C
A *3.
C ) =
2(26CtCCCCCC
it C t ! i 7 t 4 C C O ( CC
i O t 5 7 £ * C C O C C C
t 0 ) = C
= C . 3 C C C C C C C E C l
3.
C77^77CCCCCO 546C6C6C6C6C
C 7 7 2 7 7 C C C C C C 5^t6C6C6C6060 2C260000COOOfc M VA (.(28336) =063051256225=
ii 'C,
2 C 2 C t U C 6 U O ' , C 6 C é C 6 C t C 6 C t U C 6 C f C t 0 6 C Ï46C6C6C6060 62456Û606C60 23466C606060 5454606C6060 SYHB=54546C6060tG(, O t 5 7 t ' C C C C C C C 7 7 i 7 3 ( C C C C C C 7 7 2 7 1 C C C G C C 54546C606060
tNTVA I(29C341=C£C100C21307=
2 C 2 C t t K 6 C é c " c 6 C é C É C i C 6 C £ 1 £ ( £ C < C ( C 6 C Ï 4ÉC6C6C6C6Û 62156C6C6C6C 23466C60£C60 545460606060 SYH6=OU6COCCOOCC1
J- K" X . H / 2
AtXVAH OJ=roi622076454= 0.157C7900E 01
07«£< X=PI/2
0 6 5 7 6 ' t C C O C C C C 7 7 i ' i 3 C C C C C C
c £ £ " i £ A C c c c c c mnsccccu
f M \ / l t ? F ? £. d 1= f ï : C i J J ' < Î i î =
C77271CCCCCO 545460606C60
C 7 7 2 7 1 C C C O C O 54546C6C6C60 201622076454
A A V A l ( C)=CC74C0007546= 3340, 3942
2 0 2 0 < C É C 6 C 6 C L ^ C 6 L é C t C t C 6 C t l £ ( £ C £ t < C 6 C î 4 6 C 6 C t C 6 0 6 0 62456C606C60 234660606060 545460606060 S Y M B = C C 6 C O C C O C C C 1
3= 2 * C C DEUX = 2.
C J ^ i C i l C C C C C C C C ^ C . i C C C C C C C E C l
C 7 7 2 7 2 C C C C C C C77271CCOOCO 54546C6C6C60 201622076454
J1 C J = 1.51CtSUi= 2 . C C C C C
X= 2.467 AUXVAH 0)=2C2473646225= 0.24673811E 01
t 0 6 5 7 6 1 C C O O C C C 7 7 2 C 3 t C C C C C C7727700QCCC 546060606060 202600000000
V / = ; C 3 7 3 1 t 7 1 3 3 7
VI 8
/ L > V / L I 0)=iC3-|2F . E S 1 F E C 7 7 4 C 0 4 7 C Ï Î 2
(373 157 1337
l337= C .1«Ci l433E Cl
=7.402
FES7F1 - C 7 2 7 C 2 C C O O C C C 7 7 3 Î 7 U C C C C C77265CCCCCO 2C2C6C6C6C60
F A R M S 0 7 3 7 C i C C C O C C C 7 7 2 1 7 ( C C C C C C 7 7 2 6 5 C C C C C O 2C2C6C6C6C60 203731571337ENTVAl(289981=063051256225=
3S42« C J = C C 7 4 C C C C 7 Î A £ = 2F A F M 8 C 7 7 4 C 0 4 7 C 5 G 6
LN= C C £ 7 1 6 C O C O C O20206C606C6Û 4 0 6 C 6 C 6 C 6 C 6 C £ 1 6 C £ C £ C £ C 6 C Ï46C6C6C6060 62456C606C60 234660606060 545460606060 S Y M E = 5 1 6 C 6 C £ C £ C £ C *
0 6 5 7 É 4 C C O C C C C 7 7 i £ K C O O C C C77255CCCOOÛ 546C6C606060EMVAH29C34) = 060 100021307=
I 0 ) = C C 7 « C O C C 7 Ï 4 7 =
LN= C C 6 7 1 6 C C C G C C2 C 2 0 e C £ C 6 C 6 0 1 C é C £ C £ C 6 C t C £ l £ ( £ C £ C t C 6 C S46C6C6C6060 C2456C6C6C60 234660606060 545'.60606060 S Y H B = O C C C O C C C C C 14
LE=E N = 2 2 < C t C « C £ C £ C V A L O = 1.50B «= I..)
V A = 2 C 1 6 C C C O C O C OA U > V A L ( C1=2C1600CCCOOO= C .150COCCOE Cl
S T C l = i ( J 6 C C O C C C O G
J E S 7 F 4 0 6 5 7 6 4 C C O C C C C 7 7 i < l C C C C C C C772550000CO 546C6C6C6C60
C 7 7 2 1 H C C C C C C 7 7 2 5 5 C C C O C C 546C60606060 2C160000COOO
A A V A L J C)=0074000C7546= 38^0, 3942
IA= CC6716CCCOCO2C2CtC£C6C6U 4C6CtCeC£C6C <16C6C£CéC6C 546C6C6C6060 62456C6C6C60 23^660606060 545460606060 SYMB=23466C6C6CéCFARMA Û65764CCOOCC C77247CCCGCO (77257CCCCCC 23466C606C60 Cos
E N T V X L (29C24 ) = C'6C ICûCi 13C7 =F A R M 6 ( 7 7 4 C Û 4 7 C 5 £ 2
A A V A L ( 0 )=OC7400007547= 3810, 3943
LN= C C 6 7 1 6 C O C O C C2 C 2 0 « C e C 6 C £ 0 1 C 6 C £ C £ C t C t C * l £ C £ C t C é C 6 C Î16C6C6C6060 62456C6C6C60 2346606C6C60 5454606C6060 S Y H B = 2 C 2 C 6 C 6 C 6 0 6 CFARM4 0 6 5 7 6 4 C O O C O C C 7 7 2 1 K C C C C C C772310CCCCG 202060606060
E N T V / L 1 2 9 C 3 4 ) = C £ C l C O C i l 3 C 7 = A A V A L ( 01=007400007547= 3840, 3943
IN= C C 6 7 1 6 C C C O C O2 0 2 0 £ C £ C £ C £ 0 1 C 6 C £ C É C é C É C £ l £ C £ C t C ( 0 6 C Ï4£CCC6C6060 62456C6C6C60 23466C606C60 54Î46C606060 S Y H E = 5 1 6 C 6 C é C 6 C £ CFARHT4 065764CCOCCC C 7 7 2 3 Ï C C O C C C C772330000ÛG 546060606060
E M V / L I29C31 J = C £ C 1 C C C 2 13C7= A A V A L I 0) = OC7400007547= 3840, 3943
LN= C C 6 7 H C G C G C O2C2Cét iC6CéC A C e C é C t C « C 6 C £ l é ( 6 C < C £ C 6 C î<p6CÉC6C6060 62456C6C6C60 234660606060 545460606060 SYHB = C C 6 C C C C C C C C 1
LE = C N = i 3 £ C £ 0 £ C £ C 6 C V < L O = C.5C 0 = 0.5
V A = 2 C £ 4 C C C O C O C O
C 1=2CCUCCCCCGC= C . 5 C ( C C C C C E CC
S T C 1 = 2 C C 4 C C O C C C O O
RESTR4 0 6 5 7 6 4 C C O C C C C 7 7 2 2 î C C C t C C C77233000000 546060606060
FARMS 0 6 5 7 É 4 C C O O C C C 7 7 2 2 Î C C C C C C G77233CCOCCC 546C6C6C6C60 200400000000ENTVAL(28998)=063051256225=
A A V A L I 0 ) = C C 7 4 C C C C 7 S « 6 = 384C, 3542F A R M 6 C 7 7 4 C 0 4 7 C 5 0 6
LN= C C 6 7 1 6 C O C O C O2 0 2 C £ C É C 6 C 6 C 4 0 6 C £ C 6 C £ C 6 C £ l £ C 6 C t ( £ G 6 C Ï4£C6C6C6060 62456C6C6C60 234660606060 545*60606060 SYHB=OC6CCCOOOOC1
LE = X I > = 6 7 £ C 6 C 6 C £ C 6 C V A L O = 1.57 X = PI/2
V A = 2 C l £ 2 2 C 7 £ 4 ï 4
».UXVAL( 0)=2C1622076454= 0.157C7900E 01F E S T F £ C 7 7 4 C 0 4 7 C 5 0 é
FES1R5 065764CCOOGC C 7 7 2 3 Ï C C C C C C C77233GOOOOC 546060606060 20C400000000
VI 9
f f c i lK O É 5 7 < * l t O C C C
C J =
; î< * C . 7 1 Î 2 S S C C E C C
C X = PI /4
l l i i ' lUCCCC
( 7 7 ; < K C C C C C
l~ 2 £ < C , 2542
C 7 7 2 3 1 C C C C C C 2C2C6C6C6C60
C 7 7 i 3 1 C C O C C C 2 C 2 C 6 C 6 C 6 C 6 0 20C622076454ENTVA 1(28998)=063051256225 =
U= CCt716COCOCO2C^Lf L6C6C6U
174
6^!456C6C6C60 2346606C6060 545460606060 SYf,E=CC6COCCCOOC l
PI
A L X V A l t 01=202622077174= 0.31415900E 01
C 2 6 2 Z C 7 7 1 7 4
06 i ' ie4( .CCt t ( C 7 7 2 M C C C C C C C 7 7 2 3 1 C O O C C C 2C2C6C606C60 200622076454
;;i«i 1 6 7 ( 7
l U ) = 2 L 2 7 < 6 î 1 < 7 ( 7 = C . 3 * i t « . £ 5 C E C l( 7 7 4 L 0 4 7 C S Ï 2
< 5 ) t 7 t 7 C X + D = 5.PI / 4
C Ê 5 7 f c 4 C C C C C C IV iZ^ lUCCCC C 7 7 5 7 C C C C C C
C 6 5 H 4 C C C C C C C 1 7 î ^ 7 ( C C C C C C 7 7 2 5 7 C C C C C C 234660606060 202766516707ENTVAL (289981=063051256225=
A A V * L I 0 ) = ( C 7 « C C C C 7 Î 4 6 = 2 6 4 C , 3942F A I . H E C 7 7 « ( C 4 7 C 5 C 6
ltv = C C 6 7 1 6 C C C O C C2 C 2 Û 6 C 6 C 6 C 6 0 4 C 6 C É C 6 C £ C 6 C 6 1 6 C 6 C 6 C 6 0 6 C 546C6C6Cô060 62456C6C6C60 23466C606C60 545460606060 SYMB=5COCOC012C27
e i f r c c c c c c c c c i v = c ceL =00000 N = L L Alr 'ALû
/i = C C 7 4 C C 4 0 2 7 7 4
S l F 6 ( 7 7 4 C 0 4 7 C 5 0 6
S 1 C 2 = C C 7 4 C C 4 C 2 7 7 4
F E S T I - î C 6 5 U 4 C C C C C C
A L X V A L I C)=OC74C0402774= 0.18345073E-36
C 7 7 2 5 7 0 C C O C O 234660606060 2027665167C7
• 1 . 7 C 7 1 1 C S 3 E C C
C" i ï< H C C C C C C 7 7 2 5 5 C C O O O O 546C6C6C6C60 201600000000
A U X V A L C C)=601417417524=-0.10606664E 01
Coa ( C X + D ) =>— 0.707
• t C 7 2 7 C K C C C C C C" i7217 ( C C C C C C77265CCOOCO 2C206C606C60 203731571337
c C . t < 5 6 6 . < c B . Cos ( C X + D )=-1.06
V / l t L F C t L A F C f ^ C ï l C N t .341477
P t S T ( - e C 7 7 4 C 0 4 7 C 5 C 6
S T C 2 = 6 C C i 5 i ( 2 4 7 C 6
S 0 6 5 7 6 4 C C C C C C
A X2 + B. COB (C X + D ) - 6.34
Avec AM 3. B-I.5 C = 0.5 D . PI et X = H/2
VI 10
CALCUL DE LA VALEUR DE LA PONCTION DERIVEE
CAULIS II Lfi t t J.A H.NUIIN APKci U b K l V A l U N
IN= C C 6 7 1 6 C C C C C C
2 0 2 0 6 C 6 C C C 6 0 4 C 6 C 6 C 6 C 6 C 6 C 6 1 6 C t C ( ( 6 C 6 C ï 4 6 C t C 6 C 6 C 6 C t24 i tC6C6C60 23466C6Q6G6C S4546C60606U S Y M S = 2 C 2 C 6 C 6 C 6 C 6 CF A R N T 4 C 7 3 6 1 6 C C C C C C ( 7 6 i i l C C C C C C t 7 6 2 i Y O C C C O C 2C2C606C6C60
E M V / L ( 2 S C 3 4 ) = C 6 ( ' l C C C i 1 3 C 7 = A A V A L ( C J=CC7400007547= 3840, 2943Lt t i
IM C C 6 7 1 6 C C C C C C
2 C 2 C 6 C 6 C 6 C 6 C 4 C 6 C 6 C 6 C 6 C 6 C < H ( 6 C < U C 6 C i4 tC6C6C6060 624i)6CfeC6C60 23466C6C6C60 54i460606060 SYME = 2 C 2 C 6 C 6 C 6 C 6 CFAPH4 0 6 i 7 6 4 L C O C C C C'it S Î 7 C C C C C C C 7 6 f > b t > L C C t L C 2C2C60606060
2 C 7 = A A V A L I • 0 ) = C 0 7 4 0 0 0 0 7 5 4 7 = 3840, 2S43
lh= C C 6 7 1 6 C C C C C O2 0 2 C 6 C 6 C 6 C 6 0 4 C 6 C 6 C 6 C 6 C 6 C 6 1 é ( 6 C < ( 6 C 6 C 5 4 6 C 6 C 6 C 6 0 6 C 6 2 4 5 6 C 6 C 6 C 6 C 2 3 4 6 6 C 6 C 6 C 6 0 Ï 4 5 4 6 C 6 C 6 0 6 0 S Y M 6 = 5 4 6 C 6 ( 6 C 6 C 6 CFARM4 Û 6 5 7 6 4 C C O O O C C ït i 1 2 C C C C C C 0 7bt ;71(JCCCC C 546060606C60
A A V A L ( C)=OC7400007547= 3840, 2943
LIS* CC6716CCOCCC202C6C6C6C6C 4Ctt6CtCtC6C 616C6Ct(6C6C £46C6(6Cù06C 624b6C6C6C6C 234660606C6C 5454606C606Q
LE = 2 t f i ^=^liïïl6C6C6CVALO= C.
V/!=CCCCCCCÛOCCO
V/=2CC417<16GÎ4
= CC6CCCCOCCC 1
0) = 2CC4]7< 16C24= ( .S 2 ( -itSSfc CCFESlF€C774CC47CtC6
PESI f .5 0 6 5 7 6 4 C C C C C C C U i î K C C L C C C 7 6 2 2 7 U C C C C 2 C 2 C 6 C 6 C 6 C 6 C 4 C C C C C C C O O O O
^ . S L b C 6 7
A U X V A L C C)=2C0417416024= C.53032699E 00
; ; i C C C ( . C C (76^17UtOC,CC 2C2C6C606060 2 0 4 4 E 5 4 b 6 7 4 0C73tlfC(CCtC
V / L t U I - U L/ K.hCT 1LN
Avec UN = I. ZER = 0 A = 3. B
et X t= PI / 2
C => 0.5 D = PI
Pig VI t1
FORMATION TE LA TABLE DES SYMBOLES
ZER 7 1 2 5 5 1 6 C 6 C 6 C-1 6C140CCCCGCO
DEIK 2425646jeC.eC0.5 2CC4CCCGCUCO
C C C C C O O O O O C CcccccccococccccccccoccccC C C Û C C C O C O C OcccococooccccccocccococccccccccocccccccccccoccccccccccccccccccccoccocococccccccococcccccccccccccoccococccoccC C C O C C C G C C C CC C C C C C C C C C C ûcccooccccocccccccccccocccccocococcccC C C O L C C C C C C Ccccocococccccccooccocccccctccccccococccccococococccccoccccccrrccccfccccc
o.ccccccccccccA 2 1 6 C 6 C 6 C 6 C 6 C2 ; 2 C 2 4 C C C C C C C CD 2 4 6 C 6 C É C 6 C 6 C
ccccccccccccccccccccccccccccccccccccccccccccccccccccoccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccc
TJN64456C6C6Û60 13. 2 C 2 6 C C C C C Û C O X
2 2 6 C 6 C 6 C 6 Û 6 0 1.5BTT
cccccccccoooC C C C C C C C C Û O CC C C C C C C C C Û O CcccccccccoooC C C C C C C C C Û C OcccccccccooocccccccccooocctccccccooocccccccccooocccccccccoccC C C C C C C C C Û C OC C C C C C C C C Û Û OcccccccccoooccccccccccccC C C C C C C C C Û O OC C C C C C C C C Û C CC C C C C C C C C Û O OC C C C C C C C C Û O OcccccccccoooC C C C C C C C C Û O OC C C C C C C C C Û O OcccccccccocccccccccccoooC C C C C C C C C Û O Occcccccccccc
2C14CCCOOQOf676C6C6060602C16CCCOOOOO6C140CCCCQOOCCCÛÛOCOOOOOcccooocooooocccococoooocCGOOOCCGOCOOCCCÛOOCÛOOOOcccccccccococcccccccocccCÛCOOCCCCOOOCCCOCCCOÛOQOCÛOOOOCOOOOOcccccococooocccooccccoocccccocccococcccoccccoccccccccocoooooccoccccoococCCCÛOCCOOOOOcoooooccoooocccccccoococcccccccccocccccooococooocccocccoooooCGCOOCGOOOOOcccccccococcCCOOCCCCGOOC
UM 64A5446C6C60
2360606C6C60ococcccoooooocccooooooooccccoocoooooccccoocooococoooooooooooccccoooooooooccoooooooooocooooooooooCCCGCCCCOGOOOCCOCOCOOCGOcccocoooocooGCCCCOCOOGÔOccccoocooooocccoooooooooCCGOOOOOOOOOccccccocooooccccccodccooCCOCCGOOOOCOccoccooooococccoocooocooccoooocoocooccoccooooocooccccooooococccoccoooooooccccoooooooCCOCOGOOOOOO
RESULTATS DE LA DERIVATION SYMBOLIQUE
Fonction sous forme Polonaise préfixée telle qu'elle ressort de la liste SLIP
rara
B
C
C
X
UN
ZER ( ** X
** X (
ZER ( Cos (
( * UNM (
( + ( +
DEUX ) ) ( * A
DEUX UN ) ) UN ) )
4- ( * C X ]
* ( Sin ( 4- 1
( * ZER X ) 1
) Df *
[ *ZER )
Cette fonction est équivalente à la notation courante :
( ZER x X2 + A X DEUX x X (DET3X " x U ff ) +
( ZER x Cos (C.X 4- D) + B x UM x Sin ( C.X + D) x ((ZER x X + C x UN) 4- ZER))
Cette écriture est évidemment plus longue qu'il n'est nécessaire car elle
comporte encore des termes surabondants. Une notation plus concise donnerait:
(A x X (DEUX ~ M) ) 4- ( B x TOI x Sin( C.X+D) x C )
En ne supprimant que les termes ZER x ... , en remplaçant les termes
ZER 4- ... par ... et les termes UN x ... par ... Soit :
(
D
B
C
* DEUX (
UNM ( *
•*-* (
( Sin (
DEUX UN ) ) )
( * C X )
Ceci est obtenu grâce à un traitement récursif par la fonction FORCOR, qui
partant de la formule dérivée avec les termes surabondants élimine ceux d'entreeux qui sont facilement reconnaissables. Fig. VI.14.
Fig. VI.12 Fig. VI.13
13579
112
14161820152223
40
ELIMINATION DES TERMES SURABONDANTS
FONCTION FORCOR
FCNCTICN FCPCnPd. )
FCNCTICN F O R C O R C L )PLUS=2M+F C I N S = 1 H -FP.rC=U*C T V = U /S IMJ=2»-SNCCSI = 2 f -CCPUIS=2H«*JlJN=2hUNOEUX=3hOEU
LU=L/1PPFLA P P E LAPPELAPPELA P P E LA P P E LA P P E L
4l
21
INTRDD(PLUStLUS)ÎNTRDD( FOINS, MOINS)1NTPOC(PROD,MROD)I N T R H D I D I V , N I V )I N T P D D t S I N U , I N L ' ÎINTRnC(COSI ,LOSI )I N T R D C ( P U Ï S , M U I S )
L N = L A D P E ( L A )IDC=LSG(CONT(LU-1) )SYMB = C C N T ( L S D ( C O N T ( IDC) )-l)A P P E L INTRTD( SYMB,LYMB)IS1=LSD(CONT(LSD(CONT( 100))) )IS2=LSD(CONT( IS1) )SYMB1 = CONT( IS1-1)S Y H R 2 = C O N T ( IS2-1)IMPRIMER 100.SYMB, I SI , I S2, SYMP1 , S YMB2 ,LUSI (LYyB-LUS) l ,2 , lS Î ( L Y M P - W R Q O ) 3 , 2 , 3S I (LYHR-MOINS)5 ,2 ,ES I (LYME-NÏVn ,2 ,7
25
173031
3332W3513
100
, SYVB ,LU)
S H L Y M E - I N U l l l , 2, 11S I ( L Y M P - L O S I ) 1 3 , 2 , 13A P P E L P A R M T 6 ( C O N T ( L N ) , I S2, SYMB1ITC1=HCRCOR( IS1)APPEL PESTR6(MG, I S 2, SYMB 1, S YMB2 , SY/-R ,LU)A P P E L 1NTRCI(MG,LN)A P P E L P A R M T 7 ( C O N T ( L N ) , I S 2 , S Y M B l , S Y y B 2 , S Y f B , L U , I T C UITC2=MORCOR( IS2)APPEL PFSTR7(MG, IS2, SYMB 1, SYMB2 ,LYNB » LU, I TC1 )A P P E L 1NTRCI (MG,LN)CCNT]=CnNT( IT01-1)C.rNT2=CONT( ÎT02-1)S K L Y M P - L U S ) 14, 15,14S I ( L Y M E - M O I N S ) 1 6 , 15,16
R, 17, 18) 2 C T l ^ t 2 C
A ILEP A 13S U C C N T 1 - Z E P ) 2 2 , 2 1 , 2 2S I ( C C N T 2 - Z E R ) 1 3 , 2 3 , 1 3ADC=CONT(LU-1)APPEL INTRDI(CONT1,LU-1 )S I ( L S G ( C G N T 1 ) - L S D ( C O N T 1 ) ) A C , 4 1 , A CA P P E L INSIND(C,-1,-1,LL)
FCNC.TION FORCOP(L)
lt-lt-1. L L )ALLEF t 25APPEL IMSIND(A L L E R A 25AOC=CCN'T(LU-1)APPEL INTPOI(CnNT2,LU-l)S U L S G ( C O N T 2 ) - L S O ( C O N T 2 ) )42,A3,42APPEL INSINC(Ct-l f- l tLl)ALLER A 25A P P E L I N S l N C f l ,-l ,-l ,Ll)APPEL ÎEFLST(AOD)ALLER A 13S I (CCNT1-ZFR)3C,31 ,3CSHCCNT2-ZFR)33 ,31 ,33ACC=CCNT(LU-1)APPEL TNSÎNO(0,-1,-1,LU)APPEL INTRDI(ZER,LU-1)APPEL I F F L S T ( A O D )ALLER A 13SI(CCNT1-UN)32,21,.32S I ( C C M 2 - U N ) 1 3 , 2 3 , 1 3S I ( C C N T 1 - Z E R ) 3 5 , 3 1 , 3 5S I ( C O N T 2 - U N ) 1 3 t 2 3 , 1 3APPEL ÎNTRDO(LU,FORCC1R)IMPRIMER ICI,FORCORRETOURfCOELE(5X,EHSYMB=,A6,5(2X,012) , / /»MODELE(5X,7hFORCOR=,012, / / )F IN (1 ,1 ,0 ,0 ,0 , C, 1 , C , C , 1 , C , C , C , 0 , 0 )
Fig. VI-H
prvii—t
k*
LISTE FORMULE CORRIGEE
LA= 0 7 7 3 1 5 0 Q O C O C
277205077313 O O O C C O C O C O C C
077315077307 2 0 2 C É C 6 C 6 C 6 C + +
177313077205 077261C77261
2772^7077255 C C O C C C O C C C C 3
077261C772Ï3 Ï46C6C6C6060 *
077255C77247 2 1 6 C 6 C 6 C 6 C 6 C A
177253C77261 C77251C77251
277237C772A5 C C C C C O C 0 0 0 0 3
C77251C77243 546C6C606060 *
C77245C77237 242564676060 D E U X
177243C17251 C77233C77233
277221C77227 000000000003
C77233077225 545460606060 **
C77227C77221 67606C606060 X
177225077233 077223077223
177307077315 07 ~i 14 1 C77141 277213077217 C00000000003
277127C77135 C C C C C C C C C C 0 3 C77223077215 406060606060 -
0771MC71133 5 4 6 C 6 C 6 C 6 C 6 C * 077217077213 242564676060 D E U X
07713Î077127 2 2 6 C 6 C 6 C 6 C 6 0 B 077215077223 644560606060 UN
1771330771M C77131077131
277117077125 C C C O C C 0 0 0 0 0 3
077131C77123 5A6C606C6060 *
C77125C77117 6445446C6060 U N N
177123C77131 C77121C77121
277C61C77115 000000000003
C77121077111 546060606060 *
177115077C61 077113077113
277103077107 000000000003
077113077103 624560606060 SK
177107077113 077105077105
277065077101 000000000003
077105077075 202060606060 ++
177101077065 077077077077
277067077073 000000000003
077077077071 546060606060 *
077073077067 2360606C6060 C
077071077077 67606060606C X
077075077105 246060606060 0
C77111C77121 236C6C606060 C
Fig.
- 64 -
CONCLUSION
Le travail que nous avons fait surles langages de listes a pour but
de montrer l'utilité que peuvent avoir, dans un grand nombre de domaines,
les listes. L'idée essentielle est celle de structure qui prend une im-
portance égale à celle du contenu des positions de mémoires. Ceci a été
mis en évidence essentiellement dans les travaux sur les listes de symboles,
sur les listes de roots pour la recherche lexicographique, dans les program-
mes de calcul de dérivée et de calcul de valeur d'une fonction.
Cette étude, et plus particulièrement l'étude de SLIP, n'est qu'une
approche de l'idée de listes, car nous n'y avons vu qu'un moyen de résou-
dre des problèmes complexes qui étaient difficiles à programmer par les
méthodes classiques. Mais les listes ouvrent des voies nouvelles, encore
peu explorées. La reconnaissance de symboles introduit à la traduction
automatique, à la reconnaissance de structures, à l'apprentissage, à
l'intelligence artificielle. Plusieurs équipes aux Etats-Unis se penchent
sur ces problèmes, et ont déjà obtenu des résultats intéressants. D'autres
équipes, plus pragmatiques, s'intéressent à l'intégration formelle, à la
résolution d'équations différentielles. Il existe des programmes réali-
sant le calcul d'erreurs en physique. Tout ceci est relativement récent,
car les premiers travaux n'ont débuté qu'en 1961 et les premières réali-
sations homogènes datent de 1963.
Les programmes et les méthodes que nous avons développés ici ne sont
encore que des exemples. Aucun d*entre eux ne peut servir à un travail
continu, être incorporé à un processus de production ; ce sont seulement
les méthodes qui ont été exposées, car ce sont elles qui constituent les
innovations. La mise au point de tous ces programmes est longue et néces-
siterait des équipes importantes, mais il n'est pas interdit de penser que
nous verrons , dans un avenir relativement proche, de tels systèmes devenir
effectifs et différents laboratoires les avoir à leur disposition par
"télé-processing", c'est-à-dire que chaque utilisateur dispose d'un clavier
sur lequel il frappe son programme, ou ses données, ceci étant transmis à
une machine centrale, disposant des fonctions étudiées et travaillant en
fl-
ESJ
- 65 -
listes, par le moyen de lignes téléphoniques, les résultats revenant de
la même manière, avec un temps de réponse très court. Ces méthodes sont
directement applicables à la recherche bibliographique, à la consultation
de fichiers importants, à la recherche documentaire. L'utilité des langages
de listes est évidente, à ce stade de travail. Les utilisateurs n'ont pas
à connaître les langages, la machine traduisant automatiquement le langage
des utilisateurs en un langage de listes, langage qui a été utilisé pour
constitution du fichier, pour la mise sur bandes ou disques des documents,
des références bibliographiques, des méthodes de calcul des dérivées, des
intégrales, des erreurs...
Les langages de listes sont actuellement rentrés dans l'ensemble des
procédés utilisables directement par les programmeurs. IBM termine actuel-
lement la mise au point d'un langage d'une grande généralité : le PL 1,
plus efficace que FORTRAN ou ALGOL, qui utilise les listes. Beaucoup de
procédés de traitement utilisent les listes, que ce soit pour faire des
travaux récursifs, des opérations sur symboles, ou du partage de temps.
Les techniques de "time sharing" ont été mises au point après que les listes
aient été utilisée/s. Le traitement des priorités, des interruptions de
travail, des transferts de contrôle, est réglé par des méthodes de listes.
C'est dire qu'actuellement, les listes sont l'instrument de base de la
recherche en programmation.
TABLE DE CORRESPONDANCE DES NOMS DE SOUS PROGRAMMES SLIP
FRANÇAIS ET AMERICAINS
ET ORIGINE DES DENOMINATIONS MNEMONIQUES
AVLD
ASLG
AVSD
AVSG
AVLED
AVLMD
AVLND
AVLEff
AVLMG
AVLMG
AVSED
AVSMD
AVSMD
AVSEG
AVSKG
AVSMG
QUEUE
ELIM
INI TED
INLSTD
INLSTG
INITCÏÏ
INTGER
IEPLST
IEFCÏÏ
LCNVCE
LISTE
ADVLR
ADVLL
ADVSR
ADVSL
ADVLER
ADVLWR
ADVLNR
ADVLEL
ADVLUL
ADVLNL
ADVSER
ADVSWR
ADVSMR
ADVSEL
ADVSWL
ADVSML
BOT
DELETE
INITAS
INLSTR
INLSTL
INITRD
INTGER
IRALST
IRARDR
LCNTR
LIST
Avance linéaire droite
Avance linéaire gauche
Avance structurelle droite
Avance structurelle gauche
Avance linéaire données droite
Avance linéaire mixte droite
Avance linéaire noms de liste droite
Avance linéaire données gauche
Avance linéaire mixte gauche
Avance linéaire noms de liste gauche
Avance structurelle données droite
Avance sti-ucturelle mixte droite
Avance structurelle noms de listes droite
Avance structurelle données gauche
Avance structurelle mixte gauche
Avance structurelle noms de listes gauche
Queue de liste ou bottom/Donnée de la dernière cellule
Elimination dlune cellule. Delete = renvoi.
Initial available space. Initialisation espace disponible
Intercaler une liste à droite
Intercaler une liste a gauche
Initialiser le Readei; Initialiser Chercheur -
Donne un nom Entier Fortran à une cellule
Erase list. Efface liste
Erase reader. Efface chercheur
Le compteur de niveau (du chercheur). Level counter
Créer une tête de liste vide
LOCT
LNOMCH
LCPCH
LCRTCH
LISTMT
LRNV1
LRNVT
MADGCH
MADDRT
MADNQTJ
MADNTT
MTLIST
HAMTS'T
NUCELL
NULSTG
NULSTD
IMMGCH
IMMDRT
PARMT2
E.JQUEJTT
NUTT
NVQU
IMPLST
RCELL
SEQLD
SEQLG
SEQSD
SEQSG
REED
REEL
SOBST
SUBSTT
SUBSQU
EGAL
TETE
LOCT
LOFRDR
LRDRCP
LRDROV
LISTMT
LVLRV1
LVLBVT
MADLFT
MADRGT
MADNBT
MDNTP
MTLIST
NAMTST
NUCELL
NULSTL
NULSTR
ÏŒTLFT
NKTRGT
PARMT2
POPBOT
POPTOP
NEWTOP
KBWBOT
PRLSTS
RCE.LL
SEQJJi
SEQLL
SEQSR
SEQSL
REED
REEL
SUBST
SUBSTP
SUBSET
EQUAL
TOP
Location adress of Reader
Le nom du chercheur. Link of Reader
Copie le chercheur Reader copy
Crée le chercheur Reader
List enrpty . Liste vide
Level reader up to 1
Level reader up to top
Adress of left * adresse gauche
Adress right #adresse droite
Adress of Bottom adresse queue
Adress of Top adresse tête
Renvoie corps de liste en réserve
Name Test . Teste si nom de liste
New cell Nouvelle cellule
Null list left Annule la partie gauche
Null list right Annule la partie droite
Next cell left Immédiatement gauche
Next cell right immédiatement droite
Paramètres. Deux paramètres protégés
Pop Bottom Renvoie la dernière cellule
Pop Top Renvoie la tête de liste
Nouvelle tête New Top
Nouvelle queue New queue
Imprimer liste Print list
Renvoie cellule Rester cell
Séquence linéaire droite Sequence linear right
Séquence linéaire gauche Sequence linear left
Séquence structurelle droite Séquence structural right
Séquence structurelle gauche Séquence structural left
Read » lire donnée /Réel fonction variable réelle
Substituer Sustitute
Substituer tête Sustitute Top
Substituer queue Sustitute queue
Test Egalité Equality test
Tête de liste Sommet = Top
DERROR
NAMEDL
LISTAV
ITSVAL
LDATVL
MADATR
MAKEDL
SCHATR
NEWVAL
NOATVL
MTDLST
ERADLS
MRKLST
MRKLSS
LSTMRK
Description of error
Name of description list
List available (description) for LST
Value of attribute (its value)
List description attribute value
M Adress of attribute
Make description list
Search for attribute right
New value for attribute
Null attribute and value
Empties description list
Erases description list
Mark on liste (L)
Mark on list structure (L)
Mark of list (L)
BIBLIOGRAPHIE
J. WEIZENBAUM Symétrie List Processor
Communications of ACM Septembre 1963
D.G. BORROW et B, RAPHAEL A comparison of list processing computer languages
Communications of ACM Avril 1964
J. Me. CARTÏÏY et al. LISP 1.5 Programmers Manual
The MIT Press Cambride - Mass 1962
A, NEWELL et al Information Processing Language V manual
The Rand Corporation
Ho GELERNTNER - HANSEN et ŒRBERICH .FORTRAN Compiled List processing language
Communications ACM
J. COHEN et NGUlffiN HQU DUNG Définition de procédures LISP en ALGOL et exemple
d'utilisation. RFTI Chiffres V01 8 N° 4 1965 p 271-293
T. EVANS - J. COHEN - M0 TRILLING - Y. SIRET et 0. LECARME>
Publications à l1occasion du syprphosium de traitement de listes
à l1Institut de Mathématiques appliquées Grenoble - Mars 1966
J.A. SAXON Programming- the IBM 7090
Prentice Hall Inc. 1963
J. Me CARTHY Recursive functions of Symbolic expressions and their computation
by Machine. Communications of ACM Avril 1960
P. DEBRAINE Techniques binaires Application aux automatismes et aux machines
de Traitement de l'Information. INSTN - Saclay 1965-1966
Manuscrit reçu le 7 juin 1966
ANNEXE
FONCTIONS ET SOUS PROGRAMMES SLIP
*LSG
LSG
AC
MG
AUX
COMPTENTREESXARADSRARAL3RDRADEtXTRABCSFIN
12LSGMG.41.4AC**AUXAUX**.42,41
*MAOD
MADD
MGPREND LA PARTIE DECREMENT DU PARAMETRE
COMPTENTREESXARADDAGEEXTRAFIN
8MADDMG.41.418*#,42.4
DONNE L'ADRESSE DU PARAMETRE
*ID
*LSD
LSD
AC
MG
AUX
COMPTENTREESXARADSRARALSRARADDAGEEXTRABCSFIN
13LSDMG.41.4AC#*AUXAUX18**»42.41
PREND LA PARTIE ADRESSE DU PARAMETRE
ID
AC
MG
AUX
COMPTENTREESXARADSRARALSRPRADDADEEXTRABCSFIN
13IDMG,41.4AC**AUXAUX15**»42.41
DONNE LE CONTENU DE LA ZONE ID DU PARAMETRE
ot-3M
%Ul
•rlag
§C/3
*INHALTCOMPT 12ENTREE INHALT
INHALT SXA MG.4RAD 1.4SRA KA
KA RAD **DAD 18SRA KB
KB RAD **MG EEX **.4
TRA 2.4FIN
PREND LE CONTENU DE LA MEMOIRE POINTEE PARLE PARAMETRE
*INTRDDCOMPTENTREE
INTRDD SXARADSRARADSRA
KB RADKA SOR
MG EEXTRAFIN
12INTRDDMG.42,4KA1,4KB*****»,43,4
MET LE CONTENU DU PREMIER PAMAMETREDANS LE SECOND
*INSIND
INSIND
KA
AC
AD
TDI
BA
BC
BD
TDG
ÇA
ce
CD
TDD
DADB
MG
UNM
COMPTENTREESXARADSRARADDADSRASRASRASRARADSRASRARADADDTZERADDAGSRPTRARADSRPRADSRASRARADADDTZERADPDXSXDTRARADPDXSXDRADSRASRARADTZEADDRADPDXSXATRARADPAXSXARADSOREEXTRAOCT
58INSIMG»44,4KA#*18TDITDGTDDDB1,4ACAD•**UNMTDI##15AUXBA#*AUX2,4BCBD**UNMTDG##0,1AUX,ÇA##0,1AUX,3,4ceCD##TDDUNM##0,1AUX,DA#*0,1AUX,AUX##**,45,40000
ND
DANSLOGELE SELE TR
1
1
1
1
01000000
A 3
LA MEMOIRE POINTEE PAR LELE PREMIER EN PARTIE IDCOND EN PARTIE DECREMENT
TROISIEME EN PARTIE ADRESSE
DERNIER PARAMETRE
cc
cc
cc
FONCTION AVLEG(LCH,A)AVANCE LINEAIRE GAUCHEARRET SUR TOUS LES SYMBOLESA=AVLG(LCH,G,0)S K A j l . Z f 1AVLEG=RE£D(LCH)
RETOURFIN
SAUF LE.5 NOMS DE LISTE
FONCTION AVLED(LCH»A)AVANCE LINEAIRE DROITEARRET SUR TOUS LES SYMBOLESA=AVLD(LCH»0,0)SI (A)l,2»lAVLED=REED(LCH)RETOURFIN
SAUF LES NOMS DE LISTE
FONCTION AVLD(LCH»J,K)FONCTION REALISANT LiAVANCE LINEAIRE DANS UNE LISTEUTILISE LE SUIVEUR LCH~CLCH=CONT(LCH>AVANCE A DROITELK=LSDCCONT(LSG(CLCH)))CAND=CONT(LK)APPEL îNSDIR(-l,LK,-l,CLCH)SI (ID(CAND)-2)lt2»lSI ( ID(CAND)-J)3.4»3SI ( ID(CAND)-K)5,4,5AVLD=0.ALLER A 6AVLD=-1.0APPEL INTRDI(CLCH.LCH)RETOURFIN
FONCTION AVLG;LCH,J,K)FONCTION REALISANT LtAVANÇA LINEAIRE DANS UNE LISTEAVANCE A GAUCHEUTILISE LE SUIVFUR LCHCLCH=CONT(LCH)LK=LSG(CONT(L5G(CLCH>))CAND=CONT(LK)APPF.L INSDIR(-1»LK,-1,CLCH)SI(ID(CAND)-2)1,2,1SI(ÏDÎCAND)-J>3>4,3SI (ID(CAND)-K)5,4,5AVLG=0.ALLER A 6AVLG=-1.0APPEL INTRDI(CLCH,LCH)RETOURFIN
FONCTION AVLMD(LCH.A)AVANCE LINEAIRE DROITEARRET SUR TOUS LES SYMBOLESA=AVLD(LCH,1,0)SI ( A ) 1,2 » 1AVLMD=REED(LCH)RETOURFIN
O
MO
03
W
FONCTION AVLMG(LCH,A)AVANCE LINEAIRE GAUCHEARRET SUR TOUS LES SYMBOLESA=AVLG(LCH>1,0)S I < A ) 1 * 2 , 1AVLMG=RFFD(LCH)RETOURFIN
FONCTION AVSG(LCH»J,K)AVANCE STRUCTURELLE GAUCHER=CONT(LCH)LCP=LSG(R)CAND=CONT(LCP)SI(ID(CAND)-!)1>6,1
1 LCP=LSG(CAND)APPEL INSDIR(-1»LCP,-1,R>CAND=CONT(LCP)CRITERES D'ARRET.. ID= 1, 2, 0.SI ( ID(CAND)-2 )3î^-,3
3 SI(ID(CAND)-J)7»8»77 SI(ID(CAND)-K)5,8»55 SI(ID(CAND)-!)1*6»!6 M=NUCELL(Z)
APPEL INTRDKR.K)LE SUIVEUR TIENT COMPTE DE LA STRUCTURE QU'IL A TRAVERSEEAPPEL INTRDI(CONT(LCH-1),M-1)APPEL INSINDI-1»LSG(CONT(LCP-1))»LCNVCH(LCH)+1tLCH-1)APPEL INSDIR(-1»-1»M,R)CAND=CONT(LSG(CONT(LCP-1)))ALLER A 1
4 SI(LCNVCH(LCH))9»10,9SI FIN DE STRUCTURE A=-l.
10 AVSG=-1.0ALLER A 12
9 LK=LSD(R)R=CONT(LK)APPEL INTRDI(CONTCLK-3),LCH-1)CAND=CONT(LSG(LK))APPEL RCELL(LK)ALLER A 1
8 AVSG=0.12 APPEL INTRDI(R»LCH)
RETOURFIN
CC
CC
FONCTION AVLND(LCH,A>AVANCE LINEAIRE DROITEARRET SEULEMENT SUR LESA=AVLD(LCH,1,1 )SI (A) 1,2,1AVLND=REED(LCH)RETOURFIN
NOMS DE LISTE
FONCTION AVLNG(LChUA)AVANCE LINEA-IRE GAUCHEARRET SEULEMENT SUR LES NOMS DE LISTEA=AVLG(LCH,1,1)SI(A)1,2,1AVLNG=REED(LCH)RETOURFIN
VJ1
cc
cc
FONCTION AVSED(LCH.A)A«AVSD(LCH»OtO)
2 AVSED*REED(LCH)1 RETOUR
FIN
FONCTION AVSEG(LCH,A)AVANCE STRUCTURELLE GAUCHEARRET SUR TOUS LES SYMBOLES SAUF LES NOMS DE LISTEA«AVSG(LCH,0,0)
2 AVSEG-REED(LCH)1 RETOUR
FIN
FONCTION AVSMD(LCH»A)AVANCE STRUCTURELLE DROITEARRET SUR TOUS LES SYMBOLESA«AVSD(LCH.1,0)
2 AVSMD*REED(LCH)1 RETOUR
FIN
FONCTION AVSD(LCH.J»K)AVANCE STRUCTURELLE DROITED-CQNT(LCH)LCP=LSG(D)CAND«CONT(LCP)SICID(CAND)-1)1»6»1
1 LCP«LSD(CAND)APPF.L INSDlR(-l.LCPt-ltD)CAND=CONT(LCP)CRITERES D'ARRET.. ID« 1» 2t 0.SI(ID(CAND)-2)3»4»3
3 SI(ID(CAND)-J)7.8*77 SI UD(CAND)-K)5t8»55 SI(ID(CAND)-1)1.6.16 M=NUŒLL<Z)
APPF.L INTRDKD.M)LE SUIVEUR TIENT COMPTE DE LA STRUCTURE OU»IL A TRAVERSEEAPPEL INTRDI(CONT(LCH-l),M-1)APPEL INSIND<-ltLSG(CONT(LCP-D).LCNVCH(LCH)*!.LCH-1)APPEL INSDlR(-lt-ltMtD)CAND=CONT(LSG(CONT(LCP-1)))ALLER A 1
4 SKLCNVCH(LCH) )9t in»ySI FIN DE STRUCTURE A*~i.
10 AVSD»-1.0ALLER A 12
9 LK=LSDi!D)D=CONT(LK)APPEL INTRDKCONT(LK-l)» LCH-1)CAND«CONT(LSG(D»)APPEL RCELL(LK)ALLER A 1
8 AVSD=0.12 APPEL INTRDI(D.LCH)
RETOURFIN
FONCTION AVSMG(LCH.A)C AVANCE STRUCTURELLE GAUCHEC ARRET SUR TOUS LES SYMBOLES
A»AVSG(LCH»1»0)SI(A|1*2*1
2 AVSMG-REED(LCH)1 RETOUR
FIN
FONCTION AVSND(LCK,A )C AVANCE STRUCTURELLE DROITEC ARRET EXCLUSIVEMENT SUR LES NOMS DE LISTE
A=AVSD(LCHt l f 1 )S I (A ) I t2 , l
2 AVSND=REED(LCH)1 RETOUR
FIN
FONCTION SUBST(D»N)C REMPLACE LA DONNEE DE LA CELLULE N PAR LA DONNEE D
LBACK=LSG(CONT(N))C PREND POUR VALEUR L'ANCIENNE DUNNEE
SUBST=ELIM(N)APPEL IMMDRT<D»LBAClORETOURF I N
FONCTION AVSNG(LCH.A)C AVANCE STRUCTURELLE GAUCHEC ARRET EXCLUSIVEMENT SUR LES NOMS DE LISTE
A=AVSG(LCH,1»1)
FONCTION SUBSTT(D»LST)C REMPLACE LA DONNEE DE LA CELLULE DEC PREND POUR VALEUR L'ANCIENNE DONNEE
SUBSTTsSUBST(DfLSOÏCONT(LST)))RETOURFIN
EIE PAR D
2 AVSNG=REED(LCH)1 RETOUR
FIN
FONCTION E G A L ( M t N )C TEST D 'EGALITE DES 2 SYMBOLES M ET N
SI (M-N)1»2»1C SI OUI EGAL =0.2 EGAL=0
RETOURC SI NON EGAL =-1.1 EGAL=-1
RETOURF I N
FONCTION SUBSQU(D»LST)C REMPLACE LA DONNEE DE LA CELLULE DE QUEUE PAR DC PREND POUR VALEUR L'ANCIENNE DONNEE
SUBSQU=SUBST(D»LSG(CONT(LST)))RETOURFIN
'A 8
CREATION DE LA RESERVE
CINITEDSOUS PROGRAMME INITED
C IMITAS CREE LA LISTE D'ESPACE DISPONIBLEDIMENSION W(200)»X(100),LAVS(2)COMMUN CREF»X,LAVS
C RECHERCHE LES LIMITES DE L'ESPACE DISPONIBLEAPPEL KFINAL(LIMSUP)LIMINF=MADD(LAVS)N=LIMINF-LIMSUPFAIRE 1 1=1,100J=2*I-1
C CREE 100 LISTES VIDES •«PUBLIQUES»«APPEL INSD-IRf OtMADDtWt J) ) »MADD(W(J) )APPEL INSDIR(2»MADD(W(J)),MADD(W(J))
1 APPEL INSDIR(-1»-1»4095,W(J+l))FAIRE 2 I-1»N
2 LAVS(I)=0K = N-2FAIRE 3 I=lfKf2
3 APPEL INSDIR(-lt-ltMADD(LAVS( 1+2) ).»LAVS( I ) )C LOGE LES EXTREMITES DANS LA CELLULE CREF
APPEL INSDIRfO,MADD<LAVS(N-l))»MADD(LAVS<1))»CREF)RETOURFIN
INEFFAÇABLES« X ( I ) )» W ( J ) )
*KFINAL
KFINAL
AMG
C337
COMPTENTREESXARADSRARADADDDLGSOREEXTRAOCTFIN
14KFINALMG,41,4AS(EXEM)C33718•***#,42,4000000000340
A 9
RENVOI EN RESERVE
O.
UJ
•SI
UJo
Ilt-<nj
jii
Ul'.O<J>UJceo
LUi-UJ
oa
UJQ
UJUJzO rio i
ace —o t-ui u_i o< -i
t J Z— X. Oa. z u— o -UJ U OH- U5UJ O -I
z a: zo a o— u ce(- M O(J UJ Oz a t- »- zo o uj 10 •-u. i- H- te u.
-i a.K. t-o uu o
> i-z
— UJ oa z u— 2: —UJ O O3 u mUJ -J3 Q —O Z t-
UJ Zz ce oo a. o» n cet- UJ 3U 00Z t- UJt- ZO O OUI «u. ça a ce u.
UJaUJUJzOO
— UJ O* -J U- < _O > V3UJ U)Ul Ul _l<X X —
Z I-z o zO <J O•- uo;•- o H 3u z ooZ UJ Ult- Zo ce uj uj —u. a. ce ce u.
zUJ
Ul Oce za j
z -uoo •
oUl II 11-J s:O — Ul
UJu
Ul
ce o _i rjUl •>io tu ce .-<u >- o —ce — uj uj rg
* t- _i iz— < —UJ J D Ul — O•-"UJ f. H- O-O t-ZX>z </>o o cer o uj u u uj
— x oz — ce iz - LJ - a. —
O 07CC — 3! _luiu. a 10 >-uj
UJ —ce •t- 10t- Cf.aUJ UJo ceui uj_i i-o uij <UJU UJ
uj s;z <O a:- o00
cez ao« ui
«UJ
ÏOj ceui m- M
o o -•_j _i ~ z• » < ceo «-• 10 o-il 10 o• • Ul U.
I _l Z <
I | i o
l _ _ _ û o m z^ K > - _ I Z Z »r~— z z -i •- — «-< *J - O O U J i O l / J i •>
• Z Ï Î O O Z Z r t Xo — — ce — •- — •
ce vj où ce ujO Z - J - J U J U J U J O U J 1 —K - ~ « NC.Q.Q . I -O4Z
c e u i _ i _ j < < < c e z u.
-luiliio
ceUl
10
O
•3<UJ
UJaceoUlH-ao
a. oui^ zZ UJai t-z oUl U
CE UJ•
r > ceL< •- O —_l D UJ I— l/> J UI < _l --u w > — — zU. -J I Z -UJ UJ U — _l•-UJ Z > »- _l -H
Z Z Z Z Ul • «Z •- O U O uruoï^-i u c e » <» » . « ~- r-. ce> - _ J O I I Q J — ces<J Ul Z UXJ U) UJ Z Ul Oz u j u . j _ i a — z-ii-zO ce ce uj » u a. "i » -J uj —u.oa > - z z < i n z <œu.ce
< m r-l fSI
ce
I'1t''
FONCTION INITCH(LCH)C INITRD RENVOIE LE CHERCHEUR EN TETE DE LA LISTE COURANTE
APPEL INSIND(-1.LSG(LCH-1),-l,LCH)C PREND COMME VALEUR L'ADRESSE DU CHERCHEUR
INITCH=LCHRETOURFIN
CEJQUFONCTION EJQU(P)
C POPBOT RENVOIE EN RESERVE LA QUEUE DE LA LI5TE PC PREND POUR VAuEUR LA DONNEE DE P
EJQU=ELIM(LSG(CONT(LOCT(P))))
RETOURFIN
i
FONCTION IEFLST(P)C IRALST RENVOIE LA LISTE P EN RESERVE
L=LOCT<P)C TESTE LE COMPTEUR DE NIVEAUC LE DIMINUE DE UNE UNITE
APPEL INSIND(-1»-1»LCNVCH(L)-1.L-1)IEFLST=LCNVCH(L)SI(IEFLST)1.2»1
C S»IL EST NUL RENVOI DU CORPS DE LISTE2 APPEL MTLISTIP)N=LSG(CONT(L-1))SI(N)3,4,3
C TEST DtEXISTENCE D»UNE LISTE DE F90PRIETES3 NOUV=NUCELLAPPEL INSINp(lt-lt-ltNOUV)APPEL !NSlND<-lfNtN»NOUV-l)
C RENVOI DE LA LISTE DE PROPRIETE ET DE LA TETE DE LISTEAPPEL RCELL(NOUV)
4 APPEL RCELL(L)1 RETOUR
FIN
CEJTTFONCTION EJTT(P)
CPOPTOP RENVOIE EN RESERVE LE SOMMET DE LA LISIE HC PREND POUR VALEUR LA DONNEE DE H
E J T T = E L I M ( L S D { C O N T ( L U C T ( H ) ) ) )RETOURF I N
FONCTION IMMDRT(M»A)C NXTRGT CREATION D'UNE CELLULE A DKÙIIE DE AC PREND COMME VALEUR L«ADRESSE DE LA NOUVELLE CELLULE
ID*NUCELL(Z)LD=LSD(CONT(A) JAPPEL INSIND(-l.ID.-ltLD)APPEL INSIND(-lt- l t ID»A)APPEL INSIND<OtA.LD.ID)
C SI M EST UN NOM DE LJSTEtACCROCHE LA LISTE MSI(NAMTSTCM))lt2.1
2 APPEL INSIND(,1»-1»-1»ID)APPEL INS IND('-1»-1»LCNVCH( M )-*•!.M-l)
C INTRODUIT M COMME DONNEE DE LA CELLULE1 APPEL INTRDKMtID-1)
IMMDRT»IDRETOURFIN
FONCTION INLSTD(M»A)C INLSTR INTERCALE LE CORPS DE LISTE M A DROITE DE A DANS LAC LISTE DE A
L»LOCT(M)ITOP-LSD(CONTJL))IBOT«LSG(CONT(L))
C M DEVIENT UNE LISTE VIDEAPPEL INSIND(-1»L»L»L)ISUC*LSD(CONT(A>)APPEL INSIND(-1.-1.ÎTOP,A)APPEL INSIND(-ltIBOTt-l»ISUC)APPEL INSIND(-1»A»-1»ITOP)APPEL INSIND(-lt-l,ISUC,IBOT)
C PREND POUR VALEUR LINLSTD-LRETOURFIN
FONCTION IMMGCH(M.A)NXTLFT CREATION DiUNE CELLULE A GAUCHE DE A
IG«NUCELL(Z)LG»LSG(CONT(A))APPEL INSIND(-l»-ltIG-»LG)APPEL INSIND(-ltIG,-1»A)APPEL INSIND(0»LG»A,ÏG)SI M EST UN NOM DE LISTE,ACCROCHE LA LISTE MSî(NAMTST(M))1.2*1
2 APPEL INSIND(1»-1»-1»IG)APPEL INSIND<-1»-1»LCNVCH(M)+1tM-1)INTRODUIT M COMME DONNEE DE LA CELLULE
1 APPEL INTRDI(M.IG-I)PREND COMME VALEUR L'ADRESSE DE LA NOUVELLE CELLULEIMMGCH=IGRETOURFIN
FONCTION INLSTGCMtA)C INLSTL INTERCALE LE CORPS DE LISTE M A GAUCHE DE A DANS LAC LISTE DE A
L«LOCT(M)ITOP«LSD(CONT(L)JIBOT«LSG(CONT(D)
C M DEVIENT UNE LISTE VIDEAPPEL INSIND(-l.L.LtL)IPRE«LSG(CONT<A))APPEL INSIND(-1.IBOT,-1,A)APPEL INSIND(-lt-l,ITOP,TPRE)APPEL INSIND(-ltIPRE»-ltlTOP>APPEL INSIND(-1»-1»A.IBOT)
C PREND POUR VALEUR LINLSTG-LRETOUR
cc
FONCTION LCNVCH(K)LCNTR PREND COMME VALUERK EST UNE TETE DE LISTE OULCNVCH=LSOtCONT«-l ) )RETOURFIN
LELE
NIVEAU DUSUIVEUR
COMPTEUR CC
C
C
FONCTION LISTE<K)LIST CREE UNE TETE DE LISTE VIDEPREND POUR VALEUR L'ADRESSE DE LA TETE DE LÎSTtL!STE=NUCELLfZ)APPEL INSDIRJO,LISTE.LISTE.LISTE)APPEL INSIND(2*LISTE»LISTE»LISTE)SI K=9 LE COMPTEUR D£ NIVEAU EST A 0.SI(K-9)2,1»2SINON K EST UN PSEUDONYME DE LA LISTE ET LE C.DE N. EST A 1,APPEL INSIND<-1»-1»1»LISTE-1)K=LISTERETOURFIN
CC
FONCTION LCPCH(LCH)LRDRCP PREND COPIE DU SUIVEURPREND COMME VALEUR L'ADRESSE DU NOUVEAU SUIVEURLCPCH=NUCELL(Z)NOUVCH-LCPCHNOW=LCHAPPEL INTRDKCONTCNOW) .NOUVCH)APPEL INTRDI(CONT(NOW-1)»NOUVCH-1JNOW=LSD(CONT(NOW))SI (NOM)1*2*1NEW=NUCELL(Z)APPF.L INSIND(-1»-1*NEW,NOUVCH)NOUVCH=NEWALLER A 3RETOURFIM
C
C
FONCTION LISTMT(P)LISTMT TESTE SI LA LISTE EST VIDEL=LOCT(P)SI(EGAL(CONT(L).CONT(LSD(CONT(L)))))3»4.3SI OUI PREND COMME VALEUR 0.LISTMT*0RETOURSINON PREND COMME VALEUR -1.LISTMT=-lRETOURFIN
cC
FONCTION LCRTCH(P)LRDROV CREE LE SUIVEUR POUR LA LISTEPREND COMME VALEUR L'ADRESSE DU SUIVEURLCRTCH-NUCELL(Z)APPEL INSINDO.LOCTfPJfAPPEL !NSIND(0»P»0»LCRTCH-1)RETOURFIN
CC
FONCTION LNOMCH(K)LOFRDR DONNE LE NOMLE SUIVEURL=LSG(CONT(K-1))APPEL INSDIR(0»L»L»L)LNOMCH=LRETOURFIN
DE LA LISTE COURANTS OU EST ACTUELLEMENT
CC
901
FONCTION LOCT(K)LOCT TESTE SI K EST UN NOM DE LISTESI OUI LOCT = <SI(NAMTST(K))1,2»1LOCT=K
• RETOURSINON MESSAGE D'ERREUR ET APPEL EXITIMPRIMER 901APPEL EXITMODELEUH1.65H UNE LISTE ETAIT DEMANDEE COMME OPERANDE MAIS N'A PU1 ETRE TROUVEE./.42H LE PROGRAMME EST MALHEUREUSEMENT TERMINE,,)
C
C
FONCTION MADDRT(A)DONNE L'ADRESSE DE LA CELLULE A DROITEMADDRT»LSD(CONT(A))SI C'EST UNE TETE DE LISTE DONNE LE NOMSU ID(CONT(MADDRT))-2)1,2.1APPEL INSDIR(O.MADDRT.MADDRT.MADDRT)RETOURFIN
CC
FONCTION LRNVKLCH)LVLRV1 FAIT REMONTER LE SUIVEUR D'UN NIVEAUPREND COMME VALEUR LCHLRNV1=LCHSKLCNVCH(LCH) >2 .3»2RETOURL=LSD(CONT(LRNV1))APPEL INTRDKCONT(L).LRNVI)APPEL INTRDI(CONT(L-1)»LRNV1-1)APPEL RCELL(L)RETOURFIN
C
C
FONCTION MADGCH(A)DONNE L'ADRESSE DE LA CELLULE A GAUCHEMADGCH»LSG(CONT<A))SI C'EST UNE TETE DE LISTE DONNE LE NOMSI(ID(CONT(MADGCH)>-2)1.2 » 1APPEL INSDIR t 0.MADGCH.MADGCH,MADGCH)RETOURFIN
FONCTION MADNQU(P»N)DONNE L'ADRESSE DE LA NIEME CELLULE A PARTIR DE LA QUEUEL»LOCT(P)FAIRE 1 1-1.NL-LSGCCONTCD)SI(ID(CONT(L))-2)2.3,2APPEL INSDIR(0»L.L,L>MADNQU-LRETOURFIN
CC
FONCTION LRNVT(LCH)LVLRVT FAIT REMONTER LE SUIVEURPREND COMME VALEUR LCHLRNVT=LCH
1 SKLCNVCH(LCH) )2»3»23 RETOUR2 L=LSD(CONT(LRNVT) )
APPEL INTRDKCONT(LJ.LRNVT)APPEL INTRDI(CONT(L-1)*LRNVT-1)APPEL RCELHL)ALLER A 1FIN
A LA LISTE PRINCIPALE
FONCTION MTLIST(P) FONCTION NUCELL(X) ÈCOMMUN CREF C DONNE UNE NOUVELLE CELLULE EXTRAITE DE L1* RESERVEM«LOCT(P) COMMUN CREFSnLISTMTfP))3,4,3 M=LSD(CREF)
3 LD-LSD(CONT(MM C SI LA RESERVE EST EPUISEE MESSAGE ET ARRETLG«LSG(CONT<M)) SI(M)lt2.1APPEL INSIND(-l.MiM.M) 2 IMPRIMER 901APPEL INSIND(-1»-1,LD»LSG(CREFM APPEL EXITAPPEL INSDIR»-1,LG,-1»CREF) C SI LA CELLULE APPELEE ETAIT ANCIENNEMENT UN EMBRANCHEMENTAPPEL INSIND(-1»-1,O.LSG(CREF)) C RENVOI DE LA SOUS LISTE ACCROCHEE EN RESERVE
4 MTLIST-M 1 SI<ID<CONT(M))-l)3,4,3RETOUR ** APPEL IEFLST (CONT JM-1 ) )FIN 3 APPEL INSDIR(-1,-1,LSD(CONT(M))tCREF)
APPEL INTRDI(0»M)APPEL INTRDI(0*M-1)
C PREND COMME VALEUR SON ADRESSENUCELL=M
FONCTION MADNTT(PtN) RETOURDONNE L'ADRESSE DE LA NIEME CELUULE A PARTIR DE LA TETE 901 MODELEC1H1.59HLISTE DES CELLULES DISPONIBLES EPUISEE - PROGRAMME TL»LOCT(P) 1TERMINE )FAIRE 1 1=1,N FIN
1 L«LSD<CONT(L))SMIO<CONT(L))-2)2.3*2
3 APPEL lNSDIR(0»L»LtL)2 MADNTT-L
RETOURFIN
FONCTION LINDCH(K)LINDCH«LSG(CONï(K))RETOURFIN
FONCTION NAMTST(K)SI(LSG<K)-LSD(K))1.4.1
4 SI(ID(CONT(Kn-2)1.2»l2 SI(CONT(LSD<CONT(LSG(CONT(K) ) ) M-CONTOO ) 1.3*13 NAMTST-0
RETOUR1 NAMTST—1RETOURFIN
FONCTION NULSTD(A.L) FONCTION NVTTCP.Q)C NULSTR ECOURTE LA LISTE L DE SES CELLULES A DROITE DE A C ACCROCHAGE DiUNE NOUVELLE CELLULE EN TETE DE LA LISTE 0
NULSTD-LISTE<9> C PREND COMME VALEUR L'ADRESSE DE LA NOUVELLE CELLULEC PREND COMME VALEUR LE NOM DE LA LISTE CREEE C P EST LA DONNEE DE CETTE CELLULEC CREE UNE LISTE ET LUI ACCROCHE LES CELLULES ENLEVEES A L C SI P EST UN NOM DE LISTE ACCROCHAGE DE SOUS LISTE P
SIUD«CONT<A))-2)1.2.1 NVTT-IMMDRT (P.LOCT(O) )2 APPEL INSIND(2.NULSTD»NULSTD.NULSTD) RETOUR
RETOUR FIN1 LOU*LSG(CONT(L) )
LPRE«LSG<CONT(AJ »APPEL lNSlND(-ltLPREi-l»L)APPEL INSlND(-l.-ltL.LPRE)APPEL INSIND(2»LQU.A»NULSTD) FONCTION NVQU(P»Q)APPEL INSIND(-l.NULSTD.-l.A) NVQU«IMMGCH(P.LOCT(Q))APPEL INSINDC-l.-l.NULSTDiLQU) RETOURRETOUR FINFIN
VJ1
FONCTION NULSTG(A.L)C NULSTL ECOURTE LA LISTE DE TOUTES GES CELLULES A GAUCHE DE A
NULSTG-LISTE(9)C CREE UNE LISTE ET LUI ACCROCHE LES CELLULES ENLEVEES A LC PREND COMME VALEUR LE NOM DE LA LISTE CREEE
SI(ID(CONT(AJ)-2)lt2»l2 APPEL INSIND(2»NULSTGtNULSTG»NULSTG>
RETOUR1 LTT»LSD(CONT(L) )
LSUC-LSD(CONT(A))APPEL iNSlND(-lt-ltLSUC.L)APPEL INSIND(-1.L*-1*LSUOAPPEL rNSIND(2»AtLTT.NULSTG)APPEL INSlNDC-l.-l.NULSTGfA»APPEL INSINDt-l.NULSTGt-l.LTT)RETOURFIN
C
1
A 17
MISE KESERirS ET RECUPERATION DES INDEX
ET DES MEMOIRES AUXILIAIRES
FONCTION RESTR8(AMG)RECUPERATION D'UN PARAMETRE DANi LA PILE N U 8DIMENSION X(IOO)
COMMUN CREF,XAMG=EJTT(X(8))RETOURFIN
FONCTION PARMT8(MG)MISE EN RESERVE D«UN PARAMETRE DANS LA PILE NODIMENSION X(100)COMMUN CREF»XAPPEL NVTT(MG»X(8))RETOURFIN
FONCTION PARMT4(MG»N»NltST)MISE EN RESERVE DE 4 PARAMETRES DANS 4 PILEbDIMENSION X(100)COMMUN CREF»XAPPEL NVTT(MG»X(1))APPEL NVTT(N,X(2))APPEL NVTT(N1,X(3))APPEL NVTT(ST,X(4))IMPRIMER 1 » M G » N » N 1 » S TMODELE(5X»4(5X,012))RETOURFIN
FONCTI ON REST R4(AMG » AN » AN 1,ST)RECUPERATION DU SOMMET DE LA PILE DE 4 BLOCSDIMENSION X(100)
COMMUN CREF»XAMG=EJTT(Xri))AN=FJTT(X(2))AN1=EJTT(X(3))ST=EJTT(X(4))LES 4 PILES REMONTENT D'UN CRANIMPRIMER l»AMG»AN»ANliSTMODELE(4(4X,012))RETOURFIN
FONCTION REELU)PREND POUR VALEURREEL-ZRETOURFIN
Z . EST UTILISEE POUR LES CHANGEMENTS DE MODEFONCTION NAMEDL(L)PREND POUR VALEOR LE NOM DE LA LISTE DE PROPRIETE DE LA LISTE LNAMEDL.LSG(LOCTtL)-l)RETOURFIN
900901
CC
FONCTION INTGER(I)PREND POUR VALEUR IINTGER-IRETOURFIN
EST UTILISEE POUR LES CHANGEMENTS DE MODE
SOUS PROGRAMME DERRORILSTIIMPRIMER 900, LSTIMPRIMER 901RETOURMODELE<1H1.20X.05)MODELEI20X.44HLISTE D'ATTRIBUT ET DE VALEUR DEMANDESMAIS.. I
FIN
FONCTION SCHATR(AT«L)RECHERCHE UN ATTRIBUT PAR LA DROITEPREND POUR VALEUR LE NOM DE LA SOUS LISTE OUI A AT POUR ATTRIBUTLR-LCRTCHCLJSCHATR.REELCLISI(ITSVAL(AT,SCHATR))li2ilSCHATR-AVSND(LR*K>
SCHATR-0.J-IEFCH(LR)RETOURFIN
FONCTION ITSVAL(AT.LST)C RECHERCHE L'ATTRIBUT AT SUR LA LISTE DE PROPRIETES DE LA LISTE LST
SI(LSG<CGNT(LST-1I))3t4,3C SI PAS DE SYMBOLE AT ITSVAL-03 M-MADATR(AT.LST)
SKM+ltl.2,1C PREND POUR VALEUR LA VALEUR DE CET ATTRIBUT1 ITSVAL-INHALT(LSD(CONT(M))-1)
RETOURC SI PAS DE LISTE DE PROPRIETE MESSAGE D'ERREUR ET ITSVAL-04 APPEL DERROR(LST)2 ITSVAL-0
RETOURFIN
FONCTION MAKEDL(L«M)C L DEVIENT LA LISTE DESCRIPTIVE DE M
APPEL MTDLST(M)C PREND COMME VALEUR M
MAKEDL-MC S'IL Y AVAIT DEJA UNE LISTE DESCRIPTIVE,ELLE EST EFFACEEC ET REMPLACEE PAR L
N«LOCTIM)K-LOCT(L)APPEL INSINDC-l.K.-l.N-l)APPEL INS!ND(-l«-l«LCNVCH(L)+lt9-l.RETOURFIN
C/2
802
g
it-CD
cc
3
2
1
C
C
C2
C
C
C2
FONCTION MRKLSS(MtLST)MARQUE LA LISTE PRINCIPALE ET TOUTES LES SOUS LISTES DE MPREND POUR VALEUR LE NOM DE LA LISTE LSTMRKLSS-LSTLR-LCNVCHC MRKLST (M, LST )XX«AVSNDCLRtK)
APPEL INSINDeM,-lt-l.LSD<XX)-l)ALLER A 3APPEL RCELULR»RETOUR
FIN
FONCTION NEWVAL(AT»VAL,LST>CHANGE LA VALEUR DE L'ATTRIBUT AT MET VAL AU LIEU DE LA PRECEDENTE
SÎMPAS DtATTRIBUT OU PAS DE L. DE P. ON EN CREE UNE AVEC AT ET VALSI(M+l)lt2tlPREND POUR VALEUR L«ANCIENNE VALEURNEWV*L«INTGER C SUBST t VAL,LSD« CONTIM)))»RETOURAPPEL LDATVLCATtVAL.LST)NEWVAL-0RETOURFIN
FONCTION NOATVL(AT»LST)RENVOIE L'ATTRIBUT AT ET SA CELLULE DE VALEUR E.N RESERVEM-MADATRCAT.LST)SI PAS DE L. DE P. OU PAS DE AT NOATVL-0
PREND POUR VALEUR LA VALEUR DE CET ATTRIBUTNOATVL-INTGERCELIMCLSDICONTCM) ) ) )APPEL ELIM(M)RETOURNOATVL-0RETOURFIN
FONCTION LDATVL(AT»VL»LST)SI(LSG(CONT(LST-1»)»1»2,1
S S'IL N'Y A PAS DE L DE P0 EN CREE UNE ET LOGE EN TETE AT PUIS VL2 LDATVL«LISTAV(LST)C S'IL Y A UNE LISTE DE PROPRIETES LOGE EN TWTE AT ET ENSUITE VL1 APPEL IMMDRT(VLtIMHGCH(AT.LSG<CONTCLST-im)
RETOURFIN
FONCTION LISTAVILSTJC CREE UNE LISTE DE PROPRIETES DE LA LISTE LST
LISTAV«LISTE(9)C PREND POUR VALEUR L'ADRESSE DE CETTE LISTE VIDE
APPEL INSIND(-1»LSD(LISTAV1,-1»LST-1)RETOURFIN
FONCTION MADATRtAT.LSTILSTDES«LSG<CONT<LST-1»)
C S'IL N'Y A PAS DE L. DE P. A LA LISTE LSTtMADATR—»1SI(LSTDES)1,4,1
C MADATR.ADRESSE DE LA CELLULE QUI CONTIENT AT1 MADATR.LSD(CONTILSTDES)»C SI LA L. DE P. EST VIDE MADATR«-18 SI(ID<CONT(MADATR))-2)3»*t33 SIJEGAL(CONT«MADATR-l)tAT)5*6t55 M«LSD(CONTtMADATR»
SI(ID(CONT(MS)-2)7,4»77 MADATR-LSD(CONT<MJ)
ALLER A 8* MADATR—16 RETOUR
FIN
A 20
1C
IDENTIFICATIONFONCTION MTDLSKLST )PREND POUR VALEUR LSTMTDLST=LSTK = LSG ( CON T( LOCK LST )-SI (K) 1»2,1APPEL INSDIR(0,K,K,K)RENVOIE EN RESERVE LAAPPEL MTLIST(X)RETOURFIN
LISTE DE PROPRIETE CELLE CI DEVIENT VIDE
FONCTION IRADLS(L)EFFACE LA LISTE DE PROPRIETE DE L ET REMETLA=LOCKL)+1J= IEFLSKNAMEDL(L ) )APPEL INSIND(-1»0»-1,LA)RETOURFIN
LE POINTEUR A 0
FONCTION LSTMRKILST)PREND POUR VALEUR LA MARQUE DE LA LISTE LST
LSTMRK=ID(CONT<LOCKLST)-l))RETOURFIN
CC
FONCTION MRKLSKMjLST )MARQUE LA LISTE LST DE MPREND POUR VALEUR LSTMRKLST=LSTAPPEL I NS I ND < M »-!»-!» LOCK LST )-l )RETOURFIN
![Gai Luron - [T11] - La Bataille Navale Ou Gai Luron en Slip](https://img.pdfslide.fr/doc/110x75/55cf98fb550346d0339ad6f0/gai-luron-t11-la-bataille-navale-ou-gai-luron-en-slip-568455408fdaf.jpg)
