2006-07-31

Desempenho de algoritmos

Nautilus Depois de muita propaganda aqui está o artigo sobre desempenho de algoritmos. =)

Os programadores sabem que sempre há mais de um jeito de obter o mesmo resultado, mas cada um vai apresentar um desempenho diferente.

Uma das melhores sequências para a comparação de diferentes implementações é a sequência de Fibonacci. Primeiro por ser possível usar diversos algoritmos clássicos, como recursão e reiteração, segundo porque é uma sequência que existe naturalmente, o que a torna fascinante em si.

Caso alguém não conheça a sequência de Fibonacci, ela começa assim:

1 1 2 3 5 8 13 21 34 55 89...

Os matemáticos gostam de começar de zero (0 1 1 2 3...), o que não está errado e funciona da mesma forma – aliás fica mais fácil de calcular –, no entanto se considerarmos a essência natural da sequência em vez de seu comportamento matemático (Leonardo Pisano Fibonacci era naturalista e viajante antes de matemático, mais ou menos como Wallace e Darwin), veremos que não é possível que o zero participe da sequência.

Cada elemento é igual à soma dos dois elementos anteriores, e os dois primeiros valores são 1 e 1.

Recursividade


A primeira implementação da sequência de Fibonacci – e também a mais óbvia – é o algoritmo recursivo (em inglês recursion).

Recursividade, recursão ou recorrência é quando uma determinada função faz chamada a ela mesma (com parâmetros diferentes!). O exemplo clássico é o fatorial:

— Qual o fatorial de cinco (5!)?
— É cinco vezes o fatorial de quatro (5 x 4!).
— E qual o fatorial de quatro?
— É quatro vezes o fatorial de três (4 x 3!).

Para que a recursividade funcione, é preciso haver um valor base, que funcione como parada para a recursão. No caso do fatorial, o valor base é 0! = 1, portanto:

5! = 5 x 4! = 5 x 4 x 3! = 5 x 4 x 3 x 2! = 5 x 4 x 3 x 2 x 1! = 5 x 4 x 3 x 2 x 1 x 0!
5! = 5 x 4 x 3 x 2 x 1 x 1 = 120

Fibonacci como faz duas recursões simultâneas, precisa de dois valores bases, que são o primeiro e o segundo elementos, que valem um (1). A partir daí já podemos montar nosso algoritmo recursivo:

def fib(n):
if n < 2:
return 1
else:
return fib(n - 2) + fib(n - 1)


Então, fib(0) = fib(1) = 1. Os demais valores são calculados somando-se os dois anteriores.

Ao se executar este algoritmo, podemos ver que seu desempenho cai exponencialmente em relação ao índice do elemento que se quer calcular, ou seja, é péssimo. O gráfico pode ser encontrado aqui.

Então por que pensar em recursividade?

Há algumas boas razões para isso. Primeiro porque é a maneira mais simples de resolver problemas que podem ser resolvidos desta forma; segundo porque ao se aplicar outro método chamado memoization seu desempenho aumenta assustadoramente, na mesma proporção em que aumenta a quantidade de memória requerida para resolvê-lo.

Reiteração


Reiteração (em inglês iteration) é o próprio algoritmo recursivo que foi aberto de forma a não alocar mais memória e tempo de processamento do que o necessário.

O grande problema da recursividade é que cada vez que a função se chama, ela aloca mais espaço de memória para as mesmas variáveis já em uso. Na reiteração as mesmas variáveis e a mesma memória alocada são usadas para todos os cálculos, reduzindo o tempo de processamento.

A implementação reiterativa é a seguinte:

def fib(n):
a, b, c = 0, 1, 1
while c <= n:
a, b, c = b, a+b, c+1
return b


Ao analisarmos o gráfico, podemos de cara ver que este é bem mais eficiente que o recursivo devido às grandezas dos valores no eixo y (tempo). Outra coisa que podemos reparar é que seu desempenho cai aritmeticamente (o tempo cresce em linha reta), favorecendo seu uso mesmo para índices mais altos.

Observação: devido à palavra inglesa, é comum alguns programadores dizerem iteração em vez de reiteração, o que é um neologismo desnecessário.

Memoização


Realmente não há uma palavra (não que eu conheça) em português para isso, então adaptei a palavra inglesa memoization.

Memoização é uma técnica de programação usada quando há muita memória disponível (comum hoje em dia mesmo em micros pessoais) e é necessária a efiência. Consiste em fazer cache de valores conhecidos para não que não seja necessário calculá-los novamente.

Para algoritmos não-recursivos, não faz muita diferença, a menos que se use diversas vezes os mesmos parâmetros. No entanto para algoritmos recursivos o ganho é enorme, apresentando muitas vezes desempenho superior ao equivalente reiterativo.

Então – caso haja memória suficiente – a memoização traz duas vantagens: 1é possível usar o mais simples dos algoritmos (recursivo) e 2pode haver ganho de desempenho. Aliás, em se tratando de desempenho, o gráfico do algoritmo memoizado é quase linear com fator zero (no exemplo, oscilando por volta de 26µs).

