Joel VanderWerf said:
Here is an amusing little control structure that shows off ruby’s
continuations and is actually useful (of course, you might want to use
something other than a global variable–that’s just for simplicity):
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 -----------------------------------------------------------
···
“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)