Programming Language

Learn Prolog

Recently, I got in touch with the Prolog in my coursework (EEEM0005). It is not easy! Prolog is a very old programming language which I only see it in the TIOBE programming language rank (a boring index), but I was attracted by its simple structure and strange programming grammar at begining.

1
2
3
4
5
6
parent(pam, bob).
parent(tom, bob).
parent(tom, liz).
parent(bob, pat).
parent(bob, ann).
parent(pat, jim).

Above all six facts (also called clauses) represent a parent relationship:

parent relationship

It looks so simple to initiate a relation. In contrast to other modern programming languages, e.g, Java, C++, Prolog doesn’t need to define any vairable explicitly and the data types are gone. If I want to know who is the liz's parent, just query it:

1
2
?- parent(X, liz).
X=tom

Now I know X is the parent of liz, and tom is X. In Prolog, arguments begin with capital is variable, otherwise constant that we can not re-assign it. We can also know that argument X also plays a role of return value.

Like other programming languages, Prolog also has function which is called procedure that includes multiple clauses:

1
2
offspring(Y, X) :-
  parent(X, Y).

Y is offspring of X if X is parent of Y. The conclusion part (head of the clause) if true on the condition that the condition part (body of the clause) is true.

1
2
?- offspring(liz, tom).
true

Interestingly, writing Prolog is just like writing logical rules. It is a big challenge for me to learn and use Prolog because I am very familiar with traditional programming languages like Java, C, and am used to defining variables first, obtaining the return value and then calculating. Each step is basically fixed. However, Prolog breaks my way of thinking. Desciptive or declaritive programming freeds me from being tied to the program itself and let me have more time dealing with logical relationships.

Although true or false are the only return value in Prolog, you can also get the computed value via procedure arguments.

1
2
3
4
5
6
step1(X, Y):-
    Y is X + 1.
step2(Y, Z):-
    Z is X * 2.
    
?- step1(1, Y), step2(Y, Z).

Except for the programming ideas, the grammar is also different from other languages. Firstly, there are no if and switch statements in Prolog. Even though ( condition -> then_clause ; else_clause ) structure is provided in Prolog to implement the control condition, it seems not beautiful and destroys the declaritive structure.

1
2
3
4
5
6
7
% method 1
% ( condition -> then_clause ; else_clause )
foo(X, Y):-
    (   X > 2
    ->  Y is X+1
    ;	Y is X-1
    ).
if stat 1

The recommended solution is to use two procedures with different rules.

1
2
3
4
5
6
7
% method 2
bar(X, Y):-
    X > 2,
    Y is X+1, !. % cut operation
bar(X, Y):-
    X =< 2,
    Y is X-1.

If X larger than 2, the first procedure returns true, the second returns false, and vice-versus. Additonally, the cutoperation can be used for if-else as showed in above code, this is not necessary because we usually want only correct result. According to the mechanism of Prolog, it will execute the code line by line until the end of the file. cutoperation can stop matching rules in advance when find the correct rule. But we will spend much more time on considering when the relationship is destroyed after cut. green cut and red cut have the different effects.

Recursion/Backtrack is the most important feature in Prolog, this is the only way to iterate a list in Prolog (no for loop). For example, we can use recursion to describe a predecessor relation in family:

predecessor

The two graphs can be described as:

For All X and Z

X is a predecessor of Z

If X is a parent of Z

For All X and Z

X is a predecessor of Z if

there exists a Y such that

1. X is a parent of Y and,

2. Y is a predecessor of Z.

Translate them in Prolog:

1
2
3
4
5
6
predecessor(X,Z):-
	parent(X,Z).
	
predecessor(X,Z):-
	parent(X,Y),
	predecessor(Y,Z).

To match the rule, the backtrack is used in predecessor and it looks very simple and clear.

In my coursework, I need to traverse the London underground to find a route with fewest time.

This map is a subset of the London Underground that collected from https://tfl.gov.uk/maps/track/tube . The start station is South Ruislip which is in the left of the image, and the aim is to get to the London Bridge with least time. There are lots of search algorithms, but here i chose deep first search and implement with backtrack:

1
2
3
4
5
6
dfs(Path, Node, Cost1, [Node|Path], Cost1):- goal(Node), !.
dfs(Path, Node, Cost1, Sol, Cost):-
    station(Node, Next, TimeCost, _),
    not_member(Next, Path),
    Cost2 is Cost1 + TimeCost,
    dfs([Node|Path], Next, Cost2, Sol, Cost).

And get the result:

Deep first search result

Another feature in Prolog is the list, it is a simple structure widely used. A list can be written in Prolog as:

1
[ann, tennis, tom, skiing]

A list can be viewed as two parts:

  1. the first item,called headof the list,
  2. the remaining part of the list, called tail

So, for our example, the head is a, and the tail is:

1
[tennis, tom, skiing]

Combine with the backtrack, i can output the element of the list iteratively:

1
2
3
4
p([]).
p([X|T]):-
	write(X),nl,
	p(T).

The list operation in Prolog reminds me of the Lisp which has the similar operation in list.

It’s undenied that Prolog is fun and useful, and it can be used in many areas such as web application, graphics and machine learning. But it is really difficult to understand and master, and most of people would not spend time on it because no Prolog jobs. When Prolog borned, it was known as the programming language for Artificial Intelligence and actually it was very popular in the early wave of AI in 1970s. However during that period, artificial intelligence is just a box that fulls of different rules defined by human. What the AI do at that period was just matching rules and this was Prolog good at. Now, no rules preseted in AI.

reference:

  1. Prolog Programming for Artificial Intelligence - Ivan Bratko