Continuations

[Anders Janmyr]

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

 

[Edward Faulkner]

--HlL+5n6rz5pIUxbD
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
Content-Transfer-Encoding: quoted-printable

This does not work at all. I have tried many different usages but the =20
main problem seems to be that the local variable state is not =20
restored when the continuation is called. I thought that it was =20
supposed to do that.

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

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

--HlL+5n6rz5pIUxbD
Content-Type: application/pgp-signature; name="signature.asc"
Content-Description: Digital signature
Content-Disposition: inline

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.1 (GNU/Linux)

iD8DBQFDhJ3znhUz11p9MSARAv7nAKDB5W9K4CwGl5YQtbhyrttkDgk8/QCfY9mr
jMskHDgv7xmdeVvI1fUcUq0=
=9UwL
-----END PGP SIGNATURE-----

--HlL+5n6rz5pIUxbD--

 

[Edward Faulkner]

--UFHRwCdBEJvubb2X
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline

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)
catchthe_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 if board
}
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

--UFHRwCdBEJvubb2X
Content-Type: application/pgp-signature; name="signature.asc"
Content-Description: Digital signature
Content-Disposition: inline

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.1 (GNU/Linux)

iD8DBQFDhLBtnhUz11p9MSARAn8SAKCVO1T6GgBQ0km7zOfTqNLzVFJjBQCg0QaT
JKEdQoBOOqdaxwE2RMNU3gI=
=nCk5
-----END PGP SIGNATURE-----

--UFHRwCdBEJvubb2X--

 

[gabriele renzi]

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

 

[Edward Faulkner]

--CE+1k2dSO48ffgeK
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
Content-Transfer-Encoding: quoted-printable

Sorry, I don't understand what you mean here: IMHO this thing just works= =20
because of side effects in #failure and in the proc in #choose

=20
Right. I should be more clear. =20

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

regards,
Ed

--CE+1k2dSO48ffgeK
Content-Type: application/pgp-signature; name="signature.asc"
Content-Description: Digital signature
Content-Disposition: inline

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.1 (GNU/Linux)

iD8DBQFDh0oAnhUz11p9MSARAl4NAJ91CuMcqlpFllJQD8CE6D9Evke2KwCgi8SL
uV8feVnLMfXig5n8fbs7py0=
=k/38
-----END PGP SIGNATURE-----

--CE+1k2dSO48ffgeK--