Comment fonctionne un langage sans pile?

Question

J'ai entendu parler de langues sans pile. Cependant, je n'ai aucune idée de la façon dont un tel langage serait implémenté. Quelqu'un peut-il expliquer?

Answer 1

Les systèmes d'exploitation modernes, nous avons (Windows, Linux) fonctionnent avec ce que j'appelle la "grosse pile de modèle". Et que le modèle est faux, parfois, et motive le besoin de "stackless" les langues.

Le "big stack modèle" suppose qu'un programme compilé va allouer de la pile "cadres" pour les appels de fonction dans une région contiguë de la mémoire, l'utilisation de la machine instructions pour ajuster les registres contenant le pointeur de pile (et en option frame de pile pointeur) très rapidement. Cela conduit à des rapide de la fonction d'appel/retour, au prix d'avoir une grande région contiguë à la pile. Parce que 99.99% de tous les programmes exécutés en vertu de ces nouveaux Systèmes d'exploitation fonctionnent bien avec la grosse pile de modèle, les compilateurs, les chargeurs, et même les OS "savoir" à propos de cette pile. Un problème commun à toutes ces demandes ont est, "quelle doit être ma pile?". Avec une mémoire de dirt cheap, surtout ce qui se passe c'est qu'une grande partie est mise de côté pour la pile (MS par défaut est de 1 mo), et typique de l'appel à candidatures de la structure n'est jamais n'importe où à proximité de l'utiliser. Cependant, si une application ne l'utiliser, il meurt avec un illégal de la mémoire de référence ("je suis désolé Dave, je ne peux pas faire ça"), en vertu de l'atteindre, à la fin de sa pile.

La plupart des soi-disant appelé "stackless" les langues ne sont pas vraiment stackless. Ils n'ont tout simplement pas utiliser la zone contiguë de la pile fournis par ces systèmes. Ce qu'ils font, au contraire, est d'allouer un bloc de pile dans le tas sur chaque appel de fonction. Le coût par appel de fonction remonte un peu; si les fonctions sont généralement complexes, ou de la langue est de l'interprétation, ce surcoût est négligeable. (On peut aussi déterminer appel DAGs dans le programme du graphe d'appels et d'allouer un segment segment pour couvrir l'ensemble de la DAG; de cette façon, vous obtenez à la fois d'allocation de tas et de la vitesse de classique grand de la pile des appels de fonction pour tous les appels à l'intérieur de l'appel DAG).

Il y a plusieurs raisons pour l'utilisation d'allocation de segment de pile d'images:

1) Si le programme n'a de profondeur de récursivité dépend de ce problème spécifique, il est à résoudre, il est très difficile de préallouer un "big stack" zone à l'avance car le besoin de la taille n'est pas connue. On peut maladroitement organiser des appels de fonction à vérifier pour voir si il y a assez de pile de gauche, et si non, de réaffecter un plus gros morceau, la copie de la vieille pile et réajuster tous les pointeurs dans la pile; c'est tellement maladroit que je ne sais pas du tout mises en œuvre. L'allocation de stack frames signifie que l'application n'a jamais à dire son triste jusqu'à ce qu'il littéralement pas affectables mémoire à gauche.

2) Le programme de fourches sous-tâches. Chaque sous-tâche nécessite sa propre pile, et donc ne pouvez pas utiliser un "big stack" fourni. Donc, on a besoin d'allouer des piles pour chaque sous-tâche. Si vous avez des milliers de possibles sous-tâches, vous pouvez maintenant besoin de milliers de "gros stacks", et la mémoire de la demande devient soudainement ridicule. L'allocation de pile d'images permet de résoudre ce problème. Souvent, la sous-tâche "piles" reportez-vous à la maison mère des tâches à mettre en œuvre une portée lexicale; comme sous-tâches de la fourche, un arbre de "substacks" est créé un "cactus de la pile".

3) Votre langue a de continuations. Ces principes exigent que les données dans la portée lexicale visible à la fonction actuelle d'une certaine manière être préservé pour les réutiliser ultérieurement. Cela peut être mis en œuvre par la copie parent pile d'images, monter les cactus de la pile, et de continuer.

Le PARLANSE de programmation de langue j'ai mis en place n'1) et 2). Je travaille sur 3).

Answer 2

Stackless Python a toujours une pile Python (bien qu’elle puisse avoir une optimisation d’appel en queue et d’autres astuces de fusion de trames d’appel), mais elle est complètement dissociée de la pile C de l’interprète.

Haskell (tel que généralement implémenté) n'a pas de pile d'appels; l'évaluation est basée sur la réduction graphique .

Answer 3

Il existe un bel article sur le framework de langage Parrot à l' adresse http://www.linux-mag.com/cache/7373/1.html . Parrot n'utilise pas la pile pour appeler et cet article explique un peu la technique.

Answer 4

Je suppose que dans un langage comme lisp, les cadres d’appel sont stockés sur le tas plutôt que dans une pile. Cela simplifie la mise en œuvre des fermetures car vous pouvez ensuite traiter un cadre d'appel en tant qu'objet de première classe disponible pour la récupération de place lorsque la clôture n'est pas référencée. Je pense que les cadres d’appel sont implémentés comme une sorte de structure de graphe, par opposition à une structure plate dans d’autres langues.

Answer 5

Dans le stackless environnements je suis plus ou moins familier avec (machine de Turing, l'assemblage et le Brainfuck), il est commun de mettre en œuvre votre propre pile. Il n'y a rien de fondamental sur d'avoir une pile intégré dans la langue.

Dans la plupart des pratiques de ces, assemblée, il vous suffit de choisir une région de mémoire disponible pour vous, placez la pile s'inscrire pour pointer vers le bas, puis d'incrémenter ou de décrémenter pour mettre en œuvre votre pousse et pop.

EDIT: je sais que certaines architectures ont consacré des piles, mais elles ne sont pas nécessaires.