O Yoda do Vale do Silício

SIOBHAN ROBERTS

Donald Knuth, mestre em algoritmos, reflete sobre os 50 anos de seu trabalho em andamento, "A arte da programação de computadores".

Por meio século, o cientista da computação de Stanford, Donald Knuth, que tem uma ligeira semelhança com Yoda - apesar de estar de 1,80m e usando óculos - reinou como o guia espiritual do reino algorítmico.

Ele é o autor de "A arte da programação de computadores", uma obra contínua de quatro volumes e que é o trabalho de sua vida. O primeiro volume estreou em 1968, e a coleção dos volumes (vendida como um box por cerca de US $ 250) foram incluídos pela American Scientist em 2013 em sua lista de livros que moldaram o último século da ciência - juntamente com uma edição especial de "The Autobiography of Charles Darwin", "The Right Stuff" de Tom Wolfe, "Silent Spring" de Rachel Carson e monografias de Albert Einstein, John von Neumann e Richard Feynman.

Com mais de um milhão de cópias impressas, "A Arte da Programação de Computadores" é a Bíblia de seu campo. "Como uma bíblia real, é longa e abrangente; nenhum outro livro é tão abrangente", disse Peter Norvig, diretor de pesquisa do Google. Depois de 652 páginas, o primeiro volume fecha com uma sinopse na contracapa de Bill Gates: "Você deveria mandar-me um currículo se puder ler tudo."

O volume abre com um trecho de "McCall's Cookbook":

"Aqui está o seu livro, o que as suas milhares de cartas nos pediram para publicar. Levamos anos para fazer, checando e verificando inúmeras receitas para trazer apenas o melhor, apenas o interessante, apenas o perfeito."

Dentro estão os algoritmos, as receitas que alimentam a era digital - embora, como o Dr. Knuth gosta de salientar, os algoritmos também podem ser encontrados em tablets babilônicos a partir de 3.800 anos atrás. Ele é um algoritmo estimado; seu nome é anexado a alguns dos espécimes mais importantes do campo, como o algoritmo de busca de string Knuth-Morris-Pratt. Criado em 1970, ele encontra todas as ocorrências de uma determinada palavra ou padrão de letras em um texto - por exemplo, quando você pressiona Command + F para procurar uma palavra-chave em um documento.

Agora com 80 anos, o Dr. Knuth geralmente se veste como o geek jovem que ele era quando embarcou nessa odisseia: camiseta de mangas compridas sob uma camiseta de manga curta, com jeans, pelo menos nessa época do ano. Naqueles primeiros dias, ele trabalhava perto da máquina, escrevendo "em estado bruto", mexendo com os zeros e uns.

"Knuth deixou claro que o sistema poderia ser compreendido até o nível de código da máquina", disse Norvig. Hoje em dia, é claro, com os algoritmos planejando (e minando) nossa própria existência, o programador médio não tem mais tempo para manipular o muck binário e trabalha com hierarquias de abstração, camadas sobre camadas de código - e frequentemente com cadeias de código emprestadas. de bibliotecas de código. Mas uma classe de elite de engenheiros, ocasionalmente, ainda faz o mergulho profundo.

"Aqui no Google, às vezes, apenas jogamos coisas juntos", disse Norvig, durante uma reunião da equipe do Google Trips, em Mountain View, Califórnia. "Mas outras vezes, se você está servindo bilhões de usuários, é importante faça isso de forma eficiente. Uma melhoria de 10% na eficiência pode chegar a bilhões de dólares e, para obter o último nível de eficiência, é preciso entender o que está acontecendo."

Ou, como Andrei Broder, um renomado cientista do Google e um dos ex-alunos de pós-graduação do Dr. Knuth, explicou durante o encontro: "Queremos ter alguma base teórica para o que estamos fazendo. Não queremos um algoritmo frívolo ou desleixado ou de segunda categoria. Não queremos que algum outro algoritmo diga: "Vocês são idiotas."

O aplicativo Google Trips, criado em 2016, é um "algoritmo de orientação" que mapeia as atividades turísticas recomendadas para um dia inteiro. A equipe estava trabalhando na "maximização da qualidade do pior dia" - por exemplo, evitando enviar o usuário de volta à mesma vizinhança para ver locais diferentes. Eles se inspiraram em um algoritmo de 300 anos do matemático suíço Leonhard Euler, que queria mapear uma rota através da cidade prussiana de Königsberg, que atravessaria cada uma das suas sete pontes apenas uma vez. Dr. Knuth aborda o problema clássico de Euler no primeiro volume de seu tratado. (Ele certa vez aplicou o método de Euler na codificação de uma máquina de costura controlada por computador.)

Seguir a doutrina do Dr. Knuth ajuda a afastar a morbidade. Ele é conhecido por introduzir a noção de "programação letrada", enfatizando a importância de se escrever um código que seja legível tanto por humanos quanto por computadores - uma noção que hoje em dia parece quase dupla. O Dr. Knuth foi longe ao ponto de argumentar que alguns programas de computador são, como os poemas de Elizabeth Bishop e "American Pastoral" de Philip Roth, obras de literatura dignas de um Pulitzer.

