Programação Lógica (Prolog, Datalog)

Visão geral

Programação lógica (logic programming) é um paradigma de IA simbólica (symbolic AI) em que você representa conhecimento como fatos (facts) e regras (rules), e a computação consiste em derivar consequências lógicas a partir desse conhecimento. Em vez de descrever como calcular uma resposta passo a passo (como na programação imperativa), você declara o que é verdadeiro, e o sistema de execução busca provas.

Duas das linguagens de programação lógica mais importantes são:

Prolog: uma linguagem de programação lógica de propósito geral com um modelo de execução de cima para baixo (top-down), orientado a objetivos (busca em profundidade (depth-first search) com retrocesso (backtracking)), estrutura rica de termos (incluindo símbolos de função (function symbols)) e recursos práticos como corte (cut), negação por falha (negation as failure) e programação lógica com restrições (constraint logic programming).
Datalog: um subconjunto restrito, orientado a bancos de dados, da programação lógica, projetado para raciocínio eficiente e com terminação garantida sobre relações finitas. Ele tipicamente usa avaliação de baixo para cima (bottom-up) (encadeamento para frente (forward chaining)) e é amplamente utilizado em bancos de dados dedutivos (deductive databases) e em análise de programas (program analysis).

A programação lógica se insere em Lógica e está intimamente relacionada à representação de conhecimento baseada em regras (veja Regras, Ontologias, Grafos de Conhecimento). Ela também se conecta a paradigmas de aprendizado como Programação Lógica Indutiva, que aprende regras a partir de exemplos.

Ideias centrais: fatos, regras, consultas

Fatos

Um fato afirma que uma relação vale:

parent(alice, bob).
parent(bob, carol).

Isso pode ser lido como: “Alice é mãe/pai de Bob” e “Bob é mãe/pai de Carol”.

Regras

Uma regra define uma relação em termos de outras relações:

grandparent(X, Z) :- parent(X, Y), parent(Y, Z).

Leia como: “X é avô/avó de Z se existe um Y tal que X é mãe/pai de Y e Y é mãe/pai de Z.”

Consultas

Uma consulta (query) pergunta o que pode ser derivado:

?- grandparent(alice, Who).

Um sistema de programação lógica tenta encontrar substituições para variáveis (aqui Who) que façam a consulta ser logicamente implicada pelos fatos e regras.

Fundamento teórico (em resumo)

Cláusulas de Horn e lógica de primeira ordem

A maior parte da programação lógica se baseia em cláusulas de Horn (Horn clauses), um fragmento da lógica de primeira ordem (first-order logic, FOL) que permite busca de provas eficiente.

Uma regra no estilo Prolog:

head :- body1, body2, ..., bodyn.

corresponde aproximadamente à fórmula de FOL:

∀x (body1 ∧ body2 ∧ ... ∧ bodyn → head)

Essa restrição é importante: a prova de teoremas em FOL geral é poderosa, mas cara e frequentemente indecidível; cláusulas de Horn produzem raciocínio prático.

Para um aprofundamento, veja Lógica.

Unificação

Unificação (unification) é o processo de tornar dois termos lógicos iguais, encontrando uma substituição para variáveis.

Exemplo:

Unificar parent(alice, X) com parent(alice, bob) fornece a substituição {X = bob}.
Unificar parent(X, X) com parent(alice, bob) falha (exigiria alice = bob).

A unificação é central para como Prolog e muitos motores de Datalog casam regras com fatos.

Resolução e busca de provas

Sistemas de programação lógica tipicamente usam resolução (resolution), uma regra de inferência para derivar consequências. A execução de Prolog é comumente descrita como resolução SLD (SLD-resolution) (Selective Linear Definite clause resolution):

Orientada a objetivos: parte da consulta (um objetivo) e a reduz usando regras/fatos.
Seletiva: escolhe uma submeta por vez (normalmente da esquerda para a direita).
Linear: mantém uma única cadeia de metas (em vez de explorar explicitamente árvores completas de prova).

Motores de Datalog com mais frequência usam encadeamento para frente (avaliação de baixo para cima), aplicando regras repetidamente para derivar todas as consequências até alcançar um ponto fixo.

Prolog na prática

Modelo de execução: top-down + retrocesso

