Interpretação Procedimental
Vimos que um programa é um conjunto de cláusulas que define
um conjunto de relações (representa conhecimento sobre um
domínio).
No entanto, um programa reflecte também uma determinada
estratégia de resposta às interrogações que lhe são postas. Daí
a importância da ordem das cláusulas e dos predicados no
corpo das cláusulas como instrumento de controlo da
execução.
Pretende-se complementar o valor declarativo com
conhecimento da estratégia de execução para poder guiar a
programação pela intuição correcta.
Universidade da Madeira
Departamento de Matemática
Elsa Carvalho
241
Programação em Lógica e Funcional (2000/01)
(Actualizado em 2004/05)
Interpretação Procedimental
Um objectivo é uma estrutura de chamadas a procedimentos
q1, ..., qn (escalonadas segundo a regra de computação).
Um procedimento para um símbolo de predicado é o conjunto das
cláusulas do programa cujas cabeças são construídos com esse
símbolo.
Uma cláusula é o método de responder à chamada a um
procedimento pq1, ..., qn, onde p é a cabeça e q1, ..., qn é o corpo
da cláusula:
para resolver o problema p resolvam-se os sub problemas q1, ..., qn ou,
para responder a uma chamada a p, chamem-se os procedimentos q1,..., qn
A cláusula pq1, ..., qn responde a uma chamada a gi se gi e p são
unificáveis.
Universidade da Madeira
Departamento de Matemática
Elsa Carvalho
242
Programação em Lógica e Funcional (2000/01)
(Actualizado em 2004/05)
Interpretação Procedimental
Chamada a resolver p, a cláusula tenta resolver q1, ..., qn,
activando sequencialmente cada uma das chamadas.
A activação de uma chamada começa por seleccionar uma das
cláusulas do procedimento invocado, que responde à chamada
(seguindo a regra de pesquisa).
Se a chamada não for bem sucedida, então é seleccionada outra
das cláusulas que responde à chamada.
Se não houver mais cláusulas, o controlo volta à chamada
precedente.
Se não houver chamada precedente, gera-se insucesso (o
objectivo não foi atingido).
Universidade da Madeira
Departamento de Matemática
Elsa Carvalho
243
Programação em Lógica e Funcional (2000/01)
(Actualizado em 2004/05)
Interpretação Procedimental
Passagem de parâmetros
Ao unificar a chamada e a cabeça de uma cláusula, o u.m.g.
atribui termos às variáveis da cabeça da cláusula (valores
passados), que são distribuídos pelo corpo da cláusula.
O u.m.g. atribui igualmente termos às variáveis da chamada
(resultados da execução do corpo da cláusula), que são
igualmente distribuídos pelo resto do objectivo.
Assim a unificação representa a passagem de parâmetros e a
construção das respostas.
Universidade da Madeira
Departamento de Matemática
Elsa Carvalho
244
Programação em Lógica e Funcional (2000/01)
(Actualizado em 2004/05)
Corte
O corte é um instrumento de controlo da execução (sem
significado lógico), denotado por !.
Permite podar a árvore eliminando ramos que não queremos ver
construídos.
Para definir o corte é cómodo usar a terminologia procedimental.
O corte é um procedimento pré-definido, quer dizer, apenas
poderá aparecer no corpo de uma cláusula, ou num objectivo.
A chamada ao procedimento ! tem imediatamente êxito, como se
o corte fosse definido pela cláusula única (facto)
!.
Universidade da Madeira
Departamento de Matemática
Elsa Carvalho
245
Programação em Lógica e Funcional (2000/01)
(Actualizado em 2004/05)
Corte
Mas o que é essencial é o “efeito lateral” que acompanha o êxito
dessa chamada e que modifica a árvore de pesquisa actual
(modifica o percurso-construção).
Considere o programa
aceita(L)  membro(1, L), criterio_1(L)
aceita(L)  ...
...
membro(X, [X|L]) 
membro(X, [Y|L])  membro(X, L)
Que acontece com o objectivo
 aceita([1,2,1])
quando a lista [1,2,1] não satisfaz o critério_1?
Universidade da Madeira
Departamento de Matemática
Elsa Carvalho
246
Programação em Lógica e Funcional (2000/01)
(Actualizado em 2004/05)
Corte - Exemplo
 aceita([1,2,1])
 membro(1, [1,2,1]), criterio_1([1,2,1])
 criterio_1([1,2,1])
 membro(1, [2,1]), criterio_1([1,2,1])
 membro(1, [1]), criterio_1([1,2,1])
 criterio_1([1,2,1])
