Week 3: Prolog

August 31st, 2013

Prolog is the first language that completely gets me out of my comfort zone and brought me back to noob. Prolog is a pretty amazing language that at first makes you wonder how it knows so much.

Bruce picked the Rain Man character for Prolog. I can see this resemblance. They both are a great source of knowledge, if you get your questions right. Many times you’re left wondering ‘how did he know that?!’.

In the beginning I was in a continuous struggle to get to my questions right. The first hour or so I had to get used to thinking only in terms of rules and recursion. My brain seems adjusted for being able to return values. At first this made it more difficult to reason about the code and the problems at hand.

After some fooling around and getting not much done without some help, I took a different approach. I started evolving the code in really small increments, trying each increment in the prolog repl. This really helped and got me gain a better understanding of the language.

Simple algorithms like fibonacci and bubblesort that were hard at first (writing them in a single attempt) were suddenly easier to get done.

The fibonacci algorithm gave me a little deeper insight into Prolog. I implemented a tail recursive calculation of the fibonacci sequence that gave me the fibonacci number at a certain point in the index (e.g. the fibonacci of index 6 is 8) and I wondered why Prolog couldn’t reverse the rules and give me the index of a provided fibonacci number (e.g. the index of 8 is 6).

That’s when I saw the difference between functions and rules. The fibonacci algorithm is a function and in fact there is no way for Prolog to revert the algorithm like it can with rules. After some googling if fibonacci can be done with rules, it seems to be solvable by applying the Constraint Logic Programming library (or CPL).

The Sudoku solver was surprisingly simple. I took the solution from the book a bit further by generalizing it for mutiple valid Sudoku puzzle sizes (4x4, 6x6, 9x9). As I choose to stick with GNU prolog I had to write some utility functions to make for a more general solver (like partition, transpose, take, first, etc).

I wrote these utility functions using actual TDD [by which I mean here having a set of tests I can run every time I want to, rather than using the repl]. This made it a lot easier. Interestingly, I ended up taking somewhat larger increments than I would normally use.

My solutions to the more interesting exercises in the book (like the Sudoku solver) are available in the 7-languages-in-7-weeks repository on my Github profile.

Prolog is a very interesting language that makes solving the right problem a breeze. Basically it provided all-or-nothing solutions. If it cannot find a solution to the proposed problem it just prints ‘no’. This is where you have to adjust your questioning and retry.

After a bit of a puzzling start I had great fun using Prolog. It has an interesting way of thinking about the problem and describing the problem domain itself rather than a recipe for the solution. If I again come across a problem that is well suited for Prolog, I will take this advantage.

For now this is where I leave Prolog and move to my next destination: Scala. See you in a week!