- Building Blocks
- SWI-Prolog
- More Induction
- Debugging Prolog
- A Longer Example
- Why Bother with Prolog?
Like this article? We recommend
Like this article? We recommend
Like this article? We recommend
A Longer Example
One of the nice things about programming in a declarative language is that a program often is just a sufficiently specified problem. Consider the old puzzle about moving a fox, a chicken, and a bag of corn across a river. Your boat can carry only one item, and if left unattended the chicken will eat the corn or the fox will eat the chicken.
To begin with, we define an eats relationship in Prolog:
eats(fox, chicken). eats(chicken, corn).
From this, we can build a safe predicate. An item is safe on one side of the river if nothing else there eats it, or if a human is there to intervene. We express this in Prolog as follows:
safe(_, []). safe(_, Others) :- member(human, Others). safe(Item, [Other|Others]) :- eats(Other, Item),!,fail ; safe(Item, Others).
Two things to observe here:
- The member predicate is built into SWI-Prolog. member holds if the first argument is present in the second (which must be a list).
- The eats(Other, Item),!,fail clause is a pattern known as "negation by failure." If eats holds, then you’ll pass the cut and fail, preventing backtracking. This is a common way of expressing negation in Prolog.
Next, we define a predicate indicating that everything is safe if nothing eats anything else:
allSafe([],_). allSafe([Item|Items], Others) :- safe(Item, Others), allSafe(Items, Others). allSafe(X) :- allSafe(X,X).
Now that we’ve defined some of the basic parts of the game, we should define a winning state. This takes two lists, representing the items on the left and right sides of the river, and holds if everything is on the right:
won([],Right) :- member(fox, Right), member(chicken,Right), member(corn, Right), member(human, Right).
Next, we need to define legal moves. First, we define a predicate that moves something from one side to another, without testing whether it’s legal:
move(X, [X|Left], Right, NewLeft, [X|Right], A) :- append(Left, A, NewLeft). move(X, [L|Left], Right, NewLeft, NewRight, A) :- move(X, Left, Right, NewLeft, NewRight, [L|A]). move(X, Left, Right, NewLeft, NewRight) :- move(X, Left, Right, NewLeft, NewRight, []).
We’ll use this next to define valid moves. A valid move either moves the human from one side to the other, or moves the human and some other object:
validMove(OldLeft, OldRight, NewLeft, NewRight) :- move(human, OldLeft, OldRight, NewLeft, NewRight). validMove(OldLeft, OldRight, NewLeft, NewRight) :- move(human, OldLeft, OldRight, Left, Right), move(_, Left, Right, NewLeft, NewRight). validMove(OldLeft, OldRight, NewLeft, NewRight) :- member(human, OldRight), validMove(OldRight, OldLeft, NewRight, NewLeft).
Notice the third clause for this predicate. We don’t need to define predicates explicitly for moving things left and right; we just require the human to be on the left side—with the move (human,...) predicates—and swap the arguments if the human isn’t on the left side.
A valid move can still result in the game being left in a losing state, so we next define a safeMove predicate, which gives a valid move that results in the game being in a safe state:
safeMove(OldLeft, OldRight, NewLeft, NewRight) :- validMove(OldLeft, OldRight, NewLeft, NewRight), allSafe(NewLeft), allSafe(NewRight).
At this point, it’s worth testing that the code we’ve defined actually works. The entire program is in fox_chicken_corn.pro, so let’s load that file into Prolog and see what happens:
n$ swipl -q -f fox_c hicken_corn.pro ?- safeMove([fox,chicken,corn,human],[],Left, Right). Left = [fox, corn] Right = [chicken, human]
It looks sensible so far, so we can continue. When you try to solve this puzzle, there’s a lot of potential for loops. To prevent this looping, we need some way of checking whether the current game state is one that we’ve visited previously. To do this, we define a triedAlready predicate, which compares the current game state to a list of previous states, and holds if the current state has been visited already:
triedAlready(Left, Right, [[L1,R1]|Others]) :- permutation(Left, L1), permutation(Right, R1) ; triedAlready(Left, Right, Others).
Note that we use another built-in predicate here; permutation holds if both lists passed to it have the same elements, irrespective of ordering. This is a useful gambit, because our game state isn’t sorted.
We’re almost finished now. We just need to define a predicate that keeps moving until it’s in the winning state. The tryMoving predicate keeps track of all previous game states, and returns them in the final argument when it reaches the winning state:
tryMoving(Left, Right, Game, Game) :- won(Left, Right). tryMoving(Left, Right, Game, FinalGame) :- safeMove(Left, Right, NewLeft, NewRight), not(triedAlready(NewLeft, NewRight, Game)), tryMoving(NewLeft, NewRight, [[NewLeft, NewRight]|Game], FinalGame).
We can test this result:
$ swipl -q -f fox_chicken_corn.pro ?- tryMoving([fox, chicken, corn, human],[],[[[chicken, human, fox, corn], []]], Game). Game = [[[], [chicken, human, fox, corn]], [[human, chicken], [fox, corn]], [[chicken], [corn, human, fox]], [[chicken, human, corn], [fox]], [[corn], [fox, human|...]], [[human, fox|...], [chicken]], [[fox|...], [...|...]], [[...|...]|...]]
It looks like the right answer, but it’s not very clearly shown, and it’s in the wrong order (last move first). Let’s wrap this up in a helper predicate that just gives us the sequence of moves in the right order:
playGame(FinalGame) :- tryMoving([fox, chicken,corn, human],[],[[[chicken, human, fox, corn], []]], Game), reverse(Game, FinalGame).
Once we have the right sequence of moves, we may as well display it nicely. Here we use a couple of built-in predicates related to I/O, write and nl. The write predicate prints its arguments; the nl atom, when asserted, displays a new line. We can put these together to display the sequence of moves nicely:
printGame([]). printGame([[Left, Right]|Game]) :- write(Left),nl, write(’ ’), write(Right),nl, printGame(Game).
Finally, we create a trivial predicate for running the program:
go :- playGame(X),printGame(X).
When we run it, this is what we get:
$ swipl -q -f fox_chicken_corn.pro ?- go. [chicken, human, fox, corn] [] [fox, corn] [chicken, human] [human, fox, corn] [chicken] [corn] [fox, human, chicken] [chicken, human, corn] [fox] [chicken] [corn, human, fox] [human, chicken] [fox, corn] [] [chicken, human, fox, corn] Yes
A full sequence of moves, from start to finish, solving the puzzle. Note that this was done without expressly stating how to solve the problem; the solution was derived from a detailed specification by the Prolog compiler.
Programs written in this way aren’t always efficient, but they make a good starting point. Often, the addition of a few cuts in judicious places can make them a lot faster by eliminating large parts of the decision tree.