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


3.2. CLP([curly R])

The constraint logic programming scheme, written CLP(X), is a generic extension of logic programming to compute over any given constraint store. Logic programming over a constraint store has all the advantages of traditional logic programming, plus many further advantages for high-level modeling and efficient evaluation. If the constraint store holds primitive constraints from the class X, logic programming over this constraint store is termed CLP(X). In this section, we shall use a particular class of primitive constraints, linear equations, and inequations, termed [curly R], to illustrate the scheme. We shall use an example from Colmerauer (1990) to illustrate how it works.

Given the definition of a meal as consisting of an appetizer, a main meal, and a dessert, and given a database of foods and their calorific values, we wish to construct light meals, i.e., meals whose total calorific value does not exceed 10.

A CLP([curly R]) program for solving this problem is shown in Figure 1.

lightmeal(A,M,D) :-
  I>0, J>0, K>0,
  I+J+K <= 10,
  appetizer(A,I),
  main(M,J),
  dessert(D,K).

main(M,I) :-
  meat(M,I).
main(M,I) :-
  fish(M,I).
appetizer(radishes,1).
appetizer(pasta,6).

meat(beef,5).
meat(pork,7).

fish(sole,2).
fish(tuna,4).

dessert(fruit,2).
dessert(icecream,6).

FIGURE 1 The Lightmeal Program in CLP([curly R]).

A CLP([curly R]) program is syntactically a collection of clauses that are either rules or facts. Rules are as in logic programming, with the addition that they can include constraints, such as I + J + K [less than or equal to] 10, in their bodies.

The intermediate results of the execution of this program will be descibed as computation states. Each such state comprises two components, the constraint store, and the remaining goals to be solved. We shall represent such a state as Store @ Goals. CLP([curly R]) programs are executed by reducing the goals using the program clauses. Consider the query lightmeal(X,Y,Z), which asks for any way of putting together a light meal. The initial state has an empty constraint store and one goal: lightmeal(X,Y,Z).

This goal is reduced using the clause whose head matches the goal. The goal is then replaced by the body of the clause, adding any constraints to the constraint store3:


3Strictly, all variables in the clause are renamed, but we omit this detail for simplicity.
X=A,Y=M,Z=D, I+J+K =< 10, I>=0, J>=0, K>=0 @
appetiser(A,I), main(M,J), dessert(D,K)

The execution continues, choosing a matching clause for each goal and using it to reduce the goal. Variables that neither appear in the original goal, nor any of the currently remaining goals are projected out, as described above. A successful derivation is a sequence of such steps that reduces all the goals without ever meeting an inconsistency on adding constraints to the store. An example is:

X=radishes, Y=M, Z=D, 1+J+K=<10, J>=0, K>=0 @
main(M,J), dessert(D,K)


X=radishes, Y=M, Z=D, 1+J+K=<10, J>=0, K>=0 @
meat(M,J), dessert(D,K)

X=radishes, Y=beef, Z=D, 1+5+K=<10, K>=0 @
dessert(D,K)

X=radishes, Y=beef, Z=fruit @

Note that at the last step, the constraint 1 + 5 + 2 = <10 is added to the store, but it is immediately projected out.

Next we give an example of a failed derivation. The initial goal is the same as before, but this time pasta is chosen as an appetizer instead of radishes:

X=A,Y=M,Z=D, I+J+K =< 10, I>=0, J>=0, K>=0 @
appetiser(A,I), main(M,J), dessert(D,K)

X=pasta, Y=M, Z=D, 6+J+K=<10, J>=0, K>=0 @
main(M,J), dessert(D,K)

X=pasta, Y=M, Z=D, 6+J+K=<10, J>=0, K>=0 @
meat(M,J), dessert(D,K)

At the next step, whichever clause is used to reduce the goal meat(M,J), an inconsistent constraint is encountered. For example, choosing beef requires the constraint J = 5 to be added to the store, but this is inconsistent with the two constraints 6 + J + K [greater than or equal to] 10 and K [greater than or equal to] 0.

When the attempt to add a constraint to the store fails, due to inconsistency, a CLP(X) program abandons the current branch of the search tree and tries another choice. In sequential implementations, this is usually achieved by backtracking to some previous choice of clause to match with a goal. However, there are or-parallel implementations where several branches are explored at the same time, and a failing branch is simply given up, allowing the newly available processor to be assigned to another branch.


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.