As pilhas são a única maneira razoável de estruturar programas?

A maioria das arquiteturas que eu vi depende de uma pilha de chamadas para salvar / restaurar o contexto antes das chamadas de função. É um paradigma tão comum que as operações push e pop são integradas à maioria dos processadores. Existem sistemas que funcionam sem uma pilha? Em caso afirmativo, como eles funcionam e para que são usados?

Uma alternativa (um tanto) popular a uma pilha de chamadas são as continuações .

A VM Parrot é baseada em continuação, por exemplo. É completamente sem pilha: os dados são mantidos em registros (como Dalvik ou LuaVM, o Parrot é baseado em registros) e o fluxo de controle é representado com continuações (ao contrário do Dalvik ou LuaVM, que possuem uma pilha de chamadas).

Outra estrutura de dados popular, usada normalmente pelas VMs Smalltalk e Lisp é a pilha de espaguete, que é como uma rede de pilhas.

Como @rwong apontou , o estilo de passagem de continuação é uma alternativa a uma pilha de chamadas. Os programas gravados no estilo (ou transformados em) de passagem de continuação nunca retornam; portanto, não há necessidade de uma pilha.

Respondendo à sua pergunta de uma perspectiva diferente: é possível ter uma pilha de chamadas sem ter uma pilha separada, alocando os quadros da pilha no heap. Algumas implementações de Lisp e Scheme fazem isso.

Antigamente, os processadores não tinham instruções de pilha e as linguagens de programação não suportavam recursão. Com o tempo, mais e mais idiomas optam por oferecer suporte à recursão e o conjunto de hardware seguido com recursos de alocação de quadros de pilha. Esse suporte variou bastante ao longo dos anos com diferentes processadores. Alguns processadores adotaram registros de quadro de pilha e / ou ponteiro de pilha; algumas instruções adotadas que realizariam a alocação de quadros de pilha em uma única instrução.

À medida que os processadores avançam com caches de nível único e multinível, uma vantagem crítica da pilha é a da localização do cache. A parte superior da pilha está quase sempre no cache. Sempre que você pode fazer algo que tenha uma grande taxa de acertos no cache, você está no caminho certo com os processadores modernos. O cache aplicado à pilha significa que variáveis ​​locais, parâmetros, etc. estão quase sempre no cache e desfrutam do mais alto nível de desempenho.

Em suma, o uso da pilha evoluiu tanto em hardware quanto em software. Existem outros modelos (por exemplo, a computação no fluxo de dados foi tentada por um período prolongado); no entanto, a localização da pilha faz com que ela funcione muito bem. Além disso, o código processual é exatamente o que os processadores desejam para o desempenho: uma instrução informando o que fazer após o outro. Quando as instruções estão fora de ordem linear, o processador diminui tremendamente, pelo menos até o momento, uma vez que não descobrimos como fazer o acesso aleatório tão rápido quanto o acesso seqüencial. (Aliás, existem problemas semelhantes em cada nível de memória, do cache, a memória principal, o disco ...)

Entre o desempenho demonstrado das instruções de acesso seqüencial e o comportamento benéfico de armazenamento em cache da pilha de chamadas, temos, pelo menos no momento, um modelo de desempenho vencedor.

(Podemos lançar mutabilidade das estruturas de dados nos trabalhos também ...)

Isso não significa que outros modelos de programação não funcionem, especialmente quando eles podem ser traduzidos para as instruções seqüenciais e o modelo de pilha de chamadas do hardware atual. Mas há uma vantagem distinta para os modelos que suportam onde o hardware está. No entanto, as coisas nem sempre permanecem as mesmas, portanto, podemos ver mudanças no futuro, à medida que diferentes tecnologias de memória e transistor permitem mais paralelismo. É sempre uma brincadeira entre linguagens de programação e recursos de hardware, então, vamos ver!

TL; DR

• Pilha de chamadas como um mecanismo de chamada de função:
  1. Geralmente é simulado por hardware, mas não é fundamental para a construção de hardware
  2. É fundamental para a programação imperativa
  3. Não é fundamental para a programação funcional
