Mudança…

Setembro 2, 2012

Desde que comecei a escrever no blog me deparo com um dilema: escrever em português ou em inglês?

Obviamente escrever em português é mais natural para mim, mas não acho que escrever em inglês seja tão mais difícil.

Acabei optando por escrever em português devido ao caráter pessoal do blog. Porém, acredito que os posts possam ser de interesse para outras pessoas e escrevendo em inglês torno-os mais acessíveis.

Espero que quem siga meu blog não se veja problemas com essa mudança. Decidir criar um novo blog:

http://kunigami.wordpress.com/

A princípio este aqui não será mais atualizado.


O padrão de projeto Visitor e Vtables em C++

Agosto 26, 2012

Outro dia estava desenvolvendo um código Java em que precisei usar instanceof, mas como já havia lido que o uso dessa palavra-chave é sinal de design ruim, busquei ajuda e me recomendaram o padrão de projeto Visitor.

Neste post vamos falar sobre esse padrão de projeto em Java, que foi onde minha dúvida se originou e também vamos discuti-lo em C++, porque sua implementação tem relação com a estrutura Vtables que eu queria estudar a algum tempo.

Visitor em Java

Consideremos o seguinte exemplo, onde temos as classes Cachorro e Gato que são especializações de Animal e que possuem métodos para emissão de som, respectivamente latir() e miar(), respectivamente.

Queremos implementar um método emitirSom(), que recebe uma instância de Animal e emite o som de acordo com a classe instanciada. Uma alternativa usando instanceof é a seguinte:

// Listagem 1
interface Animal {    
}
public class Cachorro implements Animal {
	public void latir(){
		System.out.println("Au!");
	}
}
public class Gato implements Animal {
	public void miar(){
		System.out.println("Miau");
	}
}
...
public static void emitirSom(Animal animal){
    if(animal instanceof Cachorro){
        Cachorro cachorro = (Cachorro) animal;
        cachorro.latir();
    }
    else if(animal instanceof Gato){
        Gato gato = (Gato) animal;
        gato.miar();
    }
}

Aqui cabe uma citação a Scott Meyers, no seu livro Effective C++:

Anytime you find yourself writing code of the form “if the object is of type T1, then do something, but if it’s of type T2, then do something else,” slap yourself.

Para nos livrarmos do instanceof, basta adicionarmos um método emitirSom() à interface Animal e substituir latir()/miar(). No método emitirSom() usamos polimorfismo para escolher a implementação correta.

// Listagem 2
interface Animal {
    void emitirSom();
}
public class Cachorro implements Animal {
    @Override
    public void emitirSom(){
        System.out.println("Au!");
    }
}
public class Gato implements Animal {
    @Override
    public void emitirSom(){
        System.out.println("Miau");
    }
}
...
public static void emitirSom(Animal animal){
    animal.emitirSom();
}

Outra possibilidade é delegar a implementação de emitirSom() para uma outra classe através do padrão de projeto Visitor. Esse padrão considera dois tipos de classes: um elemento e um visitante. O elemento implementa um método geralmente chamado de accept() e o visitante o método visit().

O método accept() recebe um visitante e chama o método visit() desse visitante passando a si mesmo como parâmetro. Desta forma, o visitante pode implementar o método visit() para cada tipo.

// Listagem 3
interface Animal {
    void emitirSom();
    void accept(AnimalVisitor visitor);
}
public class Cachorro implements Animal {
    @Override
	public void accept(AnimalVisitor visitor){
        visitor.visit(this);
    }
}
public class Gato implements Animal {
    @Override
	public void accept(AnimalVisitor visitor){
        visitor.visit(this);
    }
}
interface AnimalVisitor {
    void visit(Cachorro cachorro);
    void visit(Gato gato);
}
public class EmissorDeSom implements AnimalVisitor {
    @Override
	public void visit(Gato gato){
        System.out.println("Miau");
    }
    @Override
	public void visit(Cachorro cachorro){
        System.out.println("Au!");
    }	
}

A vantagem dessa abordagem é que a classe EmissorDeSom pode conter membros e métodos comuns ao modo como os animais emitem som, que de outra forma acabaria sendo implementado na classe Animal.

Outra vantagem é que a implementação do visitante pode ser escolhida em tempo de compilação e, sendo uma injeção de dependência, facilita testes.

Visitor em C++

Em C++ não temos a palavra-chave instanceof, mas podemos usar a função typeid().

Segundo [1], se o argumento dessa função for uma referência ou um ponteiro de-referenciado para uma classe polimórfica, ela retornará um type_info correspondendo ao tipo do objeto em tempo de execução.

// Listagem 4
struct Animal {
    virtual void foo(){};
};
struct Cachorro : public Animal {
    void latir(){
        cout << "Au!\n";
    } 
};
struct Gato : public Animal {
    void miar(){
        cout << "Miau\n";
    }
};
void emitirSom(Animal *animal){
    if(typeid(*animal) == typeid(Cachorro)){
        Cachorro *cachorro = dynamic_cast<Cachorro *>(animal);
        cachorro->latir();
    }
    else if(typeid(*animal) == typeid(Gato)){
        Gato *gato = dynamic_cast<Gato *>(animal);
        gato->miar();
    }
}

Novamente, podemos criar um método emitirSom() em uma interface e usar o polimorfismo. Em C++ não temos interface, mas podemos definir um método puramente virtual como no código abaixo.

// Listagem 5
struct Animal {
    virtual void emitirSom() = 0;
};
struct Cachorro : public Animal {
    void emitirSom(){
        cout << "Au!\n";
    }
};
struct Gato : public Animal {
    void emitirSom(){
        cout << "Miau\n";
    }
};
void emitirSom(Animal *animal){
    animal->emitirSom();
}

A implementação do padrão Visitor pode ser feita da seguinte maneira:

// Listagem 6
struct Gato;
struct Cachorro;

struct AnimalVisitor {
    virtual void visit(Gato *gato) = 0;
    virtual void visit(Cachorro *cachorro) = 0;
};
struct Animal {
    virtual void accept(AnimalVisitor *visitor) = 0;
};
struct EmissorDeSom : public AnimalVisitor {
    void visit(Gato *gato){
        cout << "Miau\n";
    }
    void visit(Cachorro *cachorro){
        cout << "Au!\n";
    }    
};
struct Cachorro : public Animal {
    void accept(AnimalVisitor *visitor){
        visitor->visit(this);
    }
};
struct Gato : public Animal {
    void accept(AnimalVisitor *visitor){
        visitor->visit(this);
    }
};
void emitirSom(Animal *animal){
    AnimalVisitor *visitor = new EmissorDeSom();
    animal->accept(visitor);
}

Despacho único e despacho múltiplo

Vamos agora analisar como C++ implementa funções virtuais. Antes disso, precisamos entender o conceito de despacho dinâmico.

Despacho dinâmico é uma técnica utilizada no caso em que diferentes classes implementam diferentes métodos, mas não se sabe qual o tipo do objeto que chama o método em tempo de compilação, como nos exemplos acima.

Em C++ e Java, esse tipo de despacho é também chamado de despacho único (single dispatch) porque ele só leva em conta o tipo do objeto que chama o método. Em Lisp e algumas outras poucas linguagens, há o chamado despacho múltiplo que também leva em conta o tipo de parâmetro.

Por exemplo, considere o código abaixo:

// Listagem 7
void visitor(Cachorro *cachorro){
    cout << "Au!\n";
}
void visitor(Gato *gato){
    cout << "Miau!\n";
}
void emitirSom(Animal *animal){
    visitor(animal);
}

Teremos um erro de compilação, porque não temos ligação dinâmica a partir dos parâmetros.

Agora veremos como o despacho dinâmico é implementado em C++.

C++ Vtables

Embora a especificação do C++ não diga qual a maneira de implementar o despacho dinâmico, a maioria dos compiladores fazem uso de uma estrutura chamada virtual method table, também conhecida por outros nomes como vtable. Essencialmente, essa tabela é um array de ponteiros para os métodos virtuais.

Cada classe que define ou herda pelo menos um método virtual possui sua vtable. Ela aponta para os métodos virtuais definidos pelo seu ancestral (incluindo a si mesmo) mais próximo que podem ser utilizados por aquela classe. Além disso, cada instância de uma classe com vtable possui um ponteiro para essa tabela. Esse ponteiro é setado quando instanciamos esse objeto.

Considere o trecho da Listagem 5:

Animal *animal = new Cachorro();

Aqui o ponteiro de animal aponta para a vtable de Cachorro, e não de Animal. Então, quando fazemos

animal->emitirSom();

é feita uma consulta para saber exatamente qual implementação emitirSom() chamar. Note que para métodos virtuais existe uma indireção que pode afetar o desempenho. Por isso, por padrão, o despacho dinâmico não é efetuado em C++, a menos que alguma classe adicione a palavra-chave virtual. Em Java o despacho é habilitado por padrão.

Vamos a um exemplo,

