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

19

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 ...

Lorenzo Dematté
la source
Clean utilise un graphique et une machine de réécriture de graphique, qui est à son tour implémentée à l'aide d'une machine à trois piles, mais avec un contenu différent de celui habituellement.
Pour les machines virtuelles, une liste chaînée peut être utilisée. Chaque nœud de la liste est une trame. Étant donné que la pile matérielle est utilisée par la machine virtuelle, cela permet aux trames d'exister sur le tas sans la surcharge de realloc().
shawnhcorey

Réponses:

19

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.

John R. Strohm
la source
2
Ce fut un grand aperçu historique, merci! Lorsque j'ai posé ma question, j'avais en effet des continuations en tête, notamment le style passant-continuation (CPS). Dans ce cas, une pile n'est pas seulement gênante, mais probablement pas nécessaire: vous n'avez pas besoin de vous rappeler où retourner, vous fournissez un point où continuer votre exécution. Je me demandais si d'autres approches sans pile étaient courantes, et vous en avez donné de très bonnes dont je n'étais pas au courant.
Lorenzo Dematté
Légèrement lié: vous avez correctement indiqué "si la langue ne permet pas la récursivité". Qu'en est-il du langage avec récursivité, en particulier des fonctions qui ne sont pas récursives? Ont-ils besoin d'une pile "par conception"?
Lorenzo Dematté
"Les piles d'appels ne sont nécessaires que dans les langues qui permettent la récursivité ou la récursivité mutuelle" - non. Si une fonction peut être appelée à partir de plusieurs endroits (par exemple les deux fooet barpeut appeler baz), alors la fonction doit savoir vers quoi retourner. Si vous imbriquez ces informations "à qui retourner", vous vous retrouvez avec une pile. Peu importe comment vous l'appelez ou s'il est pris en charge par le matériel du processeur ou quelque chose que vous émulez dans le logiciel (ou même s'il s'agit d'une liste liée d'entrées allouées statiquement), c'est toujours une pile.
Brendan
@Brendan pas nécessairement (du moins, c'est tout l'objet de ma question). "Où retourner" ou mieux "où aller ensuite" doit-il être une pile, c'est-à-dire une structure LIFO? Serait-ce un arbre, une carte, une file d'attente ou autre chose?
Lorenzo Dematté
Par exemple, mon instinct est que CPS a juste besoin d'un arbre, mais je ne suis pas sûr, ni je sais où regarder. C'est pourquoi je demande ..
Lorenzo Dematté
6

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.

Brendan
la source
Par définition, une pile est une collection LIFO: dernier entré, premier sorti. Une file d'attente est une collection FIFO.
John R. Strohm
La pile est-elle donc la seule structure de données acceptable? Si oui, pourquoi?
Lorenzo Dematté
@ JohnR.Strohm: Fixed :-)
Brendan
1
Pour les langues sans récursivité (directe ou mutuelle), il est possible d'allouer statiquement pour chaque méthode une variable qui identifiera le lieu depuis lequel cette méthode a été appelée pour la dernière fois. Si l'éditeur de liens est conscient de telles choses, il peut allouer de telles variables d'une manière qui ne sera pas pire que ce qu'une pile ferait si chaque chemin d'exécution statiquement possible était réellement pris .
supercat
4

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.

Karl Damgaard Asmussen
la source
Ouah merci! J'examinerai cela ... je ne sais pas si cela s'applique vraiment aux appels de fonction, mais ça vaut quand même le coup d'oeil
Lorenzo Dematté
1
@ Karl Damgaard Asmussen "poussant les mots qui le composent à l'avant de la file d'attente" "poussant devant" N'est-ce pas une pile?
@ guesttttttt222222222 pas vraiment. Une pile d'appels stocke des pointeurs de retour, et lorsque la fonction revient, la pile d'appels est sautée. La file d'attente d'exécution ne stocke que des pointeurs vers des fonctions et lors de l'exécution de la fonction suivante, elle est étendue à sa définition et poussée à l'avant de la file d'attente. Dans XY, la file d'attente d'exécution est en fait un deque, car certaines opérations fonctionnent également à l'arrière de la file d'attente d'exécution.
Karl Damgaard Asmussen