Constraint logic programming: Difference between revisions

Revision as of 17:22, 14 March 2006

Revision as of 12:14, 15 March 2006

Line 1:

'''Constraint logic programming''' is a variantform of [[constraint programming]], in which [[logic programming]] includingis extended to include concepts from [[constraint satisfaction]]. A constraint logic program is a logic program that contains constraints in the body of clauses. An example of a clause including a constraint is <code>A(X,Y) :- X+Y>0, B(X), C(Y)</code>. In this clause, <code>X+Y>0</code> is a constraint; <code>A(X,Y)</code>, <code>B(X)</code>, and <code>C(Y)</code> are literals like in regular logic programming. Intuitively, this clause tells one condition under which the statement <code>A(X,Y)</code> holds: this is the case if <code>X+Y</code> is greater than zero and both <code>B(X)</code> and <code>C(Y)</code> are true.

Like in regular logic programming, programs are queried about the provability of a goal. A proof for a goal is composed of clauses whose constraints are satisfied and whose literals can in turn be proved using other clauses. Execution is done by an interpreter, which starts from the goal and [[Recursion|recursively]] scans the clauses trying to prove the goal. Constraints encountered during this scan are placed in a set called '''constraint store'''. If this set is found out to be unsatisfiable, the interpreter [[Backtracking|backtracks]], trying to use other clauses for proving the goal. In practice, satisfiability of the constraint store may be checked using an incomplete algorithm, which does not always detect inconsistency.