Em Python usamos para memoização um técnica chamada «decoração», onde criamos um decorador que altera a função da forma desejada. Na verdade o decorador é uma metafunção ou classe que recebe como argumento a função original e devolve a função modificada.

O decorador para memoização em Python pode ser desenvolvido assim:

class memoize:

def __init__(self, f):
self.__cache, self.__func = {}, f
self.__doc__ = f.__doc__
for e in dir(f):
if not e.statswith('_'):
setattr(self, e, getattr(f, e))

def __call__(self, *args, **kw):
i = repr((args, kw))
try:
r = self.__cache[i]
except KeyError:
r = self.__func(*args, **kw)
self.__cache[i] = r
return r


Agora, basta reescrever a função recursiva com o decorador adequado:

@memoize
def fib(n):
if n < 2:
return 1
else:
return fib(n - 2) + fib(n - 1)


Matriz característica


A sequência de Fibonacci – assim como sequências semelhantes – pode também ser entendida como o resultado de uma determinada matriz elevada ao índice desejado. Basta então implementar suporte a cálculo matricial e calcular potência de forma binária.

Python possui um módulo chamado NumPy que dá suporte a matrizes, mas usa algoritmos muito lentos, portanto fiz minha própria implementação de matrizes, limitada a tratar matrizes 2x2 (que é o caso da matriz característica da sequência em questão).

A função ficou então assim:

matriz = Matriz_2x2(1, 1, 1, 0)
def fib(n):
return pow(matriz, n)[0]


Este algoritmo só não ganha em desempenho para a memoização e a função fechada. Seu desempenho cai logaritmamente, se monstrando muito eficiente para altos índices.

Função Fechada


A partir dos autovalores da matriz característica ou do cálculo discreto da recorrência obtemos a função fechada da sequência.

A matriz característica da sequência de Fibonacci apresenta dois autovalores: \lambda_1\frac{1+\sqrt{5}}{2} e \lambda_2=\frac{1-\sqrt{5}}{2}.

A função fechada é igual à subtração das potências dos autovalores pelo índice desejado dividida pela subtração dos autovalores: \frac{\lambda_1^n-\lambda_2^n}{\lambda_1-\lambda_2}.

O único problema deste algoritmo é que ele calcula Fibonacci a partir de zero (0 1 1 2 3 5...), e queremos a sequência natural (a partir de 1: 1 1 2 3 5 8...), então temos de incrementar o argumento antes de poder tratá-lo:

def fib(n):
n += 1 # incrementa o índice
sqrt5 = pow(5., .5) # raiz quadrada de cinco
autovalor = (1 + sqrt5) / 2, (1 - sqrt5) / 2
resultado = (
pow(autovalor[0], n) - pow(autovalor[1], n)
) / (
autovalor[0] - autovalor[1]
)
return int(resultado + .5) # arredonda o resultado


Como não há recursão, reiteração, cache e nem cálculo matricial, apenas álgebra linear, este algoritmo é altamente eficiente, sendo praticamente linear de fator zero.

No exemplo, tem um tempo de execução médio de 15,7µs até por volta do índice 46, depois sobe para 16,8µs até o índice 119, máximo do teste.

Ultimate Fibonacci


O nome é só uma brincadeira! Não é uma solução definitiva em absoluto!

Com consumo mínimo de memória, os algoritmos mais eficientes são o reiterativo e a função fechada.

Na verdade, como há uma queda aritmética de desempenho, o algoritmo reiterativo é mais eficiente que os demais apenas para índices baixos – nos exemplos até por volta do índice 21. Acima disso, o melhor algoritmo é a função fechada.

Obs.: a memoização foi descartada pelo alto consumo de memória.

Então, a idéia é usar o algoritmo reiterativo até onde ele ainda é mais eficiente e daí por diante usar a função fechada. O gráfico ficou assim.

Conclusão


O objetivo deste artigo foi apenas apresentar os diversos algoritmos clássicos para implementação de conjuntos discretos, sequências matemáticas.

A recursividade é a forma mais fácil de se implementar uma sequência, no entanto a menos eficiente – a menos que você tenha disponível muita memória, então pode usar a memoização para conseguir uma maior eficiência com a implementação mais simples.

A reiteração é a forma aberta da recursividade e o algoritmo que os programadores buscam, muitas vezes apenas porque desconhecem outras soluções.

A matriz característica é uma boa solução, se a potência de matrizes for implentada de forma binária (veja o método __pow__() da classe Matriz_2x2), caso contrário se torna muito ineficiente. De qualquer forma, a partir dos autovalores da matriz característica, é possível calcular a função fechada, que resolve a sequência por álgebra linear, método altamente eficiente e que não sofre muita variação ao longo da projeção cartesiana.

Esses algoritmos ainda podem ter desempenhos diferentes não apenas de máquina para máquina, mas também de um compilador/interpretador para outro.

