A Short Introduction to Prolog

Prolog is a language that tries to apply ideas from logic to the task of programming. Here is a short guide to some of the features of the language. It can be used as a starting point for further exploration.

Installing

There are several implementations of Prolog, so you first need to decide what is the best suited for your situation. If you never used Prolog, probably the easiest way to start is installing SWI-Prolog, a free source implementation that is widely used. There are versions for all major operating systems, including Linux, Windows, and Mac OS X.

In my system, SWI Prolog installs a binary at

/opt/local/bin/swipl

Once you run the executable using a terminal window, you will get a prompt. Then you can type something like:

A is 1 + 1.
A = 2.

Here, “is” is a keyword that unifies the result of 1 + 1 with the free variable A. When you type enter, the line is executed and the result A = 2 is printed.

Notice that in the example above I talked about unification, instead of assignment. A particularity of Prolog is that unification, the process of finding a “matching” parameter for an argument, is the main mechanism for attributing values.

For a single variable, unification is the temporary binding of a value, based on the context where the variable occurs. A single variable can unify to one or more values during the execution of a program. Unlike assignment, a unification cannot be undone in the same clause unless bracktrack occurs.

Clauses

Prolog is a logic language. Expressions have a logical meaning, and the result of any expression is a boolean value. The basic difference of a language like Prolog to procedural languages is that we need to get used to translate procedural code into the required logical style. Logical expressions used by prolog are by necessity more declarative than an equivalent program written in C, for example.

The basic unit of a Prolog program is a clause. A clause is a single statement with an antecedent and a possibly empty set of consequents. Logic theory calls a statement like this a Horn clause. Thus, one can say

descendent(A, C) :- descendent(A, B), descendent(B, C).

This clause is just stating that a way of somebody being a descendent of another is to be a descendent of a descendent. This can also be explained as saying that “descendent” is a transitive relation. The rule above is true for any transitive relation.

Notice that variables always start with an upper-case letter. Constants, on the other hand, start with a lower-case letter. So, if we add the following information:

descendent(john, mary).
descendent(mary, james).

Prolog will be able to deduct, according to the rule above, that “james” is a descendent of “john”. Relations such as the last two presented above are called facts, because they are just stating our current knowedge — we already know that Mary is a descendant of John and that James descends from Mary.

Prolog implementations generaly separate statements available for a program into two kinds of files. Database files store a set of facts. It is not hard to see that such database files have a lot in common with traditional databases: they represent a set of relations, and each fact can be viewed as a database record. You can already see that Prolog provides a really nice representation for data using the basic mechanisms of the language.

Then, another set of files can be used to create queries and general rules that will apply to the data. This is where the “programmatic” part of your code will be stored. Some implementations let you mix facts and rules as necessary.

Recursion and Conditional Behavior

Recursive clauses are the main technique that Prolog uses to support repetitive behavior. However, to control recursion one needs some kind of conditional selection. Prolog implements conditionals through unification and backtrack.

Unification, as hinted above, is the process of matching an argument to a set of logical variables. The form of the variables can be used by Prolog to determine the best matching. For example, this is the standard way of working with lists:

size([], 0).
size([A|B], X) :- size(B, Y), X is Y + 1.

The above definitions use matching to answer a question about the size of a list. A list in Prolog is represented by elements enclosed in square brackets. The notation [A|B] means that A is the first element (the head) of the list, and B is the list of remaining elements (the tail). The notation [] represents the empty list. Thus, the rules above present two cases: an empty list and a list that has a head and a tail. If Prolog can match the list with one of the cases, then the corresponding rule is executed.

To use this example, type the two clauses above in a file, say listsize.pl. Then, in the Prolog prompt, use the command

consult(listsize).

You can now ask questions based on these rules:

size([1,2,3], S).
S = 3.

Notice that the first clause works just by unification: When an empty list is found as the first argument, the variable passed as the second argument is matched to 0, therefore a solution is immediately available.

When the second clause is used, however, Prolog applies a recursive call to determine the size of the tail, then adds 1 to that value in order to determine the size of the list. When this happens, all variables have an assigned value and a solution is returned.

Prolog can use the process above to compute not only one, but several solutions for a query, if more than one exists. For example, if we know the facts

employee(john, company1).
employee(mary, company1).

Then we can enter the following question

employee(X, company1).

In that case, there are multiple answers. Prolog, by default, will return one answer at a time. Each time a user can type the “;” character and receive a new solution. Another option could be to collect all solutions in a list, for example, before displaying them.

Conclusion

This is just a short tutorial on the features of Prolog. The language provides a lot more, but you can use the information above as a starting point. Above all, Prolog is a nice tool to play with algorithms that would be too complicated to use in more traditional languages. It is a great way to have fun and learn a different paradigm for computation.

Similar Posts:

  • Digg
  • del.icio.us
  • Facebook
  • Google Bookmarks
  • E-mail this story to a friend!
  • HackerNews
  • Reddit
  • StumbleUpon
  • Twitter

Post a Comment