Estou estudando técnicas de implementação para linguagens de programação e recentemente me deparei com pilhas de espaguete, que são supostamente uma boa opção para um modelo de estilo de passagem continuada (dado seu uso em, por exemplo, Scheme e SML / NJ ). Por uma questão de simplicidade, vamos considerar apenas um processo de thread único para esta pergunta.

No entanto, estou um pouco confuso com o diagrama da Wikipedia (também encontrado em outro lugar ). Em particular, não entendo como essa situação pode surgir. Só posso imaginar que os galhos acinzentados são inacessíveis e devem ser coletados no lixo. Por outro lado, com minha vaga compreensão de como implementar o CPS usando pilhas de espaguete, não consigo imaginar como você poderia obter um loop nessa estrutura. Eu tenho que concluir que, em vez de uma "árvore pai-ponteiro", é na verdade um gráfico acíclico direcionado, com tantas fontes que não são de lixo quanto existem threads e tantos sumidouros quanto possíveis "pontos de saída".

Mas meu entendimento dessa implementação é bastante vago, então acho que provavelmente estou perdendo alguma coisa. Espero que alguém possa me esclarecer aqui sobre "pilhas de chamadas de espaguete", com o que quero dizer a estrutura de dados usada no esquema e / ou SML / NJ para implementar processos baseados em CPS.

1. Dada a seguinte pilha de chamadas de espaguete:

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

   Pelo que entendi, qualquer controle de fluxo de B desenrola a pilha saltando para um pai (A se torna ativo, B inacessível agora é lixo) ou substituindo o quadro ativo por um subgráfico, conectado apenas usando referências mantidas por B ou referências para os novos quadros. A execução não pode fluir para o quadro C, o que deve significar que o quadro C é um lixo.

2. Em vez da situação anterior, acho que pode ocorrer a seguinte situação sem lixo:

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

   Por exemplo, posso imaginar que o quadro Z pertence a alguma função de decisão, que continua com o quadro X ou o quadro Y (um dos quais retornaria a W). Isso significa que as pilhas de chamadas de espaguete não são " árvores de ponteiros pai ".

3. No entanto, não consigo imaginar nenhuma situação em que um loop possa ser construído. Tome a seguinte situação, por exemplo:

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

   Eu sei que ligações recursivas são uma coisa, mas duvido muito que isso seja sensato. Se Q retornar ao R, o quadro Q será "gasto". Se R retornasse a P, e P não pudesse simplesmente retornar a Q, pois seria necessário reinicializar primeiro. Como tal, os loops causariam estados inconsistentes. (A não ser, é claro, que eu entenda mal a finalidade dessa estrutura de dados, e você usaria apenas os nós nela como um modelo para o seu quadro atual.)

A partir dessas observações, devo concluir que uma pilha de chamadas de espaguete (sem lixo) é realmente um DAG. Isso está correto? Ou estou entendendo mal o objetivo dessa estrutura de dados?

Atualizações:

• Examinei uma cópia do seguinte artigo:

  EA Hauck e BA Dent. 1968. Mecanismo de pilha B6500 / B7500 de Burroughs. Em Anais de 30 de abril a 2 de maio de 1968, conferência conjunta por computador da primavera (AFIPS '68 (Spring)). ACM, Nova York, NY, EUA, 245-251. DOI = http://dx.doi.org/10.1145/1468075.1468111

  Este artigo parece definir o Suguaro Stack System. Como se vê, esse Suguaro Stack System é uma pilha de chamadas tradicional que permite que vários "trabalhos" percorram os quadros de uma pilha parcialmente compartilhada; não está absolutamente relacionado a continuações.

• O artigo a seguir (e seu artigo complementar de 1996) aparentemente explica o que está acontecendo no compilador SML / NJ:

  Zhong Shao e Andrew W. Appel. 2000. Conversão de fechamento eficiente e segura para o espaço. ACM Trans. Programa. Lang. Syst. 22, 1 (janeiro de 2000), 129-161. DOI = http://dx.doi.org/10.1145/345099.345125

  Acho que devo ler este artigo ( cópia no site do autor ) antes de fazer qualquer outra coisa com esta pergunta. O conceito de "Fechos com segurança de conexão" é muito semelhante ao sistema Suguaro Stack, pois é sempre muito superficial e visa apenas compartilhar variáveis ​​livres:

  Nosso novo algoritmo de conversão de fechamento usa fechamentos vinculados com segurança (a terceira coluna na Figura 1) que contêm apenas variáveis ​​realmente necessárias na função, mas evitam a cópia de fechamento agrupando variáveis ​​com a mesma vida útil em um registro compartilhável. [...] Diferentemente dos fechamentos vinculados, o nível de aninhamento de fechamentos vinculados com segurança nunca excede mais de dois (uma camada para o fechamento propriamente dito; outra para registros de diferentes tempos de vida), para que eles ainda desfrutem de um tempo de acesso variável muito rápido.

  O documento também menciona explicitamente que não usa "nenhuma pilha de tempo de execução":

  Em vez disso, tratamos todos os registros de ativação como fechamentos para funções de continuação e os alocamos em registradores no heap.

  Acho que não entendi e / ou interpretei mal o artigo da Wikipedia, pois as pilhas de espaguete não são usadas para controle de fluxo. No entanto, após uma leitura cuidadosa dos artigos de Appel e Shao, talvez eu pudesse refazer a pergunta com referência ao gráfico de dependência dos fechamentos, em vez da "pilha de chamadas de espaguete" (o que aparentemente não é uma coisa).

Pilhas de espaguete são árvores de pais e ponteiros?

Sim, as pilhas de espaguete são árvores indicadoras de pais. Você pode pensar em uma pilha de espaguete como tendo a mesma estrutura que uma coleção de listas de links únicos que compartilham estrutura. Quando visualizada como um todo, a coleção de listas forma uma árvore. Porém, quando visualizadas individualmente, cada lista forma uma pilha.

Cada processo no sistema terá uma dessas listas, que representa sua pilha de controle. O cabeçalho da lista é o topo da pilha (ou seja, quadro ativo). Seu nextponteiro faz referência ao quadro pai.

O que você vê no diagrama é a estrutura para vários processos. A pilha do processo "ativo" é destacada. As partes da árvore que não fazem parte da pilha ativa ficam acinzentadas. Eles representam pilhas para outros processos.

As pilhas de espaguete formam um DAG?

Como as pilhas de espaguete são árvores indicadoras de pais, elas são de fato DAGs. Mas apenas DAGs que também são árvores podem ser pilhas de espaguete. Portanto, não, as pilhas de espaguete não formam DAGs que não são árvores.

Seu exemplo de função de decisão confunde a estrutura de uma pilha de controle com os dados armazenados na pilha. Certamente, qualquer estrutura poderia ser formada se começarmos a considerar os dados. Mas como uma estrutura de dados, cada nó em uma pilha de espaguete terá exatamente um pai.