A Arte de Escrever Programas de Computador

Estava continuando a minha leitura do Beautiful Code e em dos capítulos é citada uma forma de escrever o "binary search" sem um bug que passou um bom tempo para ser descoberto. Fiquei curioso e fui procurar.

Então vamos por partes, já que nem todo mundo que lê o blog precisa entender de programação.

Esse algorítimo (sequência de instruções lógicas para o computador) basicamente procura um dado específico (nome, número, etc.) em uma lista de dados ordenados. É uma maneira comprovadamente eficiente de fazer o computador procurar um nome em uma lista telefônica, por exemplo.

É bem simples. Basicamente você abre a lista telefônica ao meio e escolhe uma palavra. Se a que você procura está ordenada atrás dessa, você volta a dividir ao meio a lista, mas agora o trecho é do meio até o início. Olha novamente uma palavra. Se a que procura está atrás, divide novamente ao meio. Só com três passos você já reduziu as opções restantes para 1/8 da lista telefônica. E isso funciona se a palavra estiver depois também, basta dividir ao meio para o outro lado. Não precisa dizer que isso é melhor que olhar página por página, não é? :-)

Agora que você já aprendeu como funciona, deixa eu explicar o que é engraçado nessa história: esse é um dos algorítimos mais conhecidos do mundo. Está em vários livros, incluindo os mais famosos. Todo mundo que assiste aula disso acaba estudando e posteriormente utilizando-o em seus próprios softwares.

Um cara chamado Programming Pearls, 1986) e escreveu esse mesmo código para uma ferramenta de desenvolvimento Java (JDK), que serve para escrever outros programas.
Obviamente, com toda a idade do algorítimo, tudo funcionou perfeitamente.

Aí sabe o que aconteceu? NOVE ANOS depois, quando milhares e milhares de software já estavam usando, descobriram que está errado. Tá, não é que esteja completamente errado. É que existe uma condição que ainda não havia sido detectada, onde o algorítimo causa um erro de execução e interrompe se não for devidamente tratado.

Aí foram olhar direitinho e descobriram que a versão escrita no livro de 1986 tem esse problema também! Nada mal né? Vinte anos publicados no Programming Pearls, passando por centenas de milhares de estudantes e professores, possuia uma falha! E precisou ser no dia-a-dia para que alguém percebesse, quando já existiam milhares de cópias em execução.

Eu sou um dos que defendem que bugs no software não são normais. Não são coisas que precisam acontecer. No entanto, é impossível afirmar que qualquer código seja completamente imune à estas situações. Tratando-se da programação em mais alto nível, especialmente, onde mais código pode (e deve) ser reaproveitado, as chances de perpetuar um erro prévio são ainda maiores.

Algumas lições baseadas nesta historinha:

1 - Aos usuários: reclamem com o seu distribuidor! Software não é para dar problema. Não tente reduzir o orçamento retirando fases de testes.
Há, e também torça para não encontrar um desses bugs no freio ABS do seu carro ou no piloto automático de um vôo qualquer.

2 - Aos programadores: façam o seu trabalho bem feito! Pensem no imprevisto. Testem o máximo de condições possíveis. Teste entradas absurdas também. Simplesmente isso: façam com atenção e testem. E depois teste novamente! :-)

3- A todos: bug é uma palavra bonitinha para erro.

Aos não programadores, o post acaba aqui.


Aos que continuam, eis o problema (versão em Java):
1:     public static int binarySearch(int[] a, int key) {
2: int low = 0;
3: int high = a.length - 1;
4:
5: while (low <= high) {
6: int mid = (low + high) / 2;
7: int midVal = a[mid];
8:
9: if (midVal < low =" mid"> key)
12: high = mid - 1;
13: else
14: return mid; // key found
15: }
16: return -(low + 1); // key not found.
17: }
Vejam a linha 6. Nada errado, certo? Errado. Se os números forem grandes o suficiente (maiores que 2³¹-1) a soma vai resultar em um número negativo e gerar um ArrayIndexOutOfBoundsException. Em C o desastre é maior, porque nem Deus sabe o que pode acontecer...

Em Java, a correção pode ser:
 int mid = (low + high) >>> 1;
e em C:
 mid = ((unsigned int)low + (unsigned int)high)) >> 1;

Como bem lembrou Tim Bray, o cara do texto do Beautiful Code, os Rubystas e Pythonianos podem ficar felizes, pois este problema eles não teriam, já que estas linguagens dinâmicas "modernas" tratam o overflow da variável de forma transparente. Mas isso tem o seu preço também, né? :-)

Referências:
1. Beautiful Code
2. http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html

Comentários

valdir disse…
Muito legal essa história do binary search, não conhecia. E concordo, as pessoas acham "normal" o bug, não deveria ser assim.

Parabéns pelo post!
Anônimo disse…
Cara...muito bom..irei comprar esse livro! :^D

Postagens mais visitadas deste blog

Hacking GVT/Vivo Sagemcom F@st 2764 GV (aka "Desbloqueio")

Alguns "Looking-glass" úteis.