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

• Os primeiros computadores precisavam implementar chamadas de função mesmo sem stack e heap, e os compiladores gerenciavam o estado da chamada com variáveis globais ocultas correspondentes a parâmetros, endereços de retorno e variáveis locais
• O chamador armazenava os argumentos, colocava a posição de retorno em uma variável de endereço de retorno e então saltava para o ponto inicial da função; depois do cálculo, a função saltava de volta para o endereço armazenado
• Como as variáveis locais lógicas também usavam, na prática, espaço de armazenamento global, embora por fora parecessem funções, o funcionamento interno era mais próximo de memória fixa e goto
• Algumas ABIs e processadores otimizavam a passagem de argumentos e o tratamento do endereço de retorno usando registradores ou branch with link, mas as limitações básicas permaneciam
• Como o endereço de retorno da mesma função era sobrescrito por uma nova chamada, chamadas recursivas eram impossíveis, e as linguagens da época lidavam com isso proibindo recursão ou permitindo-a apenas de forma explícita

---

Como construir chamadas de função sem stack

• Nos primeiros ambientes de computação, não havia stack nem heap, que hoje consideramos óbvios
• A alocação dinâmica de memória sem heap podia ser substituída por buffers de tamanho fixo
  • Mesmo ao lidar com dados de tamanho variável, reservava-se previamente um buffer fixo grande o bastante
  • Se os dados solicitados ultrapassassem a capacidade do buffer, o programa era encerrado com um erro fatal
  • Implementações mais amigáveis permitiam definir a capacidade máxima em tempo de compilação
  • Implementações mais sofisticadas colocavam um alocador customizado sobre o buffer fixo, permitindo usá-lo como allocate e free

Convenção de chamada baseada em variáveis globais ocultas

• Para implementar chamadas de função sem stack, o compilador definia várias variáveis globais ocultas para cada função
  • Variáveis globais para cada parâmetro de entrada
  • Uma variável global que contém o endereço de retorno da função
  • Variáveis globais correspondentes às variáveis locais
• O código chamador era executado na seguinte ordem
  • Armazena os valores dos parâmetros nas respectivas variáveis globais ocultas
  • Registra a posição para onde retornar na variável de endereço de retorno da função
  • Salta com goto para a posição inicial da função
• A função lê e escreve todos os parâmetros e variáveis locais nas variáveis globais ocultas
• Ao terminar a execução, coloca o valor de retorno no registrador de valor de retorno e salta para o endereço armazenado na variável de endereço de retorno da função

Exemplo de código parecido com C transformado em código baseado em goto

• A função de exemplo add_two_values(int a, int b) pode ser transformada, sem stack, no seguinte espaço de armazenamento
  • a2v_a e a2v_b são variáveis globais para armazenar argumentos
  • a2v_c é uma variável global correspondente à variável local c
  • a2v_retaddr é uma variável global para armazenar o endereço de retorno
• O chamador sample() armazena 31415 e 2718 nas variáveis globais de argumentos, respectivamente
• Em seguida, coloca a posição resume em a2v_retaddr e salta para add_two_values
• add_two_values armazena o resultado do cálculo em return_value_register e então retorna para a2v_retaddr
• O chamador que voltou à posição resume armazena o valor do registrador de retorno em sample_x

Otimização usando registradores e branch with link

• A mesma estrutura pode ser tornada mais rápida no nível da ABI por meio de passagem por registradores
• Muitos processadores ofereciam um link register especial e a instrução branch with link
  • branch with link salva automaticamente no link register o endereço da instrução seguinte à instrução de desvio
  • O chamador pode colocar os dois primeiros argumentos em argument_register_1 e argument_register_2
  • A função chamada pode mover os valores desses registradores para suas próprias variáveis globais ocultas e usá-los
• O endereço de retorno também pode ser salvo de link_register para a variável de endereço de retorno da função
• Essa otimização mantém a estrutura básica de permitir chamadas e retornos mesmo sem stack

Por que a recursão é bloqueada

