La pile d'appel ne dit pas "d'où vous venez", mais "où vous allez ensuite" ?

Question

Dans une question précédente ( Obtenir la hiérarchie des appels d'objets ), j'ai obtenu cette réponse intéressante :

La pile d'appels n'est pas là pour vous dire d'où vous venez. Elle est là pour vous dire où vous allez ensuite.

Pour autant que je sache, lorsqu'il arrive à un appel de fonction, un programme fait généralement ce qui suit :

1. En appel code :

   • stocker l'adresse de retour (sur la pile d'appels)
   • sauvegarder l'état des registres (sur la pile d'appels)
   • écrire les paramètres qui seront transmis à la fonction (sur la pile d'appels ou dans les registres)
   • sauter à la fonction cible

2. En appelé code cible :

   • Récupérer les variables stockées (si nécessaire)

3. Procédure de retour : Annuler ce que nous avons fait lorsque nous avons appelé la fonction, c'est-à-dire dérouler/ouvrir la pile d'appels :

   • supprimer les variables locales de la pile d'appels
   • supprimer les variables de fonction de la pile d'appels
   • restaurer l'état des registres (celui que nous avons stocké auparavant)
   • sauter à l'adresse de retour (celle que nous avons enregistrée précédemment)

Question :

Comment peut-on considérer qu'il s'agit de quelque chose qui "vous dit où vous allez aller ensuite" plutôt que "vous dire d'où vous venez" ?

Y a-t-il quelque chose dans le JIT de C# ou dans l'environnement d'exécution de C# qui fait que cette pile d'appels fonctionne différemment ?

Merci de m'indiquer la documentation relative à cette description de la pile d'appels - il y a beaucoup de documentation sur le fonctionnement d'une pile d'appels traditionnelle.

Answer 1

Vous l'avez expliqué vous-même. L'"adresse de retour", par définition, vous indique votre prochaine destination .

Il n'y a aucune exigence que l'adresse de retour qui est placée sur la pile soit une adresse à l'intérieur de la méthode qui a été utilisée. appelé la méthode dans laquelle vous vous trouvez actuellement. Il s'agit typiquement ce qui facilite grandement le débogage. Mais il n'y a pas de exigence que l'adresse de retour soit une adresse à l'intérieur de l'appelant. L'optimiseur est autorisé à modifier l'adresse de retour - ce qu'il fait parfois - si cela permet au programme d'être plus rapide (ou plus petit, ou tout autre objectif d'optimisation) sans en modifier la signification.

Le but de la pile est de s'assurer que lorsque ce sous-programme se termine, il est suite -- ce qui se passe ensuite -- est correcte. Le but de la pile n'est pas de vous dire d'où vous venez. Le fait qu'elle le fasse habituellement est un heureux accident.

De plus, la pile n'est qu'un détail de mise en œuvre des concepts de suite y l'activation . Il n'est pas nécessaire que les deux concepts soient mis en œuvre par la même pile ; il peut y avoir deux piles, l'une pour les activations (variables locales) et l'autre pour la continuation (adresses de retour). De telles architectures sont évidemment beaucoup plus résistantes aux attaques de destruction de pile par des logiciels malveillants, car l'adresse de retour ne se trouve nulle part à proximité des données.

Plus intéressant encore, il n'est pas nécessaire qu'il y ait une pile ! Nous utilisons les piles d'appels pour implémenter la continuation parce qu'elles sont pratiques pour le type de programmation que nous faisons habituellement : les appels synchrones basés sur des sous-routines. Nous pourrions choisir d'implémenter le langage C# en tant que langage "Continuation Passing Style", où la continuation est en fait réifié en tant que sur le tas et non comme un paquet d'octets poussés sur une pile système d'un million d'octets . Cet objet est ensuite transmis d'une méthode à l'autre, aucune d'entre elles n'utilisant de pile. (Les activations sont ensuite réifiées en décomposant chaque méthode en plusieurs délégués possibles, chacun d'entre eux étant associé à un objet d'activation).

Dans le style continuation passing, il n'y a tout simplement pas de pile et il n'y a aucun moyen de savoir d'où l'on vient ; l'objet continuation n'a pas cette information. Il sait seulement où vous allez ensuite.

Cela peut sembler être un charabia théorique de haute volée, mais nous transformons essentiellement C# et VB en langages de type "continuation passing". dans la prochaine version ; la fonctionnalité "async" à venir n'est qu'une continuation du style passing sous un fin déguisement. Dans la prochaine version, si vous utilisez la fonctionnalité asynchrone, vous abandonnerez essentiellement la programmation basée sur la pile ; il n'y aura aucun moyen de regarder la pile d'appels et de savoir comment vous en êtes arrivé là, parce que la pile sera souvent vide.

Les continuations réifiées en tant que quelque chose d'autre qu'une pile d'appels est une idée difficile à assimiler pour beaucoup de gens ; cela a certainement été le cas pour moi. Mais une fois qu'on l'a comprise, elle s'impose d'elle-même et prend tout son sens. Pour une introduction en douceur, voici un certain nombre d'articles que j'ai écrits sur le sujet :

Une introduction à CPS, avec des exemples en JScript :

http://blogs.msdn.com/b/ericlippert/archive/2005/08/08/recursion-part-four-continuation-passing-style.aspx

http://blogs.msdn.com/b/ericlippert/archive/2005/08/11/recursion-part-five-more-on-cps.aspx

http://blogs.msdn.com/b/ericlippert/archive/2005/08/15/recursion-part-six-making-cps-work.aspx

Voici une douzaine d'articles qui commencent par une plongée plus profonde dans le CPS, puis expliquent comment tout cela fonctionne avec la fonction "asynchrone" à venir. Commencez par le bas :

http://blogs.msdn.com/b/ericlippert/archive/tags/async/

Les langages qui supportent le style de passage de continuation ont souvent une primitive magique de flux de contrôle appelée "call with current continuation", ou "call/cc" en abrégé. Dans cette question de stackoverflow, j'explique la différence triviale entre "await" et "call/cc" :

Comment la nouvelle fonctionnalité asynchrone de c# 5.0 pourrait-elle être mise en œuvre avec call/cc ?

Pour mettre la main sur la "documentation" officielle (une série de livres blancs) et une version préliminaire de la nouvelle fonction "async await" de C# et VB, ainsi qu'un forum pour les questions-réponses, rendez-vous à l'adresse suivante :

http://msdn.com/vstudio/async

Answer 2

Considérons le code suivant :

void Main()
{
    // do something
    A();
    // do something else
}

void A()
{
    // do some processing
    B();
}

void B()
{
}

Ici, la dernière chose que la fonction A est en train de faire, c'est d'appeler B . A revient immédiatement après. Un optimiseur astucieux pourrait optimiser la fonction appel a B et le remplacer par un simple sauter a B de l'adresse de départ. (Je ne suis pas sûr que les compilateurs C# actuels effectuent de telles optimisations, mais presque tous les compilateurs C++ le font). Pourquoi cela fonctionnerait-il ? Parce qu'il existe une adresse de l'élément A dans la pile, de sorte que lorsque l'appelant de B finis, il reviendrait non pas à A mais directement à A de l'appelant.

Vous pouvez donc constater que la pile ne contient pas nécessairement des informations sur l'origine de l'exécution, mais plutôt sur l'endroit où elle doit se rendre.

Sans optimisation, à l'intérieur B la pile d'appels (j'omets les variables locales et autres pour plus de clarté) :

----------------------------------------
|address of the code calling A         |
----------------------------------------
|address of the return instruction in A|
----------------------------------------

Ainsi, le retour de B revient à A et quitte immédiatement `A.

Avec l'optimisation, la pile d'appels n'est plus que

----------------------------------------
|address of the code calling A         |
----------------------------------------

Donc B renvoie directement à Main .

Dans sa réponse, Eric mentionne un autre cas (plus compliqué) où les informations de la pile ne contiennent pas le véritable appelant.

Answer 3

Ce que dit Eric dans son post, c'est que le pointeur d'exécution n'a pas besoin de savoir d'où il vient, mais seulement où il doit aller lorsque la méthode en cours se termine. Ces deux choses semblent superficiellement être la même chose, mais dans le cas (par exemple) de la récursion de la queue, l'endroit d'où nous venons et l'endroit où nous allons ensuite peuvent diverger.

Answer 4

Cela va plus loin que vous ne le pensez.

En C, il est tout à fait possible de faire en sorte qu'un programme réécrive la pile d'appels. En effet, cette technique est la base même d'un style d'exploit connu sous le nom de la programmation orientée vers le retour .

J'ai également écrit du code dans un langage qui vous donnait un contrôle direct sur la pile d'appels. Vous pouviez retirer la fonction qui appelait la vôtre et en mettre une autre à la place. Vous pouviez dupliquer l'élément au sommet de la pile d'appels, de sorte que le reste du code de la fonction appelante soit exécuté deux fois, et un tas d'autres choses intéressantes. En fait, la manipulation directe de la pile d'appels était la principale structure de contrôle fournie par ce langage. (Défi : quelqu'un peut-il identifier le langage à partir de cette description ?)

Il a clairement montré que la pile d'appels indique où l'on va, et non où l'on est allé.

Answer 5

Je pense que il essaie de dire qu'elle indique à la méthode Called où aller ensuite.

• La méthode A appelle la méthode B.
• La méthode B est achevée, quelle est la prochaine étape ?

Il fait remonter l'adresse de la méthode de l'appelé au sommet de la pile et s'y rend.

La méthode B sait donc où aller une fois qu'elle est terminée. La méthode B ne se soucie pas vraiment de savoir d'où elle vient.