Fallbacks using contiuations

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

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

···


– Jim Weirich jim@weirichhouse.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)

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.

···

On Fri, 30 Jan 2004 15:04:17 +0900, Jim Weirich wrote:


Simon Strandgaard

“Jim Weirich” jim@weirichhouse.org wrote in message news:33737.216.23.36.251.1075442652.squirrel@jimweirich.umlcoop.net

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/groups?selm=6e869a6b.0311051951.30b77ee0%40posting.google.com&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” jim@weirichhouse.org wrote in message
news:33737.216.23.36.251.1075442652.squirrel@jimweirich.umlcoop.net

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.

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.

···


– Jim Weirich jim@weirichhouse.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)

key = "file"
attrib = "\Applications\4Dapp\Chess\"
command = "xcopy [file] /y /s /e i:\source\"
command.gsub!( /[#{key}]/ , “#{attrib}” )
puts command
=> “xcopy \ApplicationsDapp\Chess\ /y /s /e i:\source\”

It should be:

=> “xcopy \Applications\4Dapp\Chess\ /y /s /e i:\source\”

Any idea why it keeps stealing my \4?

Zach

Zach Dennis wrote:

key = “file”
attrib = “\Applications\4Dapp\Chess\”
command = “xcopy [file] /y /s /e i:\source\”
command.gsub!( /[#{key}]/ , “#{attrib}” )
puts command
=> “xcopy \ApplicationsDapp\Chess\ /y /s /e i:\source\”

It should be:

=> “xcopy \Applications\4Dapp\Chess\ /y /s /e i:\source\”

Any idea why it keeps stealing my \4?

It recognizes \4 as meaning the fourth submatch of the
last regex, or something to that effect.

Double escaping or something should fix it.

Hal

-----“Zach Dennis” wrote:-----

command.gsub!( /[#{key}]/ , “#{attrib}” )

replace this line with:
command.gsub!( /[#{key}]/ , “#{Regexp::quote(attrib)}” )

Any idea why it keeps stealing my \4?

Because in gsub terms \4 represents the forth grouping:

“123412341234”.gsub(/(.)(.)(.)(.)/, ‘\4’)
=> “444”

You don’t have any groupings in your expression so ‘\4’ is equivalent to ‘’.

···


John

As others have said, ‘\4’ in a gsub string is special. To get around
this you need yet another backslash in front of it, which of course
means two more backslashes between the double quotes:

    attrib = "\\Applications\\\\4Dapp\\Chess\\"

You can safely double all backslashes in gsub strings, so you might just
want to make it special-processing-proof automatically with some
preparatory munging of your own:

    attrib = "\\Applications\\4Dapp\\Chess\\".gsub(/\\/, '\\\\\\')

Just as a side note, if you’re going to be making literal strings with
backslashes, single quotes cut down on the number of doublings required:

    attrib = '\Applications\4Dapp\Chess\\'.gsub(/\\/, '\\\\\\')

-Mark

···

On Sat, Jan 31, 2004 at 01:07:42PM +0900, Zach Dennis wrote:

key = “file”
attrib = “\Applications\4Dapp\Chess\”
command = “xcopy [file] /y /s /e i:\source\”
command.gsub!( /[#{key}]/ , “#{attrib}” )
puts command
=> “xcopy \ApplicationsDapp\Chess\ /y /s /e i:\source\”

Thank you much Hal! It’s working now.

Zach

In article 20040131052700.GA5270@mulan.thereeds.org,

key = “file”
attrib = “\Applications\4Dapp\Chess\”
command = “xcopy [file] /y /s /e i:\source\”
command.gsub!( /[#{key}]/ , “#{attrib}” )
puts command
=> “xcopy \ApplicationsDapp\Chess\ /y /s /e i:\source\”

As others have said, ‘\4’ in a gsub string is special. To get around
this you need yet another backslash in front of it, which of course
means two more backslashes between the double quotes:

   attrib = "\\Applications\\\\4Dapp\\Chess\\"

You can safely double all backslashes in gsub strings, so you might just
want to make it special-processing-proof automatically with some
preparatory munging of your own:

   attrib = "\\Applications\\4Dapp\\Chess\\".gsub(/\\/, '\\\\\\')

Just as a side note, if you’re going to be making literal strings with
backslashes, single quotes cut down on the number of doublings required:

   attrib = '\Applications\4Dapp\Chess\\'.gsub(/\\/, '\\\\\\')

also if your replacement includes \ then you might consider using the
block form of gsub or gsub! to do the replacement as it doesn’t parse
the replacement string for you (but does have some overhead):

[mike@ratdog mike]$ irb

key = “file”
=> “file”
attrib = “\Applications\4Dapp\Chess\”
=> “\Applications\4Dapp\Chess\”
command = “xcopy [file] /y /s /e i:\source\”
=> “xcopy [file] /y /s /e i:\source\”
command.gsub!(/[#{key}]/) { attrib }
=> “xcopy \Applications\4Dapp\Chess\ /y /s /e i:\source\”
puts command
xcopy \Applications\4Dapp\Chess\ /y /s /e i:\source
=> nil

Hope this helps,

Mike

···

Mark J. Reed markjreed@mail.com wrote:

On Sat, Jan 31, 2004 at 01:07:42PM +0900, Zach Dennis wrote:


mike@stok.co.uk | The “`Stok’ disclaimers” apply.
http://www.stok.co.uk/~mike/ | GPG PGP Key 1024D/059913DA
mike@exegenix.com | Fingerprint 0570 71CD 6790 7C28 3D60
http://www.exegenix.com/ | 75D2 9EC4 C1C0 0599 13DA