EXEL

Modèle:Méta bandeau d'avertissementModèle:Contrôle date bandeau{{#if:||{{#ifeq:||[[Catégorie:Article à wikifier{{#if:mai 2019|{{#ifexist:Catégorie:Article à wikifier depuis mai 2019| _depuis mai 2019}}|, date manquante}}]]}}}} Modèle:Sources à lier

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

1. <math>\longleftarrow</math> désigne l'affectation
2. "?" désigne un test, "¿" pour fermer le test (i.e if test then...else... fi).
3. la barre "|" désigne la sélection
4. l' instruction de sélection à choix multiple (i.e l' instruction CASE OF en PASCAL), elle sera explicitée plus loin dans ce paragraphe.
5. <math>\{</math><suite d'instructions avec SORTIE de boucle > <math>\}</math> désigne une boucle.
6. TQ <t> <math>\{</math><suite d'instructions> <math>\}</math> désigne la boucle TANT QUE où t est une expression booléenne.
7. "!" désigne une sortie de boucle, prononcer EXIT.
8. !i désigne une sortie de i boucles imbriquées.!1 est notée !, l'indice 1 est omis
9. !0 désigne l'instruction vide
10. le point virgule ";" sépare deux instructions séquentielles.
11. la virgule "," sépare deux instructions qui s'exécutent en parallèle.
12. le point "." désigne la concaténation de deux chaînes de caractères.
13. le symbole "ʌ" désigne la chaîne vide.
14. l'opérateur de minimisation MU "<math>\mu</math>"
15. <nom de la procédure> ( <paramètres donnés par valeur> → <paramètres résultats nommés> )
16. "..." 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 ><math>\longleftarrow</math>< 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> <math>\{</math><suite d'instructions><math>\}</math>

<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

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

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;

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

Algorithme équivalent :

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

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

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

Algorithme équivalent:

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

Algorithme avec l'instruction TQ:

i←1 ; a[n+1]←x ; TQ a[i]<math>\neq</math> x <math>\{</math> i←i+1 <math>\}</math>

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]<math>\neq</math>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]<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.

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

• Modèle:Ouvrage.
• Modèle:Ouvrage.
• Modèle:Ouvrage.
• Jacques Arsac, New lessons of programming, Paris, Université de Paris 6, Institut de programmation, 150p
• Modèle:Ouvrage.

Livres

• Modèle:Ouvrage — Avec une bibliothèque de programmes écrits en langage EXEL.

Articles

• Modèle:Article.
• Modèle:Chapitre.
• Modèle:Article.
• Modèle:Article
• Modèle:Chapitre
• Modèle:Article.
• Modèle:Article.
• Modèle:Article.
• Modèle:Article.
• Modèle:Article.
• Modèle:Article.
• Colloque international sur la programmation,PARIS,Modèle:Date-, la puissance du langage EXEL, actes pages 148-160.

Thèse

• Modèle:Ouvrage.

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