14 Languages - Prolog

The third language - Prolog

Introduction

Prolog is a language unlike every other that I have programmed in. In Prolog one does not tell the computer "first you do this, then you do that". You define a number of facts and a number of rules connecting the facts. Then you perform queries to get answers to the questions you have. Prolog uses the facts and the rules you have defined to try to answer you questions.

Executing Prolog programs

A prolog program is run in an interpreter. I use GNU Prolog (gprolog) as that is the prolog interpreter used in the Seven Languages in Seven Weeks book.

The GNU Prolog interpreter is (surprise!) started by executing the gprolog command.

A prolog program can either be entered directly at the gprolog prompt or be loaded into the interpreter using the command ['filename'] which will load the file filename.pl from the current directory.

Basic Syntax

Facts

A fact is a statement that something, e.g. lars, is (or has, or does or...) something, e.g. a programmer. To express the fact "Lars works as a programmer", the following Prolog code can be used occupation(lars, programmer).

Note the dot at the end of the statement. Every statement in Prolog is ended by a dot. If one forgets the dot, the Prolog interpreter does not display anything. Its cursor just continues to blink to indicate that more input is needed.

Another important thing to notice is the case of the first letter of "lars" and "programmer" in the example above. The lowercase letters of those words means that the values are constant. In Prolog speak, they are atoms. If the first letter should have been a capital letter they would instead be variables.

Rules (Inferences)

A rule is a combination of the stated rules to form a conclusion about something. E.g. a person like coca cola if that person is a programmer.

A rule is defined using the :- operator. To the left of the operator is the name of the rule and the list of parameters it takes. Note that the first letter of each parameter should be a capital one. If not, they become atoms instead of variables, which makes it impossible to pass a value for that parameter (other than the constant value of the atom).

An example of a rule:
likes_coca_cola(X) :- occupation(X, programmer).

In the listing above, we create a rule that says that every person who works as a programmer likes coca cola.

Rules are also called inferences.

It is possible to define rules having the same name, but taking different number of arguments. E.g. both a calculate(X) rule and a calculate(X, Y) rule can exist. In prolog speak the first of those rules are called calculate/1 and the second calculate/2. More generally, a rule is written as nameOfRule/numberOfParamsItTakes.

Queries

The facts and rules form a kind of world. Queries can be used to ask questions about that world to get the answers one is interested in. E.g. Does Lars like Coca Cola?

To obtain answers to queries are the whole point of using Prolog. They are the end products of a Prolog program.

To create a query to determine if lars likes coca cola, we invoke the likes_coca_cola rule and pass the atom lars as parameter:

| ?- likes_coca_cola(lars).
yes

lars gets bound to the variable X in the rule, and we see that, as expected, lars likes coca cola.

We can also ask Prolog to find all people that like coca cola. We do this by specifying a variable instead of an atom in the query:

| ?- likes_coca_cola(X).   

X = lars

yes

We see that Prolog again has determined that lars likes coca cola. In this example, we've only defines one programmer so Prolog terminates the execution of the query directly after having found that lars matches the query. If there would have been other programmers defines, Prolog would reply with the prompt ? after having displayed X = lars. If one then presses the ; key, the next programmer would have been printed and so on until all programmers would have been displayed.

Let's define another programmer and run the query again:

occupation(lars, programmer).
occupation(per, programmer).
likes_coca_cola(X) :- occupation(X, programmer).
...
| ?- likes_coca_cola(X).
X = lars ? ;
X = per
yes
| ?- 

Atoms

As mentioned above, atoms are things that are constant. They are not like constants in many other languages that have names and values. An atoms does not have a value other than its name. In that sense, an atom is more like a symbol i Ruby.

Variables

Also as mentioned above, variables are things that may take different values. They are specified in the parameter list of rules and can be used in the body of the rule which parameter list they are part of.

Variables can also be used in a query. In that case, Prolog tries to find all values that the variable legally could take given the defined facts and rules, and prints out those values.

Unification

Unification is a process in which Prolog tries to find values for the variables in two structures so that the structures become equal. When we issue the query likes_coca_cola(X). above, Prolog tries to find values to the variable X so that the rule likes_coca_cola(X) :- occupation(X, programmer). will be fulfilled. As we have defined the facts occupation(lars, programmer) and occupation(per, programmer), the valid values which Prolog finds are lars and per. The process which Prolog uses to find these matches is called unification.

Comments

Comments are created using the /* This is a comment.*/ syntax.

Tuples

Tuples are fixed-length datastructures. They are created using parenthesis: (1,2,3).

Two tuples unifies if they have the same length and each of the corresponding elements unify. E.g. (1,2,3) = (1,2,3)

Variables can be used when unifying tuples and it does not matter which side of the equals sign that the variables are located on.

| ?- (X,2,Z)=(1,Y,3).

X = 1
Y = 2
Z = 3

(1 ms) yes

We see that (as in all unification) Prolog tries to make both of the structures on the opposite sides of the equal sign equal and finds the solution X=1, Y=2 and Z=3.

Lists