Os gráficos de desempenho dos algoritmos se encontram em:



Códigos

[]'s

2006-07-26

Câncer no Mundo

Baal Está bem, está bem... sei que prometi que o próximo artigo seria sobre desempenho de algoritmos, mas minha indignação e a dor em meu coração não me permitem escrever sobre mais nada...

Sei que este artigo vai parecer antissemita – meus amigos judeus que me perdoem –, mas não sou antissemita!

Aliás, existindo um termo antissemitismo para indicar um crime contra o povo judeu, deveria haver também um termo antiarabismo (uma busca no Google me levou à Wikipédia) para representar crime contra os povos árabes e muçulmanos!

Também quero deixar bastante claro que sou contra toda forma de terrorismo. Os terroristas são criminosos e deveriam ser capturados, julgados e condenados por algum comitê internacional.

Agora, como posso chamar o que Israel está fazendo contra o Líbano, senão de terrorismo?

Dizem estar atacando o Hezbollah, mas na verdade estão bombardeando centros civis e a sede da força interina da ONU (segundo divulgação oficial da ONU hoje pela manhã, atingida premeditadamente) no sul do Líbano! Estão atacando o país, assassinando pessoas inocentes e indefesas.

Se vamos acabar com o terrorismo, temos de acabar primeiro com as duas maiores organizações terroristas do mundo: ISRAEL e os ESTADOS UNIDOS DA AMÉRICA.

2006-07-21

Paradigmas de programação

Poliedro Antes de escrever aquele artigo prometido sobre desempenho de algoritmos, vou escrever algo mais light. Este artigo aqui é voltado para meus amigos da faculdade (e o pessoal dos primeiros períodos) que curtem programação e teoria.

Paradigma de programação diz respeito à forma como o programador pensa para desenvolver seus códigos. Há diversos paradigmas (como é possível ver na Wikipédia), mas vou me limitar a falar sobre alguns mais comuns.

Ao contrário do que se pensa – e do que alguns programadores gostam de acreditar –, não é a linguagem de programação que determina o paradigma, mas a forma do programador pensar. Algumas linguagens facilitam o uso deste ou daquele paradigma, tornando-as boas escolhas para tais, mas a recíproca é pura ferramenta de marketing.

Vamos então dissecar alguns conceitos. =)

Programação procedimental



Erroneamente chamada de programação procedural (mal adaptado do inglês procedural programming), há conceitos distintos assim chamados.

Alguns autores usam «programação procedimental» como sinônimo de programação estruturada, o que não está errado, de forma alguma! Estes conceitos são arbitários. Estes autores se baseam no fato de que toda programação estruturada é necessariamente procedimental e, após a criação da programação estruturada, tornou-se raro (entre os bons programadores) a programação não-estruturada.

Já outros autores preferem usar a expressão com sentido justamente contrário: como sinônimo de programação não-estruturada, para contrapor a programação estruturada. E também não estão errados!

Na verdade, programação procedimental é um conceito um tanto mais abrangente do que programação estruturada.

É quando o programa em si é um procedimento – receita de bolo – a ser seguido pelo sistema para realizar uma tarefa.

A programação procedimental começa com o desenho de um fluxograma, que representa o passo-a-passo do procedimento desejado, depois este é traduzido a uma linguagem de programação qualquer.

A programação procedimental é geralmente usada em scripts ou como parte de estruturas de programação (veja a seguir).

Programação estruturada



Este é o paradigma de programação mais usado e já existe há mais de 30 anos. É o «O» da programação. =)

Nesta forma de pensar, o programa é uma estrutura que se subdivide em sub-estruturas mais simples. Então problemas complexos são dividos em problemas mais simples e estes problemas são dividos em problemas ainda mais simples. A combinação das soluções das etapas mais simples acaba solucionando as etapas mais complexas, ou melhor, mais abstratas.

A metodologia adotada pela programação estruturada é chamada top-down: começa definindo o problema de forma abstrata: «enviar um email para Fulano», então são verificados os passos necessários para realizar a tarefa. Cada passo é novamente divido em passos mais simples que frequentemente podem ter seus códigos compartilhados por outros passos, e assim sucessivamente até que o problema tenha sido reduzido a operações triviais.

No final você terá uma série de procedimentos simples, como «ouvir o soquete» e «enviar uma string», que interagindo resolvem o problema maior.

Cada estrutura, desde a mais simples até a mais abstrata, é chamada sub-rotina ou função e internamente aplica a programação procedimental. A diferença é que, como cada estrutura pode ser chamada diversas vezes, o programador salva muito código e tempo de depuração.

Programação funcional



Neste paradigma os problemas são tratados como funções matemáticas e são resolvidos por álgebra.

É usada a programação estruturada para organizar as funções, que recebem ou não argumentos e sempre retornam algum resultado. Estes resultados são combinados na busca de uma solução maior.

