Introduction to Prolog¶

What is Prolog?¶

Prolog is a logic programming language developed in the early 1970s that is about objects and relationships between objects. It aims to be a declarative programming language, i.e. Prolog programs often just say what they will do without specifying exactly how they will do it. Prolog has a built-in backtracking search that can solve pretty much any problem (if you have enough time — naive Prolog programs can be quite slow!). Other examples of declarative languages are SQL, regular expressions, and HTML.

While Prolog has not been a commercially successful language, it does have some common applications, such as:

Grammars for natural language processing. For instance, the IBM Watson system used Prolog (among other languages) to help it answer natural language questions.
AI applications that are based on logic or knowledge. Prolog has good support for first-order predicate logic. For instance, Prolog was the main language for the Japanese Fifth Generation Computer project in the 1980s.
In-memory databases. Prolog can be used as a language for creating, and querying, complex databases inside of other languages. Often, variations of Prolog are used for this sort of application, e.g. Datomic is a database that uses the Prolog-like language datalog to write queries.
Problems that require some sort of backtracking, such as scheduling or timetabling problem from logistics, can often be nicely represented and solved in Prolog.

While Prolog can be used as a general-purpose programming language, it’s not very popular for that since its syntax and semantics is unfamiliar to most programmers, and it can be quite tricky to write efficient programs (even for some common programming problems). Furthermore, it does not have a standard implementation of objects or modules (which are important in large-scale software engineering).

Despite it’s lack of commercial success, Prolog has been an influential language that has spurred a lot of research into programming languages.

Prolog Overview¶

Much of what follows is based on the book Programming in Prolog, by Clocksin and Mellish. That’s a good book to get if you’d like to learn more Prolog.

A good way to think about Prolog is that it is about relational programming. In mathematics, a relation is set of tuples. For example, if \(A\) and \(A\) are sets, then a relation is any subset of their cross product:

\[A \times B = \{(a, b) : a \in A, b \in B \}\]

More generally, if \(A_1, A_2, \ldots, A_n\) are all non-empty sets, then a relation on them is any subset of this cross-product:

\[A_1 \times A_2 \times \ldots \times A_n = \{(a_1,a_2,\ldots,a_n) : a_1\in A_1, a_2\in A_2, \ldots, a_n \in A_n \}\]

\((a_1,a_2,\ldots,a_n)\) is an n-tuple, i.e. an ordered collection of n different values. A relation is just a set of 0 or more n-tuples

For example, suppose the set \(A=\{18,19,20\}\), and the set \(P=\{\textrm{yi}, \textrm{veronica}, \textrm{pat}, \textrm{gary}\}\). We could then define the age relation like this: \(\{(\textrm{veronica},19), (\textrm{pat},19), (\textrm{yi},18)\}\). This relation is just a set of pairs, where the first element of each pair is from \(A\), and the second element is from \(P\). Another relation would be \(\{(\textrm{yi},19), (\textrm{yi},20), (\textrm{yi},18)\}\); there is no requirement that all values from \(A\) or \(P\) be present.

Relations turn out to be a very powerful way of thinking about computation. For example, consider this relation on \(A \times A \times B\), where \(A=\{1,2,3\}\) and \(B=\{1,2,3,4,5,6\}\):

x y z
=====
1 2
2 3
3 4     the relation x + y = z
1 3
2 4
3 5
1 4
2 5
3 6

For \(x\) and \(y\) \(\{1,2,3\}\), this table contains all possible sums. Now we can use this table to answer various questions. For example:

Is \(2 + 1 = 3\)? To answer this, we search the table for the triple \((2,1,3)\). It’s in the table, and so we know that \(2 + 1 = 3\) is true. Similarly, we know that \(2 + 2 = 1\) is not true because the triple \((2,2,1)\) is not anywhere in the table.
What is \(x\) in the equation \(x + 1 = 4\)? To solve this, we have to find a triple that matches \((x,1,4)\); we can see that there is only one such triple, \((3,1,4)\), and so in this equation \(x=4\).
What values of \(x\) and \(y\) satisfy \(x + y = 4\)? Here, we need to find triples that match \((x,y,4)\). There are two such triples in the table: \((1,3,4)\) and \((3,1,4)\), and so the equation has two different solutions: \(x=1\) and \(y=3\), or \(x=3\) and \(y=1\).

