Accession Number:

ADA256191

Title:

Design and Implementation of Practical Constraint Logic Programming Systems

Descriptive Note:

Doctoral thesis

Corporate Author:

CARNEGIE-MELLON UNIV PITTSBURGH PA SCHOOL OF COMPUTER SCIENCE

Personal Author(s):

Report Date:

1992-08-24

Pagination or Media Count:

240.0

Abstract:

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 CLPR, whose domain is uninterpreted functors over real numbers, is the central case study. First, the design of CLPR 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 CLPR, 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 CLPR approaches that of imperative programming languages.

Subject Categories:

  • Computer Programming and Software

Distribution Statement:

APPROVED FOR PUBLIC RELEASE