Specification and generation of constraint satisfaction systems
William Leler · 1987
Constraint languages are declarative languages that have been used in various applications such as simulation, modeling, and graphics. Unfortunately, despite their benefits, existing constraint languages tend to be application-specific, have limited extensibility, and are difficult to implement. This dissertation presents a general-purpose computer language that makes it much easier to describe and implement constraint satisfaction systems. This language, called Bertrand, supports a rule-based programming methodology and also includes a form of abstract datatype. It is implemented using a new inference mechanism called augmented term rewriting, which is an extension of standard term rewriting. Using rules, a Bertrand programmer can describe new constraint satisfaction mechanisms, including equation solvers. Rules can also be used to define new types of objects and new constraints on these objects. Augmented term rewriting uses these rules to find a model that satisfies a set of user-specified constraints. The simple semantics of augmented term rewriting makes it possible to take advantage of several known techniques for optimizing execution speed, such as fast pattern matching, compilation, constant propagation, and concurrency. Consequently, Bertrand programs can be executed efficiently using an interpreter or compiled to run on a conventional or parallel processor. This dissertation surveys existing constraint satisfaction techniques and languages, and shows how they can be implemented in Bertrand. It also gives a precise operational semantics for augmented term rewriting. Techniques for efficient execution, including interpretation and compilation, are presented. Finally, examples are given using Bertrand to solve problems in algebra such as word problems and computer aided engineering, and problems in graphics, such as computer aided design, illustration, and mapping.