The interesting thing here is that we have converted the problem of solving equations into looking up tuples in a table. And this is essentially what Prolog does: it provides a way to use relations for computation.

Structure of a Prolog Program¶

Programs in most programming languages consist of functions of things like functions, variables, and modules. Prolog is a bit different, and its program consist of three main things:

Facts about objects and their relationships. Prolog objects are not objects in the sense of object-oriented programming, but objects in the sense of logic. An object could be any value, e.g. a number, a string, a list, etc. Relationships between objects are treated as logical predicates as in first-order quantified logic.
Rules about objects and their relationships. For example, you might have the rule “if X and Y have the same parents, then they’re siblings”.
Questions that can be asked about objects and their relationships. These are similar to queries in a database system.

Facts and rules together form what is often called a knowledge base. Often, writing a Prolog program consists of creating a (sometimes very sophisticated!) knowledge base, plus queries on that knowledge base.

Running Prolog¶

To get started, download and install SWI-Prolog. You run it at the command line by typing prolog:

$ prolog
Welcome to SWI-Prolog (Multi-threaded, 32 bits, Version 7.2.3)
Copyright (c) 1990-2015 University of Amsterdam, VU Amsterdam
SWI-Prolog comes with ABSOLUTELY NO WARRANTY. This is free software,
and you are welcome to redistribute it under certain conditions.
Please visit http://www.swi-prolog.org for details.

For help, use ?- help(Topic). or ?- apropos(Word).

?-

The ?- is the Prolog interpreter’s prompt and means it’s waiting for you to assert a fact or rule, or ask it a question.

Suppose you have a file named intro.pl with this content:

% intro.pl

likes(john, mary).   % a fact asserting that john likes mary

This file contains a single fact, likes(john, mary)., which we can interpret as meaning “john likes mary”. % marks the start of a single-line source code comment.

Now lets load intro.pl into the Prolog interpreter (using [ and ]), and ask a few questions:

?- [intro].
% intro compiled 0.00 sec, 2 clauses
true.

?- likes(john, mary).
true.

?- likes(mary, john).
false.

?- likes(john, iron_man).
false.

Our program asserts that it is a fact that john likes mary, and so when we ask it the “question” likes(john, mary)., it returns true.

When we ask it if mary likes john, i.e. likes(mary, john)., Prolog returns false because that’s not a fact it knows or can infer.

The third question, likes(john, iron_man)., is interesting for a couple of reasons. The object iron_man is not mentioned anywhere in intro.pl. You might guess that this would cause an error, but it’s no problem in this example. Since Prolog can’t prove that john likes iron_man, it concludes that john doesn’t like iron_man.

But that’s a pretty aggressive conclusion: more accurately, we simply don’t know whether or not john likes iron_man because we don’t know anything about that. So a more accurate answer would be “I don’t know if john likes iron_man”. But Prolog does not do that: if Prolog cannot prove something is true, it assumes that it is false.

Facts¶

Lets look at a fact in detail:

likes(john, mary).

This specifies a relationship between two objects: the object john and the object mary are in the likes relationship.

Note the following:

The names of relationships and objects must start with a lowercase letter. In Prolog, uppercase letters are variables.
The name of a relationship is often called a predicate, i.e. likes is a predicate.
The likes predicate is binary, i.e. it has an arity of 2. It has two arguments, john and mary.
In general, the order of arguments matters, i.e. likes(john, mary). is not the same fact as likes(mary, john).
Object names, such as john and mary, are similar to symbols in Lisp. They are not strings. All we can do is test if two objects are the same or different — we can’t access their individual characters.
The dot character . must always come at the end of a fact.

Here are a few more examples of facts:

fat(homer).                  % homer is fat
male(homer).                 % homer is a male
father_of(homer, bart).      % homer is bart's father
kicked(itchy, scratchy).     % itchy kicked scratchy
stole(bart, donut, homer).   % bart stole the donut from homer

We often refer to a list of facts as a database, or knowledge base (KB). Indeed, as you will see, Prolog is sin ome ways similar to relational database system.

The names used here have no special meaning in Prolog, and could just as well been written like this:

a(b).
c(b).
d(b, e).
f(g, h).
i(e, j, b).

Of course, this is much harder to read!

Exercise. Translate each of the following facts into Prolog. Use English words and names to make them easy to read.

