How does Prolog work out what nobody wrote?
A Prolog rule is a statement that is true when other statements are true. Rules let Prolog work out answers that no fact states.
This matters because a few rules can replace a very long list of facts. In this lesson you describe who manages whom in an office, then ask who is above someone in the chain.
By the end of this lesson
Note
I can write a rule that uses other facts, including a rule that uses itself.
Key words
| Word | What it means |
|---|---|
| Rule | a statement that is true if other statements are true |
| Head | the part of a rule before the :- sign |
| Body | the part after the :- sign: the conditions to meet |
| Recursion | a rule that uses itself |
| Base case | the rule that stops the recursion |
The cells students fill in are left blank in this preview.
A rule has a head and a body
Read this rule aloud: "X is a colleague of Y if one boss B manages both, and X is not Y."
The part before :- is the head. It is what the rule proves. The part after is the body. A comma means "and", so every condition must hold. The sign \= means "is not the same as".
The office file: facts and a rule
manages(rosa, kofi).
manages(rosa, mei).
manages(kofi, liam).
manages(liam, nora).
colleague(X, Y) :- manages(B, X), manages(B, Y), X \= Y.
Save the office file
docker exec prolog sh -c "printf '%s\n' 'manages(rosa, kofi).' 'manages(rosa, mei).' 'manages(kofi, liam).' 'manages(liam, nora).' 'colleague(X, Y) :- manages(B, X), manages(B, Y), X \= Y.' 'boss_of(X, Y) :- manages(X, Y).' 'boss_of(X, Y) :- manages(X, Z), boss_of(Z, Y).' > office.pl"Shown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
Whom does Rosa manage?
docker exec prolog swipl -q -g "forall(manages(rosa, W), writeln(W))" -t halt office.plShown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
Who is a colleague of Kofi?
docker exec prolog swipl -q -g "forall(colleague(kofi, W), writeln(W))" -t halt office.plShown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
Worked example: how the rule is solved
| Step | Prolog tries | What it finds |
|---|---|---|
| 1 | manages(B, kofi) | B is rosa |
| 2 | manages(rosa, Y), first answer | Y is kofi |
| 3 | kofi \= kofi | False, so it goes back to step 2 |
| 4 | manages(rosa, Y), next answer | Y is mei |
| 5 | kofi \= mei | True, so W is mei |
The cells students fill in are left blank in this preview.
A rule that uses itself follows a chain
Who is above Nora in the office? Her manager is Liam. His manager is Kofi. Hers is Rosa. The chain can be any length, so one fixed rule cannot list it.
The answer is recursion: a rule that uses itself. Say it in two lines. A boss is someone who manages you directly. Or a boss is someone who manages a person who is a boss of you.
The two rules for boss_of
% Base case: a direct manager is a boss.
boss_of(X, Y) :- manages(X, Y).
% Recursive case: the boss of a boss is a boss.
boss_of(X, Y) :- manages(X, Z), boss_of(Z, Y).
Everyone below Rosa
docker exec prolog swipl -q -g "findall(W, boss_of(rosa, W), L), writeln(L)" -t halt office.plShown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
Worked example: is Rosa a boss of Nora?
| Step | Goal | What happens |
|---|---|---|
| 1 | boss_of(rosa, nora) | No fact says rosa manages nora, so use the second rule |
| 2 | manages(rosa, Z) | Z is kofi |
| 3 | boss_of(kofi, nora) | No direct fact again, so use the second rule |
| 4 | manages(kofi, Z) | Z is liam |
| 5 | boss_of(liam, nora) | The first rule applies: liam manages nora. Done |
The cells students fill in are left blank in this preview.
Everyone above Nora, in alphabet order
docker exec prolog swipl -q -g "findall(B, boss_of(B, nora), L), sort(L, S), writeln(S)" -t halt office.plShown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
Is Mei a boss of Nora?
docker exec prolog swipl -q -g "(boss_of(mei, nora) -> writeln(yes) ; writeln(no))" -t halt office.plShown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
A common mistake
Warning
Many people think a rule that uses itself must run for ever. It stops when it reaches a base case, a rule that does not call itself. Without one, the search never ends. Prolog also tries rules from the top, so the base case goes first.