Programação Lógica

O backtracking é o mecanismo fundamental que torna o Prolog uma linguagem
de busca e resolução de problemas. Quando uma consulta é feita, o Prolog tenta satisfazer os objetivos
na ordem em que aparecem. Se um objetivo falha, ele volta atrás (backtrack) e tenta
outra alternativa, até encontrar todas as soluções possíveis. Vamos entender esse processo com um exemplo
clássico: a geração de números binários de 3 bits.

O Programa 3.1 — Números Binários

O predicado d/1 define os dois dígitos binários possíveis. A regra b/1
afirma que uma lista de três elementos [A, B, C] é um número binário se A,
B e C forem todos dígitos binários.

Objetivo da Consulta: ?- b(N).

Ao executar ?- b(N)., o Prolog deve gerar todas as combinações possíveis
de 3 bits: [0,0,0], [0,0,1], [0,1,0], e assim por diante, até
[1,1,1] — totalizando 8 soluções.

A Árvore de Busca Passo a Passo

O Prolog constrói uma árvore de busca onde cada nó representa um objetivo a ser provado.
Acompanhe a execução abaixo:

Resolução e Redução de Objetivos

O Prolog utiliza um mecanismo chamado resolução SLD (Selected Linear Definite).
A resolução é o processo de unificar a consulta com a cabeça de uma regra e substituir
a consulta pelo corpo da regra. A redução ocorre quando um objetivo é substituído por
subobjetivos (ex: b(N) é reduzido a d(A), d(B), d(C)). A árvore acima mostra
exatamente essa cadeia de reduções e tentativas de unificação.

Ordem das Cláusulas e Objetivos

A ordem dos fatos e das metas no corpo das regras afeta diretamente
a forma da árvore de busca. Por exemplo, se definíssemos d(1). d(0). (invertendo a ordem),
a primeira solução seria [1,1,1] em vez de [0,0,0]. A ordem dos objetivos
também importa: d(C), d(B), d(A) geraria a mesma lista de soluções, mas em ordem diferente.

Exercício Proposto

Modifique a ordem dos objetivos na regra b/1 para:

Perguntas:
1. Qual será a primeira solução gerada?
2. Como a árvore de busca se altera?
3. O número total de soluções (8) continua o mesmo?
4. O que acontece se mudarmos a ordem dos fatos d(0). d(1). para d(1). d(0).?

Teste no seu interpretador Prolog e observe o comportamento. Essa prática ajuda a internalizar
como o backtracking e a ordem influenciam a execução.

✅ Conclusão

O backtracking é o motor que impulsiona a busca em Prolog.
Ele é automático e controlado pelo motor de inferência — o programador não precisa
gerenciar pilhas ou loops manualmente. Entender a árvore de busca é essencial para:

• Prever a ordem das soluções;
• Escrever regras eficientes (colocando metas restritivas primeiro);
• Controlar o fluxo com corte (!) quando necessário;
• Depurar programas que não terminam ou que geram soluções inesperadas.

Dominar o backtracking é dar um grande passo para se tornar um programador Prolog confiante e produtivo.

Diferente das linguagens imperativas, o Prolog não possui laços for ou while — sua execução é guiada por busca e backtracking. O mecanismo de inferência do Prolog explora todas as possibilidades para satisfazer uma consulta, voltando atrás (backtracking) quando um caminho falha. Isso torna a linguagem extremamente poderosa para problemas de busca, mas também exige que o programador entenda e controle esse fluxo para evitar ineficiências ou loops infinitos.

O Backtracking em Ação

O backtracking é o coração do Prolog. Quando uma meta falha, o sistema volta ao ponto de escolha mais recente (um predicado com múltiplas cláusulas ou soluções) e tenta a próxima alternativa. Por exemplo, ao consultar ?- pai(X, Y)., o Prolog tenta a primeira cláusula de pai/2; se ela falha, ele volta e testa a próxima, e assim por diante, até encontrar todas as soluções ou esgotar as possibilidades. Esse comportamento é o que permite respostas como X = joao, Y = maria ; X = joao, Y = jose ; .... O backtracking é automático e transparente, mas pode ser custoso em bases grandes. É aí que entram os mecanismos de otimização.

O Operador de Corte (!)

O operador de corte, escrito como !, é uma ferramenta de controle de fluxo que descarta pontos de escolha anteriores à sua posição na regra. Quando o Prolog encontra um !, ele se compromete com as escolhas feitas até aquele momento — ou seja, não faz mais backtracking para as metas anteriores ao corte. Nesse exemplo, se um filme for anterior a 1980, o corte impede que o Prolog tente outras cláusulas da regra ou outras alternativas para filme/4. O uso correto do corte otimiza a execução e evita buscas desnecessárias. No entanto, ele deve ser usado com cuidado, pois pode alterar a semântica do programa, eliminando soluções que seriam encontradas sem ele.

Falhas (fail) para Iteração

O predicado fail/0 força a falha imediata da meta atual, provocando backtracking. Combinado com efeitos colaterais (como write/1), ele permite iterar sobre todas as soluções de uma consulta, algo que em linguagens imperativas seria um laço. O fail força o backtracking para a próxima solução de filme/4, imprimindo cada título. Quando não há mais soluções, a primeira cláusula falha e a segunda cláusula (vazia) é executada, encerrando o processo. Esse padrão é conhecido como “falha para iterar” e é uma técnica clássica em Prolog para processar todos os resultados de uma consulta. O uso de fail com ! e not pode criar construções extremamente poderosas, como filtragem com negação e geração de todas as combinações possíveis. Dominar esses três elementos — backtracking, corte e falha — é essencial para escrever programas Prolog eficientes e expressivos.

---

💡 Em resumo: O controle de fluxo em Prolog é guiado por backtracking. O corte (!) otimiza e limita a busca, enquanto fail permite iterar sobre soluções. Juntos, esses recursos dão ao programador o poder de controlar a execução sem abrir mão da natureza declarativa da linguagem.