Introduction
Logic programming represents a fundamentally different approach to computation compared to imperative or functional programming. Rather than specifying how to solve a problem through explicit instructions, logic programming allows you to specify what the problem is, and let the system figure out how to solve it through logical inference.
In this article, we’ll explore the foundations of logic programming, understand how it differs from other programming paradigms, and see why it’s particularly powerful for certain classes of problems.
What is Logic Programming?
Logic programming is a programming paradigm based on formal logic. A logic program consists of:
- Facts: Statements that are unconditionally true
- Rules: Conditional statements that define relationships
- Queries: Questions we ask the system to answer
The system uses logical inference (typically resolution and unification) to derive answers from facts and rules.
Key Characteristics
Declarative Nature: You declare what is true, not how to compute it.
% Facts
parent(tom, bob).
parent(bob, ann).
parent(bob, pat).
% Rules
grandparent(X, Z) :- parent(X, Y), parent(Y, Z).
% Query
?- grandparent(tom, ann).
% Answer: yes
Logical Inference: The system automatically derives conclusions from facts and rules.
Backtracking: When a solution path fails, the system automatically tries alternative paths.
Unification: Pattern matching mechanism that binds variables to values.
Logic Programming vs. Other Paradigms
Imperative Programming
Imperative: Specify step-by-step instructions
# Python (imperative)
def find_grandparent(person, target):
for parent in get_parents(person):
for grandparent in get_parents(parent):
if grandparent == target:
return True
return False
Logic Programming: Specify relationships
% Prolog (declarative)
grandparent(X, Z) :- parent(X, Y), parent(Y, Z).
Functional Programming
Functional: Compute values through function composition
-- Haskell (functional)
grandparent x z = any (\y -> parent x y && parent y z) allPeople
Logic Programming: Query logical relationships
% Prolog (logical)
?- grandparent(tom, ann).
Key Differences
| Aspect | Imperative | Functional | Logic |
|---|---|---|---|
| Focus | How to compute | Function composition | What is true |
| Control | Explicit | Implicit (recursion) | Implicit (inference) |
| State | Mutable | Immutable | Logical facts |
| Backtracking | Manual | Not typical | Automatic |
| Queries | Compute values | Evaluate functions | Prove statements |
Core Concepts
Facts
Facts are the base knowledge in a logic program. They state unconditional truths.
% Simple facts
likes(mary, wine).
likes(john, mary).
likes(john, wine).
% Facts with multiple arguments
parent(tom, bob).
parent(bob, ann).
age(tom, 65).
age(bob, 40).
Rules
Rules define relationships and conditional truths. A rule has a head (conclusion) and a body (conditions).
% Rule: X is a parent 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).
% Rule: X is a sibling of Y if they share a parent
sibling(X, Y) :- parent(P, X), parent(P, Y), X \= Y.
% Rule: X is an ancestor of Y if X is a parent of Y
ancestor(X, Y) :- parent(X, Y).
% Rule: X is an ancestor of Y if X is a parent of Z and Z is an ancestor of Y
ancestor(X, Y) :- parent(X, Z), ancestor(Z, Y).
Queries
Queries ask the system to find values that satisfy certain conditions.
% Simple query: Is tom a parent of bob?
?- parent(tom, bob).
% Answer: yes
% Query with variables: Who is a parent of bob?
?- parent(X, bob).
% Answer: X = tom
% Complex query: Who is a grandparent of ann?
?- grandparent(X, ann).
% Answer: X = tom
% Query with multiple solutions
?- likes(john, X).
% Answer: X = mary ;
% X = wine
How Logic Programming Works
Unification
Unification is the process of making two terms identical by finding appropriate variable bindings.
% Unification examples
parent(tom, bob) unifies with parent(X, Y)
→ X = tom, Y = bob
parent(tom, bob) unifies with parent(tom, Z)
→ Z = bob
parent(tom, bob) does NOT unify with parent(X, X)
→ No solution (tom ≠ bob)
Resolution and Backtracking
The system uses resolution to derive new facts from existing facts and rules. When a path fails, it backtracks and tries alternatives.
% Facts
parent(tom, bob).
parent(bob, ann).
% Rule
grandparent(X, Z) :- parent(X, Y), parent(Y, Z).
% Query: ?- grandparent(tom, ann).
% Resolution process:
% 1. Try to prove grandparent(tom, ann)
% 2. Use rule: need parent(tom, Y) and parent(Y, ann)
% 3. Find parent(tom, bob) → Y = bob
% 4. Find parent(bob, ann) → Success!
% Answer: yes
Backtracking Example
% Facts
likes(mary, wine).
likes(john, mary).
likes(john, wine).
% Query: ?- likes(john, X).
% Backtracking process:
% 1. Try first fact: likes(mary, wine) - doesn't match
% 2. Try second fact: likes(john, mary) - matches! X = mary
% 3. User asks for more solutions (;)
% 4. Backtrack and try next fact: likes(john, wine) - matches! X = wine
% 5. No more facts - done
Advantages of Logic Programming
1. Declarative Clarity
Express problems naturally as logical relationships rather than procedural steps.
% Clear and concise
ancestor(X, Y) :- parent(X, Y).
ancestor(X, Y) :- parent(X, Z), ancestor(Z, Y).
2. Automatic Backtracking
The system automatically explores alternative solutions without explicit code.
% Find all solutions automatically
?- parent(X, Y).
% Returns all parent-child pairs
3. Separation of Logic and Control
The same program can be used for different purposes without modification.
% Same rule, different queries
grandparent(X, Z) :- parent(X, Y), parent(Y, Z).
?- grandparent(tom, ann). % Who is grandparent of ann?
?- grandparent(tom, X). % Who are tom's grandchildren?
?- grandparent(X, ann). % Who is ann's grandparent?
4. Rapid Prototyping
Quickly express complex relationships and test them.
% Easy to add new facts and rules
?- assert(parent(ann, bob)). % Add new fact
?- retract(parent(tom, bob)). % Remove fact
Disadvantages and Limitations
1. Performance
Logic programming can be slower than imperative code due to search overhead.
% Inefficient: searches all possibilities
?- member(X, [1,2,3,4,5]), X > 3.
% Better: use built-in predicates
?- between(4, 5, X).
2. Counterintuitive Behavior
Backtracking and unification can produce unexpected results.
% Surprising: X unifies with X
?- X = X.
% Answer: yes (always true)
% Surprising: order matters
?- parent(X, bob), parent(tom, X). % May be slower
?- parent(tom, X), parent(X, bob). % May be faster
3. Limited Imperative Features
Some problems are naturally imperative and awkward in logic programming.
% Awkward: updating state
% Logic programming prefers immutable facts
% Imperative: state = state + 1
% Logic: new_state(S1, S2) :- S2 is S1 + 1
Applications of Logic Programming
1. Knowledge Representation
Store and query complex knowledge bases.
% Medical diagnosis system
symptom(patient1, fever).
symptom(patient1, cough).
disease(flu) :- symptom(X, fever), symptom(X, cough).
2. Expert Systems
Encode expert knowledge as rules.
% Legal reasoning
eligible_for_loan(Person) :-
age(Person, Age), Age >= 18,
income(Person, Income), Income >= 20000,
credit_score(Person, Score), Score >= 600.
3. Natural Language Processing
Parse and understand natural language.
% Simple grammar
sentence --> noun_phrase, verb_phrase.
noun_phrase --> article, noun.
verb_phrase --> verb, noun_phrase.
4. Constraint Solving
Find solutions satisfying multiple constraints.
% Sudoku, scheduling, resource allocation
valid_schedule(Schedule) :-
no_conflicts(Schedule),
all_resources_available(Schedule),
meets_constraints(Schedule).
5. Database Queries
Express complex queries naturally.
% Find all employees earning more than their manager
higher_paid(E1, E2) :-
salary(E1, S1),
salary(E2, S2),
S1 > S2,
manages(E2, E1).
Logic Programming Languages
Prolog
The most popular logic programming language, used in AI, databases, and expert systems.
% Prolog example
parent(tom, bob).
parent(bob, ann).
grandparent(X, Z) :- parent(X, Y), parent(Y, Z).
?- grandparent(tom, ann).
Datalog
A subset of Prolog used for databases and knowledge representation.
% Datalog example
parent(tom, bob).
parent(bob, ann).
grandparent(X, Z) :- parent(X, Y), parent(Y, Z).
?- grandparent(tom, ann).
Answer Set Programming (ASP)
Used for knowledge representation and reasoning.
% ASP example
parent(tom, bob).
parent(bob, ann).
grandparent(X, Z) :- parent(X, Y), parent(Y, Z).
#query grandparent(tom, ann).
Getting Started with Logic Programming
Basic Structure
% 1. Define facts
parent(tom, bob).
parent(bob, ann).
% 2. Define rules
grandparent(X, Z) :- parent(X, Y), parent(Y, Z).
% 3. Query the system
?- grandparent(tom, ann).
Common Patterns
Finding all solutions:
?- parent(X, Y).
Checking existence:
?- parent(tom, bob).
Conditional logic:
?- parent(X, Y), age(X, A), A > 50.
Glossary
- Fact: An unconditional statement that is true
- Rule: A conditional statement defining relationships
- Query: A question asked to the system
- Unification: Pattern matching that binds variables to values
- Backtracking: Automatic exploration of alternative solutions
- Resolution: Logical inference mechanism
- Head: The conclusion part of a rule
- Body: The conditions part of a rule
- Predicate: A relation or property (e.g., parent/2)
- Clause: A fact or rule
- Atom: A basic logical element (e.g., tom, bob)
- Variable: A placeholder that can be bound to values (e.g., X, Y)
Practice Problems
Problem 1: Family Relationships
Given the facts:
parent(tom, bob).
parent(bob, ann).
parent(bob, pat).
parent(pat, jim).
Write rules for:
grandparent(X, Y)- X is a grandparent of Yancestor(X, Y)- X is an ancestor of Ysibling(X, Y)- X and Y are siblings
Solution:
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(P, X), parent(P, Y), X \= Y.
Problem 2: Queries
Using the facts and rules from Problem 1, answer:
- Who is a grandparent of jim?
- Who are the ancestors of jim?
- Who are the siblings of ann?
Solution:
?- grandparent(X, jim).
% Answer: X = bob
?- ancestor(X, jim).
% Answer: X = bob ; X = pat ; X = tom
?- sibling(ann, X).
% Answer: X = pat
Problem 3: Logic Programming Concepts
Explain what happens when the system processes this query:
?- parent(X, bob), parent(tom, X).
Solution: The system:
- Tries to find parent(X, bob) - finds X = tom
- Then tries parent(tom, tom) - fails
- Backtracks and tries next solution for parent(X, bob) - no more solutions
- Returns: no
Problem 4: Unification
Which of the following unify? For those that do, show the bindings.
parent(tom, bob)withparent(X, Y)parent(tom, bob)withparent(tom, tom)parent(tom, bob)withparent(X, X)age(tom, 65)withage(X, Y)
Solution:
- ✓ Unifies: X = tom, Y = bob
- ✗ Does not unify (bob ≠ tom)
- ✗ Does not unify (tom ≠ bob)
- ✓ Unifies: X = tom, Y = 65
Related Resources
Online Platforms
- SWI-Prolog Official - Leading Prolog implementation
- Learn Prolog Now! - Interactive Prolog tutorial
- Prolog Tutorial - TutorialsPoint Prolog guide
- Logic Programming Course - Coursera course
- Prolog Playground - Online Prolog interpreter
Interactive Tools
- SWI-Prolog IDE - Full development environment
- SWISH - Web-based Prolog IDE
- Prolog Online Compiler - Quick testing
- Prolog Visualizer - Trace execution
- Datalog Playground - Datalog environment
Recommended Books
- “Programming in Prolog” by Clocksin & Mellish - Classic introduction
- “The Art of Prolog” by Sterling & Shapiro - Advanced techniques
- “Logic Programming: The 1st and 2nd Conferences” - Historical perspective
- “Prolog and Natural Language Analysis” by Pereira & Shieber - NLP applications
- “Constraint Logic Programming” by Jaffar & Maher - CLP overview
Academic Journals
- Journal of Logic Programming - Primary research
- Theory and Practice of Logic Programming - Current research
- ACM Transactions on Programming Languages and Systems - Language design
- Artificial Intelligence - AI applications
- Computational Linguistics - NLP applications
Software Tools
- SWI-Prolog - Most popular Prolog
- GNU Prolog - Free Prolog implementation
- XSB Prolog - Tabling support
- Ciao Prolog - Modern Prolog
- Datalog Educational System - Datalog learning
Conclusion
Logic programming offers a unique and powerful approach to computation based on formal logic. By specifying what is true rather than how to compute it, logic programming enables:
- Clearer expression of complex relationships
- Automatic exploration of solution spaces
- Rapid prototyping of knowledge-based systems
- Flexible querying of logical facts and rules
While logic programming has limitations in performance and is not suitable for all problems, it excels in knowledge representation, expert systems, constraint solving, and natural language processing.
In the next article, we’ll explore the core building blocks of logic programs: facts, rules, and queries, and learn how to construct effective logic programs.
Next Article: Facts, Rules, and Queries
Previous Article: Proof by Cases
Comments