• A pilha como uma abstração de "último a entrar, primeiro a sair" (LIFO) é fundamental para a ciência da computação, algoritmos e até mesmo alguns domínios não técnicos.
• Alguns exemplos de organização de programas que não usam pilhas de chamadas:
  • Estilo de passagem de continuação (CPS)
  • Máquina de estado - um loop gigante, com tudo embutido. (Supostamente inspirado na arquitetura de firmware da Saab Gripen e atribuído a uma comunicação de Henry Spencer e reproduzida por John Carmack.) ^{(Nota 1)}
  • Arquitetura de fluxo de dados - uma rede de atores conectados por filas (FIFO). As filas às vezes são chamadas de canais.

O restante desta resposta é uma coleção aleatória de pensamentos e histórias e, portanto, um pouco desorganizada.

A pilha que você descreveu (como um mecanismo de chamada de função) é específica para a programação imperativa.

Abaixo da programação imperativa, você encontrará o código da máquina. O código da máquina pode emular a pilha de chamadas executando uma pequena sequência de instruções.

Abaixo do código da máquina, você encontrará o hardware responsável pela execução do software. Embora o microprocessador moderno seja complexo demais para ser descrito aqui, pode-se imaginar que exista um design muito simples, lento, mas capaz de executar o mesmo código de máquina. Um design tão simples utilizará os elementos básicos da lógica digital:

1. Lógica combinacional, isto é, uma conexão de portas lógicas (e, ou, não, ...) Observe que "lógica combinacional" exclui feedbacks.
2. Memória, isto é, flip-flops, travas, registradores, SRAM, DRAM, etc.
3. Uma máquina de estado que consiste em alguma lógica combinatória e em alguma memória, apenas o suficiente para poder implementar um "controlador" que gerencia o restante do hardware.

As discussões a seguir continham muitos exemplos de formas alternativas de estruturar programas imperativos.

• http://number-none.com/blow/john_carmack_on_inlined_code.html
• https://news.ycombinator.com/item?id=8374345

A estrutura de such as program terá a seguinte aparência:

void main(void)
{
    do
    {
        // validate inputs for task 1
        // execute task 1, inlined, 
        // must complete in a deterministically short amount of time
        // and limited to a statically allocated amount of memory
        // ...
        // validate inputs for task 2
        // execute task 2, inlined
        // ...
        // validate inputs for task N
        // execute task N, inlined
    }
    while (true);
    // if this line is reached, tell the programmers to prepare
    // themselves to appear before an accident investigation board.
    return 0; 
}

Esse estilo seria apropriado para microcontroladores, ou seja, para aqueles que veem o software como um companheiro para as funções do hardware.

Não, não necessariamente.

Leia a coleta de lixo de papel antigo de Appel pode ser mais rápida que a Alocação de pilha . Ele usa o estilo de passagem de continuação e mostra uma implementação sem pilha.

Observe também que arquiteturas antigas de computador (por exemplo, IBM / 360 ) não tinham nenhum registro de pilha de hardware. Mas o SO e o compilador reservaram um registro para o ponteiro da pilha por convenção (relacionada às convenções de chamada ) para que eles pudessem ter uma pilha de chamadas de software .

Em princípio, todo um compilador e otimizador de programa C poderia detectar o caso (algo comum em sistemas embarcados) em que o gráfico de chamada é estaticamente conhecido e sem nenhuma recursão (ou ponteiros de função). Nesse sistema, cada função poderia manter seu endereço de retorno em um local estático fixo (e foi assim que o Fortran77 trabalhou nos computadores da época de 1970).

Atualmente, os processadores também têm pilhas de chamadas (e instruções de chamada e devolução da máquina) cientes dos caches da CPU .

Você tem boas respostas até agora; deixe-me dar um exemplo impraticável, mas altamente educacional, de como você pode criar um idioma sem a noção de pilhas ou "fluxo de controle". Aqui está um programa que determina fatoriais:

function f(i) => if i == 0 then 1 else i * f(i - 1)
let x = f(3)

Colocamos este programa em uma string e avaliamos o programa por substituição textual. Então, quando estamos avaliando f(3), fazemos uma pesquisa e substituímos por 3 por i, assim:

function f(i) => if i == 0 then 1 else i * f(i - 1)
let x = if 3 == 0 then 1 else 3 * f(3 - 1)

Ótimo. Agora, realizamos outra substituição textual: vemos que a condição do "se" é falsa e substituímos outra string, produzindo o programa:

function f(i) => if i == 0 then 1 else i * f(i - 1)
let x = 3 * f(3 - 1)

Agora, substituímos outra string em todas as subexpressões que envolvem constantes:

