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.

Tatuagens em cadeia

Uma classe de artistas que eu admiro muito são os tatuadores, e por um motivo simples: eles não podem errar. Um desenhista pode usar borracha, um arte-finalista pode cobrir o erro com tinta branca, um artista digital pode apertar control-Z, mas o tatuador não pode fazer nada disso. Um escultor, se erra, tem a opção de jogar fora o bloco de pedra e começar de novo, mas o tatuador nem essa opção tem.

Exatamente por isso, tem um tatuador que eu conheço que se recusa a tatuar nomes de namorados. Tatuagens são permanentes, mas namoros são efêmeros: imagine namorar alguém que tem uma tatuagem com o nome do ex? Nesse caso, uma solução prática é reciclar a tatuagem e namorar alguém que tenha o mesmo nome do seu ex. Não é elegante, mas funciona.

Isso leva a conclusões curiosas. Veja o meu caso, por exemplo. Se eu tatuar ILA e minha esposa tatuar RICARDO, aparentemente ela estaria levando vantagem. É muito mais fácil arrumar outro Ricardo que arrumar outra Ila. Por outro lado, eu não precisaria procurar apenas Ilas, eu poderia arranjar uma Priscila ou uma Camila, bastando adicionar mais letras na tatuagem!

Isso naturalmente leva à pergunta: qual é o máximo de namoradas que um Serial Tatuator pode ter? Por exemplo, uma pessoa poderia ir de Ana para Iana e depois Fabiana. Será que dá pra achar uma cadeia de tatuagens de tamanho quatro? Cinco? Hora de fazer uma simulação!

Antes de começar, precisamos de um corpus de nomes. O jeito mais fácil de conseguir o corpus é escrevendo um crawler para um desses sites com nomes de bebês. Uma busca rápida e eu achei o Babyhold, que tem a vantagem de separar os nomes por sexo.

Script python para fazer crawling de nomes de meninas

O script retornou mais de 7100 nomes de meninas. Agora é só fazer um outro script que calcule a máxima cadeia de nomes. Como a quantidade de nomes não é tão grande assim, um algoritmo cúbico bobo dá conta do recado:

Script python para achar cadeias máximas

O script acabou achando várias soluções de tamanho seis, mas sem dúvida a seqüência mais curiosa foi a abaixo :)

Li -> Lin -> Elin -> Elina -> Angelina -> Angelina Jolie

Bônus!

Embora o algoritmo cúbico funcione bem para 7100 nomes, certamente há como otimizá-lo. Ao invés de fazer uma solução mais rápida, dessa vez eu vou abrir para os leitores enviarem suas soluções! Clicando no link abaixo você vai para o primeiro Ricbit Jam, feito com a engine do spoj. Ganha quem enviar a solução mais rápida nos próximos quinze dias. Não tem prêmio, mas o vencedor terá seu nome divulgado no próximo post :)

Ricbit Jam #1

Não adianta tentar mandar o programa em python acima, ele não acha todas as soluções e vai dar TLE no servidor do spoj. Mas você pode usar como base pra fazer a sua solução.

Newton e os universos paralelos

Neste último Natal fomos passar o feriado no sítio. Não precisei de muito tempo pra notar que eu não funciono muito bem nesse ambiente. Além de ser alérgico a quase todos os insetos, eu tinha apenas uma pequena noção de coisas básicas de quem vive por lá (como andar a cavalo, por exemplo). Isso nem me chateia, porque em compensação eu tenho outras habilidades que o pessoal do sítio não tem, como saber usar o Google Sky Map pra identificar as estrelas no céu.

Enquanto eu descansava numa rede, eu comecei a pensar como seria um universo paralelo onde o Ricbit é um matuto que entende tudo da vida no campo. Mas o pensamento não durou muito. Que coisa batida isso, se for pra imaginar um universo paralelo, vamos imaginar um mais original!

Sempre que pensamos em universo paralelos, tendemos a imaginar um muito semelhante ao nosso, onde apenas alguns detalhes mudam. E se imaginássemos um universo tão diferente que até as leis físicas são distintas da nossa? Por exemplo, como seriam as órbitas planetárias num universo onde a Lei da Gravidade não variasse com o quadrado da distância, mas sim com alguma outra expressão qualquer?

Esse exemplo é bacana por causa da sua importância histórica. Vamos voltar para o tempo do Isaac Newton, que o Asimov considerava o maior de todos os cientistas. É inegável que o Newton era um gênio, mas o que nem todo mundo sabe é que ele era briguento, vingativo, e costumava cometer o maior pecado que um cientista pode fazer: não citar as fontes.

Isso aconteceu com a Lei da Gravidade. Naquela época ainda não existiam as listas de discussão, então os cientistas conversavam por cartas escritas à mão. Certa vez, Newton recebeu uma carta do Robert Hooke, aquele que hoje é conhecido pela lei da molas. Nessa carta, Hooke dizia que suspeitava da existência de uma força da gravidade, que seria central (dependendo apenas da distância), e provavelmente proporcional ao inverso do quadrado da distância. Na carta ele ainda dizia que não sabia como provar essa suspeita.

Hoje em dia a razão para o Hooke não saber provar é clara. Pra conseguir provar, você precisa saber Cálculo, que o Newton já tinha inventado, mas ainda não tinha contado pra ninguém. Se o Newton fosse gente boa, ele teria respondido algo do tipo "eu sei provar, chega mais e vamos resolver juntos". Ao invés disso, ele ficou na miúda, e anos depois publicou o Principia Mathematica, onde ele usava o Cálculo para mostrar que a tal força central inversamente quadrática implica em órbitas que são seções cônicas.

O Hooke, compreensivelmente, ficou puto, e foi reclamar com o editor do livro, o Halley (o cientista, não o cometa). Depois de muito bate-boca, o Halley convenceu o Newton a colocar um prefácio onde ele dizia que a lei da gravidade tinha sido sugerida informalmente pelo Hooke, mas sem demonstração. Numa carta posterior ao Hooke, Newton ainda diria "se enxerguei mais longe, foi porque estava sobre o ombro de gigantes". Não era humildade, era trollagem. Conta-se que Hooke era baixinho e corcunda.

Mas o Newton não parou por aí. Certa vez, ele ficou como responsável pela mudança de prédio da Royal Society. Entre os quadros que precisavam ser mudados, estavam os retratos de todos os membros do grupo. Por uma coincidência não-explicada, o quadro do Hooke foi o único que se perdeu no caminho. Hoje em dia, ninguém sabe como era o rosto do Hooke, esse quadro perdido era o único retrato dele.

Nada disso teria acontecido se o Hooke soubesse Cálculo. E nós, para calcularmos nossas órbitas em universos paralelos, vamos fazer exatamente as contas que o Hooke desconhecia! Se você também não sabe cálculo, pule a caixa azul e vá direto pro resultado.

Consideremos um sistema com duas massas pontuais no vácuo. As contas em coordenadas cartesianas são meio chatas, então vamos usar coordenadas polares, centradas numa das massas. Nesse tipo de conta, o normal é usar um sistema de versores r e θ que giram junto com o planeta, mas a engenharia me deixou vícios difíceis de largar, então eu vou usar exponenciais complexas. A posição do planeta é a seguinte:



Note que r e θ na verdade são r(t) e θ(t), eu vou omitir o tempo pra não poluir as equações. A aceleração da partícula é a segunda derivada:




Agrupando os termos e lembrando que j² = -1, temos:



Até aqui tudo genérico. Vamos impor agora que a força seja central. Nesse caso, a componente transversal vale zero. Note que, com uma pequena manipulação algébrica, dá pra isolar uma derivada:



Aqui temos duas soluções. A primeira é sem graça, 1/r=0 se as duas massas estiverem infinitamente distantes, aí naturalmente a força transversal é zero. O segundo caso é mais legal:



Se a derivada é zero, então a integral é uma constante. Se você lembrar que r²θ é o dobro da área de um setor circular, então o que essa fórmula diz é que a taxa de variação da área de um setor é constante, ou seja, para um dado intervalo de tempo, ele percorre sempre a mesma área. Ora, essa é a segunda lei de Kepler! Pelo que concluímos, ela funciona pra qualquer força central, não só pra gravidade.

Vamos lidar com a componente radial agora. As massas são todas constantes, então vale que F=ma. Além disso, vamos introduzir uma variável u pra facilitar as contas:




Nós podemos isolar o tempo e deixar o raio em função do ângulo, usando uma mudança de váriaveis com a regra da cadeia.





Agora é só substituir na equação original:




Pronto! Esta é a equação geral das órbitas com força central. Para conferir se está certo, vamos colocar uma força inversamente quadrática. Note que as forças precisam ser negativas, pois, na nossa orientação, forças atrativas são negativas. Aliás, como eu não estou interessado em unidades, vou escolher constantes que cancelem.




Para resolver a equação diferencial, somamos a solução particular com as homogêneas. Uma particular é fácil, u=1. A homogênea todo mundo sabe de cabeça, é cos(θ) (vezes uma constante que depende das condições de contorno). Afinal, é a mesma solução do sistema massa-mola, do oscilador LC, e assim por diante.



Ahá! Esta é equação da seção cônica em coordenadas polares. Dependendo do valor de e, a órbita pode ser circular (e=0, como Vênus, aproximadamente), elíptica (e<1, como a Terra), parabólica ou hiperbólica (e=1 ou e>1, como os cometas).

Vamos tentar outro tipo de força, por exemplo, uma inversamente cúbica. Nesse caso:




Ou seja, a órbita agora é uma espiral.

Agora que temos a equação geral, podemos colocar a força que quisermos, e analisar a órbita resultante. O problema é que muitas fórmulas geram equações que não tem solução analítica, então eu fiz um scriptzinho em python pra resolver numericamente mesmo. Abaixo o script e os resultados para várias funções:

Script em python para resolver órbitas em universos paralelos

Para uma força inversamente quadrática, a órbita é circular, como esperado pela Lei da Gravidade.

Já uma força inversamente cúbica gera uma espiral. Essa força é fraquinha demais pra manter uma órbita, e o planeta vai aos poucos se afastando.

Uma força inversamente linear demora para estabilizar, mas acaba fazendo uma órbita circular também.

E uma força constante, independente da distância? Ela também termina numa órbita circular, o que pra mim faz sentido. O planeta se move até o ponto onde a força constante é igual à centrípeta.

Agora vamos sacanear e colocar uma força senoidal só pra ver o que acontece. Ele não diverge, mas faz uma órbita muito doida. Provavelmente é um atrator estranho.

A Lei de Ricbit

Já faz quinze anos que eu assino mailing lists, e uma coisa sempre foi constante em todo esse tempo: as flamewars. Aparentemente, listas na internet têm o poder de enfurecer os participantes e transformá-los em monstros incontroláveis. Ironicamente, essas brigas pela internet são tão previsíveis, que podemos até extrair padrões delas, como a Lei de Godwin.

Dia desses eu fiz uma observação sobre a natureza dessas brigas que os meus amigos apelidaram de Lei de Ricbit. A premissa é simples: as flamewars acontecem em qualquer lista de discussão, mesmo em listas sobre matemática e computação, onde supostamente os leitores são agentes racionais. Como isso pode ocorrer? Será que uma briga poderia acontecer mesmo se o Spock e o Data se encontrassem no Google Wave?

Data: Fiz uma medição surpreendente! Usando os sensores da Enterprise, eu medi os ângulos entre três estrelas distantes, e o resultado é que a soma dos ângulos do triângulo formado pelas estrelas não dá 180 graus!

Spock: Fascinante, mas temo que você tenha cometido um erro. Obviamente a soma dos ângulos de um triângulo é sempre 180 graus. Usando a lógica, eu posso provar que isso é sempre é verdade. Basta considerar uma reta paralela à base do triângulo:

Como você pode ver, os ângulos α e α' são alternos internos, e portanto iguais. O mesmo acontece com β e β', logo, a soma dos três ângulos é um ângulo raso.

Data: Como você sabe, andróides não cometem erros de medida. Os ângulos não somaram 180 graus por culpa da teoria da relatividade geral. Objetos tão massivos quanto as estrelas em questão deformam o espaço, o que explica a minha medida. Eu esperava mais dos vulcanos, certamente não se pode questionar os dados experimentais.

Spock: Eu não estava questionando a medida, estava questionando a conclusão. O que você mediu não era um triângulo de verdade, mas sim um outro tipo de figura geométrica de três vértices. Triângulos precisam necessariamente somar 180 graus: se não somarem, não são triângulos. Eu esperava mais dos andróides, certamente não se pode questionar a lógica.

Ricbit: Vocês dois vão ficar discutindo pra sempre, sem concluir nada, e eu vou mostrar o porquê. Muita gente acha que somente a lógica pode levar à verdade, mas isso não é inteiramente correto. A lógica, por si só, pode apenas produzir obviedades. A função real da lógica não é produzir verdades, mas sim transformar verdades. Para usar a lógica na prática, você precisa de verdades básicas, os axiomas, e a partir deles você deriva as verdades mais complexas.

Cada conjunto de axiomas determina um sistema formal. E é por isso que vocês nunca vão concordar, os dois estão partindo de axiomas diferentes! O Spock, ao dizer que alternos internos são iguais, assumiu implicitamente o Postulado das Paralelas do Euclides. Já o Data, ao dizer que o espaço é curvo, assumiu a negação do Postulado das Paralelas, gerando assim uma geometria não-Euclideana. Como os axiomas são diferentes, vocês dois vão discordar sempre, mesmo que usem a lógica perfeitamente.

Spock: Obviamente, eu sabia disso.

Data: Eu também.

Ricbit: Se sabiam, porque continuaram a discussão?

Spock, Data: ...

Ricbit: Olha, que tal esquecer tudo isso? Vamos jogar uma partida de Guitar Hero que é mais divertido.

Spock: Excelente! Eu fico com a guitarra, prefiro os instrumentos de corda.

Data: Onde que o Guitar Hero é instrumento de corda? Não tem corda nenhuma lá, só botão.

Spock: Ora, quando eu clico no botão ele faz som de instrumento de corda.

Data: Mas você não está excitando nenhuma corda, está só apertando um botão! Não tem como dizer que a guitarra do Guitar Hero é um instrumento de corda só porque ela produz som de corda.

Spock: Se for assim, então o piano também não é um instrumento de corda, afinal, você aciona teclas, e não cordas.

Ricbit: (facepalm)

Uma mesma proposição P pode ser verdadeira ou falsa, dependendo do sistema de axiomas que você adota. Mas como decidir qual sistema formal é o correto? A resposta é que você não decide qual é o correto, você escolhe qual é o correto. O único requisito de um sistema formal é que ele seja internamente consistente, fora isso, você escolhe o que for mais útil na ocasião.

O que vale para sistemas formais também funciona informalmente, mas ao invés de axiomas você tem definições. Qual a definição correta de "instrumento de corda"? É o que produz som de corda, ou é aquele onde você excita uma corda diretamente? Novamente, não existe um correto: você escolhe um deles e arca com as conseqüências da sua definição (se você achar que Guitar Hero não é instrumento de corda, então o piano também não vai ser).

Dito isso, agora já podemos enunciar a Lei de Ricbit, em sua forma original:

Lei de Ricbit: Se dois interlocutores discordam de uma definição, então eles vão discutir pra sempre, sem nunca concordar.

E como usar a Lei de Ricbit na prática? Fique de olho em definições conflitantes, que usualmente são implícitas. Por exemplo, um sinal claro de definição conflitante é a expressão "de verdade". FPGA não é hardware livre de verdade, como o Arduino. Java não é orientada a objeto de verdade, como Smalltalk. Quando a pessoa usa "de verdade", está te dizendo que a definição dele é diferente da sua, e aí é inútil prosseguir. E qual definição é a certa, a sua ou a dele? Tanto faz: desde que você seja consistente, pode adotar qualquer uma como verdadeira.

Lena e iLena

Existem algumas imagens que são icônicas. São tão conhecidas, que só com uma descrição simples você já sabe de qual imagem eu estou falando. O rosto do Che Guevara, a Marilyn com a saia levantada, o chinesinho parando os tanques: todos conhecem essas imagens.

Agora, se você for um estudioso do processamento digital de imagens, as suas imagens icônicas são outras. Para poder comparar algoritmos, nós usamos uma série de imagens padronizadas, como o mandrill e as pimentas. Mas, dessas imagens, nenhuma é tão conhecida como a Lena:

Lena

Há quem diga que a imagem da Lena ficou tão famosa entre os cientistas por ser uma imagem complexa o suficiente pra testar qualquer algoritmo: ela tem freqüências baixas e altas, texturas complexas, faixa dinâmica larga. A minha teoria é mais prosaica: se você vai ter que ficar olhando pra mesma imagem por meses, uma mulher bonita é melhor que um babuíno de nariz vermelho :)

Mas a imagem da Lena tem um segredo que nem todos conhecem. Quando eu descobri a origem da imagem, fiquei doido pra conseguir uma cópia original da fonte de onde essa imagem saiu. E depois de anos procurando, finalmente consegui:

Clique na imagem pra ver a versão completa, NSFW

Sim, a imagem usada por cientistas do mundo todo, na verdade, é um centerfold da Playboy!

Essa edição é a Playboy americana de novembro de 1972. Eu corajosamente a comprei no ebay, mesmo com os avisos que diziam "warning: pages may be sticky". Foi um ótimo negócio, o vendedor me vendeu uma Playboy usada, e eu comprei um pedaço da história da computação :)

A origem da imagem é curiosa. Conta-se que o pesquisador tinha um paper pra entregar no dia seguinte, e precisava de uma imagem com urgência. Ele acabou digitalizando a primeira revista que achou em sua mesa, a edição da Playboy com a Lena, que, curiosamente, também foi a edição mais vendida da história da revista. Ele não contou pra ninguém a origem da imagem, e por anos muitos usaram a imagem sem conhecer a história dela.

Isso acabou gerando um problema quando a Playboy descobriu que uma das suas imagens estava sendo copiada indiscriminadamente por aí. Inicialmente, ela tentou impedir o uso da imagem, mas depois acabou descobrindo que era boa propaganda, e hoje em dia a diretoria da revista faz vista grossa para o assunto.

Por outro lado, como a imagem ainda tem copyright, nunca se sabe se um dia a diretoria não vai mudar de idéia e vetar novamente o uso. Se você precisa de uma nova imagem de teste, agora tem uma nova solução! A minha esposa (ilustradora, modelo e atriz), fez um remake da imagem da Lena, e disponibilizou com a licença Creative Commons Attribution-Share Alike. E se você usar a imagem em algum paper, eu ainda posso fazer um peer review na faixa pra você.

iLena

Obviamente, a versão original dessa imagem só eu tenho :)