O que o programa Ada Lovelace realmente fez?

O episódio Microsoft Founding é um dos mais famosos da história do computador. Em 1975, Paul Allen voou para Albuquerque para demonstrar o intérprete BASIC que ele e Bill Gates haviam escrito para o microcomputador Altair. Como eles não tinham um computador Altair funcionando, eles testaram seu intérprete usando um emulador escrito por eles que rodava no sistema de computadores de Harvard. O emulador era baseado apenas nas especificações publicadas do processador Intel 8080. Quando Allen finalmente lançou o intérprete em um computador Altair real - na frente da pessoa que eles esperavam que comprasse seu software - ele nem sabia se o programa funcionaria. Ela ganhou. No mês seguinte, Allen e Gates fundaram formalmente a nova empresa.

Mais de cem anos antes do intérprete do BASIC Allen e Gates, Ada Lovelace escreveu e publicou um programa de computador. Ela também escreveu um programa para um computador, que sabia apenas pela descrição. Mas seu programa, diferentemente do intérprete BASIC, nunca foi executado porque o computador para o qual foi escrito nunca foi construído.

Lovelace é frequentemente chamado o primeiro programa de computador do mundo. Mas nem todos concordam que deve ser chamado assim. O legado de Lovelace acaba sendo um dos tópicos mais quentes da história da computação. Walter Isaacson escreveu que o debate sobre a extensão e o mérito de suas contribuições é de "pouca importância acadêmica". Inevitavelmente, a disputa é alimentada pelo fato de Lovelace ser uma mulher. Os historiadores citaram todos os tipos de evidências para provar que as honras prestadas a ela são consistentes com o caso ou, inversamente, não merecidas. Mas eles gastam muito menos tempo explicando os detalhes técnicos de seu trabalho publicado, o que é uma pena, pois são os detalhes técnicos que representam a parte mais interessante desta história. Quem não estaria interessado em saber como o programa escrito em 1843 deve funcionar?

Honestamente, o programa Lovelace é difícil de explicar aos habitantes da cidade. Mas são os meandros de seu programa que a tornam tão notável. Ela merece ser chamada de primeira programadora, ou não, seu programa foi gravado com tanta precisão que superou tudo o que era antes. Ela pensou cuidadosamente em quais operações podem ser combinadas em grupos que podem ser repetidos - inventando assim um ciclo. Ela percebeu o quão importante era acompanhar o estado das variáveis ​​variáveis ​​e criou um registro que refletia essas mudanças. Como programador, fiquei impressionado com o quanto o trabalho de Lovelace se assemelha à experiência de escrever software hoje.

Então, vamos dar uma olhada no programa Lovelace. Ela o projetou para calcular os números de Bernoulli . Para entender o que é, você precisa voltar alguns milênios no passado, até o início de um dos problemas mais antigos da matemática.

Soma de Graus

Os pitagóricos viviam às margens do mar Mediterrâneo e adoravam números. Um de seus hobbies era fazer triângulos de seixos.



Uma pedra, seguida por uma fileira de duas pedras, juntas formam um triângulo de três pedras. Adicione outra linha de três pedras para fazer um triângulo de seis pedras. Este procedimento pode ser continuado, sempre que adicionar uma linha com o número de pedras aumentando em um. Um triângulo de seis linhas contém 21 pedras. E quantas pedras estarão no triângulo de 423 linhas?

Os pitagóricos estavam procurando uma maneira de calcular a soma da próxima linha sem somar:

1 + 2 + 3 + ⋯ + n

Como resultado, eles perceberam que, se você colocar dois triângulos do mesmo tamanho um ao lado do outro para formar um retângulo, poderá encontrar a área do retângulo e dividi-lo em dois para obter o número de pedras em cada um dos triângulos:

1 + 2 + 3 + ⋯ + n = n (n + 1) / 2

Arquimedes estudou um problema semelhante. Ele estava interessado na seguinte sequência:

1 ² +2 ² +3 ² + ⋯ + n ²

