LogicParser 0.7

Novo release do LogicParser, estou ficando quase satisfeito, mais alguns refinamentos e pode virar 1.0.

LogicParser 0.7LogicParser 0.7 Hosted on Zooomr

O problema da vez foi o “Ajustar para caber”, pois precisava mudar o zoom pra ficar de acordo com tamanho do Viewport, e este não tem um método óbvio do tipo “get_width”. A solução foi:

vp_width = GTK_WIDGET(lpApp->viewport)->allocation.width - 4;
vp_height = GTK_WIDGET(lpApp->viewport)->allocation.height - 4;

ou seja, todo GtkWidget tem uma propriedade “allocation” que por sua vez tem as propriedades “width” e “height”. (O -4 foi só pra compensar algum espaçamento.)

Além disso essa versão precisa desesperadamente ter seus memory leaks corrigidos, alguns zooms e logo terá 100Mb de memória ocupados. Estou protelando o uso do Valgrind.

Download: logicparser-0.7.tar.gz

LogicParser 0.6

Depois de curto tempo (umas 17 horas), mais um release do LogicParser. Agora é possível atribuir valores às proposições e o resultado da expressão completa é avaliado.

LogicParser 0.6

Para mudar o valor da proposição, basta colocar o cursor sobre o valor na lista da esquerda e segurar o botão esquerdo, então um combobox aparecerá com as opções de valores (True ou False).

Download: logicparser-0.6.tar.gz

Lógica de Predicados com Python

Ultimamente tenho me divertido revendo algumas coisas de lógica e no momento estou em predicados e quantificadores. Resolvi testar esses conceitos (de forma bem simples) usando Python, assim vou compartilhar minha idéia de diversão com o mundo.

Considere a frase “Marcelo dorme 4 horas por noite”, “Marcelo” é o sujeito e “dorme 4 horas por noite” é o predicado, a lógica de predicados expressa o predicado da afirmação como uma função proposicional onde uma variável representa o sujeito. Estabelecemos que P(x) significa “x dorme 4 horas por noite”, e podemos substituir x por qualquer sujeito, bem não qualquer sujeito e sim algum que esteja no universo de discurso, que nesse caso poderia ser “todos os alunos de computação”. A função P(x) pode ser verdadeira ou falsa, dependendo da qualidade de vida do aluno de computação que substituir x na função.

A outra parte são os quantificadores, que são o universal e o existencial. Usando a função P(x) e o universo de discurso declarados acima, com o quantificador universal posso afirmar que todos os alunos de computação dormem 4 horas por noite”, ou usar o existencial e afirmar que existe pelo menos um aluno de computação que dorme 4 horas por noite”. Para ser verdadeira a proposição quantificada universalmente precisa ser verdade para todos os casos do universo de discurso, já para a proposição quantificada existencialmente, basta que exista um caso verdadeiro para tornar verdadeira a proposição. Pelo menos essa semana posso afirmar que a segunda proposição é verdadeira, infelizmente. :-\

Agora vamos à programação. Em termos algorítmicos a verificação das proposições quantificadas é feita com um loop sobre os elementos do universo de discurso, se a proposição testada for quantificada universalmente o loop pára quando encontrar um resultado falso, que invalida a proposição, se for quantificada existencialmente, ele pára ao encontrar um resultado verdadeiro, que valida a proposição.

Vou usar um exemplo matemático pra facilitar. Considere a função P(x) significando

px

Em Python fica assim:

def P(x):
... return x**2 - 4*x <= 0

Vamos considerar o universo de discurso

xez4×5.png

Agora afirmo que

ax

que é lida como “para qualquer valor de x (dentro do universo de discurso) P(x) é verdadeira”. Ora, P(x) é falsa para x=-1, o que torna falsa a proposição de que P(x) é verdadeira para qualquer valor de x. Expresso logicamente para o universo de discurso declarado acima fica:

ands.png

A avaliação de “para todo” em Python:

def avaliaParaTodo(univ):
... res = True
... for x in univ:
...... res = res and P(x)
...... if not res:
......... return False
... return res

Daí testamos para o universo de discurso (usando range)

>>> avaliaParaTodo(range(-4,5))
False

Vejamos agora o existencial

ex

que é lida como “existe ao menos um valor de x para o qual P(x) é verdadeira”. Com apenas um caso verdadeiro, como x=2, provamos a veracidade da expressão. Também pode ser expresso como:

ors.png

Em Python:

def avaliaExiste(univ):
... res = False
... for x in univ:
...... res = res or P(x)
...... if res:
......... return True
... return res

Avaliando:

>>> avaliaExiste(range(-4,5))
True

