Prolog is not that hard, part 2

[Target audience: programmers.]

Continuing our talk about Prolog, let’s improve our facts file, including some other things that “are amazing” or “sucks”:

awesome(linux).
awesome(freebsd).
awesome(openbsd).
awesome(icecream).
awesome(python).
awesome(prolog).
sucks(windows).
sucks(xml).
sucks(odata).
sucks(ldap).

Wow, that seems a little messed. Let’s organize things better by adding some more facts about all these things:

os(linux).
os(freebsd).
os(openbsd).
os(windows).
food(icecream).
technology(xml).
technology(odata).
technology(ldap).

Nice. Now Prolog can know how to categorize things better. Let’s add some “functions” (note the quotes: they are not “functions”) to our facts file. We will call them “predicates”:

awesome_os(X) :- awesome(X), os(X).

You are not alone if you think “:-” is weird. But, since the origin of that can be related to theories about “unification”, it kinds of make sense. It’s like two things (represented by “these two dots”, “:”) becoming one (“-”), you know?

This predicate says: what is an awesome operating system? Well, X is an awesome operating system if X is awesome and X is an operating system. Not hard to grasp, I believe.

Roads!

Let’s solve some problems, now! We’re going to play with paths on a “map” of ours. That’s the code. Save that on a file called “roads.pl”:

road(a, b, 10).
road(b, c, 10).
road(c, d, 100).
road(c, a, 40).
road(d, e, 100).
road(d, b, 20).
road(e, a, 30).
road(e, b, 34).
connection(A, B, Distance) :-
    road(A, B, Distance);
    road(B, A, Distance).
path(A, B, Path, Distance) :-
    connection(A, B, Distance), Path = [A, B];
    connection(A, X, D1), connection(X, B, D3), Path = [A, X, B], plus(D1, D3, Distance);
    connection(A, X, D1), connection(Y, B, D3), path(X, Y, P2, D2),
        merge([A|P2], [B], Path),
            plus(D1, D2, DA),
                plus(DA, D3, Distance).

Okaaay…

You have NO idea about what is happening, right? Not a problem. We’re going to execute this thing together to see what happens. On your terminal, load the file:

swipl -f roads.pl

And, now, ask for the path between “a” and “b”:

?- path(a, b, Path, Distance).
Path = [a, b],
Distance = 10  <Press "." to end>

It seems to be working, right? Yeah, that's a predicate meant to tell all the possible paths between A and B. And we even calculate the distance!

Now, let's see what's going on.

The map

road(a, b, 10).
road(b, c, 10).
...

We’re saying that there’s a road between points “a” and “b” whose distance equals 10 kilometers. Or miles. You decide. And there’s a road between points “b” and “c” also 10 km away. And so on.

The connections

connection(A, B, Distance) :-
    road(A, B, Distance);
    road(B, A, Distance).

That’s a very simple predicate that indicates if there’s is any direct connection between A and B (note they are variables, not the tokens “a” and “b”) in any direction.

We can call this predicate in this way:

?- connection(a, b, 10).
true <Press ".">

So, we are just using the same predicate to ask a different question: “is the distance between a and b 10 kilometers?”. Neat!

And we also can take advantage of a recursive behavior of Prolog (and that’s when the fun starts) and simply say: “you know, Mr. Prolog, I think you’re a smart guy. If I say the distance between a and b is X, could you tell me the value of X?”.

“Yes, sir!”

?- connection(a, b, X).
X = 10  <Press ".">

You see? Opposite to what happens in Python or Ruby, X doesn’t need to be adequately declared and initialized. Actually, we call “X” and unbound variable, and it’s not an error. It’s an amazing feature! Prolog realizes that and begin to search for values that satisfy X. In this case, it’s simply 10.

Interesting, huh?

Oh, and I called it “recursive” above, but, in reality, the more precise name of this feature is “backtracking”.

The paths

Our “path” predicate consists of three parts. You’ll see how I built it.

We are going to break our problem in some cases, going from the simplest to the more complex.

