Prolog - Gateway to Logic Programming

In this notebook we talk about Prolog basics. We also learn how to benefit from Prolog's power using Python.

Table of Contents:

Introduction

because logic was removed from the course’s syllabus and students might be unfamiliar with this topic it’s good to have a prerequisites subsection listing links to required skills and mathematical background such as logic itself, this notebook is trying to fulfill the lack of logic topics in the course.

What is Prolog?

Prolog is a logic programming language. It means that it is different in nature from the general-purpose form of languages like C++, Java, Python, Javascript, etc.

Prolog is based on First-Order Logic and is purely designed as a declarative programming language. The logic is expressed in terms of relations, and all the computation is initiated by queries.

The language is used for theorem proving, designing expert systems, term rewriting, automated planning, NLP, and many more interesting fields.

Why Learn Prolog?

  • Do I get a job by solely learning Prolog? The answer is probably not. Prolog is not a general-purpose language and is currently used only in specific fields.

  • Does learning Prolog change your overall programming skill? Absolutely Yes. It uses a different paradigm than famous languages and teaches you how to tackle problems differently.

  • Does learning prolog help you get a better position in a company? That depends on the type of company. Suppose the company is related to Artificial Intelligence. In that case, your way of logical thinking that you get by learning Prolog and even the Prolog can help you be promoted to a better position.

For other reasons why to learn Prolog, read this article.

As a summary, I selected this sentence from the aforementioned article:

"As a student of computer science [engineering], one can make a decent career by always following the hype, but to stand out, one has to diverge from the well-trodden paths. Those willing to explore unpopular territory have a chance of being ahead of the crowd."

Installing Prolog

Actually, Prolog is a standard, and there are different implementations of it. Arguably, the most famous and widely used one is SWI-Prolog. You can download the SWI-Prolog installer from its site. SWI-Prolog Download

If you use Windows, don't forget to check the 'add swipl to the system PATH for all users' option during the installation. If you forget to do so, you can manually add C:\Program Files\swipl\bin to the system path, given that you used the default installation path.

There are some jupyter notebook kernels available, but they mostly work on particular OS builds. Therefore, we use a python package named pyswip that runs code using SWI-Prolog. You can see the full installation guide here, but a simple pip install should suffice.

In [ ]:
!pip install pyswip
In [2]:
from pyswip import Prolog, registerForeign
prolog = Prolog()

Prolog 101

Like all programming language tutorials, the first thing is "Hello World"!

write('Hello World'),nl,write('Let\'s Learn Prolog!').

Note that all prolog statements must end with dot ..

As we use pyswip here, we won't need Prolog write, because we can use python print and even use some python functions.

Terminologies

  • Fact: A fact is a predicate expression that makes a declarative statement about the problem domain. Facts either consist of a particular item or a relation between items.
rainy.

father(michael , jane).

These two statements are both facts. father is a relationship. rainy,michael, and jane are atoms (constants). All atoms must start with lowercase letters unless they are enclosed in single quotes '.

  • Rules: rules allow us to make conditional statements. They are defined using :- symbol. left :- right1,right2 says IF right1 and right2 is true, then left is also true. Note that , acts as and operator here. Also ; acts as or operator.

  • Variables: A Variable is an object we can't name at the time of execution. Variables are uppercase.

  • Query: In making a query, you ask Prolog whether it can prove that your statement is true. In Prolog, a query is made with ?- symbol, but in pyswip we can use query(string).

Simple examle

Let's see a simple example:

In [3]:
prolog.assertz("father(michael,jane)") 
prolog.assertz("child(X,Y) :- father(Y,X)")
In [4]:
for solns in prolog.query("child(X , Y)"): #X and Y are prolog variables. This two lines simply print all child relationships.
    print(solns["X"] , "is child of" , solns["Y"])

jane is child of michael

First line is a fact that says Michael is father of Jane. Second line is a rule that says if Y is a father of X then X is a child of Y. Note that X and Y are variables.

