Visão procedimental da programação em lógica

O cálculo efectuado por um interpretador de Prolog pode ser descrito em termos de avanços e retrocessos (``back-tracking'') que são o reflexo do percurso standard. O percurso standard da árvore de procura (standard) é uma sucessão de avanços (= descidas) e de retrocessos (= subidas) de um nó a outro, partindo da raíz. Um avanço deixa eventualmente a escolha de cláusulas em espera. Um retrocesso é provocado pela passagem a uma folha da árvore de procura (falha ou sucesso) e regressa ao último nó onde deixámos escolhas em espera, de maneira a tentar a primeira escolha que resta. Cada avanço está associado a uma transformação (alvo e instanciação) e cada retrocesso está associado à anulação dessa transformação. A visão procedimental da programação em lógica, consiste em ver o átomo A como uma chamada de procedimento, cujo efeito é construir uma árvore de prova a partir de A. Um alvo B é então visto como uma sucessão de chamadas de procedimentos. Seja

         A0 :- A1, ..., Am.

a cláusula que faz passar do nó corrente ao seu filho no ramo da árvore de procura, isto é, a cláusula que permite juntar os filhos à folha A da árvore de prova parcial corrente. Então o que vemos como a chamada do procedimento A é primeiro a unificação de A com A0, que produz um unificador minimal s, seguido da sucessão de chamadas dos procedimentos s(A1), ..., s(Am). Isto permite ver a unificação como um modo de transmissão de parâmetros e a cláusula A0 :- A1, ..., Am. como uma definição de procedimento. Os parâmetros são os argumentos dos átomos. Um procedimento pode possuir várias definições, que são as cláusulas no programa. Por exemplo no ``nosso primeiro programa em Prolog'', as cláusulas progenitor contêm duas definições do ``procedimento progenitor''. Falamos de ``procedimentos não determinísticos''. Um procedimento pode ter uma definição recursiva como

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

Segundo esta visão procedimental, um programa em lógica é o análogo (não determinístico) de uma sucessão de definições de procedimentos; uma questão (= um alvo, = uma sucessão de chamadas de procedimentos) é o análogo ao programa principal clássico. Nesta analogia, a palavra variável pode ser enganosa. A variável ``em lógica'' não conhece a afectação no sentido clássico (algorítmico): ela sofre instanciações. Intuitivamente, o objecto que ela representa é precisado pelas instanciações sucessivas que ela sofre, mas esse objecto não muda bruscamente de valor como numa atribuição clássica do tipo X := X + 1. Podemos entretanto prosseguir a analogia no que concerne ao domínio de validade das variáveis de um procedimento. Cada variável é local a uma chamada de procedimento. Não existem variáveis globais. Do ponto de vista da implementação de um interpretador de Prolog, este facto corresponde à necessidade de renomear as cláusulas, embora isso não seja mais do que um reflexo do facto de que em cada cláusula as variáveis são quantificadas universalmente. Para acabar a analogia com uma linguagem baseada na noção de procedimento, podemos dizer que a função de teste é assegurada pela unificação. Por exemplo

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

é o análogo da estrutura
Se o primeiro argumento = cabeça da lista Então
        primeiro argumento pertence à lista
Senão
        ... Mesmo para descrever o cálculo determinístico seguindo a estratégia standard, é por vezes cómodo utilizar esta terminologia procedimental. Dizemos que a chamada do procedimento A tem êxito se uma das tentativas de construção de uma árvore de prova a partir de A teve êxito. Dizemos que essa chamada fracassou em tempo finito se todas as tentativas fracassaram sem nenhuma ``se perder'' num ramo infinito.


(c) Delfim F. Marado Torres
1999-04-13