Comment fonctionne un langage sans pile?

Question

J'ai entendu parler des 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 que nous avons (Windows, Linux) fonctionnent avec ce que j’appelle le "modèle à grosse pile". Et ce modèle est parfois faux et justifie le besoin de "sans pile". langues.

Le " modèle de grande pile " suppose qu'un programme compilé allouera " des cadres de pile " pour les appels de fonction dans une région contiguë de la mémoire, utiliser très rapidement les instructions de la machine pour régler les registres contenant le pointeur de pile (et le pointeur de trame de pile facultatif). Cela conduit à un appel / retour de fonction rapide, au prix d’une grande région contiguë pour la pile. Parce que 99,99% de tous les programmes exécutés sous ces systèmes d’exploitation modernes fonctionnent bien avec le modèle à grande pile, les compilateurs, les chargeurs et même le système d’exploitation "savoir". à propos de cette zone de pile.

Un problème commun à toutes ces applications est le suivant: "quelle doit être la taille de ma pile?" . Avec une mémoire peu coûteuse, une grande partie de la pile est mise de côté (MS par défaut, 1 Mo), et la structure typique des appels d’applications n’est jamais proche de l’utiliser. Mais si une application utilise tout cela, elle meurt avec une référence de mémoire illégale ("Je suis désolé, Dave, je ne peux pas le faire"), en atteignant le bout de sa pile.

La plupart des soi-disant appelés "stackless" les langues ne sont pas vraiment sans pile. Ils n'utilisent tout simplement pas la pile contiguë fournie par ces systèmes. Au lieu de cela, ils allouent un cadre de pile à partir du segment de mémoire à chaque appel de fonction. Le coût par appel de fonction augmente quelque peu; Si les fonctions sont généralement complexes ou si le langage est interprétatif, ce coût supplémentaire est insignifiant. (Il est également possible de déterminer les groupes de disponibilité de base de données dans le graphe d'appels de programme et d'allouer un segment de segment de mémoire à l'ensemble du groupe de disponibilité de base; de ??cette manière, vous obtenez à la fois l'allocation de segment de mémoire et la vitesse des appels de fonctions classiques à grande pile pour tous les appels dans le groupe de base de données d'appel). / p>

Il existe plusieurs raisons d'utiliser l'allocation de tas pour les trames de pile:

1) Si le programme effectue une récursion profonde en fonction du problème spécifique qu’il résout, il est très difficile de préallouer un "gros stack" région à l'avance car la taille requise n'est pas connue. On peut organiser maladroitement des appels de fonction pour vérifier s'il reste suffisamment de pile et, dans le cas contraire, réaffecter un bloc plus volumineux, copier l'ancienne pile et réajuster tous les pointeurs dans la pile; c'est tellement bizarre que je ne connais aucune implémentation. L’allocation de cadres de pile signifie que l’application n’a jamais à dire ses excuses tant qu’il n’ya pas littéralement plus de mémoire allouable.

2) Le programme crée des sous-tâches. Chaque sous-tâche nécessite sa propre pile et ne peut donc pas utiliser celle "grosse pile". à condition de. Il faut donc allouer des piles pour chaque sous-tâche. Si vous avez des milliers de tâches secondaires possibles, vous pourriez maintenant avoir besoin de milliers de "grandes piles", et la demande de mémoire devient soudainement ridicule. L'allocation de cadres de pile résout ce problème. Souvent, la sous-tâche "Empile". renvoyer aux tâches parentes pour implémenter la portée lexicale; en tant que sous-tâche fork, une arborescence de "sous-piles" est créée une "pile de cactus".

3) Votre langue a des continuations. Celles-ci nécessitent que les données de l'étendue lexicale visibles par la fonction actuelle soient en quelque sorte préservées pour une réutilisation ultérieure. Ceci peut être implémenté en copiant les cadres de la pile parent, en gravissant la pile de cactus et en procédant.

Le langage de programmation PARLANSE que j'ai implémenté a mis en oeuvre les étapes 1) et 2). Je travaille sur 3).

Answer 2

