A função real do programa de Ada Lovelace (2018)

 (twobithistory.org)
2 pontos por GN⁺ 2024-12-17 | 1 comentários | Compartilhar no WhatsApp
  • Em 1843, Ada Lovelace publicou um procedimento para calcular números de Bernoulli destinado à Analytical Engine, que ainda não havia sido concluída, e por isso ficou no centro do debate sobre o “primeiro programa de computador”
  • A tabela publicada mostra uma etapa de um método para lidar com toda a sequência de números de Bernoulli, e o valor que Lovelace chamou de B7 corresponde, na notação moderna, ao oitavo número de Bernoulli
  • O programa da Note G era muito mais sofisticado que o exemplo sem repetição de 11 operações de Menabrea, incluindo 25 operações, repetições aninhadas e até uma notação para acompanhar valores de variáveis
  • No processo de tradução para C, ficou evidente que a quarta operação da tabela original, v5 / v4, deveria ser v4 / v5; isso provavelmente foi um erro tipográfico, mas pode ser visto como o bug mais antigo da história da computação
  • O diferencial de Lovelace está menos no título de “primeira programadora” e mais em ter entendido a criação de cartões não como uma simples tradução de expressões algébricas, mas como uma tarefa de programação que podia ser bem ou mal executada

O programa de 1843 que não pôde ser executado

  • Ao contrário da história de fundação da Microsoft, o programa de Ada Lovelace nunca teve a chance de ser executado em uma máquina real
    • Paul Allen e Bill Gates testaram um interpretador BASIC em um emulador baseado nas especificações do Intel 8080, sem ter um Altair, e depois o fizeram rodar também em um Altair real
    • Lovelace também escreveu um programa para um computador que existia apenas em descrição, mas ele não pôde ser executado porque a Analytical Engine nunca foi construída
  • O programa de Lovelace costuma ser chamado de primeiro programa de computador do mundo, mas esse status ainda é controverso
    • O debate sobre o alcance e o valor da contribuição de Lovelace continuou a ponto de Walter Isaacson chamá-lo de “minor academic specialty”
    • A questão importante aqui não é a avaliação da pessoa, mas como o programa escrito em 1843 foi projetado para funcionar
  • O programa vai além de uma simples lista de fórmulas
    • Ele usa uma estrutura equivalente a loops, ao organizar grupos de operações repetíveis
    • Introduz uma notação para acompanhar mudanças de estado das variáveis
    • Tem aspectos que lembram a experiência atual de escrever software

Números de Bernoulli e o problema das somas de potências

  • O programa de Lovelace foi projetado para calcular números de Bernoulli
  • Por trás dos números de Bernoulli havia um antigo problema matemático: calcular somas de potências
    • Os pitagóricos buscaram uma forma de calcular 1 + 2 + 3 + ... + n sem somar diretamente, obtendo a fórmula n(n+1)/2 ao encaixar dois triângulos em um retângulo
    • Arquimedes se interessou por somas da forma 1² + 2² + 3² + ... + n² e deixou uma solução com interpretação geométrica
    • Aryabhata publicou o Aryabhatiya em 499, incluindo uma fórmula para a soma de cubos
  • O problema mais geral era encontrar um método para somas da forma 1^k + 2^k + ... + n^k
    • Johann Faulhaber calculou e publicou, em 1631, fórmulas até a 17ª potência, mas não apresentou uma solução geral
    • Blaise Pascal criou um método geral em 1665, mas ele exigia conhecer antes as fórmulas de todas as somas de potências menores
  • Jakob Bernoulli deixou uma solução geral mais prática
    • Usou o triângulo de Pascal para identificar padrões nos coeficientes dos polinômios
    • Parte dos coeficientes podia ser obtida pelo triângulo de Pascal, e o restante pela propriedade de que a soma dos coeficientes é sempre 1
    • Esse segundo fator de coeficientes se tornou a sequência conhecida como números de Bernoulli
  • A descoberta de Bernoulli não transformou imediatamente o cálculo de somas de potências arbitrárias em um problema simples
    • Para calcular a soma das k-ésimas potências, era preciso conhecer os números de Bernoulli até o k-ésimo
    • Cada número de Bernoulli é calculado com base nos números de Bernoulli anteriores
    • Ainda assim, calcular uma longa sequência de números de Bernoulli era muito mais fácil do que derivar, uma a uma, as fórmulas de cada soma de potências

As duas máquinas de cálculo de Babbage

  • Charles Babbage projetou dois tipos de calculadoras mecânicas
    • A primeira foi a Difference Engine
    • A segunda foi a Analytical Engine, hoje conhecida como um computador mecânico
  • A Difference Engine não era um computador, mas uma máquina que executava apenas adição e subtração
    • Babbage estava insatisfeito com os muitos erros nas tabelas de logaritmos da época e queria produzi-las mecanicamente
    • O método das diferenças divididas de Gaspard de Prony dividia o processo de criação de tabelas de logaritmos em pequenas etapas que exigiam apenas adição e subtração
    • Polinômios podem ser usados para aproximar funções logarítmicas e trigonométricas
  • A Difference Engine correspondia cada coluna de uma tabela de diferenças a uma coluna física de engrenagens
    • Cada engrenagem representava uma casa decimal, e uma coluna inteira representava um número decimal
    • Ela tinha 8 colunas e podia tabelar polinômios de até 7º grau
    • Uma pessoa configurava os valores iniciais e então girava uma manivela para fazer a diferença constante se propagar para a próxima coluna
  • Babbage construiu e demonstrou parte da Difference Engine, mas não conseguiu concluir a máquina inteira
    • Não encontrou fabricantes capazes de produzir a quantidade necessária de engrenagens com precisão suficiente
    • Uma Difference Engine funcional só foi construída na década de 1990, quando a usinagem de precisão já era possível
  • A Analytical Engine foi concebida como uma máquina muito mais poderosa e flexível
    • Usaria colunas de engrenagens como as da Difference Engine, mas teria centenas ou mais colunas
    • Poderia ser programada com cartões perfurados, como o Jacquard Loom
    • Executaria não apenas adição e subtração, mas também multiplicação e divisão
    • Uma parte chamada “mill” seria reorganizada conforme a operação, lendo operandos das colunas de armazenamento e registrando o resultado em outra coluna

O artigo de Menabrea e as notas de Lovelace

  • Babbage conheceu em Turim o engenheiro italiano Luigi Menabrea, que mais tarde se tornaria primeiro-ministro, e Menabrea publicou em 1842 um artigo em francês explicando as possibilidades da Analytical Engine
  • Lovelace traduziu o artigo de Menabrea para o inglês em 1843
    • Lovelace conheceu Babbage em 1833, aos 17 anos, e ficou fascinada por sua Difference Engine
    • Recebeu muita educação matemática desde a infância e, mesmo depois do casamento e do nascimento de três filhos, continuou estudando matemática com Augustus de Morgan
  • O artigo de Menabrea tratava brevemente do funcionamento da Difference Engine e da superioridade da Analytical Engine
    • A Analytical Engine era apresentada como uma máquina capaz de calcular o produto de dois números de 20 dígitos em 3 minutos
    • Usava “diagrams of development” em exemplos como um sistema simples de equações lineares e a expansão do produto de dois binômios
    • Essas tabelas também eram programas no mesmo sentido do programa de Lovelace, mas eram exemplos simples, sem ramificações nem repetição
  • A tradução de Lovelace incluía notas mais longas que o texto original, e é nelas que aparecem suas principais contribuições
    • A Note A discute longamente a possibilidade de a Analytical Engine ser uma máquina capaz de executar qualquer operação matemática
    • Ela via a máquina como algo que poderia operar não apenas sobre números, mas também sobre objetos cujas relações fundamentais mútuas pudessem ser expressas pela ciência abstrata das operações
    • Por exemplo, mencionou que um dia ela talvez pudesse compor música
  • A Note G é famosa por dois motivos
    • O argumento de Lovelace de que não se poderia dizer que a Analytical Engine “pensa” foi chamado mais tarde por Alan Turing de “Lady Lovelace’s Objection”
    • Ao mesmo tempo, para mostrar que a máquina poderia lidar com problemas muito complexos, ela incluiu um programa para calcular números de Bernoulli

