sábado, 24 de maio de 2014

Erlang vs Prolog

Poliedro

Simon Thompson Joe Armstrong criou Erlang a partir de Prolog – aliás, o primeiro compilador era escrito em Prolog.

[update 2014-05-25]
Faglia nostra: o programador Prolog e criador da linguagem Erlang é Joe Armstrong. Simon Thompson é o mantenedor e um dos resposáveis pela reescrita em C.
[/update]
Apesar de ser uma linguagem funcional, Erlang traz muita herança de Prolog e suporta o paradigma declarativo. Para demonstrar essa similaridade, vou colocar o código de fatorial: em Erlang e em Prolog, implementação simples (e ruim) e usando tail-call optimization.

Código Q&D

Vamos ao rápido e sujo, primeiro em Prolog:

fact(0, 1) :- !.
fact(N, F) :- N > 0,
              N1 is N - 1,
              fact(N1, F1),
              F is N * F1.

Agora em Erlang:

fact(0) -> 1;
fact(N) when N > 1 -> N * fact(N - 1).

A intenção é mostrar como os códigos são parecidos.

Tail call optimization

Tanto Prolog quanto Erlang têm sistemas inteligentes de esvaziamento de pilha e usar um acumulador ajuda a tornar o programa mais eficiente.

O fatorial em Prolog fica assim:

fact(N, F) :- N >= 0,
              fact(N, 1, F).

fact(0, F, F) :- !.
fact(N, A, F) :- N1 is N - 1,
                 A1 is N * A,
                 fact(N1, A1, F).

Agora em Erlang:

fact(N) when N >= 0 -> fact(N, 1).

fact(0, A) -> A;
fact(N, A) -> fact(N-1, A*N).

Bônus

Tente adivinhar em qual linguagem é este código:

fact(N, F) :- N >= 0, fact(N, 1, F).
fact(0) --> { ! }, '='.
fact(N) --> { N1 is N - 1 }, mul(N), fact(N1).
mul(N, A, R) :- R is N * A.


[]’s
ℭacilhας, ℒa ℬatalema

segunda-feira, 19 de maio de 2014

PL Framework

Glider
Falei sobre como gerenciar dados mutáveis em Prolog. O código final ficou assim:


-*- Prolog -*-
:- module(profile, [profile/2]).
:- dynamic profile/2.

set(ID, X) :- profile(ID, X), !.
set(ID, X) :- X =.. [Attr, _],
              E =.. [Attr, _],
              retractall(profile(ID, E)),
              assertz(profile(ID, X)), !.

set(_, []) :- !.
set(ID, [X|Rest]) :- set(ID, X), set(ID, Rest).

get(ID, R) :- findall(X, profile(ID, X), R).

drop(ID) :- retractall(profile(ID, _)).

Mas e se quisermos que os dados sejam persistentes, ou seja, sobrevivam entre execuções, como um banco de dados?

O dialeto SWI Prolog oferece um arcabouço com inúmeros recursos chamado PL Framework.

Para persistência, há a biblioteca persistency.pl.

O que temos de fazer é substituir algumas partes de nosso código pelos predicados da biblioteca. Começaremos importando o módulo: logo após a declaração do nosso módulo, na linha abaixo, acrescente a importação:
:- use_module(library(persistency)).

Em seguida, não precisamos mais declarar o predicado profile/2 como dinâmico, em vez disso vamos declarar uma persistência. Substituia a linha com dynamic por:
:- persistent profile(id:atom, attr:compound).

Agora precisamos subtituir as chamadas de retractall/1 por retractall_profile/2, protegidas por with_mutex/2.

Onde está:
              retractall(profile(ID, E)),

Substitua por:
              with_mutex(profile,
                         retractall_profile(ID, E)),

E substitua:
drop(ID) :- retractall(profile(ID, _)).

Por:
drop(ID) :- with_mutex(profile,
                       retractall_profile(ID, _)).

Agora precisamos substituir assertz/1 por assert_profile/2. Onde está:
              assertz(profile(ID, X)), !.

Substitua por:
              with_mutex(profile, 
                         assert_profile(ID, X)), !.

Você pode juntar os predicados dentro de with_mutex/2.

Precisamos agora de uma regra para conectar a uma base de dados em disco, por exemplo:
connect(File) :- db_attach(File, [gc]).

Se quiser um arquivo padrão:
connect :- connect('profile.db').

Código final com persistência

-*- Prolog -*-
:- module(profile, [profile/2]).
:- persistent profile(id:atom, attr:compound).

set(ID, X) :- profile(ID, X), !.
set(ID, X) :- X =.. [Attr, _],
              E =.. [Attr, _],
              with_mutex(profile,
                         (retractall_profile(ID, E),
                          assert_profile(ID, X))), !.

