Prolog Learnings: Why learn Prolog?

February 21, 2021 6-minute read

Until recently, programming a computer meant giving it a list of things to do, step by step, in order to solve a problem. In Prolog, this is no longer the case. A Prolog program can consist of a set of facts together with a set of conditions that the solution must satisfy; the computer can figure out for itself how to deduce the solution from the facts given. This is called LOGIC PROGRAMMING. Prolog is based on formal logic in the same way that FORTRAN, BASIC, and similar languages are based on arithmetic and simple algebra. Prolog solves problems by applying techniques originally developed to prove theorems in logic.

— Prolog Programming In Depth
Michael A. Covington et al.

Any developer should be exposed to the Prolog style of "Logic Programming" as it is so very different to the "procedural" style that we are so familar with. This and that Prolog sits on top of a relational database and performs automatic backtracking will bulldoze new pathways in the brain when trying to solve problems.

Lets take a look at three examples that show fact-based (or state-based) development in action.

Determine the length of a list,
Test if a list contains a specified element, and
Return the index at which the specified element is found in a list.

Length of a list

There are four states that we need to account for when determining the length of a list;

Account for the starting state,
Account for traversing a non-empty list,
Account for an empty list,
Account for traversing to the end of a list.

States (3) and (4) are the same. What is left after traversing the entire list and reaching the end is an empty list.

States (1) and (2) are the same. We are traversing a non-empty list.

This leaves only two states to account for;

Account for an empty list,
Account for traversing a non-empty list.

Before jumping in, we should cover the square bracket syntax that Prolog uses to pattern matches against lists (Elixir and Erlang use this syntax as well);

[] : An empty list.
[Element] : A list having a single element.
[Head|Rest] : Unifies the first element of the list to Head with the remaining list unified to Rest.
[One, Two, Three|Rest] : Unifies the first three elements of the list to One, Two, and Three respectively with the remaining list unified to Rest.

Length of a list

1
2
3
4
5
6
7
llength([]      , 0).       % (1)
llength([_|Rest], N1) :-    % (2)
    llength(Rest, N),
    N1 is N + 1.

?- llength([1,2,3,4], N).
N = 5.

1	For an empty list, initialize count to zero.
2	For the non-empty list, attempt to transition to an empty list.

To begin with, idiomatic Prolog code relies quite heavily on recursion (so get used to that). In the code above we use recursion to remove elements from the list and increment the count as the stack is unwound.

The predicate that handles the "non empty list" moves closer to the "empty list" state by discarding an element from the list each time it is fired (and adds one to count). Eventually the "empty list" state is reached and count is initialized to zero.

Prolog sits on top of a relational database. When predicates (similar to functions) are called, Prolog searches its internal database and fires the first matching predicate found. This means that each predicate is in effect stand-alone. This also means that the ordering of predicates is important. More specific predicates should be defined before less specific (more general) predicates in the source file.

Test if a list contains a specified element

There are three states that need to be accounted for;

An empty list and the element is not found,
The element is found,
A non-empty list and the element is not yet found.

List contains element

1
2
3
4
5
6
7
mmember([]       , _X) :- !, fail.      % (1)
mmember([X|_Rest],  X).                 % (2)
mmember([_X|Rest],  X) :-               % (3)
    mmember(Rest, X).

?- mmember([1,2,3,4,5], 3).
true.

1	An empty list, element was not found.
2	Element is found. The first element of the list X matches the element X.
3	The first element of the list does not match, discard it and continue with the Rest of the list.

Note the presence of the ! and the fail clauses in the predicate that handles the empty list.

Without the fail clause Prolog will return true unless we tell it otherwise. It matched a predicate so it has succeeded as far as it is concerned. In this case we want Prolog to return false when it cannot find a matching element. This is what fail does, it causes the predicate to fail. But in doing so it also kicks off backtracking.
Without the ! (termed a "cut"), Prolog’s default behaviour on failure is to backtrack and continue searching for an alternate matching predicate. The ! tells Prolog not to backtrack in the event of failure. We have come to the end of the list and we are certain that backtracking will not find an alternate answer.

We don’t even need to explicitly handle the empty list case as Prolog will fail to pattern match to any of the predicates that we define, so the default behaviour is to fail. In the previous "llength" example we explicitly handled the empty list because we had to return 0.

Return Element at Index

There are again three states that must be accounted for;

An empty list and the element is not found,
The element is found,
A non-empty list and the element is not yet found.

The previous examples were implemented in a non-tail call recursive style, meaning a stack frame is created each time the predicate calls itself. In this example, the recursive call is performed as the very last action and so the compiler is able to transform the recursive procedure into an iterative process (a GOTO). No additional stack frames are created. Tail call recursion is more efficient than non-tail call recursion and as an added bonus won’t blow the stack when iterating over large lists.

Always try to write in a tail call recursive style unless you know you are processing a small number of N, or your algorithm is N Log N or better.

Element at Index

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
locate_at_index_([]       , _X, _C, _I) :- !, fail.     % (1)
locate_at_index_([X|_Rest],  X,  C,  C).                % (2)
locate_at_index_([_X|Rest],  X,  C,  I) :-              % (3)
    C1 is C + 1,
    locate_at_index_(Rest, X, C1, I).

locate_at_index(Xs, X, I) :-
    locate_at_index_(Xs, X, 0, I).

?- locate_at_index([1,2,3,4,5], 4, I).
I = 3.

1	An empty list, element was not found.
2	Element is found. The first element of the list X matches the element X. Unify 'I' with the current count.
3	The first element of the list does not match, discard it and continue with the Rest of the list. Also add one to count.

We don’t even need to explicitly handle the empty list case as Prolog will fail to pattern match to any of the predicates that we define, so the default behaviour is to fail.