segunda-feira, maio 29, 2006

O Que Há com a Microsoft?

Faz algum tempo que está acontecendo um fenômeno estranho com a Microsoft, estranho não porque está acontecendo, mas porque ninguém parece estar prestando atenção nele...

Tudo começou quando a Microsoft anunciou, a coisa de um mês atras, que ia adiar o lançamento do Windows Vista, uma queda no preço das ações nessas condições é normal e até esperado, e como esperado, aconteceu. Daí, a empresa anunciou uma reestruturação da divizão do Windows (apesar de todos saberem que não é bom mexer no time de projetos em execução), e no dia seguinte veio a grande pérola: O Bill Gates anunciou em uma reportagem (com todo o jeito de comprada) que iria utilizar as patentes de software da Microsoft contra o Linux.

Este terceiro acontecimento me pegou de surpresa. (Até que os outros dois eram esperados :). ) A Microsoft tem evitado trazer atenção para a forma como as patentes de software são usadas, provavelmente para melhorar suas chances de aprovar estas patentes na Europa. Citar as patentes de software me pareceu um último recurso, bastante extremo, para desviar a atenção dos acionistas de algum problema. E um problema bem grave.

Bom, neste dia eu comecei a acompanhar o valor das ações da Microsoft. Como era de se esperar, elas estavam caindo já a três dias (desde o adiamento do Vista). Nada de mais, mas elas continuaram caindo, e caindo, e recuperando um pouco, mas voltando a cair... O resultado é que a queda chegou a quase 20%. Agora elas se recuperaram de novo, não sei se vão voltar a cair ou não.



A figura acima mostra o preço das ações desde o começo de 2006 até o dia 26 de Maio (sexta) (fonte: yahoo!). (O tempo está em segundos desde o começo de 1970, quando eu conseguir um programa que me faça este gráfico de forma correta e fácil, eu corrijo isso.) As bolsas do mundo inteiro deram uma oscilada na semana do dia 26 de Maio, mas isso mal aparece no gráfico, essa variação toda é quase exclusividade da Microsoft.

Bom, mas como eu já disse, o estranho não é nem tanto que as ações estão caindo. O que é estranho mesmo é que ninguém está comentando isso. Não é todo dia que uma empresa do tamanho da Microsoft oscila desta forma, e não aparece nenhuma menção nos jornais. Nem a imprensa especializada está dando bola, nem mesmo slashdot comentou! Como pode?

segunda-feira, maio 01, 2006

IA: Busca de Soluções

Há duas formas bastante distintas de se resolver um problema matemático. Por exemplo, para resolver a equação x = 3x + 1, pode-se aplicar as propriedades da igualdade, e subtrair 3x dos dois termos: -2x = 1, e depois divir-los por -2, obtendo x = -1/2. Outra possibilidade é testar vários valores de x na equação, até encontrar algum que a satisfaça. Este segundo método, em que soluções são testadas até se encontrar a desejada, é denominado "busca de soluções", e é o que normalmente é utilizado em inteligência artificial.

Sair tentando valores de x a esmo até encontrar algum que sirva não parece uma forma muito boa de resolver o problema, e não é mesmo. Mas em alguns casos, ninguém conheçe outro jeito, assim, a única alternativa é escolher bons valores para testar. Cria-se, então um algorítmo para gerar valores com maior probabilidade de serem os desejados. Informalmente, estes algorítmos são denominados "heurísticas" (formalmente, só alguns deles são heurísticas, os outros são pseudo-heurísticas).

Agora, para melhor projetar uma heurística, o desenvolvedor tem que saber quais são os possíveis valores que a solução pode assumir. O conjunto destes valores é chamado de "espaço de busca". Alguns dados sobre o espaço de busca são extremamente relevantes. São eles o número de dimensões deste espaço, ou seja, quantos valores são independentes na solução, ou, de forma mais fácil para um programador, é nescessário um vetor de que tamanho para representar a solução? E para cada dimensão, é importante saber se os valores são contínuos (que só podem ser representados por números reais) ou discretos (que podem ser representados com números inteiros) e se são limitados ou não, ou seja, se eles estão dentro de um intervalo bem conhecido ou se vão (desde ou) até infinito.