Por exemplo: para a solução de Fibonacci, a função fechada consiste na subtração das potências dos autovalores da matriz característica pela ordem do elemento desejado, divida pela subtração dos autovalores. Portanto teremos funções que efetuam as operações aritméticas comuns (subtração, potência, divisão, etc.), funções que retornam os autovalores e uma função mais abstrata que chama as demais funções, retornando o elemento desejado.

— Nossa!

Não se exalte! Este algoritmo estará no próximo artigo. =)

Este artigo aqui tem o objetivo apenas de apresentar os paradigmas enquanto forma de encarar a criação de códigos. Para maiores esclarecimento veja a Wikipédia.

Orientação a objetos



Esta é a menina dos olhos dos pseudo-programadores. Antes que alguém queira me crucificar ou fazer Judas de mim, deixem que eu me explique!

Orientação a objetos é, como qualquer paradigma, uma forma de pensar para criar algorismos – um recurso racional. Há linguagens que saltam o limiar e trazem este recurso para o código em si, o que é muito bom.

Mas não caia no conto do vigário!

Vocês ouvirão – ou lerão – muito que programar em Java é programar orientado a objetos. Quantas vezes vi códigos em Java que na verdade consistem de uma classe e, dentro dela, um procedimento que nem estruturado foi. Programação procedimental não-estruturada! Mas só porque o cara fez em Java ele acredita que esteja orientando a objetos.

Vamos lá... mito #1: «se a linguagem é orientada a objetos, o programa automaticamente também será».

Orientação a objetos é uma forma de pensar. Se você não consegue pensar orientado a objetos, você não consegue programar orientado a objetos. A linguagem de programação não vai fazer isso pra você.

Mito #2: «orientação a objetos e programação estruturada são exclusivas entre si».

Besteira. Orientação a objetos é dependente de programação estruturada. Se o código não for estruturado, ele automaticamente também não é orientado a objetos. Neste caso (como em outros) cada o paradigma é complementar ao anterior.

Mito #3: «não é possível usar orientação a objetos se a linguagem não for orientada a objetos».

Minha nossa! É tão difícil assim entender que orientação a objetos é um paradigma, ou seja, uma forma de pensar?! Você pode elaborar seu programa orientado a objetos e implementá-lo até mesmo em Assembly, se for bom o suficiente pra isso. Se não fosse assim, não seria possível existir linguagens orientadas a objetos, visto que, no final das contas, quem executa o programa é a máquina e os objetos executáveis são códigos em linguagem de máquina, uma sequência procedimental de comandos do microprograma do processador.

É claro, se você for esperto o bastante, vai escolher uma linguagem que possua nativamente os recursos de que precisa. =P


Esclarecidos os mitos, vamos à definição de orientação a objetos:

É quando o programador implementa não procedimentos, mas objetos que solucionem os problemas. Estes objetos possuem características que os definem e podem executar procedimentos simples chamados métodos. Os métodos de uso exclusivo de cada objeto são chamados privados, os de comunicação são chamados interfaces ou métodos públicos.

Da interação entre os objetos nasce a solução para o problema.

No entanto, na orientação a objetos o programador não define cada objeto. Ele cria as classes dos objetos e se preocupa com elas. Os objetos criados a partir de uma classe são chamados instâncias.

Na implementação dos métodos, o programador deve necessariamente usar programação estruturada, ou sua orientação a objetos vai pras cucuias.

Orientação a eventos



Um paradigma interessante: aqui há um ciclo principal (tradicionamente chamado mainloop) que se repete indefinidamente. Dentro deste ciclo, o programa fica aguardando a ocorrência de eventos e executa funções relacionadas a cada evento.

(Quem estiver prestando atenção verá que a orientação a eventos também pressupõe a programação estruturada.)

Um evento pode ser a pressão de uma tecla (ou sua soltura), um clique do mouse, uma conexão em um soquete ou a resposta da interface de um objeto. É interessante combinar orientação a eventos e orientação a objetos. O fim do ciclo principal – e consequentemente do programa – também é indicado por um evento.

A orientação a eventos é muito usada em daemons (serviços), jogos e na simples criação e manipulação de janelas.

Metaprogramação



Há duas definições de metaprogramação: a mais simples é chamada metacódigo, que nem é tanto um paradigma.

Metacódigo é um programa que gera como saída o código para outro programa. Nada de mais e não requer o uso de nenhum outros paradigmas.

Mas a metaprogramação de verdade pressupõe a orientação a objetos.

Metaprogramação é basicamente – mas não somente – o uso de metafunções e metaclasses.

Metafunções são funções que retornam outras funções (e muitas vezes também recebem funções como parâmetro). Com metafunções é possível criar funções dinamicamente, em tempo de execução.

Metaclasses são classes cujas instâncias também são classes, portanto com metaclasses é possível criar classes em tempo de execução.

Outras linguagens com paradigmas próprios também implementam metaprogramação de acordo com seu próprio funcionamento. Por exemplo, Lua usa metatabelas: tabelas que podem ser instanciadas como se fossem classes. As instâncias das metatabelas são tabelas (Walter me corrija se eu estiver errado!).

