3 min read
On this page

Logic Programming

Logic programming expresses computation as logical statements. The programmer declares what is true — the runtime figures out how to derive answers. The dominant logic programming language is Prolog.

Prolog Basics

Facts

Declare basic truths about the world.

parent(tom, bob).        % Tom is a parent of Bob
parent(tom, liz).        % Tom is a parent of Liz
parent(bob, ann).        % Bob is a parent of Ann
parent(bob, pat).        % Bob is a parent of Pat

male(tom).
male(bob).
female(liz).
female(ann).
female(pat).

Rules

Define logical relationships using implication (if).

% X is a father of Y if X is a parent of Y and X is male
father(X, Y) :- parent(X, Y), male(X).

% X is a mother of Y if X is a parent of Y and X is female
mother(X, Y) :- parent(X, Y), female(X).

% X is a grandparent of Z if X is a parent of Y and Y is a parent of Z
grandparent(X, Z) :- parent(X, Y), parent(Y, Z).

% X is a sibling of Y if they share a parent and are different
sibling(X, Y) :- parent(Z, X), parent(Z, Y), X \= Y.

% X is an ancestor of Y
ancestor(X, Y) :- parent(X, Y).
ancestor(X, Y) :- parent(X, Z), ancestor(Z, Y).

Queries

Ask questions about what's true.

?- parent(tom, bob).          % Is Tom a parent of Bob?
% yes

?- parent(tom, X).            % Who are Tom's children?
% X = bob ; X = liz

?- grandparent(tom, X).       % Who are Tom's grandchildren?
% X = ann ; X = pat

?- ancestor(tom, ann).        % Is Tom an ancestor of Ann?
% yes

?- sibling(ann, X).           % Who are Ann's siblings?
% X = pat

Unification

Unification is the process of making two terms identical by finding a substitution for variables.