Por fim, outra característica extremamente importante de cada dimensão é se ela tem uma topologia ou não. Dizer que um conjunto tem uma "topologia" é dizer que os elementos deste conjunto têm uma seqüência, por exemplo, os números inteiros têm topologia, assim, entre 1 e 4 existem os números 2 e 3, já o endereço dos entrevistados em uma pesquisa não tem topologia (a não ser que eles morem em Brasília). Em geral, as pessoas usam números (ou vetores) para representar valores de conjuntos com topologia, e nomes para conjuntos sem topologia, e, em geral conjuntos sem topologia são limitados e discretos (ou seja, finitos).

Agora, se você quer encontrar uma solução para algum problema, você precisa avaliar cada ponto do espaço de busca, ou seja, dar uma "nota" para eles. No caso da equação acima, poderia-se dar uma nota zero a pontos que não resolvem a equação, e 1 a pontos que resolvem a equação (só x = -1/2). De forma alternativa, poderia-se subistituir o x dos dois lados da igualdade, e usar a diferença (o módulo dela) entre os dois valores como nota (eu não disse que notas altas são melhores que baixas). É fácil perceber que a segunda nota contém muito mais informação do que a primeira (sim, informação é algo que se pode medir, mas isso dá uma seqüência inteira de artigos), e em geral, quanto mais informação se coloca na nota, melhor. Isso é fácil de ver neste caso, onde com a segunda nota pode-se saber se a busca está se aproximando ou afastando da solução observando se a nota aumenta ou diminui, já com a primeira nota, isso não é posível.

Depois de cada ponto do espaço de busca avaliado, o resultado é uma "superfície", onde as soluções são os ponto mais altos (ou mais baixos) desta superfície. Estes pontos têm a característica de que todos os seus vizinhos têm nota menor (ou maior) do que a sua, o que torna fácil identificá-los. Mas isso também pode acontecer com outros pontos, mesmo sem eles serem soluções, como na figura abaixo:

Os pontos A, B e C da figura acima têm a característica de ter maior nota do que seus vizinhos. Pontos com esta característica são chamados de "máximos", A e C são "máximos locais", mas só o ponto B é solução, chamado de "máximo global". De forma equivalente, há também 3 mínimos neste gráfico, sendo um deles global e dois locais. Existe um grande número de algorítmos que resolvem problemas em que todos os máximos (ou mínimos) locais são também globais. Estes algorítmos costumam ser rasoavelmente rápidos e símples. Mas há muito poucos algorítmos que resolvem problemas com máximos não globais, e estes costumam ser lentos e não garantir que encontrem a resposta. Alias, em geral para garantir que um máximo seja global em um problema em que podem haver máximos locais é preciso testar todos os pontos do espaço de busca.

Pronto, fim (ou quase) da teoria. Nos próximos artigos eu vou ser mais prático e falar de algorítmos e implementações... Até lá.

quarta-feira, abril 26, 2006

IA: Inteligência Artificial

Por falta de assunto, e aproveitando a deixa dos algorítmos genéticos, vou falar um pouco mais sobre inteligência artificial. Agora e em artigos seguintes.

Mas o que é esse negócio de "inteligência artificial"? Bom muita gente diz que a escolha desse nome não é boa, porque gera discussões sobre se computadores podem pensar, sobre o que é inteligência, sobre se os computadores vão querer "liberdade" ou até destruir a humanidade no futuro e mais. Bom, sobre a liberdade, é fácil: computadores querem o que a gente manda eles quererem, e não existe como mandar eles quererem "liberdade" (Afinal, a "liberdade" existe?). Quanto a todas as perguntas sobre computadores pensarem, Djigstra, um dos maiores pesquisadores da computação (talvez o maior até hoje) resumiu todo o debate em uma frase excelente (tradução minha):

"Perguntar se computadores podem pensar é tão útil quanto perguntar se submarinos podem nadar"

Até onde eu sei, submarinos não nadam. Mas isso leva a um debate sobre o que é nadar, que é exatamente igual ao debate sobre o que é pensar. E isso não muda a forma como os submarinos se locomovem. Mas eu ainda não expliquei o que é a inteligência artificial.

Inteligência artificial é o ramo da computação que se preocupa em resolver problemas difíceis. Símples assim, e sem nenhuma questão filosófica. A teoria da computação (outro ramo) define o que é um problema difícil (superpolinomial), mas aqui basta dizer que problemas difíceis são os que gastariam muita memória ou tempo de processamento para serem resolvidos, no sentido de se encontrar a Solução que é a melhor resposta possível. Assim, a inteligência artificial é cheia de respostas aproximadas e algorítmos que não funcionam todas as vezes.

Agora, essa definição não é aceita universalmente (na verdade, eu acabei de criar...). Existem outros nomes para o ramo da computação que tenta resolver problemas difícies, que estudam a mesma coisa, mas cujos estudiosos não gostam de dizer que estudam inteligência artificial. Existem também outros pesquisadores que não estudam problemas difíceis, mas gostam de dizer que estudam inteligência artificial. Essa definição, porém é mais correta do que errada, o que na falta de uma definição universal é bom o bastante :)

Por trabalhar com problemas que não podem ser resolvidos no sentido clássico do termo, a inteligência artificial é um tanto diferente da computação clássica. Na computação clássica, antes de tentar resolver um problema, deve-se primeiro saber se uma solução existe, então cria-se um algorítmo capaz de encontrar esta solução, e depois se implementa este algorítmo. Na inteligência artifical, é comum não se preocupar com a existência ou não de soluções, e boa parte das vezes não se sabe se um algorítmo vai "resolver" o problema antes de implementá-lo. Isso mesmo definindo-se "resolver" como encontrar uma resposta aproximada que é boa o bastante.

Bom, mas esse artigo já tá grande o bastante, volto no assunto depois. Ainda falta falar sobre a busca de soluções de forma teórica, e vou para a prática falar de algorítmos bem conhecidos.

Update: Como o blogger não suporta categorias, eu vou adicionar a sigla IA no começo dos títulos dessa categoria.

quinta-feira, abril 13, 2006

Inicialização do Linux

Um dos projetos no qual estava trabalhando antes de ficar sem tempo é um inicializador novo para o Linux. A idéia é rodar os processos em paralelo quando possivel, diferentemente do que se faz hoje, de rodar eles em série.

Bom, a idéia é bastante simples, em um diretório dentro de /etc ficam alguns arquivos que descrevem um grafo. Cada um destes arquivos define um alvo e nós comuns. Todos os nós têm uma lista de dependências, que podem conter alvos ou nós comuns, e o inicializador recebe o nome de um alvo de init.

Isso é simples, em dois dias eu pude criar um programa em Perl que fazia isso (não pretendo mudar o processo init), mas é em Perl... O Miguel tem um artigo sobre Perl no Log4Dev :) mas o problema não é esse não. Perl cai tão bem no problema que o código ficou mais legivel e fácil de se manter do que em qualquer outra linguagem que eu pensei na época. O problema é que Perl é interpretado, e nem sempre se tem um interpretador de Perl em mãos antes de começar rcS... Existe um compilador de Perl, mas ele ainda esta bem instável, e não consegue rodar o meu código, assim, até agora eu estava esperando o problema desaparecer :)

Mas então eu percebi que posso fazer o programa em Mercury! Afinal, eu preciso de grafos, e interpretar os arquivos de configuração, e usar um named fifo. Nada que seja dificil de fazer em Mercury, e vou ter um programa para aprender a linguagem direito :)

Daí, depois de tudo pronto, eu vou poder começar a parte dificil, que é traduzir as configurações do sistema atual para o novo. Isso sim vai dar trabalho.

Acabei!!!!!!!!

Finalmente acabei a versão inicial da minha dissertação de mestrado. Isso significa que eu vou ter mais tempo para escrever aqui, e que devo publicar minha biblioteca de visão estéreo logo (desisti de esperar a GPLv3, ela deve demorar muito, depois eu mudo pra ela).

Como prometido, a biblioteca gera resultados melhores do que outros métodos já conhecidos e com menor tempo de processamento. Mas muita coisa ainda está por ser feita, já que por hora ela não consegue obter resultados em tempo real, é bastante sensível a variações de ambiênte (dá pra concertar) e acho que é possivel melhorar ainda mais os resultados aumentando pouco o tempo de processamento. Além disso, ela não funciona com configurações genéricas das câmeras.

Ou seja, vai um bom tempo até ela ser mesmo útil :( Mas eu vou ter mais tempo para escrever aqui :)

segunda-feira, março 20, 2006

IA: Algorítmos Genéticos

Algorítmos genéticos (e estratégias evolutivas, eu não vou usar dois nomes não) têm atraido bastante atenção ultimamente, de gente que sabe o que faz e de gente que não sabe. O resultado é que o cada vez mais, eles são implementados de forma errada, o que é impressionante, já que são tão símples. Assim, na esperança de ajudar quem está começando a não cair nas mesmas armadilhas decidi escrever este texto.