Gold is valuable.
Water is wet.
Emily kissed Thomas.
Jimi kissed the sky.
Mr. Whispers fell asleep on the couch.
Randy stole the book from Stan and gave it to Kyle.

Solutions.

valuable(gold).
wet(water).
kissed(emily, thomas).
kissed(jim, the_sky).
fell_asleep(mr_whiskers, couch).; or fell_asleep_on_couch(mr_whiskers).
stole(randy, book, stan, kyle).

Questions¶

Given a knowledge base, we can ask questions about it, i.e. query it. For example:

?- likes(john, mary).
true

Here likes(john, mary). is interpreted as the question “Does john like mary?”.

Prolog answers questions by searching the facts in its knowledge base to see if any match the question. If so, true is returned; if not, false is returned. We will say that a query succeeds when it returns true, and fails when it returns false.

Prolog uses an algorithm called unification to do its matching. Two facts are said to unify if they have the same predicate name, the same number of arguments, and the same arguments in the same position.

So, for example, likes(john, mary) and likes(john, mary) unify, while likes(john, mary) and likes(mary, john) do not.

Variables¶

We often want to asks questions of the form “Who does john like?”, or “Who likes john?”. To deal with the “Who” in these questions, we need to introduce variables.

Variables in Prolog are called logic variables, and they are different than variables in other programming languages:

All Prolog variables must start with an uppercase letter. For example, X, Who, and John are all examples of Prolog variables, while x, who, and john are all non-variable objects.
A Prolog variable is either instantiated or uninstantiated. An instantiated variable has some value associated with it, while an uninstantiated variable has no value associated with it.

In most other programming languages, variables are always associated with some value. We might not know what the value is, but it is always there.

Suppose our knowledge base consists of these facts:

likes(john, mary).
likes(mary, skiing).
likes(john, skiing).
likes(john, flowers).
likes(mary, surprises).

We can use a variable in a question like this:

?- likes(john, X).  % What are all the things john likes?
X = mary ;          % user types ;
X = skiing ;        % user types ;
X = flowers.

The returned result is correct for the knowledge base: john likes mary, skiing, and flowers. After Prolog finds a matching assignment for X, it stops and displays what it has found. The user then has the option of stopping the program by typing ., or, by typing ; to have Prolog backtrack and try to find another value that satisfies X. In this example, the user typed ; after each value for X in order to get the next result.

When Prolog first sees the question likes(john, X). the variable X is uninstantiated, i.e. it has no value associated with it. When an uninstantiated variable appears as a predicate argument, Prolog lets that variable unify with any value in the same position for a predicate with the same name.

To answer the question likes(john, X). Prolog searches through its knowledge base to see which facts, if any, unify with likes(john, X). You could imagine the search going like this:

Can likes(john, X). unify with likes(john, mary).? Yes it can if X = mary.
Can likes(john, X). unify with likes(mary, skiing).? No, there is no possible value that can be assigned to X that will make likes(john, X). the same as likes(mary, skiing)..
Can likes(john, X). unify with likes(john, skiing).? Yes it can if X = skiing.
Can likes(john, X). unify with likes(john, flowers).? Yes it can if X = flowers.
Can likes(john, X). unify with likes(mary, surprises).? No, there is no possible value that can be assigned to X that will make likes(john, X). the same as``likes(mary, surprises).``.

When Prolog successfully unifies a fact, it internally marks the place in the knowledge base where the unification occurred so that it can later backtrack to that point and try to find a different match. When the user types ;, that tells Prolog to continue searching by starting immediately after the fact that was just unified. If, instead, the user types a ., it tells Prolog to immediately stop searching.

Here’s another example:

?- likes(X, skiing).  % Who likes skiing?
X = mary ;
X = john.

And another:

?- likes(nadine, X).  % What does nadine like?
false.

No facts in our knowledge base unify with this question, and so false is returned.

Here’s a question with two variables:

?- likes(X, Y). % What things do people like?
X = john,
Y = mary ;      % the user types all the ; characters
X = mary,
Y = skiing ;
X = john,
Y = skiing ;
X = john,
Y = flowers ;
X = mary,
Y = surprises.

Compare it to this:

?- likes(X, X).  % Who likes themselves?
false.

This means that there is no fact in the knowledge base whose first argument is the same its second argument.

Conjunctions¶

Another useful kind of question involves the word “and”, e.g. “Does john like both mary and skiing?”. In Prolog, we can write such questions as follows:

