Joel VanderWerf said:

Stuff like this is so cool ...

A while back I wrote a Ruby version of the (amb) function fopund in

"Learning Scheme in Fixnum Days" (see http://tinyurl.com/pys4). It, too,

uses continuations to fallback to earlier choices.

Here is an example using the amb function (well, object in the Ruby

version). See the Scheme link above for a good description of amb.

# BEGIN AMB EXAMPLE -------------------------------------------------

require 'amb'

class MathSolver

attr_reader :x, :y, :z

# Initialize x, y and z to be chosen from the integers 1-5.

def initialize

amb = Amb.new

x = amb.choose(1,2,3,4,5)

y = amb.choose(1,2,3,4,5)

z = amb.choose(1,2,3,4,5)

end

# Assert that the sum of x, y and z is 9.

def solve

amb.assert(x+y+z == 9)

end

# Move on to the next solution. Throw an exception if

# there are no more solutions.

def next

amb.failure

end

end

begin

s = MathSolver.new

loop {

s.solve

puts "X=#{s.x}, Y=#{s.y}, Z=#{s.z}"

s.next

}

rescue Amb::ExhaustedError

puts "Done"

end

# END EXAMPLE ----------------------------------------------------

The output of the program is ...

$ ruby amb_example.rb

X=1, Y=3, Z=5

X=1, Y=4, Z=4

X=1, Y=5, Z=3

X=2, Y=2, Z=5

X=2, Y=3, Z=4

X=2, Y=4, Z=3

X=2, Y=5, Z=2

X=3, Y=1, Z=5

X=3, Y=2, Z=4

X=3, Y=3, Z=3

X=3, Y=4, Z=2

X=3, Y=5, Z=1

X=4, Y=1, Z=4

X=4, Y=2, Z=3

X=4, Y=3, Z=2

X=4, Y=4, Z=1

X=5, Y=1, Z=3

X=5, Y=2, Z=2

X=5, Y=3, Z=1

Done

I suppose I should post the code for Amb. Here it is ...

# BEGIN AMB CODE --------------------------------------------------

class Amb

class ExhaustedError < RuntimeError; end

def initialize

fail = proc { fail ExhaustedError, "amb tree exhausted" }

end

def choose(*choices)

prev_fail = fail

callcc { |sk|

choices.each { |choice|

callcc { |fk|

fail = proc {

fail = prev_fail

fk.call(:fail)

}

if choice.respond_to? :call

sk.call(choice.call)

else

sk.call(choice)

end

}

}

fail.call

}

end

def failure

choose

end

def assert(cond)

failure unless cond

end

end

# END CODE -----------------------------------------------------------

--

-- Jim Weirich org http://onestepback.org

-----------------------------------------------------------------

"Beware of bugs in the above code; I have only proved it correct,

not tried it." -- Donald Knuth (in a memo to Peter van Emde Boas)

## Bookmarks