Voir la source de EXEL

{{Sources à lier|date=novembre 2018}}

{{Travail inédit|date=novembre 2018}}

{{Redirect|EXEL}}

'''EXEL''' est un langage de description algorithmique conçu en 1973 par l'informaticien français [[Jacques Arsac]] qui a baptisé ce langage à partir du mot « excellent ».

Un des buts de ce langage est de décrire un algorithme de façon indépendante du langage dans lequel il sera ensuite implémenté qui, au demeurant, peut être EXEL lui-même... Le langage EXEL permet de préciser aussi bien les caractéristiques des données (matrice quelconque, matrice triangularisée{{etc}}) que les algorithmes eux-mêmes (par exemple [[produit matriciel]]). Un algorithme d'inversion de matrice que l'on compose avec les caractéristiques d'une matrice triangulaire donne automatiquement par simplifications algébriques un algorithme simplifié d'inversion optimisé pour les matrices triangulaires, par exemple.

L'auteur définit le schéma des étapes de la méthode informatique comme suit :   

:Situation  concrète    →     Problème →     Algorithme →   Programme →   Résultats

Au début, il y a un état des choses qui génère un problème: c'est ce que l'auteur désigne par une situation concrète décrite en langue naturelle. Par abstraction, elle lui est associée une représentation formelle. Celle-ci définit le problème. Pour résoudre ce problème, il faudra dans la mesure du possible (problèmes NP-complet...) construire un algorithme. La traduction de cet algorithme dans un langage de programmation constitue le Programme qui sera exécuté sur ordinateur et fournira des résultats. L'interprétation des résultats est laissée aux soins de l'Homme.

L'idée, implicite de la conception du langage EXEL, c'est, dans la mesure du possible, de construire un algorithme  performant, de façon systématique: toutes les transformations et simplifications seront  prises en charge par  la machine, dans ce cas l'ordinateur, permettant d'aboutir aux résultats...  

EXEL est à l'algorithmique ce que la [[géométrie analytique]] est à la géométrie: ou bien d'emblée une solution géométrique est trouvée, sinon en peut toujours rapporter les hypothèses du problème à la géométrie analytique (i.e. coordonnées cartésiennes...). Avec le langage EXEL, ou bien d'emblée un algorithme performant est trouvé, ou bien le langage EXEL  offre  des possibilités pour la manipulation formelle des programmes qui permettent de construire un algorithme performant... Il n'y a pas de méthode générale pour construire un algorithme pas plus qu'il y a une méthode générale pour résoudre les vieux problèmes de construction géométrique, ou pour trouver une démonstration d'un théorème. C'est pourquoi la présentation du langage EXEL se fera à l'aide d'exemples.

L'écriture fréquente de longs programmes avec des langages tels que [[Fortran]], [[Algol (langage)|Algol]], [[Pascal (langage)|Pascal]]... est fastidieuse. Pour permettre une écriture condensée des programmes, à l'instar des mathématiques où il existe des abréviations comme <math>\forall</math>, pour désigner tout élément, <math>\exists</math>, pour il existe... les instructions  du langage EXEL ont été définies comme suit : 

== Instructions du langage EXEL ==
# <math>\longleftarrow</math>  désigne l'affectation 
# "?"  désigne un test, "¿"  pour fermer le test (i.e if test then...else... fi). 
# la barre "|" désigne la sélection 
# l' instruction de sélection à choix multiple (i.e l' instruction CASE OF en PASCAL), elle sera explicitée plus loin dans ce paragraphe.
# <math>\{</math><suite d'instructions avec SORTIE de boucle > <math>\}</math>  désigne une boucle. 
# TQ <t> <math>\{</math><suite d'instructions> <math>\}</math> désigne la boucle TANT QUE où t est une expression booléenne. 
# "!"  désigne une sortie de boucle, prononcer EXIT. 
# !i  désigne une sortie de i boucles imbriquées.!1 est notée !, l'indice 1 est omis 
# !0 désigne l'instruction vide 
# le point virgule ";"  sépare deux instructions séquentielles. 
# la virgule ","  sépare deux instructions qui s'exécutent en parallèle. 
# le point "." désigne la concaténation de deux chaînes de caractères. 
# le  symbole "ʌ" désigne la chaîne vide.
# l'opérateur  de minimisation MU  "<math>\mu</math>" 
# <nom de la procédure> ( <paramètres donnés par valeur> → <paramètres résultats nommés> ) 
# "..." les commentaires figurent entre double quotes. 

