Logic programming with Prolog

[Deque]

Logic programming with Prolog

Why Prolog?

Prolog is very concise. Instead of giving step-by-step instructions you describe how the world looks like.
The resulting code is very flexible to use.

No need to know data structures and algorithms.

The syntax of prolog is very simple. I.e. there aren't many reserved keywords, these are the only ones:
( ) . :- , " ! ; fail repeat write read assert retract

Due to its nature Prolog is very suitable and widely used for AI programming (expert systems) and computational linguistics.
You probably heard of Watson (https://en.wikipedia.org/wiki/Watson_%28computer%29) the AI that played Jeopardy!. Watson is written in Prolog.

Some implementations are very fast, i.e. SICStus Prolog (benchmark: http://www.stups.uni-duesseldorf.de/ProB/index.php5/Why_Prolog%3F)

Requirements:

I take as a given that you know some imperative programming and have a basic understanding of mathematical logic (because that would be a topic by itself).

Installation Linux

Install the package swi-prolog-nox, which provides the core compiler and the standard library
I.e. If you are on Ubuntu type:

Code: [Select]

sudo apt-get install swi-prolog-nox
If you want a graphical frontend install swi-prolog-x as well. However, we will do our first steps without it.

Installation Windows

Go to this page and download the latest version for your platform: http://www.swi-prolog.org/download/stable

I didn't install it on Windows, but I guess the rest will be as usual. Just follow the installation instructions.

Basics

Now that we have the prolog compiler we can start writing our first program.
This will not be a hello world, because this doesn't really show how logic programming works. So we will start with something more typical.

You will realize soon, that this is pretty different from the imperative programming paradigm you are probably used to.
If you ever believed or heard "Know one language and you know all of them", Prolog will prove that wrong. Instead of writing instructions that the computer will execute one after another, you will write relations for Prolog into a knowledge base.
Based on this knowledge you can give Prolog a query and Prolog will refute the negated query in order to find a logical consequence of that program. Predicates can have side effects like printing

You will understand this better after you saw the first example. So open a text editor of your choice and write your first knowledge base.

The first program

Code: [Select]

% knowledge base
man(robert).
animal(rex).

Every program consists of clauses. The dot marks the end of a clause. In this case you defined two clauses, the first line is a comment for the human reader. man and animal are predicates, robert and rex are logical constants. You define that robert is a man and rex is an animal.

Save this file as human.pl open a terminal, navigate to the folder you saved the knowledge base in. Now type the command:

Code: [Select]

swipl
This will start an interactive prolog interpreter.

In order to load your program type

Code: [Select]

['human.pl'].
Do not forget the dot in the end. (If you forget it just type it on the next line)

If you edit your file, you can load it again via

Code: [Select]

make.
Now you are able to execute queries over your knowledge base.
A simple query would be:

Code: [Select]

man(clara).
Prolog will tell you that this is false.
This already shows a characteristic rule of Prolog--the closed world assumption. Prolog assumes that you told everything there is to know. You didn't specify what clara is, but based on the clauses there is no evidence that clara is a man. So the answer to that query will be

Code: [Select]

false.
You can now try other queries, but it will get more interesting after we added a bit more clauses to the knowledge base.

Code: [Select]

man(robert).

human(X) :- man(X).

animal(X) :- dog(X).
animal(rex).

dog(clara).
symbols that start with capital letters are variables. In this case we used the variable X.
You can imagine the :- as a backward arrow (<-). human(X) :- man(X). is an implication that says: If X is a man then X is also a human.

We also added a clause that says: If X is a dog then X is also an animal.

Here you see the two types of clauses in Prolog, facts, and rules.
Clauses that have an implication are called rules. The characteristic of a rule is that it has a head and a body:

Code: [Select]

Head :- Body
Clauses like man(robert). are called facts.

X can be everything you like. It might be a logical constant, but also a compound term.

Let's do some queries. Save the file and type make. to reload it.

Code: [Select]

animal(clara).
Is clara an animal? Prolog will tell us

Code: [Select]

true.
This is a logical consequence Prolog found based on your knowledge base. The rule animal(X) :- dog(X) told Prolog that all dogs are animals.
The fact dog(clara) told Prolog that clara is a dog. So it could prove that clara is an animal.

Let's do something else and ask Prolog what is an animal:

Code: [Select]

animal(X).
Prolog now tries to find an answer an suggests X = clara.
If you are satisfied with that answer you can type a dot.
If you want more suggestions type a semicolon and you will get X = rex.

Implementing list operations

Now let's do something more useful and implement predicates that provide some List operations.
We create a new knowledge base called list.pl and load it via

Code: [Select]

['list.pl'].
Now we want a predicate that tells us whether an element is a member of a list.
We call this predicate member. member(Element, List) shall be true iff Element is a member of List.

Lists in prolog are determined by squared brackets. With [X|Y] we have the head X and the rest Y of the list.
I.e. for the list [1,2,3,4] the head is the element 1 and the rest is the list [2,3,4].

With this we can come up with the following definition of member:

Code: [Select]

member(X|[X|R]).
member(X|[Y|R]) :- member(X,R).
The first clause is a fact saying: A list with the head X has the member X.
But other elements of the list that are not the head are a member too, so we create the rule in the second line. It says (reading from right to left): if X is a member of the list R, X is also a member of the list [Y|R] (the list R with a new head Y prepended).

Load the knowledge base and enter some queries.
The simplest use is asking whether X is a member:

Code: [Select]

member(1,[1,2,3]).
But you can also ask for members of the list and Prolog will give you all of them starting with the head. (Provided you use ; to get more answers).

Code: [Select]

member(X,[1,2,3]).
Now let's  calculate a sum of a list. The predicate sum(List, Sum) is true iff Sum is the sum of all members of List.
Again, we need a starting point. In this case the most simple list is an empty one. So we specify that the sum of an empty list is 0:

Code: [Select]

sum([],0).

If the list is not empty we take the head of it and add it to the sum of the rest of the list:

Code: [Select]

sum([X|R],S) :- sum(R,S1), S is S1 + X.

This can be read as (from right to left): If S1 is the sum of list R AND S is S1 + X, then S is the sum of the list R with the head X prepended.
Note that adding a condition separated by comma is a logical AND. Also note that we have a function here, which is S1 + X.

Like in other languages you can use several arithmetic operators, which are: + - / * mod div

Homework for you: Implement the predicate factorial. factorial(N, F) is true iff F is N!,
i.e. for N=5, F=1*2*3*4*5,
The starting point is: N=0, F=1

Let's create another predicate that uses the member predicate to work with. subset(L1, L2) is true iff L1 is a subset of L2. The empty list is a subset of every list, so let's start with that.

Code: [Select]

subset([],_).

The underscore is an anonymous variable. You might have noticed some warnings before. They were brought up because we used variables that could have been anonymous as well, which means it doesn't matter how the variable is called, because we don't use it again in the same clause.

We still need a clause to define the subset properly that says: If X is a member of L2 AND L1 is a subset of L2, then L1 with X prepended is also a subset of L2:

Code: [Select]

subset([X|L1],L2) :- member(X,L2), subset(L1,L2).
These two clauses are enough to define a subset function.
As usual you can not only use this to determine whether one list is the subset of another, you can also use it, i.e. to get possible missing members for a subset. The query:

Code: [Select]

subset([X,2,3], [1,2,3]).
will return all possible answers for X that make the predicate true. So you get 1, 2, 3 and if you go on with typing ; finally a false as answer, because there are no further solutions.

As well can the sum predicate be used to give possible lists for a certain sum:

Code: [Select]

sum(X, 5).
This flexibility is amazing. Imagine how much code you would need to achieve the same in an imperative language. You will not only need to define several procedures or functions to gain the same flexibility, you will also need more lines for either one of them than you would in Prolog.

If you worked through this introduction you will now realize, what the difference between declarative and imperative is. Instead of telling the computer HOW to solve a problem step by step, you tell the characteristics of a predicate.
Unless you are a mathematician or have dealt with mathematical logic a lot this kind of thinking won't come natural at first. It is like you have to learn programming again. Nevertheless this language is one possible tool that a programmer should keep in mind. Some tasks are done better with this tool than with others.

Have fun programming.
If you solved the homework, post the solution here.

PS: Hello World

Did you miss a hello world program? Just type in the interpreter:

Code: [Select]

write('Hello World'), nl.
(write is a predicate with the side effect of writing the given string to stdout)
Nothing interesting in that, though.

Deque

[vezzy]

Oh yes, thanks. I've been meaning to dive in to Prolog. This will be a nice 10-minute introduction document.

[Deque]

Oh yes, thanks. I've been meaning to dive in to Prolog. This will be a nice 10-minute introduction document.

Thank you, you are the first one to tell me that Prolog really interests you.
I have the feeling most people don't like it.

[vezzy]

Probably because you have to forget everything you've ever learned from a procedural or object-oriented language.

[Psycho_Coder]

Homework :-

Code: [Select]

factorial(0,1).
factorial(N,F) :- N>0, N2 is N-1, factorial(N2,F1), F is N*F1.

Output :-

[Deque]

Probably because you have to forget everything you've ever learned from a procedural or object-oriented language.

I also believe that this is the main reason, but it shouldn't be one. Either they want to learn something new or they can stay with the languages they already know.

Homework :-

Code: [Select]

factorial(0,1).
factorial(N,F) :- N>0, N2 is N-1, factorial(N2,F1), F is N*F1.


That's correct. I give you a cookie.

[Psycho_Coder]

That's correct. I give you a cookie.

I didn't get a cookie to eat. I am hungry  . LOL, sorry mam having a fun. BTW I am sorry I forgot to thank your thread. So --> Thank you for this tutorial.

[Uriah]

+1, nice tutorial. I really like how prolog works, and can definitely see how it would be useful.

By the way, do you have any particular education background in math, Deque? A lot of your content seems to reflect that, which i really appreciate since I love math.

[Deque]

+1, nice tutorial. I really like how prolog works, and can definitely see how it would be useful.

By the way, do you have any particular education background in math, Deque? A lot of your content seems to reflect that, which i really appreciate since I love math.

Hi Uriah. Thanks for your feedback.
I have a BSc in computer science and I am currently writing my master thesis.
A lot of the courses I had (especially in the first semesters) are mathematics or build up on mathematics. I can't say that I am very good at plain mathematics, though, and I probably forgot half of what I learned in the first semesters, but I am good when it comes to certain topics like logic. I really enjoyed the AI courses.