Filosofia de Engenharia: Donald Knuth, Programar É uma Arte

Principais conclusões

• Programar é uma arte, não apenas engenharia. Knuth deu à obra de sua vida o título The Art of Computer Programming de propósito, submetendo o código a um padrão de beleza que nenhuma suíte de testes consegue medir.
• Código é literatura escrita para humanos. O primeiro público é a próxima pessoa que vai ler o programa; o compilador é apenas o segundo. A legibilidade é um requisito de engenharia de primeira classe, não uma cortesia.
• Gaste rigor só onde importa; gaste contenção em todo o resto. Prove os algoritmos, analise seu custo com exatidão, leve o ofício até o último caractere – e recuse-se a despejar esforço nos 97% do código que não fazem diferença.
• “Otimização prematura” significa medir primeiro. A frase famosa é uma disciplina de medição, não uma desculpa para código lento: encontre os poucos por cento críticos com profiling, ataque apenas esses e deixe o resto legível.

O princípio

“Em vez de imaginar que nossa principal tarefa é instruir um computador sobre o que fazer, vamos nos concentrar em explicar a seres humanos o que queremos que um computador faça.” – Donald Knuth¹

Uma única frase contém toda a postura. Para Knuth, um programa não é, em primeiro lugar, um fluxo de instruções dirigido a uma máquina; é um texto dirigido a uma pessoa – o próximo leitor, que normalmente é você mesmo, seis meses depois, tendo esquecido tudo. O compilador é o público secundário. O primeiro público é humano, e o programa ou é literatura para esse público ou é um fracasso, por mais corretamente que ele rode.

É por isso que Knuth deu à obra de sua vida o título The Art of Computer Programming, e não The Science ou The Engineering dela. Ele usa arte literalmente: um ofício perseguido pela qualidade da coisa feita, submetido a um padrão de beleza que nenhuma suíte de testes mede. A disciplina que daí decorre é exigente de um modo bem específico. Ela diz: faça o pequeno número de coisas que de fato importam, e faça-as exatamente certas. Prove que seus algoritmos estão corretos. Analise seu custo com precisão, em vez de chutar. Componha a página tipográfica de modo que ela possa ser lida sem atrito. E – a parte que todo mundo cita e quase todo mundo lê errado – não gaste seu ofício nos 97% do código que não importam, porque esforço despejado no lugar errado não é ofício, é desperdício fantasiado de diligência.

Então o princípio tem duas faces que parecem opostas e na verdade são uma só. Rigor em tudo o que importa; contenção em tudo o que não importa. A habilidade está em saber qual é qual – e a resposta de Knuth para como você sabe é a mesma que atravessa toda esta série: você mede. A frase famosa sobre otimização prematura não é uma licença para escrever código lento. É uma exigência de que você encontre os poucos por cento críticos por evidência antes de tocar em qualquer coisa, a mesma convicção de que desempenho é uma propriedade que se constrói e se mede, não um selo que se acrescenta no final.

Contexto

Donald Ervin Knuth nasceu em 10 de janeiro de 1938, em Milwaukee, Wisconsin.² Cursou bacharelado e mestrado no Case Institute of Technology – o Case ficou impressionado o suficiente para conceder o mestrado simultaneamente com o bacharelado em 1960 – e um doutorado em matemática pela Caltech em 1963.² Entrou para o corpo docente de Stanford em 1969, tornou-se Fletcher Jones Professor of Computer Science em 1977 e, em 1990, assumiu um título que essencialmente inventou para si mesmo: Professor of The Art of Computer Programming.² Há anos é professor emérito em Stanford e ainda trabalha, à mão e pelo correio, no mesmo projeto que o ocupa há mais de seis décadas.

Esse projeto começou como um acidente de escopo. Em 1962, a Addison-Wesley encomendou ao jovem Knuth um livro sobre compiladores.³ Ele começou a escrever e concluiu que não poderia explicar honestamente como construir um compilador sem antes assentar a teoria fundamental por baixo dele – ordenação, busca, estruturas de dados, a análise de quanto tempo os algoritmos de fato levam. O livro único virou uma série planejada. O primeiro volume, Fundamental Algorithms, saiu em 1968. O plano acabou crescendo para sete volumes, e a obra continua inacabada até hoje.³ A American Scientist mais tarde a apontou como um dos cem e poucos livros que moldaram um século de ciência, e o New York Times a chamou de “o tratado definidor da profissão”.³ É, por consenso razoável, a coisa mais próxima de uma bíblia que a ciência da computação tem.

