LISTAS

Uma lista é uma estrutura de dados muito comum na
programação não numérica (com particular destaque na
computação simbólica onde representa quase todo o tipo de
estrutura)  principal estrutura de dados na linguagem Lisp
(List Processing) .

As listas representam árvores de parsing (léxicas),
gramáticas, programas e entidades matemáticas tais como:
grafos, fórmulas e funções.
Representação
Notação (adequada para representação em árvore)
Tradicionalmente uma lista é representada pelo termo •(X, L) em
que X é um elemento e L o resto da lista.
A lista vazia denota-se por nil.
Notação PROLOG
Uma lista é um termo [X|L] em que X é o primeiro elemento e L é
a lista resto (sub-lista).
A lista vazia denota-se por [].
Dizemos que X é a cabeça da lista e L é a cauda.
[X|L] denota a lista (não vazia) cuja cabeça é o objecto X e
a cauda é a lista L
X1, X2, ..., Xn denota a lista constituída pelos objectos X1, X2,
..., Xn.
Exemplos
a
 1, 2, 3 
 a, b |  c  
[ a | L]
[ X | L]

Termos equivalentes
•(a, nil)
[a]
•(a, •(b,nil))
[a,b]
•(a, •(b,X))
[a,b|X]
 a |  
 1 |  2, 3 
a|b|c
[a| [] ]
[a|[b] ]
[a,b| [] ]
Listas
Podemos definir lista como
list([]).
list([X|L]) :- list([L]).
Ao contrário das linguagens funcionais, em Prolog uma
lista é um objecto polimórfico. Isto é, podemos ter listas
com objectos de diferentes tipos.
Por exemplo:
[a, 1, ana, 8.32, [a,b,c], X, ola, 6, [1, [2,3], c], fim]
LISTAS -Unificação
Lista1
Lista2
substituição
 X, Y, Z 
 a, 2, b 
{ X/a, Y/2, Z/b }
 ana 
X|L
{ X/ana, L/ }
 X, 8 | L 
 a, Y, b 
{ X/a, Y/8 L/b }
X|L
 a, 10, b 
{ X/a, L/10,b }
X
 a, 12 
