Single-Person Pair Programming

Dia desses me perguntaram no twitter o que eu achava de Pair programming. Não apenas eu gosto, como sou entusiasta! Pair programming tem um monte de vantagens, sendo que a principal delas é que o programa será escrito com dois pares de olhos. E como nos lembra a Lei do Beholder Lei de Linus: dados olhos suficientes, todos os bugs são fáceis.

Minha técnica predileta de pair programming é o Ping-Pong Pair Programming, que eu aprendi com o Miško. A idéia é mesclar as idéias do pair programming com o test-driven development. Você começa colocando dois teclados no computador, aí um parceiro escreve um teste, e o outro escreve o código que faz aquele teste passar. A vantagem desse método é que funciona mesmo se um dos programadores for preguiçoso, e, de fato, funciona até melhor assim!

Por exemplo, vamos supor que Alice e Bob querem escrever um programa bem simples: uma função que incrementa um número. Digamos que a assinatura dessa função será int increment(int value). Alice escreve um teste que valida essa função:

void teste1() {
  assertEquals(2, increment(1));
}

Um teste bem razoável. Se entrar um, tem que sair dois. Agora Bob vai escrever o código que faz esse teste passar:

int increment(int value) {
  return 2;
}

FAIL? O Bob é um cara preguiçoso, então ele escreveu um código que sempre retorna dois. Isso faz o teste passar, mas não era isso que a Alice tinha em mente!

Surpreendentemente, essa é a vantagem do ping-pong. Suponha que esse teste fosse o único teste que o código tinha. Agora digamos que alguém, anos depois, foi refatorar o código, mas fez uma bobagem no processo e agora a função que incrementa um número está retornando sempre 2. Nesse caso, o teste não vai detectar o erro!

A conclusão é que o teste inicial não era robusto o suficiente. Pra melhorar isso, Alice escreve um segundo teste:

void teste2() {
  assertEquals(3, increment(2));
}

Agora o código original do Bob não funciona, e ele precisa refatorar pra criar um código que passe os dois testes:

int increment(int value) {
  if (value == 1)
    return 2;
  else
    return 3;
}

E agora, FAIL? Não há dúvidas de que o conjunto com dois testes é mais robusto que apenas o primeiro teste, mas esse processo não parece prático. Afinal, os dois poderiam ficar no ping-pong até exaurir todos os valores do int, o que levaria um bocado de tempo.

Mas isso não acontece! Como sabemos, o Bob é preguiçoso. Na verdade, ele é tão preguiçoso, que atingiu o nível supremo da preguiça: a meta-preguiça. O Bob sabe que se ele continuar nesse ping-pong, ele vai ficar trabalhando até depois das seis, e ele quer ir pra casa ver a novela. Se a Alice escrever testes o suficiente, ela vai acabar forçando o Bob a escrever o código correto, porque é o código mais simples que resolve o problema.

void teste3() {
  assertEquals(4, increment(3));
}


int increment(int value) {
  return value + 1;
}

Agora sim! O resultado final é duplamente bom, nós temos um conjunto de testes robustos, e um código que é o mais simples possível (o que é sempre uma vantagem, esse código é o mais fácil de entender, tem o menor custo de manutenção, etc.)

Esse método me fascinou por dois motivos. Primeiro, ele é uma aplicação da Navalha de Occam em software: você parte de uma série de observações e deduz a teoria mais simples que modela o sistema. Segundo, o método é um indicativo de que é possível fazer um conjunto de testes que define a operação em questão.

Juntando as duas observações, a pergunta natural que faz é: pra que eu preciso do Bob? Eu poderia construir uma máquina que, dado um conjunto de testes, encontre o programa mais simples que os satisfaçam. Se a máquina conseguir jogar o ping-pong de maneira ótima, então acabamos de inventar o Single-Person Pair Programming!

Antes de tentar resolver esse problema, precisamos escolher alguma definição para "programa mais simples". Por exemplo, vamos escolher que o programa mais simples é o menor programa que resolve o problema. Uma maneira de achar esse programa é fazer um brute force: basta testar todos os programas possíveis!

Isso é fácil de visualizar em assembly. O conjunto de opcodes do processador é limitado, então a quantidade de programas em assembly com um único opcode é finito. Eu testo todos eles pra ver se algum satisfaz os testes: se algum passar, ele é a solução, senão, eu repito o procedimento com todos os programas de tamanho dois, e assim por diante. Esse algoritmo garantidamente acha o menor programa que satisfaz os testes.

