Pile (informatique)

En informatique, une pile (en anglais stack) est une structure de données fondée sur le principe « dernier arrivé, premier sorti » (en anglais LIFO pour last in, first out), ce qui veut dire qu'en général, le dernier élément ajouté à la pile est le premier à en sortir^[1].

Pile système[modifier | modifier le code]

La plupart des microprocesseurs gèrent nativement une pile pour les appels de routine^[2]. Elle correspond alors à une zone de la mémoire, et le processeur retient l'adresse du dernier élément.

Architecture x86[modifier | modifier le code]

Dans l'architecture x86 32 bits, le registre ESP sert à indiquer l'adresse du sommet d'une pile dans la mémoire vive^[3]. Les opcodes push et pop permettent respectivement d'empiler et de dépiler des données. Les opcodes call et ret utilisent la pile pour appeler une fonction et la quitter par la suite en retournant à l'instruction suivant immédiatement l'appel^[4].

En cas d'interruption, les registres EFLAGS, CS et EIP sont automatiquement empilés. Dans le cas d'un changement de niveau de priorité lors de l'interruption, les registres SS et ESP le sont aussi.

Une autre pile existe dans les CPU x86, celle de l'unité de calcul flottant (FPU). Plus précisément, cette unité utilise une pile limitée à 8 éléments, et dont le fonctionnement s’apparente à un barillet.

L’élément du barillet courant est nommé st(0), les éléments suivants st(N) avec N compris entre 1 et 7. Cette pile permet d'effectuer des calculs à la manière d'une calculatrice manuelle, en empilant les valeurs, puis en appliquant une opération sur les dernières valeurs empilées par exemple.

Architecture basée sur la pile[modifier | modifier le code]

Article détaillé : Processeur basé sur la pile.

Certains processeurs n'utilisent pas de registre générique, mais uniquement la pile. Les instructions concernent alors ses premiers éléments : par exemple les calculatrices Hewlett-Packard pour l'implémentation de la notation polonaise inverse^[5], les processeurs Focus, ou les machines Burroughs de la gamme B 5000^[6]. Les instructions sont alors souvent plus courtes, car elles n'ont pas à référencer des registres^[7]. Le bytecode du langage Java utilise aussi cette astuce.

Langage de programmation[modifier | modifier le code]

Dans la plupart des langages de programmation compilés, la pile d'exécution est l'endroit où sont empilés tout ou partie des paramètres d'appel des routines. Par ailleurs, on y crée un espace pour des variables locales. La pile est ainsi formée de cadres de piles (en anglais stack frames) comprenant pour chaque routine, en cours d'appel imbriqué, ses paramètres, ses variables locales et son point de retour.

Quelques langages, comme PostScript d'Adobe^[8] ou la commande dc d'Unix, implémentent un mécanisme de pile (avec la notation polonaise inverse) pour les calculs.

Le risque associé[modifier | modifier le code]

Dans tous les langages de programmation, la pile d'exécution contient une quantité limitée de mémoire, habituellement déterminée au début du programme. La taille de la pile d'exécution dépend de nombreux facteurs : la conception du compilateur, l’architecture du processeur, l’utilisation du traitement multithread et la quantité de mémoire vive disponible. Lorsque trop d’informations sont enregistrées dans la pile d’exécution, la pile déborde et écrase des zones de programme à l’extérieur de la pile : on dit alors qu’il y a dépassement de pile. Il en résulte généralement une interruption du programme^[9].

Primitives[modifier | modifier le code]

Voici les primitives communément utilisées pour manipuler des piles^[10] :

« Empiler » : ajoute un élément sur la pile. Le terme anglais correspondant est push.
« Dépiler » : enlève un élément de la pile et le renvoie. Le terme anglais correspondant est pop.
« La pile est-elle vide ? » : renvoie vrai si la pile est vide, faux sinon.
« Nombre d'éléments de la pile » : renvoie le nombre d'éléments dans la pile. Selon les implémentations, peut être fait soit en temps constant soit en temps linéaire.
« Quel est l'élément de tête ? » : renvoie l'élément de tête sans le dépiler. Le terme anglais correspondant est peek ou top.
« Vider la liste » : dépiler tous les éléments. Selon l'implémentation, cela peut être fait en temps constant ou linéaire. Le terme anglais correspondant est clear.
« Dupliquer l'élément de tête » et « échanger les deux premiers éléments » : existe sur les calculatrices fonctionnant en notation polonaise inverse. Les termes anglais correspondants sont dup et swap respectivement.

