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