I was browsing my overgrown to-do list in search for low-hanging fruits when I noticed a link to this talk with a tag “Prolog” that has been sitting there for over a year.

It turned out to be an amazing talk by Aja Hammerly. It gives you a perfect first glance at Prolog and it inspired me to play with it a little bit myself.

The following is a transcript of me trying to get an idea of what it’s all about.

Installing Prolog on Mac

This one is pretty straightforward. I chose SWI-Prolog. To install SWI-Prolog from brew run this:

brew tap homebrew/x11
brew install swi-prolog

Once installed you can launch Prolog REPL with swipl. As with Haskell you probably want to run it from the directory where your code is. To load file test run [test]. (. marks the end of expression).

Playing with lists

I chose list manipulation as my guinea pig following the steps of Learn You a Haskell for Great Good. I believe that the way language works with lists is a good indicator of language’s philosophy in general, so here we go.

First and simplest - let’s get a first element of the list. In Haskell you would write it like this:

first (x:_) = x

Very similar in Prolog:

first(El, [El | _]).

Few things can be observed from this function. Prolog’s variables start with capital letters. Prolog’s “functions” - facts or predicates - start with lower case letters. Prolog, as Haskell can pattern match head and tail of a list. And as in other languages underscore marks a placeholder. Note that in Prolog if predicate contains multiple underscores each one is a separate variable.

Recursion

In functional languages list manipulation naturally leads to recursion. So let’s see how would a predicate checking if something is a member of a list would look.

member(H, [H | _]).
member(X, [_ | T]):-
    member(X, T).

It looks innocent enough but let’s see how we can use it.

$> swipl
?- [test]. %% Loading a file where predicates are defined
true.
?- member(1, [1,2,3]).
true %% type . to finish

That’s what I would expect. However member can be used to find all members of the given list:

?- member(X, [1,2,3]).
X = 1 ;%% this is only one possible solution. Press 'n' to output them all
X = 2 ;
X = 3 ;
false.

Moreover, member can be used to find all lists that have given argument as an element:

?- member(1, L).
L = [1|_G282] ; %% pressing 'n'
L = [_G281, 1|_G285] ; %% pressing 'n' once more
L = [_G281, _G284, 1|_G288] .%% OK, I get the idea, pressing '.' now

In this case that would be an infinite number of lists with 1 in the first position, the second, etc.

Prolog can do this because of it’s way of pattern matching is different to what is used in Haskell or Erlang.

Pattern matching in Prolog vs Haskell

This question on Stack Overflow is where I got all my knowledge from.

In short - Prolog uses unification while Haskell uses one-way pattern matching. In practice it means that while in Haskell unbound variables can only occur on a left side of an expression, in Prolog they can be used on both sides.

Another important difference is pattern matching in Prolog tries to evaluate all possible solutions while in Haskell pattern matching stops when the match is found.

That’s why Prolog doesn’t stop after the first line of our definition of member:

member(H, [H | _]).
member(X, [_ | T]):-
    member(X, T).

But tries to evaluate every definition of the predicate.

I found that it introduces the whole new way of thinking about the problem. I spend several hours trying to think of the way to generate all possible pairs in the given list when it hit me:

pairs(X, Y, L):-
    member(X, L),
    member(Y, L),
    Y @> X.

As simple as that. In her talk Aja Hammerly shows how one can use Prolog to model logic circuits or solve logic puzzles and it really shines when it comes to problems like these. If you can think of a good problem for logic programming leave a comment!