Todos sabemos e amamos que as chamadas de função geralmente são implementadas usando a pilha; existem quadros, endereços de retorno, parâmetros, todo o lote.
No entanto, a pilha é um detalhe de implementação: as convenções de chamada podem fazer coisas diferentes (por exemplo, x86 fastcall usa (alguns) registradores, MIPS e seguidores usam janelas de registro etc.) e as otimizações podem fazer outras coisas (inlining, omissão do ponteiro de quadro, otimização de chamada de cauda ..).
Certamente, a presença de instruções de pilha convenientes em muitas máquinas (VMs como JVM e CLR, mas também máquinas reais como x86 com seu PUSH / POP etc.) tornam conveniente usá-lo para chamadas de função, mas em alguns casos é possível programar de uma maneira que não seja necessária uma pilha de chamadas (estou pensando no estilo de passagem de continuação aqui ou nos atores de um sistema de passagem de mensagens)
Então, eu estava começando a me perguntar: é possível implementar semântica de chamada de função sem uma pilha, ou melhor, usando uma estrutura de dados diferente (uma fila, talvez, ou um mapa associativo?)
É claro que eu entendo que uma pilha é muito conveniente (há uma razão pela qual é onipresente), mas recentemente encontrei uma implementação que me fez pensar ..
Algum de vocês sabe se alguma vez foi feito em algum idioma / máquina / máquina virtual? Em caso afirmativo, quais são as diferenças e deficiências marcantes?
EDIT: Meu pressentimento é que diferentes abordagens de sub-computação podem usar estruturas de dados diferentes. Por exemplo, o cálculo lambda não é baseado em pilha (a idéia de aplicação de função é capturada por reduções), mas eu estava olhando para uma linguagem / máquina / exemplo real. É por isso que estou perguntando ...
fonte
realloc()
.Respostas:
Dependendo do idioma, pode não ser necessário usar uma pilha de chamadas. As pilhas de chamadas são necessárias apenas em idiomas que permitem recursão ou recursão mútua. Se o idioma não permitir recursão, apenas uma chamada de qualquer procedimento poderá estar ativa a qualquer momento, e variáveis locais para esse procedimento poderão ser alocadas estaticamente. Essas linguagens precisam prever alterações de contexto, para manipulação de interrupções, mas isso ainda não requer uma pilha.
Consulte o FORTRAN IV (e versões anteriores) e versões anteriores do COBOL para obter exemplos de idiomas que não exigem pilhas de chamadas.
Consulte o Control Data 6600 (e as máquinas Control Data anteriores) para obter um exemplo de um supercomputador inicial de grande sucesso que não forneceu suporte direto de hardware para pilhas de chamadas. Consulte o PDP-8 para obter um exemplo de minicomputador inicial muito bem-sucedido que não suporta pilhas de chamadas.
Tanto quanto eu sei, as máquinas de pilha Burroughs B5000 foram as primeiras máquinas com pilhas de chamadas de hardware. As máquinas B5000 foram projetadas desde o início para executar o ALGOL, o que exigia recursão. Eles também tiveram uma das primeiras arquiteturas baseadas em descritor, que lançou as bases para arquiteturas de capacidade.
Até onde eu sei, foi o PDP-6 (que cresceu para o DEC-10) que popularizou o hardware da pilha de chamadas, quando a comunidade de hackers do MIT recebeu um e descobriu que a operação PUSHJ (Push Return Address and Jump) permitiu que a rotina de impressão decimal fosse reduzida de 50 instruções para 10.
A semântica de chamada de função mais básica em um idioma que permite recursão requer recursos que correspondem perfeitamente a uma pilha. Se é tudo o que você precisa, uma pilha básica é uma combinação boa e simples. Se você precisar de mais do que isso, sua estrutura de dados precisará fazer mais.
O melhor exemplo de necessidade de mais que encontrei é a "continuação", a capacidade de suspender um cálculo no meio, salvá-lo como uma bolha congelada de estado e acioná-lo novamente mais tarde, possivelmente várias vezes. As continuações se tornaram populares no dialeto Scheme do LISP, como uma maneira de implementar, entre outras coisas, saídas de erro. As continuações exigem a capacidade de capturar instantaneamente o ambiente de execução atual e reproduzi-lo mais tarde, e uma pilha é um pouco inconveniente para isso.
"Estrutura e interpretação de programas de computador", de Abelson & Sussman, detalha as continuações.
fonte
foo
ebar
pode chamarbaz
), a função precisa saber para onde retornar. Se você aninhar esta informação "a quem retornar", você acaba com uma pilha. Não importa como você o chama ou se é suportado pelo hardware da CPU ou algo que você imita no software (ou mesmo se é uma lista vinculada de entradas alocadas estaticamente), ainda é uma pilha.Não é possível implementar semântica de chamada de função sem usar algum tipo de pilha. Só é possível jogar jogos de palavras (por exemplo, use um nome diferente, como "FILO return buffer").
É possível usar algo que não implementa semântica de chamada de função (por exemplo, estilo de passagem de continuação, atores) e depois construir semântica de chamada de função; mas isso significa adicionar algum tipo de estrutura de dados para rastrear onde o controle é passado quando a função retorna e essa estrutura de dados seria um tipo de pilha (ou uma pilha com um nome / descrição diferente).
Imagine que você tem muitas funções que podem se chamar. No tempo de execução, cada função deve saber para onde retornar quando a função sair. Se você
first
ligarsecond
, você tem:Então, se você tiver
second
chamadasthird
:Então, se você tiver
third
chamadasfourth
:Como cada função é chamada, mais informações "para onde retornar" devem ser armazenadas em algum lugar.
Se uma função retornar, suas informações "para onde retornar" serão usadas e não serão mais necessárias. Por exemplo, se
fourth
retornar para algum lugarthird
, a quantidade de informações "para onde retornar" se tornaria:Basicamente; "semântica de chamada de função" implica que:
Isso descreve um buffer FILO / LIFO ou uma pilha.
Se você tentar usar um tipo de árvore, todos os nós da árvore nunca terão mais de um filho. Nota: um nó com vários filhos só pode acontecer se uma função chamar 2 ou mais funções ao mesmo tempo , o que exige algum tipo de simultaneidade (por exemplo, threads, fork (), etc) e não seria "semântica de chamada de função". Se todos os nós da árvore nunca tiverem mais de um filho; então essa "árvore" seria usada apenas como um buffer FILO / LIFO ou uma pilha; e como é usado apenas como um buffer ou pilha FILO / LIFO, é justo afirmar que a "árvore" é uma pilha (e a única diferença são jogos de palavras e / ou detalhes de implementação).
O mesmo se aplica a qualquer outra estrutura de dados que possa ser usada para implementar a "semântica de chamada de função" - ela será usada como uma pilha (e a única diferença são jogos de palavras e / ou detalhes de implementação); a menos que quebre "semântica de chamada de função". Nota: Eu forneceria exemplos para outras estruturas de dados, se pudesse, mas não consigo pensar em nenhuma outra estrutura que seja um pouco plausível.
Obviamente, como uma pilha é implementada é um detalhe da implementação. Pode ser uma área da memória (onde você monitora um "topo da pilha atual"), pode ser algum tipo de lista vinculada (onde você monitora a "entrada atual na lista") ou pode ser implementada em alguns outro jeito. Também não importa se o hardware possui suporte interno ou não.
Nota: Se apenas uma chamada de qualquer procedimento puder estar ativa a qualquer momento; então você pode alocar estaticamente espaço para informações "para onde retornar". Ainda é uma pilha (por exemplo, uma lista vinculada de entradas alocadas estaticamente usadas de maneira FILO / LIFO).
Observe também que existem algumas coisas que não seguem a "semântica de chamada de função". Essas coisas incluem "semânticas potencialmente muito diferentes" (por exemplo, passagem de continuação, modelo de ator); e também inclui extensões comuns para "semântica de chamada de função", como simultaneidade (threads, fibras, o que for),
setjmp
/longjmp
, manipulação de exceção etc.fonte
A linguagem concatenativa de brinquedo XY usa uma fila de chamadas e uma pilha de dados para execução.
Cada etapa da computação envolve simplesmente atribuir a próxima palavra a ser executada e, no caso de builtins, alimentar a função interna da pilha de dados e a fila de chamadas como argumentos, ou com userdefs, empurrando as palavras que a compõem para a frente da fila.
Portanto, se tivermos uma função para duplicar o elemento superior:
Em seguida, as funções de composição
+
edup
têm as seguintes assinaturas de tipos de pilha / fila:E paradoxalmente,
double
ficará assim:Então, de certa forma, XY é sem pilha.
fonte