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 ...
la source
realloc()
.Réponses:
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.
la source
foo
etbar
peut appelerbaz
), 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.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
first
appelez,second
vous avez:Ensuite, si vous avez des
second
appelsthird
:Ensuite, si vous avez des
third
appelsfourth
: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
fourth
retourne quelque part,third
la quantité d'informations "où retourner" deviendrait:Fondamentalement; La "sémantique des appels de fonctions" implique que:
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.la source
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:
Ensuite, les fonctions de composition
+
etdup
ont les signatures de type pile / file d'attente suivantes:Et paradoxalement,
double
ressemblera à ceci:Donc, dans un sens, XY est sans pile.
la source