Programação extrema



Vou ser o mais sincero possível: não entendo lhufas de programação extrema. Ou quase nada...

Conheço algumas coisinhas. Por exemplo, sei que foi criada pelos programadores de Smalltalk (valeu pela dica, Walter!).

Uma coisa curiosa da programação extrema é a forma de fazer testes.

Tradicionalmente, o programador faz seus códigos e vai testando aos poucos, corrigindo eventuais falhas, e no final testa tudo, depurando inconsistências. Em programação extrema os testes são desenvolvidos antes do código (!!!). Depois o programador vai desenvolvendo o código de forma a que satisfaça os testes.

Quem estiver interessado em programação extrema, veja na Wikipédia. =)

2006-07-20

Alfred Russel Wallace

Alfred Russel Wallace Alguém já ouviu falar de Wallace? Foi o criador da teoria da evolução das espécies.

— Peraí... esse não foi Darwin?

Vamos esclarecer essa história...

Wallace lançou sua teoria da evolução das espécies antes de Darwin. Segundo o senso comum, a teoria de Wallace seria menos desenvolvída e/ou pesquisada do que a de Darwin, mas isso não passa de especulação a favor do darwinismo. Wallace viajou o mundo, pesquisou e desenvolveu sua teoria tanto quanto Darwin.

Aliás, sua teoria era muito similar à divulgada tempos depois por Darwin. Segundo a história oficial, por puro acaso (caro leitor, você ainda verá esta palavra novamente neste artigo); segundo quem possui um mínimo de discernimento, porque Darwin leu as publicações e Wallace e complementou sua própria obra.

Só que Wallace cometeu um simples erro. Não um erro científico, mas social: ele não corrompeu sua teoria, modificando-a para um formato que agradasse a sociedade científica materialista vitoriana.

Wallace também falou da seleção natural, da sobrevivência do mais adaptado e tudo mais que Darwin citou, mas um ponto chave diferenciava sua teoria da teoria de Darwin.

Darwin justificava as mutações pelo acaso enquanto Wallace acreditava que «para todo fenômeno inteligente deve haver uma causa inteligente».

No entanto que causa é essa? Não sabemos. Foi o que Wallace disse: «não sabemos». Ele também falou de Deus – sim, demonstrando uma boa dose de religiosidade apesar do ceticismo –, mas a base é «não sabemos».

Porém a comunidade científica é vaidosa e se julga onisciente, portanto jamais poderia aceitar tal argumentação.

Se algum ignorante seletivo quiser defender esta posição prepotente, gostaria de lembrar que Lord Kelvin alegou que a ciência era suprema e não sofreria mais alterações futuras, depois toda sua «ciência suprema» caiu por terra com os trabalhos de Einstein, Bohr, Caprapt e outros – ou alguém ainda quer aplicar Newton a partículas subatômicas?

Vamos agora às conclusões práticas resultantes da diferença das duas teorias.

Segundo Darwin, como as mutações ocorrem por puro acaso, uma mesma evolução não pode ocorrer duas vezes. Segundo Wallace, como há uma causa inteligente desconhecida por trás da evolução, uma mesma evolução pode se repetir.

Ou seja, considerando o darwinismo, o camaleão africano e a siba (um cefalópode) deveriam ter um ancestral comum, e as características comuns deveria ser compartilhadas por toda linhagem anterior às duas espécies até as mesmas – o que não é verdade. Vejam vídeos do camaleão africano e da siba e entenderão o que estou dizendo.

Fica aqui então um questionamento: será sensato considerar o conhecimento humano onisciente e atribuir ao acaso tudo aquilo que não compreendemos? Será que existe acaso?

2006-07-19

Fora da caridade não há salvação

Paiva Neto Participei há uns anos de uma iniciativa espírita – esclarecendo: não sou espírita! – chamada «Campanha da Sopa».

A Campanha da Sopa consistia no seguinte: os integrantes arrecadavam alimentos e agasalhos regularmente e, toda semana, na quinta-feira de madrugada, todos se juntavam, faziam um sopão com os alimentos e saiam pela noite distribuindo sopa a agasalhos para as pessoas que dormem na rua.

É claro que há criminosos e irresponsáveis dormindo na rua, mas a grande maioria é de pessoas cuja vida deu uma volta infeliz e precisam de ajuda para se reerguer – então providenciávamos esta ajuda.

Mais tarde descobri que havia mais três grupos de Campanha da Sopa em três outros dias da semana: outro espírita, um católico e um de ateus.

Fiquei curioso, pois a semana não tem apenas quatro dias e há muitas outras entidades religiosas que poderiam estar preenchendo as lacunas. Como tenho amigos de diversas religiões – evangélicos, judeus, muçulmanos, hiduístas, etc. – procurei por estes, questionando sobre a Campanha da Sopa.

Claro, tive respostas das mais diversas, mas a mais frequente foi esta: «basta que esses necessitados se convertam a nossa religião e receberão ajuda».

Isso realmente me aborrece.