function f(i) => if i == 0 then 1 else i * f(i - 1)
let x = 3 * f(2)

E você vê como isso vai; Não vou insistir mais nisso. Poderíamos continuar fazendo uma série de substituições de cordas até chegarmos ao fim let x = 6e terminarmos.

Usamos a pilha tradicionalmente para variáveis ​​locais e informações de continuação; lembre-se, uma pilha não diz de onde você veio, mas para onde você está indo a seguir com esse valor de retorno em mãos.

No modelo de programação de substituição de cadeia, não há "variáveis ​​locais" na pilha; os parâmetros formais são substituídos por seus valores quando a função é aplicada ao seu argumento, em vez de colocados em uma tabela de pesquisa na pilha. E não há "ir a algum lugar a seguir" porque a avaliação do programa está simplesmente aplicando regras simples para que a substituição de cadeias produza um programa diferente, mas equivalente.

Agora, é claro, realmente fazer substituições de strings provavelmente não é o caminho a percorrer. Porém, linguagens de programação que suportam "raciocínio equacional" (como Haskell) estão logicamente usando essa técnica.

Desde a publicação de Parnas em 1972 de Sobre os critérios a serem usados ​​na decomposição de sistemas em módulos , foi razoavelmente aceito que a informação oculta no software é uma coisa boa. Isso se segue a um longo debate ao longo dos anos 60 sobre decomposição estrutural e programação modular.

Modularidade

Um resultado necessário das relações de caixa preta entre os módulos implementados por diferentes grupos em qualquer sistema multiencadeado requer um mecanismo para permitir a reentrada e um meio para rastrear o gráfico de chamadas dinâmico do sistema. O fluxo controlado de execução deve passar para dentro e para fora de vários módulos.

Escopo dinâmico

Assim que o escopo lexical for insuficiente para rastrear o comportamento dinâmico, será necessária alguma contabilidade de tempo de execução para rastrear a diferença.

Como qualquer thread (por definição) possui apenas um ponteiro de instrução atual, uma pilha LIFO é apropriada para rastrear cada chamada.

Exceções

Portanto, embora o modelo de continuação não mantenha uma estrutura de dados explicitamente para a pilha, ainda há a chamada aninhada de módulos que deve ser mantida em algum lugar!

Até mesmo linguagens declarativas mantêm o histórico de avaliação ou, por outro lado, achatam o plano de execução por razões de desempenho e mantêm o progresso de alguma outra maneira.

A estrutura de loop infinito identificada por rwong é comum em aplicativos de alta confiabilidade com agendamento estático que desaprova muitas estruturas de programação comuns, mas exige que o aplicativo inteiro seja considerado uma caixa branca sem ocultar informações significativas.

Vários loops intermináveis ​​simultâneos não exigem nenhuma estrutura para armazenar endereços de retorno, pois eles não chamam funções, tornando a questão discutível. Se eles se comunicam usando variáveis ​​compartilhadas, elas podem degenerar facilmente em análogos de endereço de retorno herdados no estilo Fortran.

Todos os mainframes antigos (IBM System / 360) não tinham noção de pilha. No 260, por exemplo, os parâmetros foram construídos em um local fixo na memória e, quando uma sub-rotina foi chamada, ela foi chamada R1apontando para o bloco de parâmetros e R14contendo o endereço de retorno. A rotina chamada, se quisesse chamar outra sub-rotina, teria que armazenar R14em um local conhecido antes de fazer a chamada.

Isso é muito mais confiável que uma pilha, porque tudo pode ser armazenado em locais fixos de memória estabelecidos em tempo de compilação e pode ser 100% garantido que os processos nunca ficarão sem pilha. Não existe nenhum dos "Alocar 1 MB e cruzar os dedos" que temos que fazer hoje em dia.

Chamadas de sub-rotina recursivas foram permitidas no PL / I, especificando a palavra-chave RECURSIVE. Eles queriam dizer que a memória usada pela sub-rotina foi alocada dinamicamente e não estaticamente. Mas ligações recursivas eram tão raras quanto agora.

A operação sem pilha também facilita muito o multiencadeamento massivo, e é por isso que geralmente são feitas tentativas para tornar os idiomas modernos sem obstáculos. Não há nenhuma razão, por exemplo, para que um compilador C ++ não possa ser modificado pelo back-end para usar a memória alocada dinamicamente em vez de pilhas.