Vamos mudar o universo de discurso um pouco, passando a usar o números naturais em lugar dos inteiros:

xen1.png

Agora o teste de ambos os casos, universal e existencial, resulta em verdade:

>>> avaliaParaTodo(range(0,5))
True

>>> avaliaExiste(range(0,5))
True

A coisa pode ficar mais elaborada com funções proposicionais com mais de um argumento, permitindo quantificações como “para todo x existe um y”, que algorítmicamente seria expressa com dois loops aninhados.

Depois disso tudo você pode querer mandar para sua namorada uma representação em lógica de predicados de “x ama y” ou algo assim. As mulheres adoram.

Referências:

Ah, e as fórmulas foram produzidas no OpenOffice.org Math

Compilando LogicParser em Win32 com MinGW e MSYS

Minha primeira e emocionante compilação de algo que estava desenvolvendo no Linux no insalubre ambiente Win32. Primeiro o screenshot e depois a história:

LogicParser no Windows

O ambiente de build foi montado usando MinGW/MSYS/msysDTK e o GTK+/Win32 Development Environment. A primeira compilação deu errado, mas setei a variável de ambiente PKG_CONFIG_PATH para /c/temp/GTK/2.0/lib/pkgconfig e tudo correu muito bem, mais fácil do que esperava. Depois vou ver como compilar estático pra fazer um executável morbidamente obeso, mas muito conveniente.

A aba “Graph (Image)” não funciona pois não consegui instalar o GraphViz no computador do CIn pois não tenho privilégios de administrador. Pelo menos isso me ajudou a decidir usar o GraphViz via biblioteca em lugar de usar o g_spawn_sync da GLib para chamá-lo externamente. Além disso, pra esse negócio ficar mesmo cross-platform tenho de usar algumas funções utilitárias da GLib, como g_get_tmp_dir e coisas assim.

Referências úteis nessa empreitada:

LogicParser 0.4

Mais um release do LogicParser, agora a aba “Graph (Image)” é atualizada com imagem representando a árvore parseada da expressão lógica.

LogicParser 0.4

Duas funções muito boas da GLib me ajudaram:

  • g_file_set_contents: escreve todo conteúdo de uma string para um arquivo. Simples e rápida.
  • g_spawn_sync: dispara um processo de forma síncrona, para chamar o dot, do GraphViz.

Juntanto com outras facilidades da GLib, programar em C fica fácil demais. :P

Outra coisa muito útil era o Google Code Search, a referência da GLib é muito boa, mas às vezes você quer ver o código sendo usado, e o code search ajudou bastante. Por exemplo, a especificação do g_spawn_sync tem muitos parâmetros, assustadores numa primeira olhada. “Como devo setar esses parâmetros?” Como todo mundo! No código do eog que achei nessa busca: lang:c g_spawn_sync

Sobre o futuro, o código precisa de mais “polish” e certamente preciso aprender CMake ou Autotools pra fazer um build system de respeito e não meu seboso Makefile. Por ser um projeto pequeno, pode valer à pena aprender Autotools.

Lembrando:

Update: OMG! Agora o Google Hosting disponibiliza uma wiki! Vejam a minha: http://code.google.com/p/logicparser/wiki/LogicParser

LogicParser 0.2

Segundo release do LogicParser. Está sendo bem divertido voltar a programar em C, ainda mais com a GLib facilitando as coisas. No começo é estranho usar g_print no lugar de printf, e outras coisas, mas quando penso que boa parte da portabilidade estará garantida quando for compilar esse treco em Win32… :)

Neste release adicionei um componente para gerar grafos no no formato da linguagem DOT, processados pela ferramenta homônima do pacote GraphViz.

Aqui está uma expressão na sintaxe compreendida pelo LogicParser:

p1->(f | (!p3))

O grafo gerado:

digraph ParsedTree {
if_then_0 [label=if_then];
if_then_0 -> P1_1;
if_then_0 -> or_2;
P1_1 [label=P1];
or_2 [label=or];
or_2 -> False_3;
or_2 -> not_4;
False_3 [label=False];
not_4 [label=not];
not_4 -> P3_5;
P3_5 [label=P3];
}

A linha de invocação do dot, e a figura gerada:
dot -Tpng grafo.dot -o grafo.png

p1->(f | (!p3))

Além disso tudo está documentado na sintaxe do Doxygen.

Update: ah! O comando mágico para criar um tag no subversion:
svn copy https://logicparser.googlecode.com/svn/trunk \
https://logicparser.googlecode.com/svn/tags/release-0.2 \
-m "Release 0.2 of the 'LogicParser' project."