Professional Web Applications Themes

fallbacks using contiuations - Ruby

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

  1. #1

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

  2. #2

    Default Re: fallbacks using contiuations


    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)



    Jim Guest

  3. #3

    Default Re: fallbacks using contiuations

    On Fri, 30 Jan 2004 15:04:17 +0900, Jim Weirich wrote:
     
    >
    > Stuff like this is so cool ...[/ref]
    [snip] 
    [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.

    --
    Simon Strandgaard
    Simon Guest

  4. #4

    Default Re: fallbacks using contiuations

    "Jim Weirich" <org> wrote in message news:<umlcoop.net>...
     

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

  5. #5

    Default Re: fallbacks using contiuations

     [/ref]

    Avi Bryant said: 

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



    Jim Guest

Similar Threads

  1. Replies: 8
    Last Post: October 12th, 02:00 PM

Bookmarks

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139