Sat Apr 7 08:13:12 EST 2012

Programming in Prolog

Another programming book. I picked up Clocksin and Mellish's Programming in Prolog after the former second mate encouraged me to learn more about Prolog. Before this, my only exposure to the language was a single lecture at the end of COMP2600 and that old joke ("How many prolog programmers does it take to change a lightbulb? No.").

The first thing that struck me about the book is how honest it is. The authors are very careful to always use the correct terms for everything (predicates, facts and so on) and not hand-wave away things by analogy to more conventional languages.

The main idea behind Prolog is that instead of writing a detailed procedure to compute a result, the programmer needs only to describe the solution and perhaps guide the backtracking algorithm a little bit to keep the search space manageable. An interesting consequence is that the standard library can be a lot smaller. Instead of needing six functions to slice lists six different ways, many of them can be described in terms of "append".

The problem with this is that because of the size of the search space, Prolog has to provide a "cut" operator that commits the search to choices made so far. The trouble with cut is that it can prevent the rules from generating correct (or all of the correct) results when called in reverse. Not only that, but it's not often obvious how a predicate works: it's hard to see which parts will be called forwards and which will be called backwards depending on which way the matcher is trying to instantiate a given rule.

The standard library is also a bit quirky: input and output (as described in the text) can only be done by temporarily redirecting standard input and standard output. Being a bit old, the naming of some of its predicates are a bit odd: files are "consult"ed instead of loaded, input is "see"n instead of read and so on. "assert" isn't used to catch bugs but instead adds new facts and rules to the database.

Even so, Prolog's a pretty elegant language. The basic structure of atoms and functors continues all the way down to the rule definition (:-) and interrogation (?-) operators, and this enables the authors to present a small metacircular evaluator midway through the book.

I'm glad I took the time to learn about Prolog. As a declarative language I've only really seen it lumped alongside make in "lists of languages you should at least read about", but that's a poor comparison. Sure, both are declarative, but their underlying models and methods for determining what work to do are completely different. Even if you grok "make", set aside a few hours to read about Prolog.


Posted by Jack Kelly | Permanent link | File under: readings