Pode ser imaginada como uma coluna de quadrados cada vez maiores (constituídos por pequenos cubos), posicionados um sobre o outro na forma de uma pirâmide. Arquimedes queria saber se havia uma maneira fácil de dizer quantos cubos seriam necessários para criar uma pirâmide com, digamos, 423 níveis. Ele escreveu uma solução para o problema, que também permite uma interpretação geométrica.



Três pirâmides podem ser feitas juntas para formar um prisma retangular, em uma extremidade da qual existe uma pequena saliência de um cubo de altura. Essa saliência é um triângulo que obedece às mesmas regras que os triângulos de pedra dos pitagóricos. Portanto, o volume da figura inteira é dado pela seguinte equação:

3 (1 ² +2 ² +3 ² + ⋯ + n ² ) = (n + 1) n ² + (1 + 2 + 3 + ⋯ + n)

Substituindo a equação de Pitágoras pela soma dos primeiros n números inteiros, e tendo realizado algumas operações algébricas, obtemos:

1 ² +2 ² +3 ² + ⋯ + n ² = n (n + 1) (2n + 1) / 6

Em 499, o matemático e astrônomo indiano Ariabhata publicou seu trabalho, conhecido como Ariabhatia, que forneceu uma fórmula para calcular a soma dos cubos:

1 ³ +2 ³ +3 ³ + ⋯ + n ³ = (1 + 2 + 3 + ⋯ + n) ²

A fórmula para a soma dos primeiros n números inteiros positivos até o quarto grau foi publicada apenas 500 anos depois.

Nesse momento, você pode ter uma pergunta - existe algum método universal para calcular a soma dos primeiros n números inteiros elevados à potência de k? Os matemáticos também estavam interessados ​​nisso. Johan Faulhaber, um matemático alemão, um pouco avançado em numerologia, conseguiu derivar fórmulas para a soma de números inteiros até o 17º grau, publicando-as em 1631. Mas levou muitos anos e ele não deu uma solução geral. Blaise Pascal finalmente chegou a um método generalizado em 1665, que, no entanto, dependia de contar a soma de números inteiros elevados a graus anteriores. Por exemplo, para calcular a soma dos primeiros n números inteiros positivos aumentados para o sexto grau, você primeiro aprendeu como calcular a soma dos primeiros n números inteiros positivos aumentados para o quinto grau

Uma solução generalizada mais prática foi dada em um artigo publicado postumamente pelo matemático suíço Jacob Bernoulli , que morreu em 1705. Bernoulli começou derivando fórmulas para calcular as somas dos primeiros n números inteiros positivos aumentados no primeiro, segundo, terceiro e quarto graus. Ele os escreveu na forma de polinômios:

1 + 2 + 3 + ⋯ + n = 1 / 2n ² + 1 / 2n

1 ² +2 ² +3 ² + ⋯ + n ² = 1 / 3n ³ + 1 / 2n ² + 1 / 6n

1 ³ +2 ³ +3 ³ + ⋯ + n ³ = 1 / 4n ⁴ + 1 / 2n ³ + 1 / 4n ²

Usando o triângulo de Pascal , Bernoulli percebeu que esses polinômios seguem um padrão previsível. De fato, Bernoulli dividiu os coeficientes de cada termo em dois fatores, um dos quais ele poderia determinar usando o triângulo de Pascal e o outro para derivar de uma propriedade interessante pela qual todos os coeficientes no polinômio totalizavam um. Não foi difícil entender qual expoente colocar para cada membro, pois eles também seguiram um padrão previsível. Os fatores de cada coeficiente, que tiveram que ser calculados de acordo com a regra "a soma é igual a um", formaram uma sequência que ficou conhecida como números de Bernoulli.

