Prolog

Prolog is a logic programming language.

Any prolog program consists of

  • declaration of facts (also called objects)
  • rules about objects and their relationship
  • asking "questions" about objects and their relationship

First steps

At first you have to install swi-prolog. After installing it, you can call it with swipl.

When you've started swipl you can import your myscript.pl files by consult(myscript).. Don't forget the point at the end. It is important and somehow like the ; in C.

Defining facts

The definition of facts can look like this:

loves(john,X).
  • Note that names of all relationships and all objects have to begin with a lower case letter. Variables begin with a capital letter.
  • The relationship is written first (john). The objects are separated by , and everything is finished with ..
  • The example from above means: john loves everything.
  • You can have any number of arguments.
  • The ordering of arguments is important (loves(john,X) is not the same as loves(X,john)).

Symbols

Boolean Prolog
and ,
or ;
if :-
not not
  • An underscore _ is an anonymous variable.

Rules

Rules consist of a head and a body. They are separated by :-.

Questions

?own(mary,book)

This will invoke the prolog unifier. So Prolog will check if the fact own(mary,book) can be derived from the known facts. Important is that it starts with ?. Everything else in questions is just like it was for facts.

Fox, goose and bag of beans puzzle

This puzzle helped me a lot to understand how Prolog works. It goes as follows:

Once upon a time a farmer went to market and purchased a fox, a goose, and a bag of beans. On his way home, the farmer came to the bank of a river and rented a boat. But in crossing the river by boat, the farmer could carry only himself and a single one of his purchases - the fox, the goose, or the bag of the beans. If left together, the fox would eat the goose, or the goose would eat the beans. The farmer's challenge was to carry himself and his purchases to the far bank of the river, leaving each purchase intact. How did he do it?

Source: Wikpedia

Let's call the side of the river where the farmer currently is 'left' and the other side 'right' to make things easier.

When you solve this by hand, you should note the following:

  • The only two things that the farmer can leave alone is the fox and the bag of beans.
  • As the farmer is always in the boat when anything else is in the boat, you can ignore that step. Just think of the farmer and possibly one other thing teleporting from one side to the other.
  • You only have to look at what's left and what's right. If nothing gets eaten on the left side and nothing gets eaten on the right side, you've got a valid situation.
  • Whenever a situation occurs twice, you did some redundant steps. In other words: At least one solution exists, where no repetitions take place. The shortest solution is one of them.

To solve this task, you split the problem into parts:

  • Define a rule valid that takes a 4-tuple, where the first element is the position of the man, the second of the goose, then the fox and then the beans. Positions can either be left or right.
  • Define a rule step(S1, Description, S2) that makes one step from situation S1 to situation S2 where Description contains the information what was brought to the other side. The situations are, as above, 4-tuples.
  • Define a rule reachable(S1, SituationList, Steps, S2) that is true if S2 can be reached by any number of steps from S1. The list of steps done to get from S1 to S2 is stored in Steps. The SituationList is used to prevent doing unnecessary redundant steps.

So lets get through this.

There are essentially three situations that can occur:

  • The man is on the same side as the goose,
  • the man is on the same side as the beans or
  • the man is on the same side as the fox.

If the man is on the same side as the goose, everything is fine. Nobody gets eaten / eats when the man is there.

If the man is where the beans are, then the goose should not be where the fox is. The case that the goose is where the man is was done before.

And the last case, the man is where the fox is. Now we have to make sure that the beans are not where the goose is:

p(left).
p(right).
valid((Man, Goose, Fox, Beans)) :- p(Man),p(Goose),p(Fox),p(Beans), Man == Goose.
valid((Man, Goose, Fox, Beans)) :- p(Man),p(Goose),p(Fox),p(Beans), Man == Beans, Goose \= Fox.
valid((Man, Goose, Fox, Beans)) :- p(Man),p(Goose),p(Fox),p(Beans), Man == Fox, Goose \= Beans.

The step is also quite simple. There are four possible actions you could take at each situation:

  • Only the man goes to the other side,
  • the man and the beans / goose / fox go the the other side.

So here is the code:

step((Man1, Goose, Fox, Beans), 'Man', (Man2, Goose, Fox, Beans)) :-
    Man1 \= Man2.

step((Man1, Goose1, Fox, Beans), 'Goose', (Man2, Goose2, Fox, Beans)) :-
    Man1 \= Man2, Goose1 \= Goose2.

step((Man1, Goose, Fox1, Beans), 'Fox', (Man2, Goose, Fox2, Beans)) :-
    Man1 \= Man2, Fox1 \= Fox2.

step((Man1, Goose, Fox, Beans1), 'Beans', (Man2, Goose, Fox, Beans2)) :-
    Man1 \= Man2, Beans1 \= Beans2.

And finally the reachable part.

  • Either, you're already at the situation where you want to get to. So you don't have to do any step and it doesn't matter which situations you have seen so far.
  • Or you want to get from S to G. That is only possible, when you can get from S to an intermediate situation with one step less:
reachable(S, _, [], S).
reachable(S, Visited, [Step|Steps], G) :-
    step(S, Step, Tmp), valid(Tmp), not(member(Tmp, Visited)),
    reachable(Tmp, [Tmp|Visited], Steps, G).

Putting it together:

p(left).
p(right).
valid((Man, Goose, Fox, Beans)) :- p(Man),p(Goose),p(Fox),p(Beans), Man == Goose.
valid((Man, Goose, Fox, Beans)) :- p(Man),p(Goose),p(Fox),p(Beans), Man == Beans, Goose \= Fox.
valid((Man, Goose, Fox, Beans)) :- p(Man),p(Goose),p(Fox),p(Beans), Man == Fox, Goose \= Beans.

step((Man1, Goose, Fox, Beans), 'Man', (Man2, Goose, Fox, Beans)) :-
    valid((Man2, Goose, Fox, Beans)),
    Man1 \= Man2.

step((Man1, Goose1, Fox, Beans), 'Goose', (Man2, Goose2, Fox, Beans)) :-
    valid((Man2, Goose2, Fox, Beans)),
    Man1 \= Man2, Goose1 \= Goose2.

step((Man1, Goose, Fox1, Beans), 'Fox', (Man2, Goose, Fox2, Beans)) :-
    valid((Man2, Goose, Fox2, Beans)),
    Man1 \= Man2, Fox1 \= Fox2.

step((Man1, Goose, Fox, Beans1), 'Beans', (Man2, Goose, Fox, Beans2)) :-
    valid((Man2, Goose, Fox, Beans2)),
    Man1 \= Man2, Beans1 \= Beans2.

reachable(S, _,[], S).
reachable(S, Visited, [Step|Steps], G) :-
    step(S, Step, Tmp), not(member(Tmp, Visited)),
    reachable(Tmp, [Tmp|Visited], Steps, G).

start((left,left,left,left)).
goal((right,right,right,right)).

solve(Steps) :- start(S), goal(G), reachable(S, [], Steps, G).

You can load this with swipl -s puzzle.pl and get all solutions with bagof(X, solve(T), L). When you press ; after the first solution, you get the second solution. (Yes, this riddle has only two solutions that avoid redundant steps.)

Material

Published


by

Category

Code

Tags

Contact