struct A {
    virtual void foo(){}
    virtual void bar(){}
    void baz(){}
};
struct B : public A {
    void bar(){}
    virtual void baz(){}
};

Podemos analisar as vtables das classes A e B compilando o código acima com gcc usando a opção -fdump-class-hierarchy. Um arquivo de texto com a extensão .class será gerado.

Vtable for A
A::_ZTV1A: 4u entries
0     (int (*)(...))0
4     (int (*)(...))(& _ZTI1A)
8     (int (*)(...))A::foo
12    (int (*)(...))A::bar

Class A
   size=4 align=4
   base size=4 base align=4
A (0xb71f6038) 0 nearly-empty
    vptr=((& A::_ZTV1A) + 8u)

Vtable for B
B::_ZTV1B: 5u entries
0     (int (*)(...))0
4     (int (*)(...))(& _ZTI1B)
8     (int (*)(...))A::foo
12    (int (*)(...))B::bar
16    (int (*)(...))B::baz

Class B
   size=4 align=4
   base size=4 base align=4
B (0xb7141618) 0 nearly-empty
    vptr=((& B::_ZTV1B) + 8u)
  A (0xb71f61f8) 0 nearly-empty
      primary-for B (0xb7141618)

Aqui podemos ver que a função A::foo e A::bar aparecem na vtable de A, mas a função A::baz não, porque ela não foi declarada virtual. Na vtable de B temos A::foo, porque ela não foi sobrescrita em B. Temos também B::bar, embora ela não tenha sido declarada virtual em B, essa propriedade foi herdada de A::bar. Finalmente, B::baz aparece na vtable porque foi declarada como virtual em B.

Podemos ver também o valor que os ponteiros que as instâncias dessas classes terão: vptr=((& A::_ZTV1A) + 8u) e vptr=((& B::_ZTV1B) + 8u), que é respectivamente onde os ponteiros para as funções começam nas respectivas tabelas.

Uma referência interessante para compreender melhor vtables pode ser vista em [2].

Referências

[1] The typeid operator (C++ only)
[2] LearnCpp.com – The Virtual Table


Introdução a Constraint Programming usando Gecode

Agosto 19, 2012

Neste post vamos falar sobre constraint programming (CP) ou programação com restrições.

Constraint Programming é uma técnica em que se define um espaço de busca, um conjunto de restrições e deseja-se encontrar soluções viáveis, isto é, pontos que pertencem ao espaço de busca e que satisfazem as restrições.

Segundo a Wikipedia, surgiu a partir da programação por restrições lógicas (constraint logic programming). Essa variante de programação lógica foi criada por Jaffar e Lassez, que introduziram restrições ao Prolog II, sendo que Prolog III possui suporte nativo a programação por restrições lógicas.

É possível trabalhar com CP em linguagens imperativas através de frameworks. Algumas das bibliotecas mais famosas são Gecode (C++), IBM ILOG CP (C++ proprietário), Choco (Java), JaCoP (Java) e Google OR-Tools (C++, com bindings para Java, Python e C#). A biblioteca que utilizaremos para implementar as soluções para os exemplos é a Gecode (v 3.7.3).

Em geral os resolvedores de CP fazem uso de backtracking para encontrar essas soluções e portanto além da modelagem em si, outro fator que influencia o desempenho é a maneira como se faz as ramificações (branching) na árvore de busca.

Um breve tutorial de Gecode

Gecode é uma biblioteca open-source escrita em C++. É disponibilizada com licença MIT, é bastante eficiente, tem suporte a paralelismo e é bem documentada [1].

Modelos no Gecode devem definir um “espaço”. Dentro desse espaço ficam as variáveis, os propagadores (implementações de restrições) e branchers (implementações de branchings).

Um espaço é representado pela classe Space, que o modelo deve estender.

Vamos agora detalhar alguns conceitos utilizados pelo Gecode. Após isso, apresentaremos alguns exemplos clássicos que pode ser atacados com programação por restrição.

Variáveis

O Gecode define novos tipos para especificar o domínio das variáveis, como por exemplo IntVar, para variáveis inteiras e BoolVar para variáveis binárias. Também há o tipo representando um vetor desses tipos, IntVarArray e BoolVarArray.

Podemos construir um vetor de inteiros da seguinte maneira:

IntVarArray (Space &home, int n, int min, int max)

Sempre precisamos passar uma referência de um Space como parâmetro para informar em qual espaço criaremos a variável. O parâmetro n define o número de elementos no vetor, min é o limite inferior e max o liminte superior dos elementos nesse vetor.

Restrições

As restrições delimitam o domínio de busca de uma solução. No Gecode existem funções que criam propagadores implementando essas restrições. Algumas das principais são:

Restrições de relação:

void rel (Home home, IntVar x0, IntRelType r, IntVar x1);

Aqui, Home é equivalente a &Space, pois, novamente, precisamos especificar em que espaço a restrição será gerada. Essa restrição define uma relação entre a variável x0 e x1 usando uma relação r.

Um exemplo de uso é

rel(*this, x, IRT_NQ, 0)

Que modela a restrição x!= 0. Esse exemplo pode ser escrito de maneira mais legível com o uso de sobreposição de operadores:

rel(*this, x != 0)

Restrições de distinção:

Uma restrição bastante útil é a distinct, que exige que todos os valores de um vetor tenham valores diferentes:

void distinct (Home home, IntVarArray x0);

Restrições com expressões regulares:

É possível especificar que o vetor de solução satisfaça uma expressão regular através da restrição extensional.

extensional(Home home, const IntVarArgs &amp;x, DFA d)

Essa restrição espera um vetor de inteiro e um DFA (Deterministic Finite Automata ou Autômato Determinístico Finito), que pode ser criado a partir de uma expressão regular. Essa função restringe os valores de x de forma que seja aceitável pelo DFA.

O tipo REG é uma maneira conveniente de se construir uma expressão regular a partir de expressões regulares menores.

Podemos criar a “base” de uma expressão regular com um único valor ou um conjunto possível de valores:

REG(int i);
REG (const IntArgs &x);

No exemplo abaixo, r corresponde a “1” e s corresponde a “(0|1)”.

REG r(1);

int v[] = {0, 1};
REG s(IntArray(vector<int>(v, v+2)));

Os operadores * e + foram convenientemente sobrescritos para modelar respectivamente “0 ou mais repetições” e “1 ou mais repetições”, por exemplo

REG r(1);
REG s = *r;
REG t = +r;

A variável s corresponde à expressão regular “1*” e t à “1+”.

O operador () também foi sobrescrito com duas versões: recebendo um inteiro n como parâmetro, que indica que a expressão da variável deve aparecer pelo menos n vezes; e a outra versão recebendo n e m, indicando que a expressão deve aparecer entre n e m (inclusive) vezes. Assim, no exemplo

REG r(1);
REG s = r(10);
REG t = r(3, 4);

A variável s corresponde à “1{10,}*” e t corresponde a “1{3,4}”.

Note que uma expressão regular seguida por “{n}” deve aparecer exatamente n vezes (e não pelo menos n vezes). Portanto, para modelar esse caso usando REG, devemos fazer

REG s = r(n, n);

Veremos a utilidade desse tipo de restrição no exemplo do Nonograma!

Cópia e clone

Como o algoritmo usa backtrack, ele precisa manter cópias para eventualmente voltar a uma solução anterior. Para isso precisamos implementar o método puramente virtual da classe Space, o copy(), retornando um ponteiro para a cópia criada.

virtual Space* copy(bool share) = 0;

A flag share está relacionada com o uso de múltiplas threads, mas não vamos nos preocupar com ela nesse post introdutório. Na cópia, o seguinte construtor da classe Space deve ser chamado:

Space::Space(boolean clone, Space &space);

Para fazer o clone de uma variável, podemos usar o método update(), presente na classe base dos tipos IntVar e IntVarArray:

template<class VarImp>
void Gecode::VarImpVar< VarImp >::update(Space &home, bool share, VarImpVar< VarImp > &y) 

Ele equivale a um clone. Existe um construtor de IntVar que recebe uma referência para outra IntVar, mas ele não cria um cópia e sim uma referência. Por exemplo,

IntVar x(y);

Aqui x e y referem-se à mesma variável.

Branching

Precisamos especificar o modo como será feito o backtracking através do método branch().

branch (Home home, const IntVarArgs &x, IntVarBranch vars, IntValBranch vals)

O primeiro parâmetro especifica o espaço onde a regra de branching será criada, x é um vetor de variáveis sobre o qual faremos branch, vars indica define como será feita a escolha das variáveis. O parâmetro vals indica como será feita a escolha dos valores.

Nos exemplos usaremos sempre a seguinte configuração:

branch(*this, sol, INT_VAR_SIZE_MIN, INT_VAL_MIN);

Aqui, sol representa a solução, INT_VAR_SIZE_MIN indica que o backtracking sempre fará branching sobre as variáveis com menor domínio primeiro e o parâmetro INT_VAL_MIN indica que os valores “chutados” serão feitos em ordem crescente.

Resolvedores

No Gecode há três tipos de motores de busca (search engines), um que usa busca em profundidade (chamado de DFS), outro que usa Branch-and-Bound (BAB) e um chamado Depth First Restart, que não sei exatamente o que é, mas talvez seja uma busca em profundidade iterativa (Iterative deepening depth search).

Os dois últimos motores são usados para quando se deseja otimizar uma função objetivo. Nos nosso exemplos estamos preocupados apenas em encontrar uma solução para o problema, então vamos usar apenas o DFS.

O resolvedores são um template para um tipo genérico e podem ser instanciados usando uma instância desse tipo. No nosso primeiro exemplo vamos implementar a classe SendMoreMoney e portanto podemos instanciar o motor de busca fazendo:

SendMoreMoney *m = new SendMoreMoney();
DFS<SendMoreMoney> e(m);

Os resolvedores definem o método next(), que retorna uma solução do problema (que é uma instância do modelo) e avança para a próxima. Se nosso modelo definir a função de imprimir uma solução, print(), podemos imprimir todas as soluções encontradas da seguinte maneira:

while(SendMoreMoney* s = e.next()){
    s->print();
    delete s;
}

A seguir, vamos comentar sobre 4 problemas clássicos e apresentar soluções usando CP. Os códigos-fontes estão disponíveis no Github e são adaptações dos códigos providos pela própria Gecode.

1. Puzzles Alpha-Numéricos

Um puzzle que pode ser resolvido com programação por restrições é aquele em que são dadas equações de palavras e cada letra da palavra deve ser substituída por um algarismo de modo que a equação seja satisfeita.

Letras iguais devem ser substituídas pelo mesmo algarismo, letras diferentes devem ter algarismos diferentes e a primeira letra de cada palavra não pode ser substituída por 0.

Um exemplo clássico é:

SEND + MORE = MONEY

Podemos resolver esse exemplo definindo 8 variáveis D, E, M, N, O, R, S, Y sujeitas às seguintes restrições:

1) As variáveis devem pertencer ao conjunto de inteiros [0-9].
2) M e S devem ser diferentes de 0.
3) As variáveis devem ter valores diferentes
4) A seguinte igualdade deve ser satisfeita

