# 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:

- 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) - We
**create another new list**with “[B]”, simply putting the element B inside a list notation. - We
**merge**the newly created lists one with another. - 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!