Prolog

Sun, Dec 01 2013

For some reason I always put Prolog in the same category of programming languages as COBOL, PL/I, or ALGOL: Ancient and not used by anyone out of their own free will unless there’s a significant paycheck involved. Well, I was wrong.

Recently I bought the book Seven Languages in Seven Weeks, mostly because I was curious about Clojure and Erlang. It also covered some of my favorites, Scala and Ruby, and it’s never bad to revisit some basics. It took me completely by surprise that the chapter about Prolog was not only fascinating but also something that could be of great use in future projects.

In this article I’ll try to explain why I think that this language is something every programmer should be aware of.

To get started it helps to think about Prolog as a reasoning engine. In an imperative language like C/C++ or Java the programmer has to provide the steps of how to solve a problem. Prolog, which stands for “Programming in Logic”, is a declarative language. Here you’ll state facts and inferences and let Prolog do the reasoning for you. The three building blocks are facts, rules and queries. The knowledge base, consisting of the facts and rules, gets compiled to byte code so it’s efficient to query it.

Let’s start with the following knowledge base:

% Facts
company(jobs, apple).
company(cook, apple).
company(gates, microsoft).

% Rule
colleague(X, Y) :- \+(X = Y), company(X, Z), company(Y, Z).

In the rule :- is called a subgoal and \+ does logical negation. In the Prolog shell that file can be loaded through ['filename']. and once the compilation is finished, queries can be executed.

| ?- company(jobs, microsoft).
no

| ?- company(jobs, apple).    
yes

| ?- colleague(jobs, jobs). 
no

| ?- colleague(jobs, gates).
no

| ?- colleague(jobs, cook).
yes

Queries can not only be answered with either yes or no. Prolog is also able to find matches for a query. Consider the following knowledge base:

device_type(iphone, phone).
device_type(nexus5, phone).
device_type(ipad, tablet).
device_type(nexus7, tablet).
device_type(nexus10, tablet).
device_type(macbook, notebook).
device_type(chromebook, notebook).
device_type(imac, desktop).

size(small, phone).
size(medium, tablet).
size(medium, notebook).
size(big, desktop).

device_size(X, Y) :- device_type(X, Z), size(Y, Z).

Besides basic queries like | ?- device_size(ipad, big). (which equals to no) we are also able to ask for specific values. The case of the first letter of a term determines if it is a constant (lowercase) or variable (uppercase).

| ?- device_type(What, tablet).
What = ipad ? ;
What = nexus7 ? ;
What = nexus10 ? ;
no

| ?- device_size(What, medium).
What = ipad ? a
What = nexus7
What = nexus10
What = macbook
What = chromebook
(1 ms) no

| ?- device_size(imac, What).
What = big
yes

Prolog does not calculate all of the possible answers at once. After every step it outputs all of the options it found (usually one) and gives you the choice to either start the next step of the calcuation with ;, calculate all of the remaining answers with a, or stop the calculation by pressing return.

Do not get confused by the trailing yes/no. Prolog answers with no if it can not find any more possible answers and with yes if it already successfully determined that the returned answers are complete.

Rules can also be recursive:

father(abe, homer).
father(homer, bart).

ancestor(X, Y) :- father(X, Y).
ancestor(X, Y) :- father(X, Z), ancestor(Z, Y).

Multiple declarations of the same rule basically serve as an or condition, and commas within a rule as an and condition.

| ?- ancestor(abe, homer).
true ? ;
(1 ms) no

| ?- ancestor(abe, bart). 
true ? ;
no

The last topic I want to touch upon is how to handle lists and tuples. Lists are specified as [1, 2, 3] and tuples as (1, 2, 3). Lists are of variable length. Tuples are containers with a fixed length.

Through unification variables and constants can be matched.

| ?- (A, B, C) = (1, 2, 3).
A = 1
B = 2
C = 3
yes

| ?- (A, 2, C) = (1, B, 3).
A = 1
B = 2
C = 3
yes

| ?- [1, 2, 3] = [X, X, Z].
no

| ?- [2, 2, 3] = [X, X, Z].
X = 2
Z = 3
yes

Lists can be deconstructed with [Head|Tail].

| ?- [a, b, c] = [Head|Tail].
Head = a
Tail = [b,c]
(1 ms) yes

| ?- [a, b, c] = [a|[Head|Tail]].
Head = b
Tail = [c]
yes

| ?- [a, b, c, d, e] = [_, _|[Head|Tail]].
Head = c
Tail = [d,e]
yes

| ?- [a, b, c, d, e] = [_, _|[Head|_]]. 
Head = c
yes

Two simple rule declarations suffice to sum up the elements of a list.

sum(0, []).
sum(Total, [Head|Tail]) :- sum(Sum, Tail), Total is Head + Sum.
| ?- sum(What, [1, 2, 3]).
What = 6 ? ;
no

This should give you a very basic idea of what Prolog is able to do.

If you are interested in exploring the topic further, you can check out exhaustive introductions like the Prolog book at Wikibooks or Learn Prolog Now!. You can also study implementations of familiar problems such as Soduko (15 loc), Towers of Hanoi (10 loc), or the Rubik’s Cube.

comments powered by Disqus