Non-deterministic Programming - Amb

I've been very slowly plowing through SICP and I've recently read through their chapter on non-deterministic programming. When you program this way your variables no longer have just one value, they can take on all of their possible values until stated otherwise. An example:

x = amb(1, 2, 3, 4)

In this case x is all of 1, 2, 3, and 4. If you try to print out x it will print out 1 because the act of printing it temporarily forces a value, but otherwise you can treat the variable as though it had all of those values.

You can then force certain subsets of the values with assertions:

assert x.odd?

In this case x would become just 1 and 3. If you then added a final assertion that x > 2 you would force a single value and x would be 3. If you instead added the assertion x > 3 then x would have no values: an exception would be thrown saying that x is basically "impossible".

This is useful when you are searching for something. Suppose you're trying to find numbers that satisfy Pythagorus' theorem:

a = amb(*1..10)
b = amb(*1..10)
c = amb(*1..10)

assert a**2 + b**2 == c**2

puts a, b, c
next_value
puts a, b, c

This code would print out 3, 4, and 5 on the first output, followed by 6, 8, and 10 on the second. The next_value function would tell the amb system to find another solution to the set of variables that satisfy the assertions we specified. If nothing else is found, an exception will be thrown.

Even more interesting, there is a library in Ruby called amb that implements this stuff. Unfortunately it doesn't work just like the above example, you can only get the either the first set of values that fit, or all of them:

require 'rubygems'
require 'amb'
include Amb::Operator

a = amb(*1..10)
b = amb(*1..10)
c = amb(*1..10)

# calling amb with no arguments causes it
# to backtrack until the criteria is met
amb unless a*a + b*b == c*c

# prints out the first match
puts "#{a}, #{b}, #{c}"

# prints out every match and then crashes
amb
puts "#{a}, #{b}, #{c}"

This is a pretty cool way to program, and it would be interesting to know when it might be practical to use. I tried it with a couple of problems on Project Euler but unfortunately since the backtracking method that amb uses isn't always the most efficient approach it would choke a bit. Perhaps if this gem gets some attention and some love, it might end up as something a bit more performant!