chamadas de cauda em arquiteturas sem uma pilha de chamadas

Question

A minha resposta para um recente sobre GOTOs e recursão de cauda foi formulada em termos de uma pilha de chamadas. Eu estou preocupado que não era suficientemente geral, por isso peço-lhe: como é a noção de uma chamada de cauda (ou equivalente) útil em arquiteturas sem uma pilha de chamadas

De passagem continuação, todas as chamadas funções substituir a função de chamada, e são, portanto, chamadas de cauda, ??por isso "chamada de cauda" não parece ser uma distinção útil. Em mensagens e arquiteturas de eventos com base, não parece ser um equivalente, embora por favor me corrijam se eu estiver errado. As duas últimas arquiteturas são casos interessantes como eles estão associados com OOP, ao invés de FP. E sobre outras arquiteturas? as velhas máquinas Lisp foram baseados em call-stacks?

Edit: De acordo com a " Que diabos é: Continuação Estilo de Passe ( CPS) "(e Alex abaixo), o equivalente a uma chamada cauda sob passagem continuação não é 'chamado substitui função de chamada de função', mas 'chamar função passa a continuação foi dado, em vez de criar uma nova continuação'. Este tipo de chamada cauda é útil, ao contrário do que afirmei.

Além disso, eu não estou interessado em sistemas que pilhas de chamadas uso em um nível inferior, para o nível mais elevado não requer uma pilha de chamadas. Esta restrição não se aplica a resposta de Alex porque ele está escrevendo sobre o fato de que outras arquiteturas de invocação ( é este o termo certo? ) muitas vezes têm uma pilha de chamadas equivalente, não que eles têm um lugar pilha de chamadas sob o capô. No caso de passagem continuação, a estrutura é como uma arborescência , mas com arestas na direcção oposta. equivalentes pilha de chamadas são altamente relevantes para os meus interesses.

Answer 1

Sobre a chance de que esta questão interesses alguém diferente de mim, eu tenho uma expandiu resposta para a outra questão que também responde a este. Aqui está o resumo, versão não rigorosa.

Quando um sistema computacional executa sub-cálculos (isto é, um cálculo é iniciado e deve fazer uma pausa enquanto uma outra cálculo é feito porque o primeiro depende do resultado do segundo), uma relação de dependência entre pontos de execução surge naturalmente. Em arquitecturas baseadas chamada-pilha, a relação é topologicamente uma caminho gráfico . Na CPS, é uma árvore, onde cada caminho entre a raiz e um nó é uma continuação. Na passagem de mensagens e rosqueamento, é uma coleção de gráficos de caminho. manipulação de eventos síncrona é basicamente a passagem de mensagens. Iniciando um sub-cálculo envolve estendendo a relação de dependência, exceto em uma chamada de cauda, ??que substitui uma folha em vez de acrescentar a ele.

Traduzindo cauda chamando para o tratamento de eventos assíncrona é mais complexa, então ao invés considerar uma versão mais geral. Se A é subscrito para um evento no canal 1, B é inscrito para o mesmo acontecimento no canal 2 e manipulador de B apenas accionado o evento no canal 1 (que traduz o caso em todos os canais), então A pode ser inscrito para o acontecimento no canal 2 em vez de subscrever B. Este é mais geral porque o equivalente a uma chamada cauda exige que

• assinatura de A no canal 1 é cancelado quando um está inscrito no canal 2
• os manipuladores são auto-unsubscribing (quando invocado, eles cancelar a assinatura)

Agora, para dois sistemas que não executam sub-computações: cálculo lambda (ou sistemas prazo reescrever em geral) e RPN. Para cálculo lambda, chamadas cauda correspondem aproximadamente a uma sequência de reduções em que o comprimento termo é O (1) (ver processos iterativos em seção SICP 1,2 ). Tome RPN usar uma pilha de dados e uma pilha de operações (em oposição a um fluxo de operações, as operações são aquelas ainda a ser processada), e um ambiente que mapeia símbolos de uma sequência de operações. chamadas cauda poderia corresponder a processos com o (1) crescimento da pilha.

Answer 2

"arquiteturas sem uma pilha de chamadas" tipicamente um "simular" em algum nível - por exemplo, de volta no tempo da IBM 360, foi utilizado o S-Type Convenção linkage usando registro-save áreas e argumentos de listas indicadas, por convenção, por certos registradores de uso geral.

Assim, "chamada de cauda" pode ainda importa: faz a necessidade função de chamada para preservar as informações necessárias para continuar a execução após o ponto de chamar (uma vez que a função chamada está terminada), ou não sei não vai haver nenhuma execução depois o ponto de chamada, e assim simplesmente reutilização do seu chamador "informações para a execução currículo" em vez?

Assim, por exemplo, uma otimização de chamada de cauda pode significar não anexando a continuação necessária para continuar a execução em qualquer vinculado lista está sendo utilizada para o fim ... o que eu gostaria de ver como uma "simulação de pilha de chamadas" (em algum nível, embora seja obviamente um arranjo mais flexível - não quero ter fãs pulando por toda a minha resposta de passagem de continuação; -).