Pile spaghetti
Pour les articles homonymes, voir Pile et Spaghetti (homonymie).
Une pile spaghetti (ou pile cactus, pile saguaro ou in-tree) en informatique est un arbre enraciné N-aire dans lequel les nœuds fils ont un pointeur vers leur nœud père (mais pas l'inverse).
Lors d'un parcours d'un nœud feuille en suivant ses ancêtres vers le nœud racine, la structure est semblable à une pile en liste chaînée[1]. En effet, chaque nœud a un seul pointeur vers le nœud "suivant" (père), et ignore si ce père a d'autres enfants. Ni lui ni le père ne peut explorer les autres enfants, puisqu'il n'y a pas de pointeurs descendants.
Par exemple, le compilateur d'un langage tel que C crée une pile spaghetti lorsqu'il ouvre et referme des tables de symboles représentant la portée de chaque bloc. Quand un nouveau bloc est ouvert, une table de symboles est empilée. À la fin du bloc, la portée est refermée et la table de symbole est dépilée. Toutefois cette table est conservée et non détruite, et son nœud conserve un lien vers celui de la table "parente". Ainsi lorsque le compilateur effectuera la traduction de l'arbre syntaxique abstrait, pour toute expression il pourra obtenir la table de symbole correspondant à l'environnement de l'expression, et résoudre les références des identifiants. Pour une variable X au sein de l'expression, on recherche X dans la table feuille (représentant la portée la plus intérieure), puis dans son parent, puis dans son grand-parent récursivement.
Utilisation dans les environnements d'exécution[modifier | modifier le code]
Le terme pile spaghetti est associé à l'implémentation de langages de programmation supportant les continuations. Les piles spaghetti sont utilisées pour implémenter la pile d'exécution contenant les liaisons des variables, et d'autres informations. Avec les continuations, on ne peut pas détruire les variables locales d'une fonction lorsque celle-ci retourne : une continuation mémorisée peut ré-entrer ultérieurement dans la fonction ; elle aura alors besoin de la pile entière pour s'exécuter correctement.
Pour surmonter cette difficulté, les pages de la piles peuvent être allouées dynamiquement (notamment dans le tas), et confiées automatiquement au ramasse-miettes lorsqu'il n'y a plus de continuations les référençant.
Exemples de langages[modifier | modifier le code]
- Langages avec continuations de première classe : Scheme et Standard ML of New Jersey
- Langages où la pile d'exécution peut être consultée et modifiée à l'exécution, comme Smalltalk
- Felix (en)
- Rust (en)
Voir aussi[modifier | modifier le code]
Références[modifier | modifier le code]
- Sponsored Machinery, Proceedings of the 1988 Acm Conference on Lisp and Functional Programming, New York, ACM Press, (ISBN 978-0-89791-273-0)
