Árvores de derivação no Prolog, seleções e unificação
Para ilustrar como o Prolog produz respostas para programas e objetivos, considere o seguinte programa de registro de dados simples (sem funções).
/* program P clause # */
p(a). /* #1 */
p(X) :- q(X), r(X). /* #2 */
p(X) :- u(X). /* #3 */
q(X) :- s(X). /* #4 */
r(a). /* #5 */
r(b). /* #6 */
s(a). /* #7 */
s(b). /* #8 */
s(c). /* #9 */
u(d). /* #10 */Exercício 3.1.1 Carregue o programa P no Prolog e observe o que acontece para o objetivo ?-P(X).. Quando uma resposta for relatada, pressione (ou digite) ';' para que Prolog continue a rastrear e encontrar todas as respostas.
Exercício 3.1.2 Carregue o programa P no Prolog, ligue o trace e veja o que acontece para o objetivo ?-P(X).. Quando uma resposta for relatada, pressione (ou digite) ';' para que Prolog continue a rastrear e encontrar todas as respostas. (Use ?-help(trace). primeiro, se necessário.)
O diagrama a seguir mostra uma árvore de derivação Prolog completa para o objetivo ?-P(X).. As arestas na árvore de derivação são rotuladas com o número da cláusula no arquivo de origem para o programa P que foi usado para substituir um objetivo por um sub-objetivo. Os descendentes diretos sob qualquer objetivo na árvore de derivação correspondem às escolhas. Por exemplo, o objetivo principal p(X) unifica-se com os principais objetivos das cláusulas #1, #2, #3, ou seja, são três escolhas.
O trace (Exercício 3.1.2 acima) do objetivo ?-P(X). corresponde a uma busca em profundidade desta árvore de derivação. Cada nó na árvore de derivação do Prolog era, no ponto apropriado da pesquisa, o objetivo atual. Cada nó na árvore de derivação é uma sequência de sub-objetivos. As arestas diretamente abaixo de um nó nesta árvore de derivação correspondem às opções disponíveis para substituir um sub-objetivo selecionado. A cláusula lateral atual, cujo número rotula o arco na árvore de derivação, é tentada da seguinte maneira:
Se o subobjetivo atual mais à esquerda (mostrado como g1 no pequeno diagrama abaixo) unifica-se com o cabeçalho da cláusula lateral (mostrado como h em o diagrama), então esse sub-objetivo atual mais à esquerda é substituído pelo corpo da cláusula lateral (mostrado como b1, b2, ..., bn no diagrama). De forma pictórica, poderíamos mostrar isso da seguinte forma:
Uma coisa importante não mostrada explicitamente no diagrama é que as variáveis lógicas no objetivo resultante b1, b2, ..., bn, g2, g3, ... foram vinculadas como resultado da unificação, e o Prolog precisa se manter acompanhando essas substituições unificadoras à medida que a árvore de derivação cresce em qualquer galho.
Agora, uma primeira busca em profundidade de tal árvore de derivação significa que escolhas alternativas serão tentadas assim que a busca retornar de volta à árvore até o ponto onde a escolha alternativa está disponível. Esse processo é chamado de backtracking.
Obviamente, se o final da regra estiver vazio, o sub-objetivo mais à esquerda será efetivamente apagado. Se todos os objetivos secundários puderem ser apagados em um caminho na árvore de derivação, então uma resposta foi encontrada (ou uma resposta 'sim' calculada). Neste ponto, as ligações para as variáveis podem ser usadas para dar uma resposta à consulta original.
Unificação dos Termos do Prolog
A unificação de Prolog combina dois termos Prolog T1 e T2 encontrando uma substituição de variáveis mapeando M tal que se M é aplicado a T1 e M é aplicado a T2 então os resultados são iguais.
Por exemplo, Prolog usa a unificação para satisfazer as equações (T1 = T2) ...
?- p(X,f(Y),a) = p(a,f(a),Y).
X = a Y = a
?- p(X,f(Y),a) = p(a,f(b),Y).
NoNo primeiro caso, a substituição bem-sucedida é {X/a, Y/b} e, para o segundo exemplo, não há substituição que resultaria em termos iguais. Em alguns casos, a unificação não vincula variáveis a termos básicos, mas resulta em variáveis que compartilham referências ...
?- p(X,f(Y),a) = p(Z,f(b),a).
X = _G182 Y = b Z = _G182Nesse caso, a substituição unificadora é {X/_G182, Y/b, Z/_G182} e a referência de compartilhamento é X e Z, como pode ser ilustrado pelo próximo objetivo ...
?- p(X,f(Y),a) = p(Z,f(b),a), X is d.
X = d Y = b Z = d{X/_G182, Y/b, Z/_G182} foi a substituição unificadora mais geral para o objetivo anterior, e a instância {X/d, Y/b, Z/d} é especializada para satisfazer o último objetivo.
O Prolog não realiza uma verificação de ocorrência ao vincular uma variável a outro termo, caso o outro termo também possa conter a variável. Por exemplo (SWI-Prolog) ...
?- X=f(X).
X = f(**)A referência circular é sinalizada por (**) neste exemplo, mas o objetivo é bem-sucedido {X/f(f(f(...)))}. Contudo ...
?- X=f(X), X=a.
NoA referência circular é verificada pela vinculação, portanto, o objetivo falha. "a NÃO pode ser unificado com f(_Qualquer coisa)" ...
?- a \=f(_).
YesAlguns Prologs têm uma versão de unificação de verificação de ocorrência disponível para uso. Por exemplo, em SWI-Prolog ...
?- unify_with_occurs_check(X,f(X)).
NoO algoritmo de satisfação de objetivo do Prolog, que tenta unificar o objetivo atual com o cabeçalho de uma cláusula do programa, usa uma forma de instância da cláusula que não compartilha nenhuma das variáveis no objetivo. Portanto, a verificação de ocorrência não é necessária para isso. A única possibilidade de ocorrer um erro de verificação surgirá do processamento de termos do Prolog (em programas do usuário) que possuem referência circular não intencional de variáveis que o programador acredita que devem levar o objetivos falhos, quando ocorrem. Alguns Prologs podem ter sucesso nessas ligações circulares, alguns podem falhar, outros podem realmente continuar a registrar as ligações em um loop infinito e, assim, gerar um erro de tempo de execução (out of memory). Essas situações são raras e precisam de cuidados durante a programação.
É possível imitar o algoritmo geral de unificação no Prolog. Mas aqui apresentamos uma versão especializada de unificação, cuja complexidade computacional é linear no tamanho dos termos de entrada e simplesmente combina os termos da esquerda para a direita. O predicado match(+GeneralTerm, +GroundedTerm) tenta combinar seu primeiro argumento (que pode conter variáveis) com seu segundo argumento (que deve ser fundamentado). Este pequeno programa deve ser considerado apenas como uma ilustração ou um exercício de programação, embora conheçamos aplicações convincentes para o algoritmo de correspondência LR em situações onde a unificação geral não é necessária. Não usaríamos correspondência, no entanto, em um aplicativo Prolog porque a unificação embutida seria muito mais rápida; nós simplesmente teríamos que garantir que as pressuposições para correspondência sejam verificadas apropriadamente quando a unificação embutida for usada. A referência Apt e Etalle (1993)[1] discute a questão em geral a respeito de quanto da unificação geral NÃO é realmente necessária para Prolog.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% match(U,V) :
%% U may contain variables
%% V must be ground
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% match a variable with a ground term
match(U,V) :-
var(U),
ground(V),
U = V. % U assigned value V
% match grounded terms
match(U,V) :-
ground(U),
ground(V),
U == V.
% match compound terms
match(U,V) :-
\+var(U),
ground(V),
functor(U,Functor,Arity),
functor(V,Functor,Arity),
matchargs(U,V,1,Arity).
% match arguments, left-to-right
matchargs(_,_,N,Arity) :-
N > Arity.
matchargs(U,V,N,Arity) :-
N =< Arity,
arg(N,U,ArgU),
arg(N,V,ArgV),
match(ArgU,ArgV),
N1 is N+1,
matchargs(U,V,N1,Arity).Veja Também
Referências
- ↑ Apt, K., and Etalle, S., On the Unification Free Prolog Programs, Computer Science/Department of Software Technology, Report CS-R9331, May 1993.