ACM Computing Surveys XX(Y), MMM 1996,
http://www.acm.org/surveys/xxxxxxxxx/. Copyright 1996 by the
Association for Computing Machinery, Inc. See the permissions
statement below.
Manuel Hermenegildo
Categories and subject descriptors:
A.1 [Introductory and Survey]:
D.1.6 [Programming Techniques]: Logic Programming
D.1.m [Programming Techniques]: Miscellaneous[constraint
logic programming]
D.3.2 [Language Classifications]: Concurrent, Parallel, and
Distributed Languages
D.3.4 [Programming Languages]: Processors[compilers]
F.1.2 [Modes of Computation]: Parallelism and Concurrency
F.3.1 [Logics and Meaning of Programs]: Specifying, Verifying
and Reasoning about Programs
General Terms: Languages, Program Analysis, Program Implementation,
Paralllelism and Concurrency, Distribution.
Additional Keywords and Phrases: Constraint Programming, Implementation
Technology, Global Analysis, Parallelism, Debugging, Visualization,
Distributed Programming, Global Programming.
CLIP Group,
Department of Artificial Intelligence
School of Computer Science,
Technical University of Madrid (UPM), Spain
herme at fi.upm.es,
http://clip.dia.fi.upm.es/~herme/
Abstract: We propose a number of challenges for
future constraint programming systems, including improvements in
implementation technology (using global analysis based optimization
and parallelism), debugging facilities, and the extension of the
application domain to distributed, global programming. We also
briefly discuss how we are exploring techniques to meet these
challenges in the context of the development of the CIAO constraint
logic programming system.
Constraint programming languages [JM94,Hen89a] are among the very few new language proposals that are seeing industrial success while being based on a novel programming paradigm. Intervening factors in this fact appear to be the expressiveness awarded by the high level of these languages, the combination of search and incremental constraint solving capabilities, and the relative efficiency of the resulting applications. These characteristics are added to the strengths in general-purpose symbolic processing of the underlying logic programming kernel on which they are often built. Constraints extend this kernel to numerical domains and beyond, offering a natural platform in which applications combining symbolic and numeric computing can be easily developed. This initial success notwithstanding, it seems important to identify significant challenges which lay ahead for constraint programming. Without any pretense of being exhaustive, we herein touch upon some challenges in the areas of implementation technology, network-wide programming, and language and system design.
The performance of current constraint logic programming systems often compares favorably to other constraint solving and symbolic programming tools. However, their performance is still lower than that of traditional imperative languages, specially in (non constraint related) numerical computations. A possible solution is to develop advanced compilation technology capable of detecting the cases where limited or no constraint solving is involved and compiling those cases in the most efficient way. Some promising progress has already been made towards this goal. The efficiency and effectiveness of global analysis of logic programs is already established [WHD88], and essentially the same performance as imperative languages has been achieved in some experimental systems (e.g., [RD92]). Some results on the possible speedups attainable in constraint logic programming have been reported (e.g., [MS92,GBH96]), some practical frameworks for global analysis developed (e.g., [GHB+96]), and a few systems described which perform global analysis based optimization [KMM+96,GBH96]. Such global analysis has also been applied to concurrent constraint programming systems, where one of the most important objectives is to reduce suspension and resumption of goals and synchronization overhead [CMFW93,MFP93,MGH94,KS92,MRB+94,GMS95]. Recent progress in incremental and compositional global analysis [MFP93,HPMS95,BCHP96] appears to solve most remaining problems related to dealing with large programs and the interactive program development environment that is common in constraint programming systems. However, the application of extensive optimization in commercial or widely used public domain systems still remains a goal to be achieved. Also, much research remains to be done in finding accurate abstraction domains for standard constraint systems.
Program parallelization is becoming a more and more interesting optimization since multiprocessing hardware is starting to be in many cases the default installation platform. This is often the case, for example, for departmental servers where multiprocessors using using fast, inexpensive, off-the-shelf processors are replacing mainframes at a fraction of their cost. Some high-end workstations are also multiprocessors. It appears likely that this trend towards increased use of parallelism will continue as multiprocessor architectures are better understood, interconnection network performance increases with new technologies (specially if the promise of optical interconnect is finally delivered), and feature size diminishes allowing placement of several processors on the same chip.
The interest of the study of parallelism in logic and constraint logic programs goes beyond the paradigms themselves. In fact, these languages allow studying challenging issues in parallelization while remaining in the context of a relatively clean and well understood framework for which application codes are available. Such challenging issues include inter-procedural parallelization, irregular computations, recursion, complex data structures with (well behaved) pointers, and speculative parallelism. These issues have already been studied in the context of logic programs [CC94], where significant speedups have been obtained. In the context of constraint logic programming, exploitation of parallelism in the search (or-parallelism) is comparatively easy and has been shown to achieve significant speedups in constraint programs containing independent search [Hen89b,Eur93,Le93]. On the other hand, and as pointed out in [JM94], comparatively little work has been devoted so far to exploiting parallelism within a given path of the search (and-parallelism) and in the solver itself. Although traditional concepts of independence used in imperative programming (e.g., the ``Bernstein conditions'') or even those of logic programming, do not apply in the context of CP [GHM93], notions of independence appropriate for (concurrent) CP have been recently proposed [GHM93,BHMR94]. Our group has since been tackling the issue of automatic parallelization and has recently developed an automatic parallelizing compiler for constraint logic programs, with encouraging initial results [GBH96]. While it may prove the case that there is often not much parallelism in constraint solving kernels, we believe that over the set of all programs the technology will eventually prove as successful as in the context of logic programming. However, proving this and developing new parallelization technology for constraint logic programs remains an area for future work.
An area in which current constraint logic programming systems have been found lacking by users developing industrial applications is debugging, in terms of ensuring correctness as well as understanding and improving performance of the program. Possible solutions can be based on both static and dynamic techniques. One technique is the use of assertions [DNTM89,BCHP96]. Assertions can be seen as a generalization of type systems (often including directional types), in which relatively general preconditions and postconditions can be declared for procedures. Assertions can be provided by the user and checked at compile-time or run-time. Compile-time checking can in some cases be done via global analysis. Furthermore, assertions can be generated by the compiler, which the user can then inspect in order to detect high-level errors (here, the same technology used by the compiler for optimization purposes can be used). Another possible technique is the use of visualization, both of the search space and of the constraint store at different points of the execution (e.g., [Mei96]). The development of more useful assertions, assertion checking and generation algorithms, and visualization paradigms for constraint programming remains a challenge.
Another challenge for constraint programming systems is related to the role of such systems in network-wide programming. This type of programming is likely to be of growing importance since the recent wider diffusion of the Internet and the popularity of the ``World Wide Web'' -WWW- protocols, which effectively provide a platform that is standard and ubiquitous and allows a new class of highly sophisticated distributed applications. Constraint logic programming systems already offer many characteristics which appear to place them well for making an impact in this area. Some of these characteristics, including dynamic memory management, well behaved structure and pointer manipulation, robustness, and compilation to architecture independent byte-code, are shared with other proposed network programming tools. In addition, constraint logic programming systems offer a quite unique set of other built-in features including dynamic databases, search facilities, grammars, sophisticated meta-programming, constraint solving capabilities, and well understood semantics. In addition, the theory of concurrent constraint programming offers a novel and very rich notion of inter-process communication based on constraint entailment [Mah87,SRP91]. Some of these characteristics, such as the built-in database and grammars, can facilitate the rapid coding of relatively simple applications, even by naive end users. Furthermore, it seems natural that the more sophisticated network applications, such as intelligent information retrievers or distributed decision making systems, will require complex symbolic and numeric capabilities, including natural language processing, at which constraint programming (and, in particular, constraint logic programming) has already been shown particularly successful [PAC].
Sophisticated distributed applications can be developed with current constraint logic programming systems using the available low-level primitives to build communication abstractions such as blackboards [AAF+91,CH95,TB96] and even incorporating distributed variable-based communication (which can be supported, for example, using attributed variables [HCC95]). In our experience the main feature found lacking in standard systems is native support for concurrent execution. While many systems allow starting a whole subprocess via the operating system interface and this can provide the desired functionality, it is very inefficient. A more direct support for concurrency (perhaps along the lines of that present in the AKL [JH91], Oz [Smo95], and CIAO [HtCg94,HBGP95] systems) seems highly desirable and we feel should be provided in all future constraint programming systems. One additional important use of concurrency is in implementing complex, delay based constraint solving algorithms. However, concurrency brings important new challenges in many areas. As mentioned before, an important one from the implementation point of view is developing effective analysis and optimization techniques.
Distributed concurrent constraint systems are currently being worked on [CH95,HVS96], distribution and application development libraries are being offered (e.g., [HCC95,CHV96]), and network and WWW applications are being reported [TDDBH96]. CP is a promising foundation for many aspects of the next generation of distributed systems, but it still remains as a challenge to develop simple, elegant and practically usable environments, and to demonstrate applications of such environments.
We are developing a concurrent constraint logic programming system, ``CIAO'', which illustrates our own ideas on how to approach some of the challenges that we have set forward in the previous paragraphs [HtCg94,HBGP95]. At the user level CIAO is a programming environment offering support for full standard Prolog, as well as several constraint domains, several control rules, a module and object system, and concurrency, synchronization, and distribution primitives. As opposed to other concurrent constraint languages such as AKL [JH91] or OZ [Smo95], the language is ``sequential by default'', in the sense that concurrency is annotated explicitly by the user. Optional control rules include for example the determinate-first principle [SCWY90]. A rich set of assertions is available which the compiler understands and both generates and checks by means of global analysis techniques based on abstract interpretation. These assertions include a flexible type system.
At the implementation level most functionality is implemented via source to source transformation into a simple kernel language, which is then the subject of extensive analysis and optimization, using a single set of analysis and transformation tools. High-level optimizations include parallelization, granularity control, reduction of concurrency and synchronization, reordering of goals, code simplification, and specialization. Distributed and network-wide programming are implemented via libraries [HCC95,CHV96]. One of the main features of the kernel language and the abstract machine underlying it is the support for concurrency and parallel execution, based on an extension of the capabilities of the &-Prolog engine [HG91]. CIAO is currently being used both as a workbench for testing implementation techniques (many of the program analysis and transformation systems referenced elsewhere have been prototyped on CIAO) and a powerful programming environment. Current versions of the &-Prolog and CIAO systems, and the related libraries are publicly available for experimentation (see https://cliplab.org/ for both software and publications).
Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, to republish, to post on servers, or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from Publications Dept., ACM Inc., fax +1 (212) 869-0481, or permissions@acm.org.