?- likes(john, mary), likes(john, skiing).
true.

The , means “and”, and true is returned because both facts are in the knowledge base.

All the facts separated by , must unify in order for the question to succeed. So, for example, this fails:

?- likes(john, mary), likes(john, surprises).
false.

Variables and conjunctions can be combined to ask some interesting questions. For example, “What things do john and mary both like?”:

?- likes(john, X), likes(mary, X).
X = skiing ;
false.

Prolog tries to answer this question by first trying to unify likes(john, X). It first unifies with the fact likes(john, mary)., and so X = mary. Then Prolog checks the second goal of the question, likes(mary, X). Here, X has the value mary, so it is equivalent to asking likes(mary, mary), which fails.

At this point Prolog automatically backtracks to the point where it instantiated X. It goes back to likes(john, X), unassigns X, and continues searching through the knowledge base from where it left off. So likes(john, X) next unifies with likes(john, skiing), and so X = skiing. Now it tries to satisfy likes(mary, X). Since X has the value skiing, this is the same as asking likes(mary, skiing), which is true. Thus, the entire conjunction is true.

If the user types ; after this X is returned, then Prolog keeps searching through the knowledge base in the same way, but does not find any more matches, and so returns false.

Rules¶

Rules let us encode things like “john likes anyone who likes wine”. For example:

likes(john, X) :- likes(X, wine).    % a rule

The :- in a Prolog rule means “if”. On the left of the :- is the head of the rule, and on the right is the body of the rule. As with facts, a rule ends with a ..

Here’s another rule:

likes(john, X) :- likes(X, wine), likes(X, food).    % a rule

This encodes “john likes anyone who likes both food and wine”. Or, equivalently, “john likes X if X likes wine and X likes food”.

Lets see a more complex rule. We will use this knowledge base:

male(bob).
male(doug).

female(val).
female(ada).

parents(doug, ada, bob).
parents(val, ada, bob).

We define the sister_of rule as follows:

sister_of(X, Y) :-
    female(X),
    parents(X, Mother, Father),   % Mother and Father are capitalized,
    parents(Y, Mother, Father).   % and so they are variables

This encodes the rule “X is the sister of Y if X is female, and the mother and father of X is the same as the mother and father of Y”.

We can now ask questions like this:

?- sister_of(val, doug).
true.

Tracing how this question gets answered is instructive:

The question sister_of(val, doug). unifies with the head of the sister_of rule.
Next Prolog tries to satisfy each goal in the sister_of rule in the order they’re given. Since X is val, it checks that female(val) is true.
female(val) is a fact in the knowledge base, so Prolog moves to the next goal in the rule and searches for the first fact that unifies with parents(val, Mother, Father).
Looking at the knowledge base, we can see that there is only one match: parents(val, ada, bob). Thus, at this point, Mother has the value ada, and Father has the value bob.
Prolog now tries to unify parents(Y, Mother, Father) with a fact in the knowledge base. Since X is val, Y is doug, Mother is ada, and Father is bob, Prolog checks to see if parents(doug, ada, bob) is in the knowledge base. And it is, so Prolog returns true.
Although we don’t see it, Prolog actually backtracks in this rule to see if there are any other ways to satisfy it. There’s no other way to satisfy parents(doug, ada, bob), so Prolog goes back to parents(val, Mother, Father) to see if there is some other fact in the knowledge base that unifies with it. There isn’t, so it backtracks again to female(val), which cannot be unified with anything else. Thus, Prolog has found the one and only way to satisfy this rule.

Let’s try another question:

?- sister_of(val, X).
X = doug ;
X = val.

The question sister_of(val, X). asks “Who has val as a sister?” (or “Who are val’s siblings?”). As we can see from the results, it doesn’t return quite the right answer. It correctly identifies that doug has val as a sister, but it also claims val is her owns sister! This is obviously not correct, but our rule allows it. Let’s trace it to see why:

