J'examine les techniques d'implémentation des langages de programmation et j'ai récemment rencontré des piles de spaghetti, qui sont censées être un bon choix pour un modèle de style de passage de continuation (compte tenu de leur utilisation, par exemple, dans Scheme et SML / NJ ). Pour simplifier, considérons uniquement un processus à un seul thread pour cette question.

Cependant, je suis un peu confus par le schéma sur Wikipédia (également trouvé ailleurs ). En particulier, je ne comprends pas comment une telle situation peut se produire. Je peux seulement imaginer que les branches grisées sont inaccessibles et devraient être récupérées. D'un autre côté, avec ma compréhension vague de la façon d'implémenter CPS en utilisant des piles de spaghetti, je ne peux pas imaginer comment vous pourriez obtenir une boucle dans cette structure. Je dois conclure que, plutôt qu'un "arbre parent-pointeur", il s'agit en fait d'un graphique acyclique dirigé, avec autant de sources non ordonnées qu'il y a de threads, et autant de puits qu'il y a de "points de sortie" (potentiels).

Mais ma compréhension de cette implémentation est assez vague, donc je suppose que je manque probablement quelque chose. J'espère que quelqu'un pourra m'éclairer ici sur les «piles d'appels spaghetti», c'est-à-dire la structure de données utilisée dans Scheme et / ou SML / NJ pour implémenter des processus basés sur CPS.

1. Étant donné la pile d'appels de spaghetti suivante:

   [exit point] <-- ... <-- [frame A] <-- [frame B (active)]
                                   ^
                                    `---- [frame C]
   

   Pour autant que je sache, tout contrôle de flux de B déroule la pile en sautant sur un parent (A devient actif, B inaccessible est désormais ordonné), ou en remplaçant le cadre actif par un sous-graphique, connecté uniquement à l'aide de références détenues par B ou de références aux nouveaux cadres. L'exécution ne peut pas aller à la trame C, ce qui doit signifier que la trame C est une ordure.

2. Plutôt que la situation précédente, je pense que la situation sans déchets suivante peut survenir:

   [exit point] <-- ... <-- [frame W] <-- [frame X] <-- [frame Z (active)]
                                   ^                     |
                                    `---- [frame Y] <---´
   

   Par exemple, je peux imaginer que la trame Z appartient à une fonction de décision, qui continue soit avec la trame X soit avec la trame Y (l'une ou l'autre reviendrait à W). Cela signifie que les piles d'appels spaghetti ne sont pas des " arbres de pointeurs parents ".

3. Cependant, je ne peux imaginer aucune situation où une boucle peut être construite. Prenez la situation suivante, par exemple:

   [exit point] <-- ... <-- [frame P] --> [frame Q (active)]
                                   ^             |
                                   |             v
                                    `---- [frame R]
   

   Je sais que les liaisons récursives sont une chose, mais je doute fortement que cela soit sensé. Si Q devait revenir à R, la trame Q est "dépensée". Si R devait revenir à P, et P ne peut pas simplement revenir à Q, car il faudrait d'abord le réinitialiser. En tant que telles, les boucles provoqueraient des états incohérents. (À moins, bien sûr, que je comprenne mal le but de cette structure de données, et que vous n'utiliseriez que les nœuds qu'elle contient comme modèle pour votre cadre actuel.)

À partir de ces observations, je dois conclure qu'une pile d'appels de spaghetti (sans ordures) est en fait un DAG. Est-ce correct? Ou est-ce que je comprends mal le but de cette structure de données?

Mises à jour:

• J'ai parcouru une copie du document suivant:

  EA Hauck et BA Dent. 1968. Mécanisme de pile B6500 / B7500 de Burroughs. Dans Actes du 30 avril au 2 mai 1968, conférence informatique conjointe de printemps (AFIPS '68 (printemps)). ACM, New York, NY, USA, 245-251. DOI = http://dx.doi.org/10.1145/1468075.1468111

  Cet article semble définir le système de pile Suguaro. Il s'avère que ce système de pile Suguaro est une pile d'appels traditionnelle qui permet à plusieurs "travaux" de parcourir les trames d'une pile partiellement partagée; ce n'est absolument pas lié aux suites.

• L'article suivant (et son article complémentaire de 1996) explique apparemment ce qui se passe dans le compilateur SML / NJ:

  Zhong Shao et Andrew W. Appel. 2000. Conversion de fermeture efficace et sûre pour l'espace. ACM Trans. Programme. Lang. Syst. 22, 1 (janvier 2000), 129-161. DOI = http://dx.doi.org/10.1145/345099.345125

  Je pense que je devrais lire ce document ( copie sur le site Web de l'auteur ) avant de faire quoi que ce soit d'autre avec cette question. Le concept "Safely Linked Closures" est très similaire au Suguaro Stack System, en ce sens qu'il est toujours très peu profond et uniquement destiné à partager des variables libres:

  Notre nouvel algorithme de fermeture-conversion utilise des fermetures liées en toute sécurité (la 3ème colonne de la figure 1) qui ne contiennent que les variables réellement nécessaires dans la fonction mais évitent la copie de fermeture en regroupant les variables ayant la même durée de vie dans un enregistrement partageable. [...] Contrairement aux fermetures liées, le niveau d'imbrication des fermetures liées en toute sécurité ne dépasse jamais plus de deux (une couche pour la fermeture elle-même; une autre pour les enregistrements de durée de vie différente), de sorte qu'elles bénéficient toujours d'un temps d'accès variable très rapide.

  Le document mentionne également explicitement qu'il n'utilise "aucune pile d'exécution":

  Au lieu de cela, nous traitons tous les enregistrements d'activation comme des fermetures pour les fonctions de continuation et les allouons dans les registres du tas.

  Je pense que j'ai mal compris et / ou mal lu l'article Wikipedia, car les piles de spaghetti ne sont pas utilisées pour le contrôle du flux. Cependant, après une lecture attentive des articles d'Appel et de Shao, je pourrais peut-être reformuler la question en référence au graphique de dépendance des fermetures plutôt qu'à la "pile d'appels spaghetti" (qui n'est apparemment pas une chose).

Les piles de spaghetti sont-elles des arbres parent-pointeur?

Oui, les piles de spaghettis sont des arbres parent-pointeurs. Vous pouvez penser à une pile de spaghetti comme ayant la même structure qu'une collection de listes à lien unique qui partagent la structure. Vue d'ensemble, la collection de listes forme un arbre. Mais lorsqu'elle est vue individuellement, chaque liste forme une pile.

Chaque processus du système aura une de ces listes, qui représente sa pile de contrôle. Le début de la liste est le haut de la pile (c'est-à-dire le cadre actif). Son nextpointeur fait référence au cadre parent.

Ce que vous voyez dans le diagramme est la structure de plusieurs processus. La pile du processus "actif" est mise en évidence. Les parties de l'arborescence qui ne font pas partie de la pile active sont grisées. Ceux-ci représentent des piles pour d'autres processus.

Les piles de spaghetti forment-elles un DAG?

Étant donné que les piles de spaghetti sont des arbres parent-pointeurs, ce sont en effet des DAG. Mais seuls les DAG qui sont aussi des arbres peuvent être des piles de spaghetti. Donc non, les piles de spaghetti ne forment pas des DAG qui ne sont pas des arbres.

Votre exemple de fonction de décision confond la structure d'une pile de contrôle avec les données stockées dans la pile. Certes, n'importe quelle structure pourrait se former si nous commençons à considérer les données. Mais en tant que structure de données, chaque nœud d'une pile de spaghetti aura exactement un parent.