Prolog for .NET Developers

• Download demo project with Prolog source- 317 Kb

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).


/* farmer crosses with goat */

transition(state(F0,F0,C,W), state(F1,F1,C,W)):-
    opposite(F0,F1).

/* farmer crosses with cabbage */

transition(state(F0,G,F0,W), state(F1,G,F1,W)):-
    opposite(F0,F1),
    opposite(G,W).

/* farmer crosses with wolf */

transition(state(F0,G,C,F0), state(F1,G,C,F1)):-
    opposite(F0, F1),
    opposite(G,C).

/* farmer crosses alone */

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.