Constraints

Constraint Logic Programming (CLP): initially proposed by Jaffar and Lassez 87
CLP(X) is a generic logic programming language scheme which extends pure logic programming by adopting different constraints systems X.
The implementations of one instance of the CLP scheme can differ for the choice of the specific constraint solvers.
Current work on CLP:
- efficient implementation of new constraint solvers for established domains (as finite domains, boolean domain, equality and disequality on the Herbrand domain, real or rational numbers, etc.)
- definition of new domains.
Specially useful for search and combinatorial problems.
Constraints are independent of predicates and constraint domains includes functions => Constraints are good candidates to be integrated into functional logic languages.
Theoretical aspects of this integration has been studied by Darlington, Guo, Pull 91 and López-Fraguas 92.
Unique running language: Flang (finite domain constraints) - Mantsivoda 92, 93.

Expressivity of Constraints

Problem: Knapsack

Given a list of items with a fixed weight, try to pack a sublist of them into a knapsack with weight exactly a quantity W.

Try to solve it in your favourite language before you check the solution in a functional logic language

Uniform Model

CLP can also be seen as an uniform model to integrate functional and logic programming.
H/E: finest partition induced by an equality theory E over the Herbrand Universe H,
Domain: (H/E, =)
Functional rules in the equality theory E.
Predicates in the logic programming part.
Solving constraints means to detect the E-unification of two expressions.
Done by narrowing (with some restrictions).
M. Alpuente, M. Falaschi, G. Levi, F. Manzo, G. Vidal, etc.
In the previous example, we can consider the clauses for predicates knapsack and sublist as part of the logic program and the rule for the functions as the equality theory. The constraint (addweight M) = W is now solved with respect to the equality theory.

Disequality Constraints over the Herbrand Universe

Example of constraint domain: Herbrand Universe.
Equations t1 = t2 and Disequations t1 ~= t2 between terms.
Meaning of X = a:
1. result true and answer X = a,
2. false and answer the constraint X ~= a
Programs without disequalities are programs of this kind as answer substitutions can be regarded as sets of equality constraints X = t.
Gain in expressivity. For instance, the disequation X ~= Y cannot be replaced by any equivalent, finite set of equations.

Expressivity of Disequality Constraints over the Herbrand Universe

Problem: Size of a list

Computes the size of a list, understood as the number of different elements.

Try to solve it in your favourite language before you check the solution in a functional logic language

Constraints- Implementation -

Narrowing strategy

Studied in López-Fraguas 92.
Symbolic constraints: Kuchen, López-Fraguas, Moreno-Navarro, Rodríguez-Artalejo 92 (ad hoc, for the implementation) and Arenas, Gil, López-Fraguas 94 (fully formalized).

Translation to PROLOG

Symbolic Constraints: Arenas, Gil, López-Fraguas 94
PROLOG interpreter for CLP( H/E)

Abstract Machine Implementation Flang: Abstract machine with new techniques to handle finite domains, Mantsivoda 93 Innermost evaluation. Symbolic constraints: LBAM extension Kuchen, López-Fraguas, Moreno-Navarro, Rodríguez-Artalejo 92 Lazy evaluation

Go to index