A estrutura real do programa da Note G

  • A tabela completa de Lovelace é uma forma estendida de “diagram of development”, e a imagem original pode ser vista aqui
  • O programa se parece mais com uma lista de operações especificadas por símbolos matemáticos comuns
    • Babbage ou Lovelace parecem não ter chegado ao ponto de criar algo como um conjunto de opcodes para a Analytical Engine
  • Lovelace explicou um método para calcular toda a sequência de números de Bernoulli até certo limite, mas o programa apresentado em tabela exemplifica apenas uma dessas etapas
    • O alvo do cálculo é o valor que Lovelace chamou de B7
    • Na notação matemática moderna, ele é o oitavo número de Bernoulli
    • A fórmula tem a forma B7 = -1(A0 + B1A1 + B3A3 + B5A5)
  • Cada termo dessa fórmula representa um coeficiente de um polinômio específico de soma de potências
    • A potência em questão é 8, e a fórmula da soma das 8ªs potências dos inteiros positivos é onde o oitavo número de Bernoulli aparece pela primeira vez
    • De B1 a B7 são diferentes números de Bernoulli segundo a indexação de Lovelace
    • De A0 a A5 são fatores de coeficientes que Bernoulli conseguia calcular pelo triângulo de Pascal
    • O programa de Lovelace usa n = 4
  • A tradução para C está disponível em um gist
    • Primeiro calcula A0 e B1A1
    • Depois entra em um loop repetido duas vezes para calcular B3A3 e B5A5
    • Após calcular cada produto, soma-o aos produtos anteriores para obter a soma total no fim

Loops, estado de variáveis e um bug antigo

  • A tradução para C mostra bem o caráter visionário do programa de Lovelace
    • O programa original não tinha exatamente um loop while, mas Lovelace criou grupos de operações e especificou em notas quando eles deveriam ser repetidos
    • A tradução para C tem dois loops while, um aninhado dentro do outro
    • v10, tanto no original quanto na tradução para C, funciona como uma variável contadora que diminui a cada repetição
  • A tabela de Lovelace facilita mais o acompanhamento das mudanças de estado do que a tabela de Menabrea
    • Há uma coluna chamada “Indication of change in the value on any Variable”
    • Ela coloca índices sobrescritos em cada variável para indicar os valores sucessivos que essa variável mantém durante a execução do programa
    • O sobrescrito 2 significa o segundo valor atribuído desde o início do programa
  • Ao ser transposto para C e executado, o programa inicialmente produziu um resultado incorreto, e a causa não estava no código traduzido, mas na tabela original
    • O “diagram of development” de Lovelace registra a quarta operação como v5 / v4
    • A ordem correta é v4 / v5
    • Isso provavelmente foi um erro tipográfico, não um erro no programa criado por Lovelace
  • Jim Randall também traduziu o programa de Lovelace para Python e apontou o mesmo bug de divisão e outros dois problemas
  • O bug menor no programa original se conecta à interpretação de que Lovelace tentou escrever algo próximo de um programa real, não apenas uma demonstração simples

Os limites do título de primeira programadora

  • Dizer que Lovelace escreveu ou publicou o “primeiro programa” não é totalmente preciso
    • Menabrea publicou “diagrams of development” um ano antes da tradução de Lovelace
    • Babbage também escreveu mais de 20 programas que não publicou
    • Dependendo do que se considera um programa, há espaço para debate
  • O programa publicado de Lovelace estava muito à frente dos que haviam sido publicados antes
    • O programa mais longo apresentado por Menabrea tinha 11 operações
    • Os exemplos de Menabrea não tinham loops nem ramificações
    • O programa de Lovelace incluía 25 operações e loops aninhados, portanto também uma estrutura de ramificação
  • Menabrea via que, quando a máquina fosse concluída, a dificuldade se reduziria à criação dos cartões, e que os cartões seriam apenas uma tradução de expressões algébricas, algo fácil de delegar a operadores com uma notação simples
  • Babbage e Menabrea se concentraram principalmente em aplicar a Analytical Engine aos problemas de cálculo matemático que lhes interessavam
  • Lovelace viu que a Analytical Engine poderia fazer muito mais do que Babbage ou Menabrea imaginavam, e entendeu que a “criação de cartões” não era uma tarefa secundária simples, mas uma tarefa de programação que podia ser bem ou mal executada

Leituras relacionadas

