Prolog: Part 2 - Knowledge Base

In the previous article, we explored clauses and unification in Prolog.

This article focuses on Prolog's knowledge base of facts and rules. Facts are used to state things that are unconditionally true of some situation of interest. Rules state information that is conditionally true of the situation of interest. A collection of facts and rules is called a knowledge base, and Prolog programming is all about writing knowledge bases.

Knowledge Base

A minimal Prolog knowledge base could be a fact. For example: parent(alice, bob).  This is the predicate name "parent" having two arguments. In this example, it is assumed that there is an interpretation of the predicate name and the constant names.  Just like predicate logic, you need an interpretation for clauses to have meaning. As a Prolog programmer, you should strive to design your knowledge base to be self-documenting with sensible predicate names and a logical structuring of your rules. Additional context for interpretation could be provided in external documentation or inline comments.

Recall from the previous blog that rules are of the form: head:-t1,t2, ... , tk. (where k>=1), :- is the neck of the clause, and t1,t2, ... , tk. is the body of the clause. For example: functorX(s, X):-functorY(X),functorZ(X). Let's take a look at an example knowledge base.

happy(bob).
competes(jane).
competes(bob) :- happy(bob)
powerlifter(jane) :- competes(jane).
powerlifter(bob): competes(bob).

Also recall from the previous blog that the part on the left hand side of the :- is called the head of the clause, the part on the right hand side is called the body. If the body of the clause is true, then the head of the clause is true too.  

In this example, the first rule says that Bob competes if he is happy, and the last rule says that Bob is a powerlifter if he competes. The happy predicate is defined using a single clause (a fact). You can think of a fact as a rule with an empty body. In other words, facts are conditionals that do not have any antecedent conditions.  If a knowledge base contains a rule head :- body, and Prolog knows that body follows from the information in the knowledge base, then Prolog can infer head.  This deduction step is called "modus ponens".

Predicates

This knowledge base contains three predicates: happy, competes, and powerlifter. Predicates are important concepts. The clauses we code are attempts to define what predicates mean and how they are interrelated.

Queries

What can be done with Prolog knowledge bases?  We use Prolog knowledge bases by posing queries.  For example, you can run the query:

?- happy(bob).

Prolog will answer:

yes

This is because this is one of the facts explicitly defined in the knowledge base.  If you run the query:

?- happy(Who).

Prolog will answer:

Who = bob
yes

In this query, "Who" is a logical variable and Prolog will unify the logical variable to any value which makes the query succeed.  Note that facts and queries look exactly the same, so when you run a query, you're asking Prolog if the fact exists, or can the variable be unified so that it becomes a fact.  Queries can have multiple answers.  In this case, Prolog will give the answer one at a time.

The easiest way to understand how a Prolog works is to draw a search tree and execute the search from top to bottom, depth first search (DFS).  For the query to succeed, Prolog must unify the query and the fact.  When there is more than one way of obtaining a unification, then a choice point is recorded.  Choice points are used in backtracking.

Next time, in part 3 of this Prolog series, we’ll take a closer look at queries and recursion.