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 firstorder 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 (SWIProlog’s logo is way less tacky tho’).
Let’s try to represent some examples involving basic concepts and structures with it.
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):


In Prolog we get:


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:


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


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


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):


And get what X can be to satisfy the conditions:


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.


path(X, Y) : X = Y; p(X, Y); p(X, Z), path(Z, Y).
, because if no path exists (e.g. substite $\text{X}$ with $\text{a}$, $\text{Y}$ with $\text{e}$), nothing can disprove the predicate and we’ll get “local stack overflow” error.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:
 Find a simple path from one vertex to another (in this example from $\text{a}$ to $\text{d}$):
 Query:
? path(a, d, P), !.
 Answer:
P = [a,b,d]
 Query:
 Find all the simple paths from one vertex to another (in this example from $\text{a}$ to $\text{e}$):
 Query:
? path(a, e, P).
 Answer:
P = [a,b,d,e]; P = [a,c,d,e]
 Query:
 Find all the reachable vertices from the given one (in this example from $\text{b}$):
 Query:
? findall(X, path(b, X, _), _V), sort(_V, V).
 Answer:
V = [b,d,e]
 Query:
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.