=== L'instruction de sélection multiple ===
Soient t1,t2 deux prédicats, a1,a2,a3,a4 les alternants qui sont sélectionnés selon l'indication donnée devant chacun d'eux :

la première lettre se rapporte au premier prédicat et la deuxième au second. F désigne la valeur FAUX et V la valeur VRAI.

L'instruction de sélection multiple est notée:

(t1,t2)`? FF :a1 | FT : a2 | TF : a3 | TT : a4 

ainsi, a2 est exécutée si t1 est faux et t2 est vrai...

== Instructions fondamentales ==
Le langage EXEL se compose de trois types d'instructions fondamentales :  

=== L'instruction d'affectation ===
L'instruction d'affectation est notée :
: <code>< nom ><math>\longleftarrow</math>< valeur ></code>
:: < nom > est le nom d'une variable, simple ou indicée.
::< valeur > désigne toute constante, variable ou expression possédant une valeur.

Les expressions seront écrites suivant les conventions de l'algèbre, en utilisant des parenthèses pour préciser  la priorité entre opérateurs dès que l'on s'écarte des cas les plus usuels (par exemple, ET, OU...).

=== L'instruction de sélection ===
La sélection est notée :
: <code>< test >?< suite d'instructions séparées par ; >|< suite d'instructions séparées par ; >¿</code> 

Si le test est VRAI, on exécute la suite d'instructions à droite de la barre, SINON, on exécute la suite d'instructions à gauche de la barre. 

:: <suite d'instructions> est une suite quelconque d'instructions, peut éventuellement être réduite à une seule instruction ou même vide. 
:: <test> est une expression booléenne. Le test est évalué : Si sa valeur est FAUX, la suite d'instructions à gauche de la barre est exécutée, et l'instruction de sélection est terminée. Si la valeur est VRAI, la suite d'instruction à droite de la barre est exécutée, et l'instruction de sélection est terminée.  

=== L'itération ===
On distingue deux formes de l' itération :

==== Boucle TANT QUE ====
L'itération avec l'instruction TQ, c'est la forme la plus fréquente :
: TQ <t> <code><math>\{</math><suite d'instructions><math>\}</math></code>
:: <code><t> est une expression booléenne.L</code>'exécution se fait comme suit :

#évaluer t 
#si t est VRAI, exécuter la suite d'instructions et revenir en 1 sinon l'itération est terminée.

==== Boucle avec sortie ====
<code><math>\{</math><suite d'instructions avec sortie de boucle notée !><math>\}</math></code>

La suite d'instructions entre accolades est exécutée tant que l' on atteint pas le signe !. Lorsqu' il est atteint, on sort de la boucle et on continue en séquence.EXIT doit être interprétée comme sortir de l' itération englobante, et continuer en séquence après elle.Par extension, on peut indicer !. Ainsi,!p indique la sortie de p itérations englobantes, !1 est notée !, l'indice 1 est omis. 

== Exemples ==

=== Exemple 1: l'affectation ===
Soit à échanger le contenu de deux cases mémoire : 

On distingue l'adresse d'une case mémoire à laquelle est associée la variable A, et son contenu auquel est associé une valeur, par exemple a. 

De même pour une autre case mémoire à laquelle est associée une variable B et une valeur b. 

Soit C une variable intermédiaire permettant de sauvegarder le contenu de A. 

Algorithme:

<code>C←A;   A←B;  B←C</code>

Remarque : Dans toute la suite des exemples présentés, les instructions d'entrées sorties seront omises, selon la définition du langage EXEL.  

=== Exemple 2: La sélection ===

==== La valeur absolue ====
La valeur absolue d'une variable x, |x| = si x>0 alors x sinon -x. Ce qui s'écrit en langage EXEL :  
: <code>|x| = x>=0 ?  -x | x  ¿</code>

Remarque : La notion de variable en informatique diffère de la notion de variable en mathématiques :

En mathématiques, le contenu d'une variable est constant, en informatique, le contenu d'une variable dépend de l'instant où la variable  est considérée.

==== La borne supérieure ====
===== Exemple1 =====
sup(a,b) = si a>=b alors a sinon b. Ce qui s'écrit en EXEL

<code>sup(a,b) = a>=b ? b | a ¿</code>

===== Exemple2 =====
sup(a,b,c) = sup(sup(a,b),c)

sup(a,b,c) = sup(a,b)>=c?  c |  sup(a,b)<code>¿</code>

sup(a,b,c) = (a>=b ? b | <code>a ¿</code>)   >=c?   c | a >=b?  b | a <code>¿¿</code>

=== Exemple 3 : l'itération ===
En informatique, une opération répétitive est désignée par le mot itération, en mathématiques par la récurrence. C'est le raisonnement par récurrence qui permet de construire des algorithmes itératifs. C'est un axiome dans la théorie des nombres entiers que Peano définit comme suit :
: Soit P une propriété vérifiée pour la valeur 0, si cette propriété est, dès qu'elle est vraie pour i alors elle est vraie pour i+1, alors cette propriété est vraie quel que soit i.
Application :

==== La consultation linéaire de table ====
Soit a[1:n] un tableau de n éléments, par exemple les numéros de cartes d'identité.

Soit x un numéro à chercher dans la table.

Soit t une variable booléenne : si x est trouvé dans la table alors  t=Vrai (i.e V) sinon t=Faux(i.e F)

Hypothèse de récurrence :

On suppose que l'on a parcouru la table jusqu'au rang i et x n'est pas trouvé.

Si i>n alors x n'est pas dans la table, sortie de la boucle sinon  si a(i)=x , x est trouvé, sortie de la boucle sinon on incrémente i et on rétablit l'hypothèse de récurrence.

initialisation: i←1

Algorithme en langage EXEL 

I←1. t←F;

<code><math>\{</math></code>i≤n? ! | a[i]=x  ?   i←i+1 | t←V ! <code>¿¿<math>\}</math> </code>

Algorithme équivalent :

I←1. t←F;   <code><math>\{</math></code>i≤n? ! | a[i]≠x ? t←V  ! | i←i+1 ¿¿<code><math>\}</math> </code>

Remarque : L'utilisation d'une variable booléenne n'est pas nécessaire. En effet d'après la définition du langage EXEL, à la sortie d'une boucle, on peut récupérer la valeur d'une variable contrôlée. De ce fait, si i≤n  alors x est dans la table. Cependant, encore faut-il que le compilateur dans lequel l'algorithme sera implémenté respecte cette caractéristique, ce qui est rarement le cas. Cela étant, en tenant compte de cette caractéristique, l'algorithme précédent devient:

I←1.<code><math>\{</math></code>i≤n? ! | a[i]≠x ?  ! | i←i+1 ¿¿<code><math>\}</math> </code>

si i≤n alors x est dans la table à la position i sinon x n'est pas dans la table..

Les tests utilisent plusieurs cycles d'horloge selon les machines, cette boucle peut être accélérée : 

Par insertion de x à la case n+1, l'algorithme devient :
: i←1 ; a[n+1]←x ; <code><math>\{</math>a[i]=x? i←i+1 | t←V !¿<math>\}</math> </code>

Algorithme équivalent :
: i←1 ; a[n+1]←x ; <code><math>\{</math>a[i]≠x? t←V ! | i←i+1 ¿<math>\}</math> </code>

Algorithme avec l'instruction TQ :
: i←1 ;     a[n+1]←x ; TQ   <code>a[i]</code><math>\neq</math> x  <code><math>\{</math> i←i+1 <math>\}</math> </code>

Cet ajout de x à la case n+1 n 'est possible que si la table n'est pas saturée...

Remarque : L'ordre des éléments dans la table est quelconque. Toutefois on peut trier la table (voir chapitre des tris) par ordre de fréquence d'accès décroissant. La recherche est d'autant plus courte que le rang de l'élément cherché est plus petit. D'autre part on a admis implicitement que l'élément cherché était unique, ce n'est pas le cas général. il peut exister plusieurs éléments correspondant à l'élément cherché; d'où l'importance du plus petit indice i tel que a[i]=x noté ainsi : 
: k=MU(i : a[i]=x), si k=n+1,  x n'est pas dans la table.

Remarque : L'auteur met en garde contre l'utilisation de la boucle « TANT QUE » qui parfois est source d'erreurs de programmation et complique les preuves de programme... À cet effet il cite l'exemple de l'algorithme suivant  censé faire une consultation de table et qui est erroné :
: i←1 ; TQ  <code>i≤n  et </code>a[i]<math>\neq</math>x FAIRE <code>i←i+1 FIN FAIRE</code>

Si x n'est pas dans la table, l'indice i atteint la valeur n+1, et le compilateur est censé vérifier la deuxième condition du test qui est a[i]<math>\neq</math>x, or a[n+1] n'est pas définie ce qui devrait générer un message d'erreur. Cependant, certains compilateurs, dès que le premier test est FAUX, ils continuent en séquence et ne signalent pas d'erreur.

===== Complexité =====
Il faut au plus n opérations pour trouver x, d'où la complexité d'une consultation linéaire de table est de l'ordre de n.

==== La consultation de table par dichotomie ====
Autre exemple pour l'itération:la consultation de table par dichotomie.

==== La consultation de table par hachage(i.e Hash coding) ====
La consultation de table par hachage est un autre exemple de l'itération.

=== Exemple 4: la récursivité ===
{{...}}

== Commentaires ==
Les commentaires seront insérés entre double quôtes "..." ils seront  explicites, ou bien font référence à des commentaires détaillés placés hors du programme.(l'excès  de commentaires dans le programme ombragent les instructions)

== Sources ==
; Cours
* {{Ouvrage|auteur1=Jacques Arsac|titre=The EXEL language|lieu=Paris|éditeur=Université de Paris VI, Institut de programmation|nature ouvrage=A.E.A. Fondements de la programmation|année=|pages totales=62|isbn=|sudoc=147352657}}.
* {{Ouvrage|auteur1=Jacques Arsac|titre=Cours de programmation avec EXEL|lieu=Paris|éditeur=Université de Paris VI, Institut de programmation|nature ouvrage=Licence en informatique|année=1978|pages totales=109|isbn=}}.
* {{Ouvrage|auteur1=Jacques Arsac|titre=Nouvelles leçons de programmation avec EXEL|lieu=Paris|éditeur=Université de Paris VI, Institut de programmation|année=|isbn=}}.
* Jacques Arsac, ''New lessons of programming'', Paris, Université de Paris 6, Institut de programmation, 150 p.
* {{Ouvrage|auteur1=Jacques Arsac|titre=Cours de programmation|lieu=Paris|éditeur=Université de Paris VI, Institut de programmation|nature ouvrage=DEUG|année=1980|pages totales=80|isbn=}}.
; Livres
* {{Ouvrage|auteur1=Jacques Arsac|titre=La construction de programmes structurés|lieu=Paris|éditeur=[[Éditions Dunod|Dunod]]|année=1977|isbn=}} — Avec une bibliothèque de programmes écrits en langage EXEL.
; Articles
* {{article
 |auteur1= Jacques Arsac
 |titre =  Quelques remarques et suggestions sur la justification des algorithmes
 | journal =Revue francaise d'automatique informatique recherche operationnelle
 |volume = B3 ({{5e}} année)|numéro = 3 |issn = 0397-9326|année = 1976 | pages =  3-27}}.
* {{chapitre 
 |auteur1= Jacques Arsac
 |titre chapitre=Langages sans etiquettes et transformations de programmes
 |titre ouvrage = Automata, Languages and Programming |collection = Lecture Notes in Computer Science
 |auteur ouvrage = J. Loeckx (éditeur)
 |numéro dans collection=14|année=1974|passage=112–128|issn=0302-9743
 |doi=10.1007/978-3-662-21545-6_8
 |présentation en ligne = https://link.springer.com/chapter/10.1007/978-3-662-21545-6_8#page-1}}.
* {{article
 |auteur1= Jacques Arsac|auteur2= Gilles Blain|auteur4= Gilles Ruggiu|auteur3= Louis Nolin|auteur5= Jean-Pierre Vasseur
 |titre =  Le système de programmation structurée EXEL
 | journal =Revue Technique Thomson-CSF |issn = 0035-4279 |volume = 6 |numéro = 3 |année = 1974 | pages =  715-736}}.
* {{Article|prénom1=Jacques|nom1=Arsac
|lien auteur1= Jacques Arsac
|titre=Syntactic source to source transforms and program manipulation
|périodique=Communications of the ACM|mois=janvier|année=1979|volume=22
|numéro=1|pages=43 - 54 |doi= 10.1145/359046.359057}}
* {{chapitre|langue=en |auteur1= Louis Nolin|auteur2=Gilles Ruggiu
|titre chapitre= Formalization of Exel|auteurs ouvrage= Patrick C. Fischer et Jeffrey D. Ullman (éditeurs)|titre ouvrage= ACM Symposium on Principles of Programming Languages|éditeur= ACM Press|année= 1973|passage= 108-119 |doi= 10.1145/512927.512937|présentation en ligne=http://doi.acm.org/10.1145/512927.512937}}
* {{article|auteur=Frédéric Boussinot|titre =  Un interpreteur utilisant un appel par nécessite avec partage pour l'évaluation des expressions de procedure du langage EXEL
 | journal =Revue Technique Thomson-CSF |issn = 0035-4279 |volume = 11|numéro =4 |année = décembre 1979 | pages =  921-942}}.
* {{Article
|auteur1= Bernard Robinet | auteur2 = François Nozic
|titre= Grammaire du langage EXEL, interpréteur EXEL, sémantique des structures de contrôle
|périodique= RAIRO Informatique théorique
|volume= 11
|numéro= 1
|date= 1977
|pages= 63-74
}}.
* {{Article
|auteur1= Bernard Robinet
|titre= Un modèle fonctionnel des structures de contrôle
|périodique= RAIRO Informatique théorique
|volume= 11
|numéro= 3
|date= 1977
|pages= 213-236
}}.
* {{Article
 |auteur1= Jacques Arsac|auteur2= Christian Galtier
 |auteur3= Gilles Ruggiu|auteur4= Tran Van Khai|auteur5= Jean-Pierre Vasseur
 |titre= The Edelweiss system
 |périodique= Advances in Electronics and Electron Physics
 |volume= 48
 |éditeur = Elsevier
 |date= 1979
|pages= 201-270
|doi = 10.1016/S0065-2539(08)60307-8
|présentation en ligne = https://www.sciencedirect.com/science/article/pii/S0065253908603078
}}.
* {{article|auteur=Guy Cousineau|titre =  La programmation en EXEL 
 | journal =Revue Technique Thomson-CSF |issn = 0035-4279 |volume = 10 |année = 1978 | pages =  209-234}}.
* {{article|auteur=Guy Cousineau|titre =  La programmation en EXEL 
 | journal =Revue Technique Thomson-CSF |issn = 0035-4279 |volume = 11 |année = 1979 | pages =  13-35}}.
* Colloque international sur la programmation,PARIS,{{date-|Avril 1980}}, la puissance du langage EXEL, actes pages 148-160.

;Thèse
* {{Ouvrage|auteur1=Jean-Louis Planes|titre=Interpréteur EXEL-COBOL|lieu=Paris|éditeur=Université de Paris VI, Institut de programmation|nature ouvrage=Thèse Docteur-Ingénieur|année=1979|isbn=}}.
;Divers
* N. Wirth, ''Introduction à la programmation systématique Paris'', Masson, 1977.

== Voir aussi ==
* Langage [[Haskell]]

== Liens externes ==
{{Liens}}

{{Portail|programmation informatique}}

[[Catégorie:Programmation informatique]]