Queue appelle dans les architectures sans pile d'appel

Question

Ma réponse à une question récente à propos GOTO et récursion queue a été formulée en termes d'une pile d'appel. Je crains que ce n'était pas assez général, je vous demande: comment est la notion d'un appel de la queue (ou équivalent) utiles dans les architectures sans pile d'appel

?

En passant suite, toutes les fonctions appelées remplacer la fonction d'appel, et sont donc des appels queue, donc « appels » ne semble pas être une distinction utile. Dans les architectures basées sur la messagerie et d'événements, il ne semble pas être un équivalent, mais s'il vous plaît me corriger si je me trompe. Les deux dernières architectures sont des cas intéressants car ils sont associés à la POO, plutôt que FP. Qu'en est-il d'autres architectures? Ont été les vieilles machines Lisp basées sur appel-piles?

Edit: Selon « Que diable est: Suite Passing style ( CPS) »(et Alex ci-dessous), l'équivalent d'un appel de la queue en passant la poursuite est pas « fonction que vous avez appelée appelant la fonction », mais « fonction d'appel passe la suite il a été donné, plutôt que de créer une nouvelle continuation ». Ce type d'appel de la queue est utile, contrairement à ce que j'affirmais.

En outre, je ne suis pas intéressé par les systèmes qui utilisent des piles d'appels à un niveau inférieur, pour le niveau supérieur ne nécessite pas une pile d'appel. Cette restriction ne concerne pas la réponse d'Alex parce qu'il est écrit sur le fait que d'autres architectures d'invocation ( est-ce le bon terme? ) ont souvent une pile d'appel équivalent, pas qu'ils ont une pile d'appel quelque part sous le capot. Dans le cas du passage de continuation, la structure est comme une arborescence , mais avec des bords dans la direction opposée. équivalents de la pile d'appels sont très pertinents pour mes intérêts.

Answer 1

J'ai la chance sur ce cette question des intérêts de quelqu'un d'autre que moi, un réponse étendue pour l'autre question qui répond aussi à celui-ci. Voici le résumé, la version non rigoureuse.

Quand un système de calcul effectue les sous-calculs (à savoir un démarrage de calcul et doit faire une pause pendant un autre calcul est effectué parce que la première dépend du résultat de la seconde), une relation de dépendance entre les points d'exécution se produit naturellement. Dans les architectures à base d'appel pile, la relation est topologiquement un . Dans CPS, il est un arbre, où chaque chemin entre la racine et un nœud est une continuation. En passant et le filetage message, il est une collection de graphiques de chemin. la gestion des événements synchrone est essentiellement le passage de messages. À partir d'un sous-calcul implique l'extension de la relation de dépendance, sauf dans un appel de queue qui remplace une feuille plutôt que annexant à lui.

Traduire la queue appelant à la gestion des événements asynchrones est plus complexe, donc au lieu envisager une version plus générale. Si A est abonné à un événement sur le canal 1, B est abonné au même événement sur le canal 2 et le gestionnaire de B déclenche simplement l'événement sur le canal 1 (il traduit le cas sur tous les canaux), alors A peut être souscrit à l'événement sur le canal 2 au lieu de souscrire B. Ceci est plus général parce que l'équivalent d'un appel de queue exige que

• l'abonnement d'un canal 1 est annulée lorsque A est abonné sur le canal 2
• les gestionnaires sont auto-désabonnement (lorsqu'elle est appelée, ils annulent l'abonnement)

Maintenant, pour deux systèmes qui ne fonctionnent pas sous-calculs: le calcul lambda (ou des systèmes de réécriture terme en général) et RPN. Pour le calcul de lambda, queue appels correspondent à peu près à une séquence de réductions où la longueur de durée est O (1) (voir processus itératifs en section 1.2 SICP ). Prendre RPN d'utiliser une pile de données et une pile d'opérations (par opposition à un flux d'opérations, les opérations sont celles qui restent à traiter), et un environnement qui met en correspondance des symboles pour une séquence d'opérations. les appels de queue pourraient correspondre à des processus avec O (1) la croissance de la pile.

Answer 2

« Architectures sans pile d'appel » typiquement « simulent » un à un certain niveau - par exemple, de retour dans le temps d'IBM 360, nous avons utilisé le S-Type Convention liaison à l'aide de certains registres à usage général, les registres et enregistrer les zones arguments listes indiquées, par convention.

« appels » peut encore question suivante: la nécessité de la fonction d'appel pour préserver les informations nécessaires pour reprendre l'exécution après le point d'appel (une fois la fonction appelée est terminée), ou faut-il savoir qu'il n'y aura pas d'exécution après le point d'appel, et si simplement réutiliser de son appelant "info de reprendre l'exécution" au lieu?

Ainsi, par exemple une optimisation d'appel de queue peut signifier ne pas annexant la poursuite nécessaire pour reprendre l'exécution sur quelque liste liée est utilisée dans le but ... que je veux voir comme une « simulation de pile d'appel » (à un certain niveau, mais il est évidemment un arrangement plus flexible - ne veulent pas avoir des fans de passage continuer éparpille ma réponse; -).