Saying what is true
In most languages you tell the computer what to do, step by step: set this variable, loop over that list, return this value. Prolog asks you to do something different. You describe a small world by stating what is true in it, and then you ask questions. The system works out the answers by itself.
Here is the flavour. These two lines state facts:
parent(amara, chidi).
parent(chidi, emeka).This line states a rule: someone is a grandparent of a grandchild if they are a parent of some person who is a parent of that grandchild.
grandparent(G, C) :- parent(G, P), parent(P, C).Now you can ask "who is Amara a grandparent of?" or "who are Emeka's grandparents?" or "is Chidi a grandparent of anyone?", all with the same rule. Nowhere did you write a loop, a search or a function for each question. One description serves every direction of questioning, and that is the first surprise of logic programming.
Why learn it today? Not because it will replace the languages you use every day; it will not. Learn it because it changes how you think about programs. Prolog teaches you pattern matching in its most general form (unification, which you will also find at the heart of type checkers), search with automatic backtracking, programs as data, and the idea that a specification can itself be runnable. It remains a practical tool for some jobs, such as parsing, rule systems, scheduling, puzzles and configuration problems, and its descendant Datalog quietly powers code-analysis and database tools you may already use. Lesson 8 tours where Prolog and its relatives are used.
From Marseille, 1972
Prolog was born from a meeting of two research programmes in the early 1970s.
In Marseille, Alain Colmerauer and his group were building computer systems that could converse in French: read sentences, store what they said, and answer questions about them. They needed a way to write grammars and reasoning rules together. In Edinburgh, Robert Kowalski was studying automated theorem proving. Colmerauer and Kowalski visited each other and found that a restricted form of logic, Horn clauses (statements of the form "this is true if these are all true"), could be read in two ways at once: as logical statements, and as procedures that a computer could run. To prove "grandparent" you call "parent" twice. Kowalski later summed up the idea in the slogan algorithm = logic + control.
In 1972, Colmerauer and Philippe Roussel implemented the first Prolog system; the name, suggested by Roussel's wife, abbreviates PROgrammation en LOGique. The first applications were exactly the ones the group had in mind: programs that took statements and questions in French and answered them. The idea spread quickly to Edinburgh, where David H. D. Warren wrote a Prolog compiler for the DEC-10 computer in the late 1970s that made Prolog fast enough to be taken seriously, and whose syntax, the "Edinburgh" syntax, is the one everybody uses today. In 1983 Warren designed the Warren Abstract Machine, the virtual machine on which most Prolog compilers have been modelled since.
The 1980s were Prolog's busiest decade. Japan's Fifth Generation Computer Systems project (1982 to 1992) placed logic programming at the centre of a national effort to build intelligent computers, and companies around the world built expert systems in Prolog. The project's grandest goals were not met, and interest in logic programming cooled along with the wider AI boom of that era. But the language matured: it gained an ISO standard in 1995, constraint solving, tabling, modules and large libraries.
SWI-Prolog, the system this course uses, was started by Jan Wielemaker at the University of Amsterdam in 1987 and is today the most widely used free Prolog. Others include SICStus Prolog (commercial, known for its constraint solvers), GNU Prolog, XSB (a pioneer of tabling), Scryer Prolog and Trealla Prolog (newer systems that follow the ISO standard closely). Programs that stick to the standard core run on all of them; SWI-Prolog adds many libraries of its own.
Facts, rules, queries and terms
Definition— Fact
A statement that something is true, written as a name applied to arguments and ended with a full stop: capital(peru, lima). The name (capital) is the predicate; the number of arguments is its arity. Prolog writes the predicate as capital/2.
Definition— Rule
A statement that something is true if other things are true: Head :- Body. Read :- as "if" and the comma in the body as "and". grandparent(G, C) :- parent(G, P), parent(P, C). Facts and rules together are called clauses; all the clauses for one predicate form its definition.
Definition— Query
A question, typed at the ?- prompt of the interactive toplevel or written in a program: ?- capital(peru, X). Prolog answers by finding values for the variables that make the query true, or says false if it cannot.
Everything in Prolog, data and programs alike, is a term, and there are only a few kinds:
| Kind | Examples | Rule |
|---|---|---|
| Atom | lima, amara, 'São Paulo', [] | Starts with a lower-case letter, or is quoted |
| Number | 42, -7, 3.14 | As in other languages |
| Variable | X, Who, City, _, _Count | Starts with an upper-case letter or an underscore |
| Compound term | capital(peru, lima), date(2026, 11, 19) | A name and arguments in brackets |
| String | "Hello" | Double quotes; in SWI-Prolog a string object |
Note
Every clause has two readings, and fluent Prolog programmers switch between them constantly. The declarative reading says what the clause means: "G is a grandparent of C if G is a parent of P and P is a parent of C." The procedural reading says what the machine does: "to prove grandparent(G, C), first prove parent(G, P), then, with the P found, prove parent(P, C)." The declarative reading tells you whether the program is correct; the procedural reading tells you whether it terminates and how fast it is. Good Prolog code reads well both ways.
Two rules of thumb trip up newcomers. Capitalisation matters: Lima is a variable that can stand for anything, while lima is a constant. And a variable is local to its clause: the X in one rule has nothing to do with the X in another.
Installing SWI-Prolog and a first program
Getting Prolog
- Windows and macOS: download the installer from swi-prolog.org. On macOS,
brew install swi-prologalso works. - Linux: install your distribution's
swi-prologpackage (for examplesudo apt install swi-prolog). The SWI-Prolog site links to more current builds for Ubuntu. - No install: SWISH runs SWI-Prolog in the browser.
Check the installation with swipl --version. This course was tested with SWI-Prolog 10.1.
The toplevel
Prolog is often used interactively. Save these facts and rules as family.pl:
mother(amara, chidi).
mother(amara, ngozi).
mother(ngozi, ada).
mother(ifeoma, emeka).
father(obi, chidi).
father(obi, ngozi).
father(tunde, ada).
father(chidi, emeka).
parent(P, C) :- mother(P, C).
parent(P, C) :- father(P, C).
grandparent(G, C) :-
parent(G, P),
parent(P, C).Start Prolog with the file loaded, swipl family.pl, and you get the ?- prompt. Each query ends with a full stop. When there may be more answers, Prolog shows the first and waits: press ; (or the space bar) for the next, or Enter to stop. Here is a session (Prolog's answers are as SWI-Prolog 10.1 printed them):
?- grandparent(amara, Who).
Who = emeka ;
Who = ada ;
false.
?- grandparent(Who, ada).
Who = amara ;
Who = obi ;
false.
?- parent(chidi, X).
X = emeka.
?- mother(M, emeka), father(F, emeka).
M = ifeoma,
F = chidi.
?- grandparent(tunde, X).
false.
?- mother(amara, ngozi).
true.Read the answers carefully:
- The same
grandparentrule answered "whose grandparent is Amara?" and "who are Ada's grandparents?". Which arguments you leave as variables decides which question you are asking. - The final
falseafter the last;means "no more answers". It is not an error. parent(chidi, X)gave one answer and no prompt for more, because Prolog could tell no other clause could match.- A query with a comma is a conjunction: both parts must be true, with the same variable values.
grandparent(tunde, X)isfalse: Tunde has no grandchildren in this little world. Prolog only knows what you told it. This is called the closed-world assumption, and lesson 5 returns to it.- A query without variables is a yes-or-no question.
To reload a file after editing it, type make. at the prompt. To leave, type halt. or press Ctrl-D.
Prolog as a script
Every complete program in this course runs as a script. The first line, :- initialization(main, main)., is a directive: a goal run while the file loads. It tells SWI-Prolog to call main once the whole file has been loaded and then exit: with status 0 if main succeeded, 1 if it failed, and 2 if it raised an error that nothing caught. In the last two cases SWI-Prolog prints an ERROR: line saying what went wrong. Run it with swipl main.pl.
:- initialization(main, main).
main :-
format("Hello from Prolog!~n").Hello from Prolog!format/2 prints text. In its format string ~w writes the next argument and ~n writes a newline; the arguments go in a list as the second argument.
Facts, queries and forall
This program holds a few facts about countries and asks questions from main:
:- initialization(main, main).
% capital(Country, City): City is the capital of Country.
capital(kenya, nairobi).
capital(peru, lima).
capital(japan, tokyo).
capital(portugal, lisbon).
capital(brazil, brasilia).
% speaks(Country, Language): Language is widely spoken in Country.
speaks(kenya, swahili).
speaks(kenya, english).
speaks(peru, spanish).
speaks(peru, quechua).
speaks(japan, japanese).
speaks(portugal, portuguese).
speaks(brazil, portuguese).
main :-
capital(peru, City),
format("The capital of Peru is ~w.~n", [City]),
forall(speaks(Country, portuguese),
format("Portuguese is spoken in ~w.~n", [Country])),
forall(( speaks(C, Language), capital(C, Capital) ),
format("~w: ~w, capital ~w~n", [C, Language, Capital])).The capital of Peru is lima.
Portuguese is spoken in portugal.
Portuguese is spoken in brazil.
kenya: swahili, capital nairobi
kenya: english, capital nairobi
peru: spanish, capital lima
peru: quechua, capital lima
japan: japanese, capital tokyo
portugal: portuguese, capital lisbon
brazil: portuguese, capital brasilia% starts a comment. The comment above each predicate, saying what its arguments mean, is a habit worth adopting from day one: a predicate's meaning is not obvious from its name alone. main is a rule whose body is a sequence of goals. capital(peru, City) finds the one answer. forall(Condition, Action) runs Action for every way of making Condition true; it is how a Prolog script prints all answers. The last forall has a conjunction as its condition, in brackets, joining the two tables on the country, much like a join in a database. Answers appear in the order of the facts in the file.
Rules in a program
:- initialization(main, main).
% mother(Mother, Child) and father(Father, Child)
mother(amara, chidi).
mother(amara, ngozi).
mother(ngozi, ada).
mother(ifeoma, emeka).
father(obi, chidi).
father(obi, ngozi).
father(tunde, ada).
father(chidi, emeka).
% A parent is a mother or a father: two clauses, either can apply.
parent(P, C) :- mother(P, C).
parent(P, C) :- father(P, C).
% G is a grandparent of C if G is a parent of some P who is a parent of C.
grandparent(G, C) :-
parent(G, P),
parent(P, C).
main :-
forall(grandparent(G, C),
format("~w is a grandparent of ~w~n", [G, C])).amara is a grandparent of emeka
amara is a grandparent of ada
obi is a grandparent of emeka
obi is a grandparent of adaTwo clauses for parent mean "or": a parent is a mother, or a father. That is the usual way to express alternatives in Prolog. Notice that the mothers and fathers are each kept together in the file. If you interleave the clauses of two predicates, SWI-Prolog warns that "clauses of mother/2 are not together in the source-file", because scattered clauses are usually a typing mistake; the directive :- discontiguous mother/2. silences the warning when the scattering is deliberate.
Common misconceptions
Misconception
"A Prolog variable is a box I can assign to." A Prolog variable stands for some term that is not yet known. Once it is bound to a value, it keeps that value for the rest of the clause; there is no assignment and no X = X + 1. New values come from new variables, as later lessons show.
Misconception
"Prolog reasons like a person." It follows a fixed, simple strategy: try clauses from top to bottom and goals from left to right, and back up when something fails. Lesson 3 explains it exactly. Knowing the strategy is what lets you write programs that terminate and run fast.
Misconception
"false means my program is broken." false means "with what I know, this cannot be shown true". It is an ordinary answer. Errors look different: they print ERROR: with a message.
Misconception
"Names in capitals are constants, as in C." In Prolog it is the reverse: anything starting with a capital letter is a variable. Write peru, not Peru, unless you mean "any value".
Exercises
Try each question before opening the hints. Every answer about program output was checked by running the program with SWI-Prolog 10.1.
1. First steps in Prolog
Warm-upHumanWhich of these are Prolog variables? List them separated by commas.
City, lima, _Count, 'Lima', X, peru, _
2. First steps in Prolog
Warm-upHumanWhich of these is a rule?
3. First steps in Prolog
Warm-upComputationalWith the lesson's speaks/2 facts, what does this goal print?
forall(speaks(peru, L), format("~w ", [L]))
4. First steps in Prolog
Warm-upComputationalWith the lesson's capital/2 facts, what does the query ?- capital(X, lima). bind X to?
5. First steps in Prolog
CoreComputationalUsing the lesson's family program, which values does grandparent(G, emeka) give for G? List them separated by commas.
6. First steps in Prolog
CoreComputationalHow many solutions does the query parent(P, C) have in the lesson's family program?
7. First steps in Prolog
CoreHumanWhat was the key insight, associated with Robert Kowalski, that made Prolog possible?
Further reading and resources
- SWI-Prolog downloadsInstallers for Windows and macOS, and pointers to Linux packages.
- SWI-Prolog reference manualStart with the chapters on getting started and the toplevel.
- SWISHRun Prolog in the browser without installing anything.
- Prolog (Wikipedia)A well-sourced history of the language and its implementations.
- Alain Colmerauer (Wikipedia)The French computer scientist who led the creation of Prolog.
- Robert Kowalski (Wikipedia)The logician whose procedural interpretation of Horn clauses gave Prolog its foundation.