O que é mais importante: a conversão ou a caridade?

Se você, leitor, for cristão, pergunto então: o que é mais compatível com a mensagem cristã?

Se alguém tiver a falta de caráter de responder que é a conversão, sugiro que leia o capítulo XIII da 1ª carta de São Paulo Apóstulo aos Coríntios.

Todos têm suas verdades absolutas, a minha é esta: «fora da caridade não há salvação».

2006-07-18

Incompetência

Varig Por toda parte vejo pessoas – brasileiros – rindo e fazendo piadinhas com a «queda» da Varig. «Esses empresários brasileiros são mesmo uns incompetentes

Aliás, o brasileiro é mesmo incompetente, né?

Fica tão preocupado em difamar um presidente incompetente, eleito por eleitores incompetentes, que esquece que o governo brasileiro é um parlamentarismo disfarçado e que o presidente nada mais é do que um bode expiatório das cafagestagens dos verdadeiros governantes.

Ninguém confia na tecnologia incompentente dos brasileiros, e todos importam tecnologia estrangeira – como é bonito e reconfortante ver a janelinha colorida daquele sistema operacional norte-americano, portanto, competente!

Então, os incompetentes brasileiros entregam o controle de suas empresas aos gringos competentes, que podem levar nosso país aos céus!

Enquanto isso fico eu, brasileiro incompetente, fazendo críticas que só servem para a diversão do leitor.

Hoje pela manhã vi uma reunião pública da diretoria da Varig. Eles encontraram uma forma de salvar a empresa, vendendo-o para outra empresa brasileira – portanto incompetente – capaz de saldar as dívidas. A votação saiu assim: os empregados – incompetentes – e os acionistas brasileiros – incompetentes – votaram por salvar a empresa; os acionistas estrangeiros – portanto competentes – votaram pela falência da empresa e, consequentemente, pelo aumento do desemprego no país e pelo não pagamento dos direitos trabalhistas de seus empregados. Como os estrangeiros são mais competentes, seu voto tem mais peso, e a proposta caiu por terra. =(

Pois é, caro amigo, você que tanto idolatra a competência estrangeira e faz piada da falência de empresas brasileiras é entre todos o maior dos incompetentes.

2006-07-17

Metaprogramação

Nautilus Certa vez conversando com o Fernando, um colega meu da faculdade, ele me disse que deveria haver um paradigma de programação mais avançado do que orientação a objetos. Então comentei com ele sobre orientação a eventos e metaprogramação – esqueci do paradigma funcional, ó que vergonha!

Resolvi então falar sobre metaprogramação.

Vamos compreender o que significa este meta: o que é metalinguística? É o estudo liguístico da própria linguística! Por exemplo, um dicionário é um livro metalinguístico – a linguagem usada para falar da linguagem. =)

Entendendo o uso do prefixo (na verdade um radical), vamos agora entender o que é metaprogramação.

Há dois conceitos distintos mas relacionados.

O primeiro conceito é o de metacódigo: é o código que gera como resultado outro código. Neste caso, metaprogramação é a criação de metacódigo.

Vou dar um exemplo em Shell script:

#!/bin/bash
# criaget.sh

ARQ="get.sh"

echo -n "Informe o mirror: "
read MIRROR

echo -n "Informe o caminho para o arquivo: "
read CAMINHO

if [[ "${MIRROR:0:4}" != "http" && "${MIRROR:0:3}" != "ftp" ]]
then
MIRROR="http://$MIRROR"
fi

if [[ "${MIRROR%/}" = "${$MIRROR}" ]]
then
$MIRROR="${MIRROR}/"
fi

cat > $ARQ <<-EOF
#!/bin/bash

wget -c ${MIRROR}${CAMINHO}.md5
wget -c ${MIRROR}${CAMINHO}

cat *.md5 | md5sum --check
EOF

chmod +x $ARQ

exit


Este programa irá pedir um mirror e um arquivo neste mirror, e irá gerar um código (get.sh) que, quando executado, tentará baixar o arquivo informado, fazendo uma verificação de MD5.

Não é um conceito difícil, mas não é desse tipo de metaprogramação que quero falar. =P


Outro conceito de metaprogramação é quando elementos que geralmente são definidos na codificação, como funções e classes, são definidos em tempo de execução por outro elemento semelhante.

Ou seja: funções que retornam funções e classes cujas instâncias são classes.

Vamos a um exemplo em Python:

def inteiro(f):
def func(*args, **kw):
resp = f(*args, **kw)
return int(resp + .5)
return func


Olha só: esta função recebe uma função como argumento e retorna outra função. Por exemplo:

>>> def pre_fib(n):
n += 1
return (
pow(
(1. + pow(5., .5)) / 2.,
n
) - pow(
(1. - pow(5., .5)) / 2.,
n
)
) / pow(5., .5)

>>> fib = inteiro(pre_fib)
>>> [fib(x) for xrange(10)]
[1, 1, 2, 3, 5, 8, 13, 21, 34, 55]