set(_, []) :- !.
set(ID, [X|Rest]) :- set(ID, X), set(ID, Rest).

get(ID, R) :- findall(X, profile(ID, X), R).

drop(ID) :- with_mutex(profile,
                       retractall_profile(ID, _)).

connect :- connect('profile.db').

connect(File) :- db_attach(File, [gc]).

Este artigo foi apenas um exemplo prático de Prolog.

[]’s
ℭacilhας, ℒa ℬatalema

sábado, 17 de maio de 2014

Pequeno glossário de Prolog

Glider Ontem eu escrevi um artigo simples sobre Prolog.

O artigo na Wikipédia em português me pareceu pouco completo e bastante confuso. Tem informações legais lá, mas em comparação com a versão em inglês deixa a desejar.

Não pretendo completar o que está escrito na Wikipédia (senão deveria completar lá), apenas descomplicar um pouco.

Pra começar, é preciso entender a estrutura de um programa em Prolog: consiste em um domínio de verdades, parecido com uma base de dados, e o ponto de entrada é uma pergunta (query). Dito isso, vamos definir os conceitos dentro do código:
  • Termo: qualquer dado em Prolog é chamado termo.
  • Átomo: é um nome de propósito geral sem significado inerente. É representado por uma sequência de letras e alguns caracteres, começando por uma letra minúscula, ou qualquer sequência entre piclas ('…'). Por exemplo: hanoi
  • Número: pode ser inteiro ou de ponto flutuante, não diferente de outras linguagens.
  • Termo composto: consiste em um átomo, chamado functor (que é uma cabeça ou cabeçalho) seguido de uma sequência de termos e/ou incógnitas separados por vírgulas e entre parêntesis, chamada argumentos. Por exemplo: hanoi(5, R)
  • Predicado: é uma função booleana, ou seja, que retorna verdadeiro ou falso. Um predicado pode ser um átomo ou um termo composto e deve ser definido por um fato ou por uma regra.
  • Operador: é um predicado normal de aridade 2, mas que pode ser representado de forma diferente. Por exemplo, o sinal de igual:
X = 2

É o mesmo que:
'='(X, 2)

  • Variável: prefiro evitar a expressão “variável”, pois ela é falsa, apesar de ser o nome oficial. Prefiro “incógnita”: a incógnita pode estar ligada (bound) ou não (unbound) a um termo e tem comportamento diferente de acordo com estar ou não ligada. É representada por uma sequência de letras iniciando por uma letra maiúscula ou um underscore (_). Por exemplo: X
  • Fato: indica que determinado predicado retorna verdadeiro. É um átomo ou termo composto seguido de um ponto. Por exemplo:
default(5).

  • Regra: condiciona o resultado de um predicado ao resultado de outro. É um átomo ou termo seguido de :- e então o predicado ao qual ele está condicionado. Por exemplo:.
move(_, X, Y, _, R) :- move(1, X, Y, _, R).

  • Pergunta (query): É a chamada de um predicado. Pode retornar verdadeiro, falso ou gerar uma exceção. No código, é uma linha iniciada por :- e terminada por ponto. No prompt ?- basta digitar o predicado seguido de um ponto e pressionar a tecla Enter.

Um detalhe importante é que coisas que não parecem predicados, também são! Por exemplo:
  • Vírgula: é operador (','/2) que avalia o primeiro um predicado (argumento) e só avalia o segundo se o primeiro for verdadeiro, ou seja, E lógico.
N1 is N - 1, fact(N1, F1)

  • Ponto e vírgula: operador (';'/2) que avalia o primeiro predicado e só avalia o segundo se o primeiro for falso, ou seja, OU lógico.
  • Exclamação: é um predicado de aridade 0 ('!'/0) que indica que, se a regra atual “casar” (match) com a pergunta, os próximos fatos ou regras não serão avaliados.
  • Qualquer operação matemática.

Como exemplo, segue uma implementação da resolução da torre de Hanói:
% -*- Prolog -*-
:- module(hanoi, [hanoi/0, hanoi/1, hanoi/2]).

hanoi :- hanoi(R), findall(_, show(R), _).
hanoi(R) :- default(N), hanoi(N, R).
hanoi(N, R) :- N > 0,
               findall(X,
                       move(N,
                            'a esquerda',
                            'a direita',
                            'o centro', X),
                       R).

default(5).

move(1, X, Y, _, move(X, Y)) :- !.
move(N, X, Y, Z, R) :- N1 is N - 1, move(N1, X, Z, Y, R).
move(_, X, Y, _, R) :- move(1, X, Y, _, R).
move(N, X, Y, Z, R) :- N1 is N - 1, move(N1, Z, Y, X, R).

show(move(X, Y)) :- format('mova o disco d~w para ~w~n', [X, Y]).
show([X|_]) :- show(X).
show([_|Rest]) :- show(Rest).

