The Design and Implementation of Kaleidoscope, A Constraint Imperative Programming Language

Author: Gus Lopez

Ph.D. dissertation, Department of Computer Science and Engineering, University of Washington, April 1997. Published as UW Tech Report 97-04-08.

Abstract

A constraint is a relation that should be maintained. Constraints are well-suited for object-oriented programming, particularly domains such as interactive graphics and simulation. The Constraint Imperative Programming family of languages combines declarative constraints with imperative object-oriented programming and was developed to allow constraints to respond to a change in object structure. This dissertation presents contributions to the design and implementation of constraint imperative languages.

A design for a constraint imperative language, Kaleidoscope, is presented that is based on a perturbation model for mutable objects, consistent with object mutation in conventional object-oriented languages. Aliasing is an implicit relation that conflicts with the declarative nature of constraints. A declarative mechanism for object identity is described that generalizes constraints to different aspects of object structure.

The major drawback of CIP with respect to multi-way constraints systems is performance, particularly for constraint-intensive programs. The performance gap between user-defined constraints in constraint imperative languages and constraint solvers used by conventional object-oriented languages is dramatically reduced by incremental constraint satisfaction optimizations in the Kaleidoscope virtual machine. The runtime penalty for using constraints in CIP languages is further reduced by static constraint satisfaction techniques.

full version (this is a directory containing postscript files for the dissertation, one file per chapter).

Constraints home page