S*1000 + E*100 + N*10 + D +
M*1000 + O*100 + R*10 + E =
M*10000 + O*1000 + N*100 + E*10 + Y

Podemos implementar essas restrições da seguinte forma:

// Referencias para melhor legibilidade
IntVar 
s(sol[0]), e(sol[1]), n(sol[2]), d(sol[3]),
    m(sol[4]), o(sol[5]), r(sol[6]), y(sol[7]);

// Números nao podem comecar com 0
rel(*this, s != 0);
rel(*this, m != 0);

// Todas as variaveis devem ter valores distintos
distinct(*this, sol);

// Vetor de inteiros
IntArgs c(4+4+5);
// Vector de variaveis inteiras
IntVarArgs x(4+4+5);

// SEND
c[0]=1000; c[1]=100; c[2]=10; c[3]=1;
x[0]=s; x[1]=e; x[2]=n; x[3]=d;
// MORE
c[4]=1000; c[5]=100; c[6]=10; c[7]=1;
x[4]=m; x[5]=o; x[6]=r; x[7]=e;
// MONEY
c[8]=-10000; c[9]=-1000; c[10]=-100; c[11]=-10; c[12]=-1;
x[8]=m; x[9]=o; x[10]=n; x[11]=e; x[12]=y;

linear(*this, c, x, IRT_EQ, 0);

2. O problema das N-damas

O problema das N-damas (do inglês N-queens) é também bastante conhecido. Dado um tabuleiro de xadrez NxN, encontrar uma solução em que N damas sejam dispostas neste tabuleiro de forma que nenhuma esteja em posição de ataque com a outra. Segundo Hoffman, Loessi e Moore [2], sempre existe solução para N maior ou igual a 4.

Podemos definir a solução em outras palavras: queremos uma solução em que nenhum par de damas esteja na mesma coluna, na mesma linha ou na mesma diagonal. Claramente cada coluna deverá conter exatamente uma dama, de modo que podemos modelar a solução através de um vetor linhas de N posições, onde a linhas[i] representa a linha da rainha na i-ésima coluna.

Se colocarmos uma restrição de que os valores de linhas devam ser diferentes, garantimos que as damas estão em linhas diferentes. Entretanto, isso ainda não impede o posicionamento na mesma diagonal.

Se i e j estão na mesma diagonal principal, então dada a célula da dama i é dada por (linha[i], i) e a de j é (linha[i]+k, i+k). Se estão na diagonal invertida, então a posição de j é (linha[i]+k, i-k).

É fácil ver que i e j compartilham alguma diagonal se e somente se linha[i]-i = linha[j]-j ou se linha[i]+i = linha[j]+j.

Podemos implementar essas restrições da seguinte forma:

for (int i = 0; i<n; i++)
    for (int j = i+1; j<n; j++) {
        rel(*this, sol[i] != sol[j]);
        rel(*this, sol[i]+i != sol[j]+j);
        rel(*this, sol[i]-i != sol[j]-j);
    } 

3. Sudoku

No Sudoku clássico tem-se um tabuleiro 9×9, formado por 9 sub-tabuleiros 3×3. O objetivo é preencher o tabuleiro com algarismos de 1 a 9 de forma que nenhuma coluna, nenhuma linha e nenhum sub-tabuleiro contenha números repetidos. Além disso, na grande maioria das vezes os Sudokus já vêm com alguma de suas células preenchidas.

O Gecode oferece uma estrutura bastante simples de se trabalhar com matrizes, que é a classe Matrix. Temos os métodos row(i) e col(j) que retorna respectivamente a i-ésima linha e a j-ésima coluna.

Além disso, temos o método slice(i1, i2, j1, j2) que retorna a submatriz correspondendo a [i1, i2-1] e [j1, j2-1], o que é útil para modelar a restrição de sub-tabuleiros.

As restrições podem ser implementadas praticamente a partir da definição:

// Linhas e colunas devem ter valores diferentes
for (int i=0; i<N; i++) {
    distinct(*this, m.row(i));
    distinct(*this, m.col(i));
 }

// Restricoes dos sub-quadrados
for (int i=0; i<N; i+=n) {
    for (int j=0; j<N; j+=n) {
        distinct(*this, m.slice(i, i+n, j, j+n));
    }
 }

// Celulas ja preenchidas
for (int i=0; i<N; i++)
    for (int j=0; j<N; j++)
        if (mat[i][j] != '.')
            rel(*this, m(i,j), IRT_EQ, mat[i][j] - '0');

4. Nonograma

No nonograma é dado um tabuleiro com n linhas e m colunas. Para cada linha e coluna é dado um conjunto de números. Isso indica que naquela linha ou coluna deve blocos com exatamente aqueles comprimentos. Considere o exemplo abaixo:

Já tinha falado sobre esse puzzle anteriormente e à época não tinha conseguido pensar em uma solução para ele.

Vimos que o Gecode oferece uma maneira de especificar as restrições usando DFA’s. Se usarmos uma matriz de variáveis binárias como nosso vetor de soluções, então dada uma especificação de linha ou coluna dada por

3 4 5

Podemos criar a seguinte expressão regular:

0* 1{3} 0+ 1{4} 0+ 1{5} 0*

Basicamente, nossa linha ou coluna deve começar com 0 ou mais ‘0‘s, seguido por um bloco de exatamente 3 ‘1‘s. Entre dois blocos consecutivos de ‘1‘s deve haver pelo menos um ‘0‘.

Podemos transformar uma especificação em uma expressão regular da seguinte maneira:

// Expressao regular a partir de uma linha
DFA regexp(std::vector<int> &v) {
    REG r0(0), r1(1);
    REG border = *r0;
    REG between = +r0;
    REG r = border;
    for(size_t i = 0; i < v.size(); i++){
        if(i > 0) r += between;
        r += r1(v[i], v[i]);
    }
    return r + border;
}

Agora basta adicionar uma expressão regular dessas para cada coluna e linha. Nossa entrada é dada por um vetor de vetores com as especificações das linhas (_rows) e das colunas (_cols):

Matrix<BoolVarArray> m(sol, _cols.size(), _rows.size());
    
// Restricoes das colunas
for (size_t w=0; w < cols.size(); w++)
    extensional(*this, m.col(w), regexp(cols[w]));
// Restricao das linhas
for (size_t h=0; h < rows.size(); h++)
    extensional(*this, m.row(h), regexp(rows[h]));
// Branch   
for (int w = 0; w < cols.size(); w++)
    branch(*this, m.col(w), INT_VAR_NONE, INT_VAL_MIN);

Constraint Programming vs. Programação linear Inteira

Muitos dos problemas apresentados aqui também podem ser modelados como programação linear inteira e resolvidos através de um algoritmo de branch-and-bound.