1 comentários

 
GN⁺ 2024-12-17
Comentários no Hacker News

  • O verdadeiro sinal de um programa não trivial é não funcionar na primeira tentativa.
    É surpreendente que, depois de Babbage se frustrar porque ainda não existia tecnologia de usinagem de precisão em massa para construir uma máquina simples, ele tenha projetado um novo sistema uma ordem de grandeza mais complexo e ido até a Itália em busca de capacidades de fabricação mais avançadas.

    • Já tive um funcionário assim.
      Quando empacava tentando fazer algo, começava criando suas próprias ferramentas; uma vez, por não gostar da fonte embutida em um tamanho de ponto muito pequeno, acabou criando sua própria fonte.
      Era o melhor engenheiro que eu conhecia, mas eu precisava ficar sempre de olho para ele não se enfiar em tocas de coelho.
    • +1 para a história de Babbage/Lovelace, mas, mesmo que as duas coisas sejam verdadeiras separadamente, é difícil dizer que Babbage escolheu o sistema mais complexo e a viagem à Itália como “o melhor caminho” por causa da falta de usinagem de precisão.
      Tim Robinson também disse que “se o Meccano dos anos 1920 existisse 100 anos antes, Babbage teria tido sucesso completo”, e eu o vejo como algo próximo de uma pessoa de software jogada no hardware por causa de ideias à frente do que era realisticamente possível.
      Além de lhe faltar senso de negócios e de planejamento de projeto — não conseguindo reduzir o escopo nem abrir mão da precisão de 10 dígitos —, ele continuava tendo ideias melhores e as perseguindo, caindo em tocas de coelho; e, como recebeu vários prêmios ainda jovem apenas pela proposta do Difference Engine, deve ter sido difícil desistir mesmo décadas depois.
      Outro grande eixo da tragédia foi o envolvimento com o governo. A aristocracia desprezava e desconfiava do governo e da política, enquanto as classes baixas desconfiavam porque o governo nunca lhes ajudara muito; mas Babbage era de classe média, exatamente o tipo de pessoa propensa a ter uma visão patriótica do governo, então parece ter pensado que deveria oferecer sua invenção à “nação” e que o governo deveria recompensá-lo por isso.
      Ele não conseguiu concluir o Difference Engine, mas perguntou ao governo se poderia implementar o melhor Analytical Engine com financiamento adicional, e o governo ficou indeciso por 20 anos. Mesmo quando o governo se ofereceu para devolver a invenção, ele recusou.
      Talvez por influência dos vários prêmios, ele também parece ter se apegado à identidade de “pessoa inteligente”; há uma anedota de que recusou uma proposta para julgar um prêmio junto com Faraday, dizendo que deveria ser o único jurado. Esse tipo de atitude provavelmente também o levou mais para ideias grandiosas de gênio do que para uma execução prática.
      The Thrilling Adventures of Lovelace and Babbage, de Sydney Padua, parece um livro muito bem pesquisado; não li muito do texto principal, mas li os apêndices em detalhe e posso recomendá-lo.
    • A afirmação de que “um programa não trivial não funciona na primeira tentativa” não é verdadeira.

  • Texto realmente excelente. Na introdução, achei impressionante como Lovelace pensou profundamente em como organizar cálculos em grupos repetíveis, inventando loops, e percebeu a importância de acompanhar o estado quando variáveis mudam, criando uma notação para indicar essas mudanças.
    Do ponto de vista de um programador, é surpreendente como o que Lovelace fazia se parece com a experiência atual de escrever software, e a explicação de que ela projetou aquilo para calcular números de Bernoulli é detalhada o suficiente para entender o que ela fez.
    Se estivesse viva hoje, imagino que estaria no fim do corredor, lutando com algum problema em Rust, e tenho a impressão de que teria uma forte preferência por linguagens de tipagem estática.

    • Seja qual for o grau de reconhecimento que Ada deva receber por suas técnicas de programação, o que sempre se destaca mais é sua capacidade de enxergar o panorama geral da computação.
      O ponto central é que ela viu que o Analytical Engine poderia atuar não apenas sobre números, mas também sobre outros objetos expressáveis em termos das relações de uma ciência abstrata das operações; por exemplo, se as relações fundamentais da harmonia e da composição fossem expressas dessa forma, ele poderia criar música elaborada de qualquer complexidade e duração.
      Ter pensado isso em 1842, um século antes do surgimento de computadores realmente programáveis, apenas a partir da descrição de um protótipo de computador mecânico, é um hack extraordinário.
    • A notação para acompanhar o estado quando variáveis mudam chamou especialmente minha atenção, porque parece muito com a forma de atribuição única estática.
      https://en.wikipedia.org/wiki/Static_single-assignment_form#Benefits
      Mesmo hoje isso está próximo de técnicas modernas; ela, de certa forma, já tinha isso 180 anos atrás.

  • É interessante a parte em que Paul Allen e Bill Gates testaram o interpretador BASIC para o Altair sem ter um Altair real, usando em um computador de Harvard um emulador criado apenas a partir da especificação do Intel 8080, e que ele funcionou corretamente na primeira execução diante de um Altair de verdade.
    Nesse caso, fico pensando se os verdadeiros heróis ocultos aqui não foram os engenheiros da Intel, que escreveram uma especificação precisa o bastante para que o software rodando em um emulador feito só a partir dela também rodasse sem problemas no hardware real.

    • Em 1976, no meu primeiro trabalho comercial de programação, adaptei um emulador 8008 escrito em Fortran para rodar como emulador 8080 em um minicomputador Data General.
      O objetivo era permitir que outro programador, que escrevia firmware 8080 para um plotter, depurasse o código; lembro que o código-fonte desse emulador vinha de algo da Intel chamado INTERP/8 8008. Pelo que vejo em textos online, parece que Allen e Gates também o usaram.

  • Acho que a parte mais legal é o trabalho real contido nas “notes” que ela anexou à tradução.
    Referência: https://upload.wikimedia.org/wikipedia/commons/c/cf/Diagram_for_the_computation_of_Bernoulli_numbers.jpg
    E https://en.wikipedia.org/wiki/Note_G
    O texto também se refere a este material que transpôs o trabalho dela para Python: https://enigmaticcode.wordpress.com/tag/bernoulli-numbers/

    • Metade do texto é sobre a Note A e a Note G

  • Ao ver o trecho dizendo que a versão em C do programa de Lovelace não parece tão estranha, exceto pelo excesso de variáveis com nomes nada úteis, fica claro que o autor nunca conheceu meus colegas

    • Isso me lembrou de quando, na aula de programação do ensino médio, meu parceiro de projeto dava às variáveis os nomes mais toscos e obscenos que lhe vinham à cabeça
      Eu nem era particularmente conservador, mas ele obviamente nunca lembrava para que servia a variável “butts”, e nunca chegou a entender por que continuava se confundindo por causa do próprio código
    • Ou então parece que nunca trabalhou com matemáticos, físicos ou engenheiros que programam. Assim que li essa frase, pensei: “típico quant”
      Meu pai, engenheiro químico, aprendeu a programar em FORTRAN; na época, os nomes de variáveis tinham de ser uma letra e no máximo dois dígitos. Depois ele aprendeu Basic, mas o código continuava mentalmente em FORTRAN, então esse hábito permaneceu
      No começo achei que fosse só coisa do meu pai, mas muito depois, trabalhando em Wall St com quants que copiavam código de Numerical Recipes, vi exatamente a mesma coisa em C

  • Considerando que Menabrea via a Analytical Engine principalmente como uma ferramenta para automatizar “cálculos longos e áridos”, liberando a capacidade intelectual de grandes cientistas para pensamentos mais elevados, é interessante ver como o discurso sobre automação é duradouro
    Hoje se diz exatamente a mesma coisa sobre LLMs

    • No fim, acho que o ponto central que diferencia o computador como ferramenta de um dispositivo de consumo é justamente a automação de “cálculos longos e áridos”

  • Fico curioso se alguém já criou uma máquina virtual para o conjunto de instruções de Babbage e executou o programa de Ada nela

  • Isso também foi discutido na época em que o artigo foi publicado
    What Did Ada Lovelace’s Program Actually Do? - https://news.ycombinator.com/item?id=17797003 - ago. de 2018, 52 comentários

  • Um pequeno desvio, mas fiquei curioso para saber como as pessoas a chamavam na época
    O nome dela era Augusta Ada King, e ela era Condessa de Lovelace; fico curioso se naquela época era comum abreviar o título e usá-lo como se fosse sobrenome, ou se isso é algo que passou a ser feito mais recentemente

    • No caso do titular do título, o Conde de Lovelace, havia a prática comum de chamá-lo apenas pelo nome do título
      Depois que William King-Noel se tornou Earl of Lovelace, passou a ser chamado de “Lovelace”, e ela provavelmente era chamada de “Lady Lovelace” em sociedade e de “Countess of Lovelace” em contextos formais

  • Ótimo texto. Foi a explicação mais clara que já li até agora sobre em que sentido Ada foi inovadora e por que merece reconhecimento