Prolog

Prolog (Programming in Logic) is a logic programming language created in 1972 that fundamentally changed how we think about computation. Instead of telling the computer how to solve a problem step by step, you describe what the problem is, and Prolog figures out the solution.

History & Origins

Prolog was born from the intersection of computer science and linguistics. In 1972, Alain Colmerauer at the University of Aix-Marseille in France was working on natural language processing when he collaborated with logician Philippe Roussel and, later, with Robert Kowalski from Edinburgh. Their insight was revolutionary: formal logic could serve as a programming language.

The name “Prolog” was coined by Philippe Roussel as an abbreviation for “PROgrammation en LOGique” (French for “programming in logic”).

The Edinburgh Connection

While Prolog was born in Marseille, much of its development happened at the University of Edinburgh. David H.D. Warren created the first Prolog compiler and developed the Warren Abstract Machine (WAM), which became the standard for efficient Prolog implementation. Edinburgh Prolog syntax became the de facto standard and eventually the basis for ISO Prolog.

The Fifth Generation Project

Prolog gained enormous attention in the 1980s when Japan announced its Fifth Generation Computer Systems (FGCS) project, which aimed to create revolutionary AI systems using logic programming. While the project didn’t achieve all its ambitious goals, it spurred worldwide interest in Prolog and AI research.

Core Concepts

Facts and Rules

Prolog programs consist of facts (things that are true) and rules (relationships between facts):

1
2
3
4
5
6
7
8
9

% Facts
parent(tom, bob).
parent(tom, liz).
parent(bob, ann).
parent(bob, pat).

% Rules
grandparent(X, Z) :- parent(X, Y), parent(Y, Z).
sibling(X, Y) :- parent(Z, X), parent(Z, Y), X \= Y.

Queries

You interact with Prolog by asking queries:

1
2
3
4
5
6
7
8
9

?- parent(tom, bob).
true.

?- grandparent(tom, ann).
true.

?- grandparent(tom, Who).
Who = ann ;
Who = pat.

Unification

Prolog’s power comes from unification - the process of making two terms identical by finding appropriate variable bindings:

1
2
3

?- foo(X, bar) = foo(baz, Y).
X = baz,
Y = bar.

Backtracking

When Prolog encounters a choice point, it can backtrack to try alternative solutions:

1
2
3
4
5
6
7
8

color(red).
color(green).
color(blue).

?- color(X).
X = red ;
X = green ;
X = blue.

Key Features

Declarative Programming

Prolog is declarative - you describe the problem, not the algorithm:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

% Append definition - describes what append means
append([], L, L).
append([H|T], L, [H|R]) :- append(T, L, R).

% Prolog can run this "backwards"
?- append([1,2], [3,4], Result).
Result = [1, 2, 3, 4].

?- append(X, [3,4], [1,2,3,4]).
X = [1, 2].

?- append(X, Y, [1,2,3]).
X = [], Y = [1, 2, 3] ;
X = [1], Y = [2, 3] ;
X = [1, 2], Y = [3] ;
X = [1, 2, 3], Y = [].

Pattern Matching

Prolog excels at pattern matching on structured data:

1
2
3
4
5
6

% Match and destructure lists
first([H|_], H).
rest([_|T], T).

% Match nested structures
extract_name(person(Name, _, _), Name).

Built-in Search

Prolog has built-in depth-first search with backtracking:

1
2
3

% Graph traversal - Prolog handles the search
path(X, Y) :- edge(X, Y).
path(X, Y) :- edge(X, Z), path(Z, Y).

Constraint Logic Programming

Modern Prolog systems support constraint solving:

1
2
3
4
5
6

:- use_module(library(clpfd)).

% Solve the equation: X + Y = 10, X > Y, X < 8
?- X + Y #= 10, X #> Y, X #< 8, X #> 0, Y #> 0.
X = 6, Y = 4 ;
X = 7, Y = 3.

Modern Implementations

SWI-Prolog

The most popular open-source Prolog:

• Full-featured development environment
• Excellent documentation
• Large library ecosystem
• Web frameworks (Pengines, SWISH)
• Active development since 1987

GNU Prolog

Free Prolog with native compilation:

• Compiles to native code
• Constraint solving built-in
• Strict ISO compliance
• Good for standalone applications

SICStus Prolog

Commercial Prolog for industrial applications:

