Arquivos da Categoria: Programação

Funções anônimas em C

Quem conhece funções anônimas (também conhecidas por expressões lambda) de outras linguagens, talvez já tenha sentido sua falta quando resolvendo certos problemas em C ou em C++.

A eventual chegada do padrão C++0x promete resolver esse problema, finalmente trazendo as funções lambda à linguagem. No entanto, isso se refere somente ao C++; mesmo o vindouro padrão C1X não faz referência a uma eventual chegada da ferramenta ao bom e velho C.

Porém, se seu projeto só será compilado usando o compilador GNU, uma boa parte de seus problemas pode ser resolvida com a utilização de um macro e de duas extensões. O uso dessas extensões significa que seu código deixará de seguir o padrão ISO e, portanto, deixará de ser portável. Se isso é um problema ou não, você que deverá julgar.

Saiba mais

Publicidade

Um pequeno serviço D-Bus em Python

Dentre os métodos para se fazer comunicação entre processos no Linux, o D-bus é provavelmente o que vem ganhando maior destaque recentemente. Aqui vou mostrar como implementar um serviço simples que poderá ser chamado de outros processos, demonstrando sua utilização a partir do Emacs; no entanto, nada impede que os métodos desse serviço sejam chamados de outra linguagem em que existam bindings para o D-Bus (o próprio Python, C/C++, C#, Perl, Ruby, PHP, Haskell, …). Aliás, é possível que em alguns casos seja mais simples fazer a integração entre processos escritos em linguagens diferentes através do D-Bus que usar foreign functions.

#!/usr/bin/env python2

import dbus
import dbus.service
from dbus.mainloop.glib import DBusGMainLoop
import gobject

class Greeter(dbus.service.Object):
    def __init__(self, Name=""):
        bus_name = dbus.service.BusName('org.local.greeter',\
                                            bus=dbus.SessionBus())
        dbus.service.Object.__init__(self, bus_name, '/%s' % Name)

    @dbus.service.method('org.local.greeter')
    def hello(self, Name="world"):
        print "Hello, %s!" % Name
        return "Hello, %s!" % Name 

DBusGMainLoop(set_as_default=True)
myGreeters = [Greeter("A"), Greeter("B")]

myLoop = gobject.MainLoop()

try:
    myLoop.run()
except KeyboardInterrupt:
    myLoop.quit()
    print "Bye!"

Começamos o arquivo importando os módulo necessários. Em vez de importar o módulo gobject, alguns tutoriais usam o módulo gtk. A função dos dois será a mesma: implementar o loop principal do serviço (tanto que o loop principal do gtk é implementado sobre o loop principal do gobject, apenas com alguns tratadores a mais). Como não iremos usar nenhum componente gráfico neste exemplo, não há a necessidade de se usar o gtk.

Em seguida criamos a classe que implementará o serviço, a classe Greeter. No construtor (__init__), definimos o nome do serviço — no caso, org.local.greeter —, e dizemos que ele é um Session Bus em vez de um System Bus (este reservado para serviços de mais baixo nível, como o HAL e o NetworkManager. No construtor também iniciamos o objeto, informando o nome que definimos anteriormente e lhe dando um caminho (path). O caminho é útil em casos onde se que o mesmo serviço dê acesso a vários objetos parecidos — por exemplo, o Emacs poderia dar acesso via D-Bus a cada um de seus buffers através do caminho /Emacs/Buffers/<Nome do Buffer>.

Depois, definimos um método. Note a presença do decorador (@dbus.service.method('org.local.greeter')). De certa forma, esse decorador estabelece que o método a seguir é “público”, ou seja, que pode ser acessado por processos externos. Para termos uma melhor organização do código, podemos criar outros métodos que não queremos que sejam acessíveis externamente; nesses casos, basta não usar o decorador. O método em si é bastante simples: ele imprime uma mensagem no terminal em que o serviço estiver rodando e retorna para o processo que o chamou essa mesma mensagem. Na prática, geralmente desejaremos que o serviço retorne alguma coisa em vez de imprimir, mas deixei assim para mostrar que existem as duas possibilidades.

Então temos o código para fazer o serviço executar. Criamos um novo DBusGMainLoop e o definimos como Loop padrão. Seguindo a documentação, atualmente não faz sentido criar mais de um loop, já que ainda não há suporte para isso (ao menos não no Python). Na linha seguinte são criados dois objetos da classe Greeter, cada um com um path diferente, /A e /B; fiz assim para demonstrar como isso é utilizado. E então criamos o loop principal e o executamos.

Do lado do cliente — no caso, o Emacs —, o código fica:

(require 'dbus)
(dbus-list-known-names :session)
(dbus-call-method :session "org.local.greeter"
                           "/A"
                           "org.local.greeter"
                           "hello"
                           "Emacs")

Caso se queira chamar o objeto /B, basta trocar o path na função dbus-call-methor.


Comparado ao COM do Windows, eu considero o D-Bus mais “limpo”. Mesmo quando se implementa um serviço COM em Python, sempre fico com a impressão de que certas coisas poderiam ser abstraídas de maneira melhor (CLSIDs, por exemplo).

Ainda assim, embora o D-Bus seja uma alternativa à altura (ou até melhor) que o COM, ele não substitui o DCOM. Nada impede que a comunicação entre processos seja feita entre diferentes máquinas, o problema é que, ao menos por enquanto, o D-Bus não implementa nenhum sistema de segurança — tanto de autenticação de usuário como de criptografia de dados.

Fonte

Gerador de Markov

Gerador de Markov

Um dos sites mais úteis que existem é o Gerador de Lero-lero. Não tenho certeza se o algoritmo usado é um Gerador de Markov mesmo, mas se não for, a idéia é bem parecida.

Gerador de Markov é um programa que analisa um texto procurando as combinações de palavras mais comuns e então gera um texto usando as mesmas combinações em um texto que é estatisticamente similar ao anterior. Como essa análise será feita depende da implementação. Eu escolhi usar combinações de 3 palavras, ou seja, uma palavra do texto gerado depende das duas anteriores a ela. Variando a quantidade de palavras usadas em cada combinação, altera-se o texto resultante: se eu escolhesse combinações de uma palavra, o texto gerado seria completamente aleatório, se eu escolhesse combinações de dez palavras, o texto resultante ficaria mais parecido com o original.

A implementação de um Gerador é relativamente simples, clique em “Ler o resto do artigo” para ter acesso ao código em Common Lisp. O código está bem dividido e cada função tem uma função clara (evidentemente).

Primeiramente, criamos uma hash-table que conterá as combinações de palavras. Usamos uma hash-table por ela ser mais eficiente. Se usássemos listas ou árvores, teríamos de fazer buscas toda vez que o Gerador fosse adicionar uma nova palavra ao texto. Logo no começo também, inicializamos o gerador de números aleatórios.

Para que possamos analisar as combinações de palavras, precisamos primeiro dividir a string em uma lista de strings. A função “space-position” se ocupa de descobrir onde fica o próximo “divisor de palavras”, ou seja, um espaço, um tab ou uma quebra de linha. O que vier antes será o delimitador. Se houver vários espaços em sequência, nós teríamos uma lista com algumas strings vazias, mas o “cond” na função “split-string” detecta isso com “(= pos 0)” e evita que isso aconteça.

Logo em seguida vem algumas funções auxiliares. “Last-two” retorna os dois últimos elementos de uma lista qualquer. Precisaremos dela mais tarde. “Random-elt” e “random-key” retornam um elemento aleatório de uma lista e uma chave aleatória de uma hash-table respectivamente. “List-triples” retorna os trios que podem ser formados de uma lista. Note que ela não gera todos os arranjos possíveis, apenas as combinações sequenciais. Imagine que existe um bloco com espaço para três “coisas”. Esse bloco percorre a lista sequencialmente gerando os trios. Assim, a lista ‘(1 2 3 4 5) seria percorrida como: ‘((1 2 3) 4 5), ‘(1 (2 3 4) 5) e ‘(1 2 (3 4 5)). Portanto, (list->triples ‘(1 2 3 4 5)) retornaria ‘((1 2 3) (2 3 4) (3 4 5)). “String->symbol” retorna um símbolo com o mesmo nome que o conteúdo da string passada como argumento. Não me pergunte porque eu preferi usar símbolos ao invés de strings mesmo. Talvez o gerador ficaria melhor assim, já que ele saberia diferenciar quando uma palavra está iniciando uma frase pela letra maiúscula, ou talvez isso não mudasse lá grande coisa.

“Insert-triple-into-table” é a função que faz o trabalho sujo: ela é a responsável por inserir os trios gerados por “list->triples” na hash-table que críamos no começo do programa. Ela é feia, não é uma função que me orgulho de ter escrito, mas ela funciona. Perceba que cada entrada na hash-table inicial é, por sua vez, outra hash-table. Essa segunda hash-table guarda uma lista com as possíveis palavras que podem ser usadas.

“Insert-string-into-table” organiza o trabalho de separar uma string em uma lista de strings, transformá-las em símbolos, gerar os trios e inserí-los na hash-table.

“Insert-file-into-table” foi uma função que deu trabalho escrever. Inicialmente, ela seria a função responsável por abrir um arquivo, salvá-lo como uma string e então passar para “insert-string-into-table”. Porém, a forma com que fiz isso era péssima, o consumo de memória ia para as alturas e o tempo de execução também. Em uma das tentativas, reimplementei boa parte da “insert-string-into-table” em “insert-file-into-table”, mas acabei deixando as duas funções mesmo assim, já que as duas são úteis. Depois, consegui implementar esta função segundo a idéia original com um desempenho muito melhor.

Finalmente, a parte interessante: “generate” gera um texto com no máximo o número específicado de palavras. Não há garantias de que ele gerará o número máximo, já que algumas combinações podem fazer com que ele não consiga gerar mais nada.

Só para me exibir, resolvi colocar alguns trechos que o Gerador criou tendo como base o texto deste artigo (um artigo recursivo):

“logo no começo também, inicializamos o gerador de markov mesmo, mas se não for, a idéia é bem parecida.”

“gerador de markov é um gerador de markov”

“se houver vários espaços em sequência, nãs teríamos uma lista e uma chave aleatória de uma lista e uma chave aleatória de uma lista com algumas strings vazias, mas o “cond” na função “split-string” detecta isso”

Eu o tenho usado nas conversas de MSN com sucesso. Ele detecta que a outra pessoa falou “oi :)” e gera o texto “olá =]” ou variação. Depois ele detecta a combinação “tudo bom?” e responde “sim, e contigo?”. Depois ele passa o comando para mim. OK, isso não é sério… ainda. Preciso aprender a fazer plugins para o Pidgin ainda (o bitlbee seria mais interessante nesse aspecto).

Saiba mais

Streams (listas infinitas) em C

Ultimamente tenho feito duas coisas: lido sobre Haskell e não postado no blog (além das outras coisas do dia-a-dia, claro).

Programas em Haskell são preguiçosos. Isso significa que quando uma variável é definida, ela só será computada quando seu valor for necessário. Assim, se fizermos um programa similar ao de baixo, fatorial de 1000 nunca será calculado, já que o seu valor não é necessário para calcular 1+1.

x = factorial 1000
putStrLn $ show (1+1)

Extrapolando essa mesma ideia* para outras definições, podemos definir uma lista de infinitos uns:

uns = repeat 1

Ou então com todos os números naturais:

naturais = [1..]

Com um pouco mais de perspicácia, é possível criar listas contendo todos os números de Fibonacci, ou então todos os fatoriais:

fibs = 1:1: (zipWith (+) fibs (tail fibs))
facs = 1:(zipWith (*) facs [1..])

Se quisermos 10 elementos de cada, fazemos:

dezFibs = take 10 fibs
dezFacs = take 10 facs

Essa implementação é bastante eficiente : se precisamos do fatorial de 10 e logo em seguida o de 11, não precisamos calcular 11×10×9×…×1, basta calcular 11×10!, que já havia sido computado. Melhor ainda : se uma hora precisarmos do fatorial de 7, ele já estará calculado, pronto para ser utilizado.

Agora sim a parte interessante, em que C entra nessa história. Embora minha implementação não seja nem de longe tão interessante como a utilizada pelo Haskell, ela serve de base para mostrar como uma implementação de stream ou listas infinitas pode ser feita em C.

A grande diferença entre listas e streams é que não trabalharemos com a idéia de um ponteiro para o próximo elemento, mas sim com uma expressão que ao ser executada nos dará o próximo elemento. Ou seja, ao invés de um ponteiro para outro elemento do mesmo tipo, nós temos um ponteiro para uma função.

typedef struct {
    int i;
    int (*cont)(int);
} stream;

Isso altera a forma como acessamos o próximo elemento. Não podemos mais utilizar o famoso ptr = ptr->prox porque estaremos apontando para uma função. Por isso, abstraí o processo de chamar a função com o valor da stream em uma função chamada proximo, que retorna uma nova struct com seu valor i atualizado pela função cont, o que dá a impressão de que avançamos na lista.

stream proximo(stream inicio)
{
    stream tmp;

    tmp.i = (*inicio.cont)(inicio.i);
    tmp.cont = inicio.cont;

    return(tmp);
}

Para exemplificar o uso de streams, criei a função pega que é similar à função take no Haskell, mas que no caso não retorna os valores, só os imprime.

void pega(int elementos, stream inicio)
{
    int i;
    stream atual = inicio;

    for(i = 0; i < elementos; i++)
    {
        printf("%d\n",atual.i);
        atual = proximo(atual);
    }
    printf(".\n.\n.\n\n");
}

Por fim, criei duas streams e duas funções auxiliares (que falta fazem expressões lambda). O código completo se encontra abaixo:

#include <stdlib.h>
#include <stdio.h>

typedef struct {
    int i;
    int (*cont)(int);
} stream;

stream proximo(stream inicio)
{
    stream tmp;

    tmp.i = (*inicio.cont)(inicio.i);
    tmp.cont = inicio.cont;

    return(tmp);
}

int soma_um(int i)
{
    return(i+1);
}

int repete(int i)
{
    return(i);
}

void pega(int elementos, stream inicio)
{
    int i;
    stream atual = inicio;

    for(i = 0; i < elementos; i++)
    {
        printf("%d\n",atual.i);
        atual = proximo(atual);
    }
    printf(".\n.\n.\n\n");
}       

int main(int argc, char *argv[])
{
    stream naturais, identidade;

    naturais.i = 1;
    naturais.cont = &soma_um;

    identidade.i = 1;
    identidade.cont = &repete;

    pega(10, naturais);
    pega(10, identidade);
    return 0;
}

*eu escrevi “idéia” mas aparentemente os verificadores ortográficos já aderiram todos às novas regras ortográficas… fica assim mesmo.

C: Hash tables, arrays associativos, dicionários…

Não sei quantos nomes existem para descrever esta forma de organizar séries de dados na memória, esses três do título foram as que eu consegui pensar em 5 segundos. :P

Enfim, comecemos pela forma mais simples de armazenar séries de dados na memória, arrays, seguiremos para listas, árvores, e então chegaremos às hash tables. Se tudo que você quer é um exemplo de implementação, vá ao fim do artigo.
Saiba mais

Imbutindo Common Lisp (ECL) em C

Hoje comecei a brincar com ECL (Embeddable Common Lisp). Como o nome diz, é possível embarcá-lo [1] em um programa escrito em C. Na verdade, ele é mais que isso; é possível também rodar o comando ecl para ter um interpretador de Common Lisp ou usá-lo como um compilador de Common Lisp para C/binário.

Esses dois últimos usos são relativamente simples e estão bem documentados. Meu interesse mesmo era como embarcar em um programa escrito em C e acessar funções definidas em C a partir do programa em Lisp e vice versa. Infelizmente, essa parte consta com um “TBD” no manual, que eu imagino que signifique To Be Done, a ser feito. Mesmo assim, consegui achar algumas informações na mailing list e em outros sites e fazer um programa básico.

Saiba mais

Fonte bacana para programação

Nas minhas andanças pela internet, encontrei uma fonte (TTF) chamada Envy Code R. Achei-a bem bacana, quem quiser baixar, tem um link no site, logo antes dos comentários.

Awesome: barra de título, mas só quando floating

Pediram em um tópico do fórum do Arch Linux como fazer a barra de título aparecer em janelas que estivessem “flutuando” no awesome. A idéia é boa e permite que tenhamos o melhor dos dois mundos: de um lado, o tiling continua funcionando normalmente; do outro, nós temos controle sobre programas que estejam “flutuando” de forma bastante similar ao que teríamos em gerenciadores de janela comuns, tais como o Openbox, o do GNOME e o do KDE.

A implementação disso é bastante simples, basta adicionar ao fim de seu rc.lua:

awful.hooks.property.register(function (c, prop)
  -- Remove the titlebar if fullscreen
  if c.fullscreen then
     awful.titlebar.remove(c)
  elseif not c.fullscreen then
    -- Add title bar for floating apps
    if c.titlebar == nil and awful.client.floating.get(c) then
       awful.titlebar.add(c, { modkey = modkey })
    -- Remove title bar, if it's not floating
    elseif c.titlebar and not awful.client.floating.get(c) then
       awful.titlebar.remove(c)
    end
  end
end)

Transferência rápida de arquivos com python

Às vezes é necessário passar um arquivo grande para alguém, mas devido ao tamanho máximo permitido para anexos em emails, é preciso encontrar outras formas de passar esse arquivo. Uma das opções é fazer o upload do arquivo em algum desses sites próprios para isso (rapidshare, mediafire, etc), outra é mandar o arquivo por algum programa de mensagens instantâneas (tal como o MSN).

O primeiro caso é ruim pois é necessário fazer o upload antes e depois enviar o link, e se você não for registrado no site, não terá controle sobre quanto tempo o arquivo ficará disponível. O segundo é ruim pois geralmente não é possível atingir a velocidade máxima transferindo arquivos pelo MSN.

A solução é esse pequeno script, em python, que inicia um servidor HTML na pasta em que ele for chamado, permitindo que a outra pessoa baixe os arquivos do seu PC com maior velocidade.

import SimpleHTTPServer

SimpleHTTPServer.test()

E para descobrir seu IP, use o pequeno shell script abaixo:

echo `wget -q -O - http://whatismyip.org`

Só não se esqueça que o servidor estará funcionando na porta 8000. Por isso, quando for passar o IP a seu amigo, passe da seguinte forma:

http://0.0.0.0:8000

Fonte: shell-fu

Introdução à programação genética

Nós, como programadores, estamos acostumados a ditar regras ao computador. Ainda que os defensores da programação funcional digam que eles não tenham de ensinar ao computador como fazer (como é o caso das linguagens procedurais), eles ainda tem de dizer qual a relação entre o valor que aquela função retorna e seus argumentos. Por exemplo, podemos definir a função soma como sendo soma(x, y) = x + y, mas e se pudéssemos fazer o contrário, criar um banco de dados e mandar o computador analisar esses dados e achar a relação entre eles?

A Programação Genética (PG) surge justamente dessa idéia, misturando também conceitos da biologia, ou mais precisamente, da genética e da evolução. Por mais estranho que possa parecer, criaremos programas que irão se reproduzir e sofrer mutações. Através disso e de um processo de seleção natural, seremos capazes de determinar a relação entre valores que a princípio pareciam não ter nada em comum.

Além disso, podemos usá-la também para desenvolvermos algoritmos que sejam mais rápidos, basta ajustarmos a nossa seleção “natural” para que ela leve em consideração o tempo também.

Saiba mais