New Post

Logic Programming 

Typically, when you're first taught how to code, you think about programs as a sequence of instructions. For example, to make a cup of tea, you boil the kettle, put a teabag into a mug, put the water into the mug and stir. This style of programming is called imperative programming, and it's the default style for a reason: back when programs were still being written on punchcards, the programmer had to deal with lower levels of programming like memory management by themselves – move item to memory location X, copy to register Y and so on. This programming paradigm has remained the default to this day, informing the designs of systems worth billions of dollars across the globe. However, this view of programming can also shackle our thinking, and cause us to ignore alternate paradigms that may be better suited to our particular problem. Enter: logic programming.

Fundamentally, logic programming is a sub-paradigm within a broader paradigm called declarative programming. As opposed to imperative programming, which describes how programs achieve their requirements, declarative programs describe what the program requirements are. One of the most widely used examples of this is SQL – instead of describing how to retrieve the data, you describe the constraints of the data that you wish to retrieve. Logic programming is a similar but more general system to write programs that give you answers to problems given a set of constraints.

To give you an idea of how it works, let’s break down a series of statements from one of the most influential logic programming languages, Prolog:

isAwesome(technospire).

This is the most basic kind of instruction in Prolog - a fact. Facts are used to declare true statements - in this case, that Technospire is awesome. They’re made up of a predicate, which is like a function that returns true or false, and its operands, which are the things that the predicate is true for. When we put this in a Prolog file and run it, we can then use the Prolog REPL to query the file.

?- isAwesome(technospire).

true.

?- isAwesome(ohio).

false.

As well as seeing if a given thing is awesome, we can also use Prolog to find all awesome things. This can be done by replacing the contents inside the brackets with any symbol that starts with a capital letter.

?- isAwesome(X).

X = technospire.

If we have multiple items that satisfy the predicate isAwesome, such as in the code below, we can ask for the next thing that satisfies the predicate by entering a semicolon.

isAwesome(technospire).

isAwesome(harsha).

?- isAwesome(X).

X = technospire;

X = harsha.

On its own, this isn’t particularly interesting, but this becomes very powerful once we combine it with the ability to relate different facts to each other. Take the following code:

father(harsha, ishaan).

child(X, Y) :- father(Y, X).

At the beginning, we declare the fact that Harsha is Ishaan’s father. Underneath, we have a rule that states that, for all X and Y, if Y is the father of X, X is the child of Y, with :- being our operator for logical implication in Prolog - X :- Y means Y implies X or alternatively if Y, then X. For those of you that know first order logic, this kind of statement may seem familiar, and it indeed has a direct analog in FOL:

∀x∀y[child(x, y)←father(y, x)]

Or more naturally written as:

∀x∀y[father(y, x)→child(x, y)]

In the Prolog REPL, we can find all father-child relationships:

?- father(X, Y).

X = harsha,

Y = ishaan.

We can find all fathers of Ishaan:

?- father(X, ishaan).

X = harsha.

And we can find all children of Harsha:

?- child(X, harsha).

X = ishaan.

Note that this is the same as if we were to reverse the order of arguments of the father predicate:

?- father(harsha, X).

X = ishaan.

With the ability to make facts, and the ability to logically relate these facts, we can express all kinds of systems of constraints in Prolog, making it a powerful tool for problems involving optimisation and scheduling. However, you might be wondering how you actually calculate anything or perform any computation in this language. After all, we’ve only seen Prolog’s ability to basically be a glorified database. As you’ll see, you can make it surprisingly far with just facts and relations. Let’s compute factorials in Prolog.

We start by defining our base cases for factorial.

factorial(X, 1) :- X<2. 

Similarly to before, this means that for all X, if X is lower than 2, the factorial of X is 1. So far, so good. Now we need some way of saying that the factorial of a number is equal to that number times the factorial of the predecessor of that number, which we can do as follows:

factorial(X, X*Z) :- factorial(X-1, Z).

This may look a little confusing, but all this means is that, if the factorial of X - 1 is Z, then the factorial of X is X times Z. In this way, we’re using Z as a variable as though it were an assignment - Prolog finds all Zs where factorial(X-1, Z) is true, and then we’re using the value of Z it finds to then multiply X back onto it.

We can use our factorial function like this:

?- factorial(5, X).

X = 5*((5-1)*((5-1-1)*((5-1-1-1)*1))).

Interestingly, Prolog doesn’t evaluate mathematical expressions right away. This is actually by design: like in other declarative languages such as Haskell, Prolog uses a model of evaluation called lazy evaluation, which means that expressions don’t get evaluated unless we call some operator that tells them to. The benefit of this is that we can more easily express things like infinite series, which is outside the scope of this article, but we’ll need to get around this behaviour for our factorial function. In Prolog, we can use the special predicate is to say that the left hand side is the mathematical result of the right hand side.

factorial(X, F) :- F is X*Z, Y is X-1, factorial(Y, Z).

Note: the commas on the right hand side of :- means AND.

This final statement means that if F is X*Z, Y is X-1 and Z is the factorial of Y, then F is the factorial of X. While it feels like we’re doing a very imperative assigning-things-to-other-things, the fact that these are all logical assertions means that we can actually have them any way round we want:

factorial(X, F) :- F is X*Z, Y is X-1, factorial(Y, Z).

factorial(X, F) :- Y is X-1, F is X*Z, factorial(Y, Z).

factorial(X, F) :- factorial(Y, Z), F is X*Z, Y is X-1.

are all equivalent.

Using our new factorial function:

?- factorial(5, X).

X = 120.

Even with the advent of machine learning and subsequently deep learning, logic programming has still enjoyed use in fields such as natural language processing, for defining grammars and interpreting sentences and their structures. It also shines in any problems that involve finding solutions given a set of constraints, and verification of proofs and programs. Even in the light of huge LLMs snatching headlines like GPT, it’s fun to go back and visit techniques used for solving problems that didn’t involve having the world’s data at your fingertips and, with how influential languages like Prolog have been in informing the design of subsequent languages, especially functional programming languages whose techniques have seen a rise in recent years, it’s likely that we’ll see shades of this odd programming paradigm in one form or another for years to come.