Extending an Imperative Language with Constraint Logic Programming

Help!
,
#1

Could someone enlighten me on the merits and/or drawbacks on using logic programming concepts to extend imperative languages via either Constraint Handling Rules (CHR), Mini-Kanren, or programming a Picat implementation in the language?

From a brief study, it appears CHR is designed for embedding into other languages, including imperative ones.

For example, C and Java are listed here:
https://about.chrjs.net/about-chr/systems/

Mini-Kanren is the foundation of logic programming in Clojure and some libraries exist for Common Lisp.

Picat seems to be a totally separate, multi-paradigm language that encourages declarative programming. I had thought there were multiple implementations of it, but I cannot find them at the moment.

It would seem that, in terms of implementation, Picat would be the most difficult. I don’t have any good intuition on how hard it would be to implement mini-Kanren vs CHR. Both seem less difficult than Picat, but mini-Kanren seems like it would offer a bit more in terms of benefits (probabilistic programming, tabling, etc.)

#2

In an imperative context, CHR is probably best viewed as a self-contained library. In that context, you post your rules to CHR, post your constraint declarations, and then post your query. And the result is a bunch of objects you can examine and interpret. The nice thing about imperative is you can easily just add more data to CHR and get the results.

One thing CHR is not as great at, is reversing course. If you add a(3), a(4) and a(5) and it goes and computes a bunch of stuff, some implementation might let you remove a(4), but everything it computed from a(4) will remain as-was. Prolog is flexible this way because the backtracking can restore the state before you added a(4) and move forward again without.

But on the other hand, in an imperative language you could just restart the query from the beginning with a different initial condition.

2 Likes
#3

Blockquote
In an imperative context, CHR is probably best viewed as a self-contained library. In that context, you post your rules to CHR, post your constraint declarations, and then post your query.

This was my initial intuition about the problem. After reading a few more papers about CHR, as well as some case studies extending imperative programming languages with constraints, CHR seems like the right solution.

This one was the most encouraging:
Jon Sneyers, Tom Schrijvers, and Bart Demoen. (2009). The computational power and complexity of constraint handling rules. ACM Trans. Program. Lang. Syst. 31, 2, Article 8 (February 2009), 42 pages. DOI:https://doi.org/10.1145/1462166.1462169

From the abstract:

Blockquote
Constraint Handling Rules (CHR) is a high-level rule-based programming language which is increasingly used for general-purpose programming. We introduce the CHR machine, a model of computation based on the operational semantics of CHR. Its computational power and time complexity properties are compared to those of the well-understood Turing machine and Random Access Memory machine. This allows us to prove the interesting result that every algorithm can be implemented in CHR with the best known time and space complexity.

1 Like
#4

For those looking to download the paper “The computational power and complexity of constraint handling rules” (PDF). Also added it to the list of papers in the wiki.

2 Likes