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


2.1. DECLARATIVE MODELING AND EFFICIENT ENFORCEMENT

2.1.1. Algorithm = Logic + Control

Declarative programming has a long history yielding languages such as LISP, Prolog, and other purer functional and logic programming languages, and of course it underpinned the introduction of relational databases and produced SQL which, for all its faults, is today's most commercially successful declarative programming language.

There has been a recognition that declarative programming has problems with performance and scaleability. One consequence has been a swing back to traditional procedural programming. However, constraint programming, while recognizing that efficiency is an important issue, retains the underlying declarative approach. The idea is not to abandon declarative programming (that would amount to throwing away the baby with the bathwater), but to augment it with explicit facilities to control evaluation. Hence, Kowalski's maxim that Algorithm = Logic + Control.

When constraints are used in an application, both the issues of modeling and performance are considered. An early use of constraints was in the modeling of electrical circuits. Such circuits involve a variety of constraints -- from simple equations (the current at any two points in a sequential circuit is the same), to linear equations (when a circuit divides, the current flowing in is the sum of the currents flowing out), to quadratic equations (voltage equals current multiplied by resistance), and so on. A constraint solver that can handle all the constraints on a circuit would be prohibitively inefficient. Consequently, Sussmann sought to model circuits using only a simple class of constraints. He showed that the lack of expressive power of simple constraints can be compensated for by using multiple orthogonal models of the circuit. The different constraints of the different models interact to produce more information than could be extracted from the models independently.

2.1.2. Constraints for Multidirectional Programming

In many early constraint systems, constraints were little more than functions that were evaluated in a data-driven way. The logic programming paradigm, however, suggested that programs should be runnable "in both directions'.' In addition to evaluating a function f([bar X]) yielding the result Y, it must be possible to solve the equation f([bar X]) = Y for a given value Y but unknown arguments [bar X].

Naturally, when a function is evaluated "backwards'' -- i.e., from its result producing its input -- it is no longer a function! Attempts to integrate functional and logic programming motivated much research on equation-solving systems, and in the end spawned constraint logic programming.

It was recognized that constraint solving lies at the heart of logic programming, in its built-in unification. Researchers began to replace (syntactic) unification with other equation solvers. An important example of this was Boolean unification: this is a solver for equations between Boolean expressions, whose possible values are only true or false. This development has now found a commercially successful application for design and verification of digital circuits. Moreover, Boolean unification is also being applied to the design and verification of real-time control software.

2.1.3. Constraint Logic Programming

Soon an even more radical step was taken when it was recognized that unification could be replaced by any constraint system and solver, provided certain conditions were satisfied. There was no need for a unification algorithm (which reduces an equation between expressions to an equivalent set of variable assignments). Indeed, the constraints need not be equations at all.

The resulting scheme (Jaffar and Lassez, 1987) called the Constraint Logic Programming Scheme, and written CLP(X), was illustrated by choosing mathematical equations and inequations as the constraint system, and the Simplex algorithm as the solver. This instance of CLP(X) is called CLP([curly R]), and is described in a later section.

It has inspired a whole research area, exploring the interface between logic and mathematical programming. One resulting constraint programming language is 2LP (Linear Programming and Logic Programming), which embeds mixed integer programming in a constraint programming system. Another is Newton, which uses interval constraints to do solve hard mathematical problems involving polynomials.

While constraint logic programming offers a powerful modeling language, new constraint propagation algorithms and a clean execution model, mathematical programming offers some sophisticated algorithms, highly optimized implementations, and a wealth of industrial application know-how.

The next step beyond the standard constraint logic programming scheme was to include more than one constraint system and solver in a single system. Even CLP([curly R]) was, in fact, such a combination including syntactic unification, Gaussian elimination, and the Simplex. CLP systems nowadays include a variety of solvers that exchange information through shared variables. For numeric variables, in addition to the above solvers, there may also be a Groebner base rewriting system for handling polynomial equations, a very powerful CAD solver, and a weaker but very useful constraint handler for reasoning on numeric intervals. The latter three systems are typically useful for nonlinear constraints, containing expressions in which variables are multiplied together.

2.2. PROPAGATION

2.2.1. Early Applications

Constraint propagation was used in 1972 for scene labeling applications, and has produced a long line of local consistency algorithms, recently surveyed by Tsang (1993).

Constraint propagation offers a natural way for a system to spontaneously produce the consequences of a decision. (Propagation is defined in the dictionary as "dissemination, or diffusion of statements, beliefs, practices".) Propagation is the most important form of immediate feedback for a decision-maker.

Propagation works very effectively in interactive decision support tools. In many applications, constraint programming is used in conjunction with other software tools, taking their results as input, performing propagation, and outputting the consequences. Typically, feedback from the propagation tool is given in the form of a spreadsheet interface.

Many early applications of constraint programming were related to graphics: geometric layout, user interface toolkits, graphical simulations, and graphical editors. Constraint propagation has played a key role in all these applications, with the result that control over the propagation has been thoroughly investigated: leading to a current generation of very high-performance constraint-based graphics application.


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.