Skip to content
LumenaryAcademy
Foundations 50 min

First steps in Prolog

What logic programming is, how Prolog came out of Marseille and Edinburgh, and a first program of facts, rules and queries.

Code tested · 3AI-draftedAwaiting review by a computer scientist
MotivationH

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:

prolog
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.

prolog
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.

History & global context

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.

DefinitionsH

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:

KindExamplesRule
Atomlima, amara, 'São Paulo', []Starts with a lower-case letter, or is quoted
Number42, -7, 3.14As in other languages
VariableX, Who, City, _, _CountStarts with an upper-case letter or an underscore
Compound termcapital(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.

ComputationC

Installing SWI-Prolog and a first program

Getting Prolog

  • Windows and macOS: download the installer from swi-prolog.org. On macOS, brew install swi-prolog also works.
  • Linux: install your distribution's swi-prolog package (for example sudo 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:

prolog
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):

text
?- 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 grandparent rule 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 false after 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) is false: 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.

prolog
:- initialization(main, main).

main :-
    format("Hello from Prolog!~n").
text
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:

prolog
:- 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])).
text
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

prolog
:- 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])).
text
amara is a grandparent of emeka
amara is a grandparent of ada
obi is a grandparent of emeka
obi is a grandparent of ada

Two 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 misconceptionsH

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

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-upHuman

Which of these are Prolog variables? List them separated by commas.

City, lima, _Count, 'Lima', X, peru, _

Write elements separated by commas. Order and repeats don’t matter — just like in a set!

2. First steps in Prolog

Warm-upHuman

Which of these is a rule?

Choose one

3. First steps in Prolog

Warm-upComputational

With the lesson's speaks/2 facts, what does this goal print?

forall(speaks(peru, L), format("~w ", [L]))

4. First steps in Prolog

Warm-upComputational

With the lesson's capital/2 facts, what does the query ?- capital(X, lima). bind X to?

5. First steps in Prolog

CoreComputational

Using the lesson's family program, which values does grandparent(G, emeka) give for G? List them separated by commas.

Write elements separated by commas. Order and repeats don’t matter — just like in a set!

6. First steps in Prolog

CoreComputational

How many solutions does the query parent(P, C) have in the lesson's family program?

7. First steps in Prolog

CoreHuman

What was the key insight, associated with Robert Kowalski, that made Prolog possible?

Choose one

Further reading and resources