• A principal limitação desse método de chamada é a impossibilidade de chamadas recursivas
• Quando ocorre uma chamada recursiva, a variável de endereço de retorno da mesma função é sobrescrita pelo endereço de retorno da nova chamada
• Quando a chamada externa termina, a posição original para onde deveria retornar desapareceu, fazendo-a saltar para o lugar errado
• As linguagens de programação da época evitavam esse problema não oferecendo suporte a recursão
• FORTRAN inicialmente nem sequer oferecia suporte a sub-rotinas, e sub-rotinas foram adicionadas em 1958
• O suporte a recursão em FORTRAN tornou-se padrão em 1991 e, mesmo então, era necessário marcar a sub-rotina explicitamente com RECURSIVE

Código automodificável e instruções de sub-rotina nos primeiros processadores

• Alguns compiladores usavam código automodificável de forma mais engenhosa
  • O campo de endereço dentro da instrução de salto no fim da função efetivamente fazia o papel de variável de endereço de retorno
• Esse método podia ser não apenas um truque simples, mas uma necessidade prática
  • Alguns processadores talvez não oferecessem suporte a saltos indiretos
• Depois que a utilidade das sub-rotinas foi reconhecida, vários processadores adicionaram instruções de chamada dedicadas
  • Armazenavam o endereço de retorno na primeira palavra da sub-rotina
  • A execução real começava na segunda palavra
  • Para retornar, executava-se um salto indireto por meio do rótulo de início da sub-rotina
• No exemplo em assembly, bsr add_two_values armazena o endereço de retorno na primeira palavra de add_two_values e passa a executar a partir da instrução real após o nop sacrificial

[GN⁺]

Comentários do Hacker News

• Sobre esse tema, The Art of Computer Programming foi realmente excelente
  À primeira vista parece antiquado, mas há uma quantidade enorme de algoritmos para lidar com arrays ou estruturas de dados que mudam dinamicamente, da época anterior ao heap e à pilha
  O livro avança passo a passo até garbage collection e implementação de listas em Lisp, e traz exatamente aquele conhecimento enciclopédico que se espera de Knuth
  Um exemplo de que gosto especialmente é a forma como dois arrays compartilham dinamicamente um mesmo espaço. Se um array cresce para a frente a partir de location#0 e o segundo cresce para trás a partir de location#End, o espaço alocado estaticamente é dividido de maneira eficiente
  Também é possível estender para um número arbitrário de arrays, mas, chegando a esse ponto, é melhor simplesmente usar Malloc e Realloc, e a própria técnica já fica bem próxima de uma rotina parecida com malloc

  • Alguns processadores de texto de computadores de 8 bits funcionavam assim. O documento ocupava toda a RAM disponível; o texto antes do cursor ficava no início da RAM, e o texto depois do cursor ficava no fim da RAM
    Inserções e colagens não precisavam deslocar dados, mas a navegação precisava. Mesmo assim, funcionava bem
  • Na maioria das arquiteturas de conjunto de instruções e ABIs, a pilha cresce de endereços altos para baixo, então, em sistemas de memória pequena e de thread única, essa técnica permitia dividir de forma flexível a memória entre o heap e a pilha
  • A alocação de recursos por aplicativo do MacOS antigo é explicada exatamente dessa forma. Cada app tinha um requisito mínimo de RAM e um requisito preferencial de RAM, e, quando executado, ocupava um slot do tamanho preferencial
    Se essa quantidade não estivesse disponível, recebia menos que o preferido; se nem o mínimo pudesse ser obtido, a execução falhava
    Pelo que lembro, o sistema colocava o heap e as bibliotecas na parte inferior daquele pedaço de RAM física, e a pilha na parte superior
    Por volta do System 8, uma camada de virtualização foi adicionada, tornando essa abordagem menos necessária; na época do MacOS X, como ele usava memória paginada como outros sistemas, esse tipo de malabarismo deixou de ser necessário
    Ainda assim, é divertido lembrar que esse “truque estranho” de The Art of Computer Programming já foi a forma de alocar RAM para vários apps rodando ao mesmo tempo
  • Um fato curioso: o Itanium tinha duas pilhas no total, uma pilha para push/pop manual e outra que percorria circularmente o arquivo de registradores
    Uma crescia para cima e a outra para baixo. Era uma arquitetura fascinante, mas acabou não entregando o desempenho prometido
  • O formato em disco do SQLite também usa uma técnica de arrays parecida para armazenar o conteúdo das páginas de nós folha de B-tree de tabelas
    Dentro de uma página de tamanho fixo, o array de offsets cresce para a frente, e o array de valores de linhas de comprimento variável cresce para trás a partir do fim. Pelo que entendo, ao excluir uma linha, podem surgir buracos no array de trás
    Como a documentação cita TAOCP para a própria estrutura de B-tree, não seria surpresa se isso tivesse sido uma inspiração direta