sister_of(val, X) unifies with the head of the sister_of rule, sister_of(X, Y). We need to be careful with the two X variables here. The X in the rule header is assigned val, and so for the rest of the trace we will replace that X by val. The X in the question is different. It unifies with the variable Y. We say that X and Y are shared variables, or that they coreference each other. What happens is that once one of these two variables is assigned a value, the other variable immediately gets the same value.
Now Prolog checks the individual goals in the body of the rule. The first one, female(val), succeeds.
Next Prolog tries to unify parents(val, Mother, Father), and it finds the (only) match parents(val, ada, bob). Now Mother is ada, and Father is bob.
Now Prolog tries to unify parents(Y, ada, bob). The first fact in the knowledge base that matches this is parents(doug, ada, bob). and so Y gets the value doug. The variable X from the question (not the X in the rule header!) shares the same value as X, and so the result of the question is X = doug.
If the user types ;, Prolog backtracks and tries to find another solution. Prolog backtracks by unassigning the variables in the most recently satisfied goal, i.e. it tries to find another fact to unify parents(Y, ada, bob) with. And there is such a fact in our knowledge base: parents(val, ada, bob). So Y gets assigned val, and thus the shared X variable (the one in the question, not the one in the rule head!) also gets assigned val. This is how the second result of X = val is found.

Intuitively, the problem with the sister_of rule is that it doesn’t state that someone cannot be their own sister, i.e. it nowhere says that X and Y must be different. So we could fix it like this:

sister_of(X, Y) :-
    female(X),
    parents(X, Mother, Father),
    parents(Y, Mother, Father),
    X \= Y.

\= means X \= Y succeeds only when X and Y don’t unify with each other, i.e. they have different values:

?- sister_of(val, X).
X = doug ;
false.

In general, getting rules that work correctly in all cases is quite tricky in Prolog: they must be completely precise.

Anonymous Variables¶

Prolog lets you use _ as a special anonymous variable. We use it when we must include a variable, but don’t care about the value it is assigned. For example:

?- sister_of(val, _).  % Is val the sister of someone?
true

Prolog tells us the question succeeded, but it does not return a value for _.

An important detail is that the anonymous variable _ does not corefer (i.e. share) with any other variable (even itself). So when sister_of(val, _), _ will not share the same value as the X variable in the sister_of rule.

We can also use anonymous variables in facts. For instance:

likes(_, food). % everybody likes food

Using Prolog as a Database¶

One application of Prolog is as an in-memory database. For example, here’s a simple knowledge base about rocks:

grain(obsidian, fine).
color(obsidian, dark).
composition(obsidian, laval_glass).

grain(pumice, fine).
color(pumice, light).
composition(pumice, sticky_lava_froth).

grain(scoria, fine).
color(scoria, dark).
composition(scoria, fluid_lava_froth).

grain(felsite, fine_or_mixed).
color(felsite, light).
composition(felsite, high_silica_lava).

grain(andesite, fine_or_mixed).
color(andesite, medium).
composition(andesite, medium_silica_lava).

grain(basalt, fine_or_mixed).
color(basalt, dark).
composition(basalt, low_silica_lava).

grain(pegmatite, very_coarse).
color(pegmatite, any).
composition(pegmatite, granitic).

Notice there are no rules in this knowledge base, only facts.

Here are some queries we can make:

What kind of rocks are there?:
```
?- grain(Rock, _).
Rock = obsidian ;
Rock = pumice ;
Rock = scoria ;
Rock = felsite ;
Rock = andesite ;
Rock = basalt ;
Rock = pegmatite.
```
Note that this query assumes that all rocks have a grain. We’d get the same result (for this knowledge base) if we replaced grain by color or composition.

Which rocks have a light color?:

?- color(Rock, light).
Rock = pumice ;
Rock = felsite.

Which rocks are not a light color?:

?- color(Rock, Color), Color \= light.
Rock = obsidian,
Color = dark ;
Rock = scoria,
Color = dark ;
Rock = andesite,
Color = medium ;
Rock = basalt,
Color = dark ;
Rock = pegmatite,
Color = any.

Note that an expression of the form X \= Y succeeds just when X and Y do not unify.

Which rocks have the same grain as basalt?:

?- grain(basalt, G), grain(Rock, G).
G = fine_or_mixed,
Rock = felsite ;
G = fine_or_mixed,
Rock = andesite ;
G = fine_or_mixed,
Rock = basalt.

Which rocks have a grain different than basalt?:

?- grain(basalt, BasaltGrain), grain(Other, OtherGrain),
   BasaltGrain \= OtherGrain.
BasaltGrain = fine_or_mixed,
Other = obsidian,
OtherGrain = fine ;
BasaltGrain = fine_or_mixed,
Other = pumice,
OtherGrain = fine ;
BasaltGrain = fine_or_mixed,
Other = scoria,
OtherGrain = fine ;
BasaltGrain = fine_or_mixed,
Other = pegmatite,
OtherGrain = very_coarse.