• High performance
• Excellent constraint libraries
• Used in aviation, scheduling
• Professional support

Scryer Prolog

Modern Prolog written in Rust:

• ISO-compliant
• Focus on correctness
• Modern architecture
• Growing rapidly

Other Implementations

• YAP Prolog - High-performance, Prolog-to-C compiler
• XSB Prolog - Tabling (memoization) support
• ECLiPSe - Constraint programming focus
• B-Prolog - Tabling and action rules
• Tau Prolog - Prolog in JavaScript

Prolog Syntax Overview

Terms

Everything in Prolog is a term:

• Atoms: hello, 'Hello World', foo_bar
• Numbers: 42, 3.14, -17
• Variables: X, Result, _Anonymous
• Compound Terms: foo(bar, baz), [1,2,3]

Lists

Lists are fundamental in Prolog:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

% Empty list
[]

% List with elements
[1, 2, 3]

% Head|Tail notation
[Head|Tail] = [1, 2, 3].
% Head = 1, Tail = [2, 3]

% Pattern matching
[A, B, C] = [1, 2, 3].
% A = 1, B = 2, C = 3

Operators

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

% Arithmetic (note: is/2 evaluates)
X is 3 + 4.        % X = 7
Y is 10 * 2.       % Y = 20

% Comparison
X > Y.             % Greater than
X < Y.             % Less than
X =:= Y.           % Arithmetic equality
X =\= Y.           % Arithmetic inequality

% Unification
X = Y.             % Unify X and Y
X \= Y.            % X and Y don't unify

Control Flow

1
2
3
4
5
6
7
8
9

% If-then-else
(Condition -> Then ; Else)

% Negation as failure
\+ Goal            % Succeeds if Goal fails

% Cut (commit to current choice)
member(X, [X|_]) :- !.
member(X, [_|T]) :- member(X, T).

Classic Prolog Problems

Family Relationships

1
2

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

List Operations

1
2
3
4
5
6
7
8

length([], 0).
length([_|T], N) :- length(T, N1), N is N1 + 1.

reverse([], []).
reverse([H|T], R) :- reverse(T, RT), append(RT, [H], R).

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

Sorting

1
2
3
4
5
6
7
8

% Naive sort (permutation sort)
naive_sort(List, Sorted) :-
    permutation(List, Sorted),
    sorted(Sorted).

sorted([]).
sorted([_]).
sorted([A,B|T]) :- A =< B, sorted([B|T]).

Why Prolog Still Matters

Unique Problem-Solving Approach

Prolog forces you to think differently:

• Describe relationships, not procedures
• Let the computer search for solutions
• Handle multiple solutions naturally

AI and Knowledge Representation

Prolog remains valuable for:

• Expert systems
• Semantic web and ontologies
• Natural language processing
• Automated reasoning

Educational Value

Understanding Prolog helps you:

• Think about problems declaratively
• Understand pattern matching (used in ML, Haskell, Rust)
• Learn about search and backtracking
• Appreciate different programming paradigms

Modern Applications

• Type inference engines - Many type checkers use Prolog-like unification
• Database queries - SQL and Datalog share Prolog’s roots
• Configuration management - Complex constraint satisfaction
• Scheduling systems - Airlines, universities, factories

Learning Resources

Online

• SWI-Prolog Documentation - Comprehensive reference
• Learn Prolog Now! - Free online textbook
• SWISH - Browser-based Prolog environment
• The Power of Prolog - YouTube series by Markus Triska

Books

• The Art of Prolog by Sterling and Shapiro
• Programming in Prolog by Clocksin and Mellish
• Prolog Programming for Artificial Intelligence by Bratko

The Prolog Community

• SWI-Prolog Forum - Active discussion board
• comp.lang.prolog - Usenet newsgroup
• Prolog Association - Annual conferences
• Stack Overflow - Active prolog tag

Prolog’s Legacy

Prolog’s influence extends far beyond logic programming:

• Erlang was first implemented in Prolog
• Datalog is a subset of Prolog used in databases
• Pattern matching in modern languages follows Prolog’s lead
• Unification is used in type inference
• Constraint programming grew from Prolog extensions

Whether you use Prolog directly or not, understanding it will change how you think about programming. It’s a window into a fundamentally different way of computing - one where you describe the world and let the computer figure out the rest.