A descoberta de Bernoulli não significava que a soma dos primeiros n números inteiros positivos aumentados para qualquer potência agora pudesse ser calculada trivialmente. Para calcular a soma dos primeiros n números inteiros positivos elevados à potência de k, foi necessário descobrir todos os números de Bernoulli até o k-ésimo. E cada número de Bernoulli poderia ser calculado apenas conhecendo todos os números anteriores. Mas calcular uma longa sequência de números de Bernoulli era incomparavelmente mais fácil do que contar todas as somas de números aumentados; portanto, a descoberta de Bernoulli foi um grande avanço para a matemática.

Babbage

Charles Babbage nasceu em 1791, quase cem anos após a morte de Bernoulli. Eu sempre tive uma idéia dele que ele desenvolveu, mas não construiu, um computador mecânico. Mas eu nunca entendi como esse computador deveria funcionar. Como se viu, as idéias básicas são muito fáceis de entender. O programa Lovelace deveria funcionar em uma das máquinas Babbage, portanto, precisamos fazer outra pequena digressão e conversar sobre como essas máquinas funcionavam.

Babbage criou dois computadores mecânicos separados. A primeira foi chamada de máquina da diferença . Antes da invenção das calculadoras de bolso, as pessoas contavam com logaritmos para calcular o produto de grandes números. As grandes tabelas logarítmicas não são tão difíceis de compilar, mas o número de cálculos necessários para compilá-las levou ao fato de que, na época do Babbage, elas geralmente continham erros. Irritado com isso, Babbage decidiu criar uma máquina capaz de criar mecanicamente tabelas de logaritmos sem cometer erros.

A máquina da diferença não era um computador, porque só podia adicionar e subtrair. Ela usou o método inventado pelo matemático francês Gaspard de Prony , que quebrou o processo de construir uma mesa em pequenos passos. Essas etapas exigiam apenas adição e subtração, o que significava que um pequeno exército de pessoas sem habilidades matemáticas poderia ser usado para construir a mesa. O método de Proni, conhecido como método das diferenças divididas , pode ser usado para compilar uma tabela para qualquer polinômio. E os polinômios já poderiam ser usados ​​para o cálculo aproximado das funções logarítmicas e trigonométricas.

Para imaginar como esse processo funcionou, considere a seguinte função polinomial simples:

y = x ² +1

O método da diferença de divisão encontra a diferença entre os valores y sucessivos para diferentes valores x. Depois, existem as diferenças entre essas diferenças e, possivelmente, as diferenças entre as últimas diferenças, até que apareça uma diferença constante. Essa diferença pode ser usada para obter o próximo valor polinomial através da adição.

Como o polinômio indicado possui apenas o segundo grau, podemos encontrar a diferença constante após apenas duas colunas de diferenças:

x	y	Dif. 1	Dif. 2
1	2
2	5	3
3	10	5	2
4	17	7	2
5	?	?	2
...	...	...	...

Agora, sabendo que a diferença constante é 2, podemos encontrar o valor de y quando x é 5, usando uma adição. Adicionando 2 e 7, o último valor na coluna Diff 1, obtemos 9. Adicionando 9 e 17, o último valor na coluna y, obtemos 26 - nossa resposta.

A máquina de diferença Babbage para cada coluna de diferença da tabela tinha sua própria coluna física com engrenagens. Cada engrenagem representava uma posição decimal e a coluna inteira representava um número decimal. A máquina de diferença possuía oito colunas com engrenagens, para poder compilar tabelas polinomiais até o sétimo grau. As colunas foram inicialmente configuradas para valores que coincidem com a linha inicial da tabela de diferenças, calculada com antecedência. O operador teve que girar o eixo de manivela, o que causou uma constante diferença na movimentação da máquina quando os valores armazenados em cada uma das colunas foram adicionados ao seguinte.

Babbage conseguiu construir uma pequena parte da máquina da diferença e usá-la para demonstrar suas idéias nas festas. Mas, mesmo tendo gastado tanto dinheiro que seriam suficientes para construir dois grandes navios de guerra, ele não conseguiu terminar o carro. No início do século 18, Babbage não encontrou ninguém que pudesse produzir a quantidade certa de equipamento para ele com a precisão certa. A versão de trabalho da máquina de diferença foi construída apenas na década de 1990, após o advento de máquinas de alta precisão.