In the for, we query for all child relationships and print them. Note that the result of query() is a python generator and must be used in a foreach statement or casted into a list.

consult: You can load a database of prolog statements using consult. It works both in prolog and pyswip. In prolog you can use both ?- consult('file.pl'). and ['file1.pl'].. In pyswip you can use consult(path) function.

Let's make a more complicated example and put it in a file named 1.pl.

% 1.pl

father(albert, bob).
father(albert, betsy).
father(albert, bill).

mother(alice, bob).
mother(alice, betsy).
mother(alice, bill).

father(bob, carl).
father(bob, charlie).

parent(X,Y) :- father(X,Y); mother(X,Y).

grandparent(X,Y) :- parent(X,Z),parent(Z,Y). %X is grandparent of Y if X is parent of Z and Z is parent of Y

grandchild(X,Y) :- parent(Z,X) , parent(Y,Z). %X is grandchild of Y if Y is parent of Z and Z is parent of X
In [5]:
prolog.consult("prolog_files/1.pl")
In [6]:
for solns in prolog.query("grandparent(albert , X)"):
    print("Albert" , "is grandparent of" , solns["X"])
for solns in prolog.query("grandchild(carl , X)"):
    print("Albert" , "is grandchild of" , solns["X"])

Albert is grandparent of carl
Albert is grandparent of charlie
Albert is grandchild of albert
Albert is grandchild of alice

Interesting Prolog Examples

Tower of Hanoi

Tower of Hanoi is a very famous programming problem that is used to teach recursive functions. You can see the problem definition on Wikipedia. Here we try to implement it in Prolog and solve a simple instance of it using pyswip.

% hanoi.pl

hanoi(N) :- move(N, left, right, center).
move(0, _, _, _) :- !.
move(N, A, B, C) :-
  M is N-1,
  move(M, A, C, B),
  notify([A,B]),
  move(M, C, B, A).

hanoi(N) will lead to calling move(N). move (0,_,_,_) is the termination condition of recursive call, and ! tells prolog to stop calling the function and backtracking. _ matches (unifies) with everything; It is similar to "don't care" in logic circuits. move(N,A,B,C) is the actual recursive formulation of Tower of Hanoi. is operator is the same as = in other languages and here it means "put N-1 into M". notify is a function that will be defined in python and we will use pyswip to bind prolog and python code together.

In [7]:
prolog.consult("prolog_files/hanoi.pl")
In [8]:
N= 3

def notify(t):
        print("move disk from %s pole to %s pole." % tuple(t))
notify.arity = 1
        
registerForeign(notify)
list(prolog.query("hanoi(%d)" % N));

move disk from left pole to right pole.
move disk from left pole to center pole.
move disk from right pole to center pole.
move disk from left pole to right pole.
move disk from center pole to left pole.
move disk from center pole to right pole.
move disk from left pole to right pole.

registerForeign is used to make prolog run python's notify function. Also note that as we said before, prolog.query() makes a generator. Generators are not evaluated by default. They must be used in a foreach or casted into list to force python actually evaluate them.

Coins Problem

In a country, there are coins of 1,2,5,50 and 100. We want to find all the ways to sum at most max_count of these coins to get to a cumulative sum of total. We solve this in coins.pl file.

:- use_module(library('bounds')).

