Monday, December 1, 2014

Constraint Satisfaction Problems

This post is brain dump of my recent dives into CSP -- don't consider any of this to be anything but ramblings by someone who knows approximately nothing about what he's talking about.

To begin with, CSP is likely a programming paradigm very different from the ones you already heard of. If functional and object-oriented programming is what you think of when you hear programming paradigm then CSP is like a magic bottle of golden fairy dust in that it makes everything you heard and learnt about programming seem like monkey patching a steam engine. CSP is that different. On the other hand, if you have done some linear programminglogic programming, or implemented type inferencing, then you'll find yourself right at home.

A CSP program is an set (unordered collection) of constraints (assertions), example:
    X > 1
    Y > X
    X * Y = 21
That it, that's the entire program. To figure out what it does, all you need to do is recall some basic math, because CSP (when operating on integers like this) is essentially the same thing as solving mathematical equations numerically. This means that executing a CSP means to solve the asserted equations. This in turn means that implementing a CSP program means to figure out what equations that should hold on the solution (the answer of the program) and write down those equations. As in math, the ordered of the assertions is irrelevant, so you can organize your program in the way that seems local to you.

This is all nice and all, but how is a CSP executed? Well, this when it's get's complicated. Solving the equations/constraints that constitute the CSP is a hard problem, really hard problem. The reason for this might not be clear from the above example, but replace 21 with a much larger number (e.g., the product of two large prime numbers) and it should be clear why this is a hard problem.

So if it's so hard to execute a CSP why bother writing CSP programs? Well, not all programs are hard to execute and this is important to know. Some programs will take several life-times of the universe to execute while other programs will take a split second to execute. What make the difference is the size of the domain of the variables and the number of variables.

The domain of a variable is the set of it's possible values. In the program above, X has the domain {2, 3, 4, 5, 6, 7, 8, 9, 10, 11} and Y has the domain {3, 4, 5, 6, 7, 8, 9, 10, 11}. Now you might say "well, clearly X nor Y can be 11!", and you would of course be right! What you have done is something called constraint propagation, which is what makes CSP programs with many variables with large domains possible to execute before the universe is rebooted.

What do I mean with this? Let's take a step back and look at what's really given in the above program. The only thing we actually know by looking at the assertions one at the time is the following: the domain of X is {2, 3, 4, ...} and the domain of Y is {...}. That is the domains of X and Y are both infinitely large. How long time would it take to execute a program where the domains of any variable is infinitely large? Infinitely long, of course. This is bad.

What to do? Constraint propagation to the rescue! What this means is that we use our knowledge of how the constrains work (less than, multiplication, and equals, in this case) to infer more knowledge. For example, if Y > X and X > 1, then Y > 2. Pretty simple. Continuing further we have that X * Y = 21, what does this tell us? Well if we know that X and Y are greater than zero (which they are) then we can infer that X <= 21 and Y <= 21. Let's again take a step back and consider what we just have done -- we started with two infinite domains (that is, a program that would take infinitely long to execute) and through a few simple step we're down at two domains of size 19 and 18 respectively, which can be executed fast on any machine you can find (including that old Atari you keep in your storage room). Constraint propagation is that big of a deal.

Considering what we just did, you might ask what if there is no (good) propagator for a certain constraint? This is a very good question, and there is a lot of research going on (and have been going on for a long time) in finding good propagators for all kinds of constraints. Unfortunately, it's likely that there will always be CSP programs that execute slow (the life-time-of-the-universe kind of slow).

Luckily (in some sense) this is not something that is specific for CSP programs, but programs in general -- it just becomes obvious when doing CSP programming as the paradigm open doors that previously closed to you if you came from imperative/object-oriented or functional programming.

CSP is rich in research and diving into any part of it will lead you to diverse research areas. If that doesn't make you interested then what about the fact that GoogleMicrosoft, and many more is doing it and has identified it as one of the most important areas for the the future.

It's hard to make predictions especially about the future, but considering the amount of research that's is going on in this area and the fact that industry giants work on it as well, it's not too far fetched to imagine CSP to be a big part of programming in a decade or two. Or are everyone just doing it because it "fun and challenging"? No, I don't think so either.

(Don't worry, there will still be room for C/JavaScript programmers in 2034. It'll be hard to implement an operating system using CSP or the CSP solver itself...)

No comments: