Design and Implementation of Practical Constraint Logic Programming Systems

摘要

The Constraint Logic Programming (CLP) scheme, developed by Jaffar and Lassez,defines a class of rule-based constraint programming languages. These generalize traditional logic programming languages (like Prolog) by replacing the basic operational step, unification, with constraint solving. While CLP languages have a tremendous advantage in terms of expressive power, they must be shown to be amenable to practical implementations. This thesis describes a systematic approach to the design and implementation of practical CLP systems. The approach is evaluated with respect to two major objectives. First, the Prolog subset of the languages must be executed with essentially the efficiency of an equivalent Prolog system. Second, the cost of constraint solving must be commensurate with the complexity of the constraints arising. The language CLP(R), whose domain is uninterpreted functors over real numbers, is the central case study. First, the design of CLP(R) is discussed in relation to programming methodology. The discussion of implementation begins with an interpreter that achieves the efficiency of equivalent Prolog interpreters, and meets many of the basic efficiency requirements for constraint solving. Many of the principles applied in the interpreter are then used to develop an abstract machine for CLP(R), leading to a compiler-based system achieving performance comparable to modern Prolog compilers. Furthermore, it is shown how this technology can be extended so that the efficiency of CLP(R) approaches that of imperative programming languages.