Logic Programming — Rethinking The Way We Program

Louis de Benoist on 2019-12-29

Logic Programming — Rethinking The Way We Program

An introduction to some of the most fundamental concepts in logic programming (and constraint logic programming) with Prolog.

Image Source: Janeb13

Introduction

If you’ve coded before, chances are you’re familiar with an imperative language, such as Python, Java, or C++. In this paradigm, a program is a list of instructions that modify its state when executed. Although this is the most common way of programming, it isn’t the focus of this article.

Instead, we’re going to introduce a different programming paradigm, logic programming, wherein a program is a database of relations. We will lay out the main concepts as we try to solve some simple questions in one of the most popular logic languages, prolog.

Working with Relations — is Socrates mortal?

One of the most fundamental concepts in logic programming is a relation. But what exactly is a relation?

To see this more clearly, let’s look at a very simple piece of code in prolog (you can download prolog here)

mortal(X) :- man(X).

In general, relations given by “A :- B” are read as “if B then A”. The above example can be read as,“if you are man, then you are a mortal”, AKA “men are mortal”. Note that the period is just there to end the relation. Now, let’s suppose we add the following:

man(socrates).

This just states, “socrates is a man”. Now, you might think, “this is great, but what’s the point?” The reason that we define relations is that we’re then able to perform queries. In prolog, we could perform the simple query:

?- mortal(socrates).
true.

The result of the above query is that “socrates is mortal”. It used the relational database that we constructed to see that socrates is a man and, since men are mortal, then socrates must also be mortal. If we, instead, wanted to iterate through all mortal, we could have done:

?- mortal(X).
X = socrates.

In prolog, capital letters are used to represent variables.

Simple Example with Directed Graphs

To illustrate this with a more thorough example, let’s suppose we are given the following directed graph and are interested in modeling and making inferences from it.

Image Source: wikipedia

The first, natural thing that we want to do is to somehow find a representation of the graph. The most obvious way is to represent it in terms of its connections.

arrow(1,2).
arrow(1,3).
arrow(3,2).
arrow(3,4).
arrow(4,3).

This should be quite intuitive. For example, arrow(1,2) just means that there is an arrow from vertex 1 to vertex 2.

Suppose, now, that we wish to determine whether there is a path from a given node A to node B. How could we model this using logic programming? Let’s think intuitively about the problem. There are two possible cases: either A and B are neighbors, in which case we need to check if there is an arrow from A to B. Otherwise, there is a path from A to B if there is an arrow from A to some other vertex C and a path from C to B.

The first relation can easily be written as:

is_path(A,B) :- arrow(A, B). 

The second one is also fairly straightforward:

is_path(A,B) :-
     arrow(A, C),
     is_path(C, B). 

In the second case, the comma is used to represent the logical “and”. For example, there is a path from 1 to 4 because there is an arrow from 1 to 3 and a path from 3 to 4.

We can go even further and figure out the path itself. We can define is_path/3 as follows (here, the /3 just indicates that there are 3 arguments):

is_path(A, B, P). 

We now want to give conditions to determine when P is a path from A to B. To be clear, we want to define is_path/3 in such a way that we obtain the following result to the query:

?- is_path(1,4,[1,3,4]).
true

Let’s write is_path/3, one step at a time. The base case is quite simple: we just check whether P is [A, B] and if there is an arrow from A to B.

is_path(A, B, P) :-
     P  = [A, B],
     arrow(A,B). 

The other case can be done as follows:

is_path(A, B, P) :-
     P = [A|Tail],
     arrow(A, C), 
     is_path(C, B, Tail).

Now let’s carefully look at the above code. The first thing that we do is check that P is of the form: A plus a list containing the elements after A. Then, all we do is check if there is an arrow from A to some other vertex C and recursively try to see if there the tail of P is a path from C to B.

If we apply this to the previous example, is_path(1,4,[1,3,4]), we need to check whether [1,3,4] is a path from 1 to 4. We see that P can be written [1| Tail] with Tail being [3,4]. Hence, [1,3,4] is a path from 1 to 4.

Constraint Logic Programming

Up to now, we’ve been working on the Herbrand domain, but where prolog (and logic programming, in general) really shines is when working over finite domains, CLP(FD), or the reals, CLP(ℝ).

CLP(R)

Constraint logic programming over allows you to reduce and solve systems of equations over the real numbers. In prolog, we first need to import it as follows:

:- use_module(library(clpr)).

To give a simple, straightforward, example, let’s look at the following system of equations:

Representing this in prolog is very easy:

?- {X + Y = 0, X < 3, X >= 2}.

The result of this query will be the most simplified version of the above system, in this case:

{X>=2.0, X<3.0, Y= -X}.

This can be used to reduce (and solve) equations with many different constraints.

CLP(FD)

Constraint programming over finite domains is much more applicable to everyday problems, such as task scheduling, optimization, or solving puzzles (such as the n-queens problem).

Let’s introduce CLP(FD) through a simple example. We will consider the following puzzle: we need to assign integers to each letter such that

In prolog, we can write this simple program to solve the above puzzle:

:- use_module(library(clpfd)).
puzzle([V,E,R,Y] + [N,I,C,E] = [M,E,M,E,S]) :-
     Variables = [V,E,R,Y,N,I,C,M,S],
     Variables ins 0..9,
     all_different(Variables),
     (1000*V + 100*E + 10*R + Y) + 
     (1000*N + 100*I + 10*C + E) #=
     (10000*M  + 1000*E + 100*M + 10*E + S),
     V #\= 0, N #\=0, M#\=0,
     label(Variables).

We first group all of the Variables for which we need to assign numerical values. The next thing we do is specify their domain (in between 0 and 9). Then, we force them all to be different. The main part consists of placing the main constraint given by the puzzle (in CLP(FD), the syntax for the constraint =” is “#=”). Furthermore, we make sure that V, N, and M are different than 0. The last thing that we do is label, which forces prolog to spit out individual solutions, rather than printing out the final propagated constraint.

Now, we can make the following query to obtain a solution:

?- puzzle(X).
X = ([7, 6, 2, 3]+[8, 5, 4, 6]=[1, 6, 1, 6, 9])

Conclusion

In this tutorial, we have only touched the surface of what can be done with logic programming. There are more advanced applications in group theory and artificial intelligence (especially natural language processing), to name a few. Hopefully, you now have a better idea as to what the general idea of logic programming is and how it can be applied to a variety of problems.