Les piles sont-elles le seul moyen raisonnable de structurer les programmes?

74

La plupart des architectures que j'ai vues s'appuient sur une pile d'appels pour enregistrer / restaurer le contexte avant les appels de fonction. C'est un paradigme si commun que les opérations push et pop sont intégrées à la plupart des processeurs. Existe-t-il des systèmes fonctionnant sans pile? Si oui, comment fonctionnent-ils et à quoi servent-ils?

ConditionRacer
la source
5
Étant donné le comportement attendu des fonctions dans les langages de type C (vous pouvez imbriquer des appels aussi profondément que vous le souhaitez et revenir en arrière dans l'ordre inverse), je ne vois pas comment faire pour implémenter des appels de fonction sans être incroyablement complexe. inefficace. Vous pouvez par exemple forcer le programmeur à utiliser le style de passage continu ou une autre forme de programmation bizarre, mais personne ne semble réellement travailler avec CPS pour une raison ou une autre.
Kevin
5
GLSL fonctionne sans pile (comme les autres langues dans ce support spécifique). Il interdit simplement les appels récursifs.
Leushenko
3
Vous pouvez également consulter les fenêtres de registre , utilisées par certaines architectures RISC.
Mark Booth
2
@ Kevin: "Les premiers compilateurs FORTRAN ne prenaient en charge aucune récursivité. Les architectures informatiques anciennes ne prenaient en charge aucun concept de pile. Lorsqu'ils prenaient directement en charge les appels de sous-routines, l'emplacement de retour était souvent stocké dans un emplacement fixe adjacent au code de la sous-routine. ne permet pas de ré-appeler un sous-programme avant son retour. Bien que cela ne soit pas spécifié dans Fortran 77, de nombreux compilateurs F77 acceptaient la récursivité en tant qu’option, alors que cela devenait la norme dans Fortran 90. " fr.wikipedia.org/wiki/Fortran#FORTRAN_II
Mooing Duck
3
Le microcontrôleur P8X32A ("Propeller") n'a pas de concept de pile dans son langage d'assemblage standard (PASM). Les instructions responsables du saut modifient également automatiquement l'instruction de retour dans la RAM pour déterminer où retourner, ce qui peut être choisi arbitrairement. Il est intéressant de noter que le langage "Spin" (langage interprété de haut niveau qui fonctionne sur la même puce) possède une sémantique de pile traditionnelle.
Wossname

Réponses:

50

Une alternative (un peu) populaire à une pile d'appels sont les continuations .

Parrot VM est basé sur la continuation, par exemple. Il est complètement sans pile: les données sont conservées dans des registres (comme Dalvik ou LuaVM, Parrot est basé sur des registres) et le contrôle-flux est représenté par des continuations (contrairement à Dalvik ou à LuaVM, qui disposent d'une pile d'appels).

Une autre structure de données populaire, utilisée généralement par les ordinateurs virtuels Smalltalk et Lisp est la pile de spaghettis, qui ressemble à un réseau de piles.

Comme @rwong l'a fait remarquer , le style de poursuite de passage est une alternative à une pile d'appels. Les programmes écrits dans (ou transformés en) style de passage de continuation ne reviennent jamais, il n'y a donc pas besoin de pile.

Répondre à votre question sous un angle différent: il est possible d'avoir une pile d'appels sans avoir de pile distincte, en allouant les trames de pile sur le tas. Certaines implémentations Lisp et Scheme le font.

Jörg W Mittag
la source
4
Cela dépend de votre définition d'une pile. Je ne suis pas sûr que le fait d'avoir une liste chaînée (ou un tableau de pointeurs vers ou ...) de trames de pile est tellement "pas une pile" que "une représentation différente d'une pile"; et les programmes en langage CPS (dans la pratique) ont tendance à construire des listes de suites bien reliées qui sont très similaires aux piles (si vous ne l’avez pas déjà fait, vous pouvez consulter GHC, qui empile ce qu’il appelle des "suites" sur une pile linéaire. pour l'efficacité).
Jonathan Cast le
6
"Les programmes écrits dans (ou transformés en) style de passage de continuation ne reviennent jamais " ... semble inquiétant.
Rob Penridge
5
@RobPenridge: c'est un peu cryptique, je suis d'accord. CPS signifie qu'au lieu de retourner, les fonctions prennent comme argument supplémentaire une autre fonction à appeler lorsque leur travail est terminé. Ainsi, lorsque vous appelez une fonction et que vous avez un autre travail à effectuer après avoir appelé la fonction, au lieu d'attendre le retour de la fonction pour continuer votre travail, vous enroulez le travail restant ("la suite" ) dans une fonction et transmettez-la en tant qu'argument supplémentaire. La fonction que vous avez ensuite appelée appelle cette fonction au lieu de revenir, et ainsi de suite. Aucune fonction ne revient jamais, c'est juste
Jörg W Mittag
3
… Appelle la fonction suivante. Par conséquent, vous n'avez pas besoin d'une pile d'appels, car vous n'avez jamais besoin de revenir pour restaurer l'état de liaison d'une fonction précédemment appelée. Au lieu de transporter l’ état passé pour pouvoir y revenir, vous transportez l’ état futur , si vous voulez.
Jörg W Mittag Le
1
@jcast: La fonctionnalité qui définit une pile est IMO: vous ne pouvez accéder qu'à l'élément le plus haut. Une liste de continuations, OTOH, vous donnerait accès à toutes les continuations et pas seulement à la pile la plus haute. Si vous avez des exceptions pouvant être reprises comme dans Smalltalk, par exemple, vous devez pouvoir traverser la pile sans la décomposer. Et avoir des continuations dans le langage tout en voulant conserver l’idée familière d’une pile d’appel conduit à des piles de spaghettis, qui sont fondamentalement un arbre de piles où les continuations «jettent» la pile.
Jörg W Mittag
36

Autrefois, les processeurs n'avaient pas d'instructions de pile et les langages de programmation ne prenaient pas en charge la récursivité. Au fil du temps, de plus en plus de langues choisissent de prendre en charge la récursivité et la suite matérielle intègre des fonctionnalités d’allocation de trame. Ce support a beaucoup varié au fil des ans avec différents processeurs. Certains processeurs ont adopté des registres de pointeur de pile et / ou de pile; certaines ont adopté des instructions permettant d’allouer des trames de pile en une seule instruction.

À mesure que les processeurs évoluent avec des caches à un niveau, puis à plusieurs niveaux, l'un des avantages essentiels de la pile est son emplacement en cache. Le haut de la pile est presque toujours dans le cache. Chaque fois que vous pouvez faire quelque chose qui a un taux de réussite élevé dans le cache, vous êtes sur la bonne voie avec les processeurs modernes. Le cache appliqué à la pile signifie que les variables locales, les paramètres, etc. sont presque toujours dans le cache et bénéficient du plus haut niveau de performance.

En bref, l'utilisation de la pile a évolué à la fois en matériel et en logiciel. Il existe d'autres modèles (par exemple, l'informatique par flux de données a été essayée pendant une longue période), cependant, la localisation de la pile permet un fonctionnement optimal. En outre, le code de procédure correspond exactement à ce que veulent les processeurs, en termes de performances: une instruction lui dit quoi faire après un autre. Lorsque les instructions ne sont pas linéaires, le processeur ralentit considérablement, du moins pour le moment, car nous n'avons pas trouvé comment rendre l'accès aléatoire aussi rapide que l'accès séquentiel. (Btw, il y a des problèmes similaires à chaque niveau de mémoire: cache, mémoire principale, disque ...)

Entre la performance démontrée des instructions d'accès séquentiel et le comportement de mise en cache avantageux de la pile d'appels, nous avons, du moins à l'heure actuelle, un modèle de performance gagnant.

(Nous pourrions aussi inclure la mutabilité des structures de données dans les travaux ...)

Cela ne signifie pas que d'autres modèles de programmation ne peuvent pas fonctionner, en particulier lorsqu'ils peuvent être traduits en instructions séquentielles et en modèle de pile d'appels du matériel actuel. Mais il existe un avantage distinct pour les modèles prenant en charge le matériel. Cependant, les choses ne restent pas toujours les mêmes, nous pourrions donc voir des changements à l'avenir, car différentes technologies de mémoire et de transistors permettent plus de parallélisme. C'est toujours une plaisanterie entre les langages de programmation et les capacités matérielles, alors on verra!

Erik Eidt
la source
9
En fait, les GPU n'ont toujours pas de pile. Il vous est interdit de revenir en arrière dans GLSL / SPIR-V / OpenCL (vous n'êtes pas sûr de HLSL, mais probablement, je ne vois aucune raison pour que ce soit différent). La manière dont ils gèrent réellement les "piles" d'appels de fonction consiste à utiliser un nombre absurdement grand de registres.
LinearZoetrope
@ Jsor: C'est dans une large mesure le détail de l'implémentation, comme le montre l'architecture SPARC. Comme vos GPU, SPARC possède un ensemble de registres énorme, mais il est unique en ce sens qu’il dispose d’une fenêtre coulissante qui, lorsqu’il est enveloppant, renverse les très anciens registres sur une pile en RAM. C'est donc vraiment un hybride entre les deux modèles. Et SPARC n’a pas précisé le nombre exact de registres physiques, la taille de la fenêtre de registres, de sorte que différentes implémentations pouvaient exister n'importe où sur cette échelle de "quantité énorme de registres" jusqu'à "juste assez pour une fenêtre, à chaque appel de fonction déversement directement à empiler "
MSalters
Un inconvénient du modèle de pile d’appels est que le tableau et / ou le débordement d’adresses doivent être surveillés très attentivement, car les programmes auto-modifiables en tant qu’exploit sont possibles si des bits arbitraires du tas sont exécutables.
BenPen
14

TL; DR

  • Pile d’appel en tant que mécanisme d’appel de fonction:
    1. Est généralement simulé par le matériel mais n'est pas fondamental pour la construction du matériel
    2. Est fondamental pour la programmation impérative
    3. N'est-ce pas fondamental pour la programmation fonctionnelle
  • La pile en tant qu'abstraction du "dernier entré, premier sorti" (LIFO) est fondamentale pour l'informatique, les algorithmes et même certains domaines non techniques.
  • Quelques exemples d'organisation de programme qui n'utilisent pas de piles d'appels:
    • Style de passage continu (CPS)
    • Machine d'état - une boucle géante, avec tout en ligne. (Conçu pour s'inspirer de l'architecture du microprogramme Saab Gripen et attribué à une communication de Henry Spencer reproduite par John Carmack.) (Note 1)
    • Architecture de flux de données - réseau d’acteurs connectés par des files d’attente (FIFO). Les files d'attente sont parfois appelées canaux.

Le reste de cette réponse est une collection aléatoire de pensées et d'anecdotes, et donc quelque peu désorganisée.


La pile que vous avez décrite (en tant que mécanisme d’appel de fonction) est spécifique à la programmation impérative.

En dessous de la programmation impérative, vous trouverez le code machine. Le code machine peut émuler la pile d'appels en exécutant une petite séquence d'instructions.

Sous le code machine, vous trouverez le matériel responsable de l'exécution du logiciel. Bien que le microprocesseur moderne soit trop complexe pour être décrit ici, on peut imaginer qu’il existe une conception très simple, lente mais capable d’exécuter le même code machine. Une conception aussi simple utilisera les éléments de base de la logique numérique:

  1. Logique combinatoire, c'est-à-dire une connexion de portes logiques (et, ou non, ...) Notez que la "logique combinatoire" exclut les retours.
  2. Mémoire, c.-à-d. Bascules, verrous, registres, SRAM, DRAM, etc.
  3. Une machine à états composée d'une logique combinatoire et d'une mémoire, suffisante pour implémenter un "contrôleur" gérant le reste du matériel.

Les discussions suivantes ont fourni de nombreux exemples de solutions alternatives pour structurer les programmes impératifs.

La structure de tel programme ressemblera à ceci:

void main(void)
{
    do
    {
        // validate inputs for task 1
        // execute task 1, inlined, 
        // must complete in a deterministically short amount of time
        // and limited to a statically allocated amount of memory
        // ...
        // validate inputs for task 2
        // execute task 2, inlined
        // ...
        // validate inputs for task N
        // execute task N, inlined
    }
    while (true);
    // if this line is reached, tell the programmers to prepare
    // themselves to appear before an accident investigation board.
    return 0; 
}

Ce style conviendrait aux microcontrôleurs, c'est-à-dire à ceux qui voient le logiciel comme un complément aux fonctions du matériel.


rwong
la source
@Peteris: Les piles sont des structures de données LIFO.
Christopher Creutzig
1
Intéressant. J'aurais pensé l'inverse. Par exemple, FORTRAN est un langage de programmation impératif et les premières versions n'utilisaient pas de pile d'appels. Cependant, la récursivité est fondamentale pour la programmation fonctionnelle, et je ne pense pas qu'il soit possible de l'implémenter dans le cas général sans utiliser une pile.
TED
@TED ​​- dans une implémentation en langage fonctionnel, il y a une structure de données pile (ou généralement une arborescence) représentant des calculs en attente, mais vous ne l'exécutez pas nécessairement avec des instructions utilisant les modes d'adressage orientés pile de la machine ou même les instructions d'appel / retour (de manière imbriquée / récursive - peut-être en tant que partie d'une boucle d'une machine à états).
davidbak
@davidbak - IIRC, un algorithme récursif doit être assez récursif pour pouvoir se débarrasser de la pile. Il y a probablement d'autres cas où vous pourriez l'optimiser, mais dans le cas général , vous devez avoir une pile . En fait, on m'a dit qu'il existait une preuve mathématique de ce fait flottant quelque part. Cette réponse affirme que c'est le théorème de Church-Turing (je pense que les machines de Turing utilisent une pile?)
TED
1
@TED ​​- Je suis d'accord avec toi. Je pense que la mauvaise communication ici est que j'ai lu le post du PO pour parler de l' architecture du système, ce qui signifiait pour moi l'architecture de la machine . Je pense que d'autres qui ont répondu ici ont la même compréhension. Ainsi, ceux d'entre nous qui ont compris que c'était le contexte ont répondu en disant qu'ils n'avaient pas besoin d'une pile au niveau du mode instruction / adressage de la machine. Mais je peux voir que la question peut aussi être interprétée comme signifiant simplement qu'un système de langage a généralement besoin d'une pile d'appels. Cette réponse est également non, mais pour des raisons différentes.
davidbak
11

Non pas forcément.

Lire Le vieux papier de collecte de déchets de Appel peut être plus rapide que l’allocation de pile . Il utilise le style de passage de continuation et montre une implémentation sans pile.

Notez également que les anciennes architectures informatiques (par exemple, IBM / 360 ) n’avaient aucun registre de pile matériel. Mais le système d’exploitation et le compilateur ont réservé un registre pour le pointeur de pile par convention (en rapport avec les conventions d’appel ) afin qu’ils puissent disposer d’une pile d’appels logiciels .

En principe, un compilateur et un optimiseur du programme entier pourraient détecter le cas (quelque chose de commun pour les systèmes intégrés) où le graphe d’appel est connu de manière statique et sans aucune récursion (ni pointeur de fonction). Dans un tel système, chaque fonction pouvait conserver son adresse de retour dans un emplacement statique fixe (et c'était ainsi que fonctionnait Fortran77 dans les ordinateurs de l'époque 1970).

De nos jours, les processeurs ont également des piles d’appels (et des instructions d’appel et de renvoi de la machine) prenant en compte les caches de processeur .

Basile Starynkevitch
la source
1
Assez sûr que FORTRAN a cessé d'utiliser les emplacements de retour statiques lorsque FORTRAN-66 est sorti et a nécessité une assistance pour SUBROUTINEet FUNCTION. Vous avez cependant raison pour les versions antérieures (FORTRAN-IV et éventuellement WATFIV).
TMN
Et COBOL, bien sûr. Et excellent point à propos d’IBM / 360: il s’est beaucoup utilisé même s’il manquait des modes d’adressage de pile matérielle. (R14, je crois que c'était?) Et il avait des compilateurs pour les langages basés sur des piles, par exemple, PL / I, Ada, Algol, C.
davidbak
En effet, j’ai étudié la 360 au collège et j’ai trouvé cela déconcertant au début.
JDługosz le
1
@ JDługosz Le meilleur moyen pour les étudiants modernes en architecture informatique de considérer la 360 est une machine RISC très simple ... bien qu'avec plus d'un format d'instruction ... et quelques anomalies comme TRet TRT.
davidbak
Que diriez-vous de "zéro et ajouter emballé" pour déplacer un registre? Mais "branche et lien" plutôt que pile pour adresse de retour a fait son retour.
JDługosz le
10

Vous avez de bonnes réponses jusqu'à présent. Permettez-moi de vous donner un exemple peu pratique mais très pédagogique de la manière dont vous pourriez concevoir un langage sans la notion de pile ou de "flux de contrôle". Voici un programme qui détermine les factorielles:

function f(i) => if i == 0 then 1 else i * f(i - 1)
let x = f(3)

Nous mettons ce programme dans une chaîne et nous évaluons le programme par substitution textuelle. Donc, lorsque nous évaluons f(3), nous faisons une recherche et remplaçons par 3 pour i, comme ceci:

function f(i) => if i == 0 then 1 else i * f(i - 1)
let x = if 3 == 0 then 1 else 3 * f(3 - 1)

Génial. Nous effectuons maintenant une autre substitution textuelle: nous voyons que la condition du "si" est fausse et nous remplaçons par une autre chaîne, produisant le programme:

function f(i) => if i == 0 then 1 else i * f(i - 1)
let x = 3 * f(3 - 1)

Nous faisons maintenant une autre chaîne pour remplacer toutes les sous-expressions impliquant des constantes:

function f(i) => if i == 0 then 1 else i * f(i - 1)
let x = 3 * f(2)

Et vous voyez comment cela se passe; Je ne travaillerai pas plus loin. Nous pourrions continuer à faire une série de substitutions de cordes jusqu'à ce que nous ayons fini let x = 6et nous aurions fini.

Nous utilisons traditionnellement la pile pour les variables locales et les informations de continuation; Souvenez-vous, une pile ne vous dit pas d'où vous venez, elle vous indique où vous allez ensuite avec cette valeur de retour en main.

Dans le modèle de programmation avec substitution de chaînes, il n'y a pas de "variables locales" dans la pile; les paramètres formels sont substitués à leurs valeurs lorsque la fonction est appliquée à son argument, plutôt que d'être placés dans une table de recherche sur la pile. Et il n’ya pas de solution de rechange car l’évaluation de programme consiste simplement à appliquer des règles simples pour la substitution de chaînes afin de produire un programme différent mais équivalent.

Maintenant, bien sûr, faire des substitutions de chaînes n'est probablement pas la solution. Mais les langages de programmation prenant en charge le "raisonnement équationnel" (tel que Haskell) utilisent logiquement cette technique.

Eric Lippert
la source
3
Retina est un exemple de langage de programmation basé sur Regex qui utilise des opérations de chaîne pour le calcul.
Andrew Piliser
2
@AndrewPiliser Conçu et mis en œuvre par ce mec cool .
Chat
3

Depuis la publication par Parnas en 1972 de Sur les critères à utiliser pour la décomposition de systèmes en modules, il a été raisonnablement admis que les informations dissimulées dans les logiciels sont une bonne chose. Cela fait suite à un long débat au cours des années 60 sur la décomposition structurelle et la programmation modulaire.

La modularité

Un résultat nécessaire des relations de type "boîte noire" entre les modules mis en œuvre par différents groupes dans tout système multithread requiert un mécanisme permettant la réentrance et un moyen de suivre le graphe d'appels dynamique du système. Le flux d'exécution contrôlé doit passer à la fois dans et hors de plusieurs modules.

Portée dynamique

Dès que la portée lexicale est insuffisante pour suivre le comportement dynamique, une comptabilité d’exécution est nécessaire pour suivre la différence.

Etant donné qu'un thread (par définition) n'a qu'un seul pointeur d'instruction en cours, une pile LIFO est appropriée pour suivre chaque invocation.

Exceptions

Ainsi, bien que le modèle de continuation ne maintienne pas explicitement une structure de données pour la pile, il y a toujours des appels imbriqués de modules qui doivent être conservés quelque part!

Même les langages déclaratifs conservent l'historique des évaluations ou inversement, aplatissent le plan d'exécution pour des raisons de performances et maintiennent les progrès d'une autre manière.

La structure de boucle sans fin identifiée par rwong est courante dans les applications à haute fiabilité avec une planification statique qui interdit de nombreuses structures de programmation courantes, mais exige que toute l'application soit considérée comme une boîte blanche sans aucune information masquante importante.

Plusieurs boucles sans fin simultanées ne nécessitent aucune structure pour conserver les adresses de retour car elles n'appellent pas de fonctions, ce qui rend la question sans objet. S'ils communiquent à l'aide de variables partagées, celles-ci peuvent facilement dégénérer en des adresses analogues héritées à la Fortran.

Pekka
la source
1
Vous vous peignez dans un coin en supposant " tout système multithread". Les machines à états finis couplés peuvent avoir plusieurs threads dans leur implémentation, mais ne nécessitent pas de pile LIFO. Il n'y a aucune limite dans les FSM pour que vous retourniez à n'importe quel état précédent, et encore moins dans l'ordre LIFO. Donc, c'est un vrai système multi-thread pour lequel il ne tient pas. Et si vous vous limitez à une définition du multi-thread en tant que "piles d'appels de fonctions indépendantes parallèles", vous obtenez une définition circulaire.
MSalters
Je ne lis pas la question de cette façon. OP est familier avec les appels de fonction, mais pose des questions sur les autres systèmes.
MSalters
@MSalters Mis à jour pour incorporer des boucles sans fin simultanées. Le modèle est valide, mais limite l'évolutivité. Je suggérerais que même les machines d'état modérées intègrent des appels de fonction pour permettre la réutilisation du code.
Pekka
2

Tous les anciens ordinateurs centraux (IBM System / 360) n’avaient aucune notion de pile. Sur le 260, par exemple, les paramètres ont été construits dans un emplacement fixe en mémoire et lorsqu’un sous-programme était appelé, il était appelé avec un R1pointage sur le bloc de paramètres et R14contenant l’adresse de retour. La routine appelée, si elle souhaitait appeler une autre sous-routine, devrait être enregistrée R14dans un emplacement connu avant de passer cet appel.

Ceci est beaucoup plus fiable qu'une pile, car tout peut être stocké dans des emplacements de mémoire fixes établis lors de la compilation et il est garanti à 100% que les processus ne seront jamais à court de pile. Il n’existe aucun des "Allocate 1MB et croise les doigts" que nous devons faire de nos jours.

Les appels récursifs de sous-routines étaient autorisés dans PL / I en spécifiant le mot clé RECURSIVE. Ils signifiaient que la mémoire utilisée par le sous-programme était allouée de manière dynamique plutôt que statique. Mais les appels récursifs étaient aussi rares qu’ils le sont maintenant.

Le fonctionnement sans pile facilite également beaucoup le multi-threading, raison pour laquelle on tente souvent de rendre les langues modernes sans pédoncule. Par exemple, il n'y a aucune raison, par exemple, qu'un compilateur C ++ ne puisse pas être modifié en arrière-plan pour utiliser de la mémoire allouée dynamiquement plutôt que des piles.

Martin Kochanski
la source