<jupyter_start><jupyter_text>Table of Contents:* [Introduction](intro)* [What is Prolog](what-is-prolog)* [Why Learn Prolog?](why-learn-prolog)* [Installing Prolog](installing-prolog)* [Prolog 101](prolog-101)  - [Terminologies](terminologies)  - [Simple example](simple-example)* [Instersting Prolog examples](examples)  - [Tower of Hanoi](hanoi)  - [Coins Problem](coins-problem)  - [N-Queens](n-queens)* [References](ref)  Introductionbecause 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](https://en.wikipedia.org/wiki/First-order_logic) and is purely designed as a [declarative programming language](https://en.wikipedia.org/wiki/Declarative_programming). 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](https://en.wikipedia.org/wiki/Natural_language_processing), 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](http://dstrohmaier.com/why-learn-prolog-in-2021/).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](https://www.swi-prolog.org/download/stable)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](https://github.com/yuce/pyswip/blob/master/INSTALL.md), but a simple pip install should suffice.<jupyter_code>!pip install pyswip
from pyswip import Prolog, registerForeign
prolog = Prolog()<jupyter_output><empty_output><jupyter_text>Prolog 101 Like all programming language tutorials, the first thing is "Hello World"!```prologwrite('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.```prolograiny.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 examleLet's see a simple example:<jupyter_code>prolog.assertz("father(michael,jane)") 
prolog.assertz("child(X,Y) :- father(Y,X)")
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"])<jupyter_output>jane is child of michael<jupyter_text>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`. ```prolog% 1.plfather(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 Ygrandchild(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```<jupyter_code>prolog.consult("prolog_files/1.pl")
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"])<jupyter_output>Albert is grandparent of carl
Albert is grandparent of charlie
Albert is grandchild of albert
Albert is grandchild of alice<jupyter_text>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](https://en.wikipedia.org/wiki/Tower_of_Hanoi). Here we try to implement it in Prolog and solve a simple instance of it using pyswip. ```prolog% hanoi.plhanoi(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.<jupyter_code>prolog.consult("prolog_files/hanoi.pl")
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));<jupyter_output>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.<jupyter_text>`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. ```prolog:- 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.<jupyter_code>prolog.consult("prolog_files/coins.pl")
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()<jupyter_output>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 4[...]<jupyter_text>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: ```prolog:- 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).```<jupyter_code>prolog.consult("prolog_files/queens.pl")
for i,soln in enumerate(prolog.query("n_queens(%d, Qs)." % (8))):
    print(i+1,".\t",soln["Qs"])<jupyter_output>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[...]
{'fraction_non_alphanumeric': 0.1200763358778626, 'fraction_numerical': 0.07793893129770993, 'mean_word_length': 3.9141035258814703, 'pattern_counts': {'":': 0, '<': 20, '<?xml version=': 0, '>': 20, 'https://': 6, 'lorem ipsum': 0, 'www.': 1, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 3, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '6', 'dir': 'jupyter-structured-clean-dedup', 'id': '352545', 'license': 'MIT', 'n_tokens_mistral': 5488, 'n_tokens_neox': 4652, 'n_words': 2019, 'path': 'notebooks/logic_programming/index.ipynb', 'repo_name': 'titansarus/supplementary', 'size': '13100'}