Pourquoi les programmes utilisent-ils des piles d'appels si les appels de fonction imbriqués peuvent être en ligne?

Pourquoi ne pas demander au compilateur de prendre un programme comme celui-ci:

function a(b) { return b^2 };
function c(b) { return a(b) + 5 };

et le convertir en un programme comme celui-ci:

function c(b) { return b^2 + 5 };

éliminant ainsi le besoin de l'ordinateur de se souvenir de l'adresse de retour de c (b)?

Je suppose que l’augmentation de l’espace disque dur et de la mémoire RAM nécessaires pour stocker le programme et prendre en charge sa compilation (respectivement) est la raison pour laquelle nous utilisons des piles d’appels. Est-ce exact?

Cela s'appelle "inline" et de nombreux compilateurs le font comme stratégie d'optimisation dans les cas où cela a du sens.

Dans votre exemple particulier, cette optimisation permettrait d'économiser de l'espace et du temps d'exécution. Mais si la fonction était appelée à plusieurs endroits du programme (ce qui n'est pas rare!), La taille du code augmenterait, ce qui rendait la stratégie plus incertaine. (Et bien sûr, si une fonction s’appelait directement ou indirectement, il serait impossible de s’inscrire en ligne, car le code deviendrait alors infini en taille.)

Et évidemment, cela n'est possible que pour des fonctions "privées". Les fonctions accessibles aux appelants externes ne peuvent pas être optimisées, du moins pas dans les langues avec liaison dynamique.

Votre question comporte deux parties: pourquoi avoir plusieurs fonctions (au lieu de remplacer les appels de fonction par leur définition) et pourquoi implémenter ces fonctions avec des piles d’appel au lieu d’allouer statiquement leurs données ailleurs?

La première raison est la récursivité. Pas seulement le type "oh, faisons un nouvel appel de fonction pour chaque élément de cette liste", mais aussi le type modeste où vous avez peut-être deux appels d'une fonction active en même temps, avec beaucoup d'autres fonctions entre eux. Vous devez mettre des variables locales sur une pile pour supporter cela, et vous ne pouvez pas intégrer de fonctions récursives en ligne en général.

Ensuite, il y a un problème pour les bibliothèques: vous ne savez pas quelles fonctions seront appelées d'où et à quelle fréquence, de sorte qu'une "bibliothèque" ne peut jamais être réellement compilée; elle est uniquement envoyée à tous les clients dans un format de haut niveau pratique inline dans l'application. Mis à part d'autres problèmes, vous perdez complètement la liaison dynamique avec tous ses avantages.

En outre, il existe de nombreuses raisons de ne pas utiliser les fonctions en ligne, même si vous pouviez:

1. Ce n'est pas nécessairement plus rapide. La configuration et la suppression du cadre de pile représentent peut-être une douzaine d'instructions à cycle unique. Pour de nombreuses fonctions de grande taille ou en boucle, elles ne représentent même pas 0,1% de leur temps d'exécution.
2. Cela peut être plus lent. La duplication de code a des coûts, par exemple, cela mettra plus de pression dans le cache d'instructions.
3. Certaines fonctions sont très volumineuses et appelées de nombreux endroits; leur alignement partout augmente les performances binaires bien au delà de ce qui est raisonnable.
4. Les compilateurs ont souvent de la difficulté avec de très grandes fonctions. Toutes choses étant égales par ailleurs, une fonction de taille 2 * N prend plus de 2 * T temps, alors qu'une fonction de taille N prend T temps.

Les piles nous permettent de contourner avec élégance les limites imposées par le nombre fini de registres.

Imaginez avoir exactement 26 globaux "registres az" (ou même n'avoir que les registres de la taille de la puce 8080 de la taille d'un octet) Et chaque fonction que vous écrivez dans cette application partage cette liste à plat.

Un début naïf serait d’attribuer les premiers registres à la première fonction, et sachant que cela ne prenait que 3, commencez par "d" pour la deuxième fonction ... Vous vous épuisez rapidement.

Par contre, si vous avez une bande métaphorique, comme la machine de lecture, vous pouvez faire en sorte que chaque fonction lance un "appel d’une autre fonction" en enregistrant toutes les variables qu’elle utilise et en transmettant la bande (), puis la fonction appelée peut s’embrouiller autant. s'inscrit comme il veut. Lorsque l'appelé est terminé, il renvoie le contrôle à la fonction parent, qui sait où capturer la sortie de l'appelé si nécessaire, puis lit la bande à l'envers pour restaurer son état.

