An introduction to syntax and semantics
The logical paradigm that Prolog employs can be very confusing, both to the newbie programmer and the experienced C/C++ or Java guru. This is because humans tend to think in terms of algorithms and methods of solving problems when programming a computer. Once you learn to leave the solution to Prolog and concentrate on defining the problem, things will start to make a lot more sense. It is no coincidence that Prolog programmers and literature use terminlogy that is more reminiscent of database systems and SQL than of a programming language. Prolog routines are often called queries, because they return pieces of information from a knowledge base that satisfy some selection criteria, much like an SQL query does. Let us begin..
Prolog is an interpreted language and it requires a program called a Prolog listener to actually execute code. There are Prolog classes for Java and other languages so you can use Prolog code from within a regular program. The listener reads your program from a text file. Such a file is commonly referred to as a Prolog database. Again, this is no coincidence, since Prolog programming is very much like querying a traditional database. Some common listeners are Bin Prolog, AMZI! Logic Explorer and Gprolog, the GNU Prolog listener. Your Prolog database is a simple textfile that contains statements, called clauses. What type of clauses a database can contain will become clear later on.
Forget everything you think you know about programming. Now! Prolog programming is not programming in the same respect. A Prolog programmer does not contrive algorithms. A Prolog programmer only describes 'things' in predicate logic. The listener will, through an algorithm called resolution, try to find all possible 'things' that match your description. You do not need to concern yourself with the steps involved in finding that solution. If you do try, you will be setting yourself up for a monumental headache. If you want to implement algorithms, go code C! The most common newbie mistake is to try and emulate an imperative programming style. This results in pages upon pages of unintelligible code that does something proper Prolog code can do in two or three lines.
How, then, do we go about solving problems in Prolog? Simple. We specify exactly what conditions our solution has to meet in order to be satisfactory. The listener does the rest. Compare this again to querying a database: you have a collection of data and you say something like "Get me all people who work at Research & Development and that live in the Netherlands". In slightly informal predicate logic, one would say: "Get me all X that are people AND that work in R&D AND that live in the Netherlands".
What, then, is the difference between a conventional database and a Prolog database, you ask? The difference is that in a Prolog database we don't need lots of data in files to do something useful. An explanatory example: we could make a clause that describes what a prime number is, i.e. what demands a 'thing' has to meet to be a prime number. For instance, it needs to be a number, it needs to be a natural number, and it needs to be divisible only by 1 and itself. Now, we can make another clause that says: "Give me all X that are prime numbers lower than 400." From this example, we can see that, in contrast with the conventional database, we don't need a bunch of data to start with. We don't need a file or a table with lots of prime numbers in it from which we can query. We just need to define the concept of a prime number exhaustively so the listener can synthesize prime numbers.
Syntax and semantics
Let's look at some of the above in practice. Basically, your everyday Prolog database, the text file described earlier, holds two types of clauses, namely facts and rules. We will look at them later. Both are considered by the Prolog listener to be logical statements. This means that a Prolog listener can only say if some statement is True or False. There are no functions or procedures like in C.
Some code. Let's say your prolog database, named 'test.pro' looks like this:
First, we would have to get this file into the listener. This is done by doing this in the listener prompt:
Note: only use consult once per session. Use reconsult() afterward.
Now the fact 'banana(fred)' is known in the Prolog listener. This means that 'fred' (note the lowercase first letter, this tells the listener that the character sequence 'fred' is a literal value and not a variable) is now known to be a banana by the listener. If we ask the listener "banana(fred)." it will say 'yes'. If we say "banana(annie)." it will say 'no' because no fact in the database says that annie is a banana. We could also give the listener a variable. That is when things gets interesting. Variables are any sequence of characters beginning with an uppercase letter:
This basically means: "Give me all X that are bananas!". The listener will respond with:
ThisIsAVariable = 'fred'
This means: "Sure, X is a banana, but only if he is 'fred'." If we had another clause in the database saying 'annie' is a banana, pressing the semicolon key would cause the listener to backtrack and return the next X to satisfy the clause, if there exists one. So:
X = 'fred' (press ;)
X = 'annie' (press ;)
The first line says "Yes if X is 'fred'", the second says "Yes if X is 'annie'". The 'no' says that, aside from fred and annie, there are no more bananas in the database. Pretty straightforward. Statements in the database like banana(fred) and banana(annie) are called facts. Prolog accepts them literally. Of course, your listener doesn't know what a banana is. It doesn't need to. It just knows that the literal values 'fred' and 'annie' are to be considered bananas.
The above shows us how we can get our Prolog programs to return values. Note that this is considerably different from a C program, where you have functions that return values. Here, we supply variables and demands those variables have to meet. Prolog returns all values that meet those demands.
Aside from the facts, a database can contain rules. From the listener point of view, rules look the same as facts. That is, a rule can only be true or false and it is invoked in the same way as a fact. Let us imagine a rule that is true if its parameter is a prime number. We can do this:
X = 1 ;
X = 3 ;
X = 5 ;
X = 7 ;
X = 11
From the programmer's point of view, a rule looks like this:
The above means that the rule is true if all the clauses in the rule are satisfied as well. This type of logical clause is not Prolog specific. It is known as a Horn clause. The clauses can either be facts or other rules. The ':-'-operator means something like the word "if". The comma means AND. If you need an OR you could use the semicolon in some listeners but this is ugly. You'd best define another clause with the same name to handle the other case. Make sure they are mutually exclusive to prevent double answers. The rule above is true if all subrules are true. Eventually, those rules need to boil down to literals or numbers of course, otherwise the variable Parameter never gets bound to an actual value and you will get a stack overflow.
To tie it all up, let's look at some examples of Prolog programs. Since this node is no exhaustive course in Prolog but merely an aid in understanding it for those who got stuck, we will not review any of the built in functions, the datastructures or operator definitions. Read a book. Meanwhile, enjoy!
Formatting disclaimer: the code below can be pasted to a .pro file and used. The price for this is that the HTML formatting could have been prettier. I am sorry about this!
%This query is true if the first argument is a natural
%number in the range of the second argument to the
%third argument. Note that you can use an X at the
%listener but the bounds need to be provided!
%Calling inRange(X,0,100) would cause X to be bound to
%the numbers 0 through 100 successively on backtracking.
%In logical terms, the inRange rule says something like:
%"A number X is within in a range from a lower limit L to
%an upper limit H if X is equal to L (first clause) OR if
%there is a N such that (N = L + 1) AND (N < H) AND
%X is within the range from N to H."
inRange(X,X,High). %This fact says that if the first
%argument equals the second we've
% got a 'true'.
inRange(X,Low,High):- %This rule is for the rest of the
RaisedLow is Low + 1, %'is' is always true and
%assigns the outcome to
%the variable on the left
RaisedLow =< High,
%This query is true if the second argument is a factor of
%the first. Note that you can give a variable for the
%second argument. The listener will then generate all
%factors of the first argument upon backtracking. The
%reverse, generating all integers that can be divided by
%the second argument, is not possible.
isFactor(0,X). %This is so we can ignore this
U is X - 1,
Z is X mod Y,
Z = 0.
%This query is true if the first argument is a prime
%number lower than the second argument.
primeBelow(Candidate,Threshold):- %This is true if..
inRange(Candidate,0,Threshold), %..the candidate
%is a natural
%number between 0
%and the threshold
not(isFactor(Candidate,U)). %AND the candidate
%is not divisible.
%A tough one! Some fancy Prolog magic for appending lists
%that (ab)uses only pattern matching to glue lists together.
%The query is true if the third argument is a list (like
%[1,2,3,4,5]) that exists of the first two arguments glued
%together (like [1,2,3] and [4,5]). It can also generate
%all possible input lists if only the last argument is
%It can also generate the first or second list if the other
%two are given.
The above is a small demonstration of Prolog's powerful functionality. Prolog can often accomplish complex tasks in a very small amounts of code. Try and strip out my comments and see how little actual code there is. Prolog does not require you to think about the algorithms, but it does require you to be very specific about the demands your answers should meet. Have fun!
Credits: The code is mine and freshly written for this node. I have been a Prolog labcourse assistant on occasion at the Delft University of Technology, which is where I also learned Prolog. What I didn't know comes from the "Adventures in Prolog" text freely available on the Amzi! website.