Como resultado, Babbage perdeu o interesse na máquina de diferença, percebendo que você pode criar uma máquina muito mais poderosa e flexível. Sua " máquina analítica " é hoje conhecida como o computador mecânico de Babbage. A máquina analítica baseava-se nas mesmas colunas de engrenagens da diferença, mas se a última tivesse apenas oito colunas, a analítica deveria ter várias centenas. Uma máquina analítica pode ser programada com cartões perfurados, como um tear jacquard , e pode se dividir e multiplicar, não apenas adicionar e subtrair. Para executar uma dessas operações, uma parte da máquina chamada “moinho” se reconstruiria na configuração desejada, leria operandos de outras colunas usadas para armazenar dados e depois gravaria o resultado em outras colunas.

Babbage chamou de máquina analítica porque era poderosa o suficiente para fazer algo semelhante à análise analítica. A máquina de diferença poderia produzir tabelas polinomiais, mas a máquina analítica poderia calcular, por exemplo, os coeficientes de multiplicação polinomial de outra expressão. Era uma máquina incrível, mas o governo britânico tomou uma decisão sábia em rejeitar o pedido de financiamento. Então Babbage foi para o exterior, para a Itália, para tentar encontrar apoio lá.

Notas do tradutor

Em Turim, Babbage conheceu um engenheiro italiano e o futuro primeiro-ministro Luigi Federico Menabrea. Ele convenceu Menabrea a escrever uma visão geral dos recursos da máquina analítica. Em 1842, Menabrea publicou um trabalho sobre esse assunto em francês. No ano seguinte, Lovelace publicou uma tradução do trabalho de Menabrea para o inglês.

Lovelace, então conhecido como Ada Byron, conheceu Babbage em uma festa em 1833, quando ela tinha 17 e ele 41. Lovelace foi atingido pela máquina de diferença de Babbage. Mas ela conseguiu descobrir como isso funciona, pois na infância ela aprendeu ativamente matemática. Sua mãe, Anabella Milbank, decidiu que o sólido fundamento matemático da educação de sua filha a desencorajaria da natureza selvagem e romântica que seu pai, Lord Byron , um famoso poeta, possuía. Após o encontro em 1833, Lovelace e Babbage permaneceram no círculo social geral e frequentemente correspondiam.

Ada Byron casou-se com William King em 1835. King tornou-se mais tarde conde de Lovelace, após o que Ada se tornou condessa de Lovelace. E mesmo tendo dado à luz três filhos, ela continuou estudando matemática, tendo como professora Augustus de Morgan, que descobriu as leis de Morgan . Lovelace reconheceu imediatamente o potencial da máquina analítica e concordou prontamente em trabalhar com ele para promover essa ideia. Sua amiga a convidou para traduzir o trabalho de Menabrea para um público em inglês.

O documento continha uma breve descrição da operação de uma máquina de diferença e, em seguida, foi mostrado até que ponto a máquina analítica a ultrapassaria. A máquina analítica deveria ser tão poderosa que poderia "formar o resultado da multiplicação de dois números, cada um dos quais composto por vinte caracteres, em apenas três minutos". Menabrea deu outros exemplos da possibilidade de uma máquina, demonstrando como resolveria um sistema simples de equações lineares e decomporia o resultado da multiplicação de dois binômios. Nos dois casos, Menabrea apresentou o que Lovelace chamou de "gráficos de desenvolvimento", descrevendo a sequência de operações necessárias para calcular a resposta correta. Estes eram programas, no mesmo sentido que o programa Lovelace era um programa, e foram publicados um ano antes de seu trabalho. Mas, como veremos, os programas de Menabrea eram apenas exemplos do possível. Todos eles eram triviais no sentido de que não exigiam nenhuma ramificação ou ciclo.

