Quelles sont les alternatives à l'utilisation d'une pile pour représenter la sémantique des appels de fonction?

Nous savons et aimons tous que les appels de fonction sont généralement implémentés à l'aide de la pile; il y a des trames, des adresses de retour, des paramètres, le tout.

Cependant, la pile est un détail d'implémentation: les conventions d'appel peuvent faire différentes choses (c.-à-d. Que l'appel rapide x86 utilise (certains) registres, MIPS et les suiveurs utilisent des fenêtres de registre, etc.) et les optimisations peuvent faire encore d'autres choses (inlining, omission du pointeur de trame, optimisation des appels de queue ..).

Bien sûr, la présence d'instructions de pile pratiques sur de nombreuses machines (machines virtuelles comme JVM et CLR, mais aussi de vraies machines comme x86 avec leur PUSH / POP, etc.) le rendent pratique à utiliser pour les appels de fonction, mais dans certains cas, il est possible pour programmer d'une manière dans laquelle une pile d'appels n'est pas nécessaire (je pense au style de passage de continuation ici, ou aux acteurs dans un système de transmission de messages)

Donc, je commençais à me demander: est-il possible d'implémenter une sémantique d'appel de fonction sans pile, ou mieux, en utilisant une structure de données différente (une file d'attente, peut-être, ou une carte associative?)
Bien sûr, je comprends qu'une pile est très pratique (il y a une raison pour laquelle il est omniprésent) mais j'ai récemment rencontré une implémentation qui m'a fait me demander ..

Est-ce que l'un d'entre vous sait si cela a déjà été fait dans un langage / une machine / une machine virtuelle, et si oui, quelles sont les différences et les lacunes frappantes?

EDIT: Mon intuition est que différentes approches de sous-calcul peuvent utiliser différentes structures de données. Par exemple, le calcul lambda n'est pas basé sur la pile (l'idée d'application de fonction est capturée par des réductions) mais je regardais un vrai langage / machine / exemple. Voilà pourquoi je demande ...

Selon la langue, il peut ne pas être nécessaire d'utiliser une pile d'appels. Les piles d'appels ne sont nécessaires que dans les langues qui permettent la récursivité ou la récurrence mutuelle. Si le langage ne permet pas la récursivité, alors une seule invocation d'une procédure peut être active à tout moment, et les variables locales pour cette procédure peuvent être allouées statiquement. Ces langages doivent prévoir des changements de contexte, pour la gestion des interruptions, mais cela ne nécessite toujours pas de pile.

Reportez-vous à FORTRAN IV (et versions antérieures) et aux versions antérieures de COBOL pour des exemples de langues qui ne nécessitent pas de piles d'appels.

Reportez-vous au Control Data 6600 (et aux machines Control Data antérieures) pour obtenir un exemple de supercalculateur ancien très performant qui ne fournissait pas de prise en charge matérielle directe pour les piles d'appels. Reportez-vous au PDP-8 pour un exemple de mini-ordinateur très réussi qui ne prenait pas en charge les piles d'appels.

Autant que je sache, les machines à empiler Burroughs B5000 ont été les premières machines avec des piles d'appels matériels. Les machines B5000 ont été conçues dès le départ pour exécuter ALGOL, ce qui a nécessité une récursivité. Ils possédaient également l'une des premières architectures basées sur des descripteurs, qui a jeté les bases des architectures de capacités.

Pour autant que je sache, c'est le PDP-6 (qui est devenu le DEC-10) qui a popularisé le matériel de pile d'appels, lorsque la communauté des pirates informatiques du MIT en a pris livraison et a découvert que l'opération PUSHJ (Push Return Address and Jump) a permis de réduire la routine d'impression décimale de 50 instructions à 10.

La sémantique d'appel de fonction la plus élémentaire dans un langage qui permet la récursivité nécessite des capacités qui correspondent bien à une pile. Si c'est tout ce dont vous avez besoin, alors une pile de base est une bonne correspondance simple. Si vous avez besoin de plus que cela, votre structure de données doit en faire plus.

Le meilleur exemple de besoin de plus que j'ai rencontré est la "poursuite", la possibilité de suspendre un calcul au milieu, de l'enregistrer comme une bulle d'état gelée et de le déclencher à nouveau plus tard, peut-être plusieurs fois. Les continuations sont devenues populaires dans le dialecte Scheme de LISP, comme moyen d'implémenter, entre autres, des sorties d'erreur. Les continuations nécessitent la possibilité de prendre un instantané de l'environnement d'exécution actuel, et de le reproduire plus tard, et une pile est quelque peu gênante pour cela.

Abelson & Sussman's "Structure and Interpretation of Computer Programs" donne quelques détails sur les suites.

Il n'est pas possible d'implémenter une sémantique d'appel de fonction sans utiliser une sorte de pile. Il est uniquement possible de jouer à des jeux de mots (par exemple, utilisez un nom différent, comme "FILO return buffer").

Il est possible d'utiliser quelque chose qui n'implémente pas la sémantique des appels de fonction (par exemple le style de passage de continuation, les acteurs), puis de construire la sémantique des appels de fonction par-dessus; mais cela signifie ajouter une sorte de structure de données pour suivre où le contrôle est passé lorsque la fonction revient, et cette structure de données serait un type de pile (ou une pile avec un nom / description différent).

Imaginez que vous ayez de nombreuses fonctions qui peuvent toutes s’appeler. Au moment de l'exécution, chaque fonction doit savoir où retourner lorsque la fonction se termine. Si vous firstappelez, secondvous avez:

second returns to somewhere in first

Ensuite, si vous avez des secondappels third:

third returns to somewhere in second
second returns to somewhere in first

Ensuite, si vous avez des thirdappels fourth:

fourth returns to somewhere in third
third returns to somewhere in second
second returns to somewhere in first

Lorsque chaque fonction est appelée, davantage d'informations "où retourner" doivent être stockées quelque part.

Si une fonction retourne, ses informations "où retourner" sont utilisées et ne sont plus nécessaires. Par exemple, si fourthretourne quelque part, thirdla quantité d'informations "où retourner" deviendrait:

third returns to somewhere in second
second returns to somewhere in first

Fondamentalement; La "sémantique des appels de fonctions" implique que:

• vous devez avoir des informations "où retourner"
• la quantité d'informations augmente à mesure que les fonctions sont appelées et diminue lorsque les fonctions reviennent
• la première information "où retourner" stockée sera la dernière information "où retourner" rejetée

Ceci décrit un tampon FILO / LIFO ou une pile.

Si vous essayez d'utiliser un type d'arbre, chaque nœud de l'arborescence n'aura jamais plus d'un enfant. Remarque: un nœud avec plusieurs enfants ne peut se produire que si une fonction appelle 2 fonctions ou plus en même temps , ce qui nécessite une sorte de concurrence (par exemple, threads, fork (), etc.) et il ne s'agirait pas de "sémantique d'appel de fonction". Si chaque nœud de l'arborescence n'aura jamais plus d'un enfant; alors cet "arbre" ne serait utilisé que comme tampon FILO / LIFO ou pile; et parce qu'il n'est utilisé que comme tampon FILO / LIFO ou comme pile, il est juste de prétendre que «l'arbre» ​​est une pile (et la seule différence est les jeux de mots et / ou les détails d'implémentation).

La même chose s'applique à toute autre structure de données qui pourrait éventuellement être utilisée pour implémenter la "sémantique d'appel de fonction" - elle sera utilisée comme une pile (et la seule différence est les jeux de mots et / ou les détails d'implémentation); à moins qu'il ne casse la "sémantique d'appel de fonction". Remarque: je fournirais des exemples pour d'autres structures de données si je le pouvais, mais je ne pense à aucune autre structure qui soit légèrement plausible.

Bien sûr, la façon dont une pile est implémentée est un détail d'implémentation. Ce pourrait être une zone de mémoire (où vous gardez une trace d'un "sommet de pile actuel"), ce pourrait être une sorte de liste liée (où vous gardez une trace de "l'entrée actuelle dans la liste"), ou il pourrait être implémenté dans certains autrement. Peu importe que le matériel ait ou non un support intégré.

Remarque: Si une seule invocation d'une procédure peut être active à tout moment; vous pouvez ensuite allouer statiquement de l'espace pour "où retourner". Il s'agit toujours d'une pile (par exemple, une liste chaînée d'entrées allouées statiquement utilisées de manière FILO / LIFO).

Notez également qu'il y a certaines choses qui ne suivent pas la "sémantique d'appel de fonction". Ces choses incluent «une sémantique potentiellement très différente» (par exemple, passage de continuation, modèle d'acteur); et comprend également des extensions communes à la "sémantique des appels de fonctions" comme la concurrence (threads, fibres, etc.), setjmp/longjmp , etc. , la gestion des exceptions, etc.

Le langage concaténatif du jouet XY utilise une file d'attente d'appels et une pile de données pour l'exécution.

Chaque étape de calcul implique simplement de définir le mot suivant à exécuter et, dans le cas des commandes internes, en alimentant sa fonction interne la pile de données et la file d'attente des appels en tant qu'arguments, ou avec les userdefs, en poussant les mots qui le composent à l'avant de la file d'attente.

Donc, si nous avons une fonction pour doubler l'élément supérieur:

; double dup + ;
// defines 'double' to be composed of 'dup' followed by '+'
// dup duplicates the top element of the data stack
// + pops the top two elements and push their sum

Ensuite, les fonctions de composition +et dupont les signatures de type pile / file d'attente suivantes:

// X is arbitraty stack, Y is arbitrary queue, ^ is concatenation
+      [X^a^b Y] -> [X^(a + b) Y]
dup    [X^a Y] -> [X^a^a Y]

Et paradoxalement, doubleressemblera à ceci:

double [X Y] -> [X dup^+^Y]

Donc, dans un sens, XY est sans pile.