Humbled by Prolog

I was very excited to reach Prolog. It was something completely new to me, so much so that it made me feel like a complete beginner in a way that nothing in programming has in a very long time.

I'm working my way through Seven Languages in Seven Weeks by Bruce Tate. So far we have explored Ruby and Io.

Prolog is a declarative language. This means that instead of telling the computer how to do something you just define what that something is. The computer works out the how. SQL works like this too. In SQL you don't have to bother about implementing joins or sorting or filtering. You just describe the general shape of the data (the schema) then tell it what you want out and the database does the rest.

Prolog works on logic rather than data. You describe the general shape of the world (facts and rules) and then ask it questions to see what it can infer. It can do some really powerful stuff very easily: things that would be quite challenging in imperative languages like C and Java.

By way of example, the book shows how to solve a sudoku. Here is the program in pseudocode. It's not so far away from what you might say to someone if you were teaching them the game.

• There are 81 cells.
• Each cell must be in the range 1 to 9.
• Row 1 cannot have duplicate values
• Row 2 cannot have duplicate values
• etc...
• Column 1 cannot have duplicate values
• Column 2 cannot have duplicate values
• etc...
• Block 1 cannot have duplicate values
• Block 2 cannot have duplicate values
• etc...

Prolog takes these rules and tries different combinations of possible answers until it finds one that passes all the checks. The real program is a bit longer because code doesn't have the luxury of using etc. However, I bet there is a way to reduce the amount of repetitive code (beyond the scope of an introductory chapter).

First of all, I am blown over by how simple this is. Even the simplest naive sudoku solver in Java has all sorts of complicated control flow. Beyond that, I started to get concerned about the algorithm. Is it just going through all permutations of results? Surely that has to be slow! Mustn't it make Prolog impractical for other problems? Is there a way to fix it?

Apart from the yearning for premature optimisation in this case, I think these are valid concerns. Apparently the author did too because the next example had big problems with performance. It was the 8 queens problem: Place eight queens on a chess board so that they are not attacking each other.

This time the solution was rules about queens, rows, columns and diagonals. It was short and easy to read. But it took too long to run. The optimisation was to realise that there must be one queen on each row and to add an extra rule to the world to make this explicit. This reduced the search space and allowed the program to finish in a reasonable time.

I loved this. In every other language I know, optimisation involves mutilating the design, readability and maintainability of the program. In this example, all that was needed was an extra rule to clarify something about the world. I'm sure there is a whole suite of techniques to optimise Prolog programs but I enjoyed this example very much.

The highlight of the chapter for me was an interview with a dolphin researcher. His research group has a dolphin in a tank. They have all sorts of staff: trainers, researchers and other technical people. He has used Prolog to express all the constraints of the research so they can schedule the most experiments without overworking the poor dolphin.

Finding schedules sounds like a perfect task for Prolog but his other program was far more interesting. It models the dolphin's understanding of the world. He has constructed a program that logs all the dolphin's previous training. Then when an unexpected behaviour or response to training crops up, they can use the program to aid their understanding.

As a scientist, I find this fascinating. What would I have done in his place? I'd have probably put together a few thousand lines of Java or Ruby. It would have probably taken me a long time and cost a lot of research money. It would certainly have been slow. It would definitely be harder to maintain.

I like to think of myself as a good programmer but in this case I would have come up with a very bad solution. In programming circles, we get excited about the latest frameworks, or new languages that have different takes on familiar ideas. These are trivialities. It's far more important to have a strong foundation in a variety of programming paradigms and models. The Prolog chapter in this book was exciting and humbling in equal measure.

06 October 2014