Esta é a fórmula fechada de Fibonacci, no entanto, como trabalha com números de ponto flutuante, os valores trazem erros de aproximação que precisam ser solucionados por conversão para inteiros.

A função inteiro() pega a função pre_fib() como parâmetro e retorna uma função que faz a mesma coisa que a original, mas traduzindo a resposta para inteiro. Portanto inteiro() é uma metafunção.

Python traz ainda um açúcar sintático chamado «decorador», que reduz a quantidade de código ao programar com metafunções. Por exemplo, a função acima poderia ser reescrita usando inteiro() como decorador:

@inteiro
def fib(n):
n += 1
return (
pow(
(1. + pow(5., .5)) / 2.,
n
) - pow(
(1. - pow(5., .5)) / 2.,
n
)
) / pow(5., .5)


Observação: classes podem ser usadas também como decoradores, desde que suas instâncias sejam «executáveis» (callable) – futuramente escreverei um artigo sobre memoization, então vou falar um pouco mais sobre isso.

Vamos agora falar de «metaclasses».

Metaclasse é uma classe que retorna como instância outra classe – é um recurso para criação de classes em tempo de execução (e/ou para salvar horas de codificação). =)

Em Python, metaclasses devem ser filhas (herdeiras) de type e o construtor deve receber como argumentos cls (referência à própria instância), name, bases e dict, assim como a função/classe type(), que cria tipos/classes dinamicamente.

Vamos ao exemplo proposto pelo próprio BDFL:

class autoprop(type):
def __init__(cls, name, bases, dict):
super(autoprop, cls).__init__(name, bases, dict)
props = {}
for name in dict.keys():
if len(name) > 5:
if name.startswith("_get_") \
or name.startswith("_set_") \
or name.startswith("_del_"):
props[name[5:]] = 1
for name in props.keys():
fget = getattr(cls, "_get_" + name, None)
fset = getattr(cls, "_set_" + name, None)
fdel = getattr(cls, "_del_" + name, None)
setattr(cls, name, property(fget, fset, fdel))


Esta metaclasse cria propriedades (atributos que chamam métodos) automaticamente em suas instâncias. Um exemplo:

class X:
__metaclass__ = autoprop

def __init__(self, x=None):
self.__x = 0
if x is not None:
self._set_x(x)

def _get_x(self):
return self.__x

def _set_x(self, v):
v = int(v + .5)
if v >= 0:
self.__x = v

def _del_x(self):
raise TypeError, "Nao eh possivel remover x"


Esta classe é uma instância de autoprop (não filha). Veja o que acontece com suas próprias instâncias:

>>> a = X()
>>> a.x
0
>>> a.x = 2.1
>>> a.x
2
>>> a.x = -4
>>> a.x
2
>>> del a.x
> del a.x

Traceback (most recent call last):
File "<pyshell#37>", line 1, in -toplevel-
del a.x
File "<pyshell#30>", line 14, in _del_x
raise TypeError, "Nao eh possivel remover x"
TypeError: Nao eh possivel remover x
>>> a.x
2


A propriedade x interceptou todas as chamadas a a.x e chamou os métodos convenientes (_get_x(), _set_x() e _del_x()). Para isso, a propriedade x precisou ser definida antes pela função property(). Onde esta função foi executada? Ela não existem na definição da classe X...

Exatamente: ela foi executada no construtor de autoprop, atribuindo assim a propriedade x – criada dinamicamente – a sua instância X.

Se alguém ficou em dúvida, comente este artigo e responderei!

PS: Walter, que tal escrever um artigo sobre metatabelas em Lua?

2006-07-14

Atualizações

ReciclagemGostaria novamente de sugerir aos amigos que estão acompanhando meu blog via RSS que eventualmente visitem a página via WWW, pois estarei fazendo atualizações de conteúdo.

Por exemplo, caso seja do interesse de alguém, acrescentei alguns links na barra vertical do lado direito da página de sítios onde é possível encontrar pacotes .tgz pré-compilados para Slackware.

Para instalar, basta verificar em /var/log/packages/ se o pacote já não está instalado. Se não estiver, como superusuário execute:

# installpkg ${nome_do_pacote}.tgz


Se estiver instalado, é só atualizar:

# upgradepkg ${nome_do_pacote}.tgz


Espero que seja útil. =)

2006-07-07

Python

Python Gente, Python é minha linguagem do coração. Comecei a programar com BASIC (MS XColour-BASIC), depois Assembly de ZX-80, Perl, C e finalmente Python. Aprendi outras linguagens depois disso, mas Python ficou no coração.

Traz nativamente conceitos avançados, como orientação a objetos e metaprogramação, mais algumas peculiaridades sintáticas de deixar qualquer programador com água na boca.

Vou dar um exemplo bem básico, o famigerado Hello World!!!. Em Java:


class HelloWorld {
public static void main(String[] args) {
System.out.println("Hello World!!!");
}
}



Em C:


#include <stdio.h>

int main() {
puts("Hello World!!!");
return 0;
}



