Nous oublierons volontairement dans cette section que les listes sont une des structures préexistantes de Caml pour mieux comprendre leur structure, leur puissance et leurs limitations.
Soit E un ensemble. Définissons une suite d’ensembles (En)nN par E0 = {∅} et
En+1 = E × En.
Définition 6.1.1 On appelle ensemble des listes d’éléments de E l’ensemble (E) =
⋃
n
NEn.
Autrement dit une liste d’éléments de E est soit rien, soit un élément de En du type
où les ai sont dans E.
Remarque Ce qui est important à noter, c’est qu’on s’interdit d’utiliser l’associativité du
produit cartésien et donc d’identifier En à En = E ×…×E. En effet cette identification a bien
un sens pour chaque n fixé : il suffit d’identifier (a1,(a2,(…,(an-1,(an,∅)))…)) à (a1,…,an). Par
contre, elle est beaucoup moins significative sur la réunion des En. En particulier la projection
pi : En → E, (a1,…,an)ai n’est plus définie sur ⋃
n
NEn tout entier, mais seulement sur
⋃
n≥iEn.
Définition 6.1.2 On appelle première projection, ou fonction Tête, l’application tete :
(E) \{∅}→ E qui à toute liste non vide d’éléments de E associe son premier élément :
On appelle deuxième projection, ou fonction Queue, l’application queue : (E) \{∅}→
(E) qui à toute liste non vide d’éléments de E associe son deuxième élément :
On peut reprendre de manière inductive la définition des listes d’éléments de E. Elle se fonde sur les deux règles suivantes
ce que l’on peut encore symboliser sous la forme
ou si l’on préfère par
Ceci correspond exactement à la définition d’un type construit en Caml, où l’on désigne par le paramètre de type ’a le type des éléments de E.
|
La construction des fonctions Tête et Queue se fait alors par :
|
Quant à l’ajout d’un élément en tête de liste, il peut se faire par la fonction cons (à ne pas confondre avec le constructeur Cons)
|
Remarque On constate que dans une liste construite par une application répétée de cette fonction cons, le seul élément auquel on peut accéder directement est le dernier élément qui a été ajouté. On dit encore que la liste est une structure de type LIFO : last in first out ou encore dernier entré premier sorti
En fait Caml contient un type liste déjà défini et que nous utiliserons par la suite. Il est défini exactement comme ci dessus à deux petites différences près qui portent uniquement sur les notations
Nous allons montrer comment l’on peut définir une opération sur les listes. Toutes les démonstrations de ce paragraphe seront faites par induction structurelle en partant de la définition inductive d’une liste, suivant le schéma décrit par la proposition informelle suivante.
Proposition 6.1.1 Soit f une fonction sur les listes d’éléments de E. On suppose que
Alors f fournit le résultat attendu sur toute liste d’éléments de E.
La définition d’une liste étant récursive, les procédures naturelles sur les listes sont elles mêmes récursives. Nous en donnerons néanmoins presque toujours une version itérative, nous réservant un paragraphe final pour confronter facilité d’écriture et efficacité.
Dans les premières opérations, nous privilégierons les fonctions tete et queue sur la reconnaissance de motifs, dans un souci de généralisation à d’autres langages que Caml. Mais au fur et à mesure, dans un souci de lisibilité accrue, nous privilégierons la reconnaissance de motifs ; nous conseillons au lecteur de faire l’effort de traduction dans les deux sens.
A l’aide des fonctions Tête et Queue, on peut parcourir toute une liste
et en afficher les divers éléments dans l’ordre (nous supposons connue une fonction print qui affiche les éléments de E de type ’a)
|
Proposition 6.1.2 La procédure print_liste affiche tous les éléments d’une liste dans l’ordre.
Démonstration: par induction structurelle. Si la liste est vide, la procédure ne fait rien ce qui est le résultat attendu. Si la liste est de type (a,l) et si la procédure affiche correctement l, alors la procédure commence par afficher a, puis affiche la liste l, ce qui est bien le résultat attendu.
La procédure précédente est le type même d’un sous-programme plus général qui applique une fonction f à tous les éléments d’une liste, en ignorant tous les résultats. Utilisant le caractère fonctionnel de Caml, nous pouvons en faire une procédure à deux paramètres, la fonction f et la liste l que nous nommerons liste_iteration. Appliquée à une fonction f et à une liste (a1,(a2,(…,(an-1,(an,∅)))…)) elle est équivalente à
for i = 1 to n do f(ai) done
|
Proposition 6.1.3 La procédure liste_iteration applique bien une fonction f à tous les éléments d’une liste, dans l’ordre, en ignorant tous les résultats obtenus.
Démonstration: par induction structurelle comme dans la démonstration précédente.
Remarque Notre procédure d’affichage peut se définir par
let print_liste l = liste_iteration print l
ou encore plus simplement (en utilisant la programmation fonctionnelle) par
let print_liste = liste_iteration print
Dans le même ordre d’idée, étant donnée une fonction f : E → F, il existe une unique
application mf : (E) →
(F) qui envoie la liste vide sur la liste vide, et qui envoie la liste
(a1,(a2,(…,(an-1,(an,∅)))…)) sur la liste (f(a1),(f(a2),(…,(f(an-1),(f(an),∅)))…)) On peut la
définir en Caml de manière fonctionnelle sous le nom map_liste par
|
ou avec une reconnaissance de motifs
|
La longueur d’une liste se calcule de manière récursive
|
ou itérative : on introduit une référence sur l, puis on remplace au fur et à mesure l par sa queue en incrémentant un compteur i, jusqu’à obtenir la liste vide ; un invariant évident de la boucle est i + longueur(l) après l’exécution du corps de la boucle ; on voit que la fonction est un peu plus compliqué
|
On peut par un simple parcours rechercher le maximum d’une liste d’entiers positifs par
D’où une procédure récursive
|
On peut également en donner une version itérative en parcourant toute la liste et en actualisant au fur et à mesure une référence sur le maximum trouvé (un invariant de la boucle est que m = max(a1,…,ai) après la i-ième itération)
|
On peut par un simple parcours rechercher le n-ième élément (n ≥ 1) d’une liste par
D’où une fonction récursive :
|
Une procédure itérative peut être écrite suivant la même méthode que précédemment en remplaçant au fur et à mesure des itérations la liste par sa Queue, et en interrompant brutalement la boucle indexée si la liste devient vide ; un invariant de boucle est qu’après la i-ième exécution du corps de la boucle, la liste contient ai+1,…,am où m est la longueur de la liste.
|
Etant donné une liste (a1,(a2,(…,(an-1,(an,∅)))…)), on cherche à construire la liste miroir (c’est à dire inversée) (an,(an-1,(…,(a2,(a1,∅)))…)). Une première solution récursive se présente à nous si nous disposons d’une fonction de concaténation de deux listes comme nous allons la définir dans le paragraphe suivant. Elle se fonde sur le raisonnement inductif suivant
Ce qui conduit à la fonction suivante :
|
La validité de la fonction est tout entière contenue dans le raisonnement inductif. Faisons
par contre une étude de complexité. Si n désigne la longueur de la liste l, on voit que la
fonction miroir_quad est appelée n fois, c’est à dire qu’il s’opère n concaténations d’une liste
à n- 1, puis n- 2,… , puis 1 éléments avec une liste à 1 élément. Comme on le verra dans le
paragraphe suivant, la concaténation d’une liste à p éléments a un temps de calcul
proportionnel à p. On en déduit que le temps de calcul d’une image miroir par cet algorithme
est proportionnel à (n - 1) + (n - 2) + … + 2 + 1 = = O(n2), d’où le nom
d’algorithme quadratique. Ceci ne semble guère raisonnable, et effectivement ne l’est
pas.
Pour obtenir un algorithme récursif qui travaille en un temps O(n) nous allons généraliser notre problème d’image miroir en envisageant une fonction de concaténation à l’envers. On veut ici une fonction qui reçoit en paramètres deux listes l1 d’éléments a1,…,am et l2 d’éléments b1,…,bn et qui retourne la liste concaténée l1 *l2 d’éléments am,…,a1,b1,…,bn. La fonction récursive travaille naturellement sur la liste l1
Ceci se traduit en Caml par
|
Proposition 6.1.4 La fonction concatene_envers renvoie le résultat de la concaténation de l’image miroir de l1 avec l2.
Démonstration: par induction structurelle. C’est clair si l1 est la liste vide puisqu’elle renvoie l2. Supposons que la tête de l1 soit h et la queue r, et que la proposition soit vraie pour r. Soit l1 d’éléments a1,…,am et l2 d’éléments b1,…,bn. Alors h : : l2 est la liste d’éléments a1,b1,…,bn, h est la liste d’éléments a2,…,am et la concaténation de l’image miroir de h avec h : : l2 est la liste d’éléments am,…,a1,b1,…,bn, ce que l’on voulait.
Une fois cette fonction de concaténation à l’envers construite, il suffit simplement pour construire l’image miroir d’une liste l de la concaténer à l’envers avec la liste vide. La fonction concatene_envers travaille manifestement dans un temps proportionnel à la longueur de la liste l1, et donc cette fonction miroir calcule l’image miroir d’une liste de longueur n en un temps O(n) (linéaire).
|
La même démarche conduit à une procédure itérative de concaténation à l’envers en utilisant deux références, l’une sur la liste l1 qui décroît, l’autre sur la liste l2 qui s’adjoint au fur et à mesure les éléments de têtes de l1, avec l’invariant de boucle : après la i-ième itération, x1 est la liste d’éléments ai+1,…,an et x2 est la liste d’éléments ai,…,a1,b1,…,bn ; la terminaison est garantie par la décroissance stricte de la longueur de la liste x1.
|
L’image miroir peut alors se construire comme précédemment par concaténation inverse avec la liste vide, ce qui conduit à :
|
On veut ici une fonction qui reçoit en paramètres deux listes l1 d’éléments a1,…,am et l2 d’éléments b1,…,bn et qui retourne la liste concaténée l1 * l2 d’éléments a1,…,am,b1,…,bn.
La fonction récursive travaille naturellement sur la liste l1
ce qui s’écrit :
|
La validité de cette fonction se démontre trivialement par induction structurelle sur la liste l1.
Une version itérative est a priori plus difficile à construire car de toute évidence l’appel récursif n’est pas terminal (il faut ensuite ajouter h en tête). On constate que l’on est un peu bloqué pour construire itérativement la liste d’éléments a1,…,am,b1,…,bn, sachant qu’à la première étape on n’accède aisément qu’à a1 et b1 :
La solution consiste simplement à utiliser les fonctions itératives d’image miroir du paragraphe précédent et à concaténer à l’envers l’image miroir de l1 avec l2, ce qui nous donne
|
Nous recherchons une fonction qui étant donnée une liste d’éléments a1,…,am, un entier
n [1,m + 1] et un élément x de E, nous construise la liste a1,…,an-1,x,an,…,am, où x a été
inséré à la n-ième place L’induction structurelle se formule ainsi
Nous obtenons la fonction suivante (démonstration évidente par récurrence sur n)
|
De nouveau ici la récursivité n’est pas terminale, et il n’est pas facile de donner une version itérative de cette fonction d’insertion. En effet le parcours obligatoire de la liste à partir du premier élément nous oblige a priori à ajouter les éléments successifs en queue de l’accumulateur qui va recevoir le résultat, puis à ajouter x en queue de cet accumulateur et enfin à ajouter les éléments successifs de la liste en queue de l’accumulateur, ce que nous ne pouvons pas faire facilement puisqu’on ne sait ajouter efficacement des éléments qu’en tête d’une liste.
Nous contournerons la difficulté en ajoutant tous ces éléments en tête de l’accumulateur. Le résultat sera bien entendu non pas la liste avec x inséré, mais son image miroir. Il suffit ensuite de prendre l’image miroir de ce résultat stocké dans l’accumulateur. Un invariant de la première boucle est : après la i-ième itération, accu contient ai,…,a1 et n ≤ m ; un invariant de la deuxième boucle est : après la i-ième itération, accu contient an+i,an+i-1,…,an+1,x,an,…,a1.
|
Nous cherchons une fonction qui à une liste l et un élément x associe la liste obtenue en supprimant tous les éléments de la liste égaux à x. L’induction structurelle est
ce qui conduit à
|
Une version itérative est aisément obtenue en cherchant l’image miroir de la liste l et en oubliant d’ajouter les éléments égaux à x. Il suffit ensuite de renvoyer l’image miroir de l’accumulateur. Un invariant de la boucle est : après la i-ième exécution du corps de la boucle, accu contient ceux des élément ai,…,a1 non égaux à x, dans cet ordre.
|
Nous avons construit dans le paragraphe précédent les opérations de base sur les listes avec chaque fois une version récursive et une version itérative. Nous cherchons donc à comparer ces deux modes de programmation sur les listes selon trois points de vue
En ce qui concerne la clarté et la concision, la balance penche de façon évidente en faveur des versions récursives ; ceci favorise également leur démonstration puisque la formulation même des fonctions suit l’induction structurelle qui en constitue par là-même la démonstration.
En ce qui concerne l’efficacité en temps de calcul, il est clair que tous les algorithmes récursifs que nous avons construits ont des temps de calcul en O(n), si n désigne la longueur de la liste traitée. Il peut en sembler de même pour les algorithmes itératifs, qui tous sont constitués d’une boucle qui est effectuée au plus n fois. En fait une partie du travail est masquée par les affectations des références et en particulier les affectations x:=queue !x qui font décroître la liste sur laquelle on travaille : il est clair que le processeur doit commencer par procéder à une recopie de la liste avant de l’affecter et que le temps de cette recopie ne peut être que proportionnel à la longueur de la liste. Nos versions itératives ne sont peut-être pas si linéaires que cela, et un temps de calcul en O(n2) est fort probable.
En ce qui concerne l’efficacité en occupation mémoire, les versions récursives obligent la machine à une sauvegarde du contexte à chaque appel récursif. Par contre, dans les versions itératives, l’encombrement mémoire est uniquement celui des références et peut sembler moindre ; ce n’est vrai que dans la mesure où la machine parvient à récupérer efficacement les emplacements mémoires occupés par les listes qui ne sont plus pointées par les références après leurs affectations répétées, ce qui n’est peut être pas garanti (cela l’est en Caml). De toute façon, cette libération de mémoire prend du temps.
En conclusion, en ce qui concerne les listes, comme en général pour toute structure définie inductivement, les sous-programmes récursifs sont souvent les plus concis, les plus clairs, les moins susceptibles de contenir des erreurs, et les plus efficaces. Il faut donc les privilégier.
Nous allons ici étudier les méthodes de tri de listes, en traitant le cas de listes d’entiers ; le lecteur généralisera facilement au cas du tri d’éléments d’un ensemble ordonné quelconque. Nous n’allons étudier ici que deux tris, particulièrement bien adaptés aux listes : le tri par insertion en O(n2) qui est simple et facile à programmer, le tri par fusion en O(nlog 2n) qui est très efficace en temps de calcul. Nous n’étudierons que des versions récursives de ces tris, les versions itératives ne présentant, comme nous l’avons vu dans le paragraphe précédent, aucun intérêt.
Recherchons tout d’abord comment faire l’insertion (à la bonne place) d’un élément x dans une liste déjà triée l. L’induction structurelle est la suivante
On obtient une fonction Caml (dont le temps de calcul est en O(n) si n est la longueur de l)
|
Le tri par insertion d’une liste est alors très simple
Ceci conduit à une fonction de tri dont le temps de calcul vérifie T(n) = T(n - 1) + O(n) (le O(n) étant dû à l’insertion), soit T(n) = O(n2).
|
Note de programmation Le lecteur pourra généraliser à un ensemble ordonné quelconque muni d’une relation d’ordre total ≺ en passant en paramètre une fonction booléenne f qui renvoie true si x ≺ y. On aura alors
|
Nous renvoyons le lecteur au paragraphe sur les tris pour ce qui concerne le principe du tri par fusion. Rappelons simplement que nous avons besoin de deux fonctions : une fonction de partition qui partage une liste en deux listes de tailles similaires, une fonction de fusion qui fusionne deux listes déjà triées en une nouvelle liste triée. Les démonstrations de ce paragraphe par induction structurelle sont laissées au soin du lecteur : elles ne présentent aucune difficulté.
La fonction de partition opère de manière inductive
On obtient la fonction Caml partage :
|
La fusion de deux listes triées l1 et l2 opère également de manière inductive
On obtient la fonction Caml suivante qui procède par une double reconnaissance de motifs.
|
Le tri par fusion procède alors simplement par partage de la liste, tri récursif des deux listes obtenues et fusion de ces deux listes. Le partage et la fusion ayant visiblement des temps de calcul en O(n), le temps de calcul T(n) du tri par fusion vérifiera T(n) = 2T(n∕2) + O(n), ce qui conduit à T(n) = O(nlog 2n).
|
Les listes sont particulièrement adaptées à des structures mathématiques creuses, c’est à dire où beaucoup d’éléments ont des valeurs par défauts, la plupart du temps 0. C’est ainsi que si l’on travaille avec le polynôme 1 + 3X2 + X100, c’est un épouvantable gâchis de le stocker dans un tableau de taille 101 dont 98 éléments vaudront 0. Nous allons étudier ces objets creux sur deux exemples : les polynômes et les matrices.
L’idée est de stocker un polynôme comme une liste ordonnée de monômes non nuls et de stocker un monôme aiXi sous la forme du couple (i,ai). Un polynôme creux à coefficients réels sera donc stocké comme une liste de couples formés d’un entier positif et d’un nombre réel.
L’addition se fait par une variante très simple de la procédure utilisée pour la fusion de deux listes triées : au lieu de simplement fusionner les deux listes, on procède par addition des coefficients lorsque les degrés des monômes de tête sont les mêmes (et la somme des coefficients non nulle), par simple fusion dans le cas contraire, et ceci récursivement.
|
Pour définir le produit de deux polynômes, on commence par définir le produit d’un polynôme par un monôme de la manière évidente : aXd ∑ i=0nbiXi = ∑ i=0n(abi)Xd+i
|
Puis on définit le produit de deux polynômes par
soit en Caml :
|
Nous laissons le soin au lecteur d’écrire quelques procédures utiles sur les polynômes creux : multiplication par un scalaire, soustraction, puissance, dérivée, dérivée n-ième.
Le principe est le même que pour les polynômes creux, sauf que l’on remplacera le degré du monôme par le couple (i,j) qui indexe l’élément ai,j, ces éléments étant ordonnés par exemple selon l’ordre lexicographique.
|
L’addition des matrices creuses est tout à fait similaire à l’addition des polynômes creux, à la seule différence près que l’on utilise l’ordre lexicographique :
|
En ce qui concerne le produit des matrices creuses, on commence par définir le produit d’une matrice B par une matrice élémentaire du type aEi,j où Ei,j est la matrice qui a des zéros partout, sauf à l’intersection de la i-ième ligne et de la j-ième colonne où figure un 1. On rappelle que Ei,jEk,l = δjkEi,l avec δjk = 1 si j = k et δjk = 0 sinon. On en déduit que si B = bEk,l + B1 alors
Le lemme suivant nous garantit que l’ordre lexicographique sur les indices correspondant à des termes non nuls est conservé.
Lemme 6.1.1 L’ordre lexicographique sur les matrices Ei,j est compatible avec la multiplication à gauche et à droite.
Démonstration: Bien entendu notre affirmation est un peu abusive, à moins de prendre par convention que les deux affirmations A ≺ 0 et 0 ≺ A sont vraies. Ceci signifie simplement que si (i,j) ≺ (i′,j′) et si les produits sont tous deux non nuls, Ei,jEk,l ≺ Ei′,j′Ek,l et de même Ek,lEi,j ≺ Ek,lEi′,j′.
Examinons le premier cas. Le fait que les deux produits soient non nuls nécessite j = j′ = k. Comme (i,j) ≺ (i′,j′), c’est donc que i < i′ et donc (i,l) ≺ (i′,l) soit Ei,jEk,l = Ei,l ≺ Ei′,l = Ei′,j′Ek,l.
Dans le second cas, le fait que les deux produits soient non nuls nécessite i = i′ = l. Comme (i,j) ≺ (i′,j′), c’est donc que j < j′ et donc (k,j) ≺ (k,j′) soit Ek,lEi,j = Ek,j ≺ Ek,j′ = Ek,lEi′,j′.
Ceci conduit à la fonction Caml
|
On peut alors écrire une fonction de produit de matrices creuses comme pour les polynômes creux. Le lemme précédent nous garantit encore une fois que l’ordre lexicographique sur les indices des termes non nuls est conservé.
|
Il arrive souvent qu’en algorithmique on ait besoin de sauvegarder des valeurs. On utilise alors généralement une pile. Qu’est ce qu’une pile ? C’est tout simplement un objet informatique modifiable qui dispose de deux méthodes (sous-programmes), une procédure permettant de ranger une valeur dans cette pile (en général notée push), une fonction retournant une valeur rangée dans cette pile et la supprimant au passage de la pile (en général notée pop). On voit donc qu’une pile est particulièrement adaptée à ranger provisoirement des valeurs dont on n’aura besoin qu’une seule fois par la suite.
Bien entendu, les opérations de rangement dans la pile (on dit plutôt empilage) et les opérations de récupération/suppression dans la pile (on dit plutôt dépilage) ont tendance à être très imbriquées. On peut avoir deux empilages, suivis d’un dépilage, suivi de trois empilages, suivis de quatre dépilages, etc. On distingue deux grandes méthodes de dépilages.
Le premier type de pile est similaire à une pile d’assiettes rangées dans un placard. Lorsqu’on y empile une assiette, elle se trouve sur le dessus. Lorsque l’on dépile une assiette, on la prend sur le dessus. Autrement dit, l’assiette que l’on dépile est toujours la dernière qui a été empilée. On parle alors de pile LIFO pour Last In First Out, soit dernier entré premier sorti. Ces piles portent encore en anglais le nom de stack ; ce sont celles que l’on rencontre le plus fréquemment en informatique, en particulier dans tous les problèmes liés à la récursivité : en effet lorsqu’on revient d’un sous programme appelé, c’est toujours dans le dernier sous programme appelant. C’est ce type de piles que nous allons considérer.
Le deuxième type est similaire à certains distributeurs de gobelets, où l’on introduit les gobelets par le haut et où on les récupère par le bas. Dans ce cas, le gobelet que l’on récupère est toujours le premier qui a été empilé. On parle alors de pile FIFO pour First In First Out, soit premier entré premier sorti. Ces piles portent encore le nom de queue ou files d’attente (analogue à une queue pour aller au cinéma ou pour franchir un péage d’autoroute). Elles sont moins fondamentales pour nous et interviennent principalement dans les gestions de files d’attente et tous les phénomènes où la chronologie a de l’importance (gestion du clavier, des clics de la souris, etc.).
Nous connaissons déjà des structures analogues aux piles LIFO, ce sont les listes. L’élément d’une liste auquel on peut accéder directement est le dernier élément qui y a été entré. Tout ce qu’il nous faut c’est une pile qui est modifiable tout au long du travail et qui dispose de deux sous-programmes push et pop. Le premier sous-programme est une procédure qui ajoute un élément x au sommet de la pile. Le second est une fonction qui renvoie l’élément du sommet de la pile tout en le supprimant de la pile.
Une référence sur une liste est tout à fait adaptée à cet effet et on peut simuler une pile en Caml avec les deux sous programmes. Bien entendu, il est prudent de prévoir un message d’erreur pour le cas où l’on essaye de dépiler dans une pile vide ce qui arrive plus fréquemment qu’on ne le voudrait.
|
Note de programmation En fait Caml dispose déjà dans sa bibliothèque du type stack qui possède deux méthodes push et pop, ainsi qu’une troisième méthode new, fonction qui retourne une pile vide. Si l’on regarde l’implémentation de ce type, il est un tout petit peu plus compliqué qu’on ne pourrait le croire puisqu’on y trouve
|
Pourquoi un type enregistrement modifiable comportant uniquement une liste plutôt qu’une référence sur une liste ? Tout simplement pour permettre à Caml de reconnaître le type d’une pile. En utilisant une référence, nous avons eu beau définir le type ’a pile comme synonyme de (’a list) ref, nous voyons que lorsque Caml nous affiche le type de la fonction push il nous indique ’a list ref -> ’a -> unit et non pas ’a pile -> ’a -> unit. Le synonyme est pour vous, mais vous ne pouvez pas forcer Caml à l’utiliser. Si par contre vous posez
type ’a pile = { mutable pile_contenu : ’a list }
le type ’a pile sera bien défini à l’intérieur de Caml, Caml pourra le reconnaître à coup sûr grâce à l’étiquette pile_contenu et on obtiendra :
|
C’est une méthode élégante et à retenir pour définir de nouveaux types construits.
Remarque Une autre méthode pour construire des piles est d’utiliser un tableau et un compteur indiquant le sommet de la pile. La procédure push est alors simplement i:=!i+1; tab.(!i)<-x (augmenter le compteur et stocker l’élément à la nouvelle place) et la fonction pop est alors i:=!i+1; tab.(!i+1) (diminuer le compteur et renvoyer l’élément suivant). L’inconvénient de cette technique est bien entendu d’obliger dès le départ à estimer la taille nécessaire sous peine de débordement de la pile et à réserver toute cette place, même si on n’en a pas vraiment besoin tout au long du déroulement du programme. On peut également réallouer le vecteur lors d’un débordement.
Elles sont plus difficiles à construire car on ne dispose pas directement de structure dynamique de type FIFO. Nous allons décrire un moyen utilisé par exemple dans les buffers ou tampons de claviers (emplacements mémoires destinés à recevoir les codes des touches sur lesquelles vous avez appuyé, en attendant que le logiciel puisse les traiter).
Si l’on sait que l’on n’aura pas plus de n objets à stocker on utilise un tableau a0,…,an-1 et deux indices indiquant le début et la fin de la pile. On stocke les éléments de manière circulaire dans la pile, c’est à dire que lorsque l’on déborde vers la droite, on revient à gauche de la pile ; autrement dit, on considère ces indices modulo n. On obtient alors les déclarations suivantes :
|
Dans cette déclaration, pf_contenu désigne le tableau de stockage de la pile, pf_taille la taille de ce tableau stockée une fois pour toute pour éviter de la recalculer à chaque empilage ou dépilage, pf_debut pointe sur le premier élément entré (donc celui qui sera le premier à sortir) et pf_fin l’indice de la case qui suit le dernier entré. Nous avons utilisé une petite astuce qui consiste à ajouter 1 à la taille souhaitée et à travailler modulo n + 1. Ceci permet de distinguer aisément une pile vide (quand pf_debut=pf_fin) d’une pile pleine (quand pf_debut désigne la case d’après la case d’indice pf_fin), mais en sacrifiant une place dans la pile.
|
Note de programmation Caml définit une bibliothèque auxiliaire sur les piles FIFO sous le nom queue. Cette bibliothèque n’utilise pas la technique du buffer ou tampon décrite ci dessus, mais au contraire une technique assez compliquée introduisant une structure de liste dont les éléments sont modifiables en place. Cette technique présente l’avantage de croître et décroître dynamiquement suivant les besoins, contrairement à la méthode ci-dessus.
La notation habituelle des expressions algébriques, sous forme dite infixe, où les opérateurs (addition, multiplication, soustraction, division) figurent entre leurs deux opérandes, souffre a priori d’une grande ambiguïté si l’on n’introduit pas de priorités entres les opérateurs. C’est ainsi que la notation 2 + 3 * 4 peut aussi bien désigner 2 + (3 * 4) = 14 que (2 + 3) * 4 = 20. Des parenthèses ou des règles de priorité sont donc nécessaires pour lever cette ambiguïté. Nous allons étudier ici une autre notation, appelée notation algébrique postfixée ou encore notation polonaise inversée qui ne souffre pas de ces inconvénients. Cette notation est utilisée par certains langages de programmation comme Forth ou certaines calculatrices.
Soit E un ensemble (les nombres), un ensemble d’applications de E × E dans E (les
opérateurs) et
un ensemble d’applications de E dans E (les fonctions). On considère
l’ensemble
des suites a1 … an où les ai sont dans E ∪
∪
, qu’on appellera l’ensemble des
expressions algébriques.
Exemple On pourra prendre E = R, = {+,-,*,∕} et
= {sin, cos, exp, log}. Les suites
ci-dessous sont des expressions algébriques
Définition 6.3.1 On appelle ensemble des expressions algébriques postfixées le sous ensemble
de
construit inductivement par les règles suivantes
Proposition 6.3.1 Toute expression algébrique postfixée commence par un nombre et toute expression algébrique postfixée de longueur strictement supérieure à 1 se termine par un opérateur ou par une fonction.
Démonstration: par induction structurelle en appliquant les règles de construction précédentes. Les expressions algébriques de longueur 1 sont les suites n’ayant qu’un seul élément, donc leur premier élément est un nombre ; de plus si A commence par un nombre, aussi bien A B c que A f commencent par un nombre. Ceci montre que toute expression algébrique postfixée commence par un nombre. D’autre part, le seul moyen d’obtenir une expression algébrique postfixée de longueur strictement supérieure à 1 est d’appliquer une des deux dernières règles de construction, et donc l’expression algébrique postfixée se termine forcément par un opérateur ou une fonction.
Exemple On reprend les expressions de l’exemple précédent
Ce dernier exemple montre qu’il n’est pas facile de caractériser immédiatement les expressions algébriques postfixées. Nous allons travailler en deux temps et introduire les deux définitions suivantes
Définition 6.3.2 Soit p : E ∪∪
→ N définie par p(x) = 1 si x
E, p(c) = -1 si
c
et p(f) = 0 si f
. Si A = a1 … am est une expression algébrique, on appelle
poids de A le nombre entier noté p(A) défini par p(A) = ∑
i=1mp(ai).
Définition 6.3.3 Soit A = a1 … am une expression algébrique. On appelle préfixes stricts de A les expressions algébriques Ai = a1 … ai pour 1 ≤ i ≤ m - 1.
Proposition 6.3.2 Soit A une expression algébrique postfixée. Alors A est de poids égal à 1 et tout préfixe de A a un poids supérieur ou égal à 1.
Démonstration: par récurrence sur la longueur de A. C’est clair si A
est de longueur 1, puisqu’alors A = a avec a E et que p(A) = p(a) = 1 ; de
plus A n’a dans ce cas aucun préfixe strict.
Supposons que A est construit par application de la règle 2 ; on a alors A = B C c où B et C sont des expressions algébriques postfixées (de longueur strictement inférieure) et c un opérateur ; l’hypothèse de récurrence donne alors p(A) = p(B) + p(C) + p(c) = 1 + 1 - 1 = 1. Soit A′ un préfixe strict de A. Alors soit A′ est un préfixe de B ou même B, auquel cas par l’hypothèse de récurrence p(A′) ≥ 1, soit A′ = B C′ où C′ est ou bien un préfixe strict de C ou bien C ; alors par l’hypothèse de récurrence p(C′) ≥ 1, soit p(A′) = p(B) + p(C′) = 1 + p(C′) ≥ 2.
Supposons A construit par application de la règle 3 ; on a alors A = B f où B est une expression algébrique postfixée (de longueur strictement inférieure) et f une fonction. Alors p(A) = p(B) + p(f) = 1 + 0 = 1 par l’hypothèse de récurrence. De plus si A′ est un préfixe strict de A, c’est soit B de poids 1, soit un préfixe de B qui par hypothèse de récurrence est de poids supérieur ou égal à 1.
Théorème 6.3.1 Soit A une expression algébrique postfixée de longueur strictement supérieure à 1.
Démonstration: la deuxième assertion est triviale puisque B est le plus long préfixe strict de A et qu’il est de poids 1 d’après la proposition précédente. Montrons maintenant la première. On sait que B est un préfixe strict de A et qu’il est de poids 1 (d’après la proposition précédente). Soit A′ un préfixe strict de A, strictement plus long que B. Alors A′ = B C′ où C′ est un préfixe strict de C ou bien C lui même ; on sait alors que p(C′) ≥ 1 et donc p(A′) = p(B) + p(C′) = 1 + p(C′) ≥ 2. Donc B est bien le plus long préfixe strict de poids 1.
La proposition précédente montre que, contrairement à la notation infixe, la notation postfixée ne présente aucune ambiguïté, ce que nous allons traduire sous forme de corollaire.
Corollaire 6.3.1 L’écriture d’une expression algébrique postfixée de longueur strictement supérieure à 1 sous l’une des deux formes
est unique.
Démonstration: en effet dans les deux cas, B est parfaitement caractérisée par le fait d’être le plus long préfixe strict de poids 1 et dans le premier cas, C n’est autre que A privé de B et du dernier élément de A.
Nous allons revenir à la caractérisation des expressions algébriques postfixées.
Théorème 6.3.2 Une expression algébrique A est une expression algébrique postfixée si et seulement si elle est de poids 1 et tout préfixe strict a un poids supérieur ou égal à 1.
Démonstration: nous avons déjà vu que la condition est nécessaire. Montrons qu’elle est suffisante. Soit A = a1 … am une expression algébrique de poids 1 telle que tout préfixe strict soit de poids supérieur ou égal à 1. Nous allons montrer par récurrence sur m que A est une expression algébrique postfixée. Si m = 1, on a 1 = p(A) = p(a1) donc a1 est un nombre et A est bien une expression algébrique postfixée. Si m > 1, remarquons que si A′ = a1 … am-1, alors A′ est un préfixe strict de A donc p(A′) ≥ 1. Comme p(A) = p(A′) + p(am) = 1, on a nécessairement p(am) ≤ 0, donc am est soit une fonction, soit un opérateur.
Si am est une fonction f, on a p(A′) = 1 ; comme tout préfixe strict de A′ est un préfixe strict de A, il a un poids supérieur ou égal à 1, donc par l’hypothèse de récurrence, A′ est une expression algébrique postfixée, soit A = A′ f est aussi un expression algébrique postfixée.
Si am est un opérateur c, on a p(A′) = 2. A admet au moins un préfixe strict de poids 1, à savoir a1. Soit donc B un préfixe strict de A de poids 1 de longueur maximale ; comme tout préfixe strict de B est un préfixe strict de A, par l’hypothèse de récurrence B est une expression algébrique postfixée. Comme de plus p(A′) = 2, on a B≠A′ soit A′ = B C. On a 2 = p(A′) = p(B) + p(C) = 1 + p(C), donc p(C) = 1. Soit C′ un préfixe strict de C. Alors B C′ est un préfixe strict de A strictement plus long que B, donc p(B C′) ≥ 1 et p(B C′)≠1, soit p(B C′) ≥ 2. Mais p(C′) = p(B C′) - p(B) = p(B C′) - 1 ≥ 1 ; par l’hypothèse de récurrence, C est une expression algébrique postfixée. Mais alors A = B C c est encore une expression algébrique postfixée.
Pour le moment, nos expressions algébriques postfixées sont uniquement des objets formels, des suites de symboles, sans signification. Nous avons seulement appris à les reconnaître et à les manipuler, c’est-à-dire leur syntaxe. Nous allons maintenant donner un sens à ces objets formels, c’est à dire leur définir une sémantique, à travers le théorème suivant.
Théorème 6.3.3 Il existe une unique application Ev de l’ensemble des expressions algébriques postfixées dans l’ensemble E définie inductivement par
Démonstration: ceci découle immédiatement de l’unicité de l’écriture d’une expression algébrique postfixée sous l’une des trois formes, et du chapitre sur la récursion et les définitions inductives de fonctions.
Définition 6.3.4 L’application Ev est appelée l’évaluation. L’élément de E, Ev(A) est appelé l’évaluation de l’expression algébrique postfixée A.
La méthode précédente pour l’évaluation d’une expression algébrique postfixée se heurte à la difficulté de déterminer B et C pour le cas où A = B C c avec c un opérateur. La définition de B comme le plus long préfixe de poids 1 se prête mal à un algorithme. Nous allons donc donner une méthode plus pratique utilisant une pile.
Nous allons définir une suite d’applications de l’ensemble des expressions algébriques postfixées dans l’ensemble des suites d’éléments de E par récurrence de la manière suivante. Soit A = a1 … am une expression algébrique postfixée.
Lemme 6.3.1 Pour tout i ≤ m, fi(A) est défini et la longueur de fi(A) est égale au poids de a1 … ai.
Démonstration: nous allons le montrer par récurrence sur i. C’est clair pour i = 1. Supposons que ce soit vrai pour i ≤ m - 1 et montrons le pour i + 1.
Si ai+1 E, alors il est clair que fi+1(A) est définie et sa longueur est
égale à la longueur de fi(A) plus 1, soit, par l’hypothèse de récurrence, au
poids de a1 … ai augmenté de 1 = p(ai+1), donc au poids de a1 … ai+1.
Si ai+1 est un opérateur, comme on sait que p(a1 … ai+1) ≥ 1 et que p(ai+1) = -1, on a p(a1 … ai) ≥ 2 ; par l’hypothèse de récurrence ce nombre est aussi égal à la longueur de fi(A) ce qui montre que k ≥ 2, donc que fi+1(A) est bien définie. Mais alors la longueur de fi+1(A) est, d’après sa définition, égale à la longueur de fi(A) diminuée de 1, donc au poids de a1 … ai diminué de 1, donc au poids de a1 … ai+1.
Enfin, si ai+1 est une fonction, alors il est clair que fi+1(A) est définie et sa longueur est égale à la longueur de fi(A), soit, par l’hypothèse de récurrence, au poids de a1 … ai, donc au poids de a1 … ai+1 (puisque p(ai+1 = 0). Ceci achève la démonstration du lemme.
Théorème 6.3.4 Soit A une expression algébrique postfixée de longueur m. Alors fm(A) = Ev(A).
Démonstration: par récurrence sur m. Posons A = a1 … am. C’est
clair si m = 1 puisqu’alors f1(A) = a1 = Ev(A). Supposons le résultat vrai
pour toute expression algébrique postfixée de longueur strictement inférieure
à m. Si am = f est une fonction, alors A = B f. Par hypothèse de récurrence
fm-1(A) = fm-1(B) = Ev(B) et donc fm(A) = fEv(B)
= Ev(A).
Si am = c est un opérateur, alors A = B C c où B et C sont des expressions algébriques postfixées. Appelons p la longueur de B, q la longueur de C si bien que m = p + q + 1. Pour tout i ≤ p, on a fi(A) = fi(B) et en particulier pour i = p, par l’hypothèse de récurrence, fp(A) = fp(B) = Ev(B).
On montre maintenant par récurrence sur i [1,q] que fp+i(A) =
Ev(B) fi(C). C’est clair si i = 1 ; supposons le donc pour i et distinguons
suivant le type de ap+i+1. Si ap+i+1
E, alors
Si ap+i+1 est une fonction f, posons fi(C) = b1 … bk avec k ≥ 1 ; on a fp+i(A) = Ev(B) = b1 … bk et donc
Si maintenant ap+i+1 est un opérateur d, posons fi(C) = b1 … bk avec k ≥ 1 ; comme B est le plus grand préfixe de poids 1, le poids de a1 … ap ap+1 …ap+i+1 est au mois égal à 2 et comme p(ap+i+1) = -1, le poids de a1 … ap ap+1 …ap+i est au mois égal à 3 ; mais ce nombre est aussi la longueur de fp+i(A) = Ev(B) fi(C) (par l’hypothèse de récurrence). On a donc k ≥ 2 ; on en déduit que
Pour i = q, on a donc fm-1(A) = Ev(B) fq(C) = Ev(B) Ev(C) par
l’hypothèse de récurrence. On a alors fm(A) = cEv(B),Ev(C)
= Ev(A).
Dans tous les cas, on a bien fm(A) = Ev(A).
Remarque Cette méthode fournit en même temps un vérificateur de la syntaxe de l’expression algébrique A. D’après la caractérisation des expressions algébriques postfixées, A est une expression algébrique postfixée si et seulement si fm(A) est définie (ce qui correspond à tout préfixe strict est de poids supérieur ou égal à 1) et fm(A) est de longueur 1 (ce qui correspond à p(A) = 1).
Pour écrire une procédure Caml, nous allons utiliser une structure de liste pour l’expression algébrique : l’expression algébrique a1 … am sera entrée dans une liste Caml [a1,…,am] ce qui permettra d’en extraire les éléments ai dans l’ordre de leur apparition. Pour permettre d’entrer dans cette liste aussi bien des nombres (ici réels) que des opérateurs (ici +,-,*,∕) et des fonctions (ici sin,cos,exp,log), nous définirons un type construit eap_elt (pour élément d’une expression algébrique postfixée) qui pourra être de l’un des ces trois types, les opérateurs étant symbolisés par des caractères et les fonctions par leur nom :
|
Les manipulations à faire pour calculer les fi(A) sont clairement d’adjoindre un élément ai+1, de retirer deux éléments bk-1 et bk puis d’adjoindre c(bk-1,bk), de retirer bk et d’adjoindre f(bk). Une structure de pile est donc idéale pour cela, puisque ce sont toujours les derniers éléments entrés que l’on doit retirer. Ceci conduit directement à la fonction suivante où nous avons défini une pile accu qui est une référence sur une liste, initialement vide, et deux fonctions adaptées push (qui adjoint un élément à la pile) et pop (qui retire un élément de la pile et renvoie la valeur de cet élément).
La procédure eval effectue tout le travail de manière récursive sur l’expression algébrique. L’invariant évident de ces appels récursifs est qu’après le i-ième appel de la fonction eval, B contient [ai+1;…;am] et accu contient [fi(A)] = [bk;…;b1] (dans l’ordre inverse puisque les listes Caml ont pour premier élément le dernier entré) ; la terminaison est garantie par la stricte décroissance de la liste B ; tout ceci démontre la validité de la fonction.
|
Avec quelques essais :
|
Cette fonction d’évaluation peut être facilement enrichie avec toutes les fonctions et tous les opérateurs usuels.
Remarque les puristes objecteront que la fonction précédente a un double rôle : l’un de vérification de la syntaxe de l’expression algébrique, l’autre d’évaluation de cette même expression ; de ce point de vue, il y a confusion entre la syntaxe et la sémantique. Mais ceci est inhérent aux expressions algébriques postfixées : l’évaluation de l’expression en vérifie en même temps la correction. Une deuxième approche plus générale sera vue à propos des arbres et des expressions algébriques infixes : dans ce cas il y a séparation claire entre l’analyse syntaxique (qui consiste à construire l’arbre de l’expression) et l’évaluation sémantique.