Just A Summary

If you run that, you’ll get:

A triangle with sides 3, 4 and 5 has a right angle

In English: we choose a number between 1 and 20. And then two more. Then we assert that the sum of the squares on two of the sides is equal to the square on the third and print the values. And we get the classic 3, 4, 5 Pythagorean triple. How did that happen? Where’s the loops?

One clue might be to add a line like: puts "#{a}:#{b}:#{h}" just before the amb.assert(...) line. You’ll see a whole pile of numbers spooling away until a, b and h reach the values 3, 4 and 5 respectively. It seems that, between them, Amb#one_of and Amb#assert are hiding a depth first search.

Welcome to the weird and wonderful world of continuations. Let’s take a look at a slightly simpler example and see if we can explain what’s going on.

<pre> amb = Amb.new x = amb.one_of(1..10)

Most of the magic happens in the implementation of one_of. Here’s a heavily commented version of it:

<pre> def one_of(collection)

1. callcc sets a ‘bookmark’ that we can return to later. See below
2. Essentially calling ‘k_entry’ resets the call stack to what it was when
3. callcc got called, and makes it look as though callcc just returned
4. that value.
   callcc do |k_entry|
5. loop through the collection
   collection.each do |item|
6. save our place in the loop. Taking the k_next continuation is akin to
7. simply doing ‘next’, but you can do it from anywhere…
   callcc do |k_next|
8. Push a new failure ‘continuation’ on the fail stack. If #fail gets called
9. this will restore the old failure continuation and resume the loop
   @failure_continuation = lambda do |v|
   @failure_continuation = k_prev
   k_next.call(v)
   end
10. Instead of carrying on with the loop, we return the current item through
11. the entry continuation. The loop will only get resumed if ‘fail’ gets called
    k_entry.call(item)
    end
12. <== k_next points here
    end
13. If we get here, the loop has come to an end, we’ve got no more values, so we’ll just
14. take the old failure continuation.
    result = k_prev.call(nil)
15. If we get here, that means k_prev didn’t take a continuation at all, which means we’ve
16. completely run out of possibilities. So, if the return value is the @error fence we set up
17. in initialise, we’ll throw an exception.
    if result == @error
    raise @error.message
    end
    end
18. <== k_prev points to here
end


Essentially, one_of iterates over the collection you pass it, but then freezes the iteration and ‘proposes’ the first value. Later on, an assertion (say amb.assert(x > 5)) might be false for the first value proposed. The assertion calls ‘fail’, which jumps back into @one_of@’s iteration, which proceeds to get the next value. one_of effectively says “Did I say 1? Sorry about that. I meant 2, obviously. No? 3 then? 4? 5? 6!” and the program continues on its merry way.

Admittedly, it’s not easy to understand how Amb¹ does its magic, but, frankly, most of the time that doesn’t matter. You can use it to set up some remarkably complex searches without having to worry about any of the backtracking book keeping yourself.

It helps to have some idea of what’s going on behind the scenes though, or you can end setting up a huge search space when a bit of thought in choosing your conditions etc could pay off big time. For instance, say you wanted to find all the Pythagorean triples whose hypotenuse is <= 100. A simple minded setup would look like:

<pre> amb = Amb.new triples = amb.all_values do a = amb.one_of(1..100) b = amb.one_of(1..100) h = amb.one_of(1..100)

And it would find all the pythagorean triples in that range. But it would consider some 1,000,000 cases, are [3,4,5] and [4,3,5] really distinct?

A bit of thought gives:

<pre> amb = Amb.new triples = amb.all_values do h = amb.one_of(1..100) a = amb.one_of(1..(h-1)) b = amb.one_of(([a, h-a+1].max)..(h-1))

Obviously, a can’t be longer than the hypotenuse, since the hypotenuse is, by definition the longest side of the triangle. The lower bound for @b@’s a little less obvious, but it derives from the fact that, in any triangle any side is shorter than the sum of the other two sides. However, b should also be larger than a, that way we avoid checking ‘mirror’ cases.

Now, instead of searching 1,000,000 cases, we search 76,625, which is a substantial improvement don’t you think?

I have to admit, finding Pythagorean triples isn’t the reason I ported Amb from Squeak to ruby (not that it took that long), I ported it because I wanted to use it to solve Sudokus. I’m not going to post the Sudoku implementation just yet; it’s in dire need of refactoring and clarification, but, following a first cut which would probably have kept on running ’til the heat death of the universe I have something which will do:

<pre> s = Sudoku.new(<<EOS) 34.....28 .....19.. ...64.... .....24.. 51.....97 ..61..... ....76... ..32..... 62.....39 EOS

and get output like:

<pre> Solving Sudoku: 3 4 . . . . . 2 8 . . . . . 1 9 . . . . . 6 4 . . . . . . . . . 2 4 . . 5 1 . . . . . 9 7 . . 6 1 . . . . . . . . . 7 6 . . . . . 3 2 . . . . . 6 2 . . . . . 3 9

within a sensible amount of time. It’s quite remarkable really; ruby’s not the fastest of languages, and its continuations are far from the fastest bit of the language.

The great thing about this approach is that, because Amb handles the bookkeeping, I can concentrate on reducing the search space.

¹ You will note, I’m sure that at no point do I explain what a continuation is. Mostly because, for the life of me, I can’t find the words – it’s all I can do to show you what they do.