Universidade da Madeira
Departamento de Matemática
Elsa Carvalho
 membro(1, []), criterio_1([1,2,1])
247
Programação em Lógica e Funcional (2000/01)
(Actualizado em 2004/05)
Corte
A segunda chamada a criterio_1 é redundante!
Para eliminar esta redundância poderíamos:
reforçar a compontente lógica de forma a que haja apenas
um ramo bem sucedido.
membro(X, [X|L]) 
membro(X, [Y|L])  X\==Y, membro(X, L)
Nota: o predicado infixo \== significa não equivalente.
Universidade da Madeira
Departamento de Matemática
Elsa Carvalho
248
Programação em Lógica e Funcional (2000/01)
(Actualizado em 2004/05)
Corte
reforçar a componente de controlo, fazendo com que os
ramos indesejados não sejam construídos (corte).
membro(X, [X|L])  !
membro(X, [Y|L])  membro(X, L)
O efeito sobre a árvore para o predicado membro seria o de
eliminar a exploração da zona sombreada.
Universidade da Madeira
Departamento de Matemática
Elsa Carvalho
249
Programação em Lógica e Funcional (2000/01)
(Actualizado em 2004/05)
Corte
 membro(1, [1,2,1])
!
 membro(1, [2,1])
 membro(1, [1])
!
Universidade da Madeira
Departamento de Matemática
Elsa Carvalho
250
 membro(1, [])
Programação em Lógica e Funcional (2000/01)
(Actualizado em 2004/05)
Corte
Funcionamento do corte:
Consideremos a invocação da
cláusula r  p1, ..., pm, !, q1, ..., qn.
Quando a execução do corpo
chega ao corte, a chamada é bem
sucedida e eliminam-se
as alternativas a r ainda não
exploradas e
as alternativas a qualquer das
chamadas pi ainda não
exploradas
Universidade da Madeira
Departamento de Matemática
Elsa Carvalho
251
 r, ...
p1
p1
pm
pm
 !, q1, ..., qn
Programação em Lógica e Funcional (2000/01)
(Actualizado em 2004/05)
Corte - Exemplo
 aceita([1,2,1])
 membro(1, [1,2,1]), criterio_1([1,2,1])
 !, criterio_1([1,2,1])
 membro(1, [2,1]), criterio_1([1,2,1])
 membro(2, [1]), criterio_1([1,2,1])
 criterio_1([1,2,1])
Universidade da Madeira
Departamento de Matemática
Elsa Carvalho
252
 membro(1, []), criterio_1([1,2,1])
Programação em Lógica e Funcional (2000/01)
(Actualizado em 2004/05)
Corte
O corte não tem interpretação na lógica clausal. Apenas altera a
execução de um programa. A introdução de um corte não altera o
valor declarativo do programa: a relação definida por membro é a
mesma.
No entanto, veremos que a relação calculada pode ser alterada
inadvertidamente ...
O corte no exemplo anterior foi inofensivo no que respeita à
definição de aceita. Não eliminámos respostas possíveis: apenas
eliminámos ramos redundantes para o objectivo em questão.
No entanto, o mesmo exemplo serve para ilustrar os perigos que
rodeiam a utilização do corte.
Universidade da Madeira
Departamento de Matemática
Elsa Carvalho
253
Programação em Lógica e Funcional (2000/01)
(Actualizado em 2004/05)
Corte - Exemplo
O que aconteceria se utilizássemos o novo procedimento para o
objectivo
 membro(Q, [1,2,1])
 membro(Q, [1,2,1])
 membro(Q, [2,1])
