page 1  (16 pages)
2to next section

Integrating efficient records into

concurrent constraint programming

Peter Van Roy1, Michael Mehl2, and Ralf Scheidhauer2

1 Swedish Institute of Computer Science, Stockholm, Sweden
2 Programming Systems Lab, DFKI, Saarbr?ucken, Germany

Abstract. We show how to implement efficient records in constraint logic programming (CLP) and its generalization concurrent constraint programming (CCP). Records can be naturally integrated into CCP as a new constraint domain. The implementation provides the added expressive power of concurrency and fine-grained constraints over records, yet does not pay for this expressivity when it is not used. In addition to traditional record operations, our implementation allows to compute with partiallyknown records. This fine granularity is useful for natural-language and knowledge-representation applications. The paper describes the implementation of records in the DFKI Oz system. Oz is a higher-order CCP language with encapsulated search. We show that the efficiency of records in CCP is competitive with modern Prolog implementation technology and that our implementation provides improved performance for naturallanguage applications.

Keywords. Concurrent Constraint, Record, Logic Programming, Implementation, Natural-Language Processing, Prolog

1 Introduction

Records are an important data structure with many advantages for program structuring and understandability. It has been shown that records can be naturally integrated into concurrent constraint programming (and therefore also into constraint logic programming) as a new constraint domain [19]. This gives a simple logical explanation of feature structures in natural-language processing (NLP). Erbach and Manandhar mention record constraints as a first requirement for future NLP systems [6].

This paper presents the implementation of records in the DFKI Oz system [16]. We evaluate the implementation according to its complexity as well as its space and time performance. Our implementation generalizes in two ways the compound structures (trees) of Prolog:
{ Concurrent constraints. From the implementation viewpoint, the generalization of CLP(X) to CCP(X), where X is the constraint domain, requires two changes. First, the system is concurrent{there are multiple activities that evolve independently. Second, the system requires two basic operations on the constraint domain X, namely satisfiability and entailment checking (see Sect. 7). A CLP(X) language requires only a single operation on the domain X, namely a satisfiability check. We show that the two basic operations can be efficiently implemented for records.

In Proceedings of PLILP'96, Aachen, Germany, September 1996, Springer.