Lembrando, no algoritmo de branch-and-bound resolve-se a relaxação linear do modelo em cada nó da árvore de busca. O valor dessa relaxação serve como limitante inferior (superior) para um problema de minimização (maximização). Com isso o algoritmo pode descartar soluções viáveis do problema sem analisá-las se o valor da relaxação em um nó for pior do que o valor da melhor solução encontrada até o momento.

Em CP não temos o valor desse limitante e portanto em um problema com função objetivo, em geral não se pode afirmar que uma solução é ótima a menos que se tenha analisado todas as soluções viáveis do problema.

Por outro lado, existem algumas modelagem que são complicadas de se fazer em programação linear inteira. A mais comum delas é a restrição de que duas variáveis devam ter valores diferentes.

Por exemplo no caso das N-damas, uma das restrições é de que cada elemento de linha tenha um valor diferente. Uma abordagem que pode ser usada para que variáveis x e y inteiras tenham valores diferentes é

(1) x >= y + 1

ou

(2) x <= y - 1

Lembrando que restrições disjuntas podem ser modeladas através da inclusão de uma variável binária, z que vale 0 se (1) for utilizada e 1 se (2) for utilizada. Dado uma constante M suficientemente grande temos:

(3) x \ge y + 1 - M \cdot z
(4) x \le y - 1 + M \cdot (1 - z)

Se z é 0, (3) vira (1) e (4) torna-se redundante. Se z é 1, (3) torna-se redundante e (4) vira (2).

Uma alternativa mais interessante é modelar os valores das variáveis inteiras como variáveis binárias. No caso do problema das N-damas, ao invés de trabalhar com linhas, poderíamos definir a variável c_{i,j} para cada célula do tabuleiro, sendo c_{i,j} = 1 se a dama está na posição (i,j) do tabuleiro e 0 caso contrário.

As restrições lineares a ser adicionadas são tais que a soma em cada linha e cada coluna seja exatamente 1 e que a soma em cada diagonal seja menor ou igual a 1.

Conclusão

Neste post fizemos uma pequena introdução a programação por restrições usando Geocode. Há muitos detalhes que faltam ser explorados nessa biblioteca como a customização de propagadores e branchers, bem como a comparação do desempenho de diferentes modelos.

Além disso, os exemplos empregados aqui são relativamente simples, com poucas restrições. A técnica de CP vem sendo aplicada a problemas do mundo real onde existem bastante detalhes que são modelados na forma de restrições. Pretendo estudar alguns papers e escrever sobre eles.

Ao decidir estudar CP, fiquei na dúvida sobre qual biblioteca utilizar. Eu pretendia usar a OR-Tools usando Python porque deve ser mais simples escrever os modelos. Entretanto, a documentação dessa bilioteca ainda está muito escassa e por isso acabei escolhendo a Gecode. De qualquer maneira Gecode também tem binding para uma linguagem simples de se escrever, que é o Ruby. Talvez seja uma boa oportunidade para aprender um pouco dessa linguagem.

Referências

[1] Gecode – GEneric COnstraint Development Environment
[2] Constructions for the Solution of the m Queens problem – E. Hoffmann , J. Loessi e R. Moore (Mathematics Magazine, Vol. 4, No. 2)


Review: Logicomix

Agosto 12, 2012

Logicomix é uma estória em quadrinhos sobre a busca do fundamento da matemática. É um livro fantástico porque mistura romance, história, mitologia e matemática. Além disso é uma meta-estória, pois relata o processo de desenvolvimento dos quadrinhos na própria estória.

Um dos autores (e personagem) do livro é Christos Papadimitriou, atualmente professor de teoria da computação em Berkeley. Durante minha iniciação científica cheguei a estudar um de seus livros escrito com Ken Steiglitz sobre Otimização Combinatória, mas achei muito difícil e acabei usando outro :P

Teóricos da computação fazem muito uso da lógica, especialmente os que trabalham com complexidade computacional e computabilidade. A estória dá a entender que Papadimitriou foi convidado como o especialista em lógica, embora o autor principal, Apostolos Doxiadis tenha formação matemática também.

Spoiler! O restante deste post contém um breve resumo do livro, além de uma análise pessoal.

Resumo

Tractatus Logico-Philosophicus

Bertrand Russell é o personagem central do livro que descreve sua saga em busca dos fundamentos da matemática.

Russell aparece em dois planos: em um está no presente, palestrando a um grupo de americanos contrários à adesão dos Estados Unidos à Segunda Guerra Mundial. Durante essa palestra ele conta a história de sua vida, que acontece em um outro plano. A grande maioria dos acontecimentos acontece nesse segundo plano e o Russell do plano presente serve mais como um narrador.

Além desses dois planos temos o plano em que os autores do livro estão elaborando a estória ao mesmo tempo em que ela acontece. Eles geralmente aparecem para justificar alguma discrepância entre a história e a estória, além de explicar conceitos mais técnicos.

Logo criança, Russell torna-se órfão e passa a viver com seus avós na mansão Pembroke. É apresentado aos trabalhos de Euclides por um professor particular de matemática.

Russell segue para o Trinity College, onde conhece Alfred Whitehead. Casa-se com Alys Smith e então fazem uma viagem ao continente, passando primeiramente pela Alemanha, onde conhecem Gottlob Frege e George Cantor (embora o livro deixe claro que Russell não os conheceu pessoalmente).

Na França, conhecem a esposa de Whitehead, Evelyn Wade. A estória retrata um interesse de Russell em Evelyn, embora em nenhum momento do livro pareça ter havido algo mais entre eles. Depois, Russell participa do congresso internacional de matemáticos onde David Hilbert divulga a famosa lista de 23 problemas abertos em matemática.

Neste ponto Russell descobre um paradoxo na teoria dos conjuntos, que abala o mundo da matemática. Whitehead e Russell decidem então começar a escrita do Principia mathematica, que se mostra uma tarefa desgastante.

Russell passa a dar aulas em Cambridge e é quando Ludwig Wittgenstein torna-se seu estudante de doutorado. Evelyn, a esposa de Whitehad acha que está prestes a morrer e pede para Russell consolar seu filho, Eric. Cansado de seus trabalhos com a lógica, Russell sente-se reconfortado por exercitar sentimentos como compaixão e amor para com Eric.

Começa a primeira Guerra Mundial. Russell se posiciona contra a adesão do Reino Unido, o que acaba o levando à prisão. Wittgenstein se alista ao exército Autro-Húngaro enquanto Eric, filho de Whitehead, faz o mesmo pelo lado britânico. Wittgenstein sobreviveu à guerra, fazendo-o mudar sua maneira de ver o mundo. Por outro lado, Eric é abatido em combate.

Após o fim da primeira guerra, Wittgenstein estava impedido de ir à Inglaterra por ser austríaco e portanto se encontra com Russell em território neutro: Haia, Holanda. Nesse encontro Wittgenstein contrapõe diversas ideias de Russell.

Russell casa-se pela segunda vez com Dora Black, tendo o seu primeiro filho. Seu casamento era bastante liberal, sendo que ele aceitava que amantes frequentassem sua casa. Seus pais também tiveram um casamento desta forma. Juntos decidiram fundar uma escola progressista para crianças, a Beacon Hill. À mesma época, Wittgenstein começa a dar aulas em escolas primárias.

O matemático Moritz Schlick passa a organizar o Círculo de Viena, uma associação de filósofos que se encontravam em torno da Universidade de Viena. Em uma dessas reuniões, Russell conhece Kurt Gödel e John Von Neumann e foi nesse encontro que Gödel anunciou seu primeiro teorema de incompletude, destruindo o sonho de Russell de definir um conjunto de axiomas que pudesse demonstrar todas as verdades matemáticas. Em seguida, as influências nazistas começaram a se espalhar pelo continente e em 1936, Schlick foi assassinado por um fanático nazista, o que pôs fim ao círculo e é nesse ponto que Russell conclui sua narrativa.

A estória termina voltando para o plano dos autores, que vão assistir à participação de Anne Bardy em uma encenação da peça Oresteia.

Matemática

Das diversas referências matemáticas presentes no livro, gostaria de comentar sobre as três que achei mais interessante.

Paradoxo de Russell

Em 1901, Russel apresenta um paradoxo da teoria dos conjuntos. Esse paradoxo por ser melhor entendido através de um exemplo, o paradoxo dos barbeiros.

Considere uma cidade onde existe apenas um barbeiro e uma lei que diz que o barbeiro deve fazer a barba de todos os homens que não se barbeiam sozinhos, mas não pode fazer a barba de quem se barbeia sozinho.

Consideremos duas possibilidades: o barbeiro se barbeia sozinho ou não. Se ele se barbeia sozinho, está infringindo a lei, porque ele não pode barbear quem se barbeia sozinho. Por outro lado, se ele não se barbeia, a lei o obriga a fazer sua própria barba. Conclui-se que a lei é contraditória.