Consegue entender como funciona?

Para gerar um executável com SWI Prolog:
bash$ prolog -f hanoi.pl \
-g 'use_module(library(save)), qsave_program(hanoi, [goal(hanoi)])' \
-t halt

Bônus

Há um açúcar sintático em prolog, que é -->:
a --> b, c(x), d.

Significa o mesmo que:
a(Start, End) :- b(Start, V1), c(x, V1, V2), d(V2, End).

[]’s
ℭacilhας, ℒa ℬatalema

Dados em Prolog

Glider Há uns anos falei um pouquinho sobre Prolog: sobre predicados, átomos, termos compostos, fatos, regras, incógnitas, etc.

Só pra relembrar: um programa em Prolog é um conjunto de predicados – fatos e regras – e sua execução consistem em perguntas (queries) feitas a esse domínio de verdades. Na programação declarativa, a ideia não é dizer como o computador deve resolver o problema, mas sim descrever o problema.

O entendimento de Prolog é essencial ao entendimento da programação declarativa e, assim, para poder extrair o máximo do poder de linguagens mais modernas, como Erlang.

É uma história bonita, mas um exemplo um pouco mais prático iria bem, não?

Então imaginei um exemplo: um módulo que representa perfis de dados – por exemplo, dados de perfil de usuário.

Podemos começar o código dizendo para o sistema nosso módulo:
% -*- Prolog -*-
:- module(profile, [profile/2]).

A primeira linha é um comentário que avisa a alguns editores que o arquivo se trata de um código Prolog, a segunda declara o módulo profile, que exporta o predicado profile/2 (com aridade 2).

A seguir, podemos declarar nosso predicado profile/2:
:- dynamic profile/2.

Essa declaração diz que o predicado profile/2 é dinâmico, ou seja, muda ao longo da execução do programa.

Agora precisamos de um predicado para gravar novos dados de perfil. Façamos isso com uma regra:
set(ID, X) :- profile(ID, X), !.

Essa regra diz ao sistema que, se alguém questionar set(ID, X) – onde ID é o identificador do perfil e X é um atributo do perfil – e essa combinação for verdadeira, ele não deve assumir isso como ver dade e não avaliar demais regras ou fato (!).

A próxima regra é um pouco longa, então vou falar dela linha a linha:
set(ID, X) :- X =.. [Attr, _],

Aqui diz que o predicado é set(ID, X) (exatamente igual ao anterior), e X é um termo composto de aridade 1, cujo cabeçalho será atrelado à incógnita Attr.

Caso verdade, continua a próxima linha da regra:
              E =.. [Attr, _],

Então E é termo composto com mesmo cabeçalho e aridade de X, porém com parâmetro _, que significa qualquer coisa.

Então, se X for name(john), E será name(_).
              retractall(profile(ID, E)),

Remove o predicado com o dado de perfil com o mesmo identificador e o mesmo cabeçalho informados.
              assertz(profile(ID, X)).

Cria o predicado armazenando o atributo de perfil informada – e assim termina nossa regra.

E se quisermos criar uma lista de atributos para o mesmo identificador de perfil?

Podemos criar um predicado para isso. Comecemos pelo ponto de parar, que é quando nossa lista de atributos já foi esgotada:
set(_, []) :- !.

Essa regra diz que, se a lista de atributos está vazia, não precisa fazer mais nada. Mas e se contiver algum elemento? Precisaremos questionar o set/2 para aquele atributo e continuar chamando para o resto da lista:
set(ID, [X|Rest]) :- set(ID, X), set(ID, Rest).

Resolvido.

Podemos criar um predicado para retornar todos os atributos de uma identidade:
get(ID, R) :- findall(X, profile(ID, X), R).

Precisamos agora de um predicado de limpeza, um para remover todos os atributos de um identificador (o que significa apagar o identificador):
drop(ID) :- retractall(profile(ID, _)).

Vamos testar agora nosso módulo:
?- [profile].
true.

?- profile:set(1, [name(john), age(20), city(rio)]).
true.

?- profile:set(2, [name(jack), age(21), city(sao_paulo)]).
true.

?- profile(ID, city(City)).
ID = 1
City = rio ;
ID = 2
City = sao_paulo.

?- profile:get(1, R).
R = [name(john), age(20), city(rio)].

?- profile:drop(1).
true.

?- profile(ID, _).
2 ;
2 ;
2.

?- drop(_).
true

?- profile(ID, _)
false.

?- 

Espero que o exemplo tenha sido esclarecedor. Para fazer um tracing, você pode fazer a pergunta gtrace.

Observação: para a execução, foi usando SWI Prolog, uma das mais confiáveis e robustas implementações de Prolog da atualidade.

Complemento a este artigo: Pequeno glossário de Prolog.

[]’s
ℭacilhας, ℒa ℬatalema