Last week, I went to a meetup called the Code Reading Club. We were all given the same physical packet of code (with no syntax highlighting) to discuss in groups. A lot of the meetups I’ve been to have been mostly unstructured, and it’s up to you to navigate conversations and make the best use of your time. Having a structured activity to work through for an hour was a great way to start conversations.
I did not recognize the code sample we were given, but someone in my group recognized it as Prolog.
% A teacher wishes to seat 16 quarrelsome children% in a 4x4 array of chairs% Some of the children don't get along% The problem is to seat the children so no student% is seated adjacent (4 way adjacent) to a child% they quarrel with%% The children are numbered 1 thru 16% 1..8 are girls, 9..16 are boys%%:- use_module(library(clpfd)).
compatible(Neighbor , Student) :- Student #= 3 #==> Neighbor #< 9,% #3 doesn't want to sit next to icky boys Student #= 5 #==> Neighbor #< 9,% #5 agrees with #3 Student #= 2 #==> Neighbor #\= 3,% #2 and #3 don't get along Student #= 10 #==> Neighbor #> 8.% #10 doesn't like gross girls
constrain_up(1 , _ , _ , _).constrain_up(R , C , Student , Board) :- R > 1, NR is R - 1, member(seat(NR , C , Neighbor) , Board), compatible(Neighbor , Student).
constrain_down(4 , _ , _ , _).constrain_down(R , C , Student , Board) :- R < 4, NR is R + 1, member(seat(NR , C , Neighbor) , Board), compatible(Neighbor , Student).
constrain_left(_ , 1 , _ , _).constrain_left(R , C , Student , Board) :- C > 1, NC is C - 1, member(seat(R , NC , Neighbor) , Board), compatible(Neighbor , Student).
constrain_right(_ , 4 , _ , _).constrain_right(R , C , Student , Board) :- C < 4, NC is C + 1, member(seat(R , NC , Neighbor) , Board), compatible(Neighbor , Student).
constrain_pupil(Board , seat(R , C , Student)) :- constrain_up(R , C , Student , Board), constrain_down(R , C , Student , Board), constrain_left(R , C , Student , Board), constrain_right(R , C , Student , Board).
make_seat(R , C , seat(R , C , Student)) :- Student in 1..16.
% map between seat(r,c,s) and raw variableseat_student(seat(_R, _C, S) , S).13 collapsed lines
% map between the [seat(1,1,S1)...] representaion and the [S1]% representationboard_students(In , _SoFar , Raw) :- maplist(seat_student , In , Raw).
/* How to map thru by hand 8cD
board_students([] , _ , []).board_students([seat(_, _, S)|T] , _ , [S|Vs]) :- board_students(T , _ , Vs).*/
make_board(Board) :- findall(S , ( member(R , [1,2,3,4]) , member(C , [1,2,3,4]) , make_seat(R , C , S)) , Board), maplist(seat_student , Board , Raw), all_distinct(Raw).
write_board(Board) :- member(R , [1,2,3,4]), nl, member(C , [1,2,3,4]), member(seat(R, C, S), Board), write(S), write(' '), fail.write_board(_) :- nl.
assign_all_pupils :- make_board(Board), maplist(constrain_pupil(Board) , Board), maplist(seat_student , Board , Raw), labeling([], Raw), write_board(Board).(They gave us a link to the source at the end of the meetup.)
We weren’t allowed to use any resources to understand the code, so we had to rely on cues from within the code, which mostly confused me.
- It was clear that there were few imperative statements and no main method, so I thought it was functional, but I kept seeing variables passed into functions that weren’t defined.
- I wasn’t sure what to make of the hash syntax on lines 17-20. At first I thought it was assignment, but then I thought it might be some kind of assertion.
- The repeated name on lines 22-23 looked like function overloading, but I couldn’t understand what the overload was doing.
- I couldn’t tell what was imported from the
clpfdlibrary. seatlooked domain specific, like it wouldn’t be from the library. I could see it being called, but I couldn’t find where it was defined.
It was clear that one of the goals of the group was to be accessible to all skill levels, which I really appreciate. We talked about what we found puzzling, lines we found interesting, and what we thought the overall function of the code was. That said, after staring at it on paper for an hour, I really wanted to dive into it and try to fully understand it.
Installing a Prolog Compiler
Before diving into the code at home, I wanted an overview of the language, so I watched Derek Banas’ Prolog Tutorial from ten years ago. Then, following his tutorial, I installed a prolog compiler, GNU Prolog. I saved our code sample as db.pl and loaded it through the terminal:
danjutan@MacBook-Air-5 prolog-tutorial % gprolog
GNU Prolog 1.5.0 (64 bits)Compiled Jul 8 2021, 09:35:47 with clangCopyright (C) 1999-2024 Daniel Diaz
| ?- [db].
compiling /Users/danjutan/Documents/Dev/prolog-tutorial/db.pl for byte code.../Users/danjutan/Documents/Dev/prolog-tutorial/db.pl:13: warning: unknown directive use_module/1 - maybe use initialization/1 - directive ignored/Users/danjutan/Documents/Dev/prolog-tutorial/db.pl:57:10: syntax error: . or operator expected after expression
1 error(s)
compilation failedAs it turns out, this was the wrong compiler. The line use_module(library(clpfd)) imports features that are only available in the SWI-Prolog compiler. This is an earlier version of Prolog, one of many more Prolog implementations. I installed it and was able to successfully load the file with swipl -s db.pl.
I decided to use Visual Studio Code as my editor, and I had to install an extension to provide syntax highlighting.
This started my Prolog journey, and the following is what I’ve learned. Having a goal to understand a piece of code was a great motivating tool and a great way to guide what I prioritized, and writing it up helped clarify my knowledge.
Facts and Rules
A fact is a statement that a specific thing is true. It is a single line that ends in a . For example, color(blue). states that blue is a color. flight(seattle, denver). states that there is a “flight” relationship between Seattle and Denver. We would interpret that as there being direct flight between Seattle and Denver.
You can query a set of facts in the interactive shell. Let’s use these facts:
flight(seattle, denver).flight(seattle, chicago).flight(seattle, dallas).flight(denver, newyork).flight(chicago, newyork).flight(dallas, newyork).Then in the shell:
1 ?- flight(seattle, denver).true.
2 ?- flight(seattle, newyork).false.Prolog can “solve for X”. Type a semicolon after each output to see all results:
3 ?- flight(seattle, X).X = denver ;X = chicago ;X = dallas.A rule is a statement that something is true if it satisfies certain conditions, called goals. These goals are separated by a comma. For example:
connection(A, C) :- flight(A, B), flight(B, C).This rule says, there is a connection between A and C if there is a flight between A and some B, and a flight between B and C. The , means and ( ; would mean or).
A, B, and C are variables. Variables always begin with an upper case letter. In this example, A and C are arguments to the connection rule, but B seems to be passed to flight without being defined first. That’s because that line is actually defining B to be anything that satisfies this rule. We're asking is there some B such that there is a flight between A and B and a flight between B and C?
Prolog will check every possible B where flight(A, B) is true. Then for each of those, it will move on to the next goal and check if flight(B, C) is also true.
If we have flight(seattle, denver). and flight(denver, newyork). then connection(seattle, newyork) is true. But if there are multiple ways to satisfy the rule, Prolog will actually find all of them. Let’s add a write statement to our rule:
connection(A, C) :- flight(A, B), flight(B, C), write(B).The write goal writes its argument to the shell. (write always resolves to true.)
We can query a connection:
danjutan@MacBook-Air-5 prolog-tutorial % swipl -s db.pl
4 ?- connection(seattle, newyork).
denvertrue ;chicagotrue ;dallastrue.So Prolog does not simply execute from top to bottom. It will backtrack and find all solutions to a problem that you set up. This principle is used throughout our code sample.
The Objective
Most of our code sample consists of rules, with a few facts mixed in. At the end of the file, there is a rule with no arguments.
assign_all_pupils :- make_board(Board), maplist(constrain_pupil(Board) , Board), maplist(seat_student , Board , Raw), labeling([], Raw), write_board(Board).This is essentially the starting point for our program. We can query our assign_all_pupils function and see the output of our program:
5 ?- assign_all_pupils.
1 2 4 35 6 9 78 11 10 1213 14 15 16
trueAs we did before, we use fact syntax to query; in this context, instead of saying “assign_all_pupils is true” it is asking “is assign_all_pupils true?” Prolog then runs that rule to find out, which causes the board to be printed.
Reading the comments at the top of the code, we can see that the program is trying to seat 16 students in a 4x4 array of chairs. Lines 16-20 lay out some constraints. With no Prolog knowledge, these lines were the easiest to reason about at the meetup because of the comments:
compatible(Neighbor , Student) :- Student #= 3 #==> Neighbor #< 9,% #3 doesn't want to sit next to icky boys Student #= 5 #==> Neighbor #< 9,% #5 agrees with #3 Student #= 2 #==> Neighbor #\= 3,% #2 and #3 don't get along Student #= 10 #==> Neighbor #> 8.% #10 doesn't like gross girls- Line 17 says: if
Studentis equal to 3 thenNeighbormust be less than (#<) 9. Since the initial comment defines students 1-8 as girls, this means that student 3 won't sit next to boys. - Student 5 has the same restriction.
- Student 2 won't sit next to student 3 (
#\=means "can't be equal"). - Student 10 won't sit next to girls.
compatible(Neighbor, Student) says a neighbor (which is a number) and a student (also a number) are only compatible if all of these constraints are satisfied. There are only constraints for students 3, 5, 2, and 10, so any other student is automatically compatible with any neighbor.
6 ?- compatible(3, 10).false.
7 ?- compatible(3, 8).true.
8 ?- compatible(9, 10).true.#==> is called reified implication and the other #-prefixed operations are called integer constraints. This syntax is SWI-Prolog specific, imported by that use_module(library(clpfd)) line. (Other Prolog compilers have their own variants).
CLP(FD)
CLP(FD) stands for Constraint Logic Programming over Finite Domains. Features from this library are all about constraints; we’ll see another one later. I didn’t dive very deep into it, but the library has extensive documentation here . The author summarizes its use cases:
CLP(FD) constraints are one of the main reasons why logic programming approaches are picked over other paradigms for solving many tasks of high practical relevance. The usefulness of CLP(FD) constraints for scheduling, allocation and combinatorial optimization tasks is well-known both in academia and industry.
Unfortunately, while there is an explicit import syntax in Prolog, this code sample doesn’t use it, so I had to look everything up to see whether it came from the library.
We can now understand the output: a 4x4 array of students that satisfies all of the constraints spelled out in the compatible rule.
Constraint Rules
For each direction, we have a constrain fact and a rule. These check whether the neighbor sitting next to the student in that direction is compatible with it.
constrain_up(1 , _ , _ , _).constrain_up(R , C , Student , Board) :- R > 1, NR is R - 1, member(seat(NR , C , Neighbor) , Board), compatible(Neighbor , Student).
constrain_down(4 , _ , _ , _).constrain_down(R , C , Student , Board) :-4 collapsed lines
R < 4, NR is R + 1, member(seat(NR , C , Neighbor) , Board), compatible(Neighbor , Student).
constrain_left(_ , 1 , _ , _).constrain_left(R , C , Student , Board) :-4 collapsed lines
C > 1, NC is C - 1, member(seat(R , NC , Neighbor) , Board), compatible(Neighbor , Student).
constrain_right(_ , 4 , _ , _).constrain_right(R , C , Student , Board) :-4 collapsed lines
C < 4, NC is C + 1, member(seat(R , NC , Neighbor) , Board), compatible(Neighbor , Student).Let’s start with the rule constrain_up(R, C, Student, Board). R is row and C is column. Student is a number, as we saw earlier. And we haven’t seen what Board is yet.
It first checks whether R > 1—if we're going to look up, we need to make sure we can. The next line, NR is R - 1, refers to a variable NR that does not exist yet. This line tells Prolog to make sure NR satisfies the relationship “NR is R - 1”. Effectively, it sets a new variable NR to R - 1.
Line 26 uses a compound term seat. This puts components together and gives them a name, making them easier to work with. We can guess that seat(NR, C, Neighbor) refers to the notion that Neighbor is sitting at row NR and column C. This implies that the components of seat are a row, a column, and a student number. We could, for example, write seat(1, 2, 3) to refer to student 3 sitting at row 1, column 2. You won't find seat itself being defined in the code; you can use it without declaring it.
member tells you whether something is a member of a list; so member(seat(NR, C, Neighbor), Board) checks if that seat is a member of the list Board. (This tells us that Board is a list of seats, the state of the board.) But Neighbor isn't defined yet! Line 26 and 27 say: check if there is some Neighbor who is sitting at row NR and column C that is compatible with Student.
Next, let's look at line 22, constrain_up(1 , _ , _ , _). This line is a fact. It says "constrain_up is true for row 1 and any column, Student, and Board." _ is an anonymous variable, meaning we don't care about the value.
We can see that constrain_down is similarly always true if the row is 4, constrain_left is always true if the column is 1, and constrain_right is always true if the column is 4. This makes sense because in any of these positions, there is no neighbor in that direction, so the compatibility constraints should be considered automatically satisfied.
All of this is brought together on line 50:
constrain_pupil(Board , seat(R , C , Student)) :- constrain_up(R , C , Student , Board), constrain_down(R , C , Student , Board), constrain_left(R , C , Student , Board), constrain_right(R , C , Student , Board).This rule takes a board state and a seat and checks if all of the constraints are true; i.e., if the neighbor in each direction is compatible with this student.
Making a Board
Let's break down make_board on line 75:
make_board(Board) :- findall(S , ( member(R , [1,2,3,4]) , member(C , [1,2,3,4]) , make_seat(R , C , S)) , Board), maplist(seat_student , Board , Raw), all_distinct(Raw).First, notice where it is used:
assign_all_pupils :- make_board(Board), ...make_board is called with an uninstantiated variable Board, meaning that the Board argument is an output of make_board, not an input. We also know from before that Board is a list of seats, so we should expect this rule to set Board to a list.
“Output variables”
Prolog’s goal is to make a relation true and will work bidirectionally.
flight(X, newyork) will instantiate X to all flights to New York, and flight(seattle, X) will instantiate X to all flights from Seattle. So neither argument is strictly an “output” variable.
In the case of make_board, it is only called with an uninstantiated Board in our code sample. So it makes sense to me to consider Board an “output”. We will see that, in that case, make_board instantiates Board to a valid board. But we could actually treat Board as an input and pass an existing board, and make_board would instead verify if the board was valid!
That’s exactly what findall does: it takes a goal and makes a list of things that satisfies the goal. Earlier, we used the example of connecting flights. We wrote a connection rule which checked if two cities had a connection. The way Prolog works, it finds all connecting cities between two cities. We could see those connections in the shell, but what if we wanted to use them as a list? We could use findall:
findall(B, ( flight(A, B), flight(B, C)), List).If we run this in the shell, we get List = [denver, chicago, dallas].
findall takes three arguments. It looks like findall(Template , Goal, Result):
- The last argument,
Result, is the output variable; the list will be saved here. Goalis the condition that Prolog will work to satisfy. The number of ways to satisfy the goal will be the number of items in the output list. If we want to use multiple goals, like in a rule, we can wrap them in().Templateis the variable in the goal that contains the value we want to save to the list.
So in our flight example, Prolog finds all A, B, C that satisfy flight(A, B), flight(B, C). Then from each of those cases, it takes B and saves it to List. Let’s look at the findall in our code again:
findall(S , ( member(R , [1,2,3,4]) , member(C , [1,2,3,4]) , make_seat(R , C , S)) , Board),Here, the template is S, so it will look to match S in the goal. The result is Board, so the Board variable will become a list. Previously we saw a variable named Board was a list of seats, so we can expect that S is a seat.
To analyze the goal, keep in mind the principle of Prolog finding all solutions. If R was already defined, member(R, [1,2,3,4]) would tell us if R was in the list [1,2,3,4]. But since R is not defined, member(R, [1,2,3,4]) tells Prolog to find all R that are in that list; then, for each of them, continue on to the next goal. Effectively, it is looping through [1, 2, 3, 4], using R as the iterator variable.
Similarly, member(C , [1,2,3,4]) tells Prolog to find all C that are in the list. This effectively creates a nested loop: R will iterate through [1,2,3,4], and for each of those, C will iterate through [1, 2, 3, 4].
The third goal, make_seat, will run for every combination of R and C. The unknown variable in make_seat(R, C, S) is S, so we know that the third argument is the output. Let’s take a look at make_seat:
make_seat(R , C , seat(R , C , Student)) :- Student in 1..16.We see that the output variable is a seat, with row and column equal to the first two arguments, and a yet undefined Student.
This in was another constraint feature imported using clpfd. This doesn't set Student to anything, but it says, "from now on, Student can only be set to a number between 1 and 16".
So make_seat takes a row and column and outputs a seat at that row and column. The seat has an undefined Student which is constrained between 1 and 16.
So, the findall loops through all possible spots, makes a seat for each of them, and saves it to Board.
Filling the seats
So far, we have a board of seats with students numbers that are undefined except for a constraint that they must be between 1 and 16. Let’s work backwards from the end of this rule.
make_board(Board) :- findall(S , ( member(R , [1,2,3,4]) , member(C , [1,2,3,4]) , make_seat(R , C , S)) , Board), maplist(seat_student , Board , Raw), all_distinct(Raw).all_distinct is another constraint. Given a list of variables, it constrains the list so that everything is distinct. If we pass it all of the students in the seats, it will make sure that they represent the numbers 1 through 16.
maplist takes a predicate and two lists. A predicate is the name of a fact or rule. maplist iterates through the first list and calls the predicate. For each input element, the predicate saves something to the output variable. So maplist effectively transforms the first list using the predicate and saves it to the second list.
To do this, the predicate must have two arguments, an input and an output. We see that this is true:
% map between seat(r,c,s) and raw variableseat_student(seat(_R, _C, S) , S).This takes a seat, ignores the row and column, and outputs a student. If we analyze it as a fact, it says, "the student of a seat(R, C, S) is S".
So maplist takes each seat in Board, gets its student, and saves it to Raw, making Raw a list of all the students in the board. Then all_distinct(Raw) constraints those students so they are all distinct. The result is that Board is a list of 16 seats. There still isn’t a specific student number in each seat, but we know that when they are set, student of those seats must be between 1 and 16, and no two seats can have the same student.
Putting It All Together
Let’s move into the last part of the code sample.
write_board
write_board(Board) :- member(R , [1,2,3,4]), nl, member(C , [1,2,3,4]), member(seat(R, C, S), Board), write(S), write(' '), fail.write_board(_) :- nl.This uses the same looping pattern as before. We iterate through possible rows, then iterate through possible columns. At the beginning of each row, we print a newline (nl).
For line 88, remember Prolog’s desire to solve for the unknown variable. Here, S (the student of the seat) is unknown. So Prolog will find the student at row R and column C in the board. On line 89 it will write it out, followed by a space.
Line 90 is puzzling: why do we want the rule to fail? fail tells Prolog to backtrack. This is a concept we’ve seen before.
- When we were using our
flightexamples in the shell, we used;to tell Prolog to backtrack and show us the next solution. - Previously, used the
memberpattern within afindallgoal.findallalso tells Prolog to backtrack and run the goal until all possibilities were exhausted, allowing the loop to work. - In a normal rule outside the shell, we use the
failkeyword to tell Prolog to continue to the next solution.
When write_board is on its last iteration of the loop, it fails, but there are no solutions left in this rule. In that case, Prolog will try the next rule of the same name. This causes write_board(_) to be called, printing a newline.
In summary, write_board loops through the rows and columns of the board, grabs the student at each seat, and outputs it. Afterwards, it prints a newline.
assign_all_pupils
Finally, we return to our “entry point”:
assign_all_pupils :- make_board(Board), maplist(constrain_pupil(Board) , Board), maplist(seat_student , Board , Raw), labeling([], Raw), write_board(Board).This rule starts by creating a board. This gives us a list of seats with students that are between 1 and 16, with no students the same.
Then we have maplist with only two arguments; previously, we called it with three. Another difference is that the predicate here is not just the name of a rule, but also an argument. constrain_pupil(Board , seat(R , C , Student)) has two arguments, but here we’re calling it with one. This means that when maplist calls that predicate, it will keep the first argument as Board, but fill in the second argument.
When maplist is called with only two arguments, it validates the list using the predicate (instead of transforming it). And when Prolog creates a relationship, it always tries to make it true. So this line applies the constraint of constrain_pupil to every seat in the board.
Now we have a board with all of the constraints we need:
- Every student is between 1 and 16
- No students are the same
- Every student satisfies
constrain_up,constrain_down,constrain_left, andconstrain_right—every student is compatible with its neighbors.
Next, we just have to pick student numbers that satisfy these constraints.
Line 96 is a line we’ve seen before: it takes the student out of each seat and saves it to a list, Raw. This will allow us to set the students in the board.
On line 97, labeling([], Raw) finally picks values for Raw that satisfy the constraints. It can use one of many strategies for this, which you can choose by passing in options to the first argument. By passing [], we use the default search strategy. It works like this:
- Take the next variable we need to set in the
Rawlist. - Assign it the smallest possible value from its allowed domain of values.
- If there are no allowed values when we try to make an assignment, backtrack to the last variable we assigned and choose a different value.
- Related variables’ domains are automatically constrained based on this assignment. For example, if we assign one student variable to
2, any student next to it will not have3as an allowed value.
Finally, with all of the students assigned, we can call write_board and print the output.
Reflections
It’s clear that the main logic of this code sample was specific to CLP(FD), the library that was imported. So I got a crash course in that as well as Prolog itself.
Based on what I learned here, the core idea of Prolog is setting up relationships for Prolog to fulfill, questions for it to answer. In the process of giving you an answer, Prolog can do elaborate work for you.
The core idea of CLP(FD) seems to be setting up constraints. As you set up constraints, you narrow in on an answer. This also lets the answer be arbitrary as long as it satisfies the constraints. In an imperative language, you’d need a specific algorithm to generate the answer, and it would have a specific form rather than a range of possibilities.
Wikipedia calls Prolog a “logic-based programming language” and says it has influenced languages like Clojure and Erlang. It’s worthwhile exploring new programming paradigms; I feel like it challenges the way I think about code, and I hope to play with Prolog again.