This is a selection of papers that represents current work in constraint handling rules (CHR), a logic programming language. I appreciated a small number of papers that are longer than the standard conference paper, as it enabled topics to be explored to a depth often missed when there is a page limit.

The third paper, “Constructing rule-based solvers for intentionally-defined constraints,” starts with a quote:

Constraint programming represents one of the closest approaches computer science has yet made to the Holy Grail of programming: the user states the problem, the computer solves it.

It is questionable whether this really is the Holy Grail of programming. Experience suggests that writing specifications is often as hard or even harder than writing code. A sophisticated algorithm that, given a specification, returns results without the need for an intermediate stage of executable code may leave us more baffled if it gives us the wrong results than one that has code we can analyze. It may disguise a possible rather poor algorithm for actually solving a problem, since what we have is a metasolver, rather than a direct solver of the problem.

While I can see there are some problems that are amenable to the constraint programming approach, the main concern I have with this collection is that it makes some grand claims, while I am left uncertain on how widely applicable it really is. The papers in this book concentrate almost entirely on well-known toy problems. I would to at least one paper showing CHR being used on a more realistic problem. There are hints in some of the papers that effective use of CHR requires sophisticated knowledge of what happens underneath, for example a suggestion for adding priorities to control search behavior. I’m concerned that academic research on programming languages has become very inward looking, producing languages that are baffling to all but academic researchers. The dense network of citations to their own work or that of close colleagues, in these papers, is a symptom that leads to this concern.

CHR is a specific programming language, but, like most modern programming languages, it can be linked with other programming languages for use in a larger system. This is what has become of logic programming since the paradigm hit the headlines when the Japanese Fifth Generation Project adopted it in the 1980s, and was then dismissed as a failure. The project failed partly because it was wildly overambitious, but one spinoff from it has recently emerged as useful. The programming language Erlang, currently promoted as the best prospect for controlling multicore architectures, owes its origin to the logic programming work of the 1980s. Erlang hid its logic programming origins, but CHR adheres directly to the logic programming ideal of a programming language: statements in the language are viewed as clauses in predicate logic, and its execution model as logical proof.

Most people who know of logic programming think of it as synonymous with Prolog, but Prolog is a case of the prototype that never got thrown away. Prolog was meant to be a simple demonstration, with just a crude depth-first/backtracking search algorithm. The intention was that once Prolog demonstrated the possibility of logic programming, programming languages that captured more fully predicate logic and its variety of proof techniques would be developed. Experimental languages closer to the ideal of programming as logic were proposed, but none replaced Prolog for practical use. Perhaps Prolog’s very simple operational model explains its longevity, while languages closer to full logic, but with more complex operational models, fade.

CHR needs to be considered in this context. Programs in CHR have a similarity to programs in Prolog, but, whereas Prolog only has rules for logical consequence, CHR has rules for logical equivalence and “simpigation” rules that combine both. Logical equivalence enables facts to be removed from the store; this, with the propagation of logical consequence, transforms the store to a state where the answers are given and new facts are derived as logical consequences of the facts and constraints already known. The operational semantics that order the application of these rules make the full programming language.

One of the papers gives an extension where the rules may include both disjunction and conjunction. Another gives an extension with probabilistic abductive reasoning, which means suggesting a possible but not provable fact as the most-likely explanation for an observed situation.

The book demonstrates the considerable effort put into developing CHR, but leaves me feeling that it needs to be balanced by wider promotion, to see if it can stand up as a genuinely useful tool.