Declarative Programming with Prolog – Part 2: Unification, Recursion, and Lists


Table of Contents

  • Part 1 – Getting Started
  • Part 2 – Unification, Recursion, and Lists
  • Part 3 – Putting it All Together (Coming Soon)

Welcome back to this series on Declarative Programming with Prolog! If you haven’t already, make sure you check out the first post about getting started with Prolog, because in this post we’re going to dig deeper into some core concepts – specifically unification, recursion, and lists. Without further ado, let’s get into it.

Unification

We’ve already briefly mentioned unification and how we used it to set our variables in our rules and queries – but there’s more to it than that. At its core, unification means to make everything equal a valid result. This is different from assignment because we’re not usually telling Prolog exactly what our variables should equal – it’s figuring that out on its own.

Let’s use this example to understand more about unification:

The first two lines are nothing new – they’re just facts. We can even understand the next rule by now – especially now that you know unification is happening under the hood. When we query failed_houses with two variables, Prolog is unifying those variables to values that fit all of the subgoals – and as you can see, there are multiple combinations of values that satisfy them all:

Let’s take a look at that last rule now: little_pigs. What’s happening here is that we’re unifying the variables that are passed in to predetermined atoms – respectively straw, wood, and brick. This means that the rule will succeed only if we either pass all arguments as variables, or if we pass in arguments as atoms that already match those preset values:

However, the rule will fail if we try to pass in an atom that doesn’t match what we’re unifying the variables to:

Unification is a cool concept that’s core to how Prolog does its magic. The concepts below (as well as the last post in this series) will really help to illustrate unification more – keep following along!

Recursion

Just like in many functional languages, Prolog doesn’t support formal looping constructs like for or while loops. This might seem like a limitation at first – but fear not; Prolog handles these needs with some snazzy recursion.

We’ll use this example to illustrate recursion in Prolog:

In this example, henry is a boss to rob, who is a boss to john, who is a boss to sam. We’re going to use recursion to illustrate a relationship between these 4 individuals beyond what we can query via the facts. To do this, we’re going to use two rules called higherup – each that accepts two arguments. It is completely valid to have facts and rules that have the same predicate and arity in Prolog – and only one of them ever needs to return true for the whole query to return true.

The first higherup rule is a base case that just checks if the two arguments have a direct boss fact that links them together.

The second higherup rule is where the real recursion happens; it accepts two arguments and tries to satisfy two subgoals: one which checks if X is a boss to someone, and another that checks if that same someone is a boss to Y. Confused yet? Let’s do an example

This query to the higherup rule will check the first rule it finds – which is our base case that checks if the two variables match to one of the boss facts. In this case, they do! The rule returns successfully, which means the whole query is true since only one successful rule or fact per predicate is needed. It never queries that second rule.

That was a pretty boring example – so let’s do another one:

Here is where the real recursion happens, and I’ll list out a chain of events to explain exactly what’s happening here:

  1. Prolog queries the higherup rule with the atoms henry and sam. The order matters.
  2. The first higherup rule fails because there’s no direct boss fact for henry and sam.
  3. The second higherup rule is queried:
    • The first subgoal unifies X to henry, and (we assume) Z to rob, since that’s currently the only atom with a common fact to henry in the order the arguments were passed.
    • The second subgoal queries higherup again – this time passing in rob as the first argument and sam as the second.
  4. The first higherup rule fails again because there’s no direct boss fact for rob and sam.
  5. The second higherup rule is queried:
    • The first subgoal unifies X to rob, and (we assume) Z to john, since that’s currently the only atom with a common fact to rob in the order the arguments were passed.
    • The second subgoal queries higherup again – this time passing in john as the first argument and sam as the second.
  6. The first higherup rule passes this time, because there IS a direct boss fact for john and sam!
  7. The whole query returns true.

Overall, it took three loops over our rules for our query to return successfully. You should be careful with recursion because as with most other languages, you can easily run out of application memory if you loop too many times. That is, unless you tail-call optimize your recursion, like we did in this example.

Tail-Call Optimization

Prolog (among many other languages) has the power of tail-call optimization during recursion which means that it’s possible to maintain constant memory usage throughout – no matter how many times you loop. You could loop 2 or 200 times – and memory usage would be the same. How is this possible, you might ask? This happens when your recursive action is the very last thing called in your rule (i.e. the tail call). In our example above, the very last subgoal of our very last rule with the higherup predicate is where our recursion happens – and every time it gets to this subgoal, Prolog only needs to remember one thing about the current stack frame: Is the query true up until this point? No logic will happen in the current stack frame after the recursive call – so it doesn’t need to store any data about the current stack frame because there’s no point in doing so. Each time Prolog comes across the recursive call, it knows that it can keep going deeper and all it has to remember is that the query is true up until that point. That means that when it finally does satisfy a base case or return false – it doesn’t pop all the way up the stack chain. It just flat out returns true or false right from where the query ended.

All of this goes out the window if you place another subgoal after the recursive call, or if you place another rule/fact with the same predicate and arity after the rule with the recursive action – because in that case, Prolog would need to store the state of the current stack frame so that it could resume logic at that point. For tail-call optimization to work, the recursive action has to be the last possible action in the current stack frame.

Lists

Lastly, we need to review how lists work. In Prolog, lists are containers of variable length, while tuples are containers of fixed length. Lists are indicated by brackets ( [] ) while tuples are indicated by parentheses ( () ).

While both certainly have their use-cases, we’ll focus solely on lists in this example because they can do some neat things that tuples can’t.

We can unify values inside of lists (as well as tuples):

You’ll notice that the variables are on the other side of the equals sign. This is probably weird to see – but remember that unification is different than assignment. Prolog uses unification to make sure that everything matches to a valid value – no matter where it is. We can even spread the variables on both sides of the equals sign:

Taking things a step further, we can deconstruct a list by splitting it into a head entry and another list that makes up everything but that first head entry:

This is something that tuples can’t do – and this becomes a really powerful concept behind what all you can do with lists. You can deconstruct a tail list even further:

In fact, if you wanted to get the n-th entry of a list, you would use list deconstruction until you got the entry you wanted. Here’s how we can get the third entry in a 5-length list:

The underscores are wildcard characters in Prolog, and they will accept any value and just toss it out; they’re practically just placeholders for values. Overall this looks ugly, right? I agree, and if you’re doing things like this, then that’s normally a code smell that you may not be using Prolog in the best way.

That’s all that we’re gonna cover with lists in Prolog; you can certainly get deeper than this – but there’s still really not much to them. We’ll showcase how you can use them in real-world examples in the next post.

Final thoughts

If I had to place emphasis on understanding one core concept in Prolog (other than basic facts, rules, and queries), it would be unification. No other language has this capability quite like Prolog does – and it’s really, really powerful (and not the easiest thing to understand on the first go through). With the power of unification, we’re able to build complex rules and queries that emphasize recursion, lists, math, and much more. I hope you enjoyed this post; we reviewed a lot – and we’re going to be using every bit of knowledge we gained here in the final post of this series where we’ll build a sudoku-solver with very little logic compared to how an imperative language might approach that problem.

Stay tuned!

Note: You can check out all the examples in this post in my Prolog Demo GitHub repo!