Prolog responde a consultas tentando prová-las usando:

Redução de metas: substitui uma meta pelo corpo de uma regra compatível.
Unificação: associa variáveis para que metas casem com fatos/cabeças de regras.
Retrocesso: se uma escolha falha mais adiante, tenta fatos/regras alternativos.

Isso é poderoso, mas a ordem exata de avaliação importa para desempenho e até para terminação.

Exemplo: ancestral com recursão

parent(alice, bob).
parent(bob, carol).
parent(carol, dave).

ancestor(X, Z) :- parent(X, Z).
ancestor(X, Z) :- parent(X, Y), ancestor(Y, Z).

Consulta:

?- ancestor(alice, Who).

Prolog produzirá Who = bob e, ao retroceder, Who = carol, depois Who = dave.

Estruturas de dados: termos e listas

Prolog tem termos simbólicos ricos (árvores), úteis para IA simbólica e processamento de linguagem. Listas são especialmente comuns:

member(X, [X|_]).
member(X, [_|T]) :- member(X, T).

Consulta:

?- member(X, [a,b,c]).

Produz X = a; X = b; X = c.

Negação por falha

Prolog tipicamente implementa negação como negação por falha:

not_parent(X, Y) :- \+ parent(X, Y).

Interpretação: \+ Goal tem sucesso se Prolog falhar em provar Goal. Isso não é negação lógica clássica; depende do que é conhecido/provável (uma hipótese do mundo fechado (closed-world assumption)).

Isso pode ser muito útil em sistemas de regras ao estilo de IA, mas exige cuidado: se as variáveis não estiverem suficientemente instanciadas, os resultados podem ser contraintuitivos.

Controle: corte e leitura procedural

Prolog permite controle explícito da busca usando o operador de corte !, que “fixa” as escolhas feitas até aquele ponto:

max(A, B, A) :- A >= B, !.
max(_, B, B).

Cortes podem melhorar desempenho e impor determinismo, mas também tornam os programas menos puramente declarativos (mais “procedurais”).

Programação Lógica com Restrições (CLP)

Uma grande extensão prática é a programação lógica com restrições, como clpfd (domínios finitos), que integra resolução de restrições com busca lógica:

% Example in SWI-Prolog with clpfd:
% :- use_module(library(clpfd)).

solve([A,B,C]) :-
  [A,B,C] ins 1..9,
  A + B #= C,
  all_different([A,B,C]).

Isso faz a ponte entre programação lógica e busca/otimização combinatória.

Datalog na prática

O que torna Datalog diferente?

Datalog é projetado para raciocínio tipo banco de dados:

Tipicamente sem símbolos de função (sem aninhamento arbitrário de termos como f(g(X))), o que ajuda a garantir terminação.
Programas definem relações (tabelas) usando regras.
A avaliação costuma ser de baixo para cima, computando o fecho de todos os fatos deriváveis.

Isso torna Datalog especialmente atraente para bancos de dados dedutivos e análise estática (static analysis).

Um exemplo em Datalog: fecho transitivo

Fatos:

edge(alice, bob).
edge(bob, carol).
edge(carol, dave).

Regras:

path(X, Y) :- edge(X, Y).
path(X, Z) :- edge(X, Y), path(Y, Z).

Consulta:

?- path(alice, Z).

Um motor de Datalog tipicamente computará todos os fatos path/2 implicados por essas regras, alcançando um ponto fixo.

Avaliação bottom-up e pontos fixos

Um modelo mental comum para a execução de Datalog:

Comece com fatos do banco de dados extensional (banco de dados extensional (extensional database, EDB)): fatos base como edge/2.
Aplique regras para derivar fatos do banco de dados intensional (banco de dados intensional (intensional database, IDB)): relações derivadas como path/2.
Repita até que nenhum fato novo seja produzido (um menor ponto fixo (least fixed point)).

Isso está intimamente relacionado à aplicação de regras de inferência em sistemas de encadeamento para frente e pode ser implementado eficientemente usando junções relacionais e indexação.

Segurança (restrição de alcance)

Muitos sistemas de Datalog exigem regras seguras (safety): toda variável na cabeça (e frequentemente em submetas negadas) deve aparecer em um literal positivo no corpo. Isso evita regras que implicitamente variam sobre um domínio infinito.

Exemplo inseguro (tipicamente rejeitado):

p(X) :- not q(X).

porque X não tem um “gerador” positivo como r(X) para restringi-lo.

Negação: negação estratificada

Datalog frequentemente suporta negação estratificada (stratified negation), em que a negação é permitida apenas se não criar dependências cíclicas via negação. Isso preserva uma semântica bem definida e permite avaliação previsível.

Padrões comuns

Consultas como extração de relações

A programação lógica brilha quando você quer fazer consultas relacionais complexas sem escrever código explícito de travessia.

Exemplo (Prolog): encontrar todos os avós/avós:

?- grandparent(G, C).

Isso é análogo a uma consulta relacional (como SQL), mas com recursão e variáveis lógicas.

Recursão (especialmente problemas em grafos)

Recursão é a forma idiomática de expressar alcançabilidade, ancestralidade, fecho de dependências e fluxo de dados.

No entanto, a recursão interage fortemente com a estratégia de avaliação:

Em Prolog, regras com recursão à esquerda podem entrar em loop sob busca em profundidade.
Em Datalog, a recursão é natural e tipicamente tem terminação garantida sob as restrições padrão.

Junções e regras multi-relação

Regras frequentemente se comportam como junções de banco de dados:

works_on(alice, proj1).
works_on(bob, proj1).
manages(eve, proj1).

reports_to(Person, Manager) :-
  works_on(Person, Project),
  manages(Manager, Project).

Consulta:

?- reports_to(P, M).

Agregação (variantes de Datalog)

Muitos motores modernos de Datalog adicionam agregados (count, min, max). Exemplo (a sintaxe varia por motor):

Contar quantos funcionários trabalham em cada projeto
Computar caminhos mais curtos (com semianéis (semirings) especializados ou recursão + agregação)

Agregados empurram Datalog em direção a analytics e análise de programas, mas complicam semântica e avaliação (motores tipicamente definem regras bem delimitadas para monotonicidade e estratificação).

Semântica: significado declarativo vs comportamento operacional

Uma distinção-chave na programação lógica:

Semântica declarativa (declarative semantics): o significado do programa como um conjunto de consequências lógicas (modelos).
Semântica operacional (operational semantics): como o motor de fato encontra respostas (ordem de busca, indexação, memoização).

Prolog é famosamente “declarativo em espírito”, mas detalhes operacionais (ordenação de metas, corte, indexação) podem importar muito. Datalog é mais próximo de um subconjunto puramente declarativo, com um modelo de execução projetado para preservar terminação e significado previsível.

Desempenho e estratégias de avaliação

Prolog: busca em profundidade e seus trade-offs

A estratégia padrão de Prolog é eficiente em memória e frequentemente rápida, mas pode:

Ficar presa em ramos infinitos (não terminação)
Ser sensível à ordenação de regras e metas
Repetir trabalho em consultas recursivas (a menos que use tabulação)

Tabulação (memoização)

Muitos sistemas Prolog suportam tabulação (tabling) (resolução SLG (SLG resolution)), que memoiza submetas para evitar computação repetida e pode garantir terminação para algumas classes de programas.

Isso torna Prolog mais parecido com Datalog para consultas recursivas e é particularmente útil para parsing, alcançabilidade e programação dinâmica.

Datalog: otimização bottom-up

Motores de Datalog usam técnicas de bancos de dados:

Avaliação semi-ingênua (semi-naive evaluation): evita recomputar junções do zero a cada iteração, focando nos fatos recém-derivados (o “delta”).
Indexação e ordenação de junções (join ordering): cruciais para escalar.
Conjuntos mágicos (magic sets): uma transformação que torna a avaliação bottom-up mais orientada a objetivos (especialmente quando você só precisa de respostas relevantes para uma consulta).

Essas técnicas explicam por que Datalog é eficaz para análise em larga escala e inferência em bases de conhecimento.

Onde a programação lógica é usada

Bases de conhecimento e raciocínio baseado em regras

A programação lógica representa naturalmente conhecimento estruturado e regras:

Bases de regras no estilo de sistemas especialistas
Raciocínio sobre políticas (“este acesso é permitido?”)
Integração de dados e lógica de vinculação de entidades (frequentemente combinada com outras técnicas)