Votre cadre d’appel de base n’est que cela. Il est créé et supprimé par des séquences de code machine normalisées que le compilateur insère autour des transitions d’une fonction à l’autre. (Cela fait longtemps que je ne devais plus me souvenir de mes cadres de pile C, mais vous pouvez lire les différentes manières dont les tâches de qui laisse quoi à X86_calling_conventions .)

(La récursivité est géniale, mais si vous aviez déjà à jongler avec des registres sans pile, vous apprécieriez vraiment les piles.)

Je suppose que l’augmentation de l’espace disque dur et de la mémoire RAM nécessaires pour stocker le programme et prendre en charge sa compilation (respectivement) est la raison pour laquelle nous utilisons des piles d’appels. Est-ce exact?

Bien que nous puissions davantage nous aligner ces temps-ci, ("plus de vitesse" est toujours bon; "moins de ko d'assemblage" signifie très peu dans un monde de flux vidéo). La principale limitation réside dans la capacité du compilateur à aplatir certains types de modèles de code.

Par exemple, les objets polymorphes - si vous ne connaissez pas le seul et unique type d'objet qui vous sera remis, vous ne pouvez pas l'aplatir; vous devez regarder la table des fonctionnalités de l'objet et appeler via ce pointeur ... trivial à faire au moment de l'exécution, impossible à aligner au moment de la compilation.

Une chaîne d’outils moderne peut heureusement intégrer une fonction définie par un polymorphisme quand elle a suffisamment écrasé le ou les appelants pour savoir exactement quelle est la saveur de obj:

class Base {
    public: void act() = 0;
};
class Child1: public Base {
    public: void act() {};
};
void ActOn(Base* something) {
    something->act();
}
void InlineMe() {
    Child1 thingamabob;
    ActOn(&thingamabob);
}

Dans ce qui précède, le compilateur peut choisir de garder le droit d'inline alignée, d'InlineMe à tout ce qui se trouve à l'intérieur d'act (), sans avoir besoin de toucher les vtables au moment de l'exécution.

Mais toute incertitude quant à la nature de l'objet le laissera comme un appel à une fonction discrète, même si d'autres invocations de la même fonction sont en ligne .

Cas que cette approche ne peut pas gérer:

function fib(a) { if(a>2) return fib(a-1)+fib(a-2); else return 1; }

function many(a) { for(i = 1 to a) { b(i); };}

Il existe des langues et des plates-formes avec peu ou pas de piles d'appels. Les microprocesseurs PIC ont une pile matérielle limitée à 2 à 32 entrées . Cela crée des contraintes de conception.

COBOL interdit la récursivité: https://stackoverflow.com/questions/27806812/in-cobol-is-it-possible-trecursively- call-a- alinéa

Imposer une interdiction de récursion signifie que vous pouvez représenter le graphe d'appel entier du programme de manière statique en tant que DAG. Votre compilateur pourrait alors émettre une copie d'une fonction pour chaque lieu à partir duquel elle est appelée avec un saut fixe au lieu d'un retour. Aucune pile requise, juste plus d'espace de programme, potentiellement beaucoup pour les systèmes complexes. Mais pour les petits systèmes embarqués, cela signifie que vous pouvez vous assurer de ne pas avoir de débordement de pile au moment de l'exécution, ce qui serait une mauvaise nouvelle pour la commande de papillon de votre réacteur nucléaire / turbine à réaction / voiture, etc.

Vous voulez une fonction en ligne , et la plupart des compilateurs (en optimisation ) le font.

Notez que l’inline exige que la fonction appelée soit connue (et n’est efficace que si la fonction appelée n’est pas trop grande), puisqu’elle remplace l’appel par la réécriture de la fonction appelée. Ainsi, vous ne pouvez généralement pas insérer une fonction inconnue en ligne (par exemple, un pointeur de fonction contenant des fonctions de bibliothèques partagées liées dynamiquement , ce qui est peut-être visible en tant que méthode virtuelle dans certaines tables , mais certains compilateurs peuvent parfois optimiser via des techniques de dévirtualisation ). Bien sûr, il n’est pas toujours possible d’inclure des fonctions récursives (certains compilateurs astucieux peuvent utiliser une évaluation partielle et, dans certains cas, être capables d’inclure des fonctions récursives).

