The Drafting Table

Week 3: Prolog

Dan Scott -

This post continues my series on Seven Language in Seven Weeks by Bruce Tate. As in the previous posts, I'm going to share my notes on this chapter, including a few excerpts, some significant methods, snippets of code, and links for further reading.

Week 1 ˙ Week 2 ˙ Week 3 ˙ Week 4 ˙ Week 5 ˙ Week 6 ˙ Week 7

I said last week that I was a bit excited about Prolog. That's because it is very different from any languages I've used before. Prolog is a declarative language (so it might help get into the right mindset for the functional languages later in the book) rather than an imperative one. This means that you specify constraints on a problem instead of an algorithm for solving it.

Here is a brief description of Prolog from Bruce Tate:

Prolog programming has two major steps. Start by building a knowledge base, composed of logical facts and inferences about the problem domain. Next, compile your knowledge base, and ask questions about the domain. Some of the questions can be assertions and Prolog will respond with yes or no*. Other queries have variables. Prolog fills in these gaps that makes those queries true.
Rather than simple assignment, Prolog uses a process called unification that makes variables on both sides of a system match. Sometimes, Prolog has to try many different possible combinations of variables to unify variables for an instance.

*The interpreter I was using (SWI-Prolog) uses true and false instead.

To use Prolog, you develop a "knowledge base" of facts and rules in a .pl file (I simply used the gedit text editor to write these) and then load it into an interpreter and make queries about it. As mentioned, I used the SWI-Prolog interpreter; the examples in the book used GNU Prolog (so there were a few things that didn't work exactly as described). Facts are typically written as relation(argument1, argument2). —note that it is important to end with a period and use all lowercase letters. For example, the fact capital(fredericton, newbrunswick). means Fredericton is the capital of New Brunswick. There can be facts with more (or less) than two arguments. Typical rules might be written as relation(X,Y) :- subgoal1, subgoal2, subgoal3. —again, they need to end with a period but arguments will mostly be replaced with variables (variables always begin with a capital letter but can be more than one letter). Sub-goals (I used 3 for example, but there can be any number) to the right of :- must all be true for the rule to be met (if they are separated by commas; semicolons indicate any sub-goal can be true). Variables can be used in the sub-goals and so can the relation itself (for recursion).

In the interpreter, you can call on facts and rules (filled in with appropriate arguments) after loading the file with the knowledge base. If you call on them with values in lower-case, Prolog will tell you whether the fact or rule is true or false for those values. If you call on a fact/rule with variables (in upper-case) as the arguments (or a mix of variables and fixed values), it will tell you what values those variables can/must take to satisfy all of the relevant facts and rules. This process of binding variables with the values that make both sides of a rule match is known as "unification". Note that Prolog may find multiple possible solutions (in which case you can press ; at the prompt to see the next one) or none (in which case it simply says false). Also note that Prolog doesn't remember the values of variables between queries, so you can use a common variable (e.g. X or What) in repeated queries without any problems.

Prolog has some built-in methods (I'm not sure if they are the same between different interpreter implementations, however), but simply knowing the basic syntax goes a long way. Compared to the other languages in the series so far, I just have a short list of things to know:

  • In the interpreter, ?- begins a prompt line. Queries you type have to end with a period, just as facts and rules in the knowledge base.
  • To load a knowledge base, type ['filename.pl']. in the interpreter.
  • To quit the interpreter, type halt. (I had to look this one up because it wasn't obvious). help. gives some tips. Launching the interpreter (assuming you're using SWI-Prolog) is done with the command swipl in the terminal.
  • _ is a wildcard variable. When used in a rule or a query it can take on any value (other variables will be unified to a fixed value within the context of a rule/query).
  • Lists go in square brackets. Round parentheses are used for tuples, which have a fixed length.
  • The notation [Head|Tail] matches Head with the first element of a list and Tail with the remainder (which can be empty). Any variables can be used (or fixed values in lower-case if the situation calls for it), it doesn't have to literally be Head and Tail.
  • See this table for predefined operators in Prolog. Equalities and inequalities, for example, are =, \=, =<, >=.
  • Prolog is really oriented toward logic. So unifying variables to meet equalities/inequalities is quite natural. To do arithmetic in a rule, you need to use the keyword is (e.g. N1 is N + 1,).
  • A week wasn't really long enough to get comfortable with how Prolog handles lists. Here are some of the built-in functions for them. Seven Languages in Seven Weeks describes how append(list1, list2, list3) can be used in four different ways: if all three lists are given actual values it tells whether it is true or false that list3 is the combination of list1 and list2; if the third list is a variable, it becomes (by unification) the combination of list1 and list2; if one of the first two lists is a variable it will become (if possible) what would need to be added to the other list to give list three; and if the first two lists are both variables, all possible splits in list3 are shown.
  • Preceding a sub-goal of a rule with \+ looks for the condition where that sub-goal cannot be proven.
  • ! cuts off possible answers. When used as a sub-goal, only the first variables that successfully match preceding sub-goals are used in attempting to match subsequent sub-goals.

A lot of what I've tried to describe so far is pretty abstract. Hopefully the following examples will demonstrate how Prolog can be used:

One of the examples Bruce Tate gives in the chapter on Prolog is using it to determine how a map can be coloured without two territories of the same colour touching each other. This is a problem that is very well-suited to Prolog because even though it can be complicated for certain maps it is simple to define the conditions that must be met. I liked his example so I decided to try to solve it in a different way for practice:

colour(yellow). 
colour(teal).
colour(purple). 
colour(white). 

border(X,Y) :- colour(X) \= colour(Y). 

mapping(Maine, NH, Vermont, Mass, Conn, RI) :- 
  colour(Maine), colour(NH), colour(Vermont), colour(Mass), colour(Conn), colour(RI),
  border(Maine, NH), 
  border(NH, Vermont),
  border(NH, Mass),
  border(Mass, Vermont), 
  border(Mass, Conn), 
  border(Mass, RI), 
  border(Conn, RI).

At the start of this knowledge base I've stated four facts to define colours that may be used. Next comes a rule that if X and Y border each other, they can't be the same colour. Finally is the rule called mapping that has six states as its arguments (note that they start with capital letters so they act as variables). This rule has a number of subgoals that basically require that each state be matched with a colour and that certain states have to follow the border rule (already defined: they must be different colours) since they are next to each other.

In the interpreter, I simply load the knowledge base then use the mapping rule as a query.

?- ['map2.pl'].
true.

?- mapping(Maine, NH, Vermont, Mass, Conn, RI). 
Maine = Vermont, Vermont = Conn, Conn = yellow,
NH = RI, RI = teal,
Mass = purple ;

It ends with a semi-colon (that I typed to continue, then cut off the rest of the results) since there are other possible colouring patterns. I allowed for four colours and only three were needed so that creates a lot of additional possibilities.

The other example I wrote is to solve the viral logic puzzle from a few years ago about #CherylsBirthday. This article presents the puzzle and explains the solution (SPOILER ALERT: don't scroll down if you want to try it yourself first). Here it is in Prolog:

month(may). 
month(june).
month(july). 
month(august). 

day(fourteen).
day(fifteen). 
day(sixteen).
day(seventeen).
day(eighteen). 
day(nineteen). 

round0(may, fifteen).
round0(may, sixteen). 
round0(may, nineteen). 
round0(june, seventeen). 
round0(june, eighteen). 
round0(july, fourteen). 
round0(july, sixteen). 
round0(august, fourteen). 
round0(august, fifteen). 
round0(august, seventeen). 

nonuniqueday(D) :- day(D), month(M1), month(M2), M1 \= M2, round0(M1,D), round0(M2,D). 

bernardmightknow(M) :- round0(M,D), \+ nonuniqueday(D). 

round1(M,D) :- round0(M,D), \+ bernardmightknow(M).

nonuniqueday2(D) :- day(D), month(M1), month(M2), M1 \= M2, round1(M1,D), round1(M2,D). 

round2(M,D) :- round1(M,D), \+ nonuniqueday2(D). 

nonuniquemonth(M) :- month(M), day(D1), day(D2), D1 \= D2, round2(M,D1), round2(M,D2). 

round3(M,D) :- round2(M,D), \+ nonuniquemonth(M).

I'm sure there is a more succinct way to solve this (perhaps if I was better at handling lists in Prolog, or knew how to find unique days or months in a single step). The initial facts are the months and days that are possible, then the specific dates that Cheryl offered as possibilities (round0 is before Albert or Bernard have received any additional information). In round1, we know that it has to be a month without a unique day or else there is the possibility that Bernard might have enough information to solve it on his own (e.g. if Bernard got the number nineteen then the only possibility would be May 19th). I didn't know how to find months with unique days in a single step so I defined a rule for non-unique days then set a sub-goal to find its logical negation (using \+). In round2, the first rule asks for (Month, Day) combinations that passed the rules of round1 to use the process of elimination. Since Bernard can guess correctly after some months have been ruled out by Albert's comment, the process of looking for unique days is repeated (but only on possibilities that haven't been ruled out). Finally, a similar procedure is used in round3 to find a month with only one possible day (since knowing the month now gives Albert enough information to correctly guess Cheryl's birthday) considering only the combinations that passed round2.

Here are the results when I loaded this into the interpreter and made a query:

?- ['cherylsbday.pl'].
true.

?- round3(M,D). 
M = july,
D = sixteen ;
false.

Actually, it was an iterative process of making lots of queries that didn't identify Cheryl's birthday then tweaking the rules and trying again.

Bruce Tate points out that Prolog is kind of a niche language. Some problems are ideal to approach in this logical way of defining constraints and then letting the software find cases where the variables can match up with the rules. Aside from the map colouring problem, another great example in the book is a Sudoku solver. Other problems can be frustrating to attempt with Prolog. If you don't have the logic of the problem completely defined it will either give you too many possible answers (if it is under-constrained) or no answer, just false (if it is over-constrained).

Each chapter in Seven Languages in Seven Weeks has an interview with someone involved in creating the language or someone who uses it for interesting applications. This chapter spoke with Brian Tarbox, a researcher on dolphin cognition. He talked about using Prolog to model what words and commands dolphins could understand and also developing lab schedules (with a lot of constraints such as when personnel with certain skills or special equipment or facilities were available). The interview was a nice glimpse of situations where Prolog can be very useful.

Finally, here are some links for further reading/study on Prolog:

Permalink