A generalização para a teoria dos conjuntos é a seguinte: seja R conjunto de todos os conjuntos que não contém a si mesmos. Pergunta-se: R está contido em si mesmo? Vamos analisar duas possibilidades. Se R está contido em si mesmo, então R é um conjunto que contém a si mesmo e não poderia estar em R. Por outro lado, se R não está contido em si mesmo, ele é um conjunto que não contém a si mesmo e portanto deveria ser incluído em R :)

O Infinito e a Teoria dos Conjuntos

Em Logicomix, Russell descreve o paradoxo do hotel de Hilbert que exemplifica o quão contra-intuitivo é trabalhar com o conceito de infinito. A ideia por trás do paradoxo pode ser usada para provar, por exemplo, que existe uma bijeção entre os números naturais pares e os números naturais!

Isso está relacionado com o trabalho de George Cantor, que criou os conceitos de conjuntos enumeráveis e não enumeráveis, sendo os enumeráveis aqueles com mesma cardinalidade dos números naturais, ou seja, para os quais existe um mapeamento um pra um de seus elementos para com os números naturais.

Assim como os números naturais pares têm mesma cardinalidade dos números naturais, Cantor demonstrou que os números inteiros são enumeráveis assim como o conjunto dos números racionais! O conjuntos dos números reais não é enumerável.

Os 23 problemas de Hilbert

David Hilbert divulgou uma lista de 23 problemas não resolvidos à época de 1900. Há três problemas sobre os quais gostaria de comentar.

O principal problema da lista, e que até hoje não foi resolvido, é o problema 8, que é demonstrar a Hipótese de Riemann. O livro The music of primes, fornece uma introdução bem acessível sobre a hipótese, a função zeta de Riemann e a relação com números primos.

Um problema importante também é o número 2, provar que os axiomas da aritmética são consistentes. O segundo teorema da incompletude de Gödel mostra que não é possível provar esse teorema usando a própria aritmética. Entretanto, não há um consenso se isto é uma solução ou não para o problema.

Finalmente, um problema que eu acho particularmente interessante é o número 10: encontrar um algoritmo que determina se uma equação Diofantina polinomial com coeficientes inteiros tem uma solução.

Gosto desse problema porque é fácil de enunciar, está relacionado à área que pesquisei no mestrado (programação linear inteira) e porque foi resultado de um trabalho longo e de contribuição de diversas pessoas, Martin Davis, Yuri Matiyasevich, Hilary Putnam e Julia Robinson.

Mitologia

Algumas referências mitológicas aparecem na estória. A primeira é a um mito indiano sobre a tartaruga que segura o mundo. Russell faz a analogia como o mundo sendo a matemática e a tartaruga seus fundamentos.

Em certo ponto Whitehead mostra a Russell o quadro “As Danaides” de John Waterhouse. As Danaides são as 50 filhas de Dánao, que estavam prometidas aos 50 filhos de Egipto, seu irmão gêmeo. Todas exceto Hipernestra assassinaram seus esposos na noite de núpcias e como punição foram obrigadas por Hades a encherem um jarro de água com furos durante toda a eternidade.

As Danaides: pintura a óleo de John Waterhouse

Whitehead usou o mito como metáfora para o trabalho do Principia Mathematica. Russell queria encontrar um fundamento para a matemática, mas sempre via necessidade de fundamentar cada base que encontrava. Como se disse no livro, ele estava procurando a base da tartaruga que segurava o mundo, mas encontrou uma torre infinita de tartarugas.

Finalmente, temos a encenação peça Oresteia, uma trilogia escrita pelo dramaturgo grego Ésquilo.

O livro retrata a terceira peça, Eunêmides, no qual as Erínias, deusas da vingança decidem punir Orestes. Atena intervém e decide que o futuro de Orestes deve ser decidido por um júri popular.

Literatura e Teatro

Alguns clássicos da literatura e teatro aparecem na estória. O avô de Russell possuia uma biblioteca onde Bertie descobriu a Divina Comédia de Dante Alighieri, que foi chamado de o livro proibido.

Em Cambridge lê Pais e Filhos, de Ivan Turguniev. Segundo a Wikipédia, o protagonista do livro é Bazárov, um jovem intelectual materialista, que nega o amor, a arte, a religião e a tradição, e diz acreditar apenas em verdades cientificamente comprovadas pela experiência. Essa negação da religião e tradição podem ser encontradas na personalidade de Russell na estória.

A estória também retrata a peça de teatro Espectros, do norueguês Henrik Ibsen. Há um destaque para a frase “os pecados dos pais se repetem nos filhos”. Talvez seja uma referência ao estilo de vida dos pais de Russell, que acabou se repetindo em seu casamento com Dora.

Russell passa a recitar versos do poema Alastor, de Percy Shelley. Segundo a Wikipedia, Alastor conta a história de um poeta que persegue a parte mais obscura da natureza em busca de “verdades estranhas em terras desconhecidas”. Podemos enxergar um paralelo aqui com a busca pelos fundamentos da matemática por porte de Russell.

Ao conhecer Alys, Russell cita diversos personagens do livro Alice no País das Maravilhas, de Lewis Carroll, como o Tweedledee, Tweedledum, Gato de Cheshire e o Chapeleiro maluco.

Após o fim da Primeira Guerra Mundial Russell demonstra seu descontentamento com o dadaísmo e cita versos do poema The Second Coming, the William Butler Yeats, que refletem sua opinião.

Conclusão

Gostei bastante deste livro e recomendo a quem gosta de lógica e história da matemática. Eu particularmente não sou muito fã de história em quadrinhos, achei que se fosse em prosa a estória poderia conter mais detalhes. Lendo sobre a vida dos principais personagens na Wikipedia, penso que faltou um pouco de coesão nos fatos relatados.

Achei excelente inserir referências a clássicos da literatura para ajudar a caracterizar a personalidade de Russell. Fico feliz de ter escrito esse resumo e análise porque acho que consegui enxergar alguns detalhes que tinham passados despercebidos na primeira leitura.

Interpretei o fato da estória ser uma meta-estória como uma alusão ao paradoxo de Russell, que tem como base conjuntos que contêm a si mesmos. No caso do Logicomix é uma estória que contém a si mesma.

A encenação de Orestéia me pareceu desconexa com o restante da estória. Talvez a ideia fosse mesmo contar duas estórias independentes (a de Bertrand e a dos autores).

Leitura adicional

Alguns livros e links que eu selecionei para o aprofundamento no conteúdo do Logicomix. Na verdade só li o primeiro e é o único que posso recomendar. Os outros estão na minha pilha de leitura.

[1] The Music of the Primes de Marcus du Sautory – Já li, e gostei muito. Fala sobre os 23 problemas de Hilbert e a hipótese de Riemmann de uma maneira bastante acessível.
[2] Alice no país das maravilhas de Lewis Carroll – Lewis Carroll era um matemático e lógico. Este livro é mencionado no Logicomix.
[3] Scott Aaronson – Filosofia e Ciência da Computação Teórica, Scott Aaronson é um professor de Teoria de Computação no MIT e conhecido por seu trabalho em Computação Quântica.


Paul Graham e Combinatores em Haskell

Agosto 5, 2012

Paul Graham é um ensaísta, programador e investidor. É graduado em Cornell e possui doutorado por Harvard [1].

Como ensaísta, escreveu diversos artigos sendo o mais famosos deles o “A plan for spam” sobre o uso de um filtro Bayesiano para combater spam.

Como programador, Graham é conhecido por seu trabalho com Lisp, tendo escrito livros sobre esta linguagem e vem desenvolvendo um dialeto chamado Arc. Também desenvolveu a primeira aplicação web chamada Viaweb, posteriormente adquirida pela Yahoo!

Como investidor, fundou em 2005 a empresa Y Combinator que faz investimentos em start-ups. Algumas das empresas financiadas pela Y-Combinator são: Dropbox, Airbnb, reddit e Posterous.

Sobre o nome da empresa, eis uma tradução livre do FAQ deles:

Porque vocês escolheram o nome “Y Combinator?”

O combinador Y é uma das ideias mais legais em ciência da computação e é também uma metáfora para o que nós fazemos. É um programa que roda programas; é uma empresa que ajuda a abrir empresas.

Neste post gostaria de apresentar algumas notas de estudos sobre combinadores em Haskell, descrevendo os principais tipos de combinadores incluindo o tipo Y.


Combinadores em Haskell

Esse post teve origem durante os estudos do Capítulo 9 do Real World Haskell.

Em certo ponto do capítulo o autor menciona o termo de combinadores, não deixando muito claro o que são e para que servem. Fui pesquisar um pouco sobre o assunto e decidi escrever um post.

Um combinador pode ser definido como uma função lambda que não tem variáveis livres. Uma variável livre é uma variável que não foi passada como parâmetro na função lambda. Alguns exemplos de funções lambda em Haskell:

1) A função abaixo é um combinador pois a variável x está no parâmetro

\x -> x

2) No exemplo a seguir y é uma variável livre e portanto não é um combinador.

\x -> x y

