Date: April 8, 2025

This month marks an exciting time for my upcoming release of Logic for Programmers. As part of the enhancements, I am completely overhauling the chapter dedicated to Logic Programming Languages. This revision is intended to provide a more practical understanding of these languages by replacing the existing puzzle-solving examples, such as the classic eight queens problem and four-coloring challenges, with more applicable programs that could inspire readers to consider how Prolog might be beneficial in their everyday tasks.

Puzzles have always been a popular way to demonstrate the capabilities of programming paradigms. The ability of a computer program to tackle these complex challenges often feels like magic to those of us who understand the creativity and insight required for human problem-solving. Yet, in my quest to create a practical guide, I want to focus on examples that resonate more with real-world applications.

However, for a newsletter piece, I believe showcasing a puzzle solver can still be quite engaging. Recently, I came across an intriguing post by my friend Pablo Meier, who effectively employs Prolog to solve a video game puzzle. The puzzle involves ten true/false questions, represented as a/b, and four student attempts. Our goal is to determine the fourth student's score based on the scores of the first three students:

• bbababbabb = 7
• baaababaaa = 5
• baaabbbaba = 3
• bbaaabbaaa = ???

You can explore Pablo's solution and even attempt it using SWI-Prolog.

After spending considerable time studying Prolog for the sake of this book chapter, I was motivated to discover whether I could present a more elegant solution than Pablo's. What follows includes both code and spoiler alerts regarding the puzzle's solution.

In a typical introduction, I would link to a more gentle tutorial I crafted, but given that this might be my first public discussion about Prolog, I will instead reference a Picat introduction for those unfamiliar with logical programming.

The Program

For those eager to get hands-on, you can test this all online using SWISH, or you can directly check out my finalized version of the code.

:- use_module ( library ( dif )). % Enables sound inequality:- use_module ( library ( clpfd )). % Applies finite domain constraints

Initially, we import necessary libraries. The dif library permits us to define dif(A, B), which becomes true if A and B are unequal. Meanwhile, clpfd allows us the convenience of stating relationships, such as A #= B + 1, indicating that 'A' is one greater than 'B'.

We will treat both the students' submissions and the answer keys as lists, where each entry corresponds to either 'a' or 'b'. In Prolog, identifiers that are lowercase are recognized as atoms (analogous to symbols in other programming languages), while those beginning with a capital letter are treated as variables. Prolog's strength lies in its ability to find values for these variables that fulfill defined equations, a process known as unification.

To illustrate how the scoring works, consider the following query:

% ?- means query?- L = [ a , B , c ], [ Y | X ] = [ 1 , 2 | L ], B + 1 #= 7.B = 6 , L = [ a , 6 , c ], X = [ 2 , a , 6 , c ], Y = 1

Next, we will define a recursive predicate for score/3 to compute the students test score:

% The student's test score% score(student answers, answer key, score)score ([], [], 0 ).score ([ A | As ], [ A | Ks ], N ) :- N #= M + 1 , score ( As , Ks , M ).score ([ A | As ], [ K | Ks ], N ) :- dif ( A , K ), score ( As , Ks , N ).

In this definition, the first argument represents the student's answers, the second is the answer key, and the third provides the final score. The base case is defined as an empty test, which naturally has a score of zero. For non-empty tests, we compare the head values of each list. If they match, we increment the score; if they differ, we retain the score as is.

Its important to note that instead of traditional conditional statements like if x then y else z, we leverage pattern matching to succinctly express logical conditions. Prolog does possess a conditional operator, but using it limits the flexibility of backtracking, thus reducing its usefulness.

Exploring Bidirectionality

One of the most fascinating features of Prolog is that all purely logical predicates are bidirectional. Using the score predicate, we can verify if a student's expected score is accurate:

?- score ([ a , b , b ], [ b , b , b ], 2 ).true

Alternatively, we can input answers and a key to retrieve the score:

?- score ([ a , b , b ], [ b , b , b ], X ).X = 2

Moreover, we can also query the key and a desired score to ascertain what answers would yield that score:

?- score ( X , [ b , b , b ], 2 ).X = [ b , b , _ A ], dif ( _ A , b )X = [ b , _ A , b ], dif ( _ A , b )X = [ _ A , b , b ], dif ( _ A , b )

In this case, the variable _A represents an answer that we havent explicitly constrained to be either 'a' or 'b', but well address this in due course.

Returning to the Program

Now that we have a functional scoring system, our next task is to deduce a possible answer key that aligns with the collected data, thereby providing accurate scores for all students:

key ( Key ) :-% Determine key validityscore ([ b , b , a , b , a , b , b , a , b , b ], Key , 7 ),score ([ b , a , a , a , b , a , b , a , a , a ], Key , 5 ),score ([ b , a , a , a , b , b , b , a , b , a ], Key , 3 ).

Thus far, we have not explicitly stated that the length of the key must correspond to the length of the students' answers, which is only implicitly verified by the score predicate. It's prudent to add the clause length(Key, 10) to ensure the key has the correct number of entries. Furthermore, we should specify that each element of the key must be either 'a' or 'b'. Instead of creating a separate predicate for each constraint, we can utilize maplist. This function takes a list and applies the predicate to each element, simplifying our code.

contains ( L , X ) :- member ( X , L ).key ( Key ) :- length ( Key , 10 ), maplist ( contains ([ a , b ]), L ), % the score stuff

After writing this, we can query to find the key:

?- key ( Key )Key = [ a , b , a , b , a , a , b , a , a , b ]Key = [ b , b , a , b , a , a , a , a , a , b ]Key = [ b , b , a , b , a , a , b , b , a , b ]Key = [ b , b , b , b , a , a , b , a , a , b ]

Interestingly, our findings reveal four different keys that could all potentially explain the dataset. Does this imply multiple answers to the puzzle?

Not quite!

The objective wasn't to uncover the exact answer key, but rather to determine the score of the fourth student. When we query for this, we find that all four keys yield the same score for the fourth student:

?- key ( Key ), score ([ b , b , a , a , a , b , b , a , a , a ], Key , X ).X = 6X = 6X = 6X = 6

Its always satisfying when a puzzle appears to present various solutions, yet they converge on a single answer.

In total, my program is a streamlined 15 lines of code, which is a significant reduction from the original 80 lines. Take that, Pablo!

For those interested, you can also retrieve all answers simultaneously by implementing findall(X, (key(Key), score($answer-array, Key, X)), L).

Nevertheless, I find that puzzles might not always be the most effective teaching tools.

The practical examples I am incorporating into the book revolve around analyzing version control commit graphs and planning infrastructure changes, topics that are far more relevant to real-world applications in the workplace. Look out for these in the next release!

If youre reading this article online, consider subscribing to my updates here. I send out newsletters every week, and for more information, you can visit my main website.

Also, Im thrilled to share that my new book, Logic for Programmers, is currently available in early access! You can grab your copy here.