Fonctionnalités

Une pile est une structure de donnée assez simple qui est inspirée des piles d'assiettes. Les actions que l'on peut effectuer sur une pile sont l'empilage d'une assiette au sommet de la pile et le dépilage du sommet de la pile. Cette structure de donnée joue dans tous nos ordinateurs car elle a permis de programmer les fonctions des langages impératifs. La pile permet d'associer à chaque appel de fonctions un environnement où sont placés les arguments. Comme cet espace est alloué dynamiquement, la fonction peut être récursive. La pile des ordinateurs est implémentée par le processeur lui-même, donnant des performances optimales.

Voici les fonctionnalités que l'on attend de la bibliothèque :

• pile-créer() : Retourne une nouvelle pile vide.
• pile?(objet) : Retourne vrai si l'objet est une pile, faux sinon.
• pile-vide?(pile) : Retourne vrai si la pile est vide, faux sinon.
• pile-détruire(pile) : Détruit la pile donnée en argument.
• pile-empile(pile,élément) : Place l'élément au sommet de la pile.
• élément<-pile-dépile(pile) : Retourne l'élément au sommet de la pile.
• pile-affiche(pile) : Affiche à l'écran le contenu de la pile.

En Scheme, la destruction de la pile est gérée par le système. Nous n'avons donc pas à nous préoccuper de cette fonction. A première vue, cela ne fait pas une grande différence avec les langages traditionnels comme C, mais en réalité, le fait de s'affranchir des fonctions de destruction enlève une grande partie de la complexité des programmes. En effet, il peut devenir très complexe de libérer correctement des structures de données cycliques. En Scheme, le mécanisme rammasse-miètes (garbage collector) est capable à tout moment de savoir quelles données ne sont plus utilisées, et donc de les libérer. Le programmeur est donc complètement affranchi de cette tache.

Nous présentons ici trois réalisations en Scheme de la pile. La première utilise des objets Scheme standard, la seconde utilise une méthode couramment utilisée en Scheme, par envoi de message, et enfin la troisième utilise le système orienté objets d'OpenScheme.