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

Uma alternativa (um pouco) popular a uma pilha de chamadas é continuações .

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

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

Como @rwong apontou , o estilo de continuação de passagem é uma alternativa para uma pilha de chamadas. Programas escritos em (ou transformados em) estilo de continuação de passagem nunca retornam, então 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 de 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 hardware acompanha a suíte com recursos de alocação de quadros de pilha. Esse suporte variou muito ao longo dos anos com diferentes processadores. Alguns processadores adotaram registros de ponteiro de pilha e / ou 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, em seguida, de vários níveis, uma vantagem crucial da pilha é a da localidade do cache. O topo da pilha está quase sempre no cache. Sempre que você pode fazer algo que tenha uma grande taxa de acertos de cache, você está no caminho certo com 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 resumo, o uso da pilha evoluiu tanto em hardware quanto em software. Existem outros modelos (por exemplo, a computação de fluxo de dados foi tentada por um longo período), no entanto, a localização da pilha faz com que ela funcione muito bem. Além disso, o código procedural é exatamente o que os processadores querem, para desempenho: uma instrução informando o que fazer após o outro. Quando as instruções estão fora de ordem linear, o processador desacelera tremendamente, pelo menos até o momento, já que não descobrimos como fazer acesso aleatório tão rápido quanto o acesso sequencial. (Btw, existem problemas semelhantes em cada nível de memória, do cache, para a memória principal, para o disco ...)

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

(Também podemos jogar a mutabilidade das estruturas de dados nos trabalhos ...)

Isso não significa que outros modelos de programação não funcionem, especialmente quando eles podem ser traduzidos para as instruções sequenciais e o modelo de pilha de chamadas do hardware atual. Mas há uma vantagem distinta para modelos que suportam onde o hardware está. No entanto, as coisas nem sempre permanecem as mesmas, então podemos ver mudanças no futuro, já 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 programação imperativa
  3. Não é fundamental para programação funcional
• A pilha como uma abstração de "last-in, first-out" (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 continuação de passagem (CPS)
  • Máquina de estado - um loop gigante, com tudo embutido. (Pretendia ser inspirado na arquitetura de firmware do Saab Gripen, e atribuído a uma comunicação de Henry Spencer e reproduzido por John Carmack.) ^{(Nota # 1)}
  • Arquitetura de fluxo de dados - uma rede de atores conectados por filas (FIFO). As filas são às vezes chamadas de canais.

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

A pilha que você descreveu (como mecanismo de chamada de função) é específica da 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 existe um design muito simples, lento, mas que ainda é capaz de executar o mesmo código de máquina. Um design tão simples fará uso dos elementos básicos da lógica digital:

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

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

• link
• link

A estrutura de um programa como este 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 quem vê o software como um complemento das funções do hardware.

Não, não necessariamente.

Leia o documento antigo da Appel A coleta de lixo 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 empilhar.

Observe também que arquiteturas de computadores antigas (por exemplo, IBM / 360 ) não tinham nenhum registro de pilha de hardware. Mas o sistema operacional e o compilador reservavam um registro para o ponteiro da pilha por convenção (relacionado a convenções de chamada ) para que pudessem ter uma pilha de chamadas de software .

Em princípio, todo um compilador e otimizador de programa C pode detectar o caso (um tanto comum para sistemas embarcados) onde o gráfico de chamada é estaticamente conhecido e sem qualquer recursão (ou ponteiros de função). Em tal sistema, cada função poderia manter seu endereço de retorno em um local estático fixo (e era assim que Fortran77 funcionava em 1970 era computadores).

Hoje em dia, os processadores também têm pilhas de chamadas (e chamadas e retornam instruções da máquina) cientes dos caches da CPU .

Você tem algumas boas respostas até agora; Deixe-me dar-lhe um exemplo prático, mas altamente educativo, de como você poderia projetar uma linguagem sem a noção de pilhas ou "fluxo de controle". Aqui está um programa que determina os 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 para 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 "if" é falsa e faz outra string substituir, produzindo o programa:

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

Agora fazemos outra substituição de string em todas as subexpressões envolvendo constantes:

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

E você vê como isso acontece; Eu não vou trabalhar o ponto mais. Poderíamos continuar fazendo uma série de substituições de string até chegarmos a let x = 6 e terminaríamos.

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

No modelo de substituição de string de programação, 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 serem colocados em uma tabela de consulta na pilha. E não há como "ir a algum lugar a seguir", porque a avaliação do programa está simplesmente aplicando regras simples para a substituição de cadeias para produzir um programa diferente, mas equivalente.

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

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

Modularidade

Um resultado necessário dos relacionamentos de caixa preta entre módulos implementados por diferentes grupos em qualquer sistema multi-thread requer um mecanismo para permitir reentrância e um meio de rastrear o gráfico de chamada dinâmico do sistema. Fluxo controlado de execução tem que passar tanto dentro como fora de múltiplos módulos.

Escopo dinâmico

Assim que o escopo léxico for insuficiente para rastrear o comportamento dinâmico, é necessária alguma escrituração em tempo de execução para rastrear a diferença.

Dado que qualquer thread (por definição) tem apenas um único ponteiro de instrução atual, um LIFO-stack é apropriado para rastrear cada invocação.

Exceções

Assim, enquanto o modelo de continuação não mantém uma estrutura de dados explicitamente para a pilha, ainda há a chamada aninhada de módulos que devem ser mantidos em algum lugar!

Até mesmo as linguagens declarativas mantêm o histórico de avaliação ou, inversamente, achatam o plano de execução por motivos de desempenho e mantêm o progresso de alguma outra forma.

A estrutura de ciclo infinito identificada por rwong é comum em aplicativos de alta confiabilidade com programação estática que proíbe muitos recursos comuns estruturas de programação, mas exige que toda a aplicação seja considerada uma caixa branca sem ocultar informações significativas.

Múltiplos loops intermináveis concorrentes não requerem nenhuma estrutura para manter endereços de retorno, pois eles não chamam funções, fazendo com que a questão seja discutível. Se eles se comunicam usando variáveis compartilhadas, eles podem degenerar facilmente em análogos de endereços 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 era chamada, era chamada com R1 apontando para o bloco de parâmetros e R14 contendo o endereço de retorno. A rotina chamada, se quisesse chamar outra sub-rotina, teria que armazenar R14 em um local conhecido antes de fazer a chamada.

Isso é muito mais confiável do que uma pilha porque tudo pode ser armazenado em locais de memória fixa estabelecidos em tempo de compilação e pode ser 100% garantido que os processos nunca ficarão sem pilha. Não há nada do "Alocar 1MB 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 significavam que a memória usada pela sub-rotina era dinamicamente, em vez de alocada estaticamente. Mas as chamadas recursivas eram tão raras como são agora.

A operação sem pilha também facilita muito o multi-threading massivo, razão pela qual muitas vezes são feitas tentativas para tornar as línguas modernas sem stalkless. Não há nenhuma razão, por exemplo, para que um compilador C ++ não possa ser modificado de back-end para usar a memória alocada dinamicamente em vez de pilhas.