!
{Q/1}
 membro(Q, [1])
{Q/2}
 membro(Q, [])
{Q/1}
Universidade da Madeira
Departamento de Matemática
Elsa Carvalho
254
Programação em Lógica e Funcional (2000/01)
(Actualizado em 2004/05)
Corte
O corte introduz incompletude e situações aberrantes que põem
em cheque o valor declarativo do programa.
A utilização do corte normalmente dificulta a leitura e a
compreensão dos programas, pois as relações definidas e
calculadas não coincidem. Deve ser evitado em favor de outras
soluções.
Uma alternativa consiste no reforço da componente lógica, tal
como foi apresentado anteriormente.
Universidade da Madeira
Departamento de Matemática
Elsa Carvalho
255
Programação em Lógica e Funcional (2000/01)
(Actualizado em 2004/05)
Corte
Em certos casos a utilização do corte é inofensiva e mesmo
benéfica (cortes limpos):
dist(X, X, 0)  !
dist(suc(X), Y, suc(Z))  X>=Y, !, dist(X,Y,Z)
dist(X,Y,Z)  X<Y, !, dist(Y,X,Z)
As três cláusulas excluem-se mutuamente e, por isso, os cortes
não excluem ramos bem sucedidos (apenas evitam que outras
cláusulas respondam à chamada).
Universidade da Madeira
Departamento de Matemática
Elsa Carvalho
256
Programação em Lógica e Funcional (2000/01)
(Actualizado em 2004/05)
Iteração vs. Recursão
Uma cláusula recursiva é uma cláusula que contém uma chamada
a si própria:
p(X)  q1, ..., qn, p(t), r1, ..., rm
Por exemplo, ordenada([X,Y|T])  ordenada([Y|T]), X<Y
Uma cláusula iterativa é uma cláusula recursiva cuja chamada a si
própria é apenas a última chamada do corpo
p(X)  q1, ..., qn, p(t)
Por exemplo, ordenada([X,Y|T])  X<Y, ordenada([Y|T])
Universidade da Madeira
Departamento de Matemática
Elsa Carvalho
257
Programação em Lógica e Funcional (2000/01)
(Actualizado em 2004/05)
Iteração vs. Recursão
Programas iterativos são normalmente mais eficientes:
a saída do corpo da cláusula não necessita de aguardar pelos
resultados de chamadas futuras, evitando a gestão de uma pilha
de chamadas pendentes.
Inversão de uma lista:
inverte([], []) 
inverte([X|L1], L2)  inverte(L1, W), fim(X, W, L2)
fim(X, [], [X]) 
fim(X, [Y|Z], [Y|W])  fim(X, Z, W)
Universidade da Madeira
Departamento de Matemática
Elsa Carvalho
258
Programação em Lógica e Funcional (2000/01)
(Actualizado em 2004/05)
Universidade da Madeira
Departamento de Matemática
Elsa Carvalho
259
Programação em Lógica e Funcional (2000/01)
(Actualizado em 2004/05)
{ Q/ [c,b,a] }
{ Q2/ [a] }
 fim(a,[ ], Q2)
{ Q1/ [b|Q2] }
 fim(a,[b], Q1)
{ Q/ [c|Q1] }
 fim(a,[c,b], Q)
 fim(b, [ ], W4), fim(a,[c|W4], Q)
 fim(b, [c], W1), fim(a, W1, Q)
 fim(c, [], W2), fim(b, W2, W1), fim(a, W1, Q)
 inverte([], W3), fim(c, W3, W2), fim(b, W2, W1), fim(a, W1, Q)
 inverte([c], W2), fim(b, W2, W1), fim(a, W1, Q)
 inverte([b,c], W1), fim(a, W1, Q)
 inverte([a,b,c], Q)
Iteração vs. Recursão
Iteração vs. Recursão
Certos programas recursivos podem ser transformados em
programas iterativos fazendo uso de acumuladores, i.e., de
variáveis lógicas que passam informação sobre um valor
acumulado numa iteração para a próxima iteração.
Versão iterativa
inverte(L, L1)  aux_inverte(L, L1, [])
aux_inverte([X|L1], L2, W)  aux_inverte(L1, L2, [X|W])
aux_inverte([], L2, L2) 
Universidade da Madeira
Departamento de Matemática
Elsa Carvalho
260
Programação em Lógica e Funcional (2000/01)
(Actualizado em 2004/05)
Universidade da Madeira
Departamento de Matemática
Elsa Carvalho
261
Programação em Lógica e Funcional (2000/01)
(Actualizado em 2004/05)
{ Q/ [c,b,a] }
 aux_inverte([ ], Q, [c,b,a])
 aux_inverte([c], Q, [b,a])
 aux_inverte([b,c], Q, [a])
 aux_inverte([a,b,c], Q, [ ])
 inverte([a,b,c], Q)
Iteração vs. Recursão