Lovelace acrescentou algumas notas à tradução do trabalho de Menabrea e, no total, eles se revelaram mais longos que o trabalho original. Foi lá que ela fez sua principal contribuição para a computação. Na nota A, que Lovelace fez na descrição inicial da máquina analítica, ela explicou em detalhes, e às vezes liricamente, que essa máquina seria capaz de executar operações matemáticas arbitrárias. Ela previu que uma máquina como essa não se limitaria a trabalhar com números e seria capaz de processar qualquer objeto "cuja interação fundamental mútua possa ser expressa pela ciência abstrata das operações e que possa ser adaptada aos registros operacionais e ao mecanismo da máquina". Ela acrescentou que um dia essa máquina poderá, por exemplo, compor músicas. Essa previsão foi ainda mais notável, porque o próprio Menabrea considerou essa máquina apenas uma ferramenta para automatizar "cálculos longos e chatos" que liberariam as capacidades intelectuais de cientistas brilhantes para pesquisas mais avançadas. A previsão milagrosa de Lovelace, como mostra a nota A, é um dos principais motivos pelos quais honramos hoje.

Outra nota famosa é a nota de G. Lovelace, começando por afirmar que, apesar de suas impressionantes capacidades, a máquina analítica não pode ser "pensada". É esta nota de rodapé que Alan Turing mais tarde chamará de "objeção de Ada Lovelace". No entanto, Lovelace continua, o carro é capaz de coisas incríveis. Para demonstrar a capacidade de lidar com problemas mais complexos, Lovelace ofereceu seu programa para calcular números de Bernoulli.

Seu texto completo, na forma de um "gráfico de desenvolvimento" expandido, cujo formato Lovelace descreve na Nota D, pode ser visto aqui . Esta é essencialmente uma lista de operações indicadas por símbolos matemáticos. Parece que Babbage ou Lovelace chegaram ao ponto de desenvolver um conjunto de códigos operacionais para a máquina analítica.

Embora Lovelace tenha descrito um método para calcular uma sequência completa de números de Bernoulli até um certo limite, seu programa mostrou apenas uma etapa desse processo. Ela contou o número que chamou de B7, conhecido pelos matemáticos modernos como o oitavo número de Bernoulli. Portanto, seu programa resolveu a seguinte equação:

B7 = −1 (A ₀ + B ₁ A ₁ + B ₃ A ₃ + B ₅ A ₅ )

Aqui, cada termo representa um coeficiente em uma fórmula polinomial para a soma dos números inteiros elevados até um certo grau. Aqui estamos falando sobre a oitava potência, uma vez que o oitavo número de Bernoulli aparece pela primeira vez na fórmula da soma dos números inteiros positivos aumentados para a oitava potência. Os números B e A representam dois tipos de fatores descobertos por Bernoulli. Os números B1 a B7 são os vários números de Bernoulli numerados de acordo com Lovelace.Os números A0 a A5 são multiplicadores dos coeficientes que Bernoulli poderia calcular usando o triângulo Pascal. Os valores de A0, A1 e A3 são mostrados abaixo. Aqui n indica o índice de um número de Bernoulli em uma sequência de números ímpares de Bernoulli, começando com o primeiro. No programa Lovelace, n = 4.

A ₀ = −1 / 2⋅ (2n - 1) / (2n + 1)

A ₁ = 2n / 2

A ₃ = 2n (2n - 1) (2n - 2) / (2⋅ 3⋅4)

A ₅ = 2n (2n - 1) (2n - 2) (2n - 3) (2n - 4) / (2⋅3⋅4⋅5⋅6) Traduzi

o programa Lovelace para C , e assim provavelmente será mais fácil de ler. Primeiro, o programa dela calcula A ₀ e o resultado da multiplicação B ₁ A ₁. Então começa o ciclo, repetido duas vezes, para calcular B ₃ A ₃ e B ₅ A ₅ , uma vez que são lidos da mesma maneira. Após contar cada multiplicação, o resultado é adicionado aos anteriores, portanto, ao final do programa, é obtido o valor total.

