# Recolher soluções e compor estruturas em Prolog

findall, bagof, setof, variáveis livres, diferenças de listas, DCG e predicados de ordem superior.

Página: https://resumos.rgo.pt/cadeiras/pfl/solucoes-estruturas-prolog/

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.

**main.pl**

```prolog
:- 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) ).
```

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

![Duas diferenças de listas, [a,b|T]-T e [c|U]-U, têm caudas abertas T e U. A ligação T=[c|U] dá [a,b,c|U]-U sem copiar o prefixo. U=[] fecha a cauda e dá [a,b,c]-[].](https://resumos.rgo.pt/cadeiras/pfl/solucoes-estruturas-prolog/figura-1.svg)

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](https://resumos.rgo.pt/cadeiras/pfl/solucoes-estruturas-prolog/#da-dcg-%C3%A0-cl%C3%A1usula-traduzida). 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.

**main.pl**

```prolog
:- 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).
```

## 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

Separa o que o template guarda das variáveis que criam grupos.

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

Uma prova repetida continua na lista de bagof; setof remove valores repetidos, não cria uma lista vazia em caso de falha.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/solucoes-estruturas-prolog/#quando-aparece-um-grupo-por-pessoa)

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.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/solucoes-estruturas-prolog/#operadores-mudam-a-escrita-do-termo)

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.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/solucoes-estruturas-prolog/#construir-termos-e-executar-objetivos)

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.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/solucoes-estruturas-prolog/#repetir-por-falha-e-ordenar-por-chave)

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.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/solucoes-estruturas-prolog/#repetir-por-falha-e-ordenar-por-chave)

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.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/solucoes-estruturas-prolog/#indexa%C3%A7%C3%A3o-depende-do-motor)

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

Os dois argumentos adicionais conservam os restos entre componentes da regra.

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

Contagens iguais não impõem a ordem dos tokens.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/solucoes-estruturas-prolog/#da-dcg-%C3%A0-cl%C3%A1usula-traduzida)

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.

[Voltar à explicação](https://resumos.rgo.pt/cadeiras/pfl/solucoes-estruturas-prolog/#listas-abertas-e-diferen%C3%A7as-de-listas)