3) Aqui ambos x e y foram passadas por parâmetro, então temos um combinador.

\x y -> x y

4) O exemplo abaixo não é um combinador porque f não foi passado como parâmetro

\x y -> f (x y)

5) A seguir temos uma pegadinha. Observe que o operador + é na verdade uma função que recebe dois argumentos, como no exemplo (4). Porém como o operador não foi passado como parâmetro, também não é um combinador.

\x y -> x + y 

Simplificadamente, podemos pensar em um combinador como uma função que recebe funções e retorna outra função resultado da combinação das funções de entrada.

Tipos de combinadores

Nas próximas seções, vamos apresentar alguns dos combinadores mais conhecidos. Esses combinadores têm como nome uma única letra maiúscula. Porém, no livro To Mock a Mocking Bird [2], Raymond Smullyman apelida os diferentes tipos de combinadores com nomes de pássaros. Por isso, cada seção terá o nome do combinador e entre parênteses o apelido dado por Smullyman.

Combinador I (Identity Bird ou Idiot Bird)

Este é o combinador mais simples, a identidade. É uma função que retorna o seu próprio parâmetro. Em Haskell podemos escrever:

i x = x

Essa é justamente a definição da função id da biblioteca Prelude.

Combinador K (Kestrel)

Esse é o combinador constante, ele recebe dois argumentos e ignora o segundo. Em Haskell podemos escrever:

k x y = x

Essa é justamente a definição da função const da biblioteca Prelude.

Combinador S (Starling)

O combinador S é uma função que pode ser definida da seguinte maneira em Haskell:

s x y z = x z (y z)

Podemos escrever o combinador I usando apenas os combinadores S e K como

i = s k k

A demonstração é a seguinte:

Aplicando a função (s k k) sobre um argumento x temos

(s k k) x = s k k x

Substituindo s por sua definição,

(s k k x) = k x (k x)

Agora seja f = (k x) uma função qualquer. Temos que k x f = x por definição, então

k x (k x) = k x f = x = i x

É possível mostrar que qualquer combinador pode ser escrito como função dos combinadores S e K!

Combinador B (Bluebird)

O combinador B pode ser escrito em função de S e K como

b = s (k s) k

Vamos ver a cara dessa função aplicada a alguns argumentos. Seja f1 = (k s). Usando currying vemos que essa é uma função que recebe um argumento e sempre retorna s. Aplicando b sobre um argumento x, temos

b x = s f1 k x = f1 x (k x) = s (k x)

Seja f2 = (k x). Temos que f2 é uma função que recebe um argumento qualquer e sempre retorna x. Assim, temos b x = s f2. Vamos aplicá-la sobre mais dois parâmetros y e z:

(s f2) y z = s f2 y z = f2 z (y z) = x (y z)

Ou seja

b x y z = x (y z)

O que esta função faz é a composição das funções x e y e é justamente a definição do operador (.) do Haskell.

Combinador C (Cardinal)

Esse combinador pode ser escrito em função dos combinadores K, S e B como

c = s (b b s) (k k)

Pode-se mostrar que esse combinador equivale a

c f x y = f y x

Essa é justamente a definição do operador flip do Prelude, que retorna uma função com a ordem dos parâmetros trocada.

Combinador Y (Sage Bird)

Simplificadamente o combinator Y é um combinador que transforma uma função não recursiva em uma função recursiva!

Antes de descrevê-lo, vamos analisar como faríamos isso sem o combinador Y. Para isso, vamos usar como exemplo uma função que calcula o fatorial [8]. Fazendo uso de recursão, podemos escrever:

fat = \n -> if n == 0 then 1 else n * fat (n - 1)
fat 5 -- imprime 120

A expressão lambda acima não é um combinador porque depende de fat, que não foi passado como parâmetro.

Vamos tentar passar a função por parâmetro então

fat' = \f n -> if n == 0 then 1 else n * f (n - 1)

Observe que fat’ não é uma função recursiva. Agora fazemos o seguinte:

fat = fat' fat
fat 5 -- imprime 120

Estamos definindo fat como sendo o resultado de fat' quando passamos fat como parâmetro. Parece mágica, mas em linguagens com avaliação preguiçosa isso vai funcionar. Por quê?

Vamos analisar alguns exemplos. A função fat pode ser desmembrada em

fat = 
  fat' fat = 
      \n -> if n == 0 then 1 else return n * fat (n - 1)

Para n = 0, a função retornará 1 e não se dará ao trabalho de calcular fat(-1).

Vamos agora desmembrar a função duas vezes:

fat = 
  fat' fat = 
      fat' (fat' fat) = if n == 0 then 1 else return n * 
      (if (n - 1) == 0 then 1 ele return (n-1)* fat (n - 2))

Para n = 1, é possível ver que uma avaliação preguiçosa não precisa desmembramentos do que isso.

Ok, conseguimos transformar uma função não recursiva fat' em uma função recursiva. Vamos criar uma função auxiliar para que a função fat' seja passada como parâmetro

aux f = f (aux f)
fat = aux fat'
fat 5 -- imprime 120

