fallbacks using contiuations

[Joel VanderWerf]

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):

# Yield to the associated block, if any. If the block raises an
# exception that matches +excep+, then resume execution at the
# previous successful fallback block.
#
def fallback(excep = StandardError)
cont = nil
callcc {|cont|}
result = block_given? ? yield : nil
$cont = cont # if it worked, remember what we did
result
rescue excep
$cont.call if $cont
raise
end

if __FILE__ == $0

first_time_C = true
first_time_E = true

puts "A"

fallback do
puts "B"
end

fallback do
puts "C"
if first_time_C
first_time_C = false
raise
end
end

fallback do
puts "D"
end

fallback do
puts "E"
if first_time_E
first_time_E = false
raise
end
end

fallback do
puts "F"
end

end

__END__

Output is:

A
B
C
B
C
D
E
D
E
F

 

[Jim Weirich]

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.callfail)
}
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 -----------------------------------------------------------

 

[Simon Strandgaard]

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 ... [snip]
I suppose I should post the code for Amb. Here it is ...

[snip]

Nice nicE!

I am working on a regexp engine which uses same kind of logic,
but without using continuations. Instead I use a stack for backtracking.

Amb is a nice implementation/inspiration for improvement.

 

[Avi Bryant]

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.

I posted an implementation of Amb back in November, but I don't think
many people saw it because the news->ML gateway was down at the time.
See
http://groups.google.com/[email protected]&output=gplain
..

Our code is almost identical (mine is also derived from LSFD), but
your implementation of choose() is a little bit smarter - it will take
either objects or procs, and has a variable number of args, whereas
mine takes an array of procs, and I have one_of() to take regular
values.

Anyway, neat to see this come up again. I think it's a very cool
idiom.

Cheers,
Avi

 

[Jim Weirich]

Avi Bryant said:

I posted an implementation of Amb back in November, but I don't think
many people saw it because the news->ML gateway was down at the time.

It seems that the amb function has been very popular lately. I just
stumbled on this implementation (http://bonk.nu/blog/archives/000106.html)
yesterday while looking for something else. It looks like Urban did his
version last June. It is interesting in that he made choose a method on
array.