Prolog is a computer programming language that is used for solving problems that involve objects, and the relationships between objects.
Programming in Prolog consists of:
- Specifying some facts about objects and their relationships
- Defining some rules about objects and their relationships
- Asking questions about objects and their relationships
How it Works
Prolog performs a task in response to a question from the programmer. A question provides a conjunction of goals to be satisfied. Prolog uses the known clauses to satisfy the goals. A fact can cause a goal to be satisfied immediately, whereas a rule can only reduce the task to that of satisfying a conjunction of subgoals. However, a clause can only be used if it unifies the goal under consideration. If a goal can’t be satisfied, backtracking will be initiated. Backtracking consists of reviewing what has been done, attempting to re-satisfy the goals by finding an alternative way to satisfy them.
- Variables must begin with an upper-case letter
- Comments are written as
% ...or as
/** ... */
Two different types:
- Atoms made of letters and digits (e.g:
- They must begin with a lower-case letter in its name (e.g:
- They must begin with a lower-case letter in its name (e.g:
- Atoms made of symbols (e.g:
If an atom is enclosed in single quotes, then it may contain any characters
- Exponential notation is allowed
- The must begin with an upper-case letter or an underscore
Use an underscore as an anonymous variable (like Haskell):
?- likes(_, john).
It saves from having to invent names for variables that are going to be unused anyway.
Structures (compound terms)
A structure is a single object consisting of a collection of other objects, called components.
owns(john, book(ulysses, author(james, joyce)))
Here the structures are:
[ foo, X, [ bar, baz ] ]
Head & Tail
X is the head, and
Y is the tail.
p([1, 2, 3]). ?- p([X|Y]). X = 1 Y = [2, 3]
p([ mary, likes, wine ]). ?- p([X,Y|Z]). X = mary Y = likes Z = [wine]
To check if an element is inside the list, we must check if its the head of the list, and if not, check if its the head of the tail, and so on.
member(X, [X|_]). member(X, [_|Y]) :- member(X, Y).
The first fact says that
X is a member of the array if the array has
its head. The second fact says that
X is a member of the tail of the array
Y), if the tail’s head is
?- member(2, [1, 2, 3]). yes
Mapping is performed by declaring facts that transform certain elements into other elements, and then having a fact that transforms all elements of the list by applying itself recursively to the tail of the list.
change(yes, no). change(no, yes). change(X, X).
The last line does nothing to atoms other than
alter(, ). alter([H|T], [X|Y]) :- change(H, X), alter(T, Y).
?- alter([ yes, yes, no, foo ], X) X = [ no, no, yes, foo ]
/** Concatenating  and `list` results in `list` */ append(, L, L). append([X|List1], List2, [X|List3]) :- append(List1, List2, List3).
In this implementation, we take each element from
List1 in turn, and make it
the head of the third argument. At some point, the third list, will contain all
the elements of
List1 at its head and
List1 will be empty, so the base
class applies, saying that the remaining of the third list (what is not the
List2, effectively performing the concatenation.
?- append([1, 2, 3], [4, 5, 6], Result). Result = [1, 2, 3, 4, 5, 6] /** First pass */ X = 1 List1 = [ 2, 3 ] List2 = [ 4, 5, 6 ] List3 = [ 2, 3 ] Result = [ 1, <unknown> ] /** Second pass */ X = 2 List1 = [ 3 ] List2 = [ 4, 5, 6 ] List3 = [ 3 ] Result = [ 1, 2, <unknown> ] /** Third pass */ X = 3 List1 =  List2 = [ 4, 5, 6 ] List3 =  Result = [ 1, 2, 3, <unknown> ] /** Fourth pass */ L = [ 4, 5, 6 ] Result = [ 1, 2, 3, 4, 5, 6 ]
?- append(X, [4, 5, 6], [1, 2, 3, 4, 5, 6]). X = [1, 2, 3]
listlength(, 0). listlength([X|S], Length) :- listlength(S, L), Length is L + 1.
Define extra utility predicates that handle an accumulator.
- Reducer-based definition of
listlength(List, Length) :- listlength_acc(List, 0, Length). listlength_acc(, Accumulator, Accumulator). listlength_acc([Head|Tail], Accumulator, Length) :- Total is Accumulator + 1, listlength_acc(Tail, Total, Length).
- Can be instantiated or non-instantiated:
likes(john, mary). ?- likes(john, X)
X variable is non-instantiated. Prolog finds that
X = mary. At this point the variable is instantiated.
?- [goal1], [goal2], [goal3].
- Prolog attemps to satify each goal in turn (first
?- [goal1]; [goal2]; [goal3].
- Try to avoid colons by defining extra clauses
Rules are general statements about objects and their relationships. They consist of a “head” and a “body”, separated by
:- (pronounced “if”)
- Rules are used when you want to say that a fact depends on a group of other facts
likes(john, X) :- likes(X, wine).
johnlikes any female that likes
likes(john, X) :- female(X), likes(X, wine).
- A list containing the atom
- A list containing the atoms
- If two objects are equal, we say that they
- If one of the two sides of an equal predicate contains a variable, then Prolog attempts to unify both objects:
?- rides(student, bycicle) = rides(student, X). X = bycicle
== (strict equal)
= predicate considers an uninstantiated variable to equal to anything,
== only considers uninstantiated variable to equal other uninstantiated
variables already sharing with it.
Check if two numbers are equal.
5 =:= 5.
Check if two numbers are different.
5 =/= 8.
Evaluate an arithmetic expression.
- Its right-hand argument is a term which is interpreted as an arithmetic expression
- The answer is unified with the left-hand argument to determine whether the goal succeeds
- All the values of the variables on the right side must be known
population(usa, 203). area(usa, 3). density(Country, Density) :- population(Country, Population), area(Country, Area), Density = Population / Area. ?- density(usa, X). X = 67.666666667
- We can use
isto save a temporary variable:
sum(A, B, Result) :- Total is A + B, Result is Total.
Treats its argument as a goal and attempt to satisfy it.
\+X succeeds only when the goal
This could be implemented like this:
\+P :- call(P), !, fail. \+P.
var(X) succeeds if
X is an uninstantiated variable:
?- var(X). yes ?- var(25). no
nonvar(X) succeeds if
X is an instantiated variable.
- This is the opposite of
var. It could be defined as:
nonvar(X) :- var(X), !, fail. nonvar(_).
atom(X) succeeds if
X is an atom.
number(X) succeeds if
X is an atom.
atomic(X) succeeds if
X is ether an atom or a number.
A goal without arguments that always succeeds.
A goal without arguments that always fails. It’s usually used to force backtracing to take place.
- Typicall used along with
average_tax_payer(Person) :- foreigner(Person), !, fail.
Person is a foreigner, then
foreigner(Person) succeeds, causing Prolog
to proceed on the same fact and “cross the cut fence”.
fail always fails, and
since we had a “cut” right before, Prolog can’t backtrace anywhere, and will
cause the entire
average_tax_payer fact to fail.
Person is not a foreigner,
foreigner(Person) will fail, so Prolog will
continue with the next definition of
average_tax_payer instead of “crossing
the cut fence”.
Write a string to the screen.
write("Foo bar baz").
- Any uninstantiated variable is written as an underscore followed by its
unique id number (e.g:
Read the next term you type in from the computer keyboard.
read(X). /** X is instantiated to the user's input */
Force all succeeding output to appear on the next line.
Read a character from the user.
If the argument passed to it is not instantiated, the goal succeeds and the variable gets assigned
If the argument passed to it is instantiated,
get_charcompares the character for equality
Write a character to the screen.
Open a file.
open("path/to/file", read, X). open("path/to/file", write, X).
X is instantiated to a term naming a stream.
Close a stream.
main :- open("path/to/file", read, X), do_something_with_file(X), close(X).
Set a stream as the current input stream.
- All read-related functions will operate on the default input stream
open("path/to/file", read, X), set_input(X).
Set a stream as the current output stream.
- All write-related functions will operate on the default output stream
open("path/to/file", write, X), set_output(X).
Get a reference to the current input stream.
- This is useful to revert the current input stream after modifying it:
main :- open("path/to/file", read, X), current_input(Stream), set_input(X), do_something_with_file(X), close(X), set_input(Stream).
Get a reference to the current output stream.
- This is useful to revert the current output stream after modifying it:
main :- open("path/to/file", write, X), current_output(Stream), set_output(X), do_something_with_file(X), close(X), set_output(Stream).
Import the clauses of another file into the current session.
You can use the following syntax sugar if you need to consult multiple files:
Print a declared clause definition to the screen:
likes(foo, bar). listing(likes).
Get information about a structure.
person("Juan Cruz", "Viotti", 21). ?- functor(person, Functor, Arity) Functor = person Arity = 3
Access the nth element of a structure:
?- arg(2, person("Juan Cruz", "Viotti", 21), Value) Value = "Viotti"
Get a list of the functor plus all the arguments to it.
foo(a, b, c) =.. X. X = [foo, a, b, c]
Get a list of an atom’s characters.
atom_chars(hello, X). X = [h, e, l, l, o]
Get a list of an number’s characters.
number_chars(16.1, X). X = ['1', '6', '.', '1']
Declare an operator.
op(X, Y, Z) declares an operator having precedence class
Y, and name
- The goal will only succeed if the operation declaration is legal
Valid associativity values:
The “cut” is a goal that allows you to tell Prolog which previous choices it need not consider again when it backtracks through the chain of satisfied goals.
When a cut is encountered as a goal, the system thereupon becomes committed to all choices made since the parent goal was invoked. All other alternatives are discarded. Hence an attempt to re-satisfy any goal between the parent goal and the cut goal fill fail.
The “cut” is represented with an exclamation sign (
- This makes programs faster and more memory efficient, since Prolog will not waste time attempting to satisfy goals that you can tell beforehand will never contribute to a solution
/** This program checks if a person has access to certain library facilities */ facility(Person, Facility) :- book_overdue(Person, Book), !, basic_facility(Facility). facility(Person, Facility) :- general_facility(Facility). basic_facility(reference). basic_facility(enquiries). additional_facility(borrowing). additional_facility(inter_library_loan). general_facility(Facility) :- basic_facility(Facility). general_facility(Facility) :- additional_facility(Facility). /** Program data */ client("A. Jones"). client("W. Metesk"). book_overdue("A. Jones", book29907).
We can then ask what facilities are open to a specific client by querying:
?- facility("A. Jones", X)
Without the “cut”, the first
facility clause will fail because “A. Jones” has
an overdue book, so Prolog will try the next fact, which only checks if
general_facility(Facility), which will be fulfilled, and thus the program
will report that “A. Jones” has access to any facility.
By putting the “cut” after
book_overdue(Person, Book), we tell Prolog that
we’re only interested on if
Person has any book overdue, not all of them, so
if the goal fails, Prolog will not try to find every overdue book in vain. It
also tells Prolog that it should stop considering any other fact after it,
facility to correctly report “no” if the person has any overdue book.
If a client is found to have an overdue book, then only allow the client to access the basic facilities of the library. Don’t bother going through all the client’s overdue books, and don’t consider any other rule about facilities.
This is done by preppending ordering predicates with
- Uninstantiated variables < floating-point numbers < integers < atoms < structures
- For two uninstantiated variables, this is implementation dependent
- Atoms are compared alphabetically
- One structure is less than another if its functor has a lower arity
- If they both have the same arity, then the ordering is based on the functor name
- If they both have the same arity and functor, they are ordered based on their arguments (for the first correspondent arguments that differ)
g(X) @< f(X, Y). g(Z, b) @< f(a, A). 123.5 @< 2
Enable tracing with
trace. and disable with
Spying is like tracing, but it applies to certain predicates you pick:
You can remove to spy with
Rules of Thumbs
- Declare facts before rules to avoid potential infinite left recursion
- It is a good practice to replace cuts with
\+, unless doing so imposes a too big performance hit