Hasso-Plattner-Institut25 Jahre HPI
Hasso-Plattner-Institut25 Jahre HPI

Tim Felgentreff

The Design and Implementation of Object-Constraint Programming

Constraints allow developers to specify desired properties of systems and have those properties be maintained automatically. This results in compact, declarative code in interactive applications, avoiding scattered code to check and imperatively re-satisfy invariants in response to user input that perturbs the system. Constraints thus provide flexibility and expressiveness for solving complex problems and maintaining a desired system state. Despite these advantages, constraint programming is not yet widespread, with imperative programming still the norm.

There is a long history of research on constraint programming as well as its integration with general purpose programming languages, and especially the imperative paradigm. However, this integration typically does not unify the constructs for encapsulation and abstraction from both paradigms, and often leads to a parallel world of constraint code fragments and abstractions intermingled with the general purpose code. This impedes re-use of modules, as client code written in one paradigm can only use modules written to support that paradigm and modules require redundant definitions if they are to be used in both paradigms. Furthermore, clear distinction between the paradigms requires developers to learn about and fully understand both paradigms to make use of them.

In our work, we have developed a design for a family of object-constraint language called Babelsberg. Our design unifies the constructs for encapsulation and abstraction by using only object-oriented method definitions for both declarative and imperative code. Just like assertions, our constraints are expressed using ordinary imperative expressions, including full objects and message sends. Unlike assertions, however, the system attempts to satisfy them if they are not currently true, and keeps them satisfied throughout the rest of the execution. We provide a semantics that guides implementers of our design to combine Babelsberg with existing, object-oriented host languages both semantically and syntactically, and demonstrate its feasibility with an executable semantics and three concrete implementations of Babelsberg. To allow developers to use the power of constraints without having to understand the specifics of different constraint solving strategies, we integrate an architecture for using multiple cooperating solvers. Finally, based on our experience with the concrete implementations, we propose performant implementation strategies of key features for object-constraint programming.

We argue that our approach provides a useful step toward making constraint solving a useful tool for object-oriented programmers. We also provide example code, written in our implementations, which use constraints in a variety of application domains, including interactive graphics, physical simulations, data streaming with both hard and soft constraints on performance, or interactive puzzles.