Notez également que l’insertion de ligne, même si cela est facilement possible, n’est pas toujours efficace: vous (en fait, votre compilateur) pourriez augmenter tellement la taille du code que les caches de processeur (ou prédicteur de branche ) fonctionneraient moins efficacement, ce qui rendrait votre programme exécuté Ralentissez.

^{Je me concentre un peu sur le style de programmation fonctionnelle , puisque vous avez étiqueté votre question en tant que telle.}

Notez qu'il n'est pas nécessaire d'avoir une pile d'appels (du moins dans le sens machine de l'expression "pile d'appels"). Vous ne pouvez utiliser que le tas.

Alors jetez un coup d'œil aux continuations et lisez-en davantage sur le style de passage de continuation (CPS) et sa transformation (intuitivement, vous pouvez utiliser les fermetures de continuation comme des "cadres d'appel" réifiés alloués dans le tas, et ils ressemblent en quelque sorte à une pile d'appels; alors vous avez besoin d'un ramasse-miettes efficace ).

Andrew Appel a écrit un livre Compiler avec des suites et une collecte de vieux papiers peut être plus rapide que l'allocation de pile . Voir aussi l'article de A.Kennedy (ICFP2007) Compiler avec des suites , suite

Je recommande également de lire le livre Lisp In Small Pieces de Queinnec , qui contient plusieurs chapitres sur la suite et la compilation.

Notez également que certaines langues (par exemple, Brainfuck ) ou des machines abstraites (par exemple, OISC , RAM ) ne disposent d’aucune possibilité d’appel, mais sont toujours complètes en turing. Vous n’avez donc (théoriquement) pas besoin d’un mécanisme d’appel de fonction, même si c'est extrêmement pratique. Par ailleurs, certaines anciennes architectures de jeux d’instructions (par exemple, IBM / 370 ) n’ont même pas de pile d’appels matériels, ni d’instructions de machine appelantes (l’IBM / 370 ne dispose que d’une instruction machine Branch and Link )

Enfin, si votre programme complet (y compris toutes les bibliothèques nécessaires) ne comporte aucune récursivité, vous pouvez stocker l'adresse de retour (et les variables "locales", qui deviennent réellement statiques) de chaque fonction dans des emplacements statiques. Les anciens compilateurs Fortran77 l’ont fait au début des années 1980 (les programmes compilés n’utilisaient donc aucune pile d’appels à ce moment-là).

L'inclusion (le remplacement d'appels de fonctions par des fonctionnalités équivalentes) fonctionne bien comme stratégie d'optimisation pour de petites fonctions simples. Les frais généraux liés à un appel de fonction peuvent être échangés contre une petite pénalité liée à la taille du programme (ou, dans certains cas, aucune pénalité).

Cependant, de grandes fonctions appelant d'autres fonctions pourraient entraîner une énorme explosion de la taille du programme si tout était en ligne.

Le but des fonctions appelables est de faciliter une réutilisation efficace, non seulement par le programmeur, mais également par la machine elle-même, et cela inclut des propriétés comme une mémoire raisonnable ou une empreinte sur disque.

Pour ce que ça vaut: vous pouvez avoir des fonctions appelables sans pile d'appels. Par exemple: IBM System / 360. Lors de la programmation dans des langages tels que FORTRAN sur ce matériel, le compteur de programme (adresse de retour) est enregistré dans une petite partie de la mémoire réservée juste avant le point d’entrée de la fonction. Il autorise les fonctions réutilisables, mais pas les codes récursifs ou multithreads (une tentative d'appel récursif ou rentrant entraînerait le remplacement d'une adresse de retour précédemment enregistrée).

Comme expliqué par d'autres réponses, les piles sont de bonnes choses. Ils facilitent la récursion et les appels multithreads. Tout algorithme codé pour utiliser la récursivité peut être codé sans recourir à la récursivité, mais le résultat peut être plus complexe, plus difficile à maintenir et moins efficace. Je ne suis pas sûr qu'une architecture sans pile puisse supporter le multi-threading du tout.