First case: the path between A and B is direct: there’s a road connecting them. So:

path(A, B, Path, Distance) :-
    connection(A, B, Distance), Path = [A, B].

I expect that A and B are, at first sight, bounded, while Path and Distance are unbounded. So, I make sure there’s a direct connection between A and B and, that being the case, I build a path (represented by a list): [A, B].

The list notation is quite simple and powerful. For now on, let’s say it’s almost like Python. You can build a list this way:

?- L = [1,2,3,4,5].
L = [1, 2, 3, 4, 5].

Now, let’s think about indirect connections. The simplest case of indirect connection between A and B is A — X — B, right? When there’s only one point between origin and destiny. Let’s see:

path(A, B, Path, Distance) :-
    connection(A, B, Distance), Path = [A, B];
    connection(A, X, D1), connection(X, B, D3), Path = [A, X, B], plus(D1, D3, Distance).

So, we’re saying: it’s the simples case or (“;”) the second case we thought about for now. On the line after “or” (“;”), we are saying: if there is a connection between A and X and another connection between X and B, then the path, obviously, is [A, X, B], and the distance is the sum of the distance between A and X and the distance between X and B.

(plus(1, 2, Value) will put the value 3 to the variable “Value”!)

Now, the complex case. Assuming there is a path between A and B, but there’s more than one point between both, so there must be a path between some point directly connected to A and some point directly connected to B and this path is going to conform to one of these three rules. Let’s see:

path(A, B, Path, Distance) :-
    /* Case 1: */
    connection(A, B, Distance), Path = [A, B];
    /* Case 2: */
    connection(A, X, D1), connection(X, B, D3), Path = [A, X, B], plus(D1, D3, Distance);
    /* Case 3: */
    connection(A, X, D1), connection(Y, B, D3), path(X, Y, P2, D2),
        merge([A|P2], [B], Path), /* Mark 1 */
            plus(D1, D2, DA), plus(DA, D3, Distance).

So, in plain English: there must exist a connection between A (that we know) and X (a variable we expect Prolog to fill) and a connection between B (that we know) and Y (another variable we are going to let Prolog fill) and a path between X and Y.

You see: we already know how to find a connection between these two new and unknown points, X and Y! It's our predicate “connection”!

After that, we calculate the results. At “Mark 1”, we are doing some things:

1. We create a new list with “[A|P2]”. More on this later. (We are putting A as the first element of the list P2, that is like the “Path2”, here)
2. We create another new list with “[B]”, simply putting the element B inside a list notation.
3. We merge the newly created lists one with another.
4. We save the result on the unbound (until now) variable “Path”.

So, we just add up the distances (using a helper variable “DA”) and the result is ready.

Lists, heads and tails

Prolog has a very special kind of list construction. Every list, except an empty one, is made of a head and a tail. For example:

L = [1,2,3,4,5].

This list has a head (1) and a tail ([2,3,4,5]). So it could be written this way:

L = [1|[2,3,4,5]].

Let’s try that:

?- L = [1|[2,3,4,5]].
L = [1, 2, 3, 4, 5].

See? Prolog has a special notation for heads and tails: the vertical bar (some people like to call it “pipe”…). The tail of this list, in turn, could be written in the same way:

?- L = [2|[3,4,5]].
L = [2, 3, 4, 5].

So, in the end, our list could be built this way:

?- L = [1|[2|[3|[4|[5|[]]]]]].
L = [1, 2, 3, 4, 5].

And you can play with lists. Look:

?- L = [1,2,3], [H|T] = L.
L = [1, 2, 3], /* The list from the first statement */
H = 1, /* The Head */
T = [2, 3]. /* The Tail */

Trust me: it’s very useful!

Caveats

This predicate we wrote finds all possible paths between two points. So, there will be cases where the number of combinations are infinite, since we are not checking for cycles (like A-B-C-A).

In short

Well, I think it’s enough for now.

If you want to learn more, I recommend seeing the SWI-Prolog site: http://www.swi-prolog.org/.

See ya!