The semantics of constraint logic programs

✍ Scribed by Joxan Jaffar; Michael Maher; Kim Marriott; Peter Stuckey

• Publisher: Elsevier Science
• Year: 1998
• Tongue: English
• Weight: 350 KB
• Volume: 37
• Category: Article
• ISSN: 0743-1066
• DOI: 10.1016/s0743-1066(98)10002-x

✦ Synopsis

The Constraint Logic Programming (CLP) Scheme was introduced by Jaar and Lassez. The scheme gave a formal framework, based on constraints, for the basic operational, logical and algebraic semantics of an extended class of logic programs. This paper presents for the ®rst time the semantic foundations of CLP in a self-contained and complete package. The main contributions are threefold. First, we extend the original conference paper by presenting de®nitions and basic semantic constructs from ®rst principles, giving new and complete proofs for the main lemmas. Importantly, we clarify which theorems depend on conditions such as solution compactness, satisfaction completeness and independence of constraints. Second, we generalize the original results to allow for incompleteness of the constraint solver. This is important since almost all CLP systems use an incomplete solver. Third, we give conditions on the (possibly incomplete) solver which ensure that the operational semantics is con¯uent, that is, has independence of literal scheduling.