Chamadas de sub-rotina no mundo antigo: antes de os computadores terem stack ou heap

Chamadas de sub-rotina na era antiga sem stack e heap nos computadores

• Na computação moderna, stack e heap são algo tão natural que quase passam despercebidos, mas nos primeiros tempos da computação os computadores funcionavam sem stack nem heap.
• Não é tão difícil imaginar a computação sem alocação dinâmica de memória. Era preciso usar buffers de memória de tamanho fixo para tudo.
• Quando era necessário lidar com dados de tamanho variável, reservava-se um buffer fixo grande o bastante para acomodar os dados esperados.
• Também era possível fornecer configurações em tempo de compilação para que o cliente ajustasse a capacidade máxima, ou escrever um alocador personalizado que pudesse "alocar" e "liberar" memória dentro de buffers de tamanho fixo.

Chamando funções sem stack

• O compilador definia variáveis globais secretas para os parâmetros de entrada, o endereço de retorno e as variáveis locais de cada função.
• Para gerar uma chamada de função, o compilador atribuía os valores dos parâmetros a essas variáveis globais secretas correspondentes, atribuía o endereço de retorno à variável secreta de "endereço de retorno" da função e então saltava para o início da função.
• A função lia os parâmetros dessas variáveis globais secretas e usava variáveis globais secretas predefinidas que correspondiam logicamente às variáveis locais.
• Quando a função terminava, ela saltava para o endereço armazenado na variável secreta de "endereço de retorno" da função.

Otimização de ABI

• Para otimizar a ABI, alguns valores eram passados em registradores em vez de variáveis globais.
• A maioria dos processadores tinha um registrador de "link" e uma instrução de "branch with link", que definia automaticamente o registrador de link com o endereço seguinte à instrução de "branch with link".
• A convenção de chamada era otimizada para passar os dois primeiros parâmetros em registradores.

A impossibilidade da recursão

• Chamadas recursivas não funcionavam. Como a chamada recursiva sobrescrevia a variável de endereço de retorno com o endereço de retorno da própria chamada recursiva, a chamada externa acabava saltando para o lugar errado ao terminar.
• As linguagens de programação da época resolveram esse problema declarando que não davam suporte à recursão.

Conversa bônus

• Alguns compiladores operavam de forma ainda mais engenhosa usando código auto-modificável: a variável especial de endereço de retorno era, na verdade, o campo de endereço da instrução de salto no fim da função.
• Quando o processador não oferecia suporte a salto indireto, esse método era usado por necessidade prática.
• Depois que o valor prático das sub-rotinas foi reconhecido, muitos processadores passaram a adicionar instruções de chamada de sub-rotina que armazenavam o endereço de retorno na primeira palavra da sub-rotina e iniciavam a execução a partir da segunda palavra da sub-rotina.
• Para retornar da sub-rotina, era executado um salto indireto por meio do rótulo inicial da sub-rotina.

Opinião do GN⁺

• Este artigo ajuda a entender a evolução das técnicas de gerenciamento de memória usadas no desenvolvimento de software moderno ao explicar como se programava nos primeiros tempos da computação, quando não existiam stack nem heap.
• A forma de programar da época, sem stack nem heap, pode parecer muito estranha e ineficiente para desenvolvedores modernos, mas oferece um contexto importante para entender como a tecnologia evoluiu ao longo da história da computação.
• As limitações de programação de uma era em que chamadas recursivas eram impossíveis trazem um fato histórico interessante para desenvolvedores que hoje usam algoritmos recursivos.
• Sob uma perspectiva crítica, esses métodos iniciais de programação mostram como eram extremamente limitados para atender às exigências complexas e variadas do mundo moderno.

[GN⁺]

Comentários do Hacker News

• Avaliação positiva do livro "A Arte da Programação de Computadores"

  • Embora o livro pareça antigo, ele aborda algoritmos para modificar vários arrays dinâmicos e estruturas de dados anteriores ao heap e à stack.
  • O livro também explica coleta de lixo e a implementação de listas em Lisp, oferecendo um conhecimento enciclopédico que Knuth sabe despertar.

• Explicação de como dois arrays podem compartilhar dinamicamente um único espaço

  • Um array cresce normalmente a partir da posição #0, e o outro cresce ao contrário a partir da posição #End, permitindo que os dois compartilhem com eficiência um espaço alocado estaticamente.
  • Esse método pode ser estendido para vários arrays, mas nesse ponto pode ser melhor usar Malloc e Realloc.

• Compartilhamento de um link para uma história divertida sobre como foi controversa a introdução de funções recursivas na linguagem ALGOL

  • O link traz uma história interessante sobre como a recursão foi introduzida nas linguagens de programação.

• Relato de experiência ao escrever um interpretador Forth para uma máquina SUBLEQ e uma máquina bit-serial

  • Essas duas máquinas não têm a pilha de chamadas de função, que é essencial para Forth.
  • A SUBLEQ não permite carregamento e armazenamento indiretos, e requer código auto-modificante para realizar tarefas incomuns.
  • Foi construída uma máquina virtual para executar essas funções e dar suporte a multithreading cooperativo.
  • Quando necessário, o heap é escrito em Forth, incluindo também operações de ponto flutuante implementadas como funções de software.

• Explicação sobre a evolução técnica relacionada à chamada de sub-rotinas no processador PDP-8

  • No início, a instrução JMS armazenava o endereço de retorno na primeira palavra da função.
  • Depois, locais de auto-incremento passaram a ser usados para criar uma stack simples, e o prólogo/epílogo da função gerenciava manualmente essa stack para permitir recursão completa.
  • Mais tarde, uma stack em hardware foi adicionada à implementação do microprocessador para melhorar o desempenho.

• Compartilhamento da preferência por recursão de um usuário com longa experiência em programação funcional

  • Ele sabe como converter algoritmos recursivos em iterativos, mas prefere a recursão.
  • Na maioria dos casos, a recursão é rápida o bastante, especialmente quando o compilador oferece suporte a tail recursion.
  • Ao hackear jogos de Commodore 64, tenta aprender como a programação era feita no passado.

• Relato de experiência no projeto de um multiplexador serial RS232 por volta de 1991

  • Projeto de hardware usando processador Z80, EPROM e dispositivo serial Z80-SIO.
  • Como não havia stack, usava-se um método de pré-carregar o endereço de retorno em pares de registradores para chamadas de função.

• Menção à situação antiga em que, antes de o heap poder ser expandido, os programadores precisavam considerar a distribuição possível das entradas e definir adequadamente o tamanho do armazenamento intermediário

  • Isso levava a "bugs e limitações".

• Explicação de que, numa época em que não era possível usar recursão, tail recursion era possível

  • Era preciso usar desvios normais, exceto pelo branch_with_link usado na chamada inicial.

• Explicação de como o compilador do Enhanced GNU Awk aloca variáveis globais secretas para blocos @let fora de funções

  • Essas variáveis são reutilizadas o máximo possível.

• Menção a um post que descreve o mundo do artigo "Goto considered harmful"

  • A maioria das pessoas conhece apenas o título, e o artigo defende oferecer um único ponto de entrada para sub-rotinas.
  • Às vezes escreve-se código assembly para saltar para outra sub-rotina, mas isso não significa que se queira que todo código assembly seja assim.