Ele também é um perfeccionista notório. Randall Munroe, o caricaturista xkcd e autor de "Thing Explainer", aprendeu pela primeira vez sobre o Dr. Knuth de pessoas da ciência da computação que mencionaram o dinheiro da recompensa que o Dr. Knuth paga a qualquer um que acha um erro em qualquer de seus livros. Como lembrou o Sr. Munroe, "as pessoas falavam em obter um desses cheques como se fosse o prêmio Nobel da ciência da computação".

Os rigorosos padrões do Dr. Knuth, literários ou não, podem explicar por que o trabalho de sua vida está longe de ser concluído. Ele tem uma aposta com Sergey Brin, o co-fundador do Google e um ex-aluno (para usar o termo vagamente), sobre se o Sr. Brin terminará seu Ph.D. antes que o Dr. Knuth conclua sua obra.

O alvorecer do algoritmo

Aos 19 anos, o Dr. Knuth publicou seu primeiro artigo técnico, "O Sistema Potrzebie de Pesos e Medidas", na revista Mad. Ele se tornou um cientista da computação antes da existência da disciplina, estudando matemática no que hoje é a Universidade Case Western Reserve, em Cleveland. Ele analisou os programas de amostra do mainframe IBM 650 da escola, um computador decimal e, percebendo algumas inadequações, reescreveu o software, bem como o livro usado na aula. Como um projeto paralelo, ele correu estatísticas para o time de basquete, escrevendo um programa de computador que os ajudou a ganhar o campeonato - e ganhou um segmento de Walter Cronkite chamado "O Treinador Eletrônico".

Durante as férias de verão, o Dr. Knuth ganhava mais dinheiro do que os professores ganhando em um ano escrevendo compiladores. Um compilador é como um tradutor, convertendo uma linguagem de programação de alto nível (assemelhando-se à álgebra) a uma de nível inferior (às vezes, um binário arcano) e, idealmente, melhorando-a no processo. Na ciência da computação, "otimização" é verdadeiramente uma arte, e isso é articulado em outro provérbio dos Knuthianos: "A otimização prematura é a raiz de todo mal".

Eventualmente, o próprio Dr. Knuth se tornou um compilador, inadvertidamente fundando um novo campo que passou a chamar de "análise de algoritmos". Um editor o contratou para escrever um livro sobre compiladores, mas evoluiu para um livro coletando tudo o que sabia sobre como escreva para computadores - um livro sobre algoritmos.

"Na época do Renascimento, a origem dessa palavra estava em dúvida", começou. "E os primeiros linguistas tentaram adivinhar sua derivação fazendo combinações como algiros [dolorosas] + arithmos [número]." Na verdade, Dr. Knuth continuou, o homônimo é o autor persa do século IX Abū 'Abd Allāh Muhammad ibn Mūsā al-Khwārizmī, latinizado como Algorithmi. Nunca um para meias medidas, Dr. Knuth foi em peregrinação em 1979 para a terra ancestral de al-Khwārizmī no Uzbequistão.

Quando o Dr. Knuth começou, ele pretendia escrever um único trabalho. Logo depois, a ciência da computação passou pelo Big Bang, então reinventou e reformulou o projeto em sete volumes. Agora ele produz sub volumes, chamados fascículos. A próxima instalação, "Volume 4, Fascículo 5", abrangendo, entre outras coisas, "backtracking" e "links de dança", foi feita para ser publicada em tempo para o Natal. Está atrasado até o próximo mês de abril, porque continua encontrando problemas cada vez mais irresistíveis que deseja apresentar.

A fim de otimizar suas chances de chegar ao fim, o Dr. Knuth há muito tempo guardou seu tempo. Ele se aposentou aos 55 anos, restringiu seus compromissos públicos e deixou o e-mail (oficialmente, pelo menos). Andrei Broder lembrou que o gerenciamento do tempo era a característica definidora de seu professor, mesmo no início dos anos 80.

Dr. Knuth costumava realizar consultas aos alunos nas sextas-feiras de manhã, até começar a passar as noites no laboratório de John McCarthy, um dos fundadores da inteligência artificial, para obter acesso aos computadores quando estavam livres. Horrorizado com o que seu amado livro parecia na página com o advento da publicação digital, o Dr. Knuth tinha ido em uma missão para criar o sistema de composição de computador TeX, que continua a ser o padrão ouro para todas as formas de comunicação científica e publicação. Alguns consideram a maior contribuição do Dr. Knuth para o mundo e a maior contribuição para a tipografia desde Gutenberg.

Esse desvio de uma década ocorreu na época em que os computadores eram compartilhados entre os usuários e corriam mais rápido à noite, enquanto a maioria dos humanos dormia. Então, o Dr. Knuth trocou o dia para a noite, alterou sua programação em 12 horas e mapeou as consultas dos alunos às sextas-feiras a partir das 20h. à meia-noite. O Dr. Broder relembrou: "Quando eu disse à minha namorada que não podemos fazer nada sexta-feira à noite porque às sextas-feiras às 10 tenho que encontrar meu conselheiro, ela pensou: 'Isso é algo tão estúpido que deve ser verdade.'".

