Qu'est-ce que cela signifie vraiment qu'un langage de programmation est sans pile?

Question

Selon cette réponse

https://stackoverflow.com/questions/551950/what-stackless-programming-languages-are-available/671296#671296

tous ces langages de programmation sont stackless

• Stackless Python
• PyPy
• Lisp
• Schéma
• Tcl
• Lua
• Parrot VM

Qu'est-ce que cela signifie vraiment pour eux d'être stackless? Cela signifie-t-il qu'ils n'utilisent pas une pile d'appels? S'ils n'utilisent pas une pile d'appels, qu'utilisent-ils?

Answer 1

Qu'est-ce que cela signifie vraiment pour eux d'être sans pile? Cela signifie-t-il qu'ils n'utilisent pas une pile d'appels?

Oui, c'est à peu près juste.

Si elles n'utilisent pas une pile d'appels, qu'est-ce qu'elles utilisent?

L'implémentation exacte variera, bien sûr, d'une langue à l'autre. Dans Stackless Python, il y a un répartiteur qui démarre l'interpréteur Python en utilisant le cadre le plus en haut et ses résultats. L'interpréteur traite les opcodes au besoin, un à la fois, jusqu'à ce qu'il atteigne un code opération CALL_FUNCTION, le signal que vous êtes sur le point d'entrer dans une fonction. Cela force le répartiteur à créer une nouvelle image avec les informations pertinentes et à retourner au distributeur avec l'indicateur de déroulement. À partir de là, le répartiteur recommence, pointant l'interprète vers le cadre supérieur.

Les langages sans pile évitent les piles d'appels pour un certain nombre de raisons, mais dans de nombreux cas, ils sont utilisés pour que certaines constructions de programmation deviennent beaucoup plus faciles à implémenter. Le canonique est continuations. Les continuations sont des structures de contrôle très puissantes et très simples qui peuvent représenter n'importe laquelle des structures de contrôle habituelles que vous connaissez probablement déjà (while, do, if, switch, et cetera).

Si c'est source de confusion, vous pouvez essayer envelopper votre tête autour de l'article de Wikipedia, et en particulier l'analogie sandwich mièvre continuation:

Dites que vous êtes dans la cuisine devant le réfrigérateur , en pensant à un sandwich. Vous prenez une suite là-bas et collez-le dans votre poche. Ensuite, vous obtenez un peu de dinde et du pain du réfrigérateur et vous faites un sandwich, qui est maintenant assis sur le comptoir. Vous invoquez la continuation dans votre poche, et vous vous retrouvez à nouveau devant le réfrigérateur, en pensant à un sandwich. Mais heureusement, il y a un sandwich sur le comptoir, et tous les matériaux utilisés pour le faire ont disparu. Alors tu le manges.Ils n'utilisent pas de pile d'appels, car ils opèrent en continuation-passing style

Answer 2

Si vous n'êtes pas familier avec l'optimisation des appels de queue, c'est probablement une bonne première étape pour comprendre ce que cela signifie. Pour émuler l'appel/retour traditionnel sur ce modèle, au lieu de pousser une adresse de retour et d'attendre que le reste de la trame reste intacte, l'appelant se referme sur le reste de son code et toutes les variables qui sont encore nécessaires (le reste sont libérés). Il effectue ensuite un appel de queue à l'appelé, en passant cette continuation comme argument. Lorsque l'appelé "renvoie", il le fait en appelant cette continuation, en lui passant la valeur de retour en argument.

En ce qui concerne ce qui précède, c'est simplement une manière compliquée de faire des appels de fonction. Cependant, il généralise très bien à des scénarios plus complexes:

1. exception/finally/blocs etc sont très facilement modélisés - si vous pouvez passer une continuation « de retour » comme argument, vous pouvez passer 2 (ou plus) juste aussi facilement. Les blocs "condition handler" de lisp-y (qui peuvent ou non renvoyer le contrôle à l'appelant) sont aussi faciles - passez une continuation pour le reste de cette fonction, qui pourrait ou non être appelée.
2. Plusieurs valeurs de retour sont également rendues faciles - passez plusieurs arguments sur la continuation.
3. Les retours/copies de retour ne sont plus différents du passage d'argument de fonction. Cela rend souvent plus facile l'élimination des temporaires.
4. L'optimisation de la récurrence de la queue est triviale - l'appelant transmet simplement la suite «retour» qu'il a reçue plutôt que d'en capturer une nouvelle.