A função aux faz o que queremos que o combinador Y faça: recebe uma função não recursiva (por exemplo fat') e retorna uma recursiva (nesse caso fat). Entretanto, aux não é um combinador porque o aux que é chamado recursivamente é uma variável livre.

Vamos apresentar então o combinador Y. Sua definição teórica é dada por

y = \f -> (\x -> f (x x)) (\x -> f (x x))

Ainda não consegui entender essa definição de maneira clara o suficiente para arriscar uma explicação aqui. Minha sugestão é ler [8], onde Mike Vaniel deriva a função acima em Scheme.

De qualquer maneira, se formos implementá-lo em Haskell, teremos um erro de compilação devido a tipo infinito [3]. Para resolver esse problema, [4] apresenta a seguinte solução:

newtype Rec a = In { out :: Rec a -> a }

y :: (a -> a) -> a
y = \f -> (\x -> f (out x x)) (In (\x -> f (out x x)))

Para evitar problemas com tipo infinito, encapsulamos o segundo termo (\x -> f (x x)) em um novo tipo, o Rec a, através do construtor In. As funções lambda recebem x que é do tipo Rec a e por isso não podemos aplicar x sobre x diretamente. Antes devemos “desencapsular” a função contida nele usando out.

Lembrando, o newtype define uma estrutura semelhante a um tipo de dado algébrico, com a diferença que só se permite um construtor, no caso definido pelo In, e um “getter”, especificado pelo out.

Por exemplo, vamos definir um tipo chamado NovoTipo que encapsula uma função que recebe um tipo genérico e retorna esse mesmo tipo genérico, ou seja, com tipo a -> a.

newtype NovoTipo a = Construtor { getter :: a -> a }

Podemos encapsular uma função que recebe e retorna um inteiro. Por exemplo:

somaUm::Int -> Int
somaUm v = v + 1
let x = Construtor somaUm

Podemos verificar o tipo dessa variável no ghci:

> :type x
x :: NovoTipo Int

O getter extrai a função que foi encapsulada, ou seja, podemos fazer:

> (getter x) 9
10

Outros combinadores

Este site [5] tem uma lista mais extensa de combinadores. Existe um pacote do Haskell chamado data-aviary [6] contendo a implementação de diversos desses combinadores.

Reg Braithwaite discute alguns combinadores na prática usando Ruby no seu blog/projeto homoiconic [7].

Conclusão

Fiquei satisfeito em desviar um pouco da leitura do livro Real World Haskell para aprender mais sobre combinadores. Graças a isso acabei descobrindo coisas interessantes como a origem do nome da empresa do Graham e que algumas funções muito usadas em Haskell são combinadores.

Além disso, embrora o combinador Y não seja tão útil na prática, as ideias por trás dele são muito interessantes (e, na minha opinião, complicadas!).

Referências

[1] Paul Graham – Biografia
[2] How to Mock a Mocking Bird – Smullyman
[3] StackOverflow – Y Combinator in Haskell
[4] [Haskell] How to define Y combinator in Haskell
[5] Combinator Birds
[6] Hackage – The data-aviary package
[7] Github – Homoiconic
[8] Mike’s World-O-Programming – The Y Combinator
[9] Y-Combinator em Javascript


Introdução a Jbehave

Julho 22, 2012

Neste post vamos falar um pouco sobre desenvolvimento orientado a comportamento (Behaviour Driven Development) também conhecido como BDD e focar em uma das ferramentas que facilitam a execução dessa prática, o jbehave.

As ferramentas utilizadas são Maven 3, jbehave (v 3.6.8) e o jUnit (4.10). O código-fonte do projeto está disponível no github.

Introdução

O desenvolvimento orientado a comportamento é uma evolução do desenvolvimento orientado a testes (Test Driven Development) ou TDD. Falamos um pouco sobre TDD em um post anterior.

Uma das motivações para a reformulação da prática foi o fato de que muitos adeptos não percebiam que TDD é mais sobre definição de comportamento do que sobre testes propriamente dito.

O BDD visa minimizar falhas de comunicação entre o pessoal de negócio e o pessoal técnico. Para isso, se baseia em um vocabulário comum e conciso para garantir que todos usem os mesmos termos, utilizando em geral o projeto orientado a domínio (Domain Driven Design).

Os testes definem comportamentos, ou seja, a relação entre os domínios do sistema. A ideia é que com o uso de um vocabulário comum, os testes sirvam como documentação das especificações do sistema, de modo que possam ser lidos pelos desenvolvedores, testadores e analistas de negócio.

Algumas ferramentas auxiliam nesse processo, permitindo a descrição dos testes em linguagem natural. Algumas dessas ferramentas para trabalhar com BDD em Java são o jbehave, o Concordion e o easyb (que na verdade usa Groovy). Uma outra bastante conhecida é o RSpec, voltada para Ruby.

Jbehave

O jbehave é um framework de desenvolvimento orientado a comportamento ou BDD (Behaviour Driven Development), desenvolvido por Dan North.

http://brianrepko.files.wordpress.com/2010/09/jbehave-logo.png

Exemplo prático

O uso do jbehave consiste em 3 passos principais:

  1. A implementação de uma classe POJO com anotações para criar uma correspondência entre o texto da estória e os métodos dessa classe.
  2. A criação de uma estória (essencialmente um arquivo de texto com extensão .story)
  3. A implementação de um embutidor ou embarcador (traduções livres de embedder) para que as estórias sejam executadas através de um framework de testes, que no nosso caso será o JUnit.

Vamos considerar um exemplo bastante simples: uma classe com um método que soma dois inteiros e guarda o resultado em uma variável interna. Vamos chamá-la de Adder:

public class Adder {

    private int result;
	
    public void add(int a, int b){
        result = a + b;
    }	
    public int getResult(){
        return result;
    }	
}

Implementação do POJO

Vamos criar uma classe que fará a correspondência entre a estória e os métodos de teste. Vamos chamá-la de AdderSteps.

public class AdderSteps {
	
    private Adder adder;
	
    @Given("um somador é criado")
    @Aliases(values={"um somador é instanciado"})
    public void theAdderIsCreated(){
        adder = new Adder();
    }
	
    @When("eu adiciono $a e $b")
    public void iAddTwoNumbers(int a, int b){
        adder.add(a, b);
    }

    @Then("o resultado deve ser $c")
    public void theResultMustBe(int c){
        assertEquals(adder.getResult(), c);
    }

}

O método theAdderIsCreated instancia um Adder, iAddTwoNumbers faz a soma dos dois números através do método do Adder e theResultMustBe verifica se o resultado da soma é igual ao parâmetro (usa o JUnit).

O principal destaque do código acima são as anotações Given, Aliases, When e Then.

A anotação Given faz a associação com a linha começando com a palavra-chave given no arquivo de texto e continuando com o texto passado como parâmetro. Assim, se houver a linha no arquivo de texto da estória

Given um somador é criado

O método theAdderIsCreated() será chamado. O uso da anotação Aliases permite que o método seja chamado com outros nomes. No caso a linha abaixo

Given um somador é instanciado

também chamaria o método.

As anotações When e Then são análogas para as palavras-chaves when e then. Porém, no exemplo vemos que as strings de parâmetro dessas anotações têm o símbolo $.

Isso faz a associação das variáveis com os valores presentes no arquivo de estória. Por exemplo, a linha

When eu adiciono 1 e 2

associará a variável a com 1 e a variável b com 2, chamando o método iAddTwoNumbers(1, 2).

Definição de uma estória

Com a classe que faz as correspondências implementada, podemos criar um caso de teste através de uma estória:

Given um somador é criado
When eu adiciono 1 e 4
Then o resultado deve ser 5

Veja como o teste fica bem mais legível nessa forma do em código, servindo como uma documentação natural.

Se as especificações são dadas em português então faz sentido o texto também ser escrito assim. Entretanto, o uso de palavras-chaves em inglês deixa o texto estranho. A seguir veremos como contornar este problema.

Implementação do embutidor para o JUnit

Agora podemos embutir nossa estória em um framework de testes, no caso o JUnit. O jbehave define uma classe própria para isso chamada JUnitStory. Agora basta estendê-la e sobrescrever o método stepsFactory(), para instanciar a nossa classe de associação, o AdderSteps.

public class TestAdder extends JUnitStory {
 
    @Override
    public InjectableStepsFactory stepsFactory() {        
        return new InstanceStepsFactory(configuration(), new AdderSteps());
    }
}

O método configuration() retorna um objeto Configuration contendo diversas configurações. Para personalizá-las, podemos sobrescrever o método configuration():

@Override
public Configuration configuration() {
    return new MostUsefulConfiguration()
        // Onde procurar pelas estórias
        .useStoryLoader(new LoadFromClasspath(this.getClass()))
        // Para onde fazer os reports
        .useStoryReporterBuilder(new StoryReporterBuilder()
                                 .withDefaultFormats()
                                 .withFormats(Format.CONSOLE, Format.HTML)); 
}

A classe Configuration usa o encadeamento de método para obter uma interface mais fluente.

O método MostUsefulConfiguration() instancia uma configuração padrão e o useStoryLoader() personaliza o modo como as estórias são carregadas. Neste caso, estamos especificando que ele fica no mesmo caminho da classe.

A classe está no pacote me.kuniga.jbehave e por convenção fica em test/java/me/kuniga/jbehave. Portanto, podemos colocar as estórias em test/resources/me/kuniga/jbehave que o maven tratará de colocá-las no mesmo caminho.

O método useStoryReporterBuilder() configura como os resultados do teste serão exibidos. No código acima estamos indicando que tais resultados serão exibidos na saída padrão e exportados para html, que por padrão ficam em target/jbehave/

A classe JUnitStory possui um método anotado com @Test e por isso nossa classe TestAdder será executada pelo JUnit.

Nota: Até o momento não consegui rodar os testes através do maven devido a problemas de encoding (a associação com os métodos não é feita corretamente). Se eu descobrir o porquê disso edito o post. Por ora, é possível rodar os testes pelo próprio Eclipse.

Ao executarmos os testes, um relatório estará disponível em target/jbehave/me.kuniga.jbehave.test_adder.html.

Palavras-chaves em Português

É possível configurar o JBehave para reconheça as palavras-chaves traduzidas. Primeiramente devemos instanciar um objeto da classe Keywords com o idioma português. Felizmente o JBehave já provê um arquivo de propriedades com as traduções. Portanto, basta fazermos:

Keywords keywords = new LocalizedKeywords(new Locale("pt"));

As traduções para as palavras-chaves são: “Given” – “Dado que“; “When” – “Quando“; “Then” – “Então“.

Então configuramos as palavras-chave e o parser das estórias através dos métodos useKeywords() e useStoryParser() [2].

O método configuration() completo fica:

public Configuration configuration() {
    	
    Keywords keywords = new LocalizedKeywords(new Locale("pt"));
    	
    return new MostUsefulConfiguration()
        .useKeywords(keywords)
        .useStoryParser(new RegexStoryParser(keywords))
        // Onde procurar pelas estórias
        .useStoryLoader(new LoadFromClasspath(this.getClass()))
        // Para onde fazer os reports
        .useStoryReporterBuilder(new StoryReporterBuilder()
                                 .withDefaultFormats()
                                 .withFormats(Format.CONSOLE, Format.HTML)); 
}

Agora podemos re-escrever nossa estória como:

Dado que um somador é instanciado
Quando eu adiciono 1 e 4
Então o resultado deve ser 5

Código-fonte do JBehave

O código-fonte do jBehave vem com alguns exemplos. Pode-se obter o código usando git:

git clone git://git.codehaus.org/jbehave-core.git

Os exemplos se encontram em jbehave-core/examples/.

O arquivo de propriedades com a tradução das palavras-chaves além de outros termos pode ser encontrado em:

jbehave-core/jbehave-core/src/main/resources/i18n/keywords_pt.properties

Conclusão

Achei muito bacana a ideia de gerar o código a partir de uma descrição textual, principalmente em casos em que gerar um caso de teste exige muita configuração.

Além do mais, o teste fica naturalmente documentado e essa documentação fica atrelada ao código, não correndo o risco de ficar ultrapassada (princípio DRY).

Para criar instâncias complexas é interessante o uso do encadeamento de métodos sobre o qual falamos acima. Cada método de configuração poderia ser associado a um @Given. Combinando com as ideias de [3], poderíamos especificar um linguagem de domínio específico (Domain Specific Language ou DSL) para testes usando o jbehave!

Referências

[1] Behaviour-driven.org – Introduction
[2] jbehave – Stories in your language
[3] The Java Fluent API Designer Crash Course


Kuratowski e a planaridade de grafos

Julho 14, 2012

Kazimierz Kuratowski (1896-1980) foi um matemático polonês cuja pesquisa se concentrou na área de topologia.

Ele viveu em um época e local diretamente afetados por duas guerras mundiais. Em 1913 foi estudar engenharia na Escócia mas seus estudos foram logo interrompidos devido ao início da primeira guerra. Entre 1927 e 1934 ele lecionou na politécnica de Lviv, onde frequentava a Cafeteria Escocesa, um estabelecimento famoso por ser o local onde se reuniam membros da escola de matemática de Lviv.

A partir de 1934 ele se transferiu para a Universidade de Varsóvia. Durante a segunda guerra ele passou a dar aulas clandestinamente pois a educação superior na Polônia foi proibida durante a ocupação alemã. Com a reabertura da Universidade em 1945, Kuratowski voltou a lecionar, tendo depois ocupado diversos cargos importantes e contribuído com a reconstrução da vida científica na Polônia [1].

Neste post gostaria de falar sobre um resultado obtido por Kuratowski em teoria dos grafos, mais especificamente na caracterização de grafos planares.

Grafos Planares

Grafos planares formam uma classe de grafos com a propriedade que existe algum desenho deles no plano de forma que suas arestas não se cruzem.

Exemplos de grafos planares são o K_4 (grafo completo de 4 vértices) e árvores, como mostra a Figura 1.

Figura 1: exemplo de grafos planares

Exemplos de grafos não planares são o K_5 (grafo completo de 5 vértices) e o K_{3,3} (grafo bipartido completo com ambas partições de tamanho 3), conforme a Figura 2.

Figura 2: Exemplos de grafos não-planares

Teorema de Kuratowski. Kuratowski mostrou que um grafo é planar se e somente se ele não contém um subgrafo que é uma subdivisão do K_5 e nem do K_{3,3}.

Uma subdivisão de um grafo consiste em colocar vértices “no meio” das arestas. Por exemplo, na Figura 3 temos uma subdivisão do K_{3,3} e segundo o teorema de Kuratowski, este não é um grafo planar.

Figura 3: Uma subdivisão do K_{3,3}

Característica de Euler. Grafos planares possuem a característica de Euler. Dado um desenho de um grafo planar conexo, com v vértices, e arestas e f faces, então v - e + f = 2

Grafos-moeda. (coin graphs) Comentei brevemente sobre grafos-moeda em um post sobre grafos de discos (disk graphs). Voltamos a falar dessa classe de grafos pois o teorema de Koebe diz que grafos-moeda e grafos planares são equivalentes [3].

Mais especificamente, o teorema diz que dado um grafo planar G, existe um conjunto de discos cujo grafo moeda é G. O grafo moeda de um conjunto de discos é um grafo com um vértice para cada disco e uma aresta entre dois vértices se seus discos correspondentes se tocam (lembrando que não é permitida sobreposição dos discos).

Por outro lado, dado um conjunto de discos no plano, podemos desenhar um grafo planar. Desenhe cada vértice do grafo no centro de cada disco e ligue por um segmento de reta os centros de dois discos que se tangenciam. É possível ver que o grafo desenhado é planar e ainda, todas as arestas são linhas retas.

A conclusão é que para todo grafo planar existe um desenho que utiliza apenas linhas retas para representar as arestas, que é justamente o que afirma o Teorema de Fáry.

Teste de Planaridade

Embora Kuratowski tenha dado uma caracterização bastante simples de grafos planares, não é trivial verificar essa condição para um grafo qualquer.

Foram desenvolvidos diversos algoritmos de teste de planaridade lineares no tamanho do grafo, ou seja, O(V + E) (portanto assintoticamente ótimos). O primeiro desses algoritmos a ser publicado foi desenvolvido por Hopcroft e Tarjan [4] (ganhadores do prêmio Turing em 1986).

Essa primeira versão era bastante complexa e portanto novas abordagem foram publicadas ao longo dos anos buscando um algoritmo mais simples. Um breve histórico pode ser conferido na Wikipedia.

A mais recente data de 2004 e é devida a Boyer e Myrvold [5], sobre a qual falaremos a seguir.

O Algoritmo de Boyer e Myrvold

Vamos analisar alguns conceitos chaves desse algoritmo, sem entrar em detalhes, pois o intuito do post é apenas passar uma ideia geral do algoritmo. Para mais detalhes, consulte [5, 6].

Considere um grafo G = (V, E) não direcionado. Sem perda de generalidade, vamos supor que G é conexo. Se não for, é fácil ver podemos analisar a planaridade de cada componente separadamente.

1. Busca em profundidade

Inicialmente fazemos uma busca em profundidade (DFS) sobre G, gerando a árvore da DFS, cujas arestas são denominadas arestas da árvore. As arestas que ficaram de fora são as chamadas arestas de retorno. Note que como o grafo é não direcionado, as arestas de retorno sempre unem um vértice com seu ancestral na árvore da DFS.

2. Componentes biconexas

Antes de prosseguir, vamos relembrar dois conceitos: um ponto de articulação em um grafo conexo é um vértice cuja remoção origina duas ou mais componentes conexas. Uma componente biconexa é uma componente conexa que não tem pontos de articulação.

O algoritmo sempre trabalha com as componentes biconexas do grafo, replicando o ponto de articulação em cada uma delas. Note que em uma árvore, todo nó interno é um ponto de articulação e portanto inicialmente temos uma componente biconexa para cada aresta da árvore. Denotaremos esse grafo intermediário de \tilde G.

3. Adição das arestas de retorno

O restante do algoritmo consiste basicamente em adicionar as arestas de retorno uma a uma sempre garantindo que não haja cruzamento delas ou caso contrário conclui que o grafo não é planar. A ideia central é deixar “livres” os vértices que ainda têm arestas por adicionar.

Os vértices são então processados em ordem contrária a que foram processados na DFS. Assim, os filhos são sempre processados antes do pai na árvore da DFS. Consideremos então o processamento de um vértice v. Vamos adicionar as arestas de retorno de v a seus descendentes.

4. Aglutinação das componentes

Ao adicionar uma aresta de retorno, duas ou mais componentes biconexas podem ser aglutinadas. No exemplo da Figura 4, a inclusão da aresta de retorno (v, w) fará com que as duas componentes da Figura 4 (c) se tornem uma única componente, como pode ser observado na Figura 4 (d).

Figura 4: (a) Grafo real; (b) r é um ponto de articulação pois sua remoção gera duas componentes; (c) representamos as componentes biconexas; (d) ao adicionar a aresta de retorno (v, w) é preciso inverter a componente inferior para que a aresta (x, y) possa ser adicionada posteriomente.

5. Espelhamento das componentes

Outra operação necessária é a chamada espelhamento de uma componente biconexa. Voltando ao exemplo da Figura 4, temos que a aresta (x, y) será adicionada posteriormente (supondo que x é ancestral de v na árvore da DFS).

Porém, se adicionarmos a aresta (v, w) no grafo da Figura 4 (c), isolaremos x de y (note que não podemos “passar” a aresta entre r e sua cópia porque as componentes serão aglutinadas). Uma alternativa é “espelhar” a componente inferior como é feito na Figura 4 (d). Desta forma, os vértices x e y ainda podem ser conectados por uma aresta.

6. Ordem de adição das arestas de retorno

Como dissemos, o algoritmo itera sobre os vértices na ordem inversa da que foram processados pela DFS. Porém, um vértice v pode ter mais de uma aresta de retorno a adicionar a seus descendentes. Qual a ordem em que essas arestas devem ser adicionadas?

O algoritmo executa uma outra busca em profundidade a partir de v percorrendo apenas os vértices que estão na face externa e vai adicionando as arestas conforme vai encontrando os vértices com os quais v tem arestas de retorno a adicionar.

Se a busca terminar sem ter adicionado todas as arestas de retorno de v, então o grafo não é planar.

Conclusão

Esse algoritmo é bastante complicado e usa muitos truques para alcançar a complexidade linear no tamanho do grafo de entrada. Para quem tem mais interesse nos detalhes do algoritmo, pode consultar o artigo original [5]. Para detalhes de implementação, é possível estudar o código-fonte desse algoritmo da biblioteca de grafos da Boost [7].

No problema atacado durante meu mestrado, usamos uma ideia parecida com essa de trabalhar com componentes biconexas com o ponto de articulação replicado em cada uma delas. Mais especificamente, na tentativa de diminuir o tamanho das instâncias de entrada, fizemos a decomposição em componentes biconexas que podem ser resolvidas de maneira independente. Comentei sobre essa estratégia em um post anterior.

Referências

[1] Wikipédia – Kazimierz Kuratowski
[2] Wikipedia – Planarity Testing
[3] Kontaktprobleme der konformen Abbildung – Koebe P.
[4] Efficient Planarity Testing – Hopcroft J., Tarjan R.
[5] On the cutting edge: Simplified O(n) Planarity by Edge Addition – Boyer, Myrvold. (pdf)
[6] Dr Dobbs: Planarity By Edge Addition
[7] Boost: Boyer-Myrvold Planarity Testing


Seguir

Get every new post delivered to your Inbox.