The simplicity of Prolog

Published on January 25, 2025 25 minute read
Back to homepage

Nowadays the most popular programming languages are Python, Javascript, Java, C++, C#, Kotlin and Ruby, and the average programmer is probably familiar with one or more of these languages. It's relatively easy to switch from one to another (barring any framework specific knowledge that may be needed), since they are all imperative (and for the most part object-oriented) languages, and are thus alike in their design.

Imperative languages focus on how a problem is solved, using sequences of instructions to manipulate state. There are multiple reasons for their popularity. Firstly, they are considered easy to learn, since it's easy to visualize physical cells of memory containing values and getting updates through a set of instructions. Secondly, the computational model maps nicely to hardware, and so instructions from imperative languages can often easily be translated to machine code that can be optimized quite a lot. For the same reason, imperative languages were developed way before other programming paradigms, and so have historically speaking had a larger backing.

In contrast, declarative languages focus on describing what the problem or desired outcome is. An example of a declarative language you are probably familiar with is SQL. When specifying a SELECT-statement, you usually don't really care how the records are retrieved, only that they adhere to specified conditions. While SQL isn't normally used as a general purpose programming language I think it's quite illustrative for those otherwise unfamiliar with declarative languages (though apparently it is Turing complete). There are entire paradigms of actual general purpose programming languages that are declarative. The main two of these are functional programming and logic programming.

Source: https://xkcd.com/1033/

A programmer writing code in a functional programming language does not write statements to update some state. In fact, there is no state at all. Rather, they apply, and compose functions to transform data. And so a program is nothing more than a chain of data transformations. Examples of concepts from functional languages that are now adopted into imperative languages are functions like map, fold, and filter. The most popular example of a functional programming language is Haskell.

A programmer writing in a logic programming language does not write statements or functions. In a logic program, you only define relations between things, and then can ask a question to which the system responds with all possible answers to your question that are deducible from the relations. This has the advantage of sounding horribly vague, and incredibly tedious at the same time - but it really is not. The most popular example of a logic programming language is Prolog, at which we'll be taking a look in this article. Additionally, we'll compare the implementation of a simple application in Kotlin versus the same application in Prolog. In the coming articles, we'll use Prolog to tackle some more complicated problems.

A short introduction to logic programming

Prolog is a simple language: there are only a few language constructs, and so not a lot of moving parts to be mindful of. Well-written Prolog programs are often also simple, in the sense that they add little to no extra complexity to the problem being solved. At the same time, the language can be hard to learn, as it functions quite differently from languages people are usually already familiar with.

The only basic language constructs in Prolog are facts, rules, and queries. These are composed of logical combinations of predicates. Simply put: a fact is something that is inherently true in your program, a rule is a conditional relation "if A is true, then B is true", and a query is anything we would like to have answered according to the facts and rules in our system. Prolog finds the answers to these queries through unification, which is a sort of fancy pattern matching.

Let's start with an example: palindromes. A sequence, string or array is a palindrome if it remains unchanged if we reverse all its elements. We'll first define what list reversal means, and use it to define palindromes. For the helper predicate our goal will be to relate one list to another, such that they are each others reversal.

% reverse(A, B) relates the list A with its reversal B reverse([], []). reverse([Element|Tail], Reversed) :- reverse(Tail, ReversedTail), append(ReversedTail, [Element], Reversed). % A list is considered a palindrome if it equals its reversal palindrome(List) :- reverse(List, List).

The snippet starts with a comment. There are only single line comments in Prolog, and they start with a percentage symbol.

Next up is a fact. They are written as Fact. - a single predicate followed by a dot. In this case, we simply state that the reverse of the empty list is the empty list.