Em 1974, Knuth recebeu o ACM A.M. Turing Award – a mais alta honraria da computação – “por uma série de grandes contribuições à análise de algoritmos e ao projeto de linguagens de programação e, em particular, por suas contribuições mais significativas à ‘arte da programação de computadores’ por meio de sua série de livros amplamente conhecidos”.⁴ Sua palestra Turing tinha o título, caracteristicamente, de “Computer Programming as an Art”.⁴

A obra

The Art of Computer Programming e a análise de algoritmos

Knuth é chamado de pai da análise de algoritmos, e o título é merecido.² Antes do TAOCP, os programadores em larga medida raciocinavam sobre algoritmos de modo informal – este aqui parece mais rápido, aquele parece um desperdício. O projeto de Knuth foi pôr esse raciocínio sobre uma base matemática rigorosa: derivar, com exatidão, quantas operações um algoritmo realiza em função de sua entrada, e fazê-lo com a mesma precisão que um matemático leva a um teorema. Ele popularizou a notação assintótica “big-O” que todo programador hoje usa para descrever como o custo escala.² O ponto nunca foi a notação; foi a convicção de que o custo de um programa é uma quantidade conhecível que você deveria calcular, não um palpite que você deveria ter.

Os volumes em si são famosos por uma espécie de completude obsessiva – toda afirmação provada, todo algoritmo analisado, todo caso de borda tratado – e pelos cheques de recompensa que Knuth oferece por qualquer erro encontrado. O cheque é de US$ 2,56, que ele descreve como “um dólar hexadecimal”, porque 256 centavos é 100 na base dezesseis.⁵ O valor é uma piada; a disciplina por trás dele não é. Knuth está apostando dinheiro de que seu trabalho está correto, e convidando o mundo a provar que ele está errado. O estado polido e ainda autoritativo do TAOCP, décadas depois, é em parte produto dessa aposta permanente.⁵ (Ele parou de enviar cheques literais em 2008, depois de uma fraude bancária, e agora emite certificados contra um imaginário “Bank of San Serriffe” – o rigor sobreviveu; o rastro de papel mudou.)⁵

Otimização prematura e os 3% críticos

A frase mais citada da engenharia de software é de Knuth, e quase sempre é citada errado – despojada da oração que lhe dá sentido. Aqui está a passagem completa, de seu artigo de 1974 “Structured Programming with go to Statements”, no ACM Computing Surveys:

“Os programadores desperdiçam enormes quantidades de tempo pensando, ou se preocupando, com a velocidade de partes não críticas de seus programas, e essas tentativas de eficiência na verdade têm um forte impacto negativo quando se consideram a depuração e a manutenção. Devemos esquecer as pequenas eficiências, digamos cerca de 97% do tempo: a otimização prematura é a raiz de todo mal. No entanto, não devemos abrir mão de nossas oportunidades nesses 3% críticos.”⁶

Lida por inteiro, ela não é um argumento contra desempenho. É um argumento a favor da medição. O ponto de Knuth é empírico: um programa gasta quase todo o seu tempo numa fração minúscula de seu código, e otimizar os outros 97% – as partes que mal rodam – custa esforço real, rende quase nada e torna o código mais difícil de ler e de confiar. O “mal” não é a otimização. O mal é otimizar antes de você saber para onde vai o tempo – gastar ofício em fé em vez de evidência. A disciplina que ele prescreve é o oposto da preguiça: encontre os 3% críticos com profiling e então ataque-os com força.

