Ask HN: Best resources on implementing constraint logic programming?

[LunaSea]

Hello HN,

I'like to implement my own little custom constraint logic programming language. Features like declarative integer arithmetic as implemented by Prolog's CLP(FD) module are especially interesting to me.

Would anyone advise books or other types of resources that would help implementing a project like this?

I've seen some resource about SAT solvers but couldn't find much on the actual implementation of a constraint logic programming language or library.

Anything regarding logical purity and SAT solvers if also appreciated.

Thanks in advance

[i_don_t_know]

SICP contains a chapter on non-deterministic programming that’s similar to how Prolog executes: https://mitp-content-server.mit.edu/books/content/sectbyfn/b...

There’s also a chapter on logic programming but it doesn’t quite work the same way as Prolog: https://mitp-content-server.mit.edu/books/content/sectbyfn/b...

Peter Norvig has a couple of chapters (11,12) on how to implement Prolog in his book PAIP. He also has a chapter (17) on constraint satisfaction but IIRC it’s not integrated into his Prolog system: https://github.com/norvig/paip-lisp

Many real Prolog implementations are based on the WAM. For an excellent introduction to the WAM look at: http://wambook.sourceforge.net/

I don’t have books or papers on implementing constraints and how to integrate them with Prolog. But here are two great classes on Coursera that explain how constraints and constraint propagation work. You can audit them for free:

Discrete Optimization by Hentenryck https://www.coursera.org/learn/discrete-optimization

Solving Algorithms for Discrete Optimization by Lee and Stuckey https://www.coursera.org/learn/solving-algorithms-discrete-o...

I believe constraints are typically integrated into Prolog through attributed variables: https://www.metalevel.at/prolog/attributedvariables

But I don’t really know how that works. Markus Triska has a few papers on constraint solvers for SWI Prolog on his webpage. He can probably give you more and better pointers: https://www.metalevel.at/

[LunaSea → i_don_t_know]

Many thanks for this very complete response!

It seems to be a niche topic so I didn't expect to find a resource that exactly matched.

[i_don_t_know → LunaSea]

I found a paper on compiling constraints for clp(fd) in the context of GNU Prolog: https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.30...

[bjourne]

Do you know about the backtracking algorithm? All constraint solvers use that algorithm (or an optimized variant of it) to find satisfying variable assignments. So if you don't know backtracking you should first learn about it to solve N-queens problems and Sudoku puzzles.