CONSTRAINT ORIENTED PROGRAMMING

"A world without constraints would be totally chaotic". "That something is predictable implies that a constraint exists." "Every law of nature is a constraint" (William Ross Ashby).

"Laws describe constraints; they do not create." "The universe is based on freedom. Laws, restrictions on freedom, are secondary" (Arthur M. Young).

---

Constraint Oriented System
In a constraint-oriented system, the user defines (by means of a specific language) the solution space of a problem, supplies the constraints that exist and specifies the type of solution sought. The system, automatically, by means of a search engine, tries to find the solution.

In theory, such a system approaches the ideal of automatic programming, since it uses purely declarative programming and frees the programmer from having to develop a search algorithm for each problem. But there are difficulties in practice:

• There is no universal constraint-oriented system (general problem solver). It is usual to limit oneself to a specific domain.
  
  
• Many problems cannot be specified in the form of constraints alone. Additional programming paradigms are usually required.
  
  
• The specification of such a system requires a thorough analysis to clearly define the solution space, the constraints and the solution to be sought.
  
  
• It may happen that the resources required (time and memory) to find the solutions are disproportionate, if search engines perform exhaustive searches.

But the constraint paradigm also provides advantages:

• If no system is available to implement constraints, analyzing the problem with this philosophy helps in its specification and programming.
  
  
• If a system for implementing constraints is available, it can be a good tool for prototyping.

Specification in MENTAL
With MENTAL no particular language is needed to specify a Constraint Oriented System. The language's own resources are sufficient.

A typical problem of Constraint-Oriented Programming consists of finding the values of a series of unknown variables that must satisfy a series of conditions (constraints) that must be satisfied at the same time. In the case that the conditional expression is very extensive, representations (potential substitutions) can be used to improve comprehension.


Example

A classic example is the "8 queens problem". Proposed by the chess player Max Bezzel in 1848, it involves finding a position on the chessboard with the following restrictions: 1) there are only 8 queens on the board, and 2) no queen can attack another queen.


There are 92 possible solutions, of which 12 are essentially distinct, since the rest are obtained by symmetries, rotations and translations.

This problem (which is NP-Complete) interested mathematicians like Gauss and Cantor, who generalized it to n queens on a board of n×n squares.

Numbering the rows from bottom-up, and the columns from left to right, and representing the positions of the queens by the sequence (i1 … i8), where ij is the column occupied by the queen of row j, the solution expression, together with the constraints, is as follows:

s = {⟨([i[1…8]]) ← ij≠ik ← j ≠k ← (abs(ij−ik) ≠ abs(j−k)) ← j≥1 ← j≤8 ← k≥1 ← k≤8 ⟩}

One solution (the one indicated in the image) is: (2 4 5 8 3 1 7 5).

• The condition ij≠ik ← j≠k is the non-membership of the same row.
  
  
• The condition abs(ij−ik) ≠ abs(j−k) is the non-membership of the same diagonal. When two queens are on the same diagonal, the difference (in absolute value) between their respective rows is equal to the difference (in absolute value) between their respective columns.
  
  
• abs is the absolute value of an integer:
  
  ⟨( abs(m) = (−m ← m<0 →' m) )⟩ // m indicates integer number

Its generalization for n queens is:

⟨( s(n) = {⟨([i⌊1…n⌋]) ← ij≠ik ← j≠k ← (abs(ij−ik) ≠ abs(j−k)) ← j≥1 ← j≤n ← k≥1 ← k≤n ⟩} )⟩

This problem has no solution for n=2 and n=3.

For n=4 has only one solution: (2 4 1 3).


To improve understanding, we can use auxiliary expressions. For example:

( CondCol =: (ij≠ik ← j≠k) ) // condition of different column

( CondDiag =: (abs(ij−ik) ≠ abs(j−k)) ) // different diagonal condition

( CondGen =: (j≥1 ← j≤n ← k≥1 ← k≤n) ) // general condition

And the general expression would be:

⟨( s(n) = {⟨([i⌊1…n⌋]) ← CondCol ← CondDiag ← CondGen⟩} )⟩

---

Addenda
A little history

• The pioneer of Constraint Oriented Programming was Ivan Sutherland [1963], who in his thesis described Sketchpad, a system oriented to the generation and edition of geometric figures. His ideas were advanced for his time and required hardware and software that was not then available.
  
  
• Constraint Oriented Programming began with logic programming, including constraints within a logic program. That is why it was called Constraint Logic Programming, CLP). It was Jaffar and Lassez who first used it in Prolog II applications. The first CLP implementations were Prolog III, CLP(R) and CHIP. Today, most Prolog implementations include one or more libraries for CLP.
  
  
• OPS5 and ThingLab are general purpose systems of the "condition → action" type, with which constraint-oriented applications can be implemented.
  
  
• IDEAL is another system that uses auto−constraints for drawing geometric figures. It incorporates an equation solver.

Bibliography

• Bal, Henri E. y Grune, Dick. Constraint Programming. Apartado 7.1.1 de Programming Language Essentials. Addison−Wesley, 1994.
  
  
• Krzyztof, R. Principles of Constraint Programming. Cambridge University Press, 2003.
  
  
• Leler, W. Constraint Programming Languages – Their Specification and Generation. Addison−Wesley, 1988.
  
  
• Sutherland, Ivan. Sketchpad: A Man−machine Graphical Communication System. Garland Publications, 1963, 1980.