What does our "Hello World" program look like in a logical programming language? It is just a single line.
| ?- write('Hello World').
Hello World
yesThe program itself does not look too different from many we have seen. The statement looks like a function call finished with a period. The output, however, shows an additional message "yes" that gives us some hint that this program does something else behind the scenes.
Prolog is all about facts, rules, and how to satisfy goals. The write "function" is actually a built-in goal that always succeeds and that happens to write a Prolog expression (in our case just a string) to an output stream as a side effect.
The first example in any Prolog tutorial is a family tree. The facts define who is whose child, and the after defining a few rules you can ask all kinds of questions concerning the relationships of the family members. Here are some facts about a well-known family.
parent(elizabeth, elizabeth2). parent(george6, elizabeth2). parent(elizabeth2, charles). parent(elizabeth2, andrew). parent(elizabeth2, edward). parent(philip, charles). parent(philip, andrew). parent(philip, edward). parent(charles, william). parent(charles, henry). parent(diana, william). parent(diana, henry).
Using a Prolog interpreter, we could enter these facts directly in the shell, but since gprolog is a compiler we have to read them from an file. Hence, we place the facts in a file called family.pl and read it into the Prolog system using the consult goal.
| ?- consult('family.pl').
compiling .../family.pl for byte code...
.../family.pl compiled, 16 lines read - 1781 bytes written, 15 ms
yesA shorthand for consult(file) is the file in square brackets, [file]. Alternatively, we could also read the facts from standard input by specifying user as the file name.
Now that these important facts are loaded, we can ask questions, that is, we can ask the Prolog system to satisfy goals. We can, for example, check if the system has really learned the facts.
| ?- parent(philip, andrew). true ? yes | ?- parent(philip, hugo). no
Things get a little bit more interesting when we introduce variables. You may have noticed that up to now we have used lowercase identifiers only. Prolog uses the case of identifiers to distinguish their meaning. Identifiers starting with an uppercase letter denote variables. If we want to find out who are andrew's parents, we just replace the first argument by a variable.
| ?- parent(X, andrew). X = elizabeth2 ?
After finding the first answer, Prolog displays it and gives us the choice to stop the search or ask for more. Hitting the enter key lets us return to the main prompt, the semicolon gives us the next answer, and the key a (for all) lets Prolog look for all possible answers.
| ?- parent(X, andrew). X = elizabeth2 ? ; X = philip ? ; no
For, we have only dealt with facts, but Prolog's real power comes with rules. How can we define a grand parent, for example? A grand parent is a parent who has at least one child who is a parent. In Prolog this can be expressed by the following rule.
grandparent(C,G) :- parent(C,P), parent(P,G).
The symbol :- means "follows from", and the comma combines multiple goals with "and" (conjunction). The whole rule can be read as "C is a grand parent of G if there is a P such that C is parent of P and P is parent of G". This is first order predicate logic with an implicit "for all" on the left and "exists" on the right hand side.
To enter this rule, you have to again enter it in a file and load this file using the consult goal, or read it from standard input using consult(user). To finish your input you can either use the end-of-file key (CTRL-D on UNIX), or the built-in end_of_file term.
| ?- consult(user). compiling user for byte code... grandparent(C,G) :- parent(C,P), parent(P,G). end_of_file. user compiled, 2 lines read - 418 bytes written, 10844 ms yes
With this rule in the system, we can now ask for henry's grand parents.
| ?- grandparent(X, henry). X = elizabeth2 ? a X = philip no
Here is another rule defining the sibling relationship.
sibling(A,B) :- parent(P,A), parent(P,B), A \= B.
The only new element is the /= operator checking if two terms are not identical (a child is not a sibling of itself).
| ?- sibling(X,charles). X = andrew ? a X = edward X = andrew X = edward no
Unfortunately, we get multiple entries since the rule applies to both parents. We have to wait until we can handle lists properly to solve this problem.
Prolog structures combine related data into a single term. They syntactically indistinguishable from goals, that is, they look like function calls as well.
| ?- X = a(1, 2). X = a(1,2) yes | ?- a(X, Y) = a(1, b(c, d)). X = 1 Y = b(c,d) yes
The "function" is called the "functor" of the structure. I like to think of Prolog structures as named tuples (just put the functor as a name in front of a tuple).
As you can see, structures don't have to be declared, and they can participate in matching operations. Structures are the building blocks of Prolog's other data structures such as lists and arithmetical expressions. These other forms are just syntactic sugar for the equivalent nested structures.
It seems like programming for artificial intelligence requires lots of list processing, since the both, Lisp and Prolog, have strong list support. A Prolog list literal is a sequence of comma separated terms enclosed in square brackets (a list syntax which looks familiar by now).
| ?- X = [a, b, c]. X = [a,b,c] yes | ?- X = [1, 'blah', [x, y]]. X = [1,blah,[x,y]] yes
Internally, list are represented as trees of linked nodes with head and tail, just like in Lisp. We can create a list using the dot operator . combining an element and a list as head and tail of the new list.
| ?- X = .(a, [b, c]). X = [a,b,c] yes | ?- .(X, Y) = [a, b, c]. X = a Y = [b,c] yes
An alternative syntax is the vertical bar inside of square brackets separating head and tail.
| ?- X = [a | [b, c]]. X = [a,b,c] yes | ?- [X | Y] = [a, b, c]. X = a Y = [b,c] yes
It is interesting to see the built-in list predicates in comparison to the list fuctions in functional languages. There is, for example, a member goal which checks if a term is contained in a list. Using pattern matching, we can also use this goal to walk through the member of a list.
| ?- member(b, [a, b, c]). true ? a no | ?- member(X, [a, b, c]). X = a ? a X = b X = c no
We could define this predicate ourselves with the following two rules.
member(X, [X|_]). member(X, [_|Tail]) :- member(X, Tail).
Similarly, the built-in concatenation goal append can be used to show all the combinations of lists whose concatenation is identical to a given result list.
| ?- append([1, 2], [3, 4], X). X = [1,2,3,4] yes | ?- append(X, Y, [1, 2, 3]). X = [] Y = [1,2,3] ? a X = [1] Y = [2,3] X = [1,2] Y = [3] X = [1,2,3] Y = [] no
You may have wondered why we did not test arithmetical expressions right after the "Hello World" program. The reason is that arithmetic does not fit easily into the Prolog's logical programming paradigm. Prolog was not invented to solve numerical problems. However, it is possible to perform computations in Prolog. The key are special operators which cause the Prolog system to evaluate an arithmetical expression before continuing the resolution.
If you would like to use Prolog as a calculator, the is operator is all you need. It works like the equality operator, but evaluates its right hand side before matching it with the left hand side.
| ?- X is 3 + 4 * 5. X = 23 yes
The comparison operators evaluate the expressions on both sides and compare the numerical results.
| ?- 2 + 3 > 1 + 2. yes | ?- 2 + 2 =< 1 + 3. yes | ?- 2 + 2 >= 1 + 3.
Note that the "less or equal" operator has the unusual symbol =< (the only argument I can think of is the symmetry between "greater or equal" and "less or equal").
There are special operators for numerical equality and inequality, =:= and =\= which also force both sides to be evaluated.
| ?- 1 + 3 =:= 2 + 2. yes | ?- 4 =\= 5. yes