f(X, b) = f(a, Y)      % X = a, Y = b
f(X, X) = f(a, a)      % X = a
f(X, X) = f(a, b)      % FAILS (X can't be both a and b)
f(X, g(X)) = f(a, Y)   % X = a, Y = g(a)

Most General Unifier (MGU): The simplest substitution that unifies two terms. Found by Robinson's unification algorithm.

Occurs check: X = f(X) should fail (infinite term). Most Prolog implementations skip the occurs check for efficiency (can lead to infinite terms if not careful).

Prolog's execution model: depth-first search with backtracking.

  1. Try to satisfy the first goal.
  2. If a match is found, proceed to the next goal.
  3. If no match is found, backtrack to the previous choice point and try the next alternative.
path(X, Y) :- edge(X, Y).
path(X, Y) :- edge(X, Z), path(Z, Y).

% For query path(a, d):
% Try edge(a, d) — fails
% Try edge(a, Z), path(Z, d):
%   edge(a, b) succeeds, Z = b
%   Now try path(b, d):
%     edge(b, d) — succeeds!
% Answer: yes, via a→b→d

Search Tree

path(a, d)
├── edge(a, d)  → FAIL
└── edge(a, Z), path(Z, d)
    ├── Z=b: path(b, d)
    │   ├── edge(b, d) → SUCCESS
    │   └── edge(b, W), path(W, d) → ...
    └── Z=c: path(c, d) → ...

Cut Operator (!)

Cut prunes the search tree — commits to current choices, preventing backtracking past the cut.

max(X, Y, X) :- X >= Y, !.
max(X, Y, Y).

Without cut: max(5, 3, X) might try both clauses. With cut: once X >= Y succeeds, the second clause is never tried.

Green cut: Doesn't change the logical meaning (just improves efficiency). Red cut: Changes the meaning (removes valid solutions). Generally avoided.

Negation as Failure

Prolog uses closed-world assumption: anything not provable is assumed false.

not_parent(X, Y) :- \+ parent(X, Y).
% \+ means "not provable"

?- \+ parent(tom, ann).    % Can we prove parent(tom, ann)? No → true

+ is not logical negation — it's "failure to prove." This has subtle semantic issues (floundering with unbound variables).

Logic Variables

Variables in logic programming are fundamentally different from imperative variables:

  • Single assignment: Once bound, a variable keeps its value forever (no mutation).
  • Bidirectional: A variable can be input or output depending on the query.
append([], L, L).
append([H|T], L, [H|R]) :- append(T, L, R).

?- append([1,2], [3,4], X).     % X = [1,2,3,4] (compute result)
?- append(X, [3,4], [1,2,3,4]). % X = [1,2]     (compute input!)
?- append(X, Y, [1,2,3]).       % generates all splits:
                                 % X=[], Y=[1,2,3]
                                 % X=[1], Y=[2,3]
                                 % X=[1,2], Y=[3]
                                 % X=[1,2,3], Y=[]

This multi-directional nature is a key advantage of logic programming.

Constraint Logic Programming (CLP)

Extend logic programming with constraint solvers for specific domains.

CLP(FD) — Finite Domains

Integer constraint satisfaction:

:- use_module(library(clpfd)).

sudoku(Rows) :-
    length(Rows, 9),
    maplist(length_(9), Rows),
    append(Rows, Vs), Vs ins 1..9,
    maplist(all_distinct, Rows),
    transpose(Rows, Cols),
    maplist(all_distinct, Cols),
    blocks(Rows),
    maplist(label, Rows).

CLP(R) — Reals

Constraints over real numbers:

?- { X + Y = 10, X - Y = 2 }.
% X = 6.0, Y = 4.0

Datalog

A restricted subset of Prolog:

  • No function symbols (only constants and variables).
  • No negation (in pure Datalog).
  • Guaranteed termination (finite domains).

Applications: Database query languages, program analysis, security policy specification.

% Facts
edge(a, b).
edge(b, c).
edge(c, d).

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

% Query
?- path(a, X).
% X = b, c, d

Used in: Soufflé (high-performance Datalog for program analysis), Datomic (database), LogiQL.

Answer Set Programming (ASP)

A declarative paradigm for combinatorial search and optimization. Define the problem — the ASP solver finds solutions.

% Graph coloring
color(1..3).                        % 3 colors
1 { assign(V, C) : color(C) } 1 :- vertex(V).  % each vertex gets exactly 1 color
:- edge(U, V), assign(U, C), assign(V, C).      % adjacent vertices can't share colors

Solvers: Clingo, DLV. Based on SAT/constraint solving internally.

Applications: Planning, scheduling, configuration, knowledge representation, combinatorial optimization.

Logic Programming in Practice

Strengths

  • Declarative: Describe the problem, not the solution procedure.
  • Pattern matching: Unification is powerful for symbolic computation.
  • Search built-in: Backtracking explores alternatives automatically.
  • Multi-directional: Same predicate can be used for different queries.
  • Natural for rule-based systems: Business rules, expert systems, regulations.

Weaknesses

  • Control: Programmer must think about Prolog's search strategy (depth-first, left-to-right). Inefficient for some problems.
  • Negation: Negation as failure has semantic issues.
  • Side effects: I/O and mutable state don't fit the logical model well.
  • Performance: Overhead from unification, backtracking, and dynamic clause lookup.
  • Scalability: Pure Prolog doesn't scale well to large systems (but CLP and Datalog variants do).

Applications in CS

  • AI and expert systems: Knowledge representation, rule-based reasoning, theorem proving.
  • Natural language processing: Definite clause grammars (DCGs) for parsing.
  • Database queries: Datalog is a query language. SQL can be viewed as a form of logic programming.
  • Program analysis: Points-to analysis, taint analysis implemented in Datalog (Soufflé, Doop).
  • Type checking: Type inference as logic programming (Hindley-Milner via unification).
  • Planning: AI planning (STRIPS-like planners use logic).
  • Verification: Model checking, property verification.
  • Semantic web: OWL reasoning, SPARQL queries on RDF graphs.