# Continuations

**URL:** <https://www.ruby-forum.com/t/continuations/100757>\
**Category:** Ruby\
**Created:** [November 23, 2005, 5:14pm UTC](https://www.ruby-forum.com/t/continuations/100757 "2005-11-23T17:14:47Z")\
**Posts on this page:** 5\
**Page:** 1

<div class="post-metadata">

**Author:** ![anders.janmyr](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/a/e47774/32.png) [@anders.janmyr](https://www.ruby-forum.com/u/anders.janmyr)\
**Post date:** [November 23, 2005, 5:14pm UTC](https://www.ruby-forum.com/t/continuations/100757/1 "2005-11-23T17:14:47Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![anders.janmyr](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/a/e47774/32.png) [@anders.janmyr](https://www.ruby-forum.com/u/anders.janmyr)\
**Post date:** [November 23, 2005, 5:55pm UTC](https://www.ruby-forum.com/t/continuations/100757/2 "2005-11-23T17:55:15Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![anders.janmyr](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/a/e47774/32.png) [@anders.janmyr](https://www.ruby-forum.com/u/anders.janmyr)\
**Post date:** [November 23, 2005, 7:11pm UTC](https://www.ruby-forum.com/t/continuations/100757/3 "2005-11-23T19:11:54Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![anders.janmyr](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/a/e47774/32.png) [@anders.janmyr](https://www.ruby-forum.com/u/anders.janmyr)\
**Post date:** [November 25, 2005, 6:32pm UTC](https://www.ruby-forum.com/t/continuations/100757/4 "2005-11-25T18:32:13Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![anders.janmyr](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/a/e47774/32.png) [@anders.janmyr](https://www.ruby-forum.com/u/anders.janmyr)\
**Post date:** [November 23, 2005, 9:13pm UTC](https://www.ruby-forum.com/t/continuations/100757/5 "2005-11-23T21:13:14Z")

</div>

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