Hacker News new | past | comments | ask | show | jobs | submit login
Constraints (1981) [pdf] (dspace.mit.edu)
23 points by tosh 40 days ago | hide | past | favorite | 7 comments



Constraints blend in especially seamlessly with logic programming languages like Prolog. In fact, Prolog itself can be regarded as a constraint solver over Herbrand terms.

For instance, here is the "adder" example from the paper, using Scryer Prolog and its built-in constraint solver over integers:

    $ scryer-prolog
    ?- use_module(library(clpz)).
       true.
    ?- A1 + A2 #= Sum.
       clpz:(A1+A2#=Sum).
    ?- A1 + A2 #= 5.
       clpz:(A1+A2#=5).
    ?- -2 + A2 #= 5.
       A2 = 7.
In this interaction, we state what we know about the relation, and the answer tells us what the system has deduced. For example, given the sum and A1, the system has deduced that A2 is 7.

The speed and sophistication of built-in constraint solvers over various domains is often an important reason for buying a commercial Prolog system.


Real interesting.

My first thought, given how old the paper is, is what kind of further research and applications did this lead to?

Or was it a dead-end?


Constraint programming is a thriving area of research that is used a lot in practice for solving various kinds of combinatorial optimization problems. It’s similar in use cases to mathematical programming (such as linear programming and mixed integer programming) and SAT/SMT solving, and each technique has their own pros and cons.

The easiest way to test CP out is probably using the modelling language MiniZinc. It is from the CP tradition in how models are expressed, but can compile down to many different types of solvers.

While there are programming languages that integrate CP, the main way it is implemented and used is through libraries such as Gecode, Google Or-tools, and IBM CP Optimizer.


I think the approach eventually petered-out or was incorporated entirely into other approaches.

But I have on my bookshelf Principles And Practice of Constraint Programming, edited by Saraswat and Van Hentenryck (1995) and wikipedia has an entry for the approach [1]. So the paradigm was up-and-coming for a time. A lot of ideas can rise and fall over forty years. Broadly, it was more or less part of logic programming, which was part of the symbolic/GOFAI (good old fashioned AI) paradigm, which naturally has been waning for many years.

[1] https://en.wikipedia.org/wiki/Constraint_programming


The geometry tools in GeoGebra [1] seem an obvious application of the paradigm, but I'm not aware of any programming languages based on it.

[1] https://www.geogebra.org


miniZinc is a constraint modeling language.

Many Prologs support constraint modeling. Common Lisp has the Screamer package which is built on the idea. minikanren provides constraint modeling in many languages.


I used to love that IBM Selectric Letter Gothic Font-ball.




Applications are open for YC Winter 2022

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: