terça-feira, 8 de abril de 2008

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 :)