Para começar, para que servem esses algorítmos genéticos? Algorítmos genéticos são úteis para resolver problemas de otimização. Problemas em que você tem alguma coisa com alguns parâmetros e precisa encontrar os melhores valores para estes parâmetros. Isso parece restritivo, mas não é, nao se sabe de nenhum problema na computação que não possa ser visto como um problema de otimização. Algorítmos genéticos são mais úteis se o problema tiver vários parâmetros e você tiver poucas informações a respeito dele.

Os algorítmos genéticos funcionam todos de forma bastante semelhante, os parâmetros a serem otimizados são concatenados em uma população de cromossomos (na prática, um pedaço da memória, normalmente vetores), cada cromossomo é avaliado segundo sua utilidade, os melhores são copiados por cima dos piores e os genes (parâmetros) de alguns cromossomos são embaralhados dois a dois. Cada iteração destas é denominada uma geração. Após diversas gerações você provavelmente terá cromossomos bem próximos do ótimo na sua população. Pode-se fazer algumas coisas diferentes, como mutações (aleatórias ou não) nos genes e preservar os melhores cromossomos para as gerações seguintes, mas no geral as diferenças são em como se faz cada uma destas etapas.

Vale notar que a única etapa que depende do problema é o cálculo da utilidade dos cromossomos. Esta utilidade é um número que é maior quão mais desejável seja o cromossomo. Normalmente ela também é positiva, o que facilita a implementação.

A embaralhada dos genes é chamada de cross-over, e é a etapa mais importante do algorítmo. (Se você acha que é a mutação, já começou errado.) Sem o cross-over, tem-se que se procurar o cromossomo ótimo em todas as combinações possíveis dos genes, pois o fato de um cromossomo ser ruim não significa que um certo gene dele é ruim, todos os outros que estão junto com ele também influenciam. Assim, não podemos avaliar os genes, somente os indivíduos. Quando os genes são embaralhados, porém, eles passam a ocorrer independentemente dos outros, se todos os indivíduos com um gene forem ruins, o gene deve ser ruim. Ou seja, agora podemos avaliar os genes separadamente, quanto mais indivíduos forem analizados, mais certeza teremos da avaliação.

Para entender porque o cross-over é tão importante, imagine um problema em que queremos otimizar 2 características, cada uma com 10 possibilidades. Esta é uma tarefa trivial para um computador, pois só temos 100 possíveis indivíduos, mesmo assim, o número de genes é bem menor, só há 20 possíveis genes. Se tivessemos, porém 3 características, teriamos mil indivíduos e 30 genes, com 6 características, teriamos um milhão de indivíduos, e só 60 genes. É fácil ver que o número de indivíduos cresce muito mais rápido do que o de genes. De fato, ele cresce exponencialmente mais rápido, tornando muito mais eficiente avaliar os genes do que os indivíduos.

Agora vamos aos detalhes. A primeira coisa que o algorítmo faz é criar a população inicial. E esta é a primeira das preocupações do programador. Idealmente, essa população tem que reúnir todos os genes possíveis, em diversas combinações. Na maior parte das vezes, porém, isso não é possível, já que os genes são muitos. Nestes casos, tenta-se obter a maior variedade possível já nesta população, normalmente escolhendo-a de forma aleatória, e utilizam-se mutações para introduzir os outros genes depois. A mutação mais comum é, em cada geração, escolher aleatóriamente alguns cromossomos e mudar o valor de um de seus genes de forma também aleatória.

O tamaho (número de indivíduos) da população também é importante. Normalmente todas as gerações têm o mesmo tamanho, o que permite a implementação com vetores de tamanho fixo, sem alocação dinâmica. A população tem que ser tão maior quanto maior for o número de genes em cada cromossomo, pois quanto mais genes interferirem na utilidade do cromossomo, mais cromossomos devem ser medidos para se ter certeza do resultado. O número de gerações é outro parâmetro que deve ser ajustado. Quanto mais valores diferentes cada gene de um cromossomo puder adquirir, mais gerações são necessárias para testar estes valores.