Next, we have a rule. They are written as Head :- Body., where the Head is derived if the Body is true. The Body can consist of multiple comma-separated predicates, all of which must hold (so commas denote conjunction/"and" in the rule body) in order to derive Head. In this case, we are "pattern matching" on a non-empty list in the first argument (note that [X|Y] simply means, that we are considering a list where the first element is X and the remainder is Y). Hence, this rule states that the reversal of a list of which the first element is Element and the (possibly empty) remainder is Tail, is the list Reversed if Reversed is the list we get when we reverse the Tail and then add the Element to the end of it (append(X, Y, Z) denotes that list X and Y together form list Z). Words startings with an uppercase letter or underscore are considered variables in Prolog. Variables can only be bound once.

These two clauses complete the definition of reverse, which we can now use to define palindrome. The definition of palindrome consists of a single rule which states: List is considered a palindrome if its reversal is itself.

Alright, so now what? Well, now we can ask our system questions (queries). A query starts with :- or ?-, followed by the question. If there are any variables in our query, the response to our query will tell us for which value assignment(s) of those variables the given query holds. If there are no solutions at all, we will get false, or if the query is vacuously true regardless of variables, we will get true.

Here are some example queries and corresponding results for reverse:

% Is the reverse of [1, 2, 3] the list [3, 2, 1]? Yes. :- reverse([1, 2, 3], [3, 2, 1]). true. % Is the reverse of [1,2,3] the empty list? No. :- reverse([1, 2, 3], []). false. % What is the reverse of [1, 2, 3]? [3, 2, 1]. :- reverse([1, 2, 3], X). X = [3, 2, 1]. % What is the first element of the reversal [1, 2, 3]? 3. :- reverse([1, 2, 3], [X, _, _]). X = 3. % What must hold if the reverse of [A, B, C] is [X, Y, Z]? :- reverse([A, B, C], [X, Y, Z]). A = Z, B = Y, C = X. % If the reverse is [3, 2, 1] what was the original list? :- reverse(X, [3, 2, 1]). X = [1, 2, 3]. % What are all lists A and B that are each others reversal? :- reverse(A, B). A = B, B = []; A = B, B = [_]; A = [_A, _B], B = [_B, _A]; A = [_A, _B, _C], B = [_C, _B, _A]; % Non-termination: there are infinitely many solutions

(Where _ denotes the "anonymous variable", which can be anything, but we don't care what it actually is. And _A, _B and _C are "helper" variables generated by the system to answer our question.)

This reveals a few interesting properties of Prolog: we need not specify each parameter of a predicate, we can execute our code "in multiple directions" so to speak, we can get more than one answer if there are any (separated by semicolons), we can "complete" partial solutions, and even generate every single solution - all using the same piece of code!

Similarly, here are some example queries and results for palindrome:

% Is [1, 2] a palindrome? :- palindrome([1, 2]). false. % When is [1, A] a palindrome? :- palindrome([1, A]). A = 1. % When is [1, A, B, 4 | C] a palindrome? :- palindrome([1, A, B, 4 | C]). A = 4, C = [1]; B = 4, C = [A, 1]; C = [B, A, 1]; C = [4, B, A, 1]; % Non-termination: there are infinitely many solutions % When is X a palindrome? :- palindrome(X). X = []; X = [_]; X = [_A, _A]; X = [_A, _, _A]; X = [_A, _B, _B, _A]; X = [_A, _B, _, _B, _A]; X = [_A, _B, _C, _C, _B, _A]; % Non-termination: there are infinitely many solutions

Take a moment to appreciate how little work we had to do to support all these different ways of calling these predicates. Additionally, try to come up with how you would even begin to implement such functionality (testing, completing, and generating palindromes) in a language you are already familiar with - it would probably take a lot more work!

You can play around with the code on SWISH, and try some queries yourself. Queries should be written in the bottom-right text field, you don't need to specify :- at the start. (SWISH doesn't work on all mobile devices. There should be a blue button titled "Run!" in the bottom right corner; this button does not always appear.)

Case study: authorization system