Obviamente, traduzir para C não pode ser uma reprodução exata do programa Lovelace. Ele declara variáveis ​​na pilha, e as variáveis ​​Lovelace eram mais como registros. Mas ele torna mais óbvia a parte mais profética do programa Lovelace. Um programa C possui dois loops while, um dentro do outro. O programa Lovelace não possuía loops de tempo, mas agrupou as operações e descreveu em uma nota por que elas deveriam ser repetidas. A variável v10 do programa original e traduzida para C funciona como um contador, diminuindo a cada passagem do ciclo - um design semelhante é familiar a todos os programadores. Em geral, além da abundância de variáveis ​​com nomes obscuros, um programa em C não parece desconhecido.

Também é importante notar que a tradução do programa Lovelace para C não foi muito difícil, graças a um detalhe em seu diagrama. Diferentemente das tabelas Menabrea, sua tabela possui uma coluna "sinal de alteração no valor de uma variável", o que facilita muito o rastreamento de uma alteração no estado. Ela adiciona um sobrescrito a cada variável para indicar valores sucessivos armazenados nelas. O índice 2, por exemplo, significa que o valor usado é o segundo valor atribuído à variável desde o início do programa.

Primeiro programador?

Depois de traduzir o programa Lovelace para C, consegui executá-lo no computador. Para minha decepção, o resultado foi incorreto. Depois de procurar por erros, finalmente percebi que o problema não estava no meu código - o bug estava contido no programa original!

No "gráfico de desenvolvimento", Lovelace escreve na quarta operação v5 / v4. Mas v4 / v5 estará correto. Este erro pode aparecer na impressão, mas não na Lovelace. De uma forma ou de outra, esse é o bug mais antigo do computador. Fiquei surpreso por ter passado cerca de dez minutos procurando o primeiro bug da história.

Jim Randall, outro blogueiro que traduziu o programa Lovelace para PythonTambém observou esse bug de divisão e outros dois problemas. Quais são os pequenos erros no programa publicado Ada Lovelace nos dizendo? É possível que ela estivesse tentando escrever não apenas uma demonstração, mas um programa real. Afinal, você não pode escrever algo além de programas de brinquedos, evitando erros?

Um artigo da Wikipedia diz que Lovelace foi o primeiro a publicar um "programa complicado". Talvez seja exatamente assim que vale a pena perceber sua conquista. Menabrea, em seu trabalho, publicou "gráficos de desenvolvimento" um ano antes da publicação da tradução Lovelace. Babbage também escreveu mais de vinte programas que nunca foram publicados. Portanto, não é inteiramente correto escrever que Lovelace escreveu ou publicou o primeiro programa, embora sempre se possa discutir sobre o que constitui um programa. E ainda assim, o programa Lovelace está muito à frente de tudo o que foi publicado antes dele. No programa mais longo, Menabrea teve 11 operações e não houve loops e ramificações. O programa Lovelace tinha 25 operações e um loop aninhado (e, portanto, ramificação). Menabrea no final de seu trabalho escreveu o seguinte:

Após a construção da máquina, as dificuldades se resumem em fazer cartões; mas como essa é apenas uma tradução de fórmulas algébricas, por meio de alguma notação simples, será bastante simples delegar sua execução a algum trabalhador.

Babbage e Menabrea não estavam particularmente interessados ​​em aplicar a máquina analítica a problemas que iam além dos problemas matemáticos que inspiraram Babbage a criar computadores. Lovelace percebeu que a máquina analítica era capaz de muito mais do que Babbage e Menabrea poderiam ter imaginado. Lovelace também percebeu que "fazer cartões" não seria um trabalho mecânico e que isso poderia ser feito mal ou bem. É difícil avaliar isso sem entender o programa da Nota G e sem ver quanto cuidado ela tomou ao desenvolvê-lo. Mas, tendo feito isso, você pode concordar que o Lovelace, mesmo sem ser o primeiro programador, foi o primeiro a merecer esse nome.