There is a function called amb(). Think of it as choosing true or false ambiguously, and returning one of them – the only restriction on which it returns is the one that makes your program not fail.<p/> (Alternatively, think of passing amb() a list, and having it return one of them arbitrarily, and failing if none of the return values work. You can probably see how these are related – think of filtering the list based on amb().)<p/>

What’s this good for? Well, you can think about problems totally differently. If you want to solve an equation like x^2 - 7x + 10 = 0, you can call amb() to get you an integer between 0 and 10. Then plug it into the equation; if it comes out true, print it; if it fails, make your program fail.<p/>

Do you see how this is cool? You can describe the constraints for a solution and then simply read off that solution! You just have to make sure that amb() is searching the proper domain. You don’t need to be bothered about how the program actually goes about finding a solution, though, and I think that is really cool.<p/>

This is a really good example of declarative programming – saying ‘this is what I want in the end’ and then letting somebody else figure out how to get from here to there. I like to call it ‘supercoding’ because it sort of abstracts the actual programming away – you’re not writing loops, you’re writing constraints.<p/>

It is pretty intuitive to describe your solutions in this way, but it is not so easy to determine how long it will take to find a solution. If you are running on a quantum computer, the solution should just appear (‘cuz this is what quantum computers DO, as I understand them) – but if you’re on a regular machine, it will need to think a bit. In fact, each time you call amb, you are multiplying the number of possible execution paths by 2 (or however many choices you have), so most amb algorithms are exponential based on the number of times they call amb. And exponential algorithms are rarely the best way to do anything, so it’s not an amazing way to do anything. But it is cool to program.<p/>

One way I like to think about it sometimes is that you call amb() once, but it returns twice; when somebody fails they just die. Somebody implemented amb() in C using fork() to save the state of the function, let the guy return true and continue execution; have the parent waitpid until the guy exited, and if he failed, complain. That makes a lot of sense.