Amirmahdi Namjoo
Author
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,right2says IFright1andright2is 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 inpyswipwe can usequery(string).
Simple example
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.