Até agora não tem muito o que ir errado. O erro mais comum nos parâmetros acima é colocar uma taxa de mutação muito alta. Em cada geração não se costuma escolher mais de 10% dos cromossomos para a mutação, na maior parte das vezes, se utiliza um valor bem mais baixo, como 2% ou 5%. Como já disse, se a população inicial for boa, a mutação não é nem mesmo nescessaria. Mas a maior parte dos erros acontece mesmo é ao se definir o cross-over. A principal função do cross-over é fazer com que os genes occorram independentemente na população, e é muito importante lembrar disso ao se definir esta operação. O cross-over deve embaralhar os genes da melhor forma possível, fazendo com que dois genes não costumem passar sempre juntos de um cromossomo para o outro.

O operador de cross-over mais utilizado escolhe aleatóriamente dois cromossomos e um ponto nestes cromossomos, depois disso, ele troca todos os genes de um dos cromossomos até este ponto aleatório com os do outro cromossomo. Este operador é razoável, não é o ideal, mas funciona até bem. Algumas pessoas, porém, resolvem simplificar a implementação e destroem este operador. Algumas vezes, estas pessoas escolhem sempre uma parte específica dos cromossomos para trocar os genes, outras vezes, resolvem agrupar os genes antes da troca, fazendo com que vários deles sempre sejam trocados juntos, o resultado é que o algorítmo pára de funcionar. É claro que aumentando a taxa de mutação, o tamanho da população e o número de gerações, o algorítmo resultante vai gerar vários indivíduos aleatórios, e alguma hora deve chegar em um bom. É claro também que isso vai precisar de muito mais tempo e sorte do que um algorimo genético precisaria.

Para finalizar, queria apresentar um operador de cross-over que torna os genes completamente independentes. Alguém já deve ter proposto este operador, mas nunca encontrei um operador ideal na literatura. Como eu disse, o operador que normalmente é utilizado não é ideal, apesar de conseguir resolver a maior parte dos problemas. Para fazer um cross-over ideal em um par de cromossomos com n genes, basta gerar um número aleatório de n bits - onde cada bit tem uma probabilidade de ser 1 ou 0 que não precisa ser necessáriamente 50%, mas um bit não pode interferir nos outros - e trocar os genes das posições em que se obtiver um 1, mantendo os das que se obtem 0.

quarta-feira, fevereiro 22, 2006

Software Livre é Assintoticamente mais Rápido?

Não é de hoje que a velocidade com que o software livre se desenvolve espanta as pessoas. Não é de hoje também que eu suspeito que o desenvolvimento do software livre não é simplesmente mais rápido do que o do não livre, mas assintoticamente mais rápido. Vejamos o porquê... Mas primeiro, o que isso significa mesmo?

Partindo do princípio de que o software livre é mesmo desenvolvido mais rápido, imagine que, de repente, por algum motivo qualquer, a velocidade de desenvolvimento do software não livre dobre. O que acontece agora? Ele passa o software livre? Se não, imagine que esta velocidade é agora triplicada, ou miltiplicada por 100, ou por 1000... Dizer que o software livre cresce assintoticamente mais rápido do que o não livre é o mesmo que dizer que mesmo que a velocidade do software não livre seja multiplicada por qualquer valor (10, 100, 1000...) ele não consegue passar o software livre no longo prazo. Mas isso só vale para o longo prazo. No curto prazo, o software livre pode ser mais lento mesmo sendo assintoticamente mais rápido.

Porque eu desconfio disso? Bom, o software livre parece mesmo mais rápido. É algo impressionante de se ver um pacote de software livre de repente começar a crescer e, em poucos meses, percorrer o mesmo caminho em que programas não livres gastaram décadas. Mas por que assintoticamente mais rápidos? Eu não fui o único que notou isso (mas perdi is links que tinha, quando encontrar, coloco aqui): Os programas livres começam pequenos, bem pequenos, e crescendo devagar. Enquanto isso, as alternativas proprietárias (quando existem) começam maiores e crescendo rápido. De repente, porém, sem nenhum aviso, os programas livres passam os proprietários. Isso é sinal de que são assintoticamente mais rápidos.

Outra pergunta muito boa é: Como isso é possível? Os dois são programas, feitos por programadores que não são muito diferentes nos dois mundos (muitas vezes são até a mesma pessoa). Como um pode ser tão mais rápido do que o outro? Não pode ser porque mais programadores trabalham em um deles, senão a diferença seria somente proporcional, nunca assintótica.

Encontrei uma resposta para essa pergunta enquanto lia "The Art of Unix Programming". Reaproveitamento de código! Isso, aliado à tendência de descartar código mal feito nos programas livres pode aumentar a produtividade dos programadores.

