How to get a grip on those troublesome constraints

Programming with Constraints
February 5, 1999

The level of abstraction possible in programming languages has increased over the years. Initially programmers worked at the machine instruction level, first using binary code and then assembler programming with mnemonics for the machine instructions. Next came high-level imperative programming languages such as Fortran, although these still mapped fairly directly to the underlying machine. Even relatively modern languages such as C++ and Java follow this basic paradigm.

However, it is increasingly possible to break away from the provision of sequential (or sometimes concurrent) commands for the computer and to produce programs that are nearer to a specification considering what is required rather than how it will be implemented. These so-called "declarative" approaches include functional programming (based on mathematical functions) and logic programming (based on the more general mathematical relations, allowing the possibility of non-determinism). The programmer's task is largely freed from consideration of the standard von Neumann computer architecture or (if available) of parallel computation. A declarative program can be interpreted and mapped to whatever computational facilities are available on a particular system in a generic manner.

A drawback of "standard" logic programming is that the various clauses in the program typically include a number of low-level constraints of some form, and vanilla logic programming languages such as Prolog do not give much provision for the implementation of these beyond lists and basic (not very satisfactory) arithmetic support. Often many constraints must be encoded as further clauses by the programmer for the specific problem being solved. A more helpful approach for the programmer is to attempt to make provision for such constraints in as general a way as possible.

Researchers have been experimenting with such facilities, and there are some reasonably robust commercial constraint programming systems available. However, there are not many general books in this area, especially for student teaching, so this book is to be welcomed.

The subject matter is still rather novel in terms of teaching and practical use. Thus this book is likely to be of most interest for final-year undergraduate or masters-level computer science courses. Experience of a more traditional logic programming language such as Prolog would be helpful but not essential.

I would encourage lecturers to consider a course on constraint programming for more advanced students, especially if declarative languages are not well represented on the degree course. I think this paradigm will be of increasing importance. It has the benefit of a sound mathematical basis and the ability to solve some complex problems with minimal programming effort compared with more traditional programming languages. This book draws together the various issues, previously available only from a variety of sources, into a single volume.

The book is divided into three major parts, constraints (in general), constraint logic programming or CLP (in particular), and other constraint programming languages (eg for databases and concurrent systems). An indication of core and supplementary sections is given. The book could be used by a lecturer to introduce constraint programming as part of a general course on different programming paradigms.

A major issue in practical use is efficiency. The book generally avoids this for industrial-scale problems, which may not be feasible with current technology. Optimisation of constraint problems is covered, but for now, use of CLP applications is likely to be limited to the domains over which generic constraint solvers can be employed with reasonable efficiency.

Where the approach is applicable, there can be dramatic gains in programmer productivity compared with traditional programming, as this book illustrates by its small but powerful examples. Equivalent imperative programs would be many times larger and take longer to develop.

This book has no direct competition in its (still rather niche) field, but I believe it will be the first of a number of more didactic books in this area. Certainly it is a worthy, comprehensive and scholarly contribution that should help open up the field at advanced undergraduate and taught-postgraduate level.

Jonathan Bowen is lecturer in computer science, University of Reading.

Programming with Constraints: An Introduction

Author - Kim Marriott and Peter J. Stuckey
ISBN - 0 262 13341 5
Publisher - MIT Press
Price - £28.50
Pages - 467

You've reached your article limit.

Register to continue

Registration is free and only takes a moment. Once registered you can read a total of 3 articles each month, plus:

  • Sign up for the editor's highlights
  • Receive World University Rankings news first
  • Get job alerts, shortlist jobs and save job searches
  • Participate in reader discussions and post comments
Register

Have your say

Log in or register to post comments