não unificáveis
X|Y|Z
 a, 12, b 
{ X/a, Y/12, Z/b }
 c | L1 
 Y, a | L2 
{ L1/ a | L2, Y/c }
Alguns predicados básicos para manipular
listas MEMBRO (member*)
Determinar se um elemento é membro de uma lista (member).
X é membro de uma lista L (member(X,L)) se X é a cabeça de L, ou X é
membro da cauda de L
member(X,[X|L]).
member(X,[Y|L]) : member(X,L)
Exemplos
?  member(b,[a,b,c]).
yes
?  member(b,[a,[b,c]]).
no
?  member([b,c],[a,[b,c]]).
yes
?- member(X,[a,[b,c]]).
X = a;
X = [b,c];
no
(Construa as respectivas árvores de pesquisa)
Alguns predicados básicos para manipular listas
CONCATENAÇÃO (append*)
append(L,M,N) - N é a concatenação de L e M
se L é vazia, N é igual a M;
se L não é vazia, N é igual à lista cuja cabeça é a cabeça de L e cauda igual à
concatenação da cauda de L com a lista M.
Exemplos
? – append([a,[b,c],d],[a,[],b],L).
append([],M,M).
L = [a,[b,c],d,a,[],b];
append([X|L],M,[X|N]) : append(L,M,N).
no
?  append(L1,L2,[a,b,c
L1 = []
L2 = [a,b,c];
L1 = [a]
L2 = [b,c];
L1 = [a,b]
L2 = [c];
L1 = [a,b,c]
L2 = [];
no
Alguns predicados básicos para manipular listas
ADICIONAR (add)
Em geral não é necessário definir um procedimento para adicionar um
objecto no início (i.e. à esquerda dos restantes elementos) de uma
lista.
Sabemos que se X é um objecto e L uma lista, [X|L] é a lista que
resulta de adicionar X a L.
No caso de ser necessário é definido um procedimento (add) que é
constituído pela seguinte cláusula:
add(X,L,[X|L]).
Exemplo
?  add([a,b],[1,2,[]],L).
L = [[a,b],1,2,[]];
no
Alguns procedimentos básicos sobre listas
Remover (del)
del(X,L,M) - M é a lista que resulta da remoção de
uma ocorrência do objecto X na lista L.
M é a cauda de L, se X é a cabeça de L;
M é a lista cuja cabeça é X e a cauda
que resulta da remoção de X da cauda
de L, se X não é a cabeça de L.

del(X,[X|L],L).
del(X,[Y|L],[Y|M]) : del(X,L,M).
Exemplos
? – del(a,[
L = [b,a,a]
L = [a,b,a]
L = [a,b,a]
no
? – del(a,L
L = [a,1,2]
L = [1,a,2]
L = [1,2,a]
no
Alguns procedimentos básicos sobre listas
SUBLISTA (sublist)
S é uma sublista de L (sublist(S,L))se
L pode ser decomposta nas listas L1 e L2, e L2 pode ser
decomposta nas listas S e alguma L3
sublist(S,L) :- append(L1,L2,L), append(S,L3,L2).

Exemplos
? – sublist([a,b],[b,c,a]).
no
? – sublist(S,[a,b,c]).
S = [];
S = [a];
S = [a,b];
S = [a,b,c];
S = [b];

Alguns procedimentos básicos sobre listas
Permutação (permutation)
L2 é uma permutação de L1 (permutation(L1,L2)) se
L2 é vazia, se L1 é vazia, ou
L2 é a lista que resulta de permutar a cauda de L1 e adicionar a cabeça de L1 em
qualquer posição.
permutation([ ],[ ]).
permutation([X|L],P) : permutation(L,L1), insert(X,L1,P).
Exemplo
? – permutation([a,b,c],P).
P = [a,b,c];
P = [a,c,b];
P = [b,a,c];
P = [b,c,a];
P = [c,a,b];
P = [c,b,a];
no
* insert(X,L1,L2) :- del(X,L2,L1).
TRADUÇÃO (EXEMPLO)



Alterar uma frase da linguagem natural,
representada pela lista das palavras que a
constituem (mantendo a ordem original das
palavras na frase), através de uma função que
a cada palavra associa uma outra palavra (i.e.
uma função de tradução).
[you, are, a, computer] (representa a frase )
função de tradução é descrita através dos
seguintes factos:
change(you,i).
change(are,[am, not]).
change(french, german).
Exercícios

Defina os seguintes predicados de manipulação de listas:

prefixo(L, M): que é verdadeiro se L é uma sub-lista inicial de M.
Por exemplo, prefixo([a,b], [a,b,c]) é verdadeiro.
sufixo(L, M): que é verdadeiro se L é uma sub-lista terminal de M.
Por exemplo, sufixo([b,c], [a,b,c] é verdadeiro.
sublista(L, M): que é verdadeiro se L é uma sub-lista de M. De
notar que uma sub-lista necessita que os elementos sejam
consecutivos, ou seja, [b,c] é uma sub-lista de [a,b,c,d] enquanto
que [a,c] não é.
Aritmética


Em Prolog podemos fazer uso de operadores aritméticos não
lógicos pré-definidos pelo sistema, como por exemplo
 >, >=, +, *, -, etc.
A interrogação




tem como resposta
?5<7
yes
Esta faceta mostra uma componente não lógica do Prolog que
é o seu processador de expressões aritméticas.
Aritmética & Lógica










Assim temos, as seguintes funções cujos argumentos são expressões
aritméticas:
X+Y
X mod Y
X^Y
sqrt(X)
floor(X)
X-Y
X rem Y
sin(X)
ceil(X)
X/Y
exp(X)
X//Y
cos(X)
log10(X)
log(X)
-X
tan(X)
Predicados aritméticos
(X e Y são expressões aritméticas, Z é um termo)
Z is X
X é avaliado e o resultado é unificado com Z
X =:= Y
é verdadeiro se os valores de X e Y são iguais
X =\= Y
é verdadeiro se os valores de X e Y são
diferentes
Avaliador de expressões
aritméticas is




O interpretador de Prolog possui um processador de
expressões que é invocado com interrogações da forma:
Variável is expressão
O predicado is denomina o avaliador aritmético. A
interrogação pode ser lida como “Variável toma o valor
do resultado de expressão”. Ou seja expressão é
processada como uma expressão aritmética e o seu
resultado é unificado com Variável.
A interrogação tem ou não sucesso de acordo com o
resultado desta unificação.
Avaliador de expressões
aritméticas


O operador = denomina unificação explicita. Corresponde à igualdade de
termos, provocando a instanciação das variáveis envolvidas. Não provoca
o processamento da expressão.
Por exemplo se tivermos
Z=5+3


Z é substituido por 5+3 e não por 8.

A interrogação



?Y=3, X is 5 + Y.
tem como resultado
X=8, Y=3.
Avaliador de expressões
aritméticas








No entanto podemos ter situações de erro se a expressão a calcular
não for totalmente instanciada.
Por exemplo
?Y=X+3, Z is Y+1, X=5.
Neste exemplo a primeira unificação é perfeitamente válida. É
possível unificar uma variável com uma expressão. No entanto não é
possível calcular uma expressão aritmética com variáveis não
instanciadas.
Neste exemplo o Prolog interrompe a computação e produz uma
mensagem de erro.
A expressão
? Y=X+3, X=5, Z is Y+1.
já não levanta problemas.
Avaliador de expressões
aritméticas
Exemplo



fact(0,1).
fact(X,Z):- W is X-1, W>=0, fact(W,Y), Z is X*Y.
De notar que interrogações do tipo
?factorial(X, 2).



dão origem a mensagens de erro e consequente paragem da
execução.
Porquê?
Expressões aritméticas

O operador Z =:= 3+Y compara apenas o
resultado do processamento de Z e de 3+Y, o que
implica que tenham que ser expressões
aritméticas. Não provoca instanciação de
variáveis.
OPERADORES DE COMPARAÇÃO



As expressões de comparação de expressões aritméticas são construídas
com os operadores usuais de comparação para números inteiros e reais: >
(maior do que), < (menor do que), >= (maior ou igual do que), =<
(menor ou igual do que), =:= (igual a) e =\= (diferente de); que estão
usualmente pré-definidos nas implementações do PROLOG.
A avaliação de qualquer operador de comparação é produzida após a
avaliação (completa) dos respectivos operandos
e.g. na expressão
5*2>X+1
são, primeiramente, avaliadas as expressões
 5 * 2 e X + 1
(o que só é possível após a instânciação de X) e, depois, é avaliada a
expressão de comparação).



OPERADORES DE COMPARAÇÃO










Na comparação =:= (igual a) as expressões (aritméticas) à esquerda
e direita do operador são avaliadas antes da avaliação da comparação
Na comparação = são comparadas as estruturas dos termos (não
necessariamente expressões aritméticas) à esquerda e direita do
operador. Por exemplo
?  1 + 2 =:= 2 + 1.
yes
?  1 + 2 = 2 + 1.
no
?  1 + A = B + 2.
A = 2;
B = 1;
no
Exemplo (máximo divisor comum)
O máximo divisor comum Z de dois inteiros X e Y é obtido da seguinte
forma (Algoritmo de Euclides):
 se X = Y então Z = X;
 se X < Y então Z é igual ao máximo divisor comum entre X e Y – X;
 se Y < X então Z é igual ao máximo divisor comum entre X e X – Y
(ou o máximo divisor comum entre Y e X).

mdc(X,X,X).
mdc(X,Y,Z) : X < Y, Y1 is Y – X, mdc(X,Y1,Z).
mdc(X,Y,Z) : Y < X, Y1 is X – Y, mdc(Y1,Y,Z).
(ou Y < X, mdc(Y,X,Z))
TIPOS DE NOTAÇÃO PARA OS
OPERADORES
Infixos Prefixos Sufixos
(ou
posfixos
)
 onde
xfx
fx
xf
 x representa um argumento cuja
xfy é estritamente
fy
yf
precedência
menor
do que a
yfxprecedência do operador.
 y representa um argumento cuja

TIPOS DE NOTAÇÃO PARA OS
OPERADORES
Associatividade
Para operadores de igual prioridade,
precisamos de saber se avaliamos da
esquerda para a direita ou vice-versa.
Infixo xfx não
associativo
xfy associativo à
direita
yfx associativo à
esquerda
Prefixo fx não
REPRESENTAÇÃO EM PROLOG
(directivas)
: op(Prec,PosAssoc,Atomo).

onde

Prec denota a precedência (i.e. um

número inteiro entre 1 e 1200 que
depende da implementação do Prolog).

Nota: Uma prioridade maior é






Exemplo (operadores lógicos)
Uma implementação dos operadores
lógicos , ,  e .
: op(800,xfx,equivalence).
: op(700,xfy,or).
: op(600,xfy,and).
: op(500,fy,not).
?
X=equivalence(not(and(X,Y)),or(not(X
),not(Y))).
TIPOS DE NOTAÇÃO PARA OS
OPERADORES
Infixos Prefixos Sufixos
(ou
posfixos
)
 onde
xfx
fx
xf
 x representa um argumento cuja
xfy é estritamente
fy
yf
precedência
menor
do que a
yfxprecedência do operador.
 y representa um argumento cuja

TIPOS DE NOTAÇÃO PARA OS
OPERADORES
Associatividade
Para operadores de igual prioridade,
precisamos de saber se avaliamos da
esquerda para a direita ou vice-versa.
Infixo xfx não
associativo
xfy associativo à
direita
yfx associativo à
esquerda
Prefixo fx não
REPRESENTAÇÃO EM PROLOG
(directivas)
: op(Prec,PosAssoc,Atomo).

onde

Prec denota a precedência (i.e. um

número inteiro entre 1 e 1200 que
depende da implementação do Prolog).

Nota: Uma prioridade maior é






Exemplo (operadores lógicos)
Uma implementação dos operadores
lógicos , ,  e .
: op(800,xfx,equivalence).
: op(700,xfy,or).
: op(600,xfy,and).
: op(500,fy,not).
?
X=equivalence(not(and(X,Y)),or(not(X
),not(Y))).
Procedimentos Pré-definidos em prolog
comunicação
Vários tipos de comunicação
utilizador/programa:
 Comunicação
básica (questão, em
seguida,
resposta
em
termos
instanciações de variáveis).
 Comunicação (input) de dados sobre
outras formas (quais?).
 Comunicação (output) de dados em
terminal
user_in
input
streams
file_in 1
file_out 1
P
file_in 2



user_out
file_out 2
output
streams

O programa pode utilizar vários ficheiros simultaneamente para leitura,
designados por input streams ou para escrita, designados por output
streams.
Durante a execução de um programa em PROLOG são abertos, inicialmente,
um ficheiro de leitura, designado por current input stream e um ficheiro de
escrita, designado por current output stream.
Processamento de ficheiros de termos
PROCEDIMENTO read
O procedimento (de input) read faz a leitura de termos a partir do current input
stream.
O objectivo
read(X).
faz a leitura de um termo T (a introduzir após validar o objectivo) e,
seguidamente, X é substituído por T, se X é uma variável; senão read(X)
falha sem retrocesso.
Exemplo
? read(X).
? read(atomo).
? read(X).
|: termo.
|: atomoX.
|: Y.
X = termo;
no
X = _G111
no
yes
Observação
A introdução de um termo termina com um ponto.
PROCEDIMENTO write
O procedimento (de output) write faz a
escrita de termos no current output stream.
O objectivo
write(T).
escreve o termo T na forma sintática utilizada
para as instâncias das variáveis.
Exemplo
? write(termo). ? write(X). ?
PROCEDIMENTO tab
O procedimento (de output) tab faz a inserção de espaços em branco no
current output stream.
O objectivo tab(N) introduz N espaços em branco no current output stream.
Exemplos
? read(X),tab(10),write(X).
|: [a,b,c].
[a,b,c]
X = [a,b,c];
no
?- write(ola), tab(5), write(amigos).
ola
amigos
PROCEDIMENTO nl
O procedimento nl faz deslocar a escrita
de termos, no current output stream,
para o início da próxima linha.
Exemplo
?write(ola),nl,write([a,b,c]).
ola
[a,b,c]
Exemplo
cube :write('proximo
numero: '),
read(X),
process(X).
process(stop) :- !.
process(N) :C is N * N * N,
write('o cubo de
? cube.
proximo numero:
5.
o cubo de 5 e
125
proximo numero:
4.
o cubo de 4 e 64
proximo numero:

Manipulação de caracteres
PROCEDIMENTO put
O procedimento (de output) put
escreve, no current output stream, um
carácter codificado em ASCII.
O objectivo
put(C)
escreve o carácter que corresponde ao
código ASCII C.
(De)Composição de átomos
name(A,L)
é verdadeiro se L é a sequência (representada por uma lista) dos códigos ASCII
que correspondem aos caracteres que formam o átomo A.
Exemplo
getsentence(Wordlist) :- get0(Char), getrest(Char,Wordlist).
getrest(46,[]) :- !.
getrest(32,Wordlist) :- !, getsentence(Wordlist).
getrest(Letter,[Word|Wordlist]) :- getletters(Letter,Letters,Nextchar),
name(Word,Letters),getrest(Nextchar,Wordlist).
getletters(46,[],46) :- !.
getletters(32,[],32) :- !.
getletters(Let,[Let|Letters],Nextchar) :get0(Char),getletters(Char,Letters,Nextchar).
? getsentence(W).
|: Mary was pleased to see the robot fail.
['Mary','was','pleased','to','see','the','robot','fail']
yes
Leitura de programas
Podemos comunicar os nossos programas ao PROLOG através dos
predicados pré-definidos: consult e reconsult.
PROCEDIMENTO consult
O efeito da execução do objectivo ? consult(F) é disponibilizar todas as
cláusulas no ficheiro F, na sessão actual do PROLOG, para serem
utilizadas, posteriormente, na execução de objectivos introduzidos
pelo utilizador.
Se, na mesma sessão do PROLOG, outro ficheiro (e.g. G) é lido através
da execução do objectivo ? consult(G), então é adicionado, ao fim
do ficheiro actual, as cláusulas do (novo) ficheiro G.

PROCEDIMENTO reconsult
O efeito da execução do objectivo ? reconsult(F) é análogo à execução
do objectivo ? consult(F), excepto que, todas as cláusulas do
ficheiro F, que foram previamente definidas, são redefinidas pelas
cláusulas na nova versão de F.

Verificar o tipo dos termos
integer(X) é verdadeiro se X é um inteiro.
var(X) é verdadeiro se X é uma variável não
instanciada.
nonvar(X) é verdadeiro se X é um termo,
que não seja uma variável, ou X é uma
variável instanciada.
atom(X) é verdadeiro se X é um átomo.
real(X) é verdadeiro se X é um real.
PROCEDIMENTO =..
T =.. L é verdadeiro se L é uma lista
que contém o functor principal do
termo T seguido dos seus argumentos.
Exemplo
enlarge(Fig,F,Fig1) :Fig =.. [Type|Parameters],
multiplylist(Parameters,F,Parameters1),
Fig1 =.. [Type|Parameters1].
multiplylist([],_,[]).
PROCEDIMENTO functor
functor(Term,F,N) é verdadeiro se F é o
functor principal de Term e N a aridade de
F.
PROCEDIMENTO arg
=
Tipos de igualdade
X = Y é verdadeiro se X é igual a Y.
is
X is E é verdadeiro se X é a avaliação da expressão
E.
=:=
E1 =:= E2 é verdadeiro se a avaliação da
expressão E1 é idêntica à avaliação da expressão
E2.
=\=
Exemplos
? f(a,b) == f(a,b).
yes
? f(a,b) == f(a,X).
no
? f(a,X) == f(a,Y).
no
? X \== Y.
manipulação de bases de dados


Uma base de dados relacional é uma
especificação de conjunto de relações.
Um programa em PROLOG é um tipo
de base de dados relacional onde a
especificação de relações está
parcialmente explícita através dos
factos e parcialmente implícita através
das regras.
PROCEDIMENTO assert
assert(C) adiciona a cláusula C à base de
dados (activa).

PROCEDIMENTO asserta
asserta(C) adiciona a cláusula C ao início da
base de dados (activa).
Uma aplicação do procedimento asserta é
guardar objectivos que foram previamente
computados.

Exemplos
? assert(p(a)),assertz(p(b)),asserta(p(c)).
yes
? p(X).
X = c;
X = a;
X = b;
no
?- retract(p(a)).
yes
Controlo de execução - o Corte !
O corte, denotado por !, elimina o
retrocesso.
fail é um objectivo que falha sempre.
true é um objectivo que é sempre bem
sucedido
not(P) é tipo de negação que se
comporta exactamente como se tivesse
definido da seguinte forma:
not(P) :- P,!,fail;true.
Controlo de execução - o Corte !
Adição de elementos sem
duplicação
adic(X,L,L1).
Se x é membro de L então L=L1
senão L1 é L com a inserção de X
na cabeça.
adic(X,L,L):membro(X,L),!,Adic(X,L,L1).
Controlo de execução - If-then-else
ifThenElse(X,Y,Z).
Pode ser simulado em Prolog por
ifThenElse(X,Y,Z):- X,!,Y.
ifThenElse(X,Y,Z)_- Z.
PROCEDIMENTO bagof
bagof(X,P,L) é verdadeiro se a lista L contém todo o objecto X que satisfaz o
objectivo P
.Exemplo
age(peter,7).
age(ann,5).
age(pat,8).
age(tom,5).
? bagof(Child,age(Child,5),List).
List = [ann,tom];
no
? bagof(Child,age(Child,Age),List).
Age = 7
List = [peter];
Age = 5
List = [ann,tom];
Age = 8
List = [pat];
no
? bagof(Child,Age^age(Child,Age),List).
List = [peter,ann,pat,tom];
no
PROCEDIMENTO setof
setof(X,P,L) é verdadeiro se a lista L
(ordenada, por ordem alfabética ou
por ordem crescente, no caso dos
números, e sem elementos repetidos)
contém todo o objecto X que satisfaz o
objectivo P.
Exemplo
?
PROCEDIMENTO findall
findall(X,P,L) é verdadeiro se a lista L
contém todo o objecto X que satisfaz o
objectivo P.
Exemplo
findall(+Template,
+Goal, -Bag)
?
findall(Child,age(Child,Age),List).
Creates a list of the instantiations Template gets successively on backtracking
over Goal and unifies the result with Bag. Succeeds with an empty list if Goal has
List =findall/3
[peter,ann,pat,tom];
no solutions.
is equivalent to bagof/3 with all free variables bound with
the existence operator (^), except that bagof/3 fails when goal has no solutions.
no
Princípios da Programação em
Prolog












princípios gerais da programação
Os critérios usualmente adoptados para avaliar a qualidade de um programa incluem a
verificar as seguintes propriedades:
Correcção
Um programa deve fazer o que é suposto fazer.
Eficiência
Um programa deve minimizar o tempo de execução e o espaço em memória.
Legibilidade/Transparência
Um programa deve ser legível e fácil de interpretar.
Robustez
A introdução de dados incorrectos ou inesperados deve ser prevista pelo programa.
A ocorrência destes erros deve ser notificada e não deve interromper a execução do
programa.
Documentação
Um programa deve estar devidamente documentado (o texto do programa e os
comentários constituem a documentação mínima associada ao programa).
Princípios da Programação em
Prolog


A importância destes critérios depende do problema, das
circunstâncias em que o programa é escrito e do contexto onde é
suposto ser utilizado. No entanto, a correcção é, sem dúvida, o critério
mais importante.
Como escrever programas que satisfaçam algumas (as mais
importantes num determinado contexto) ou, preferencialmente, todas
estas propriedades?

interpretar/raciocinar (linguagem de especificação)

codificar (linguagem de programação)

Devemos, primeiro, interpretar o problema, desenvolver e analisar
(numa linguagem de especificação) soluções e, após ser definida a
"melhor" solução, devemos passar à codificação (numa linguagem de
programação).
Princípios da Programação em Prolog
Refinamento gradual






refinamento gradual
Para transformar (gradualmente) a especificação (e.g. na linguagem
natural ou numa linguagem de especificação) de um problema num
programa codificado numa linguagem de programação, é usual utilizar o
Refinamento Gradual (Top-Down), i.e. um programa é obtido após
uma sequência de transformações (ou refinamentos) – aplicadas tanto às
definições dos procedimentos como às estruturas de dados  equivalentes
que traduzem um aumento de detalhe no sentido da aproximação à
linguagem de programação.
Vantagens
Permite a formulação de rascunhos de soluções em termos do que é mais
relevante para a resolução do problema.
Cada solução é sucinta, simples e correcta.
Cada refinamento representa um pequeno passo na resolução do
problema; o refinamento de uma solução correcta gera uma (nova)
solução num nível mais detalhado, i.e. menos abstracto.
metodologia de programação na
P.L.





No caso da programação em lógica o refinamento incide sobre a
definição das relações que constituem o programa. Se a natureza
do problema sugere uma aproximação algorítmica, então deve ser
aplicado um refinamento gradual algorítmico, adoptando a
perspectiva procedimental do PROLOG.
O processo de desenvolvimento de uma solução para um problema
consiste em decompor o problema em (sub) problemas mais
simples (i.e. de menor complexidade).
Como encontrar os subproblemas mais adequados?
Recursividade
Dividir o problema em casos pertencentes aos dois grupos
seguintes:
trivial ou casos limite;
casos gerais onde a solução é construída a partir de
versões mais simples do problema original.




Uma razão pela qual a recursividade é aplicada à definição
de relações no PROLOG tem a ver com a natureza da
estrutura recursiva dos dados.
generalização
É conveniente generalizar o problema original, sendo
assim, possível construir uma solução recursiva mais
abrangente. Portanto, a solução para o problema original
é um caso particular de um problema mais geral.
A generalização de uma relação tipicamente envolve um
aumento do seu número de argumentos. Este processo é
acompanhado de um aprofundamento do problema de
forma a conseguir obter a generalização mais adequada.
Representações Gráficas






Quando desenvolvemos uma solução para um problema é usual
recorrer a representações gráficas para ajudar a identificar as
relações essenciais entre os objectos.
Vantagens
O PROLOG é particularmente adequado para problemas que envolvam
relações entre objectos. Os grafos, onde os nós representam os
objectos e os arcos as relações entre os objectos, são particularmente
apropriados para a representação dos problemas.
As estruturas de dados em PROLOG são representadas por árvores.
A natureza declarativa do PROLOG facilita a tradução da
representação gráfica para o PROLOG.
Convenções estilísticas
Regras estilísticas
O corpo de uma cláusula de programa não
deve ter muitos literais.
Os procedimentos não devem conter muitas
cláusulas.
Os nomes utilizados para os procedimentos e
variáveis devem indicar o significado das
relações e a adequação das estruturas de
dados.
Devem ser utilizados espaços, linhas em
branco e indentação. As cláusulas que
pertencem a um procedimento devem estar
agrupadas: cada cláusula e cada literal do

Comentários nos programas
Em geral a seguinte informação deve ser incluída nos
comentários dos programas:
o que é que o programa faz (objectivo do programa),
como deve ser utilizado (e.g. qual o objectivo a ser
introduzido para iniciar a execução do programa e os
resultados esperados após a sua execução (possivelmente
parcial));
como estão representados os principais objectos;
o tempo de execução e a memória exigidos pelo programa;
quais as limitações do programa;
qual o significado de cada predicado; quais são os seus
argumentos (identificando os de input e os de output);

debugging




debugging- Implementação, nas linguagens de programação, de um
conjunto de procedimentos que auxiliam o programador a detectar
nos programas (ou em partes (módulos) dos programas) a ocorrência
de erros, durante a execução dos programas.
Geralmente estes procedimentos acompanham o desenvolvimento da
computação desde o seu início e permitem suspender a execução
sempre que desejado (possivelmente para verificar, por exemplo, se
os resultados da computação são diferentes dos esperados naquele
ponto do programa).
Em consequência da adopção generalizada da técnica bottom-up
para a construção de uma implementação para um programa, é
natural que a técnica de debugging seja utilizada, primeiro, no teste
de pequenas partes do programa e, depois, em partes gradualmente
maiores (ou eventualmente no programa completo) tendo,
previamente a garantia de que as partes mais pequenas estão isentas
de erros.
debugging em PROLOG






No PROLOG a técnica (designada por tracing) que suporta o
debugging fornece a visualização gradual (passo a passo) do
progresso (comportamento relacionado com a satisfação dos
objectivos) do programa durante a sua execução.
Existem alguns procedimentos pré-definidos (depende da
implementação do PROLOG) para o debugging tais como:
trace (notrace)
Activa (Desactiva) a visualização do comportamento do programa
para os objectivos que se seguem.
spy(P) (nospy(P))
Activa (Desactiva) a visualização do comportamento do predicado P
para os objectivos que se seguem.
optimização dos programas
PROLOG
Para
optimizar a eficiência (tempo/memória) da execução de um programa
em PROLOG é necessário estudar os aspectos da sua interpretação
procedimental (capítulo 3 (Interpretação Procedimental) dos
Fundamentos da Programação em lógica).
Alguns
aspectos da interpretação procedimental de um programa PROLOG
estão directamente relacionados com formas de optimização, que são
usualmente utilizadas no desenvolvimento dos programas, tais como:
alterar a ordem dos procedimentos no programa;
alterar a ordem das cláusulas nos procedimentos;
utilizar a técnica do corte;
adicionar ao programa, através das variantes do procedimento assert,
resultados que, posteriormente, optimizam o programa para outros
objectivos;
(optimização baseada na representação dos objectos) definir
estruturas de dados mais adequadas para representar os objectos.