Um problema teórico com essa abordagem é que ela está sujeita ao problema da parada de Turing. Eventualmente, algum desses programas que você está testando pode entrar num loop infinito e você não tem como detectar isso. Uma solução é sair pela tangente: a maioria dos problemas da vida real podem ser resolvidos com modelos computacionais mais fracos que a máquina de Turing. Em assembly, nós poderíamos proibir os saltos pra trás, o que resolve essa limitação.

Essa técnica para achar o programa mínimo se chama Superotimização, e hoje em dia há vários papers sobre o assunto. Em 2003 eu escrevi um superotimizador para assembly Z80, então foi fácil adaptá-lo para fazer Single-person Pair Programming.

Single-person Pair Programming escrito em C

Vamos testar. Se eu tenho um único teste, 1->2, o programa acha três soluções mínimas, sendo uma delas ADD A,A. É claro, com esse único teste, ele não sabe se estamos somando um ou multiplicando por dois. Colocando dois testes, 1->2 e 2->3, ele já converge para a solução única INC A.

Complicando: e se quisermos um incremento módulo 8 (ou seja, a=(a+1)%8)? Podemos definir isso com os testes 1->2, 2->3 e 7->0. Colocando essa suite no programa, temos o resultado abaixo:

INC A
AND 7

Ou seja, o Single-person Pair Programming funciona direitinho!

Bônus!

O vencedor do Ricbit Jam #1 foi o Davi Costa, parabéns! Por uma questão de logística que envolve a China eu ainda não tive como compilar os resultados, mas fiquem de olho lá no meu twitter que em breve eu farei uma página com soluções e comentários.

Erdös e os logaritmos

Essa foi uma semana triste para a ciência, com a morte de dois grandes nomes: Edward Lorenz (criador dos atratores de Lorenz e criador da expressão "efeito borboleta"), e John Wheeler (orientador do Feynman e criador das expressões "buraco negro" e "buraco de minhoca"). Sempre que morre um cientista famoso, eu fico pensando que perdi a oportunidade de conhecê-lo pessoalmente pra agradecer pelo seu trabalho. Mas alguns cientistas eu consegui conhecer em vida, um deles foi o Paul Erdös.

Em novembro de 94, o Erdös deu uma palestra na USP, e, sabendo que ele estaria lá, fui correndo assistir. Pra quem não conhece, o Erdös foi o segundo matemático mais prolífico da história, só o Euler publicou mais que ele (embora anedoticamente ele seja mais conhecido pela brincadeira dos números de Erdös). É claro que um estudante de primeiro ano, como eu era, não tinha a menor chance de entender os detalhes da palestra que ele deu. Na verdade, o que me deixou impressionado foi que, em um dado momento, ele demonstrou que o upper bound de uma função era O(log log log log n), e eu pensei comigo mesmo que um dia ainda ia encadear logaritmos como ele fazia.

O tempo passou e eu ainda não consegui encadear quatro logaritmos, mas outro dia eu consegui pelo menos dois! Foi quando eu estava otimizando um código, e o seguinte problema apareceu no meio de um inner loop: achar a menor potência de 10 que seja maior ou igual a um inteiro dado. A implementação simples é a abaixo, vamos assumir que os inteiros em questão sejam de 64 bits, e que f(0)=1 por convenção:


unsigned long long simple_power10(unsigned long long i) {
  unsigned long long current = 10000000000000000000ULL;
  while (true) {
    if (current <= i)
      return current + !current;
    current /= 10;
  }
}

Esse código é razoavelmente rápido, roda em O(log n). O ideal seria rodar em O(1), fazendo uma tabela com os valores pré-calculados. Porém, uma tabela assim é inviável na faixa de valores de 64 bits. Um caminho mais esperto é usar uma busca binária para achar o valor correto:

if (i < 100) {
  if (i < 10)
    return 1;
  else
    return 10; 
} else {
  if (i < 1000)
    return 100;
  else
    return 1000;
}

Essa idéia é bem melhor, mas o problema agora é escrevê-la. Para a faixa de 64 bits, os ifs aninhados ficam muito longos, e um cara distraído como eu certamente iria errar alguma coisa na implementação. Felizmente, existe uma solução: template metaprogramming!

