Logic Programming with Prolog

4 min readOct 11, 2019

The following is a brief introduction to Prolog, a declarative turing-complete programming language based on first-order-logic. Applications of Prolog include the construction of grammars used in computational linguistics.

Preliminary

To start coding you can either download a compiler like the one from the GNU Prolog website or if you prefere a notebook-like environment you can do your coding at SWISH. Any terminology specific to Prolog is written in italic. Particularly important terminology will also be bold. That being said, we can now start to code!

Facts and Rules

Essential to Prolog is the so called knowledgebase. A knowledgebase consists of axiomatic facts the programm can “reason” about. These facts represent properties of or relations between objects. The programmer is free to choose those facts and name them according to the task at hand. I recommend to use suggestive names and to be rather canny w.r.t. the number of facts, since this makes it easier to keep track and avoid redundance. Let’s look at some examples: If we want our programm to assume that Plato is a philosopher, we say something like:

is_philosopher(plato).

We can further expand our facts by adding information involving two or more objects. For example we can express the fact that Plato and Xenophon are scholars of Sokrates like so:

is_philosopher(plato).
is_philosopher(xenophon).
is_philosopher(sokrates).is_scholar_of(plato,sokrates).
is_scholar_of(xenophon,sokrates).

Note that all examples begin with small letters. This is because capital letters or words starting with a capital letter are seen as variables. To extract insight from the knb that is not explicitly stated, we use rules. Rules are of the form

head:-
   body.

Technically facts are also rules, for they can be regarded as rules with an empty body. The next code cell contains an example for a Prolog-rule based on our current knb. Lets find out which two philosophers were schooled by Sokrates!

are_co_scholars(X,Y):-
   is_scholar_of(X,Z),
   is_scholar_of(Y,Z),
   X\==Y.

Rules like the one above have a body and the body contains the goals that Prolog has to prove in order to come up with an answer to a query.

Queries

If we want to know if Plato is a philosopher, we can query the knb for an anwer. This is done by putting “?-” in front of the fact. Queries are another fundamental construct in the Prolog language.

?- is_philosopher(plato) (*)#Prolog will answer "true"

We may also want to know all philosophers at once. In this case the query

?- is_philosopher(X)

will do the job. Here “X” is an arbitrary capital letter, hence a variable. The query above yields all objects that have the predicate philosopher. We can also query our knb for a term that matches or unifies with our rule:

are_co_scholars(X,Y):-
   is_scholar_of(X,Z),
   is_scholar_of(Y,Z),
   X\==Y.?- are_co_scholars(plato, xenophon)?- are_co_scholars(P,Q)

You should be able to guess the output correctly.

Datatypes

There is only one datatype in Prolog and that is the term. Terms, however, come across as constants, variables or as a compound. Constants include atoms and numbers. Numbers can be floats or integers. Compounded terms are internally represented as n-ary functors, hence a functor that takes n arguments. To express that a certain compounded term T is a n-ary functor, one says that T is of the form functor/n. An example of a compounded term is the non-empty list. The list [1] is represented as .(1,[]). Recursiveley we get [1,2] = .(2,[1]) = .(2,.(1,[])) and so forth. You can see that lists are ./2 functors. The empty list is atomic in that sense and counts as an atom. Atoms are for example symbols or sequences of symbols like [] or ! or anything enclosed in single quotes. There is a lot more to say about terms in Prolog but this would be somewhat out of the scope of this intro. The key fact in this section is that terms are the only real types in Prolog. :)

Recursion

Rules can be recursively defined. This means at some point in the code the rule makes a reference to itself. Recursion is the only way to perform a repeated task in Prolog. Consider the following example:

child_of(kronos,hades).
child_of(kronos,zeus).
child_of(zeus,athene).ancestor_of(X,Y):-
   child_of(X,Y).ancestor_of(X,Y):-
   child_of(X,Z),
   ancestor_of(Z,Y).?- ancestor_of(kronos,athene)

First we define the ancestor-rule just like the child-rule. Of course every child of X is also an ancestor of X. If Prolog doesn’t find a match on the level of children, it will move to the second definition of the rule. Prolog finds that Athene is a child of Zeus. Zeus then becomes a candidate for the second subgoal, that is to check if Kronos is an ancestor of Zeus. Here the recursion kicks in and Prolog jumps back to the first definition of the ancestor-rule and finds that Zeus is indeed a direct child of Kronos. Success! Now suppose Athene had a child and we wanted to check wheather this child is a descendant of Kronos. How would Prolog look for a solution?

That’s it for this article. I hope it’s an easy read and that I have sparked some interest in logic-programming! :)