Estratégia standard

Fixamos a primeira componente de uma estratégia, isto é, as escolhas do tipo f, adoptando a escolha standard: consideramos sempre a árvore de procura standard. A segunda componente de uma estratégia, isto é, o método de tentar todas as escolhas do tipo c, pode agora ser descrito como um percurso da árvore de procura. Designamos por percurso standard, o percurso ``em profundidade primeiro e da esquerda para a direita'' da árvore de procura. Chamamos estratégia standard à estratégia definida pela árvore de procura standard e pelo percurso standard. Na prática procede-se a um ``percurso-construção'' da árvore de procura. É um meio de compreender o cálculo efectuado por um interpretador de um programa em lógica (interpretador Prolog) quando submetemos uma questão: ele efectua o percurso-construção da árvore de procura oriunda da questão e a cada construção de uma folha sucesso, ele faz sair como resultado a resposta calculada dessa folha. Na prática, o resultado é a restrição da resposta calculada às variáveis que figuram na questão. Se não houver nenhuma variável na questão, o resultado consiste apenas na indicação de sucesso. É, em particular, um meio de compreender:

a)

A ordem pela qual são produzidas as respostas (ordem induzida pela ordem do percurso-construção).

b)

A razão da presença eventual de variáveis nas respostas produzidas por um interpretador Prolog.

c)

A razão de um ``bloqueamento'' eventual, assim como a ausência de certas respostas (ver comentário à frente).

O Prolog pode ser visto como um interpretador que segue a estratégia standard. No entanto, além da parte ``puramente lógica'', o Prolog tem partes ``impuras'' ou ``não lógicas'', que veremos mais à frente. Embora estes elementos ``não lógicos'' não tenham uma interpretação na lógica clássica, podemos, mesmo assim, descrevê-los em termos da árvore de procura. Certas primitivas da linguagem, que não têm senão um significado operacional, podem ser descritas em termos da modificação dinâmica da árvore de procura no decorrer do percurso-construção. É importante observar que pode acontecer o percurso-construção apenas construir efectivamente uma parte da árvore de procura. Em particular com a estratégia standard o percurso-construção pode perder-se num ramo infinito e portanto jamais percorrer certos ramos ulteriores que ficarão por construir. É então possível, se a árvore de procura tiver ramos infinitos, que certas respostas não sejam jamais calculadas, porque as folhas sucesso correspondentes não serão jamais atingidas (veja-se o exemplo que se segue). Por esta razão, dizemos que a estratégia standard é incompleta. A escolha da estratégia standard (incompleta) por parte do Prolog, justifica-
-se por razões de ordem prática, pelos problemas de gestão de memória. Vamos agora mostrar, com um exemplo, a influência da ordem das cláusulas num programa. Para isso basta relembrar o programa que fizemos com o predicado member/2 e árvore de procura que construímos. Com a estratégia standard, obtemos uma infinidade de respostas, pela ordem:

         L = [a|R1];
         L = [E1,a|R2];
         ...

Se agora invertermos a ordem das duas cláusulas

         member(X,[Y|R]) :- member(X,R).
         member(X,[X|R]).

resulta claro que obtemos uma nova árvore de procura que é exactamente a simétrica da anterior. Em particular, agora o ramo infinito é o ramo mais à esquerda. Com a estratégia standard, a procura vai prosseguir indefinidamente sem nunca obtermos uma resposta.