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

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?

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.

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!

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.

• http://number-none.com/blow/john_carmack_on_inlined_code.html
• https://news.ycombinator.com/item?id=8374345

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.

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 .

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.

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.

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.