• Colocar funções recursivas no ALGOL foi algo bastante controverso e continua sendo uma história interessante: https://vanemden.wordpress.com/2014/06/18/how-recursion-got-...

  • Posts relacionados:
    How recursion got into programming: intrigue, betrayal, and advanced semantics - https://news.ycombinator.com/item?id=33123916 - outubro de 2022, 8 comentários
    How Recursion Got into Programming (2014) - https://news.ycombinator.com/item?id=23061881 - maio de 2020, 47 comentários
    How recursion got into Algol 60: a comedy of errors - https://news.ycombinator.com/item?id=10131664 - agosto de 2015, 124 comentários
    How recursion got into programming: a comedy of errors - https://news.ycombinator.com/item?id=8073361 - julho de 2014, 108 comentários

• Interpretador Forth para a máquina SUBLEQ (https://github.com/howerj/subleq) e um interpretador para uma máquina bit-serial (https://github.com/howerj/bit-serial) foram escritos, mas nenhuma das duas tinha a pilha de chamadas de função necessária para Forth
  A SUBLEQ nem permite load/store indiretos, então, para fazer qualquer coisa minimamente complexa, é preciso usar código automodificável
  A abordagem foi criar, em ambas as máquinas, uma máquina virtual capaz de desempenhar essa função e também incluir multithreading cooperativo
  Se for preciso um heap, ele é escrito em Forth; o conjunto de palavras de ponto flutuante também é escrito em Forth. Muitos MCUs ainda não têm instruções de ponto flutuante, e isso pode ser tratado por chamadas a funções de software que as implementam
  Outros compiladores provavelmente usaram uma abordagem parecida, embora não tenham sido mencionados. Alguns interpretadores BASIC também implementavam uma VM e a usavam como alvo; P-Code é parecido

  • O TI-99/4A tinha apenas 256 bytes, ou seja, 128 palavras, de RAM principal diretamente acessível pela CPU
    A maior parte da memória básica do sistema era RAM de vídeo, e precisava ser acessada por um procedimento bem trabalhoso de dar poke/peek nos registradores do chip de vídeo
    O chip de vídeo mantinha um ponteiro de memória atual com autoincremento, de modo que, em leituras ou escritas sequenciais, o ponteiro aumentava em 1; mas o simples fato de a maior parte da memória do sistema só poder ser acessada dessa forma já dificultava escrever programas grandes
    Por isso a TI criou uma máquina abstrata chamada GPL, que tornava esse acesso à RAM de vídeo mais natural. Só que, por ser interpretada em cima do TMS9900, era mais lenta que código nativo; e a CPU só podia acessar a RAM do chip de vídeo quando o chip não estava fazendo o scanout da tela, como nos períodos de retraço horizontal/vertical, o que a tornava ainda mais lenta
    Como o código BASIC e as variáveis também ficavam todos nessa memória de vídeo, fica óbvio em que foi escrito o interpretador BASIC do TI-99/4A. Não era nada rápido
    A parte interessante é que o TMS9900 não tinha registradores de uso geral reais. Os registradores de espaço de trabalho WR0~WR15 ficavam em algum lugar da memória, e o registrador de ponteiro de espaço de trabalho WP apontava para eles
    Os únicos registradores físicos da CPU eram três: PC, WP e o registrador de status. Como resultado, era possível fazer uma forma bem primitiva de janelas de registradores; ao desviar com a instrução BLWP, um novo conjunto de “registradores” em outra posição da memória era ativado, e o endereço de retorno era salvo no novo espaço de trabalho
    Tenho falado bastante do TI-99/4A ultimamente porque estou fazendo, como projeto pessoal, um assembler para essa máquina
  • Vi esses trabalhos enquanto aprendia e me aprofundava em Forth e Subleq. Gostei de ler a abordagem e queria comprar o livro, mas a Amazon diz que não dá. Fico curioso se haverá uma reimpressão
  • Eu ia falar de subleq, mas lá até escrever um simples “Hello world” é realmente difícil

• É verdade que alguns processadores armazenavam o endereço de retorno na palavra imediatamente antes da primeira instrução da sub-rotina, e o PDP-8 fazia isso
  A evolução do PDP-8 também pode ser vista como uma jornada de suporte de hardware à recursão
  No início, a instrução JMS enfiava o endereço de retorno na primeira palavra da função. Muitas vezes o chamador colocava os argumentos depois da instrução JMS, e o chamado lia os argumentos por offsets em relação à instrução de retorno, incrementando-a a cada vez para que o endereço de retorno voltasse a apontar para a posição do código
  Depois, tornou-se bastante comum criar uma pilha simples usando uma das posições de autoincremento. O PDP-8 tinha 8 posições de memória que eram incrementadas sempre que usadas como ponteiros, e o prólogo/epílogo das funções gerenciava essa pilha diretamente, permitindo recursão completa
  Mais tarde, implementações em microprocessador como o Harris 6120 adicionaram uma pilha em hardware, melhorando o desempenho

  • O Librascope LGP-30 de 1956 tinha a instrução R, isto é, uma instrução de armazenamento de endereço de retorno
    Essa instrução salvava o PC+1, já incrementado, na parte de endereço da instrução no local de destino; por convenção, esse destino era uma instrução de desvio incondicional logo antes do início da sub-rotina
    Depois da instrução R, colocava-se uma instrução U de desvio incondicional para a sub-rotina
    A sub-rotina retornava desviando para o endereço imediatamente anterior a ela, onde havia um desvio incondicional de volta para logo depois do ponto de chamada
    Sem uma convenção de chamada mais avançada, recursão era impossível. E todos os códigos de instrução da linguagem assembly tinham uma só letra
  • IBM 1800, IBM 1130 e muitas máquinas daquela época também faziam isso. Máquinas com registradores suficientes, como a linha Xerox Sigma, podiam evitar essa prática

• Em programas escritos para AVR-8, usar a convenção de chamada de C às vezes parece uma loucura
  Escrevendo em assembly, dá para manter variáveis de loop internas o tempo todo no grande arquivo de registradores, ou então usar os métodos descritos no texto
  Também é boa a ideia de “colorir” funções nesse tipo de app. Se você sabe que uma função vermelha e uma função verde não ficam ativas ao mesmo tempo, pode reutilizar as variáveis locais ou os parâmetros das duas

  • Ao trabalhar em ambientes restritos, especialmente quando se está acostumado às conveniências de um sistema operacional de desktop, o uso de pilha em C pode não ser intuitivo
    Em um projeto de uma base de código para microcontrolador em que entrei no passado, vários desenvolvedores passaram semanas rastreando bugs difíceis de capturar em vários subsistemas
    Quando o código era movido, os bugs se moviam junto. Depois de investigar um pouco e colocar armadilhas, consegui encontrar os pontos do código em que a pilha de chamadas ficava profunda demais e sobrescrevia outras estruturas de dados

• Quando comecei a aprender programação, fui forçado a programar exatamente desse jeito. Não foi nos anos 1970, foi em 2001
  Porque minha primeira experiência com programação foi a “linguagem” de scripting semigráfica oferecida pela ferramenta de desenvolvimento de jogos RPG Maker 2000
  Se você nunca viu scripting no RM2K, imagine uma mistura de Scratch com o modo Paredit do Emacs. Ex.: https://forums.rpgmakerweb.com/data/attachments/21/21958-f89...
  Parece texto, mas não dá para editar como texto; só como blocos com diálogos de propriedades anexados
  Naturalmente, a linguagem de scripting do RPG Maker não tinha nada sofisticado como uma stack. Se você precisava de uma sub-rotina reutilizável, tinha de alocar variáveis globais secretas para parâmetros, e não havia reentrância
  Pensando em retrospecto, acho que, com teimosia suficiente, daria para implementar tanto registradores quanto uma stack de runtime dentro do RPG Maker 2000
  No começo parece fácil. Dá para criar “registradores” falsos, como a zero page do 6502, e também criar uma stack com acesso indireto a variáveis (https://rpgmaker.net/tutorials/523/)
  O problema é que o RM2K tem concorrência na forma de scripts de “parallel process”. Se processos paralelos usam esse tipo de abstração, “threads” diferentes saem sobrescrevendo o estado umas das outras
  Portanto seriam necessárias várias zero pages e stacks para cada “núcleo virtual”, e seria preciso alocar/vincular/escalonar um núcleo virtual para cada script paralelo. Ou seja, cada script teria de ter de algum modo um stack pointer que só ele conhecesse
  Para tornar isso estável mesmo com race conditions, normalmente seria necessário algo como um mutex
  Considerando a persistência dos desenvolvedores de jogos em RPG Maker, imagino que alguém tenha encontrado uma forma de enganar algum recurso de runtime para se comportar como um mutex, mas, sinceramente, tenho até medo de saber o que fizeram na prática

  • Eu também comecei com rpgmaker, e ler isso me deu uma nostalgia enorme
    Lembro de baixar no rpgmaker.net um jogo que implementava um custom battle system. Era uma implementação que substituía todo o sistema de batalha embutido usando técnicas como as que você descreveu
    Quando abri no editor para ver como funcionava, fiquei completamente impressionado. Havia centenas de “variáveis” e, se não me falha a memória, elas só aceitavam i64; também havia centenas de “switches”. Os switches eram booleanos
    Na época, eu não tinha nenhuma noção de stack, heap ou chamadas de função
    Nem consigo imaginar quanta energia deve ter sido necessária para criar aquilo e depois manter/debugar

• Se bem me lembro, ao escrever programas BASIC no ZX81, eu fazia isso de um jeito próximo de “sem stack”
  1 GOTO 30
10 LET C = A + B
20 RETURN
30 LET A = 1
40 LET B = 2
50 GOSUB 10
60 LET A = C
70 LET B = 3
80 GOSUB 10
90 PRINT C
RUN
6
  Na prática, eu fazia manualmente o trabalho que o compilador faz no texto. Os números de linha eram endereços de memória, e as variáveis ocultas não estavam ocultas para mim. Porque eu era o compilador
  A única coisa que o interpretador fazia por mim era armazenar o endereço de retorno do GOSUB
  Dito isso, o código pode estar sintaticamente errado ou minha memória pode estar distorcida. 40 anos é bastante tempo, mas a ideia geral está correta
  Além disso, o processador Z80 dentro da máquina tinha recursos de gerenciamento de stack. O interpretador BASIC era realmente simples, mas tinha desculpa: havia apenas 1 KB de RAM e 8 KB de ROM contendo o SO, o interpretador, tudo

  • Isso ainda usa pelo menos uma stack de chamadas. GOSUB armazena o número da linha, ou alguma outra referência, que RETURN vai consultar; e, se você aninha chamadas GOSUB, precisa lembrar vários pontos de retorno, então é necessária alguma forma de stack
    Mas alguns BASICs tinham apenas um array fixo de ponteiros de retorno e um índice da posição atual, em vez de uma stack de uso geral; por exemplo, a profundidade de chamada podia ser fixa em 7. Do ponto de vista do programador, funciona como uma stack de chamadas
    Claro, não é uma stack “de verdade”, com variáveis locais/parâmetros, como alguém poderia esperar ao ouvir a palavra stack
    No ambiente padrão do BBC BASIC, dava para fazer uma demonstração divertida mostrando o que acontece com chamadas aninhadas, incluindo recursão. Se você colocasse a posição da stack no topo da memória de vídeo e evitasse desenhar algo ali, dava para ver a stack crescendo conforme o trabalho avançava
    A resolução da tela era baixa, então um endereço de retorno de 2 bytes aparecia como 8 pixels grossos nos modos de tela 1 ou 5. No modo 2 eram 4, mas com cores piscantes, o que era pior; e nos modos 0, 3, 4, 6 eram 16, mas olhar bit a bit era mais difícil de entender do que a repetição de 8 cores

• Antes de existir uma heap expansível arbitrariamente, os programadores exerciam pelo menos um pouco de julgamento de engenharia
  Porque era preciso considerar a distribuição probabilística das entradas e dimensionar adequadamente todo o armazenamento intermediário
  Foi assim que surgiram os “BUGS AND LIMITATIONS”

  • Esse jeito antigo ainda é atual, dependendo do que você está fazendo. Em hard real-time, quase não se usa memória dinâmica, principalmente porque o tempo de alocação/liberação de memória não é determinístico
    Então tudo é alocado estaticamente em tempo de compilação, e você precisa saber quanta memória a entrada vai consumir
    Mas saber o limite superior do consumo de memória também era algo normal para programadores de aplicação no passado. Afinal, você nunca quer ficar sem memória
    Hoje em dia parece que simplesmente deixam o uso de memória no modo YOLO
  • Historicamente, um dos grandes objetivos do GNU também era isso. Ele buscava eliminar limites artificiais dos utilitários centrais
    Por exemplo, foi uma grande melhoria em relação a restrições como o sed ter um comprimento máximo de comando finito e curto
  • Na verdade, o erro foi ter feito humanos fornecerem entradas a programas de computador

• Fiz programação funcional por tanto tempo que é realmente difícil imaginar como escrever código sem recursão
  Tecnicamente, sei como transformar algoritmos recursivos em algoritmos iterativos, e já fiz isso em ambientes com grandes restrições de recursos, mas não gosto
  Normalmente acho que a versão recursiva é mais bonita e, em 99% dos casos, rápida o bastante. Se o compilador dá suporte a recursão de cauda, chega perto de 100%, mas na maioria dos trabalhos mais interessantes você acaba tendo que manter a pilha manualmente de qualquer forma
  Às vezes faço esse tipo de coisa de propósito, para aprender como faziam antes de eu nascer. Tenho brincado de vez em quando com jogos do Commodore 64, e isso me faz perceber muito o luxo que é hoje estar acostumado a hardware rápido, barato e fácil de usar

  • Os conjuntos de instruções de hoje são definitivamente muito mais úteis
    Para fazer recursão nessas máquinas antigas, era preciso criar manualmente um mecanismo de pilha e, mesmo assim, ainda havia problemas a resolver, porque basicamente não havia outro jeito padrão de fazer isso além de usar armazenamento global
    Vivi aquela época, mas não recomendaria a ninguém

• No recurso @let do Enhanced GNU Awk, blocos @let fora de funções, por exemplo dentro de blocos BEGIN ou END, faziam o compilador alocar variáveis globais secretas
  Essas variáveis são reutilizadas entre blocos tanto quanto possível
  $ ./gawk --dump-variables 'BEGIN { @let (a, b, c = 1) { } }'
$ cat awkvars.out
$let0001: untyped variable
$let0002: untyped variable
$let0003: 1
ARGC: 1
ARGIND: 0
ARGV: array, 1 elements
BINMODE: 0
[ .. snip many ]
  https://www.kylheku.com/cgit/egawk/about/

  • Esse site não funciona pelo meu ISP. Nem ping funciona, e nc -z 104.37.63.7 443 também não
    Atualização: parece que a infraestrutura de segurança está quebrada. Nem sei o que é isso e também não uso Twitter. Verificando o AS, é Google Fiber
    E eu preferiria que não fizessem doxxing comigo