Continuations

Ruby
1

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

2

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

3

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

4

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

5

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