What is Prolog good for?



Based on the material presented in class you may wonder what Prolog is good for. We did not have time to cover a full example demonstrating the expressive power of Prolog during the lecture. Here is such an example.

Prolog is a great language for several types of puzzle solving problems. Consider the following well-known riddle:

The wolf, the goat, the cabbage: A farmer and his goat, wolf, and cabbage come to the West bank of a river that they wish to cross. There is a boat, but it has only room for two, and the farmer is the only one that can row. If the goat and the cabbage get in the boat at the same time, the goat will eat the cabbage. Similarly, if the wolf and the goat are together without the farmer, the goat will be eaten. Devise a series of crossings of the river so that all concerned make it across safely to the East bank.

To solve this problem in Prolog, one can encode the configuration of the 4 objects (farmer, wolf, goat, cabbage) as a list. If w denotes the West bank and e denotes the East bank, then the initial state it:

[w,w,w,w]        (everyone is on the West bank)

If the farmer takes the wolf across, then the configuration becomes:

[e,e,w,w]        (and the goat eats the cabbage)

The desired final configuration is:

[e,e,e,e]        (everyone is on the East bank)

In each move, the farmer crosses the river with wither the wolf, the goat, the cabbage, or nothing. Each move can be represented with a corresponding atom: wolf, goat, cabbage, and nothing.

Now, each move transforms one configuration into another. This can be written as a Prolog predicate move(Config,Move,NextConfig) where Config is a configuration, Move is one of the four basic moves, and NextConfig is the configuration that results from applying that move to Config.

For instance, the goal move([w,w,w,w],wolf,[e,e,w,w]) would be valid and could be encoded as a fact:

move([w,w,w,w],wolf,[e,e,w,w]).       (note the '.')

But there would be MANY such facts to encode. The key observation here is that when the wolf and the farmer move, the goat and the cabbage do not change position. So a more generate fact is:

move([w,w,Goat,Cabbage],wolf,[e,e,Goat,Cabbage]).      

where Goat and Cabbage are variables.

Now, there is a similar move when the farmer and the wolf go from East to West. One can thus further generalize the above fact as:

move([X,X,Goat,Cabbage],wolf,[Y,Y,Goat,Cabbage]) :- change(X,Y).

which assumes that a change predicate is defined as:

change(e,w).
change(w,e).

One could have thought of just writing:

move([X,X,Goat,Cabbage],wolf,[Y,Y,Goat,Cabbage]). but in this case X and Y above could unify to any atom (e.g. to goat), which is invalid.

Now, one can encode all the valid moves:
change(e,w).
change(w,e).

move([X,X,Goat,Cabbage],wolf,[Y,Y,Goat,Cabbage]) :- change(X,Y).
move([X,Wolf,X,Cabbage],goat,[Y,Wolf,Y,Cabbage]) :- change(X,Y).
move([X,Wolf,Goat,X],cabbage,[Y,Wolf,Goat,Y]) :- change(X,Y).
move([X,Wolf,Goat,Cabbage],nothing,[Y,Wolf,Goat,Cabbage]) :- change(X,Y).
Next, configurations need to be tested for safety (so that nothing gets eaten). To do this we define a predicate oneEq(X,Y,Z) that is true if at least one of Y or Z is equal to X.
oneEq(X,X,_).
oneEq(X,_,X).

The idea is that if at least one of the goat or the wolf is on the same bank as the farmer, AND if at least one of the goat or cabbage is on the same side as the farmer, then the configuration is safe (think about it for a minute). This can be encoded as:

safe([Man,Wolf,Goat,Cabbage]) :-
    oneEq(Man,Goat,Wolf),     oneEq(Man,Goat,Cabbage).
With move and safe, the puzzled can be solved. A solution is defined as a starting configuration and a list of moves that takes you to the goal configuration. A solution to [e,e,e,e] would be the empty list (no moves are needed). Otherwise, a solution is defined recursively as one move that takes you to a safe configuration followed by a solution. This recursion is easily encoded as:
solution([e,e,e,e],[]).
solution(Config,[FirstMove|OtherMoves]) :-     move(Config,Move,NextConfig),     safe(NextConfig),     solution(NextConfig,OtherMoves).
WARNING: nothing in this Prolog program specifies how long the solution has to be. In fact, a solution could be arbitrary long (e.g. insert an infinite number of nothing moves when the goat is on one side and the wolf and the cabbage on the other). But it Prolog is asked for a solution of a specific length, is will oblige:
?- length(X,7), solution([w,w,w,w],X).

X = [goat, nothing, wolf, goat, cabbage, nothing, goat]

Yes
which means: "First cross with the goat, then cross back empty, then cross with the wolf, then cross back with the goat, then cross with the cabbage, then cross back empty, a finally cross with the goat". It turns out that this is the minimum number of steps. If you keep asking Prolog for solutions you'll find that there are no solutions with an even number of steps, that some queries answer several times the same solution, etc.. There is MUCH MORE to Prolog than what we're covering in this class and we recommend that you follow the links provided on the main page to learn more about Prolog.

Here is the entire source code.

Other common puzzle solving programs in Prolog are: