Forum: Ruby Continuations

Announcement (2017-05-07): www.ruby-forum.com is now read-only since I unfortunately do not have the time to support and maintain the forum any more. Please see rubyonrails.org/community and ruby-lang.org/en/community for other Rails- und Ruby-related community platforms.
Ebdf8870ee58be2c7f1a5bb29e0ca8e8?d=identicon&s=25 anders.janmyr (Guest)
on 2005-11-23 17:14
(Received via mailing list)
Hello Everyone,
I am trying to come to terms with continuations and I am failing
miserably.

I have a method "traverse" which basically is a traversal algorithm
for a sudoko game.
To learn more about continuations I tried to write one that used
continuations instead: traverse_cc.
This does not work at all. I have tried many different usages but the
main problem seems to be that the local variable state is not
restored when the continuation is called. I thought that it was
supposed to do that.

Any help will be appreciated

Regards
Anders

   def traverse(debug)
     @solve_count += 1
     print "F" if debug
     return true if @available_positions.empty?
     position = @available_positions.pop
     position.reset
     position.possible_numbers.each do |num|
       position.place(num)
       return true if traverse(debug)
     end
     position.place(nil)
     @available_positions.push position
     print "B" if debug
     return false
   end



   def traverse_cc(debug)
     $c_stack = []
     available_positions = @available_positions.dup
     position = nil
     possible_numbers = nil
     until (available_positions.empty?)
       @solve_count += 1
       callcc do |cont|
         $c_stack.push cont
         print "F" if debug
         position = available_positions.pop
         position.reset
       end
       possible_numbers = position.possible_numbers

       if possible_numbers.empty?
         print "pop #{available_positions.size}:#
{possible_numbers.size}:#{$c_stack.size}\n"
         $c_stack.pop.call
       else
         num = possible_numbers.pop
         position.place(num)
       end

       print "#{available_positions.size}:#{possible_numbers.size}:#
{$c_stack.size}, "
     end
     return true
   end
036a1b88dafaab8ffd73a8b0a74b5b38?d=identicon&s=25 ef (Guest)
on 2005-11-23 17:55
(Received via mailing list)
On Thu, Nov 24, 2005 at 01:11:26AM +0900, Anders Janmyr wrote:
> This does not work at all. I have tried many different usages but the
> main problem seems to be that the local variable state is not
> restored when the continuation is called. I thought that it was
> supposed to do that.

Alas, that's not how continuations work in Ruby.  The call stack is
restored, but state is not.

Continuations are much simpler in purely functional code, where there
is no explicit state.  If you can rewrite your example to be purely
functional, it will behave the way you were expecting.

regards,
Ed
036a1b88dafaab8ffd73a8b0a74b5b38?d=identicon&s=25 ef (Guest)
on 2005-11-23 19:11
(Received via mailing list)
Here is a functional sodoku solver that uses continuations.  Note that
it works because all the functions called within the chooser are
purely functional -- they do not alter their arguments, and their
value does not depend on any saved state.


# Size of board
SIZE = 9
# Size of individual boxes
BOX = 3

input = """+-------+-------+-------+
| _ 6 _ | 1 _ 4 | _ 5 _ |
| _ _ 8 | 3 _ 5 | 6 _ _ |
| 2 _ _ | _ _ _ | _ _ 1 |
+-------+-------+-------+
| 8 _ _ | 4 _ 7 | _ _ 6 |
| _ _ 6 | _ _ _ | 3 _ _ |
| 7 _ _ | 9 _ 1 | _ _ 4 |
+-------+-------+-------+
| 5 _ _ | _ _ _ | _ _ 2 |
| _ _ 7 | 2 _ 6 | 9 _ _ |
| _ 4 _ | 5 _ 8 | _ 7 _ |
+-------+-------+-------+"""

# ---- Continuation-based Choooser -----------------
$paths = []

def choose(possibilities)
  catch(:the_choice){
    possibilities.each do |p|
      throw :the_choice, p  if callcc {|cc| $paths << cc;}
    end
    failure
  }
end

def failure
  raise "No solution" if $paths.empty?
  $paths.pop.call
end
# ----------------------------------------------------

# Returns board as a flat array
def parse(board)
  board.scan( /[1-9_]/ ).map {|x| x == '_' ? nil : x.to_i}
end

# all existing numbers on the same horizontal row as elt
def horiz(board, elt)
  board[ elt - elt%SIZE , SIZE ].select {|x| x}
end

# all existing numbers in same vertical column as elt
def vert(board, elt)
  result = []
  (elt % SIZE).step(SIZE*SIZE, SIZE) {|i|
    result << board[i] if board[i]
  }
  result
end

# all existing numbers in same box as elt
def box(board, elt)
  result = []
  start = (elt / SIZE / BOX * BOX) * SIZE + (elt % SIZE / BOX * BOX)
  BOX.times {|i| result += board[start + i*SIZE,BOX] }
  result.select {|x| x}
end

# numbers that can legally fill elt
def available(board, elt)
  (1..9).to_a - horiz(board,elt) - vert(board,elt) - box(board,elt)
end

# Recursive solution
def solve(board)
  elt = board.index(nil)
  return board unless elt
  newboard = board.dup
  newboard[elt] = choose(available(board,elt))
  solve(newboard)
end

def output(board)
  SIZE.times {|i|
    puts "#{board[i*SIZE,SIZE].join(' ')}\n"
  }
  :done
end

# Go!
output(solve(parse(input)))


regards,
Ed
32edd0717b3144d5c58a352d613abdc9?d=identicon&s=25 surrender_it (Guest)
on 2005-11-23 21:13
(Received via mailing list)
Edward Faulkner ha scritto:
> Here is a functional sodoku solver that uses continuations.  Note that
> it works because all the functions called within the chooser are
> purely functional -- they do not alter their arguments, and their
> value does not depend on any saved state.

Sorry, I don't understand what you mean here: IMHO this thing just works
because of side effects in #failure and in the proc in #choose
036a1b88dafaab8ffd73a8b0a74b5b38?d=identicon&s=25 ef (Guest)
on 2005-11-25 18:32
(Received via mailing list)
On Thu, Nov 24, 2005 at 05:12:25AM +0900, gabriele renzi wrote:
> Sorry, I don't understand what you mean here: IMHO this thing just works
> because of side effects in #failure and in the proc in #choose

Right.  I should be more clear.

The useful abstraction here is that once you've written #choose and
#failure, you can use them without knowing how they work, as long as
the rest of your program is purely functional.

The whole thing works because you allow #choose and #failure to manage
all state for you.

regards,
Ed
This topic is locked and can not be replied to.