Uma palavra sobre atribuição, porque ela importa para quem quer que cite a frase com honestidade. A sentença aparece no artigo de Knuth de 1974, em sua própria prosa. Mas quinze anos depois o próprio Knuth se referiu a ela como “o dito de Hoare”, atribuindo-a a Tony Hoare – e quando Hoare foi perguntado diretamente, ele também a recusou, sugerindo que poderia ser de Dijkstra e que melhor seria tratá-la como “cultura comum ou folclore”.⁷ Então a afirmação correta mais limpa é esta: a redação que todos nós citamos é de Knuth, publicada por Knuth em 1974; a ideia ele generosamente se recusou a reivindicar como exclusivamente sua. Essa recusa é, ela mesma, fiel ao personagem. O homem que paga você para encontrar seus erros não tem interesse em ficar com um crédito do qual não tem certeza de ser dono.

TeX, METAFONT e a tipografia digital como ofício

Em 1976, Knuth recebeu as provas de paginação da segunda edição do Volume 2 e ficou horrorizado. A composição em metal quente que tornara a primeira edição bela estava sendo substituída pela fototipografia inicial, e o resultado era feio – a matemática, em particular, parecia errada.³ Outra pessoa teria aceitado aquilo como o preço do progresso. Knuth, que não podia deixar seus próprios livros serem mal compostos, decidiu em 1977 dedicar um pouco de tempo a construir algo melhor. O pouco de tempo virou quase uma década. O resultado foi o TeX, o sistema de composição tipográfica, e o METAFONT, o sistema complementar para projetar as próprias fontes; ambos foram concluídos e publicados como livros em 1986.³

Nenhum desvio de sua carreira revela mais. Um matemático interrompeu sua obra-prima por oito anos para resolver, a partir de primeiros princípios, o problema de pôr caracteres belos numa página – porque a aparência da página não era, em sua mente, separável da qualidade do trabalho. O TeX ainda é o padrão para a composição de matemática no mundo inteiro, quarenta anos depois. É a declaração mais clara possível de que, para Knuth, o artefato se estende até o último pixel do último glifo: o ofício não para no código. É a versão do engenheiro para acabar o fundo da cerca – a parte que o leitor nunca nota conscientemente é a parte que ele se recusou a fazer mal.

Programação literária

Se um programa é feito para ser lido por humanos, então a maneira como o escrevemos – na ordem do compilador, com comentários pregados como uma reflexão tardia – está de cabeça para baixo. Em 1984, num artigo de The Computer Journal, Knuth propôs invertê-la. Ele chamou a prática de programação literária (literate programming) e construiu um sistema chamado WEB para fazê-lo.¹

Na programação literária você escreve um único documento na ordem do pensamento humano – prosa explicando o que você pretende, com fragmentos de código entrelaçados onde a explicação os pede, na sequência que melhor se lê. Duas ferramentas então o processam: tangle extrai o código na ordem de que o compilador precisa, e weave produz a documentação formatada e tipograficamente composta que uma pessoa lê.⁸ O WEB combinava Pascal e TeX; o CWEB posterior, com Silvio Levy, fez o mesmo para C.⁸ A descrição do próprio Knuth é que “um programa é mais bem pensado como uma teia… a tarefa do programador é enunciar essas partes e essas relações, na ordem que for melhor para a compreensão humana”.⁸

A programação literária nunca se tornou prática dominante, e vale ser honesto quanto a isso. Mas a convicção por baixo dela – de que a explicação não é documentação do programa, mas é o programa, de que a legibilidade é um requisito de engenharia de primeira classe e não uma cortesia – venceu silenciosamente. É o mesmo instinto que nos faz valorizar código que se explica sozinho, e é a resposta mais profunda que Knuth dá à pergunta sobre para que serve programar.

O método

O método é consistente ao longo de sessenta anos e quatro domínios – algoritmos, tipografia, projeto de linguagens e a própria escrita.

Escreva para o leitor humano primeiro. A máquina é o segundo público. Um programa, como uma prova ou um parágrafo, é julgado pela capacidade da próxima pessoa de acompanhá-lo. A programação literária é essa convicção transformada em ferramenta.¹⁸

Prove, depois teste. “Cuidado com os bugs no código acima; só provei que está correto, não o experimentei”, escreveu Knuth num memorando de 1977 – uma frase que tem graça precisamente porque ele é a pessoa rara que de fato prova seu código.⁹ A piada contém a disciplina: a correção é argumentada, não presumida, e uma prova é necessária, mas ainda não suficiente. Você deve as duas coisas.