Il n'existe pas de normalisation pour les primitives de manipulation de pile : leurs noms sont donc indiqués de manière informelle. Seules les trois premières sont réellement indispensables, les autres pouvant s'en déduire.

Algorithmes[modifier | modifier le code]

Cette implémentation est celle utilisée dans les processeurs — elle est simple et la pile occupe peu de place. Une implémentation sous forme de liste chaînée est également possible pour des programmes.

algorithmes

 '''Classe Pile'''
 Attributs :
     pile   : tableau[1, MAX] de Objet
     sommet : entier ''{indice du dernier element entre}''
 Methodes
     Mprocédure '''PUSH'''(element)            ''{entre un element (Objet)}''
     Mfonction  '''POP'''() retourne Objet     ''{sort un Objet}'' 
     ''{non données ici}''
     Mfonction  '''FULL'''() retourne booleen  ''{la pile est-elle pleine ? (retourne sommet >= MAX)}''
     Mfonction  '''EMPTY'''() retourne booleen ''{la pile est-elle vide ? (retourne sommet <= 0)}''
     Mfonction  '''SIZE'''() retourne entier   ''{retourne le nombre d'elements (retourne sommet)}
     Mprocedure '''INIT'''()                   ''{constructeur (met sommet à 0)}

 '''Mprocédure''' ''PUSH'' (element)
 ''{ajouter un élément sur la pile}''
 Paramètres :
    (D)   element : Objet
    (D/R) cible   : Pile
 Début
    Si cible.sommet <= MAX
    Alors
       cible.sommet <- cible.sommet + 1
       cible.pile[cible.sommet] <- element
    Sinon
       afficher("Pile pleine")
    Fsi
 Fin

 '''Mfonction''' ''POP'' () retourne objet
 ''{enlever un élément de la pile et le renvoyer}''
 Paramètres :
    (D/R) cible : Pile
 Variables :
    Element : objet
 Début
    Si cible.sommet > 0
    Alors
       Element <- cible.pile[cible.sommet]
       cible.sommet <- cible.sommet - 1
    Sinon
       afficher("Pile vide")
    Fsi
    Retourner Element
 Fin

Applications[modifier | modifier le code]

Les algorithmes récursifs utilisent une pile d'appel. Dans un langage non récursif (Fortran par exemple), on peut simuler la récursivité en créant les primitives de gestion d'une pile^[11].
Dans un navigateur web, une pile sert à mémoriser les pages Web visitées. L'adresse de chaque nouvelle page visitée est empilée et l'utilisateur dépile l'adresse courante pour accéder à la page précédente en cliquant le bouton « Afficher la page précédente ».
L'évaluation des expressions mathématiques en notation post-fixée (ou polonaise inverse) utilise une pile^[5].
La fonction « Annuler la frappe » (en anglais Undo) d'un traitement de texte mémorise les modifications apportées au texte dans une pile.
Un algorithme de recherche en profondeur utilise une pile pour mémoriser les nœuds visités^[10]. Par exemple, on peut inverser un tableau ou une chaîne de caractères en utilisant une pile. Il suffit d'empiler les éléments sur une pile puis de reconstituer le tableau (ou la chaîne) inverse en dépilant les éléments.

Notes et références[modifier | modifier le code]

↑ Informations lexicographiques et étymologiques de « pile » (sens C3) dans le Trésor de la langue française informatisé, sur le site du Centre national de ressources textuelles et lexicales
↑ C'est le cas pour le MOS Technology 6502 et le Z80 de Zilog : Rodnay Zaks, Programming the Z 80, Sybex, 1979 (réimpr. 1980, 1981), 630 p. (ISBN 0-89588-094-6 et 2-902414-20-X, lire en ligne) ; pour les processeurs de la famille x86, cf. Jon Erickson, Techniques de HAcking, Pearson France, 1979 (réimpr. 2012), 500 p. (ISBN 978-2-7440-2536-5), p. 43,73,134
↑ Cf. Erickson, op. cit. p. 42
↑ Pierre Marchand, « Structure interne des ordinateurs. Supplément: Initiation à l'assembleur », sur Université de Laval - Département d'informatique, automne 2001 (consulté le 6 juin 2021)
↑ ^{a et b} J.-P. Zanotti, « XIV. Évaluation avec une pile », sur Algorithmique pour la licence
↑ (en) Alastair J. W. Mayer, « The Architecture of the Burroughs B5000 - 20 Years Later and Still Ahead of the Times? », ACM's Computer Architecture News,‎ 1982 (lire en ligne).
↑ Koopman 1989.
↑ (en) Charles Geschke et John Warnock, PostScript Language - Tutorial and Cookbook, Addison & Wesley Publ., 1985 (ISBN 0-201-10179-3), « 2. The PostScript stack »
↑ (en) Burley, James Craig, « Using and Porting GNU Fortran », 1^er juin 1991.
↑ ^{a et b} Cf. par ex. Alfred V. Aho, John E. Hopcroft et Jeffrey D. Ullman (trad. J.-M. Moreau), Structures de données et algorithmes [« Data Structures and Algorithms »], Paris, InterEditions et Addison-Wesley Europe, 1983 (ISBN 2729601945), « 2. Types de données abstraites élémentaires ».
↑ Cette technique est détaillée notamment dans Bertrand Meyer et Claude Baudoin, Méthodes de programmation, Eyrolles, coll. « Études et Recherches d'EdF », 1984

Annexes[modifier | modifier le code]

Bibliographie[modifier | modifier le code]

[Koopman 1989] (en) Lawrence Philip Koopman, Stack Computers, New York, The Journal of Forth Application and Research, 1989 (lire en ligne).

Articles connexes[modifier | modifier le code]

Portail de la programmation informatique

[1] Informations lexicographiques et étymologiques de « pile » (sens C3) dans le Trésor de la langue française informatisé, sur le site du Centre national de ressources textuelles et lexicales

[Zaks-2] C'est le cas pour le MOS Technology 6502 et le Z80 de Zilog : Rodnay Zaks, Programming the Z 80, Sybex, 1979 (réimpr. 1980, 1981), 630 p. (ISBN 0-89588-094-6 et 2-902414-20-X, lire en ligne) ; pour les processeurs de la famille x86, cf. Jon Erickson, Techniques de HAcking, Pearson France, 1979 (réimpr. 2012), 500 p. (ISBN 978-2-7440-2536-5), p. 43,73,134

[Erickson-3] Cf. Erickson, op. cit. p. 42

[Marchand-4] Pierre Marchand, « Structure interne des ordinateurs. Supplément: Initiation à l'assembleur », sur Université de Laval - Département d'informatique, automne 2001 (consulté le 6 juin 2021)

[Zanotti-5] {a et b} J.-P. Zanotti, « XIV. Évaluation avec une pile », sur Algorithmique pour la licence

[Mayer-6] (en) Alastair J. W. Mayer, « The Architecture of the Burroughs B5000 - 20 Years Later and Still Ahead of the Times? », ACM's Computer Architecture News,‎ 1982 (lire en ligne).

[Koopman1989-7] Koopman 1989.

[BlueBook-8] (en) Charles Geschke et John Warnock, PostScript Language - Tutorial and Cookbook, Addison & Wesley Publ., 1985 (ISBN 0-201-10179-3), « 2. The PostScript stack »

[9] (en) Burley, James Craig, « Using and Porting GNU Fortran », 1^er juin 1991.

[Aho,_Hopcroft_&_Ullman-10] {a et b} Cf. par ex. Alfred V. Aho, John E. Hopcroft et Jeffrey D. Ullman (trad. J.-M. Moreau), Structures de données et algorithmes [« Data Structures and Algorithms »], Paris, InterEditions et Addison-Wesley Europe, 1983 (ISBN 2729601945), « 2. Types de données abstraites élémentaires ».

[Meyr-Baudw1-11] Cette technique est détaillée notamment dans Bertrand Meyer et Claude Baudoin, Méthodes de programmation, Eyrolles, coll. « Études et Recherches d'EdF », 1984

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]