Recolher soluções e compor estruturas em Prolog
findall, bagof, setof, variáveis livres, diferenças de listas, DCG e predicados de ordem superior.
Uma consulta devolve uma resposta de cada vez; para obter uma lista, escolhemos o que recolher, se as repetições devem ficar e se precisamos de uma lista por pessoa. As inscrições seguintes servem para comparar estas decisões. Depois da recolha, a página compõe estruturas: diferenças de listas, gramáticas, predicados de ordem superior, operadores e construção de termos.
Os três predicados sobre os mesmos factos
Com inscrito(ana,pfl). inscrito(ana,lbaw). inscrito(bruno,pfl)., compara:
?- findall(C, inscrito(ana,C), L).
L = [pfl, lbaw].
?- bagof(C, inscrito(ana,C), L).
L = [pfl, lbaw].
?- bagof(C, A^inscrito(A,C), L).
L = [pfl, lbaw, pfl].
?- setof(C, inscrito(ana,C), L).
L = [lbaw, pfl].Nas duas primeiras consultas, ana já está fixada e não há agrupamento; na terceira, A^ impede que as pessoas criem grupos separados, por isso as duas inscrições em pfl ficam na mesma lista. setof ordena e remove repetidos, e sem soluções findall sucede com [] enquanto os outros falham.
Escolher a recolha
| Predicado | Repetições | Variáveis livres no objetivo | Sem respostas |
|---|---|---|---|
findall(T,G,L) | Conserva. | Não criam grupos. | Sucede com L=[]. |
bagof(T,G,L) | Conserva. | Criam uma lista por combinação de valores. | Falha. |
setof(T,G,L) | Remove e ordena pela ordem de termos. | Criam grupos como bagof. | Falha. |
O template T é o que guardamos de cada prova de G. Uma variável que aparece em G mas não em T é livre para efeitos de agrupamento, salvo quando a quantificamos com ^. As ligações usadas dentro de findall não ficam como uma solução exterior para essas variáveis.
Com inscrito(ana,pfl)., inscrito(ana,lbaw)., inscrito(bruno,pfl). e uma segunda ocorrência de inscrito(ana,pfl)., findall(C,inscrito(ana,C),L) dá [pfl,lbaw,pfl], pois as duas provas para pfl continuam presentes; setof dá [lbaw,pfl], ordenado e sem repetidos.
Quando aparece um grupo por pessoa
Em bagof(C,inscrito(A,C),Cs), o template guarda C, mas A aparece apenas no objetivo. Obtemos A=ana, Cs=[pfl,lbaw,pfl] e depois A=bruno, Cs=[pfl]. Pedir mais respostas percorre grupos, não elementos de uma só lista.
Para juntar cadeiras de todas as pessoas sem esse agrupamento, escreve bagof(C,A^inscrito(A,C),Cs). O A^ torna A existencial naquele objetivo. A enumeração precisa de terminar para produzir a lista inteira; findall não devolve um prefixo de uma procura infinita.
:- use_module(library(lists)).
inscrito(ana, pfl).
inscrito(ana, lbaw).
inscrito(bruno, pfl).
inscrito(ana, pfl).
maximo(X,Y,X) :- X >= Y, !.
maximo(X,Y,Y) :- X < Y.
write_portatil(X) :- write(X), nl.
main :-
findall(C, inscrito(ana,C), Todas), write_portatil(Todas),
setof(C, inscrito(ana,C), Unicas), write_portatil(Unicas),
findall(A-Cs, bagof(C, inscrito(A,C), Cs), Grupos), write_portatil(Grupos),
bagof(C, A^inscrito(A,C), SemGrupos), write_portatil(SemGrupos),
( maximo(7,5,5) -> write_portatil(erro) ; write_portatil(recusado) ).Executa o código para ver a saída e os gráficos.
findall(X,fail,L) dá L=[]; bagof(X,fail,L) falha. Um bagof também pode falhar dentro de uma regra e impedir os objetivos seguintes. Se o enunciado exige uma lista vazia quando não há candidatos, escolhe esse comportamento explicitamente.
Listas abertas e diferenças de listas
[a,b|T] é uma lista aberta quando T ainda não tem valor. Não é uma lista finita terminada em []; preencher T acrescenta a continuação sem copiar o prefixo. Uma diferença de listas representa o par entre a lista completa e a sua cauda ainda por preencher, por exemplo [a,b|T]-T.
juntar_dl(A-B, B-C, A-C).Para juntar [a,b|T]-T e [c|U]-U, unificamos T com [c|U] e obtemos [a,b,c|U]-U; para fechar a lista, unificamos U=[]. O exemplo supõe caudas abertas frescas e listas construídas segundo este contrato, porque reutilizar uma cauda com a própria estrutura pode criar um ciclo.
A concatenação habitual percorre a primeira lista. Com caudas abertas frescas, a ligação mostrada na figura não percorre o prefixo e custa tempo constante no modelo de unificação sem occurs check. Construir, converter ou copiar as listas tem outros custos; não os eliminamos por escrever o par com -.
Da DCG à cláusula traduzida
Para s --> [a], s, [b]., a tradução é:
s([a|R1], S) :- s(R1, R2), R2 = [b|S].
s(S, S). % tradução de s --> [].Os argumentos adicionais são a entrada e o resto: em s([a,a,b,b],[]), a primeira chamada retira um a e a segunda retira outro antes de chamar s([b,b],R2). O caso vazio mantém [b,b] como resto e, no regresso, cada chamada retira um b, deixando o resto final [].
Gramáticas com DCG
Uma DCG descreve uma sequência de tokens. --> é traduzido em predicados que passam a entrada e a entrada restante, aproveitando o mesmo princípio das diferenças de listas:
s --> [a], s, [b].
s --> [].phrase(s,[a,a,b,b]) sucede: consumimos dois a, escolhemos a alternativa vazia e consumimos dois b no regresso. phrase(s,[a,b,a,b]) falha; esta gramática reconhece todos os a antes de todos os b, em igual quantidade. phrase/2 exige o consumo completo; phrase/3 permite observar o resto. A tradução acima mostra por que a ordem das alternativas e o modo de chamada continuam a afetar a procura: a escrita parece uma gramática, mas a execução continua a ser Prolog.
Recursão à esquerda pode entrar num ciclo antes de consumir um token. A ordem das alternativas e o modo de chamada continuam a afetar a procura, como mostra a tradução da mesma gramática. O facto de a escrita parecer uma gramática não elimina as regras de execução de Prolog.
Passar um predicado
call(P,X) aplica o objetivo representado por P a um argumento adicional. maplist(P,List) pede que o predicado se prove para todos os elementos; não devolve automaticamente uma lista transformada. A forma com duas listas, maplist(P,Entrada,Saida), usa um predicado de dois argumentos para relacionar os elementos correspondentes.
Ao usar predicados meta, verifica aridade, argumentos conhecidos e o comportamento quando um objetivo tem várias soluções. A ordem de procura e a necessidade de terminar não deixam de existir por serem escondidas numa biblioteca.
Operadores mudam a escrita do termo
:- op(600, xfy, liga). permite escrever a liga b em vez de liga(a,b). A declaração muda a leitura da sintaxe; não cria um predicado que faça uma operação. O número menor liga mais fortemente. Por isso, a + b * c tem estrutura +(a,*(b,c)), com as prioridades predefinidas.
Nas letras do tipo, f marca o operador; x exige um argumento de prioridade menor; y permite prioridade menor ou igual. Parênteses dão prioridade zero à expressão agrupada.
| Tipo | Forma | Repetição na mesma prioridade |
|---|---|---|
fx | Prefixo, op a. | op op a exige parênteses. |
fy | Prefixo, op a. | Aceita op op a, lido como op (op a). |
xfx | Infixo, a op b. | Não associa uma cadeia sem parênteses. |
xfy | Infixo. | Associa à direita: a op (b op c). |
yfx | Infixo. | Associa à esquerda: (a op b) op c. |
Com liga declarado xfy, a liga b liga c é liga(a,liga(b,c)), enquanto com yfx seria liga(liga(a,b),c). Usa write_canonical/1 para ver a estrutura sem a escrita de operadores; as declarações devem aparecer antes dos termos que as usam.
Construir termos e executar objetivos
O operador univ, =../2, relaciona um termo com uma lista cujo primeiro elemento é o nome do functor e os restantes são argumentos:
tarefa(treino,1) =.. [tarefa,treino,1].
Termo =.. [tarefa,treino,1].A segunda unificação constrói Termo=tarefa(treino,1) sem executar a tarefa; só call(Termo) tenta provar o objetivo com esse nome e argumentos. Para construir um termo, precisamos de um nome válido conhecido e de uma lista própria, pois com as duas pontas livres =.. não enumera todos os termos.
Unificar e desmontar termos difere de produzir efeitos, como imprimir ou alterar a base de conhecimento. Uma impressão permanece no ecrã quando o motor retrocede; não é anulada como uma ligação de variável. Essa diferença explica o caráter extra-lógico de operações de entrada e saída.
Repetir por falha e ordenar por chave
Para mostrar todas as tarefas, podemos enumerar uma, imprimir e usar fail para pedir a seguinte. Quando acabam, uma segunda cláusula garante sucesso:
imprimir_tarefas(F) :-
tarefa(Nome, _),
call(F, Nome, Texto),
writeln(Texto),
fail.
imprimir_tarefas(_).Este ciclo dirigido pela falha pressupõe uma enumeração finita e que F termina. Uma tarefa para a qual F falhe é saltada, e se F tiver várias soluções haverá várias impressões. A ordem segue a enumeração de tarefa/2, não uma ordenação automática. A cláusula final não faz outra impressão.
Se o objetivo é ordenar, recolhe primeiro pares Chave-Valor. keysort/2 ordena pela chave, conserva pares repetidos e conserva a ordem original entre chaves iguais. sort/2 também compara o valor e elimina duplicados, por isso trocar um pelo outro pode mudar a resposta.
:- op(600, xfy, liga).
tarefa(leitura, 2).
tarefa(treino, 1).
tarefa(revisao, 2).
mostrar_rotulo(Nome, Texto) :- atom_concat('tarefa:', Nome, Texto).
imprimir_tarefas(F) :-
tarefa(Nome, _),
call(F, Nome, Texto),
write_portatil(Texto),
fail.
imprimir_tarefas(_).
write_portatil(X) :- write(X), nl.
main :-
write_canonical(a liga b liga c), nl,
Termo =.. [tarefa, treino, 1],
write_canonical(Termo), nl,
findall(P-N, tarefa(N,P), Pares),
keysort(Pares, Ordenados),
write_portatil(Ordenados),
imprimir_tarefas(mostrar_rotulo).Executa o código para ver a saída e os gráficos.
Indexação depende do motor
Modelo clássico e indexação JIT
Ao chamar estado(ativo,X), um índice pode excluir cláusulas cuja cabeça começa por outro átomo. No modelo clássico do primeiro argumento, estado(ativo,X) oferece essa informação na cabeça; estado(E,X) :- E=ativo,... não a oferece diretamente. A indexação poupa tentativas de cláusulas, mas não muda as respostas lógicas nem ordena resultados.
O modelo clássico do primeiro argumento não descreve todas as versões de Prolog. O SWI tem indexação JIT que pode escolher vários argumentos e reconhecer certas unificações no início do corpo. Numa questão sobre eficiência, identifica motor, versão e modo da chamada.
Exercícios
Repetições, grupos e ausência de respostas
Usa estes factos na ordem escrita:
inscrito(ana,pfl).
inscrito(ana,lbaw).
inscrito(bruno,pfl).
inscrito(ana,pfl).Calcula todas as respostas de bagof(C,inscrito(A,C),Cs) e compara com bagof(C,A^inscrito(A,C),Cs) e setof(C,A^inscrito(A,C),Cs). O que acontece se substituíres o objetivo por inscrito(carla,C) em findall, bagof e setof?
Pista
Solução
A não aparece no template e não está quantificada. Há dois grupos: A=ana, Cs=[pfl,lbaw,pfl] e A=bruno, Cs=[pfl].
Com A^, há uma só lista: [pfl,lbaw,pfl,pfl], na ordem das provas. setof ordena e elimina repetições: [lbaw,pfl].
Carla não tem inscrições. findall(C,inscrito(carla,C),Cs) sucede com Cs=[]; bagof e setof falham. Uma regra que precise de continuar com uma lista vazia deve escolher esse contrato.
Confere a tua resposta:
- Calculo cada grupo com repetições.
- Uso A^ para recolher num só grupo.
- Distingo lista vazia de falha sem respostas.
Erros frequentes
Ler a associatividade declarada
Depois de op(550,xfy,une), que estrutura tem p une q une r?
Pista
x exige prioridade menor; y permite igual.
Solução
A estrutura é une(p,une(q,r)). Com xfx, a cadeia sem
parênteses seria recusada.
une(p,une(q,r)). xfy permite um operador da mesma prioridade no argumento direito.une(une(p,q),r). Esta associação corresponde a yfx.- A declaração executa une/2 três vezes.. op/3 define como se lê o termo, não executa a operação.
Erros frequentes
A prioridade numérica decide a ligação entre operadores diferentes; x/y decide o encadeamento à mesma prioridade.
Construir não significa executar
O que resulta de G =.. [soma,4,7,R], antes de qualquer
call?
Pista
Não há avaliação aritmética no operador univ.
Solução
G=soma(4,7,R). Para calcular uma soma teria de existir
uma definição adequada de soma/3 e ser executado call(G).
G=soma(4,7,R), com R ainda livre.. A lista define o functor e os argumentos do termo.R=11, sem precisar de outra chamada.. =.. não chama o predicado soma.- G é sempre a lista
[soma,4,7,R].. O lado esquerdo fica ligado a um termo composto.
Erros frequentes
Um termo pode representar um objetivo sem ter sido provado.
Conservar a ordem dos empates
Calcula keysort([3-z,1-b,3-a,3-z],L). Depois indica a
diferença se se usasse sort/2.
Pista
keysort é estável e não elimina pares.
Solução
keysort dá [1-b,3-z,3-a,3-z].
sort dá
[1-b,3-a,3-z], comparando termos completos e retirando o
par repetido.
Confere a tua resposta:
- Ordeno por chave, não pelo valor.
- Conservo as duas ocorrências de 3-z.
- Mantenho z antes de a no empate de chave 3.
Erros frequentes
Inverter uma lista ordenada para obter ordem decrescente também inverte a ordem dos empates.
Retroceder sem apagar o ecrã
Há três factos item/1. O predicado mostrar tem uma cláusula
item(X),writeln(X),fail e outra cláusula
vazia. Quantas linhas imprime numa chamada, e por que termina com sucesso?
Pista
Os efeitos de writeln não são ligações de variáveis.
Solução
Imprime três linhas. fail faz retroceder para item; quando já não há factos, a segunda cláusula sucede. O texto impresso permanece.
Confere a tua resposta:
- Cada solução provoca uma impressão.
- fail força a procura da alternativa seguinte.
- A cláusula final dá sucesso e não apaga impressões.
Erros frequentes
Sem a cláusula final, a enumeração ainda imprime, mas a chamada termina em falha.
Separar respostas e eficiência
Duas definições equivalentes têm estado(ativo,X) na cabeça
ou estado(E,X)
seguido de E=ativo no corpo. É correto afirmar que a
primeira é sempre mais rápida em qualquer Prolog?
Pista
Um modelo de indexação não é uma regra de todos os motores.
Solução
Não. No modelo clássico do primeiro argumento, a cabeça instanciada oferece informação ao índice. Motores modernos podem transformar a segunda forma. A comparação exige motor, versão, dados e modo da chamada; não se deduz um tempo universal.
Confere a tua resposta:
- A indexação pode excluir cabeças incompatíveis.
- As respostas não devem mudar.
- Identifico versão, argumento conhecido e possíveis otimizações do corpo.
Erros frequentes
Não confundas o functor que identifica o predicado com o índice que seleciona as suas cláusulas.
Traduzir a gramática e seguir o consumo
Traduz para predicados com entrada e resto a DCG:
s --> [a], s, [b].
s --> [].Segue o consumo para [a,a,b,b] e [a,b,a,b], exigindo resto vazio. Ter dois a e dois b é suficiente para aceitar?
Pista
Solução
A tradução é:
s([a|R1],S) :- s(R1,R2), R2 = [b|S].
s(S,S).Na primeira lista, retiramos dois a. A alternativa vazia deixa [b,b]; no regresso, retiramos um b em cada chamada, chegando ao resto [].
Na segunda, retirar o primeiro a deixa [b,a,b]. A recursão não pode retirar outro a; a alternativa vazia conserva esse resto. Retiramos o b final da regra exterior, mas ainda sobra [a,b], que não unifica com []. Falha o consumo completo. A gramática exige todos os a antes dos b, além de igual quantidade.
Confere a tua resposta:
- Traduzo a regra recursiva e a alternativa vazia.
- Aceito [a,a,b,b] com resto vazio.
- Localizo a falha em [a,b,a,b].
Erros frequentes
Unir duas caudas abertas
Com juntar_dl(A-B,B-C,A-C), junta [m,n|T]-T e [p,q|U]-U. Que variável
fecha a lista do resultado? As duas caudas começam livres e distintas.
Pista
O segundo argumento exige a mesma cauda B usada no primeiro.
Solução
O resultado é [m,n,p,q|U]-U. Ligar U=[] fecha-o como [m,n,p,q]-[]. O
prefixo da primeira lista não precisa de ser copiado.
Confere a tua resposta:
- Ligo T a [p,q|U].
- Obtenho [m,n,p,q|U]-U.
- Fecho a lista ligando U a [].
Erros frequentes
Ligar T a [] antes de juntar impede acrescentar o segundo
segmento. Não reutilizes U como a própria lista completa.