Let's consider a simple system you might be faced with building as a software engineer: a service that tracks users, roles, and rights, and is able to answer whether a user has a right through a role. We're going to look at the core application logic only, so, among other things, we abstract away database interaction, MVC structure, etc. We'll build the system twice: once in Kotlin (object-oriented programming), and once in Prolog (logic programming).

Let's start off with Kotlin.

A class diagram (generated using Mermaid) for our system could look like this: 

                ---
                  config:
                    class:
                      hideEmptyMembersBox: true
                ---
                classDiagram
                class User {
                    roles : Set~Role~
                    isAuthorized(right: Right) Boolean
                }
                class Role {
                    rights : Set~Right~
                    isAuthorized(right: Right) Boolean
                }
                class Right
                
                User --* Role : has many
                Role --* Right : has many

                classDef default fill:#f9f,stroke:#333,stroke-width:2px

Each of the three core components are modeled as a class, roles belong to users through composition, and the same holds for rights with respect to roles. Authorization checks from the user are delegated to the authorization check of the roles the user has assigned to them. An implementation could look like this:

// Class structure data class User( val name: String, val roles: Set<Role> ) { fun isAuthorized(right: Right) = roles.any { role -> role.isAuthorized(right) } } data class Role( val name: String, val rights: Set<Right> ) { fun isAuthorized(right: Right) = rights.contains(right) } data class Right(val name: String) // Example data val manage = Right("manage") val view = Right("view") val admin = Role("admin", setOf(view, manage)) val supervisor = Role("supervisor", setOf(view, manage)) val employee = Role("employee", setOf(view)) val damian = User("Damian", setOf(admin)) val kai = User("Kai", setOf(supervisor)) val nela = User("Nela", setOf(supervisor)) val anna = User("Anna", setOf(employee)) val reinier = User("Reinier", setOf(employee)) // Main method fun main() { listOf(damian, kai, nela, anna, reinier).forEach { user -> val canManage = user.isAuthorized(manage) val canView = user.isAuthorized(view) println("User: ${user.name},\tmanage: $canManage\tview: $canView") } }

You can play around with the code in the Kotlin Playground.

I would say this is the stereotypical object-oriented solution to the question. And while it's definitely an approach that solves the problem, there's a bit of "fluff" involved that unnecessarily complicates the program. For example, the fact that a User actually contains roles through composition doesn't help answer the core question for which we designed the system: is a user authorized to do a specific thing?

If you're only familiar with OOP languages, you may not even be aware of this fluff, as thinking in terms of classes and objects is an important part of the IT and CS curricula, and defining the interactions between classes is the crux of OOP. But regardless whether you're aware of it or not, the fluff is there, and it can have an impact on the adaptability of your program.

Now, let's try the same thing in Prolog.

Rather than subdivide the problem into classes, we try to define the relations that must hold in the system: what does it mean to be authorized?

% Relations authorized(User, Right) :- user_role(User, Role), role_right(Role, Right). % Example data user_role(damian, admin). user_role(kai, supervisor). user_role(nela, supervisor). user_role(anna, employee). user_role(reinier, employee). role_right(admin, _). role_right(supervisor, manage). role_right(supervisor, view). role_right(employee, view).

And we're done already! Remember: words starting with an uppercase letter are considered variables. Those starting with lowercase letters are "terms" (either predicates or atoms, atoms like admin are a type of constant). You can play around with the code on SWISH.

The definition of the authorized predicate can be read as: you can say that a User has a Right if the User has a Role, for which the Role has that Right.

As before, we can now query our Prolog system. For example, we could ask the system whether authorized(reinier, manage). holds in our program. Since this isn't true, we get false. Similarly, asking authorized(damian, manage). yields true.

And, just as in our introduction, the true strength of Prolog now comes from its generality. We can for example ask the Prolog system: authorized(nela, Right)., where the second argument Right is a variable. This yields all possible assignments to this variable for which the predicate holds, i.e. it yields all rights that nela has. Similarly, we could ask the converse: authorized(User, manage)., yielding all values of User that are authorized to manage. Informally speaking, we can execute our code in multiple directions!