O reaproveitamento de código é uma daquelas coisas que todo mundo diz que é bom, mas ninguém faz. Pelo menos no mundo do software proprietário. Já no mundo do software livre, uma pessoa costuma se deparar com centeneas de bibliotecas compartilhadas entre os programas que usa. Isso era um dos maiores problemas nos sistemas mais antigos, em que o tratamento de dependências era manual. Ou seja, no software livre, o código é de fato reaproveitado.

Mas que ganho isso gera? Bom, para isso, vamos comparar os diferentes programas pela sua funcionalidade. Entendo por "funcionalidade" a quantidade de funções diferentes que o programa pode executar. É uma medida subjetiva, e não coincide com a utilidade, mas deixemos estes problemas para depois. Para fins de modelo, proponho que todas as funções "custam" o mesmo tempo de programação. Sem reaproveitamento de código, então, a funcionalidade x custo é uma reta:
Os números não são importantes, só estão ai para comparar com os outros gráficos. Preferí contar somente o custo de "melhorias" no software, logo, a funcionalidade não começa do zero (só pra constar, sai do 30). É interessante notar que não há nenhum ponto especial (fora o de custo zero) no gráfico acima. Ou seja, alguém que observe o desenvolvimento do programa não vai notar nada de diferente, só um crescimento constante.

Com o reaproveitamento de código, a coisa muda. Idealmente, quanto mais código o programador tem à sua disposição, menos ele tem que escrever para criar uma certa funcionalidade. Imagino que seja rasoável esperar que para criar uma certa função, a cada N funções que ele possua em bibliotecas ou que possa recortar e colar em seu programa, ele precise escrever N/y linhas a menos, onde y é constante (y > 1, é claro). Assim, o custo de cada função diminui proporcionalmente à funcionalidade que ele já possui implementada. Isso nos dá que a funcionalidade x custo é uma exponencial:



De novo, os números não são importantes. De novo, a funcionalidade não sai do zero (apesar do que parece), mas de um valor mais baixo do que no caso anterior. Isso foi proposital, já que o software livre normalmente é "lançado" com menos funcionalidade do que o proprietário, e não influencia no modelo, só vai gerar uma figura mais legal no final. (Só pra constar, a base é 1.013.) A exponencial também não tem nenhum ponto especial (fora o de custo zero), assim, alguém acompanhando o desenvolvimento deste programa não vai perceber nada de diferente em nenhum momento. O programa simplesmente continua crescendo, só um pouco mais rápido do que crescia a até pouco tempo atrás.

Comparando os dois gráficos, porém, aparecem dois pontos especiais:

No ponto A, a exponencial tem a mesma inclinação da reta, ou seja, o custo de se adicionar mais uma funcionalidade com ou sem reaproveitamento de código é igual. Este é o ponto em que o reaproveitamento começa a compensar, e é razoável imaginar que seja neste momento que o programa começa a chamar a atenção dos programadores, como aconteceu com o software livre lá por 97 e 98.

Já no ponto B, a funcionalidade dos dois é igual. À partir deste ponto, o reaproveitamento de código começa a gerar melhores programas. É de se esperar que neste ponto o projeto começe a chamar a atenção dos usuários, como aconteceu com o software livre em 2003 - 2004.

Bom, mas isso já está ficando muito longo, então vamos logo para o mundo real. Na verdade, essa "funcionalidade" não serve para nada. Para que todo esse bla bla bla sirva para alguma coisa, a utilidade dos programas tem que crescer com a funcionalidade. Essa proposição é bastante rasoável, bastando que os programas sejam bem gerenciados. O maior problema, porém, é que é bastante dificil confirmar este modelo. A funcionalidade não pode ser medida, a utilidade também não. Poderiamos medir o preço, mas o software livre tende a ter baixo custo, não refletindo a utilidade.

