For the Zigtoberfest 2024 I gave a talk about interesting properties of constraint programs. This page provides a small summary of the talk.

Not in a reading mood? Let me do the talking over on YouTube:

Intro

Constraint programming, unlike imperative programming, focuses on defining the desired properties of a result rather than specifying a sequence of steps. While there exist languages that have this paradigm built-in (e.g., Oz or Kaleidoscope), it is more common for constraints to be an extension or library for a programming language. For this talk, we are going to look at constraint programs through CHR.

CHR (Constraint Handling Rules) is a rule-based language and formalism that is used through an embedding into a host language. This makes it interesting to see how CHR's declarative nature can be used in languages with a possibly completely different paradigm. Besides that, it also brings cool properties that CHR programs can have to said other languages. Those properties will be what we are looking closer at in this little write-up.

To start off, let's look at a simple example of a CHR program. This and all other examples can be used with Prolog's CHR embedding.

min(N) \ min(M) <=> N <= M | true.

This example will compute the minimum of an arbitrary number of values. We can read it like this: If there are two candidates for the minimum, min(N) and min(M), then the minimum is the smaller one of the two and the bigger one will be removed. What's cool about this notation is that it's extremely concise and easy to read. Just by looking at it, we can instantly tell what it does.

CHR Basics

Rule Structure

A Rule always consists of three parts: The head, the guard, and the body. HEAD <op> GUARD | BODY.

Rule Types

CHR knows about three different types of rules:

1. Propagation C ==> G | B: If the guard G holds, then constraints from the body B will be added.
2. Simplification C <=> G | B: If the guard G holds, then the constraint C will be removed and constraints from the body B will be added.
3. Simpagation C1 \ C2 <=> G | B: If the guard G holds, then the constraint C2 will be removed and constraints from the body B will be added.

You might have already noticed that a simpagation can express both a simplification and a propagation. Therefore, the Zig embedding I wrote only uses simpagations (or 4-tuples) under the hood.

Properties

Anytime Algorithms

We start with a simple property that every CHR algorithm has: It is an anytime algorithm. This means that the algorithm can be stopped at any point in time and the state at this time will be a valid approximation of the final result.

Let's say we have the following query: min(4), min(2), min(1). When we interrupt the computation after the first two constraints were handles, we will get min(2) as the result. While that's not a correct final answer, it's at least more valid than the initial min(4).

This property is especially useful if we need to guarantee a certain response time for our algorithm. Let's say it has to produce a result in under 100ms. Due to it being anytime, we can just stop the computation after 100ms, observe the current state, and return it as an approximation.

Memoization

Every computer scientist has probably written the fibonacci function at least once in their life. In CHR we can formulate it as follows:

fib(0, R) <=> R = 1 | true.
fib(1, R) <=> R = 1 | true.
fib(N, R) <=> N > 1 |
        N1 = N - 1, N2 = N - 2,
        fib(N1, R1), fib(N2, R2),
        R = R1 + R2.

While this works totally fine, it's also painfully slow — especially for bigger values of N. The reason for this is that we are computing the same values over and over again. If we could just remember and reuse the intermediate results, we could speed this up to linear time complexity.

Achieving this is criminally easy in CHR. We just need to change our simplification rules to propagations and add a little cleanup rule:

fib(N,M1) \ fib(N,M2) <=> M1=M2.

fib(0, R) ==> R = 1 | true.
fib(1, R) ==> R = 1 | true.
fib(N, R) ==> N > 1 |
        N1 = N - 1,  N2 = N - 2,
        fib(N1, R1), fib(N2, R2),
        R = R1 + R2.

This way, we don't throw away intermediate fib(N,M) constraints but keep them. If we later need to compute, e.g., fib(5, R) it might be already present with a result bound to R.

Confluence

The next property we will look at is confluence. Not every CHR program is necessarily confluent, but it's a very desirable property to have, since it will give us other handy properties for free. A program is confluent if it will always produce the same result for a given input, regardless of the order in which the rules are applied or in which order the query is given. Therefore, the relation of the initial and final state is a function.

a ==> b.
a ==> false.

The above code snippet is not confluent. Given a, depending on which rule we check first, we will get different final states. Namely b and false.

But on the upside, we (or the completion algorithm) can make this program confluent by adding a single rule:

a ==> b.
a ==> false.

b ==> false.

But note that not every program can be made confluent.

Incremenrality

Given that our algorithm is confluent, its also incremental or online. But what does that mean? In an online algorithm, we can add new constraints to the system at any time and they will eventually participate in the computation and contribute to the final state. This is very powerful, especially in e.g. feedback loops where we need to react to new input constantly.

Declarative Concurrency

Writing correct concurrent programs is typically hard. But with a confluent CHR program not so much. Actually, we don't have to do anything at all. We can just take a hand full of constraints, put it on one machine, put the other ones on another machine, evaluate both sets in parallel, bring them back together, and we will have a correct result that equals the one we would have gotten if we would have evaluated everything on a single machine.

If you wanna try it out, here's a simple implementation of the map-reduce pattern.

map(OP) \ v(X) <=>
    C =.. [OP, X, R],
    call(C),
    r(R)

reduce(OP) \ r(X), r(Y) <=>
    C =.. [OP, X, Y, R],
    call(C),
    r(R)

Destructive Assignment

By the way, we can also use confluence to show why it's often hard to write a correct concurrent algorithm in imperative languages. Take a look at the following rule:

assign(K, V), cell(K, V') <=> cell(K, V).

This simple rules models destructive assignments, the backbone of imperative programming. Now given a query like cell(a,1), assign(a,2), assign(a,3) we first set a to 2 and following that to 3. But for confluence we need the query order to be independent of the result. But swapping the two assign constraints will yield a different result. Thus destructive assignments are not confluent and by proxy not trivially concurrent.