Em sistemas modernos, a programação lógica frequentemente complementa representações baseadas em grafos; veja Regras, Ontologias, Grafos de Conhecimento. Para raciocínio centrado em ontologias com fragmentos decidíveis de lógica de primeira ordem, veja Lógicas de Descrição.

Bancos de dados dedutivos

Datalog se originou na comunidade de bancos de dados como uma forma de adicionar recursão e inferência a bancos de dados relacionais:

Definir relações derivadas (views) via regras
Computar fecho transitivo, alcançabilidade, proveniência
Expressar restrições e fatos derivados de forma declarativa

Isso é útil quando você quer a conveniência da inferência lógica com a escalabilidade da execução de banco de dados.

Análise de programas (análise estática) e compiladores

Um grande sucesso moderno de Datalog é a análise estática:

Análise de apontamento (points-to analysis)
Rastreamento de contaminação (taint tracking)
Construção de grafo de chamadas (call graph)
Análise de fluxo de dados (dataflow analysis)
Auditorias de segurança e detecção de vulnerabilidades

Nesses domínios, programas são convertidos em fatos (por exemplo, calls(f,g), assign(x,y)) e regras de análise são escritas em Datalog. Motores como Soufflé (amplamente usado em pesquisa e na indústria) compilam Datalog para C++ de alto desempenho.

Por que funciona bem:

Análises são naturalmente expressas como relações + recursão até ponto fixo.
A avaliação bottom-up computa o fecho de forma eficiente.
O conjunto de regras é auditável e mais fácil de modificar do que código de análise artesanal.

Proveniência de dados e explicação

Como resultados são derivados por regras, frequentemente é possível rastrear por que um fato foi derivado (sua prova ou grafo de derivação). Isso dá suporte a:

Explicações para conclusões inferidas
Depuração de conjuntos de regras
Proveniência em pipelines de dados

(As capacidades exatas dependem do motor; alguns fornecem recursos explícitos de proveniência.)

Orientações práticas e armadilhas comuns

Dicas para Prolog

Ordene metas para falhar cedo: coloque submetas mais restritivas antes.
Tenha atenção à não terminação com recursão sob busca em profundidade.
Use tabulação quando disponível para consultas recursivas que, de outra forma, repetem trabalho.
Use corte com parcimônia; prefira relações puras a menos que você precise de controle/desempenho.

Dicas para Datalog

Garanta que regras sejam seguras (com restrição de alcance) e respeitem as restrições do motor.
Observe recursão + negação: prefira projetos estratificados.
Modele dados para se ajustar a junções relacionais: um bom desenho de predicados pode melhorar drasticamente o desempenho.
Ao escalar, apoie-se nas ferramentas do motor (perfiladores (profilers), dicas de ordenação de junções, índices se houver suporte).

Programação lógica vs outros paradigmas de IA

A programação lógica é um pilar da IA simbólica clássica: ela fornece estrutura explícita e inferência, ao contrário de muitas abordagens estatísticas. Em sistemas modernos de IA, ela frequentemente aparece como um componente:

Um modelo neural propõe candidatos; regras lógicas os validam ou restringem.
Regras codificam restrições de domínio que são difíceis de aprender a partir de dados.
Camadas baseadas em lógica dão suporte à interpretabilidade e conformidade.

Para aprender regras a partir de dados, veja Programação Lógica Indutiva. Para fundamentos mais amplos de raciocínio simbólico, veja Lógica.

Resumo

Programação lógica representa conhecimento como fatos e regras e responde perguntas via inferência lógica.
Unificação casa metas com fatos/regras; resolução conduz a busca de provas.
Prolog é uma linguagem lógica geral e expressiva, com execução top-down, retrocesso e recursos práticos de controle.
Datalog é uma forma restrita, orientada a banco de dados, projetada para terminação e avaliação bottom-up eficiente, amplamente usada em bancos de dados dedutivos e em análise de programas.
Padrões comuns incluem consultas relacionais, recursão (alcançabilidade) e regras no estilo de junção; o desempenho depende fortemente da estratégia de avaliação e de restrições (tabulação, avaliação semi-ingênua, negação estratificada).

A programação lógica continua sendo uma ferramenta prática para construir sistemas em que conhecimento estruturado, recursão e inferência explicável importam.