Doing Simple Arithmetic with Prolog¶

Prolog functions do not return values in the same way that functions in most other languages do. You need to use extra parameters to get the results of a calculation. For instance:

to_celsius(F, C) :- C is (F - 32) * 5 / 9.

The is operator is used whenever we need the result of an arithmetic calculation.

You call to_celsius like this:

?- to_celsius(90, C).
C = 32.22222222222222.

Unfortunately, the first argument of to_celsius cannot be uninstantiated, e.g.:

?- to_celsius(F, 15).
ERROR: is/2: Arguments are not sufficiently instantiated

The error says that the right-hand side of the is statement is not allowed to have uninstantiated variables.

Here’s another function that calculates the area of a circle:

circle_area(Radius, Area) :- Area is Radius * Radius * 3.14.

?- circle_area(3, Area).
Area = 28.26.

Working with Lists¶

Prolog provides good support for lists. Prolog list begin with [, end with ], and separate values with ,. For example, [5, 7, 3] and [a, b, c] are both Prolog lists. Prolog provides a nice notation for easily accessing the first element of a list, and the rest of the elements:

?- [Head|Rest] = [a, b, c, d].
Head = a,
Rest = [b, c, d].

We will frequently use this | notation for processing lists one element at a time.

You can also get more than one at item at the head of the list like this:

?- [First, Second | Rest] = [a, b, c, d].
First = a,
Second = b,
Rest = [c, d].

The Member Function¶

Prolog rules are flexible enough to implement any function we like, and so it is possible to use Prolog as a general-purpose programming language.

Lets write a function called member(X, L) that succeeds just when X is somewhere on the list L. Prolog has no loops, so we use recursion:

member(X, [X|_]).                       % base case
member(X, [_|Rest]) :- member(X, Rest). % recursive case

As with any recursive function, we have a base case and a recursive case. The base case is member(X, [X|_]), which succeeds just when the item we are are looking for is the first element of the list. We use the anonymous variable _ here because we don’t use the rest of the list.

In the recursive case, we can safely assume that the first element of the list is not X because it would have been caught by the previous case. So if X is on the list, it must be somewhere in Rest, and that’s what we check in the body.

We can use member like this:

?- member(5, [6, 8, 15, 1]).
false.

?- member(5, [6, 8, 5, 1]).
true ;                       % user typed ;
false.

The second example is odd: Prolog has returned both true and false! Which is it? Prolog found the 5 at the end of the list, and that’s why it returned true. Because the user typed ;, Prolog backtracks to its most recent decision point, and tries to find 5 somewhere later in the list. It can’t, and so it returns false.

So you can think of the true as meaning a 5 was found, and the false meaning “no more 5s were found”. If you only care about whether or not there is a 5 somewhere in the list, then you can stop (type .) as soon as true is returned.

Now comes a very nice feature of Prolog. We can use member to generate items on a list one by one. For example:

?- member(X, [6, 8, 1, 15]).
X = 6 ;
X = 8 ;
X = 1 ;
X = 15 ;
false.

This essentially iterates through the list an element at a time, similar to a loop in an imperative language.

We can also write queries:

?- member(5, [6, 8, X, 1, 15]).
X = 5 ;
false.

These examples show that member can do much more than just test if a number is on a list. Prolog programmers often try to write functions in a way that allows variables to appear anywhere in the arguments. It isn’t always possible to do so (see to_celsius above), but when you can do it, the results can be quite useful.

The Length Function¶

The Prolog function length(Lst, N) can be used to calculate the length of a list:

?- length([], N).
N = 0.

?- length([3], N).
N = 1.

?- length([3, 6, 8], N).
N = 3.

?- length([3, X, 6, 8], N).
N = 4.

You can also use length to test if a list is of a given length, e.g.:

?- length([3, 1, 4], 3).
true.

?- length([3, 1, 4], 2).
false.

Surprisingly, you can also have length create lists of a given length for you, e.g.:

?- length(X, 2).
X = [_G1985, _G1988].

X is a list of length 2, and it contains two variables generated by Prolog.

You can even pass two variables to length:

?- length(Lst, N).
Lst = [],
N = 0 ;
Lst = [_G1997],
N = 1 ;
Lst = [_G1997, _G2000],
N = 2 ;
Lst = [_G1997, _G2000, _G2003],
N = 3 ;
Lst = [_G1997, _G2000, _G2003, _G2006],
N = 4
...

This generates an infinite number of lists of lengths 0, 1, 2, 3, ….

While length is built-in, it is instructive to write our own version of it. For example:

mylen([], 0).            % base case
mylen([_|Xs], Len) :-    % recursive case
    mylen(Xs, Rest_len),
    Len is 1 + Rest_len.

In the usual cases, mylen works the same as length:

?- mylen([], N).
N = 0.

?- mylen([3], N).
N = 1.

?- mylen([3, 6, 8], N).
N = 3.

?- mylen([3, X, 6, 8], N).
N = 4.

?- mylen([3, 1, 4], 3).
true.

?- mylen([3, 1, 4], 2).
false.

It also works when you pass it two variables:

?- mylen(Lst, N).
Lst = [],
N = 0 ;
Lst = [_G20210],
N = 1 ;
Lst = [_G20210, _G20213],
N = 2 ;
Lst = [_G20210, _G20213, _G20216],
N = 3 ;
Lst = [_G20210, _G20213, _G20216, _G20219],
N = 4
...

But it does not quite work the same in this case:

?- mylen(Lst, 3).
Lst = [_G22652, _G22655, _G22658] ;    % user types ;
% ... runs forever ...

mylen(Lst, 3) finds, as a first solution, a list of length 3. But then if you request another solution by typing ;, the program appears to get stuck in an infinite loop. Since we’re only interested in learning basic Prolog, we will simply ignore this problem; this particular use of mylen doesn’t seem to be very common or useful.

Simple Statistics¶

Suppose you want to calculate the sum of a list of numbers. Here’s how you could do it in Prolog:

sum([], 0).             % base case
sum([X|Xs], Total) :-   % recursive case
    sum(Xs, T),
    Total is X + T.     % always use "is" for arithmetic

Now we can write a function to calculate the average:

mean(X, Avg) :-
    sum(X, Total),
    length(X, N),
    Avg is Total / N.

Next, lets write a function that calculates the minimum value of a list. First, we write the min function that determines the smaller of two inputs:

min(X, Y, X) :- X =< Y.  % =< is less than or equal to
min(X, Y, Y) :- X > Y.

We use min in the definition of min_list as follows:

min_list([X], X).               % base case
min_list([Head|Tail], Min) :-   % recursive case
    min_list(Tail, Tmin),
    min(Head, Tmin, Min).

Appending¶

Prolog has a standard built-in append function, but it is instructive to write our own version. For example:

myappend([], Ys, Ys).            % base case
myappend([X|Xs], Ys, [X|Zs]) :-  % recursive case
  myappend(Xs, Ys, Zs).

Take some time to work through this definition carefully — it is well worth understanding.

This function can be used in a number of different ways. For example:

?- myappend([1,2],[3,4],[1,2,3,4]).     % confirm that two lists append
true.                                   % to another list

?- myappend([1,2],[3,4],[1,2,3,4,5]).
false.

?- myappend([1,2],[3,4],X).        % append two lists
X = [1, 2, 3, 4].

?- myappend([1,2],X,[1,2,3,4]).    % what list appends to make another?
X = [3, 4].

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

?- myappend(X,Y,[1,2,3,4]).        % all pairs of list that append to make
X = [],                            % [1,2,3,4]
Y = [1, 2, 3, 4] ;
X = [1],
Y = [2, 3, 4] ;
X = [1, 2],
Y = [3, 4] ;
X = [1, 2, 3],
Y = [4] ;
X = [1, 2, 3, 4],
Y = [] ;
false.

?- myappend(X,Y,Z).
X = [],
Y = Z ;
X = [_G2375],
Z = [_G2375|Y] ;
X = [_G2375, _G2381],
Z = [_G2375, _G2381|Y] ;
X = [_G2375, _G2381, _G2387],
Z = [_G2375, _G2381, _G2387|Y] ;
X = [_G2375, _G2381, _G2387, _G2393],
Z = [_G2375, _G2381, _G2387, _G2393|Y] ;
X = [_G2375, _G2381, _G2387, _G2393, _G2399],
Z = [_G2375, _G2381, _G2387, _G2393, _G2399|Y]
...

As you can see, myappend has a number of uses, which is pretty impressive for such a small function!