Analise o custo; não o adivinhe. O tempo de execução de um algoritmo é uma quantidade a ser derivada matematicamente, não um palpite. Esse é o ato fundador da análise de algoritmos, e é por isso que “big-O” está na boca de todo programador.²

Meça antes de otimizar. A otimização prematura é a raiz de todo mal porque gasta ofício em fé. Encontre os 3% críticos por evidência; otimize só ali; deixe o resto legível.⁶

Deixe o ofício correr até o último glifo. Parar a obra da vida por oito anos para construir o TeX é o método na sua forma mais pura: a qualidade do artefato não para onde o código para. Ela termina na borda da página.³

Proteja o foco profundo. Knuth abandonou o e-mail em 1º de janeiro de 1990 – “tenho sido um homem feliz desde então”, escreveu – com o raciocínio de que o e-mail é para pessoas cujo trabalho é estar por cima das coisas, ao passo que o trabalho dele é estar por baixo das coisas, estudando um assunto profundamente o bastante para explicá-lo bem.¹⁰ A recusa da interrupção não é excentricidade; é a precondição do trabalho.

Cadeia de influência

Quem o moldou

A tradição matemática, especialmente a combinatória e a teoria dos números. Knuth chegou à programação como matemático, e trouxe o padrão inegociável do matemático – uma afirmação não é conhecimento enquanto não for provada – para um campo que vinha se virando na intuição. (Influência formadora)

A encomenda da Addison-Wesley em 1962. O acidente que fixou a trajetória. Pedido a escrever um livro sobre compiladores, Knuth seguiu o problema até seus fundamentos e nunca mais voltou à superfície; a análise de algoritmos existe em sua forma moderna porque ele se recusou a escrever o livro fácil que lhe pediram. (Influência direta)

A tipografia em metal quente e o livro impresso. Seu padrão para a aparência de uma página composta foi formado pelo ofício de uma era anterior da impressão – e é exatamente por isso que as provas fototipográficas de 1976 eram intoleráveis e o TeX se tornou necessário. (Influência formadora)

Quem ele moldou

Todo programador em atividade. A análise big-O, o estudo rigoroso de algoritmos e o próprio TAOCP são alfabetização básica. Uma geração aprendeu o que um algoritmo custa com Knuth, tenha ela aberto seus livros ou não.

A publicação matemática e científica do mundo. TeX e LaTeX são o substrato de essencialmente todo artigo de matemática, preprint de física e livro técnico composto nos últimos quarenta anos. O desvio de oito anos de Knuth virou infraestrutura.

A cultura da correção e da legibilidade. A programação literária, os cheques de recompensa, “provei que está correto, não o experimentei” – isso definiu um tom. A expectativa de que código sério deva ser ao mesmo tempo comprovadamente certo e agradável de ler é, em parte, legado de Knuth.

O fio condutor

Knuth e Edsger Dijkstra são os dois grandes apóstolos da correção desta série, e a tensão produtiva entre eles é a coisa mais instrutiva dela. Ambos escreviam à mão, desconfiavam da máquina como árbitra da verdade e insistiam que um programa deveria ser objeto de raciocínio, não apenas executado. Mas onde Dijkstra sustentava que o teste só pode mostrar a presença de bugs e nunca a sua ausência – e pendia fortemente para a prova como o único terreno real – o “só provei que está correto, não o experimentei” de Knuth pisca para o limite da própria prova: ele prova e testa, e paga você quando ambos falham. Pragmatismo dentro do rigor. John Carmack está sobre o mesmo eixo, vindo da outra ponta – faça profiling do hotspot, entenda a máquina até seus fundamentos, ataque o laço crítico – que é exatamente os “3% críticos” de Knuth mirados no teto do hardware em vez da prova. E o Unix de Thompson e Ritchie, em que o C foi construído para que um sistema operacional pudesse ser lido e portado em vez de soldado à mão numa única máquina, é a mesma crença que Knuth tornou explícita: programas são escritos para humanos. (Ponte da série)

O que eu tiro disto

