Constraint logic programming: Difference between revisions

Revision as of 04:53, 18 December 2019

Revision as of 15:29, 28 April 2020

Line 115:

A second reformulation that can increase efficiency is to place constraints before literals in the body of clauses. Again, {{code|2=prolog|A(X):-B(X),X>0}} and {{code|2=prolog|A(X):-X>0,B(X)}} are in principle equivalent. However, the first may require more computation. For example, if the constraint store contains the constraint <code>X<-2</code>, the interpreter recursively evaluates <code>B(X)</code> in the first case; if it succeeds, it then finds out that the constraint store is inconsistent when adding <code>X>0</code>. In the second case, when evaluating that clause, the interpreter first adds <code>X>0</code> to the constraint store and then possibly evaluates <code>B(X)</code>. Since the constraint store after the addition of <code>X>0</code> turns out to be inconsistent, the recursive evaluation of <code>B(X)</code> is not performed at all.

A third reformulation that can increase efficiency is the addition of redundant constrainsconstraints. If the programmer knows (by whatever means) that the solution of a problem satisfies a specific constraint, they can include that constraint to cause inconsistency of the constraint store as soon as possible. For example, if it is known beforehand that the evaluation of <code>B(X)</code> will result in a positive value for <code>X</code>, the programmer may add <code>X>0</code> before any occurrence of <code>B(X)</code>. As an example, <code>A(X,Y):-B(X),C(X)</code> will fail on the goal <code>A(-2,Z)</code>, but this is only found out during the evaluation of the subgoal <code>B(X)</code>. On the other hand, if the above clause is replaced by {{code|2=prolog|A(X,Y):-X>0,A(X),B(X)}}, the interpreter backtracks as soon as the constraint <code>X>0</code> is added to the constraint store, which happens before the evaluation of <code>B(X)</code> even starts.

==Constraint handling rules==