coins(S, Count, Total) :-
    % A=1, B=5, C=10, D=50, E=100
    S = [A, B, C, D, E],

    Av is   1,
    Bv is   5,
    Cv is  10,
    Dv is  50,
    Ev is 100,

    Aup is Total // Av, % // means integer division
    Bup is Total // Bv,
    Cup is Total // Cv,
    Dup is Total // Dv,
    Eup is Total // Ev,

    A in 0..Aup,
    B in 0..Bup,
    C in 0..Cup,
    D in 0..Dup,
    E in 0..Eup,

    VA #= A*Av,
    VB #= B*Bv,
    VC #= C*Cv,
    VD #= D*Dv,
    VE #= E*Ev,

    sum(S, #=, Count),
    VA + VB + VC + VD + VE #= Total,

    label(S).

bound library is used to make the search space limited. For example if sum is 1000, we could have at most 100 coins of value 10. So C should be between 0 to 100. #= is same as = for algebraic expressions. sum (S,#=,Count) means that sum of all elements in list S should be equal to Count. Elements of S indicate count of each coin.

In [9]:
prolog.consult("prolog_files/coins.pl")
In [10]:
max_count = 100
total = 500
for i, soln in enumerate(prolog.query("coins(S, %d, %d)." % (max_count,total))):
    S = zip(soln["S"], [1, 5, 10, 50, 100])
    print(i, end=" ")
    for c, v in S:
        print("%dx%d" % (c,v), end=" ")
    print()

0 0x1 100x5 0x10 0x50 0x100 
1 5x1 91x5 4x10 0x50 0x100 
2 10x1 82x5 8x10 0x50 0x100 
3 15x1 73x5 12x10 0x50 0x100 
4 15x1 81x5 3x10 1x50 0x100 
5 20x1 64x5 16x10 0x50 0x100 
6 20x1 72x5 7x10 1x50 0x100 
7 25x1 55x5 20x10 0x50 0x100 
8 25x1 63x5 11x10 1x50 0x100 
9 25x1 71x5 2x10 2x50 0x100 
10 25x1 73x5 1x10 0x50 1x100 
11 30x1 46x5 24x10 0x50 0x100 
12 30x1 54x5 15x10 1x50 0x100 
13 30x1 62x5 6x10 2x50 0x100 
14 30x1 64x5 5x10 0x50 1x100 
15 35x1 37x5 28x10 0x50 0x100 
16 35x1 45x5 19x10 1x50 0x100 
17 35x1 53x5 10x10 2x50 0x100 
18 35x1 55x5 9x10 0x50 1x100 
19 35x1 61x5 1x10 3x50 0x100 
20 35x1 63x5 0x10 1x50 1x100 
21 40x1 28x5 32x10 0x50 0x100 
22 40x1 36x5 23x10 1x50 0x100 
23 40x1 44x5 14x10 2x50 0x100 
24 40x1 46x5 13x10 0x50 1x100 
25 40x1 52x5 5x10 3x50 0x100 
26 40x1 54x5 4x10 1x50 1x100 
27 45x1 19x5 36x10 0x50 0x100 
28 45x1 27x5 27x10 1x50 0x100 
29 45x1 35x5 18x10 2x50 0x100 
30 45x1 37x5 17x10 0x50 1x100 
31 45x1 43x5 9x10 3x50 0x100 
32 45x1 45x5 8x10 1x50 1x100 
33 45x1 51x5 0x10 4x50 0x100 
34 50x1 10x5 40x10 0x50 0x100 
35 50x1 18x5 31x10 1x50 0x100 
36 50x1 26x5 22x10 2x50 0x100 
37 50x1 28x5 21x10 0x50 1x100 
38 50x1 34x5 13x10 3x50 0x100 
39 50x1 36x5 12x10 1x50 1x100 
40 50x1 42x5 4x10 4x50 0x100 
41 50x1 44x5 3x10 2x50 1x100 
42 50x1 46x5 2x10 0x50 2x100 
43 55x1 1x5 44x10 0x50 0x100 
44 55x1 9x5 35x10 1x50 0x100 
45 55x1 17x5 26x10 2x50 0x100 
46 55x1 19x5 25x10 0x50 1x100 
47 55x1 25x5 17x10 3x50 0x100 
48 55x1 27x5 16x10 1x50 1x100 
49 55x1 33x5 8x10 4x50 0x100 
50 55x1 35x5 7x10 2x50 1x100 
51 55x1 37x5 6x10 0x50 2x100 
52 60x1 0x5 39x10 1x50 0x100 
53 60x1 8x5 30x10 2x50 0x100 
54 60x1 10x5 29x10 0x50 1x100 
55 60x1 16x5 21x10 3x50 0x100 
56 60x1 18x5 20x10 1x50 1x100 
57 60x1 24x5 12x10 4x50 0x100 
58 60x1 26x5 11x10 2x50 1x100 
59 60x1 28x5 10x10 0x50 2x100 
60 60x1 32x5 3x10 5x50 0x100 
61 60x1 34x5 2x10 3x50 1x100 
62 60x1 36x5 1x10 1x50 2x100 
63 65x1 1x5 33x10 0x50 1x100 
64 65x1 7x5 25x10 3x50 0x100 
65 65x1 9x5 24x10 1x50 1x100 
66 65x1 15x5 16x10 4x50 0x100 
67 65x1 17x5 15x10 2x50 1x100 
68 65x1 19x5 14x10 0x50 2x100 
69 65x1 23x5 7x10 5x50 0x100 
70 65x1 25x5 6x10 3x50 1x100 
71 65x1 27x5 5x10 1x50 2x100 
72 70x1 0x5 28x10 1x50 1x100 
73 70x1 6x5 20x10 4x50 0x100 
74 70x1 8x5 19x10 2x50 1x100 
75 70x1 10x5 18x10 0x50 2x100 
76 70x1 14x5 11x10 5x50 0x100 
77 70x1 16x5 10x10 3x50 1x100 
78 70x1 18x5 9x10 1x50 2x100 
79 70x1 22x5 2x10 6x50 0x100 
80 70x1 24x5 1x10 4x50 1x100 
81 70x1 26x5 0x10 2x50 2x100 
82 75x1 1x5 22x10 0x50 2x100 
83 75x1 5x5 15x10 5x50 0x100 
84 75x1 7x5 14x10 3x50 1x100 
85 75x1 9x5 13x10 1x50 2x100 
86 75x1 13x5 6x10 6x50 0x100 
87 75x1 15x5 5x10 4x50 1x100 
88 75x1 17x5 4x10 2x50 2x100 
89 75x1 19x5 3x10 0x50 3x100 
90 80x1 0x5 17x10 1x50 2x100 
91 80x1 4x5 10x10 6x50 0x100 
92 80x1 6x5 9x10 4x50 1x100 
93 80x1 8x5 8x10 2x50 2x100 
94 80x1 10x5 7x10 0x50 3x100 
95 80x1 12x5 1x10 7x50 0x100 
96 80x1 14x5 0x10 5x50 1x100 
97 85x1 1x5 11x10 0x50 3x100 
98 85x1 3x5 5x10 7x50 0x100 
99 85x1 5x5 4x10 5x50 1x100 
100 85x1 7x5 3x10 3x50 2x100 
101 85x1 9x5 2x10 1x50 3x100 
102 90x1 0x5 6x10 1x50 3x100 
103 90x1 2x5 0x10 8x50 0x100 
104 95x1 1x5 0x10 0x50 4x100

N-Queens

N-Queens is a famous problem that asks how to put N queens in an $N \times N$ checkboard such that none of them threatens each other. As we know, in each column, there must be one queen, so we encode the state as an N-tuple in which element at index $i$ indicates which row the queen at column $i$ resides in. We can simply model this problem in Prolog like this:

:- use_module(library(clpfd)).

n_queens(N, Qs) :-
        length(Qs, N),
        Qs ins 1..N, %ins is in clpfd library. It check that "each" element of Qs is in range 1 to N
        safe_queens(Qs),
        label(Qs).

safe_queens([]). %Empty list is a good combination.
safe_queens([Q|Qs]) :- safe_queens(Qs, Q, 1), safe_queens(Qs).

safe_queens([], _, _). %Empty list is a good combination.
safe_queens([Q|Qs], Q0, D0) :-
        Q0 #\= Q,
        abs(Q0 - Q) #\= D0, %Diagonal Check
        D1 #= D0 + 1,
        safe_queens(Qs, Q0, D1).
In [2]:
prolog.consult("prolog_files/queens.pl")
In [3]:
for i,soln in enumerate(prolog.query("n_queens(%d, Qs)." % (8))):
    print(i+1,".\t",soln["Qs"])

1 .	 [1, 5, 8, 6, 3, 7, 2, 4]
2 .	 [1, 6, 8, 3, 7, 4, 2, 5]
3 .	 [1, 7, 4, 6, 8, 2, 5, 3]
4 .	 [1, 7, 5, 8, 2, 4, 6, 3]
5 .	 [2, 4, 6, 8, 3, 1, 7, 5]
6 .	 [2, 5, 7, 1, 3, 8, 6, 4]
7 .	 [2, 5, 7, 4, 1, 8, 6, 3]
8 .	 [2, 6, 1, 7, 4, 8, 3, 5]
9 .	 [2, 6, 8, 3, 1, 4, 7, 5]
10 .	 [2, 7, 3, 6, 8, 5, 1, 4]
11 .	 [2, 7, 5, 8, 1, 4, 6, 3]
12 .	 [2, 8, 6, 1, 3, 5, 7, 4]
13 .	 [3, 1, 7, 5, 8, 2, 4, 6]
14 .	 [3, 5, 2, 8, 1, 7, 4, 6]
15 .	 [3, 5, 2, 8, 6, 4, 7, 1]
16 .	 [3, 5, 7, 1, 4, 2, 8, 6]
17 .	 [3, 5, 8, 4, 1, 7, 2, 6]
18 .	 [3, 6, 2, 5, 8, 1, 7, 4]
19 .	 [3, 6, 2, 7, 1, 4, 8, 5]
20 .	 [3, 6, 2, 7, 5, 1, 8, 4]
21 .	 [3, 6, 4, 1, 8, 5, 7, 2]
22 .	 [3, 6, 4, 2, 8, 5, 7, 1]
23 .	 [3, 6, 8, 1, 4, 7, 5, 2]
24 .	 [3, 6, 8, 1, 5, 7, 2, 4]
25 .	 [3, 6, 8, 2, 4, 1, 7, 5]
26 .	 [3, 7, 2, 8, 5, 1, 4, 6]
27 .	 [3, 7, 2, 8, 6, 4, 1, 5]
28 .	 [3, 8, 4, 7, 1, 6, 2, 5]
29 .	 [4, 1, 5, 8, 2, 7, 3, 6]
30 .	 [4, 1, 5, 8, 6, 3, 7, 2]
31 .	 [4, 2, 5, 8, 6, 1, 3, 7]
32 .	 [4, 2, 7, 3, 6, 8, 1, 5]
33 .	 [4, 2, 7, 3, 6, 8, 5, 1]
34 .	 [4, 2, 7, 5, 1, 8, 6, 3]
35 .	 [4, 2, 8, 5, 7, 1, 3, 6]
36 .	 [4, 2, 8, 6, 1, 3, 5, 7]
37 .	 [4, 6, 1, 5, 2, 8, 3, 7]
38 .	 [4, 6, 8, 2, 7, 1, 3, 5]
39 .	 [4, 6, 8, 3, 1, 7, 5, 2]
40 .	 [4, 7, 1, 8, 5, 2, 6, 3]
41 .	 [4, 7, 3, 8, 2, 5, 1, 6]
42 .	 [4, 7, 5, 2, 6, 1, 3, 8]
43 .	 [4, 7, 5, 3, 1, 6, 8, 2]
44 .	 [4, 8, 1, 3, 6, 2, 7, 5]
45 .	 [4, 8, 1, 5, 7, 2, 6, 3]
46 .	 [4, 8, 5, 3, 1, 7, 2, 6]
47 .	 [5, 1, 4, 6, 8, 2, 7, 3]
48 .	 [5, 1, 8, 4, 2, 7, 3, 6]
49 .	 [5, 1, 8, 6, 3, 7, 2, 4]
50 .	 [5, 2, 4, 6, 8, 3, 1, 7]
51 .	 [5, 2, 4, 7, 3, 8, 6, 1]
52 .	 [5, 2, 6, 1, 7, 4, 8, 3]
53 .	 [5, 2, 8, 1, 4, 7, 3, 6]
54 .	 [5, 3, 1, 6, 8, 2, 4, 7]
55 .	 [5, 3, 1, 7, 2, 8, 6, 4]
56 .	 [5, 3, 8, 4, 7, 1, 6, 2]
57 .	 [5, 7, 1, 3, 8, 6, 4, 2]
58 .	 [5, 7, 1, 4, 2, 8, 6, 3]
59 .	 [5, 7, 2, 4, 8, 1, 3, 6]
60 .	 [5, 7, 2, 6, 3, 1, 4, 8]
61 .	 [5, 7, 2, 6, 3, 1, 8, 4]
62 .	 [5, 7, 4, 1, 3, 8, 6, 2]
63 .	 [5, 8, 4, 1, 3, 6, 2, 7]
64 .	 [5, 8, 4, 1, 7, 2, 6, 3]
65 .	 [6, 1, 5, 2, 8, 3, 7, 4]
66 .	 [6, 2, 7, 1, 3, 5, 8, 4]
67 .	 [6, 2, 7, 1, 4, 8, 5, 3]
68 .	 [6, 3, 1, 7, 5, 8, 2, 4]
69 .	 [6, 3, 1, 8, 4, 2, 7, 5]
70 .	 [6, 3, 1, 8, 5, 2, 4, 7]
71 .	 [6, 3, 5, 7, 1, 4, 2, 8]
72 .	 [6, 3, 5, 8, 1, 4, 2, 7]
73 .	 [6, 3, 7, 2, 4, 8, 1, 5]
74 .	 [6, 3, 7, 2, 8, 5, 1, 4]
75 .	 [6, 3, 7, 4, 1, 8, 2, 5]
76 .	 [6, 4, 1, 5, 8, 2, 7, 3]
77 .	 [6, 4, 2, 8, 5, 7, 1, 3]
78 .	 [6, 4, 7, 1, 3, 5, 2, 8]
79 .	 [6, 4, 7, 1, 8, 2, 5, 3]
80 .	 [6, 8, 2, 4, 1, 7, 5, 3]
81 .	 [7, 1, 3, 8, 6, 4, 2, 5]
82 .	 [7, 2, 4, 1, 8, 5, 3, 6]
83 .	 [7, 2, 6, 3, 1, 4, 8, 5]
84 .	 [7, 3, 1, 6, 8, 5, 2, 4]
85 .	 [7, 3, 8, 2, 5, 1, 6, 4]
86 .	 [7, 4, 2, 5, 8, 1, 3, 6]
87 .	 [7, 4, 2, 8, 6, 1, 3, 5]
88 .	 [7, 5, 3, 1, 6, 8, 2, 4]
89 .	 [8, 2, 4, 1, 7, 5, 3, 6]
90 .	 [8, 2, 5, 3, 1, 7, 4, 6]
91 .	 [8, 3, 1, 6, 2, 5, 7, 4]
92 .	 [8, 4, 1, 3, 6, 2, 7, 5]

As you can see, it has found all 92 unique solutions of 8-Queen. You can test it with other numbers too. The code we wrote for this problem is much less than its implementation in most general purpose langauges and yet, it is very elegant and can be understood with little to no effort if you are familiar with prolog syntax.

Good References to Learn Prolog, Pyswip, and their applications:

Authors
Amirmahdi Namjoo
Author