Mark Eschbach

Software Developer && System Analyst

Prolog: The Inferent

Prolog is a declartive logic language from the early 1970s. There are many implementations of Prolog, including open source implementations. I have used many Prolog environment, however I keep coming back to .

So what do I mean by a declarative logic language? Prolog uses a database, defining a number of predicates. Each predicate contains a head and a body. The head provides the predicate name and the number of accepted parameters. The number of parameters a given predicate contains is called the arity. A predicate body may contain 0 or more clauses which which invoke additional predicates. When all clauses within a body are true, the predicate is true. The head and body are separated by the symbol :-. The following fragment defines a predicate named head with an arity of two and a body invoke the predicate true, and clause(Parameter1).

head(Parameter1, _Parameter2) :- true, clause(Parameter1).
		

Variables are unified in Prolog. A variable is initial unbound. Upon the first attempt to unify the variable, it becomes bound. Once bound further attempts to unify the variable will result in an equality check, failing if the new value is not equal to the old value. Similar to mathmatics, the variables may only contain a single value.

Inference

In imperative langauges, we describe on a per-step basis, a sequence of commands. Depending on the level of languages, this may have a near one to one mapping to the processing unit instruction. Prolog is a delcarative langauge, allowing us to delcare what goals (predicates) need to be true for our goal to succeed. There are two types of goals: a fact, and a rule.

Facts populate the knowledge base and may be thought of as axioms. Generally facts state the relationship between to constants. A script file is called a knowledge base in Prolog. If we were to consult the following knowledge base in Prolog, the parents_of( james, george, mary ). would return true.

parents_of( james, george, mary ).
		

Notice how the predicate does not contain a body, or the definition. This is the key inidcator we are looking at an axiomatic fact. I could declare facts all day, however this isn't better than a realation data store. The real power of Prolog comes form inference. Consider the following Prolog database:

parents_of( james, george, mary ).
parents_of( mary, samatha, steve ).
parents_of( george, andrei, elizabeth ).

parent_of( Child, Parent ) :- parents_of( Child, Parent, _ ).
parent_of( Child, Parent ) :- parents_of( Child, _, Parent ).
parent( Person ) :- parent_of(_, Person).
		

Let us ask Prolog for whom is a parent. To do so we use the goal parent(Person).. Person is a variable because of the captial letter, and does not contain a value. Therefore Prolog will attempt to find a true solution to bind Person. The result will depend on your implementation, for me on SWI-Prolog I got Person = samatha. There is some magic sauce behind the scenes which don't see. Well call this magic a choice point, and there is more than one. On SWI-Prolog, if you press ; Prolog will present you with an additional solution. In my case the solution was Person = andrei. This is called backtracking.