Logic Programming with Prolog

Introduction

I’m taking a course in mathematical logic & logic programming in my university. And I wanted to play around with first-order logic in practice.

As a bonus, I would be more familiar with a logic programming paradigm.

In order to not complicate things, I chose Prolog language and a compiler GNU Prolog (SWI-Prolog’s logo is way less tacky tho’).

Let’s try to represent some examples involving basic concepts and structures with it.

Click to see a meme.

Applications

Lists

Get the last element

One of the simplest yet not trivial operations on a singly linked list is to get its last element.

In a functional language like Haskell we would implement it like that (omit type signature and exceptions handling):

1
2

my_last [x] = x
my_last (_:xs) = my_last xs

In Prolog we get:

1
2
3
4
5

% my_last/2 for (X, Y) is true iff
% X is the last element of Y

my_last(X, [X]).
my_last(X, [_|XS]) :- my_last(X, XS).

To me, this is visually similar to the functional way. So, submitting a query ?- my_last(X, [3, 1, 7]). gives us X=7 as an answer.

Also, we can substitute “the last element” variable by hand and ask Prolog to prove/disprove our goal by submitting it. Example: ?- my_last(2, [5, 2]). returns yes.

Reverse a list

Let’s move on to another operation: reversing the list (build the list that contains the elements of the initial list in the reverse order).

Again, let’s write a functional solution first:

1
2

my_reverse [] = []
my_reverse (x:xs) = my_reverse xs ++ [x]

Now move to Prolog. First, I want to define an auxiliary predicate that drops the last elements of a list:

1
2
3
4
5
6
7

% all_but_last/2 for (X, Y) is true iff
% X is Y, but with its last element dropped off

all_but_last([], [_]).
all_but_last(X, [H|T]) :-
    all_but_last(Y, T),
    X = [H|Y].

No we can express reverse predicate in terms of the predefined predicates my_last/2 and all_but_last/2:

1
2
3
4
5
6
7

% my_reverse/2 for (X, Y) is true iff
% X is reversed Y

my_reverse([], []).
my_reverse(X, [H|T]) :-
    all_but_last(U, X), my_last(V, X),
    V = H, my_reverse(U, T).

Let’s check: ?- my_reverse(X, [1, 5, 3]). yields X = [3,5,1].

Summary

Functional way:

Accepts a list as an input, returns the reversed one

• For an empty list the answer is an empty list
• Otherwise, reverse the tail and append the currently first element to its end

Logic way:

Accepts two lists, tries to prove statement that the first list is the reversed second one

• If one of the arguments is not a constant, Prolog (not us) searches for its substitution that would satisfy out predicate.

This observation allows us to do some fancy things, one example is shown in the next subsection.

Solution from constraints

Suppose that you want to check if some list satisfying several conditions exists, and if it is, construct it:

• Its first element is 4
• Its last element is 7
• Its fourth element is 9
• It is a palindrome list if we drop the first element
• Contains value 10
• The length equals 12

We submit the following query that reflects these requirements (using predicates from standard library):

1

?- X=[4|_T], last(X, 7), nth(4, X, 9), reverse(_T, _T), member(10, X), length(X, 12).

And get what X can be to satisfy the conditions:

1
2
3
4

X = [4,7,10,9,A,B,_,B,A,9,10,7]
X = [4,7,A,9,10,B,_,B,10,9,A,7]
X = [4,7,A,9,B,10,_,10,B,9,A,7]
X = [4,7,A,9,B,C,10,C,B,9,A,7]

where A, B, C — variables that defines some elements equality constraints.

Graphs

Find a path in oriented graph

Assume we have a directed graph $G = (V, E)$ and want to find out for some $u, v \in V$ if there exists a path between $u$ and $v$ and find one in the form of

$$[w_0, w_1, \cdots, w_n],$$ where $w_0=u,\, w_n=v,\, (i \ne j \implies w_i \ne w_j)$.

Let’s introduce a predicate $\text{edge}$ that expresses the set of edges: $$\text{edge}(x, y) = x,y \in V \, \wedge \, (x,y) \in E$$

We’ll hide the fact that the arguments of the predicate are vertices in its meaning.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

% Our graph structure
% +-->b--+
% |      ↓
% a      d     e-->f
% |      ↑
% +-->c--+

edge(a, b).
edge(a, c).
edge(b, d).
edge(c, d).
edge(e, f).

% path/3 for (X, Y, P) is true iff
% P is a simple path from X to Y in the form of [X, ..., Y]

path(X, Y, P) :- path(X, Y, P, [X]).

% path/4 for (X, Y, P, Visited) is true iff
% P is a simple path from X to Y not visiting
% vertices from Visited except the first one

path(X, X, P, Visited) :- reverse(Visited, P).
path(X, Y, P, Visited) :-
    p(X, Z),
    \+ member(Z, Visited),
    path(Z, Y, P, [Z|Visited]).

In particular we’re able now to find a path from a vertex to another vertex, but additionally we can instantly do some other things now:

Conclusion

In this post we’ve seen how we can apply a logic approach to some prolems and how it’s different from imperative/functional ones.