Towards a compiler for a constraint language

ABSTRACT

For many engineering tasks, constraints are a useful knowledge representation formalism to specify functional relationships. In this paper, we describe a programming language based on constraints which, unlike former approaches, enables us to handle sets of possible values (rather than single values) and to filter them until consistent subsets are obtained that satisfy the constraints.As, e.g., in technical systems, the constraint relations are of different complexity, structure, and applicability, several ways to describe a relation are provided. Different control strategies are available, computing local consistency as well as globally consistent solutions. It is sketched how to realize a compiler for the language, which optimizes constraint descriptions during definition time. As a result, combinatorial explosion can be reduced, depending on the number of variables used in a constraint description.CONSAT is used in several applications, for example, in a system for process diagnosis [Voss 1988], where constraints are applied to maintain functional relationships in physical units. For this purpose, CONSAT was incorporated into the hybrid knowledge representation system BABYLON in order to use constraints together with rules, frames, and Prolog [Guesgen et al. 1987].

REFERENCES

• Freuder 1982: Eugene C. Freuder, A Sufficient Condition for Backtrack-Free Search, Journal of the ACM (JACM), v.29 n.1, p.24-32, Jan. 1982 [doi>10.1145/322290.322292]
• Guesgen et al. 1987: H.W. Guesgen, U. Junker, A. Voss: Constraints in a Hybrid Knowledge Representation System. In: Proceedings of the IJCA187, Milan, Italy, 1987, 30-33.
• Guesgen, Hertzberg 1988: H. W. Gusgen , J. Hertzberg, Some fundamental properties of local constraint propagation, Artificial Intelligence, v.36 n.2, p.237-247, September 1988 [doi>10.1016/0004-3702(88)90004-5]
• Mackworth 1977: A. K. Mackworth: Consistency in Networks of Relations. Artificial Intelligence 8 (1977) 99-118.
• Steele 1980: Guy L. Steele, Jr., The Definition and Implementation of a Computer Programming Language Based on Constraints, Massachusetts Institute of Technology, Cambridge, MA, 1980
• Voss 1988: H. Voss: Architectural Issues for Expert Systems in Real-Time Control. To appear in: Proceedings of the 1st IFAC Workshop Artificial Intelligence in Real- Time Control, 1988.
• Waltz 1972: David L. Waltz, Generating Semantic Descriptions From Drawings of Scenes With Shadows, Massachusetts Institute of Technology, Cambridge, MA, 1972

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Compilers

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.4 Knowledge Representation Formalisms and Methods
          Subjects: Representations (procedural and rule-based)

General Terms:
Design, Languages, Theory