Brought to you by EarthWeb
IT Library Logo

Click Here!
Click Here!

Search the site:
 
EXPERT SEARCH -----
Programming Languages
Databases
Security
Web Services
Network Services
Middleware
Components
Operating Systems
User Interfaces
Groupware & Collaboration
Content Management
Productivity Applications
Hardware
Fun & Games

EarthWeb Direct EarthWeb Direct Fatbrain Auctions Support Source Answers

EarthWeb sites
Crossnodes
Datamation
Developer.com
DICE
EarthWeb.com
EarthWeb Direct
ERP Hub
Gamelan
GoCertify.com
HTMLGoodies
Intranet Journal
IT Knowledge
IT Library
JavaGoodies
JARS
JavaScripts.com
open source IT
RoadCoders
Y2K Info

Previous Table of Contents Next


5. IMPLEMENTATION AND APPLICATIONS

5.1. CONSTRAINTS EMBEDDED IN A HOST PROGRAMMING LANGUAGE

5.1.1. Control

A constraint programming language is the result of embedding constraints into a host programming language. The host program sends new constraints to the constraint handler, under program control. The information that can be returned to the host program depends on how tightly the constraints are embedded in the host language. Most basically, the constraint handler can report consistency or inconsistency. Given a closer embedding, it can also return variable bindings. Most closely it might allow the host programming language to be extended with guards and other annotations, so as to allow host program statements to be suspended and woken up like other constraint agents.

We can diagram the behavior of a constraint program as in Figure 6.

The diagram shows three successive phases occurring during program execution.


FIGURE 6 Control in constraint programming.

In the first phase, the host program is executing under explicit program control. The host program performs such tasks as input/output, event handling, and search. It may execute for some time before finally sending a constraint to the handler. The diagram illustrates the host program performing search over three branches. For the purposes of the diagram, it does not matter how these branches are explored (sequentially, or in parallel) and how they are expressed (by recursion over a set of alternatives, or by nondeterministic choice and backtracking). The succeeding phases of the execution are only shown for the second branch.

In the second phase, the constraint handler is executing, and its control is constraint-driven. The constraint handler only becomes active when it receives a new constraint from the host program. The behavior of the constraint handler (represented in Figure 6 as a network of thick lines) is defined by a set of atomic behaviors (each of which is represented by a single arc in the network). An atomic behavior is the posting of a new constraint to the store, or a single propagation step performed by a constraint agent, or the invocation of the body in a guarded constraint. When no more constraint propagation is possible, the constraint handler returns to the host program with success, and the host program resumes control, as illustrated in the third phase of Figure 6.

5.1.2. Concurrency

The challenge for embedding constraint handling in a host programming language is to deal with constraint agents acting concurrently. Assuming the programmer has little or no control over the waking and resuspending of constraint agents, the constraint programming framework must ensure that the final result of constraint propagation, before the host program resumes control, is independent of the order in which the agents wake up and post new basic constraints to the constraint store. The concurrent constraints framework (Saraswat, 1993) enables this condition to be met for large classes of practically useful constraint agents.

5.1.3. Logic Programming as a Host Language

Constraints fit hand in glove with declarative host programming languages. Three of the most influential constraint programming languages were embedded in Prolog, Prolog III, CLP([curly R]) and CHIP. While all three system are still developing further, there are many new constraint programming systems emerging, including ECLiPSe, Oz, 2LP, and Newton.

From a theoretical point of view, the extension of logic programming to Constraint Logic Programming (CLP) has been very fruitful. A good survey is given by Jaffar and Maher (1994). For example, ALPS -- a form of logic programming with guards -- was an extremely influential language, becoming the forerunner of the Concurrent Constraints paradigm (Saraswat, 1993). Concurrent constraint programming has in turn provided a very clean model of concurrent and multi-agent computing. Constraints can also be modeled in terms of information systems, which allow us to reason about the behavior of constraint programs at an abstract level.

5.1.4. Libraries for Embedded Constraint Programming

The constraint programming technology has matured to the point where it is possible to isolate some essential features and offer them as libraries or embedded cleanly in general-purpose host programming languages.

For example, isolating constraints as libraries has made possible the development of sophisticated constraint-based scheduling systems (see Zweben and Fox, 1994). More generally, there are commercially available libraries supporting constraint handling such as the CHIP and ILOG {C++} constraint libraries.


Previous Table of Contents Next

footer nav
Use of this site is subject certain Terms & Conditions.
Copyright (c) 1996-1999 EarthWeb, Inc.. All rights reserved. Reproduction in whole or in part in any form or medium without express written permission of EarthWeb is prohibited. Please read our privacy policy for details.