In fact, we can ask the system something that's known as the most general query of a predicate, where we leave all arguments unspecified: authorized(User, Right).. This enumerates all possible solutions to the question: does User have Right? Try it out if you haven't already.

In total the authorized predicate can be called 4 different ways, since each of the 2 arguments can either be specified or be a variable. Our Kotlin system would require an function for each of these ways to be able to do the same things. Below is the resulting Kotlin code if we want to support the same functionality:

// Class structure data class User( val name: String, val roles: Set<Role> ) { fun isAuthorized(right: Right) = roles.any { role -> role.isAuthorized(right) } fun allRights() = roles.fold(mutableSetOf<Right>()) { rights, role -> rights.addAll(role.rights) rights } companion object { fun usersWithRight(users: Collection<User>, right: Right) = users.filter { it.isAuthorized(right) } fun userRightPairs(users: Collection<User>) = buildList { users.forEach { user -> user.allRights().forEach { right -> add(Pair(user, right)) } } } } } data class Role( val name: String, val rights: Set<Right> ) { fun isAuthorized(right: Right) = rights.contains(right) } data class Right(val name: String) // Example data val manage = Right("manage") val view = Right("view") val admin = Role("admin", setOf(view, manage)) val supervisor = Role("supervisor", setOf(view, manage)) val employee = Role("employee", setOf(view)) val damian = User("Damian", setOf(admin)) val kai = User("Kai", setOf(supervisor)) val nela = User("Nela", setOf(supervisor)) val anna = User("Anna", setOf(employee)) val reinier = User("Reinier", setOf(employee)) val allRights = listOf(view, manage) val allUsers = listOf(damian, kai, nela, anna, reinier) // Main method fun main() { allUsers.forEach { user -> val canManage = user.isAuthorized(manage) val canView = user.isAuthorized(view) println("User: ${user.name},\tmanage: $canManage\tview: $canView") println(user.allRights()) } allRights.forEach { right -> val users = User.usersWithRight(allUsers, right) println("Right: ${right.name}\t$users") } println(User.userRightPairs(allUsers)) }

You can play around with the code in the Kotlin Playground.

The following snippets can be considered equivalent across the systems:

Not all of these may make sense to support in an actual system, but if we did want to support them, not having to maintain multiple methods for the same piece of logic makes the Prolog code much easier to refactor in this case.

Changing requirements: accounting for time

After having run your system for some time, your clients have expressed a wish for a new functionality: rather than solely tracking the authorization state at the current moment, they want to be able to track and query it over time. So someone may only be assigned a role for a specific time frame, and a role may only have a right for a specific time frame. You should now only be considered authorized at a point in time if you have a role at that point in time that has that right at that point in time.

So we go back to the drawing board for our class diagram, and start adding associative entities (also referred to as join tables in database jargon). Rather than assigning a role directly to a user, we assign them the role for a specific time range, and similar for roles and rights. We still maintain roles and rights as entities in their own right, so we can add properties on them independently from their assignment to users and roles respectively.

