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

Question

Selon cette réponse

https://stackoverflow.com/questions/551950/what -stackless-programmation-langues-sont-disponibles / 671296 # 671296

tous ces langages de programmation sont stackless

• Stackless Python
• PyPy
• Lisp
• Système
• Tcl
• Lua
• Parrot VM

Qu'est-ce que cela signifie vraiment pour eux d'être stackless? Est-ce que cela veut dire qu'ils n'utilisent pas une pile d'appel? S'ils ne pas utiliser une pile d'appel, qu'est-ce qu'ils utilisent?

Answer 1

  

Qu'est-ce que cela signifie vraiment pour eux d'être stackless? Est-ce que cela veut dire qu'ils n'utilisent pas une pile d'appel?

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

  

S'ils ne pas utiliser une pile d'appel, qu'est-ce qu'ils utilisent?

La mise en œuvre exacte, bien sûr, varient d'une langue à. Dans Stackless Python, il y a un répartiteur qui démarre l'interpréteur Python en utilisant le cadre et ses supérieure résultats. L'interprète traite opcodes au besoin un à la fois jusqu'à ce qu'il atteigne un opcode CALL_FUNCTION, le signal que vous êtes sur le point d'entrer en fonction. Cela provoque le répartiteur de construire un nouveau cadre avec les informations pertinentes et retourner au répartiteur avec le drapeau dérouleur. De là, le répartiteur commence à nouveau, en montrant l'interprète à la trame supérieure.

langues Stackless évitent les piles d'appel pour un certain nombre de raisons, mais dans de nombreux cas, il est utilisé de telle sorte que certaines constructions de programmation deviennent beaucoup plus faciles à mettre en œuvre. L'canonique est continuations . Continuations sont très puissants, les structures de contrôle très simples qui peuvent représenter l'une des structures de contrôle habituelles, vous êtes probablement déjà au courant (while, do, if, switch, etc. et).

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

  

Dites que vous êtes dans la cuisine devant le réfrigérateur, en pensant à un sandwich. Vous prenez une continuation là et le coller dans votre poche. Ensuite, vous obtenez la dinde et du pain hors du réfrigérateur et de vous faire un sandwich, qui est maintenant assis sur le comptoir. Vous invoquez la continuation dans votre poche, et vous vous retrouvez debout devant le réfrigérateur à nouveau, en pensant à un sandwich. Mais heureusement, il y a un sandwich sur le comptoir, et tous les matériaux utilisés pour le faire sont partis. Donc, vous mangez.

Answer 2

Ils n'utilisent pas une pile d'appel, car ils fonctionnent dans de style passage de continuation . Si vous n'êtes pas familier avec l'optimisation des appels récursifs, qui est probablement une bonne première étape pour comprendre ce que cela signifie.

Pour imiter l'appel traditionnel / retour sur ce modèle, au lieu de pousser une adresse de retour et attendant le reste du cadre pour rester intact l'appelant se ferme sur le reste de son code et toutes les variables qui sont encore nécessaires (les autres sont libéré). Il effectue ensuite un appel de queue à l'appelé, en passant cette suite comme argument. Lorsque l'appelé « retourne », il le fait en appelant cette suite, en passant la valeur de retour comme argument à lui.

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

1. exception / finally / etc blocs sont très facilement modélisés - si vous pouvez passer une continuation « de retour » comme argument, vous pouvez passer 2 (ou plus) tout aussi facilement. Lisp-y blocs « gestionnaire d'état » (qui peut ou ne peut pas renvoyer le contrôle à l'appelant) sont également faciles -. passer une suite pour le reste de cette fonction, qui pourrait ou ne pourrait pas être appelé
2. Valeurs de retour multiples sont également rendues faciles -. Passer plusieurs arguments à la poursuite
3. de retour temporaires / copie ne sont plus différent que le passage des arguments de la fonction. Cela rend souvent plus facile d'éliminer les temporaires.
4. l'optimisation de récursivité La queue est trivial - l'appelant passe simplement sur la suite « retour » il a reçu plutôt que de capturer un nouveau
.