Quando Knuth escolhe estar fisicamente presente, no entanto, ele está 100 por cento no momento. "Isso faz você feliz por estar perto dele", disse Jennifer Chayes, diretora administrativa da Microsoft Research. "Ele é um máximo na comunidade. Se você tivesse uma função de otimização que fosse de alguma forma uma combinação de calor e profundidade, Don a seria."

Domingo com o algoritmo

O Dr. Knuth mora em Stanford e permite um visitante de domingo. Que ele poupou um dia inteiro foi excepcional - geralmente a sua disponibilidade é o "horário da soneca modulada", um ritual diário sagrado a partir das 13h às 16h. Ele começou cedo, na Primeira Igreja Luterana de Palo Alto, onde ele ministrou uma aula da escola dominical para uma multidão que só frequentava a sala de estar. Dirigindo para casa, ele ficou filosófico sobre matemática.

"Eu nunca saberei de tudo", disse ele. "Minha vida seria muito pior se não houvesse nada sobre o que eu soubesse as respostas, e se não houvesse nada sobre o qual eu não soubesse as respostas." Então ele ofereceu uma visita à sua casa "moderna da Califórnia", que ele e esposa, Jill, construída em 1970. Seu escritório está cheio de pilhas de USB varas e adornada com arte do coração do dia dos namorados de Jill, um designer gráfico. O mais impressionante é a sala de música, construída em torno de seu órgão de tubos de 812 tubos feito sob medida. O dia terminou com cerveja em uma festa de quebra-cabeça.

Quebra-cabeças e jogos - e escrever uma novela sobre números surreais e compor um sonho musical multimídia de 90 minutos, "Fantasia Apocalyptica" - são o tipo de coisa que realmente faz cócegas nele. Uma parte de seu livro é intitulada "Puzzles Versus the Real World". Ele enviou um e-mail para a equipe de pai e filho de Martin Demaine, um artista, e Erik Demaine, um cientista da computação, ambos do Massachusetts Institute of Technology, porque Dr. Knuth incluiu suas "fontes de quebra-cabeças algorítmicas".

"Fiquei emocionado", disse Erik Demaine. "É uma honra estar no livro." Ele mencionou outra citação de Knuth, que serve como o lema inspirador para a conferência semestral "FUN with Algorithms": "O prazer provavelmente tem sido o principal objetivo o tempo todo."

Mas então, disse Demaine, o campo foi e ficou prático. Engenheiros, cientistas e artistas estão se unindo para resolver problemas do mundo real - dobramento de proteínas, robótica, airbags - usando os desenhos de origami matemáticos de Demaine para como dobrar papel e ligações em diferentes formas.

Claro, toda a ladainha algorítmica também está causando problemas do mundo real. Algoritmos escritos por humanos - lidando com problemas cada vez mais difíceis, mas produzindo código embutido com bugs e vieses - são bastante preocupantes. Mais preocupantes, talvez, sejam os algoritmos que não são escritos por humanos, algoritmos escritos pela máquina, conforme ela aprende.

Os programadores ainda treinam a máquina e, crucialmente, alimentam os dados. (Os dados são o novo domínio de vieses e bugs, e aqui os bugs e vieses são mais difíceis de encontrar e consertar). No entanto, como Kevin Slavin, um afiliado de pesquisa do Media Lab do M.I.T., disse: "Estamos agora escrevendo algoritmos que não podemos ler. Isso faz com que este seja um momento único na história, pois estamos sujeitos a ideias, ações e esforços de um conjunto de física que tem origens humanas sem compreensão humana.". Como Slavin observou, frequentemente, "é um futuro brilhante, se você é um algoritmo".

Ainda mais se você for um algoritmo versado em Knuth. "Hoje, os programadores usam coisas que Knuth e outros fizeram como componentes de seus algoritmos, e combinam isso com todas as outras coisas de que precisam", disse o Dr. Norvig, do Google.

"Com A.I., temos a mesma coisa. É só que a parte combinada será feita automaticamente, com base nos dados, em vez de se basear no trabalho de um programador. Você quer A.I. para poder combinar componentes para obter uma boa resposta com base nos dados. Mas você tem que decidir quais são esses componentes. Pode acontecer que cada componente seja uma página ou um capítulo de Knuth, porque essa é a melhor maneira possível de realizar alguma tarefa."

Sorte, então, que Dr. Knuth continua nisso. Ele calcula que levará outros 25 anos para terminar "A arte da programação de computadores", embora esse período de tempo tenha sido uma constante desde 1980. Os algoritmos de criação de algoritmos poderiam ter seu próprio capítulo, ou talvez uma página no epílogo? "Definitivamente não", disse Dr. Knuth.

"Eu estou preocupado que os algoritmos estão ficando muito proeminentes no mundo", acrescentou. "Começou que os cientistas da computação estavam preocupados que ninguém estivesse nos ouvindo. Agora estou preocupado que muitas pessoas estejam ouvindo."


Artigo traduzido por Gabriela Pontes
Estagiária de Pesquisa & Desenvolvimento e Editora de conteúdo na Go2Web