All in all, this gives us the new diagram (I've omitted the new methods from the previous section for clarity): 

                ---
                  config:
                    class:
                      hideEmptyMembersBox: true
                ---
                classDiagram
                class User {
                    userRoleAssignments: Set~UserRoleAssignment~
                    isAuthorized(right: Right, timestamp: Instant) Boolean
                }
                class UserRoleAssignment {
                    validFrom: Instant
                    validTo: Instant
                    validDuring(timestamp: Instant) Boolean
                }
                class Role {
                    roleRightAssignment : Set~RoleRightAssignment~
                    isAuthorized(right: Right, timestamp: Instant) Boolean
                }
                class RoleRightAssignment {
                    validFrom: Instant
                    validTo: Instant
                    validDuring(timestamp: Instant) Boolean
                }
                class Right
                
                User -- UserRoleAssignment
                UserRoleAssignment -- Role
                Role -- RoleRightAssignment
                RoleRightAssignment -- Right

                classDef default fill:#f9f,stroke:#333,stroke-width:2px

The required code changes follow rather naturally from our new choice of class hierarchy, but are quite far-reaching. We need to add new classes UserRoleAssignment and RoleRightAssignment, replace the roles and rights fields, refactor the isAuthorized method of both User and Role by adding a time parameter, and add this parameter to each call site of either of these methods (so far, in allRights, usersWithRight, and userRightPairs - and probably only more as the system ages).

I'll leave this refactoring as an exercise to the reader.

Making the same change in our Prolog system turns out to be much simpler: since there is no separate logic for the different ways in which the predicate can be queried, there are less places that need to be refactored, just one, in fact. We add a Timestamp argument to the authorized predicate, and add two timestamps to each fact - for simplicity assume timestamps are represented by integers (for example representing Unix time). Using constraint logic programming, we can restrict the domain of Timestamp, to get:

:- use_module(library(clpfd)). % Relations authorized(User, Right, Timestamp) :- user_role(User, Role, URFrom, URTo), Timestamp #>= URFrom, Timestamp #< URTo, role_right(Role, Right, RRFrom, RRTo), Timestamp #>= RRFrom, Timestamp #< RRTo. % Example data user_role(damian, admin, 0, 300). user_role(kai, supervisor, 0, 150). user_role(nela, supervisor, 150, 300). user_role(anna, employee, 0, 200). user_role(reinier, employee, 100, 300). role_right(admin, _, 0, 300). role_right(supervisor, manage, 100, 200). role_right(supervisor, view, 0, 300). role_right(employee, view, 0, 300).

You can play around with the code on SWISH.

Since each of the three variables in the authorized predicate (User, Right, and Timestamp) can either be specified or be left unbound, the new authorized predicate now permits 23=8 modes of execution!

For example:

And again, none of these modes of execution required additional code - they all originated from the same relation! In our Kotlin system, we would first need to refactor our object model to include time, including refactoring each method that depended on it, making it harder to make such changes in the presence of more methods. And even after this refactor, we still miss the 4 extra modes of execution offered by Prolog.

Finally, note the elegance of what the last example listed above is telling us: any Timestamp within a certain range will do to make the statement true. We didn't even need to define the concept of a period! Imagine how much additional effort would be required to support this in our Kotlin system.

Wrapping up

So what should you take away from all of this?

Obviously, no programming language is "the best". Some languages may be more suitable to model specific types of systems (and even that is subjective). But there are many more factors at play that can make one language a more reasonable choice over another besides language features, including but not limited to: availability of tooling, active maintenance, community support, existing knowledge within a team/company, probability of new hirees knowing the language, start up costs, etc.

Realistically, a lot of these factors are not in favor of choosing Prolog, because while it is a simple language (there is often little additional complexity added to the problem you're solving), it is definitely not an easy language (it can have a steep learning curve due to being very different from "traditional" languages): it sometimes requires you to really think.

Sadly, after more than 50 years, it still somewhat suffers from the "bootstrapping problem". There's a vicious cycle: outside of niche fields and research, there is little usage because there aren't many programmers that know it, and there aren't many programmers that learn it because there is no demand...

Nonetheless I think there is value in knowing the language, for multiple reasons. Different paradigms offer different ways to look at a problem, and in some cases this may involve much less hassle than working in a paradigm you might already know. Some may interpret this as: "Prolog is a suitable language only when your system is simple.", but I think the converse is true: "Prolog helps keep your system simple!"

To sum it all up:

"If all you have is object-oriented programming, everything looks like an object."

So try and learn new things! If you are excited to learn more, here are some excellent resources to start you on your journey:

In my next posts, I will show some problems that lend themselves well to being solved using Prolog, so stay tuned!