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 ,Pascal... est fastidieuse. Pour permettre une écriture condensée des programmes, à l'instar des mathématiques où il existe des abréviations comme , pour désigner tout élément, , pour il existe... les instructions  du langage EXEL ont été définies comme suit :

Instructions du langage EXEL 
   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.
 <suite d'instructions avec SORTIE de boucle >   désigne une boucle. 
 TQ <t> <suite d'instructions>  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  "" 
 <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 :

< nom >< valeur >

< 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 :

< test >?< suite d'instructions séparées par ; >|< suite d'instructions séparées par ; >¿ 

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> <suite d'instructions>

<t> est une expression booléenne.L'exécution se fait comme suit :

1) évaluer t 

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

Boucle avec sortie 
<suite d'instructions avec sortie de boucle notée !>

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:

C←A;   A←B;  B←C

Remarque1 :

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 :  

|x| = x>=0 ?  -x | x  ¿

Remarque2:

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

sup(a,b) = a>=b ? b | a ¿

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

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

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

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;

i≤n? ! | a[i]=x  ?   i←i+1 | t←V ! ¿¿ 

Algorithme équivalent :

I←1. t←F;   i≤n? ! | a[i]≠x ? t←V  ! | i←i+1 ¿¿ 

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.i≤n? ! | a[i]≠x ?  ! | i←i+1 ¿¿ 

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 ; a[i]=x? i←i+1 | t←V !¿ 

Algorithme équivalent:

i←1 ; a[n+1]←x ; a[i]≠x? t←V ! | i←i+1 ¿ 

Algorithme avec l'instruction TQ:

i←1 ;     a[n+1]←x ; TQ   a[i] x   i←i+1  

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

Remarque1 :

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 correspondants à 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.

Remarque2 :  

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  i≤n  et a[i]x FAIRE i←i+1 FIN FAIRE

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]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é

Exemple1: calcul du PGCD

Exemple2: le plus grand élément d'une suite

Exemple3: le calcul de factorielle n

Exemple4: la suite de Fibonacci

Exemple 5: les tris

Exemple1:le tri bulle

Exemple2:le tri par insertion

Exemple3:le tri fusion

Exemple4:le tri topologique

Exemple5: le tri rapide

Exemple6: le tri en épis(heapsort)

Exemple 6:la methode du back_tracking(i.e retour arrière)

Exemple1: le problème des huit reines

Autres exemples

Exemple1:Algorithme du plus court chemin

Exemple2:Ordonnancement et chemin critique

Exemple3:Flot maximal de coût minimal

Exemple4:la méthode out of Kilter

Exemple5:l'affectation(au sens de la recherche opérationnelle )

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
 .
 .
 .
Jacques Arsac, New lessons of programming, Paris, Université de Paris 6, Institut de programmation, 150p
 .
 Livres
  — Avec une bibliothèque de programmes écrits en langage EXEL.
 Articles
 .
 .
 .
 
 
 .
 .
 .
 .
 .
 .
 Colloque international sur la programmation,PARIS,, la puissance du langage EXEL, actes pages 148-160.

Thèse
 .
Divers
 Louis Nolin, 1968, Université Pierre et Marie Curie, Paris/INRIA  ATF : un langage "intelligent":ATF capable, de "s'auto-transformer", "s'optimiser", et "se valider" de "lui même":ATF, précurseur du langage EXEL.
 M. NIVAT - Langages algébriques sur un magma libre et sémantique des schémas de programme 
 Yves Lafont. Logiques, Catégories & Machines. Implantation de Langages de Programmation guidée par la Logique Catégorique. 
N.Wirth.Introduction à la programmation systématique Paris, Masson, 1977.

Voir aussi 
 Langage Haskell

Programmation informatique