Introduction
In November 2006, Sacha Barber posted an interesting article on Code Project which used the classic
missionaries and cannibals problem to illustrate an AI search technique in C#. This simple problem provides
an ideal introduction to an alternative programming language, the artificial intelligence language Prolog.
One of the most interesting features of the Common Language Specification (CLS) is the tacit recognition
that there is no single language which is ideal for all problems. While C# is a splendid language,
some mathematical problems might be better expressed in APL, or perhaps SML, while some logic
problems cry out for Prolog. Even more importantly, the CLS allows for easy mixed-language programming.
This means that we can build a user interface in a language ideal for that purpose, perhaps C#,
while describing the cannibals and missionary problem in a language well suited to such searches. This division
can also improve a program's maintainability, since the core problem code can be separated not only
from the user interface, but also from any platform-specific considerations.
Rather than re-hash the cannibals and missionaries problem, we will use a similar problem, the farmer-cabbage-goats-wolf
problem. Both problems illustrate a general class of problems, in which we must find a path to a particular
goal which satisfies strict constraints. The same underlying problem structure appears in many more sophisticated problems, including symbolic reasoning, natural language processing, and cognitive modeling. Such problems are often far simpler to express in Prolog than in a conventional procedural language such as Java or C#. Before discussing the core problem itself, let's examine some of the options available to the .NET or Mono developer who wishes to explore Prolog.
There are many good Prolog implementations out there, including several excellent Open Source packages. Each, of course, has its
strengths and weaknesses. In my opinion,
the two of greatest interest to the .NET developer are XSB and P#. XSB is a top-notch artificial intelligence
programming platform. In fact it is not really fair to call it Prolog at all; XSB is a superset of Prolog. While it
runs Prolog code, it supports many powerful features and extensions not stricly part of the Prolog language. XSB is open source and is
available for many platforms, including Windows and Linux. Its compiled code runs in an unmanaged environment, however. The .NET developer using XSB as a
component would have to be very comfortable invoking API-level procedures. P#, on the other hand, is
an Open Source Prolog implementation created specifically for the CLR by Jon Cook. While not as powerful as XSB, it is an
terrific tool for developers wishing to embed rule-driven Prolog code in a C# program. (Kudos to Mr. Cook!)
P# can be used in two different ways: as a Prolog interpreter or as a Prolog-to-C# compiler. The interpreter would be ideal if one only wanted a solution to the Missionaries and Cannibals problem. He or she could write the Prolog code, run it in the interpreter, and have their answer.
The interpreter is also ideal for the learner; simple Prolog rules can be developed and explored in an easy comfortable environment.
In contrast, if one were developing an expert system for, say, systems diagnostics, then it might be more valuable to compile the Prolog code into C# and embed the resulting
code in a larger application.
Background
A few Prolog basics are necessary to understand this example. Prolog is fairly restrictive on syntax. Variable names begin with
uppercase letters and lowercase letters are used for fixed values and Prolog terms. The variables
work in a way quite different from what you are used to in your favorite procedural programming
language, perhaps C#. Prolog variables are similar to variables in high-school algebra, and operate
in a manner closely analogous to what logicians call "unification". That is to say, given a variable,
Prolog searches its facts and attempts to determine if there is value for the variable which
will make a statement true. In Prolog, one generally does not assign values to variables at all.
Prolog texts often choose introductory examples from genealogy (an excellent application of Prolog, by the way). The fact
father('Abraham','Isaac').
indicates that these two programmatic atoms, 'Abraham' and 'Isaac' are related in the
clause called father. We can then query our one-row database with
father(X,'Isaac').
To test this in our interactive environment, we must "assert" any new facts into our
current session. Here is a copy of an interactive Prolog session:
| ?- assert(father('Abraham','Isaac')).
yes
| ?- father(X,'Isaac').
X = Abraham ?
yes
| ?-
After Prolog tracks through the database, it discovers that the query is true if
X = Abraham.
Using the code
It seems fair to say that Prolog programming cannot be learned in one afternoon, but the Cannibals-Missionaries problem or the Famer-Cabbages-Goat-Wolves problem will provide an illustration of how Prolog works. In procedural languages like C#, values are assigned to variables. In Prolog, variables are more analogous to variables as you used them in high-school algebra. The Prolog code seeks values to variables which satisfy the constraints of the rules defined in the Prolog code.
Here is an example of a Prolog rule; it is simple, but unfamiliar, so it takes a
bit of getting used to. We use "state(F,G,C,W)" to describe the position of the four protagonists
in the little drama. For example, state(n,n,s,s) would indicate that the farmer and goat
are on the north shore and the cabbage and wolf are on the south shore. We can then define a set of
Prolog rules which define the permitted transitions from state to state. For example, the following
rule demands that the farmer and the goat (positions 1 and 2) can make the same transition to
the opposite shore if the position of the wolf and cabbage are left unchanged.
transition(state(F0,F0,C,W), state(F1,F1,C,W)):-
opposite(F0,F1).
Similar rules are defined for each of the allowable transitions.
Now let's run the program in the interactive P# environment. Start the program PSharpGUI.exe. A prolog file can be loaded
into the editor through the usual File\Open dialog. However, to interactively use the facts
and rules in a file, the file must also be opened in the prolog environment itself. If the file
does not need editing, it can be opened directly. Since a prolog file consists of prolog facts,
opening such a file into the environment is referred to as "consulting" it. We will need to consult
a collection of standard utilities, list.pl and the farmer-goat rules file, farmergoat.pl.
consult('list').
consult('farmergoat').
Note that the file extension is not included and be sure not to forget the period at the end of the consult clause.
Many prolog programs will have a "main" clause or a "go" clause which is set to run automatically when
the file is consulted. In this case, we learn more by typing in a clause:
path(state(n,n,n,n),state(s,s,s,s), FinalPath).
This clause becomes our goal; we want to find a sequence of allowed transitions which
takes us from the starting state, everyone on the north shore, to the final state, everyone on the south.
If such a sequence of states exists, it will be "unified" with the variable FinalPath. Though
we will not discuss it here, Prolog is quite capable of going back and finding additional solutions, should
they exist.
Here is the full code to farmergoat.pl:
opposite(n,s).
opposite(s,n).
transition(state(F0,F0,C,W), state(F1,F1,C,W)):-
opposite(F0,F1).
transition(state(F0,G,F0,W), state(F1,G,F1,W)):-
opposite(F0,F1),
opposite(G,W).
transition(state(F0,G,C,F0), state(F1,G,C,F1)):-
opposite(F0, F1),
opposite(G,C).
transition(state(F0,G,C,W), state(F1,G,C,W)):-
opposite(F0,F1),
opposite(G,C),
opposite(G,W).
path(A,B,FinalPath):-
path(A,B,[], ReversedFinalPath),
reverse(ReversedFinalPath, FinalPath).
path(CurState, GoalState,PrevStates, [GoalState|PrevStates]):-
transition(CurState, GoalState).
path(CurState, GoalState, PrevStates, FinalPath):-
transition(CurState, NextState),
not(member(NextState, PrevStates)),
path(NextState, GoalState, [CurState|PrevStates], FinalPath).
For developers wishing to learn more about Prolog, there are several excellent texts,
but in my opinion the best for getting started is Ivan Bratko's exceptional "PROLOG
Programming for Artificial Intelligence" published by Addison Wesley. Interested evelopers are also welcome to contact the author of this article. Those
who are not only interested but nostalgic will receive a Prolog implementation of the
command-line classic "Hunt the Wumpus".
Points of Interest
Although Prolog has been around for over three decades, it is recently enjoying a
resurgence of interest in a number of fields including natural language processing. Of particular
interest to the author is the use of Prolog to generate hypotheses from large databases.
About Dan Buskirk
Dan Buskirk is a professional SQL Server developer and .NET programmer. He can rarely
resist exploring new things that look like fun.
