Learning Prolog - Unification for equality and World Peace.

λ March 14, 2021
Tags: prolog

TL;DR – If I had to sum up what makes logic programming with Prolog so radically different from all of the other paradigms, it would be to say that you tell Prolog what the ‘answer’ looks like but not how to arrive at it; that it manages to figure out on its own. You do not tell it how to arrive at the solution Magic? No, just clever implementation machinery.

SWI Prolog.

The distribution that I use is SWI Prolog, it is very mature, very stable and absolutely packed with stuff. The community is fantastic, the atmosphere is fantastic and the documentation is also fantastic, in fact it’s hard to knock it at all really. I have had nothing but great answers on the forums and a lot of the people on it are either the creator (Jan Wielemaker) or actively engaged in helping to develop it / use it.

Where to start ?

Before you can begin to ‘grok’ Prolog you have to learn a few new concepts that, probably from your current function or imperative background, will take some time and practice to take on board, I know I had some serious head-scratching fun with it when I started my journey with it.

Prolog is fundamentally about proving things are true or false. You feed it facts and rules and then you pose it queries. But… you can also write programs that have a full user interface (the default SWI tools like the editor are all written in SWI Prolog using a cross-platform library they developed), or you can use OpenGL or any other library thanks to the foreign-function interface.

We will start with unification as that is the core concept; attempting to match two terms to see if they are capable of being made to represent the same structure. Forget any notions you have of what = means in your current favourite language!

UNIFICATION 101

Yes, I shouted it because it is so important. The first thing to take on board is that this operation uses the = operator which in most languages is used for assignment, in Prolog the = means unify. The easiest way to explain it is with some simple examples but in the real world, the structures on either side of the = can be very very complex but the principle is the same.

Rule 1: An unbound variable matches anything.

This means that if the left side or right side of the = operator is a variable that currently has no value, then it will take on the value of the opposite side, this will then mean that the two side unified, and the result of the unification was success and the next predicate after will be executed, or if that was the last part of a predicate, the predicate has now succeeded as all previous steps must also have succeeded to get that far. For example, the following are all successful applications of the unification operator:

? X = [1, 2, 3]
X = [1, 2, 3].
 
? 42 = Z.
Z = 42.

? "Hello" = "World".
false.

The ? is the REPL input prompt, the next line is the response. The last example is false because Hello cannot be equal to World, they are two constants that differ in value and thus will never be equal.

So, if one side is currently unbound, after unification it will have the same value as the other side.

One of the more powerful aspects is the fact that, unlike imperative languages where assignment tends to be from right to left, in Prolog it doesn’t matter, unification is NOT assignment and you need to take that on-board pretty early on or it gets confusing. If you typed something like this:

? 42 = 42.
true.

What it means is that the two side are the same term, absolutely no numerical comparison was done at all. There is only one way to do arithmetic in Prolog (two if you use constraints) and that is with the is keyword but I am not going down that road.

Principal Functors and Atoms

In Prolog, defining a data structure required no effort and you literally make it up on the spot. The number of data types in Prolog are pretty small, but remember we are dealing with a symbolic processing system that seeks to prove something is the same as something else, true or false, succeed or fail. An atom is typically a lowercase string with no spaces, it starts with a lowercase letter and after that it is usually more mixed letters, digits and underscores. Some dialects MAY be different but that’s a good rule of thumb. If you want an atom with spaces or anything funky then you place it between single quotes:

a               % as simple as it gets
hello_World     % another simple atom
'Yeah Baby :)'  % more complex

Atoms are held internally in a table, the same atom used many times incurs no extra overhead other than the reference to it. If you have used Elixir or Erlang, the concept of atoms is pretty much the same.

Now we come to data structures. The simplest data structure is this:

hacker(fred).   % fred is a hacker 

It is a fact, also called a ground term, ground as in ground level not coffee beans. It means that there are no variables in the term, the principle functor is the atom hacker and the single argument is an atom called fred. A ground term is a fact, it states something within the Prolog database, or knowledge base as it can be called. Any fact not in the database is assumed false, this is called the closed world assumption.

When you see Prolog code, you have to remember that what you are looking at is not code as an imperative or functional system would be but as a logical system is; the code is symbolic, it is declaring something loud and proud and the sole purpose of the Prolog engine is to see if something is true or false and can it be unified. Something is either true or false, simple as that.

The following code looks like arithmetic is being done but not so!

X = 1 + 2 + 3.

is parsed and stored internally as

X = +(1 +(2, 3)).

and that that is NOT calling the addition operator as you may think but is just the atom + as a principle functor that has two arguments because it is in fact a built-in binary operator but right now, it is just a data structure like any other. It is not until run time that anything happens with it. The real slim shady arithmetic is done with is, this code does do what you think and is as how an imperative program would work:

? X is 1 + 2 + 3.
X = 6.

Here are some more complex data structures, note that nesting a structure is nothing more than repetition, the system does not check that they have the same structure as no formal definition exists, it’s all down to you:

hacker('fr3d', email("fredsemail@address.com", 300)).
employee(233242, 'Software', 'Fred', 'Smith').  % or more explicitly...
employee(id(233242), dept('Software'), name('Fred'), surname('Smith')).

Unification as extraction

Let’s say that we have done a query and we want to get the department name from a variable we know contains an employee, now we can begin to see how unification can be used, and it works either way around:

% first we set the result
QueryResult = employee(id(233242), dept('Software'), name('Fred'), surname('Smith')).

% now we use unification to 'shape match out' what we want
employee(Id, Dept, FirstName, LastName) = QueryResult.

% or, unification is bi-directional after all!
QueryResult = employee(Id, Dept, FirstName, LastName).