Resumindo, eu não faço a menor idéia de como confirmar o modelo. Mas se há uma diferença assintótica no comportamento dos dois, isso deve se refletir em algo que possa ser medido. Só não sei o que :(

Outro problema é que assumi que o ganho de produtividade é proporcional à funcionalidade disponível para reuso. Isso também não é comprovado, apezar de parecer razoável.

quarta-feira, fevereiro 08, 2006

Mercury, Outra Vez

Continuação deste post sobre o Mercury.

Bom, acabei de ler o tutorial sobre o Mercury, ele é bom, mais ainda está incompleto. Nada fora do comum para uma linguágem que foi lançada há menos de um ano, mas não ajuda.

De qualquer forma, a linguágem é muito mais um Prolog com estensões funcionais do que um Haskel com estensões lógicas. E eu chamei aqui de "estensões", mas não são, a parte funcional cai muito bem na linguágem, não é um módulo separado (como é OO em C++).

Como prometido, ela implementa tipos fortes, e é modular. Tem até um negócio que faz o mesmo papel do encapsulamento em OO, mas não tem (que eu saiba) o equivalente aos pacotes do Java. Além disso, é compilada, o que facilita o uso de mais de um arquivo.

Realmente, o Mercury traz opções que possibilitam uma otimização muito boa do código. Mas isso vem com o custo de declarações mais complicadas. Nada demais pra quem está acostumado com programação estruturada e OO, mas algum trabalho a mais para quem se acostumou com Lisp, Haskel ou Prolog (esse alguém existe?). Se o compilador implementa ou não essas otimizações não é muito importante, como elas são possíveis, se a linguágem pegar alguém vai implementar (mas o pessoal diz que implementou um bom número delas).

Tudo isso vem com um problema (além de serem dois paradigmas que quase ninguém conhece), não tem compilador para Windows. Dá para compilar e rodar os programs usando o CygWin, mas não é nativo, e coisas novas dificilmente pegam se não rodarem no Windows. O backend deles usa gcc, de forma que deve ser fácil compilar os programs PARA o windows, mas não NO windows.

Fica a esperança de ver uma linguágem muito boa se espalhar por aí. O paradigma lógico é muito bom para, por exemplo, criar interfaces, tanto homem-máquina, quanto máquina-máquina. O paradigma funcional adiciona a possibilidade de se fazer contas facilmente, o que faz muita falta no prolog.

terça-feira, fevereiro 07, 2006

Visão Estéreo

Já que eu já comecei mesmo o blog, vou continuar postando :)

Bom, meu trabalho de mestrado (que está quase acabando) é um algorí­tmo para visão estéreo. Primeiro, visão estéreo é a que é obtida com duas câmeras ou mais. Com uma câmera só, ela se chama monocular. Mas por que a diferença? Acontece que dá para fazer coisas muito legais quando se fotografa um objeto por mais de uma direção. A aplicação mais comum disso é calcular a distância de cada ponto do objeto até o plano das câmeras (profundidade) e construir um modelo 3D da cena.

A etapa mais dificil (demorada) da reconstrução 3D, é conhecida por 'matching'. Nessa etapa, o computador tem que descobrir que ponto de uma imagem corresponde a cada ponto da outra. Meu algoritmo resolve essa etapa do problema. Mas o que é MUITO legal é que ele é muito mais rápido do que o algoritmo que se costuma usar quando se quer um matching rápido e ao mesmo tempo, erra menos.

Bom, não preciso dizer que estou bastante satisfeito, né. Estou esperando a GPLv3 sair para publicar minha biblioteca. Até lá ainda devo voltar a tocar no assunto.

Mercury

Pois é. Eu bem que queria esperar um pouco mais antes de começar esse blog, mas se eu esperasse, ia acabar me esquecendo disso:

Hoje apareceu um pacote novo no repositório do Debian que é muito interessante. Ele se chama mercury, e promete ser uma linguágem ao mesmo tempo lógica e funcional, compilada (com boa otimização), com tipos fortes e modular. O que me chamou a atenção foram os tipos fortes e a modularidade, eles fazem muita falta nas linguágens funcionais (a princípio eu não entendi que ela era lógica também).

Bom, comecei, então a pesquisar sobre ela. Achei a página dela, que tem um livro sobre a linguágem, mas ele é péssimo para começar a aprender, embora sirva como referência. Achei, então, na página sobre ela na Wikipedia, esse tutorial. Ele parece bom, embora eu ainda esteja no começo.

O maior problema que vejo nos paradigmas lógico e funcional são exatamente a falta de tipos fortes no funcional (no lógico eu nunca imaginei que essa idéia fizese sentido) e a pouca modularidade. E antes que alguém reclame, modularidade significa tambem poder dividir o programa em arquivos reutilizáveis e em espaços de nomes independentes, coisa dificil de fazer na maior parte das linguágens (padrão) funcionais.