Usualmente pensamos em template metaprogramming para fazer cálculos em tempo de compilação, mas ele pode ser usado nesse caso também, pra gerar o código da busca binária. E ainda ganhamos uma vantagem, o código pode ser usado para qualquer tipo, não ficando preso ao unsigned long long, como no primeiro caso. Para implementar, começamos fazendo um template para gerar potências de dez:

template<class T, const int n>
struct p10 {
  const static T value = T(10) * p10<T, n-1>::value;
};

template<class T>
struct p10<T, 0> {
  const static T value = T(1);
};


Com ele em mãos, podemos fazer a busca binária propriamente dita:

template<class T, const int start, const int len>
struct compare10 {
  static T compare(const T x) {
    if (x >= p10<T, start + len/2>::value)
      return compare10<T, start + len/2, len/2>::compare(x);
    else
      return compare10<T, start, len/2>::compare(x);
  }
};

template<class T, const int start>
struct compare10<T, start, 1> {
  static T compare(const T x) {
    return p10<T, start>::value;
  }
};


E depois basta fazer o bootstrap, usando agora uma função pouco conhecida da biblioteca padrão do C++: o digits10, que volta a quantidade máxima de dígitos decimais que cabe num tipo qualquer.

template<class T>
T template_power10(T x) {
  return compare10<T, 0, numeric_limits<T>::digits10>::compare(x);
}


Abaixo, uma versão completa, já com benchmark, para comparar as duas versões. Na minha máquina, a versão com metaprogramming calcula um milhão de valores em metade do tempo da versão original. Isso é graças à complexidade reduzida da versão com metaprogramming, que é apenas O(log log n), com dois logaritmos, como eu queria demonstrar :)

Benchmark das duas versões

Ritos de passagem

Quase todas as comunidades possuem algum tipo de rito de passagem. Entre os cristãos, há o batismo, entre os judeus, o bar mitzva, entre as patricinhas, o baile de debutante. É claro que entre os programadores também existem ritos de passagem, sendo que o mais comum é o hello world. Nas universidades brasileiras da década de 90, um rito muito comum eram os números romanos.

Tanto a USP quanto a UFMG, nessa época, pediam aos alunos como primeiro exercício que escrevessem um programinha que fizesse a conversão de um inteiro para seu equivalente em números romanos. Parece uma tarefa extremamente simples, e é mesmo, embora seja apenas a primeira etapa de uma curva crescente de dificuldade (no meu ano, os exercícios seguintes foram o cálculo das forças em uma treliça, e um sistema para projeção de sólidos 3D).

Por outro lado, quanto mais simples a tarefa, maior a oportunidade para você exercer sua criatividade. Consta que um dos alunos da UFMG mandou o código abaixo como resposta para o exercício:

scanf("%d", &n);
if (n==1) printf("I");
if (n==2) printf("II");
...
if (n==3999) printf("MMMCMXCIX");


Quando eu vi essa solução, achei muito legal: é claro que não tem como o professor reclamar, afinal ela satisfaz ao enunciado proposto. Mas embora seja uma solução divertida, ela não é ótima. De fato, do jeito que está escrito, essa solução é apenas O(n).

Como fazer então uma solução que seja ao mesmo tempo sacana e ótima? Uma mudança simples seria criar um array de strings inicializado com os valores, assim você teria desempenho O(1). Por outro lado, simplesmente criar o array por extenso, como no caso acima, não tem muita graça. Mais legal seria criar o array em tempo de execução usando algum tipo de metaprogramming, como o template metaprogramming em C++.

Ainda assim, template metaprogramming já não é tão obscuro quanto costumava ser, muita gente já conhece o método. O que poucos conhecem é uma maneira de fazer metaprogramming usando apenas features presentes na linguagem C. A solução que eu acabei criando foi a abaixo, com um encantamento conhecido apenas pelos sacerdotes do ioccc, o preprocessor metaprogramming:

Números romanos usando preprocessor metaprogramming

O preprocessador do C não é turing-complete como os templates do C++, mas é suficiente para escrever rotinas mais simples. A minha solução usa um autômato finito, onde a transição de estado é feita através de um #include de si mesmo, e os estados são codificados bit a bit, em BCD.

Eu recomendo testar o código pra conferir que ele funciona, embora já avise de antemão que a compilação pode demorar um pouco. Pra ver o código gerado sem as diretivas do preprocessador, basta usar a flag -E do gcc.

Depois de terminado esse programinha, acabei ficando com mais uma idéia divertida de uso de metaprogramming, mas essa fica pra depois :)