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.

Ao Infinito e Além

O que há de comum entre Cantor, Gödel e Turing? Pelo menos duas coisas, e a primeira delas é que os três tentaram expandir os limites da matemática.

Cantor, por exemplo, queria contar até infinito. Essa é uma tarefa bem difícil: todos os que tentaram, cansaram antes de concluir! Mas o que o Cantor percebeu foi que, embora seja difícil contar diretamente, você pode contar até infinito indiretamente, desde que você saiba qual o significado real de "contar" alguma coisa.

O que significa, por exemplo, que você tem quatro maçãs? Na interpretação de Cantor, isso significa que você pode criar uma bijeção do seu conjunto de maçãs com um subconjunto dos números naturais, como na figura abaixo:

Se você criou uma bijeção do seu conjunto com o conjunto dos quatro primeiros naturais, então você efetivamente contou seu conjunto e concluiu que ele tem quatro elementos. O truque do Cantor foi perceber que você podia estender esse conceito, e criar bijeções com todos os naturais, ao invés de só algum subconjunto. E isso leva a resultados que são bem pouco intuitivos!

Por exemplo, o conjunto dos números pares. A intuição do iniciante é que esse conjunto tem a metade dos elementos dos naturais. Mas não é verdade, porque você pode construir uma bijeção entre os dois:


Para cada natural você tem um par correspondente, para cada par você tem um natural. Pelo raciocínio do Cantor, então esses dois conjuntos tem o mesmo número de elementos, o que também mostra que, pelo menos quando você está lidando com o infinito, a parte pode ser igual ao todo.

Indo além, o Cantor também mostrou que os Números Racionais também são do mesmo tamanho dos Naturais. Quem quiser repetir a demonstração original dele, pode tentar fazer o problema CANTON do spoj, que pede para você criar a bijeção. Uma maneira alternativa é utilizar uma construção inventada pelo Gödel: a cada racional p/q, você associa o natural 2^p3^q, e pra transformar o natural de volta numa racional, você usa a fatoração única que o Teorema Fundamental da Aritmética te garante.

Quando um conjunto tem o mesmo tamanho dos naturais, diz-se que ele tem cardinalidade aleph-zero, ou ainda, que é um conjunto contável. Mas todos os conjuntos infinitos são contáveis? Não! O Cantor também mostrou que o conjunto dos Números Reais é maior que qualquer conjunto contável dado, utilizando um método chamado argumento diagonal. Ou seja, os números reais são um tipo de infinito maior que o infinito dos naturais!

Agora, se os racionais são contáveis, e os reais não são, fica claro que os culpados por existir um infinito maior que o outro são os irracionais. Mas quais irracionais? Existem vários tipos deles também. Por exemplo, alguns irracionais podem ser construídos como raízes de polinômios de coeficientes inteiros (diz-se que esses são irracionais algébricos). Um exemplo é a razão áurea, que é a maior raiz do polinômio x²-x-1.

Porém, os irracionais algébricos são contáveis também. Basta utilizar novamente o mesmo truque do Gödel, dessa vez você associa cada coeficiente do polinômio a um expoente de um número primo. Um polinômio como x²+2x+1, por exemplo, escreveria-se como 2¹*3²*5¹.

Ora, se os irracionais algébricos são contáveis, então o que torna os reais maiores que os naturais são os irracionais não-algébricos (ou transcendentes). Mas mesmo entre esses existem vários tipos. O número Pi, por exemplo: você não consegue construí-lo como uma raiz de um polinômio, mas pode aproximá-lo com um algoritmo computacional, com tanta precisão quanto se queira. Dos números que podem ser aproximados por algoritmos, diz-se que são números computáveis.

Surpreendentemente, os irracionais computáveis são contáveis também. A maneira simples de visualizar isso é da seguinte maneira: se existe um algoritmo que aproxima o número, então esse algoritmo pode ser implementado numa linguagem qualquer (como nos garante a tese de Church-Turing). Agora, imagine que você criou um binário que implementou esse algoritmo, e esse binário tem X bytes. Se você fizer um hexdump do binario e imprimi-lo, você vai ter na sua frente um número hexa de 2X dígitos (que é um número natural grandinho, mas ainda assim um natural).

Mas se os irracionais computáveis são contáveis, quem são os não-contáveis? Existem números que não podem ser calculados por algoritmos? A resposta é sim, e um desses números é a constante de Chaitin. A construção da constante é curiosa. Nós vimos que, a cada algoritmo possível, existe um natural associado. Calcule então a seguinte somatória: para cada algoritmo existente (cujo natural associado é n), se o algoritmo pára, você soma 2^-n, senão não soma nada. Ora, essa somatória não pode ser calculada por um algoritmo, porque o Teorema de Turing garante que você não pode construir um algoritmo que detecta se outro algoritmo pára. A constante de Chaitin, então, é um número não-computável.

Mas os irracionais não-computáveis ainda não são o segredo do infinito real. Eu não consigo construir um algoritmo que aproxima a constante de Chaitin, mas no parágrafo acima eu consegui descrever exatamente do que a constante se trata. Os números que eu consigo descrever são números definíveis, e, (surpresa), eles são contáveis também. O argumento é ainda mais simples, se eu posso escrever um arquivo texto que contenha a descrição do número, o hexdump desse arquivo também vai associar a descrição a um número natural.

Então, os números que fazem o infinito dos reais ser maior que o infinito dos naturais são os números que não podemos construir, não podemos aproximar e não podemos descrever, ou seja, nem dá pra pensar sobre eles!

Se a essa altura sua cabeça deu tilt, então deixe-me concluir qual é a segunda coisa em comum entre Cantor, Gödel e Turing: os três ficaram doidos. De fato, Cantor achava que era um mensageiro de Deus, e terminou a vida num hospício. Gödel ficou paranóico com comida contaminada, e só comia o que a mulher preparava (quando a mulher ficou doente e internada num hospital, ele literalmente morreu de fome). E o Turing ficou tão deprimido que se matou, comendo uma maçã envenenada.

Há quem diga que existe relação causal entre estudar o infinito e ficar doido. Se você é desse tipo, hum, então era melhor não ter lido esse post :)

(Esse post é dedicado ao prof. Henrique, in memorian, líder do nosso grupo de doidos, que se reunia toda sexta na USP para estudar matemática, computação e ciências cognitivas. Três vivas aos que estudam o infinito, e além!)

A Meta-Assinatura

Como eu já disse antes, eu sou uma criatura que se empolga fácil. Ainda não tinha feito nem duas semanas que eu e o Fábio tínhamos entrado na Poli, e nós já estávamos procurando iniciação científica pra fazer. Depois de alguma procura, achamos uma legal: o Routo Terada estava procurando alunos pra estudar Criptologia.

O nosso medo inicial era que o Routo não quisesse aceitar dois alunos de primeiro ano, mas isso foi mais simples que esperávamos: "Ah, eu posso passar uma tarefa simples pra vocês. O Schneier acabou de publicar um algoritmo novo chamado Blowfish, vocês tem seis meses pra quebrar". É claro que não conseguimos quebrar o Blowfish, mas aprendemos um bocado no processo :)

Assinaturas digitais, por exemplo. O Isaac Newton, quando queria provar que algum manuscrito era dele, podia simplesmente assiná-lo com uma pena; mas o Stephen Hawking não pode fazer isso! Pra ele, o ideal são as assinaturas digitais. Para assinar digitalmente, você precisa de algum tipo de problema que seja difícil de resolver, mas que seja fácil de checar se foi resolvido (como a fatoração de números, ou o problema da sacola).

Um exemplo simples de como isso funciona me veio à mente algum tempo atrás, enquanto eu lia um livro do Hofstadter (se você não conhece o Hofstadter, tem uma entrevista dele para a rede Globo disponível online). Suponha que eu fiz uma grande descoberta e quero divulgar isso para o mundo:

O Ricardo sabe onde está o Bin Laden.

Embora tenha meu nome ali, qualquer um pode alterar e trocar o nome, então não tem como garantir que fui eu que escrevi:

O Wilerson sabe onde está o Bin Laden.

O método que eu bolei, e que na falta de nome melhor eu chamo de Meta-Assinatura, consiste em adicionar informação auto-referente à sua sentença:

O Ricardo afirma que sabe onde esta o Bin Laden, nesta sentenca com dezessete letras a, vinte e sete letras e, seis letras i, sete letras o, quatro letras u e uma letra x.

Confira que a contagem de letras está certinha. Dessa maneira, o Wilerson não pode trocar o nome na frase, pois se ele trocar, a contagem de letras vai mudar. Assim, a frase com meta-assinatura garante quem é o autor. Nesse método, contar as letras é muito simples, mas consertar a frase para o número de letras bater, é bem difícil (quer dizer, só com seis letras e algum esforço, até dá pra consertar a frase, mas se você usar o alfabeto inteiro na sua contagem, aí fica realmente complexo).

Para criar a frase com meta-assinatura, você não pode tentar procurar a solução por força bruta, porque demora demais. Uma solução mais rápida é criar uma função que conte as letras da sentença e troque os números correspondentes, e depois cruzar os dedos e torcer pro ponto fixo dessa função ser um atrator. O script em python abaixo faz isso, tomando o cuidado de detectar loops para não ficar preso:

Meta-Assinatura em python

Eu ainda não consegui assinar uma sentença usando todas as letras do alfabeto (ie, gerando um pangram), porque esse método não garante convergência. Se você conseguir, me avise :)