Agora em Python:


#!/usr/bin/env python

print "Hello World!!!"



E esta relação de simplicidade se estende para outros procedimentos.

Python é uma linguagem interpretada e interativa, o que facilita o desenvolvimento. Você pode iniciar um prompt do interpretador e testar os comandos, ou criar um script para interpretação indireta.

Outra alternativa é, assim como Java, compilar os códigos para bytecodes, que usam como máquina virtual o próprio interpretador.

As plataformas que dispõem de Python são Windows, GNU/Linux, Unix, MacOSX, Amiga, Palm Handhelds e celulares Nokia.

A WikiPédia traz uma ótima descrição da linguagem e o curso Python na Prática traz uma lista de vantagens da linguagem.

Apesar de ter dito que tentarei evitar falar de Informática, ainda vou falar muito de Python. =)

2006-07-06

RSS

RSS Para os amigos que estão começando a acompanhar meu blog via RSS, vai aqui um aviso:

Vejam os posts via HTTP com frequência!

Digo isso porque estou atualizando os posts regularmente, por dois motivos:

1) Não tenho muito tempo para revisar os artigos antes de publicá-los, pois estou sem Internet em casa, então de tempos em tempos encontro algum erro - e se alguém me sugerir alguma alteração no artigo e eu concordar, pode contar que farei.

2) Às vezes me lembro de algum link interessante que poderia enriquecer o artigo, então atualizo acrescentando-o.

Está avisado. =)

O Código Da Vinci... de novo

Da Vinci Code Outro assunto que quero evitar é o tal do «Código Da Vinci» de Dan Brown.

Não aguento mais falar ou ouvir falar nisso. Mas há duas coisas referente ao «Código Da Vinci» que não consigo engolir, então vou escrever este post simplesmente para desabafar. =P

A Língua Pura



No livro, Dan Brown se refere à língua inglesa como a «língua pura», por não ter sofrido influência do latim.

Então, se o sr. Brown quer uma língua pura, vai ter de se virar sem algumas palavras. Pra citar só umas poucas: abominate, act, accept, adapt, advance, air, animal, beast, captive, car, cat, charity, color, comment, copy, create, data, declaim, delicate, describe, doctrine, extra, family, fortune, fragile, front, grace, imitate, invoke, latex, liberty, material, maximize, media, mille, misery, move, nature, navigate, normal, object, offer, optimize, planet, poetry, post, prepare, prompt, rational, rect, relax, republic, respect, script, state, status, subject, super, theater, title, transfer, tribute, ultra, village, vote e todas as palavras terminadas com -ation e -ator, para citar só as mais óbvias.

É tudo mentira



Por outro lado, os opositores de Dan Brown estão partindo para o exagero: usando o fato de Dan Brown ter «mentido» (palavra forte) para endoçar mentiras inversas.

Confúcio dizia que uma verdade não se torna mentira por ter vindo da boca de um mentiroso.

Como disse um representante da Santa Sé Católica num programa do National Geographic Channel, se Jesus Cristo foi ou não casado, isso não diminui (ou não deveria diminuir) a fé dos cristãos. O celibato foi uma idéia defendida por São Paulo Apóstolo.

Se Jesus foi ou não casado, não há menção bíblica. Por um lado, era muito, muito estranho um judeu não ser casado, o que assustaria e afastaria possíveis seguidores; por outro, Jesus foi seguidor de João Batista, que era essênio, e os essênios eram celibatários. Portanto não há nada que diga se Jesus foi ou não casado.

É uma discussão infértil.

Outra coisa: a importância dos Evangelhos Apócrifos e os cristãos gnósticos.

Havia mais de trinta evangelhos. Os Evangelhos Canônicos não foram escolhidos por sua veracidade contra os apócrifos, mas porque eram os mais compatíveis com as crenças que o imperador romano queria priorizar, ou seja, o culto a Mitra (já sincretizado com o culto a Apolo) e o culto a Ísis - não o cristianismo.

Pronto, desabafei. =)

2006-07-05

Prólogo

Sempre que converso com algum amigo blogueiro, este sempre me sugere criar um blog meu, no entanto não tinha pensado a sério sobre o assunto até agora.

Dois pontos me passaram então pela cabeça: qual ferramenta usar e falar de quê.

A princípio comecei a criar minha própria ferramenta de blog, usando Apache2, Python 2.4, MySQL, mod_python, SQLObject e htmltmpl (um porte para Python do módulo HTML::Template para Perl.org). Não foi difícil, o que me atrapalhou foi encontrar onde hospedar isso.

Então, em nome da má vontade, resolvi abandonar meu pequeno projeto e hospedar no BlogSpot mesmo.

Quanto ao foco, não quero cair no lugar comum e falar de Informática. Sei que vou acabar falando sobre Informática, principalmente programação e Software Livre, porque trabalho com isso, vivo disso, então será inevitável, mas juro que vou tentar falar de assuntos gerais. =)

Bem, por enquanto é só isso mesmo...