Introduction
Prolog is a logic programming language based on first-order logic. Rather than specifying how to solve a problem (imperative), Prolog programs specify what the problem is (declarative). The Prolog system automatically searches for solutions using unification and backtracking. This article explores Prolog fundamentals and practical programming.
Historical Context
Prolog was developed by Alain Colmerauer and Robert Kowalski in the 1970s. It became popular in AI research and is still used for knowledge representation, expert systems, and logic programming. Modern Prolog systems like SWI-Prolog are powerful and widely used.
Prolog Basics
Facts
Definition: Basic assertions about the world
Example:
parent(tom, bob).
parent(tom, liz).
parent(bob, ann).
parent(bob, pat).
parent(pat, jim).
Rules
Definition: Conditional statements
Example:
grandparent(X, Z) :- parent(X, Y), parent(Y, Z).
ancestor(X, Y) :- parent(X, Y).
ancestor(X, Y) :- parent(X, Z), ancestor(Z, Y).
Queries
Definition: Questions about the knowledge base
Example:
?- parent(tom, X).
X = bob ;
X = liz.
?- grandparent(tom, X).
X = ann ;
X = pat ;
X = jim.
Unification
Definition
Unification: Finding substitution making two terms equal
Example:
Unify parent(tom, X) with parent(tom, bob)
Substitution: X = bob
Unification Algorithm
Process:
- If terms are identical, succeed
- If one is variable, bind it to other
- If both are compound, unify arguments
- Otherwise, fail
Backtracking
Definition
Backtracking: Systematic search for solutions
Process:
- Try first clause
- If fails, try next clause
- If all fail, backtrack to previous choice point
Example:
?- parent(X, Y).
X = tom, Y = bob ; (first solution)
X = tom, Y = liz ; (backtrack, try next)
X = bob, Y = ann ; (backtrack, try next)
...
Lists
List Syntax
Empty List: [] Non-empty List: [Head|Tail]
Example:
[1, 2, 3] = [1|[2, 3]] = [1|[2|[3|[]]]]
List Operations
Member:
member(X, [X|_]).
member(X, [_|T]) :- member(X, T).
Append:
append([], L, L).
append([H|T1], L2, [H|T3]) :- append(T1, L2, T3).
Length:
length([], 0).
length([_|T], N) :- length(T, N1), N is N1 + 1.
Arithmetic
Arithmetic Evaluation
is: Evaluate arithmetic expression
Example:
?- X is 2 + 3.
X = 5.
?- X is 2 * 3 + 4.
X = 10.
Comparison
Operators: <, >, =<, >=, =:=, ==
Example:
?- 5 > 3.
true.
?- X = 5, X > 3.
X = 5.
Practical Example: Family Relations
Knowledge Base
% Facts
parent(tom, bob).
parent(tom, liz).
parent(bob, ann).
parent(bob, pat).
parent(pat, jim).
% Rules
grandparent(X, Z) :- parent(X, Y), parent(Y, Z).
ancestor(X, Y) :- parent(X, Y).
ancestor(X, Y) :- parent(X, Z), ancestor(Z, Y).
sibling(X, Y) :- parent(Z, X), parent(Z, Y), X \= Y.
Queries
?- grandparent(tom, X).
X = ann ;
X = pat ;
X = jim.
?- ancestor(tom, X).
X = bob ;
X = liz ;
X = ann ;
X = pat ;
X = jim.
?- sibling(X, Y).
X = bob, Y = liz ;
X = liz, Y = bob ;
X = ann, Y = pat ;
X = pat, Y = ann.
Cut and Negation
Cut (!)
Purpose: Prevent backtracking
Example:
max(X, Y, X) :- X >= Y, !.
max(X, Y, Y).
Negation (+)
Purpose: Negation as failure
Example:
not_parent(X, Y) :- \+ parent(X, Y).
Glossary
Atom: Basic constant (e.g., tom, bob) Backtracking: Systematic search for solutions Clause: Fact or rule Compound Term: Structure with functor and arguments Cut: Prevent backtracking Fact: Basic assertion Predicate: Relation or property Query: Question about knowledge base Rule: Conditional statement Unification: Finding substitution making terms equal Variable: Unknown to be bound
Practice Problems
Problem 1: Write Prolog rules for “uncle” relationship.
Solution:
uncle(X, Y) :- parent(Z, Y), sibling(X, Z).
Problem 2: Write Prolog predicate to find all members of a list.
Solution:
member(X, [X|_]).
member(X, [_|T]) :- member(X, T).
Problem 3: Write Prolog predicate to reverse a list.
Solution:
reverse([], []).
reverse([H|T], R) :- reverse(T, RT), append(RT, [H], R).
Related Resources
- Prolog: https://en.wikipedia.org/wiki/Prolog
- SWI-Prolog: https://www.swi-prolog.org/
- Logic Programming: https://en.wikipedia.org/wiki/Logic_programming
- Unification: https://en.wikipedia.org/wiki/Unification_(computer_science)
- Backtracking: https://en.wikipedia.org/wiki/Backtracking
- First-Order Logic: https://plato.stanford.edu/entries/logic-firstorder/
- Declarative Programming: https://en.wikipedia.org/wiki/Declarative_programming
- Automated Reasoning: https://en.wikipedia.org/wiki/Automated_reasoning
- Knowledge Representation: https://en.wikipedia.org/wiki/Knowledge_representation_and_reasoning
- Expert Systems: https://en.wikipedia.org/wiki/Expert_system
- Datalog: https://en.wikipedia.org/wiki/Datalog
- Constraint Logic Programming: https://en.wikipedia.org/wiki/Constraint_logic_programming
- Formal Methods: https://plato.stanford.edu/entries/formal-methods/
- Programming Languages: https://en.wikipedia.org/wiki/Programming_language
- Artificial Intelligence: https://en.wikipedia.org/wiki/Artificial_intelligence
Conclusion
Prolog provides a powerful declarative approach to programming based on logic. By specifying what the problem is rather than how to solve it, Prolog enables concise, elegant solutions to logic problems.
Understanding Prolog is valuable for anyone working with logic programming, knowledge representation, or AI systems. The combination of unification, backtracking, and logical inference makes Prolog a unique and powerful programming paradigm.
Comments