Stackless Python a toujours une pile Python (bien qu'elle puisse avoir une optimisation des appels en aval et d'autres astuces de fusion de trames d'appel ), mais il est complètement séparé de la pile C de l'interpréteur.

Haskell (tel qu’implémenté couramment) ne possède pas de pile d’appels; l'évaluation est basée sur la réduction du graphique .

Answer 3

Il existe un bel article sur le cadre 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

Dans les environnements sans pile avec lesquels je suis plus ou moins familier (machine de Turing, assemblage et Brainfuck), il est courant d'implémenter votre propre pile. Il n'y a rien de fondamental à avoir une pile intégrée dans le langage.

Dans l’assemblage le plus pratique, il vous suffit de choisir une région de mémoire à votre disposition, de définir le registre de pile pour qu’il pointe vers le bas, puis d’augmenter ou de décrémenter vos implémentations.

EDIT: Je sais que certaines architectures ont des piles dédiées, mais elles ne sont pas nécessaires.

Answer 5

Il existe une description facile à comprendre des suites de cet article: http: // www. defmacro.org/ramblings/fp.html

Les continuations sont quelque chose que vous pouvez transmettre à une fonction dans un langage en pile, mais qui peut également être utilisée par la propre sémantique d'un langage pour le rendre "sans pile". Bien sûr, la pile est toujours là, mais comme l’a décrit Ira Baxter, ce n’est pas un gros segment contigu.

Answer 6

Dites que vous vouliez implémenter le C sans pile. La première chose à réaliser est que cela n’a pas besoin d’une pile:

a == b

Mais, est-ce que c'est ça?

isequal(a, b) { return a == b; }

Non. Parce qu'un compilateur intelligent appellera isequal , il sera transformé en a == b . Alors, pourquoi ne pas simplement tout aligner? Bien sûr, vous allez générer plus de code, mais si vous en vaincrez la pile, cela est facile avec un petit compromis.

Qu'en est-il de la récursivité? Aucun problème. Une fonction queue-récursive comme:

bang(x) { return x == 1 ? 1 : x * bang(x-1); }

Peut toujours être en ligne, car il s’agit en réalité d’une boucle perdue:

bang(x) {
    for(int i = x; i >=1; i--) x *= x-1;
    return x;
}

En théorie, un compilateur très intelligent pourrait vous aider. Mais un moins intelligent pourrait encore l'aplatir comme un goto:

ax = x;
NOTDONE:
if(ax > 1) {
    x = x*(--ax);
    goto NOTDONE;
}

Il existe un cas où vous devez faire un petit échange. Cela ne peut pas être en ligne:

fib(n) { return n <= 2 ? n : fib(n-1) + fib(n-2); }

Stackless C ne peut tout simplement pas faire cela. Abandonnez-vous beaucoup? Pas vraiment. C’est quelque chose de normal C ne peut pas très bien faire non plus. Si vous ne me croyez pas, appelez simplement fib (1000) et voyez ce qu'il advient de votre précieux ordinateur.

Answer 7

Appelez-moi ancien, mais je me souviens bien que les normes FORTRAN et COBOL ne prenaient pas en charge les appels récursifs et ne nécessitaient donc pas de pile. En effet, je me souviens des implémentations pour les machines de la série CDC 6000 où il n’y avait pas de pile, et FORTRAN ferait des choses étranges si vous tentiez d’appeler un sous-programme de manière récursive.

Pour l'enregistrement, au lieu d'une pile d'appels, le jeu d'instructions CDC 6000 a utilisé l'instruction RJ pour appeler un sous-programme. Ceci a sauvegardé la valeur PC actuelle à l'emplacement cible de l'appel, puis est redirigé vers l'emplacement suivant. À la fin, un sous-programme effectuerait un saut indirect vers l'emplacement cible de l'appel. Ce PC sauvegardé rechargé est retourné à l'appelant.

Évidemment, cela ne fonctionne pas avec les appels récursifs. (Et je me souviens que le compilateur CDC FORTRAN IV générerait un code cassé si vous tentiez de faire de la récursivité ...)

Answer 8

N'hésitez pas à me corriger si je me trompe, mais je penserais qu'allouer de la mémoire sur le tas pour chaque cadre d'appel de fonction provoquerait une saturation extrême de la mémoire. Après tout, le système d’exploitation doit gérer cette mémoire. Je penserais que le moyen d'éviter cette ruée en mémoire serait un cache pour les cadres d'appel. Donc, si vous avez quand même besoin d’un cache, nous pourrions aussi bien le rendre contigu en mémoire et l’appeler une pile.