Constraint logic programming
In practice, satisfiability of the constraint store may be checked using an incomplete algorithm, which does not always detect inconsistency.Since the constraint store is satisfiable and no other literal is left to prove, the interpreter stops with the solution X=1, Y=1.The semantics of constraint logic programs can be defined in terms of a virtual interpreter that maintains a pairA successful termination is generated when the current goal is empty and the constraint store is satisfiable.In practice, satisfiability is checked using methods that simplify the constraint store, that is, rewrite it into an equivalent but simpler-to-solve form.Formally, the semantics of constraint logic programming is defined in terms of derivations.They also choose the clause of the second rule according to the order in which they are written, and rewrite the constraint store when it is modified.The specific methods used in practice replace the constraint store with one that is simpler to solve.Such constraints are necessary because the interpreter adds t1=t2 to the goal whenever a literal P(...t1...) is replaced with the body of a clause fresh variant whose head is P(...t2...).When no function symbols are used, terms are expressions over reals, possibly including variables.If the domain of a variable is not specified, it is assumed to be the set of integers representable in the language.If the domain of a variable becomes empty, the constraint store is inconsistent, and the algorithm backtracks.A variable can take an arbitrary term as a value, if its domain has not been specified to be a set of integers or constants.The constraint store is unsatisfiable if a variable is bound to take both a value of the specific domain and a functor applied to terms.These operations are aimed at making the constraint store simpler to be checked for satisfiability and solved.The simplest case method is for the interpreter to save the complete state of the store every time it makes a choice (it chooses a clause to rewrite a goal).More efficient methods for allowing the constraint store to return to a previous state exist.This can be done by simply saving the old value of the constraints that have been modified; this method is called trailing.Whenever the interpreter evaluates such a literal, it performs a search over the domains of the variables of the list to find an assignment that satisfies all relevant constraints.The second use of the labeling literal is to actually determine an evaluation of the variables that satisfies the constraint store.A constraint satisfaction problem is typical solved by a constraint logic program having the following structure: When the interpreter evaluates the goal solve(args), it places the body of a fresh variant of the first clause in the current goal.The algorithm can be implemented using clauses for the choice of assigning a literal to true or false, and constraint handling rules to specify propagation.It is considered better than the top-down one when the aim is that of producing all consequences of a given program, rather than proving a single goal.For example, the bottom up evaluation of the following program requires two steps: The set of consequences is initially empty.At the first step, A(q) is the only clause whose body can be proved (because it is empty), and A(q) is therefore added to the current set of consequences.The advantage of the bottom-up evaluation over the top-down one is that cycles of derivations do not produce an infinite loop.This drawback can be overcome by checking for entailment facts that are to be added to the current set of consequences.This is the most evident effect of an intended directionality of the interpreter, which never revises a choice it has previously taken.Constraint logic programming has been applied to a number of fields, such as automated scheduling,[1] type inference,[2] civil engineering, mechanical engineering, digital circuit verification, air traffic control, finance, and others.[citation needed] Constraint logic programming was introduced by Jaffar and Lassez in 1987.