The above is the example, here is how you HAVE to enter at the REPL, this is because after executing the first line, the REPL forgets so we have to ask for the query whilst the variable is still bound to a value, we do this by chaining the statements with a comma, read as ‘AND’, the REPL shows us the extracted values from the query result:

?- QueryResult = employee(id(233242), dept('Software'),
                    name('Fred'), surname('Smith')),
% unify the result with extraction place holders...
employee(Id,Department,Firstname,Lastname) = QueryResult.

% the system prints out all the variables now, and their values...
QueryResult = employee(id(233242), dept('Software'), name('Fred'), surname('Smith')),
Id = id(233242),
Department = dept('Software'),
Firstname = name('Fred'),
Lastname = surname('Smith').

So, we can see that because we placed unbound values into the employee principal functor that the values in those positions became bound to the variables. You -could- call this a destructuring bind in other languages but that’s not what we are doing really, but if it helps to think that way, fair enough. Let’s do even more focused unification to remove the pointless principal functors, I mean, we already know it is a Department name etc so lets remove them now:

?- QueryResult = employee(id(233242), dept('Software'),
                    name('Fred'), surname('Smith')),
% unify the result with extraction place holders...
employee(id(Id),dept(Department),name(Firstname),surname(Lastname)) = QueryResult.

% the system prints out all the variables now, and their values...
QueryResult = employee(id(233242), dept('Software'), name('Fred'), surname('Smith')),
Id = 233242,
Department = 'Software',
Firstname = 'Fred',
Lastname = 'Smith'.

See the subtle difference? By placing the principal functor into the unification pattern, the unbound variables are now situated at the same place as the core values, which is how we got the above answers. You can now do what you will with those variables.

Construction with Unification

Let’s say we wanted to go the other way, to be able to pass in some raw details and have something passed back that is a functor, for example let’s say we just asked the user for some details and we are about to create a new employee record, we might declare the following predicate in the knowledge base:

%        in  in    in     in      in     out
make_emp(ID, Dept, Name, Surname, Wages, Record) :-
    Record = employee(ID, dept(Dept),
                      name(Name), surname(Surname),
                      salary(Wages)).

% calling it with some raw values...
%                                                     -unbound-
make_emp(3214234, 'Gardening', 'Meg', 'Griffin', 100, RECORD). 
RECORD = employee(3214234, dept('Gardening'), name('Meg'), surname('Griffin'), salary(100)).

In my first article I said that in Prolog there are only conventions for argument ordering, going from left to right we have inputs then outputs, you can see that all of the above are inputs except for Record which has been unified with the pattern on the right because it was unbound on entry and thus the functor that we created on the left hand side had no choice but to match. The new value of Record is thus the value of this functor, which is then available to the caller. Awesome stuff. But it gets more awesome, we COULD decide to do the unification in the head of the clause like this, which reads even more naturally:

%        in  in    in     in      in
make_emp(ID, Dept, Name, Surname, Wages,
    % out - because the CALLER will have given an unbound variable so the
    % unification happens -here- in the head of the clause! Wow.
    employee(ID, dept(Dept),
             name(Name), surname(Surname),
            salary(Wages))).

% calling it with some raw values...
%                                                     -unbound-
make_emp(3214234, 'Gardening', 'Meg', 'Griffin', 100, RECORD). 
RECORD = employee(3214234, dept('Gardening'), name('Meg'), surname('Griffin'), salary(100)).

This means that the pattern matched and that we didn’t even need to unify with a new Variable, it means that we can even perform pattern matching and unification at the same time in the head of the clause. This is powerful stuff.

Meta-Level Stuff with Functors

Prolog has an operator, =.. pronounced univ and, combined with unification it either creates a functor or decomposes a functor into its principal functor name and arguments, as we can see here:

?- QueryResult = employee(id(233242), dept('Software'),
                    name('Fred'), surname('Smith')),
QueryResult =.. Parts.

QueryResult = employee(id(233242), dept('Software'), name('Fred'), surname('Smith')),
Parts = [employee, id(233242), dept('Software'), name('Fred'), surname('Smith')].

He we see that Parts is now a list, the first element is the principle functor of the opposite side term, and the remaining elements of the list are the arguments to the functor.

This means that we can build a complex functor at run time, and then like all good reflective programming languages we could then call that just like any other predicate. This allows for incredibly powerful programming techniques as documented in more detail on the SWI site.

Unification can be terribly clever but also confusing especially if you make a mistake, but like any language, it comes with experience. Unification can cope with very complex terms, matching whole lists for example, as a parting example, consider this, manually laid out for clarity:

% Set up a term
% Now we want the second entry of the list of contacts
? Record = emp(09874325, department('Sales'),
           contacts(['fred', 'mary', 'bill']),
        salary(100000)),
% using `_` means discard/don't care/don't want it and all we need to
% is unify through the list, it WILL fail if the list is too short
Record = emp(_, _, contacts([_, Mary|_]), _).

Record = emp(9874325, department('Sales'), contacts([fred, mary, bill]), salary(100000)),
Mary = mary.

So there you go, the variable Mary is now bound to the atom mary as we wanted. Unification is -the core skill- to master when you first start with Prolog, it can get as jiggy as you need and I have barely touched the surface but I hope you’ve gotten some idea of how powerful a feature it is.

I freaking love Prolog. Finally I found something that thinks like I do.

In my next article on unification I will show some more examples now that we have a basic understanding of what it is, what it does, and what you can do with it. Once we ’ve covered that then I plan to move on to the concept of difference lists which are an incredibly clever and powerful way of allowing the Prolog engine to seemingly work in multiple directions at once, the classic case is the append/3 predicate which can be used to split lists, or join them depending upon what state the input variables are in.

Some light list reading!

See you then.