A lição que guardo é que a frase mais citada do meu campo é uma disciplina de medição vestida com a fantasia de um aforismo. “A otimização prematura é a raiz de todo mal” é usada para desculpar código lento e preguiçoso, que é o inverso exato do que Knuth quis dizer. O que ele de fato exige é mais difícil do que otimizar tudo ou não otimizar nada: faça profiling primeiro, localize os 3% críticos por evidência, despeje seu ofício exatamente neles e deixe o resto legível. Esse é o mesmo padrão de qualidade ser a única variável – a pergunta nunca é “isto está rápido o suficiente?” ou “isto está engenhoso o suficiente?”, mas “tenho evidência de onde o custo de fato está?”. É a barreira da evidência aplicada ao desempenho: um palpite sobre o hotspot não é conhecimento enquanto você não o tiver medido.

No mundo em que construo agora – agentes, laços de ferramentas, chamadas a modelos – as duas faces de Knuth são ambas estruturais. A contenção: não otimize um prompt ou um caminho de recuperação que você não mediu; quase toda a latência vive em umas poucas chamadas, e o resto é ruído que você deveria deixar legível. O rigor: onde importa, prove, teste e coloque algo em jogo apostando que está certo. E a convicção da programação literária é a que considero mais relevante aos cinquenta anos de idade – quando um sistema consegue gerar código mais rápido do que qualquer um consegue ler, escrever para o leitor humano primeiro deixa de ser uma gentileza e passa a ser a única coisa que mantém o sistema inspecionável. Essa convicção – de que o bom gosto é um sistema técnico que você mede e defende, não um clima que você decreta – corre direto de uma encomenda de livro de 1962 a uma estrutura de agentes de 2026.

FAQ

Qual é a filosofia de engenharia de Donald Knuth?

Knuth trata a programação como uma arte cujo primeiro público é humano, não a máquina: “explicar a seres humanos o que queremos que um computador faça”.¹ A disciplina que daí decorre emparelha rigor exigente com contenção deliberada – provar que os algoritmos estão corretos, analisar seu custo matematicamente e levar o ofício até a página tipográfica, ao mesmo tempo que se recusa a gastar esforço otimizando as partes de um programa que não importam. Ele resolve qual é qual pela medição, que é o sentido real de sua frase sobre otimização prematura.⁶

O que “a otimização prematura é a raiz de todo mal” de fato quis dizer?

É uma exigência de medição, não uma rejeição do desempenho. A citação completa de 1974 é: “Devemos esquecer as pequenas eficiências, digamos cerca de 97% do tempo: a otimização prematura é a raiz de todo mal. No entanto, não devemos abrir mão de nossas oportunidades nesses 3% críticos.”⁶ O ponto de Knuth é que um programa gasta quase todo o seu tempo numa pequena fração de seu código; otimizar os outros 97% desperdiça esforço e prejudica a legibilidade. A disciplina é fazer profiling primeiro, encontrar os poucos por cento críticos e otimizar apenas esses. Usar a frase para desculpar código lento inverte seu sentido.

Knuth inventou a citação da “otimização prematura”, ou foi Hoare?

A redação que todo mundo cita é de Knuth, publicada em seu próprio artigo de 1974 no Computing Surveys, “Structured Programming with go to Statements”.⁶ Quinze anos depois, porém, o próprio Knuth se referiu a ela como “o dito de Hoare” e a atribuiu a Tony Hoare; quando Hoare foi perguntado diretamente, ele também recusou a autoria, sugeriu que poderia remontar a Dijkstra e disse que o melhor era tratá-la como “cultura comum ou folclore”.⁷ O resumo honesto: a frase tal como a citamos é de Knuth, mas ele generosamente declinou reivindicar a ideia como exclusivamente sua.

O que Donald Knuth criou?

Knuth escreveu The Art of Computer Programming (iniciado em 1962, primeiro volume em 1968, em andamento – o tratado definidor da ciência da computação) e fundou a moderna análise de algoritmos, popularizando a notação big-O.²³ Frustrado com a má composição tipográfica de seus próprios livros, criou o sistema de composição TeX e o sistema de fontes METAFONT, ambos publicados em 1986 e ainda padrão para a publicação matemática.³ Ele também originou a programação literária e o sistema WEB, a prática de escrever programas para serem lidos por humanos.¹⁸ Recebeu o ACM Turing Award de 1974.⁴

Fontes