Elsa Carvalho 241 Universidade da Madeira Departamento de Matemática Programação em Lógica e Funcional (2000/01) (Actualizado em 2004/05) Interpretação

Elsa Carvalho

Programação em Lógica e Funcional (2000/01)(Actualizado em 2004/05)

1Universidade da Madeira

Departamento de Matemática

Interpretação ProcedimentalVimos 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.

Elsa Carvalho




Interpretação ProcedimentalUm 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 pq1, ..., 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 pq1, ..., qn responde a uma chamada a gi se gi e p são unificáveis.

Elsa Carvalho




Interpretação ProcedimentalChamada 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).

Elsa Carvalho




Interpretação ProcedimentalPassagem de parâmetrosAo 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.

Elsa Carvalho




CorteO 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)

!.

Elsa Carvalho




CorteMas 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?

Elsa Carvalho




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]) membro(1, []), criterio_1([1,2,1])

Elsa Carvalho




CorteA 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.

Elsa Carvalho




Cortereforç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.

Elsa Carvalho




Corte membro(1, [1,2,1])

membro(1, [2,1])

membro(1, [1])

membro(1, [])

!

!

Elsa Carvalho




CorteFuncionamento 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 eas alternativas a qualquer das chamadas pi ainda não exploradas

r, ...

p1p1

pmpm

!, q1, ..., qn

Elsa Carvalho




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]) membro(1, []), criterio_1([1,2,1])

Elsa Carvalho




CorteO 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.

Elsa Carvalho




Corte - ExemploO que aconteceria se utilizássemos o novo procedimento para o objectivo membro(Q, [1,2,1])

membro(Q, [1,2,1])

!

{Q/1}

membro(Q, [2,1])

{Q/2} membro(Q, [1])

{Q/1} membro(Q, [])

Elsa Carvalho




CorteO 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.

Elsa Carvalho




CorteEm 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).

Elsa Carvalho




Iteração vs. RecursãoUma 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])

Elsa Carvalho




Iteração vs. RecursãoProgramas 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)

Elsa Carvalho




in

vert

e([

a,b

,c],

Q)

Iter

ação

vs.

Rec

urs

ão

in

vert

e([

b,c

], W

1),

fim

(a, W

1, Q

)

in

vert

e([c

], W

2),

fim(b

, W

2, W

1),

fim(a

, W

1, Q

)

in

vert

e([],

W3)

, fim

(c, W

3, W

2), f

im(b

, W2,

W1)

, fim

(a, W

1, Q

)

f

im(c

, []

, W

2),

fim(b

, W

2, W

1),

fim(a

, W

1, Q

)

fi

m(b

, [c]

, W1

), fi

m(a

, W1,

Q)

fi

m(b

, [ ],

W4)

, fim

(a,[c

|W4

], Q

)

fi

m(a

,[c,b

], Q

)

fi

m(a

,[b],

Q1

)

fi

m(a

,[ ],

Q2

){ Q

/ [c

|Q1]

}

{ Q

1/ [

b|Q

2] }

{ Q

2/ [

a] }

{ Q

/ [c

,b,a

] }

Elsa Carvalho




Iteração vs. RecursãoCertos 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)

Elsa Carvalho




in

vert

e([a

,b,c

], Q

)

a

ux_i

nver

te([

a,b,

c],

Q,

[ ])

a

ux_i

nver

te([

b,c]

, Q

, [a

])

a

ux_i

nver

te([

c],

Q,

[b,a

])

a

ux_i

nver

te([

],

Q,

[c,b

,a])

{ Q

/ [c

,b,a

] }

Iter

ação

vs.

Rec

urs

ão

Documents

Elsa Carvalho 241 Universidade da Madeira Departamento de Matemática Programação em Lógica e Funcional (2000/01) (Actualizado em 2004/05) Interpretação