Lists are datastructures that can hold a variable number of items. Lists are created using brackets: [1,2,3] and are unified in the same manner as tuples:

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

X = 1
Y = 2
Z = 3

yes

An interesting thing with lists is that they can be deconstructed in a head part consisting of the first element and a tail part containing the rest of the list. Such deconstruction can be by unifying a list using the [Head|Tail] construct. Of course, the variable names are arbitrary. An example of deconstructing a list:

| ?- [1,2,3]=[Head|Tail].

Head = 1
Tail = [2,3]

yes

If the list only contains one element, the tail unifies to the empty list:

| ?- [1]=[Head|Tail].    

Head = 1
Tail = []

yes

The underscore wild card

When unifying lists or tuples, an underscore can be used as a wild card to indicate that an element of a specific position or a tail is not interesting. This is useful when one wants to access some other position in a list but the first. An example: to access the second element in a list we may do the following:

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

X = 2

yes

Here we say that we are not interested in the first element but please assign the second element to the variable X, and by the way, we're not interested in the rest of the list (the tail) either.

Recursion

A rule can recursively call itself. To make that work, one needs to have a non-recursive base rule where the recursive calls will end up. Then we can have other rules of the same name that in addition to performing a recursive call also performs some other action that changes the params used in the recursive call. Other actions can of course also be performed, both before and after the recursive call.

One of the standard problems when discussing recursion is computing a Fibonacci number. So let's try that. A naive implementation of this problem in Prolog can look like this:

fibonacci(0, 1).
fibonacci(1, 1).
fibonacci(N, Result) :- 
  N1 is N - 1, 
  N2 is N - 2, 
  fibonacci(N1, R1), 
  fibonacci(N2, R2), 
  Result is R1 + R2.

In the program two facts and one rule is defined. First we have the base cases: the first Fibonacci number == 1 and the second Fibonacci number == 1. Then we have the general case which is taken care of by defining a rule that calls itself, or one of the base cases, recursively.

We see that the rule, and the facts. takes two parameters: the ordinal deciding which Fibonacci number to calculate and the calculated value. Unification then takes care of making the two sides of the rule equal and after that has been performed, the result can be found in the Result variable.

To me, this feels kind of strange. Result acts as an output parameter in some other languages (like Ada, if I remember correctly), but I'm not sure that is the correct way of thinking. Or rather, I'm certain that this is not the way to think about it. I think that a more proper way to think about it is that unification makes the two sides of the rule equal, and afterwards, as a convenient side-effect, the Result parameter will contain the result that one wanted to obtain. Prolog is a peculiar language.

I the listing above the is operator has been used. It is used when performing arithmetic, and it acts like an assignment operator. Of course, it is not described in this way in the documentation I've found. In there, its workings is described as "first the right hand side is evaluated, then the left hand side and right hand side are unified".

My first attempt of writing a Fibonacci program in Prolog did not include the variables N1 and N2. Instead I tried to pass N - 1 and N - 2 directly in the recursive call to fibonacci(), This, however, did not work. Right now, I don't know why. It most certainly has a logical explanation. It's Prolog after all.

Tail Recursion

Is there a problem with the problem with the program in listing 1 above? Yes, it is. The recursive call is not the last statements in the rule, I.e. the rule is not tail recursive. Why is this a problem then? It is a problem because when performing very many nested recursive calls, the stack of the program may run out of space, which makes the program terminate with an exception. If the program is written in a tail-recursive manner, a modestly potent interpreter/compiler can rearrange the program and create an iterative variant from the recursive one, and by doing that, avoid running out of stack space.

So, how do we create a tail-recursive variant of the Fibonacci program above? Well, if we start calculating the first and second Fibonacci number, we can use those numbers to calculate the the third number and so on. So it we add two more parameters to the fib() rule, where the first is the i:th Fibonacci number and the second is the (i+1):th Fibonacci number we can use those to calculate the (i+2):th number, which then can be passed to the next recursive call (together with the (i+1):th). This means that when we have perfomed n iterations, we have the answer in the first of those new parameters, namely the n:th Fibonacci number.

The rule can look like this:

fib(DownCounter, ValueForN, ValueForNPlus1, FinalResult) :- 
                                                  NextDownCounter is DownCounter - 1, 
                                                  ValueForNPlus2 is ValueForN + ValueForNPlus1, 
                                                  fib(NextDownCounter, ValueForNPlus1, ValueForNPlus2, FinalResult).

Pretty straight forward, eh? But what's the FinalResult parameter we just passes through to the recursive invocations? It is the parameter in we will put the final result. But it it not used? That's because we haven't defined the base case yet (which means that the recursion will continue forever, or at least until we get a stack overflow exception). So let's define the base case.

We have performed n recursive calls when the DownCounter reaches 0. Thus, we create a case where we put 0 instead of DownlinkCounter. Then we said that we had the result in the first new parameter, ValueForNPlus1. The second new parameter, we're not really interested in as it contains the (n+1):th Fibonacci number, so let's make it clear that we don't care about that value by putting an underscore in that position instead of ValueForNPlus1. The fourth and final parameter is where we want to put the result. The base case thus becomes:

fib(0, FinalResult, _, FinalResult).

We could be finished here. For example, to calculate the sixth Fibonacci number we could invoke the rule like this

| ?- fib(6, 0, 1, FinalResult).

FinalResult = 8 ?

Is is however possible to make a slight simplification. If we use the fib/4 rule directly, we always have to specify 0 as the second parameter and 1 as the third parameter. We therefore create a fib/2 rule that only hard-codes these values:

fib(DownCounter, FinalResult) :- fib(DownCounter, 0, 1, FinalResult).

Using this rule, we can calculate the sixth Fibonacci number like this:

| ?- fib(6, FinalResult).

FinalResult = 8 ?

The full tail-recursive Fibonacci program looks like this:

fib(0, FinalResult, _, FinalResult).
fib(DownCounter, ValueForN, ValueForNPlus1, FinalResult) :- 
                                                  NextDownCounter is DownCounter - 1, 
                                                  ValueForNPlus2 is ValueForN + ValueForNPlus1, 
                                                  fib(NextDownCounter, ValueForNPlus1, ValueForNPlus2, FinalResult).
fib(DownCounter, FinalResult) :- fib(DownCounter, 0, 1, FinalResult).

Hello World!

A simple hello world program (are there any others?) can look like this in Prolog:

helloWorld :- write('Hello World!'), nl.

When invoked, the output looks like this:

| ?- helloWorld.
Hello World!

yes

Features

Unification. It is so engraved into the language that it hardly can be called a feature. But I do it anyway ;) It it immensely powerful for certain kinds of problems.

As a small demonstration of the power of Prolog and unification, let's write a small program that can solve a sudoku.

Gotchas

• Using := instead of :- when starting a rule.
• Fail to remember to end each fact or rule with a dot.
• Using an atom instead of a variable when performing a query. I.e. starting a word with a lowercase letter when an uppercase letter should have been used.

FizzBuzz in Prolog

An implementation of the FizzBuzz kata in Prolog can look like this:

/* Start at 1.*/
fizzBuzz :- fizzBuzz(1).

/* When we reach 101, we stop. */
fizzBuzz(101).

/* Rule resolving to true for numbers dividable by both 3 and 5. */
fizzBuzz(N) :- 
    X is N mod 3,  
    Y is N mod 5,
    X == 0, 
    Y == 0,
    writeAndPerformNextCall(N, 'FizzBuzz').

/* Rule resolving to true for numbers dividable by 3 but not 5. */
fizzBuzz(N) :- 
    X is N mod 3,  
    Y is N mod 5,
    X == 0, 
    Y \= 0,
    writeAndPerformNextCall(N, 'Fizz').

/* Rule resolving to true for numbers dividable by 5 but not 3. */
fizzBuzz(N) :- 
    X is N mod 3,  
    Y is N mod 5,
    X \= 0, 
    Y == 0,
    writeAndPerformNextCall(N, 'Buzz').

/* Rule resolving to true for numbers not  by neither 3 nor 5. */
fizzBuzz(N) :- 
    X is N mod 3,  
    Y is N mod 5,
    X \= 0, 
    Y \= 0,
    writeAndPerformNextCall(N, N).

/* Rule that prints the specified text and performs the next recursive call with the next integer in the series.*/
writeAndPerformNextCall(N, Txt) :-
    write(Txt), 
    nl, 
    NPlus1 is N + 1,
    fizzBuzz(NPlus1).

In the program above, we've defined one rule for each of the four cases:

1. Number dividable by both 3 and 5.
2. Number dividable by both 3 but not 5.
3. Number dividable by both 5 but not 3.
4. Number not dividable by 3 or 5.

I think that the FizzBuzz program in Prolog is quite neat. Four rules govern the four cases that can happen, and recursive calls take us to the next number in the series. It was not very easy for me to reach the solution above however. I must say that the Prolog-version of the FizzBuzz-kata was the one that, by far, has taken me the longest time to write. Otherwise, the Kata is very simple and straightforward to write. The time it took at lot longer to find an acceptable solution. I think that this is so because I'm very unused to thinking "The Prolog Way".

What I like about Prolog

Solutions to certain kinds of problems, like solving a Sudoku, can be expressed extremely beautifully in Prolog. Once one understands unification that is. Such programs often become short, concise and to the point. Sometimes seeing a Prolog program producing a solution to a problem feels like magic.

Also on the plus side, there is a lot of Prolog related material on the Net, much, much more than about Io.

What I don't like about Prolog

Prolog has a steep learning curve. It is not easy for a beginner to learn the language. If one checks out some Prolog programs written by more experienced Prolog programmers, those are often terse and very hard to understand.

Also, Prolog does not feels like an all-purpose programming language. It is aimed at logic programming, for which it is extremely well suited, and when one has another type of problem, one should perhaps choose another language. This is not criticism against Prolog. It does what what it was build for very well.

Onwards, upwards

It was fun to play around with Prolog! I'm not certain, however, that I ever will use it in a work related context. Now its time for a language which I have a fair chance of using at work. At least in a couple of years from now. Scala!

Previous parts in the series

Links