[RubyJuice] Loops with continuations

Ruby continuations are a mistery for most of the rubists, including me. Personally I never had the chance to use them in production code, but I think that’s mainly because I never correctly understood how they work, plus for every scenario when continuations could be used I was able to find a more conventional solution.

Continuations were removed from the core library (probably due to lack of appreciation) so you need to require 'continuation' to use them in ruby > 1.8

What are continuations anyway?

Ruby documentation about continuations says:

«Continuations are somewhat analogous to a structured version of C’s setjmp/longjmp (although they contain more state, so you might consider them closer to threads).»

So if you already know some C you probably have a rough idea of what we’re talking about. If you don’t and you happen to have some knowledge of the BASIC programming language, then you can consider them like GOTO statements.

Today I’m going to show how to create loops with continuations, but you can use them for other purposes as well.

The Basics

During the early 80s everybody used to write endless loops like this:

10 PRINT "HELLO WORLD"
20 GOTO 10

The code above should be easy to understand for anybody, also for who had no previous experience with BASIC. So, how do we express the same behavior with ruby continuations?

continuation = callcc {|cc| cc }
p 'Hello world'
continuation.call(continuation)

Remember to save the code into a file, as continuation loops don’t work correctly inside irb.

What’s happening here? The first line creates a Continuation instance and stores it into the continuation variable. The second line is the body of the loop. The third line works like the good old GOTO statement, invoking the continuation; the program continues from the end of the callcc block.

The code inside the block of the callcc method is executed only once (I’m actually not doing much there in this example, but you can do). The block returns the continuation object.

Now, let’s write some code that prints integers up to a given number:

def integers_upto(n)
  i = 0
  continuation = callcc {|cc| cc }
  p i
  i += 1
  continuation.call(continuation) if i <= n
end

integers_upto 3
# 0 1 2 3

The code above can be slightly improved: we can avoid to explicitly set the variable i to its incremented value and let the continuation do it:

def integers_upto(n)
  continuation, i = callcc {|cc| [cc, 0]}
  p i
  continuation.call(continuation, i+1) if i <= n
end

Do you like it? I don’t really much. There are far too many ways to have the same behavior with simpler code, for example:

def integers_upto(n)
  0.upto(n) {|i| p i}
end

Fibonacci with continuations

Sometimes continuations allow to write some very coincise code, for example look at this Fibonacci numbers implementation:

def fibonacci(n)
  cc, fib, prev, i = callcc {|cc| [cc, 1, 0, 0]}
  p fib
  cc.call(cc, fib+prev, fib, i+1) if i < n
end

fibonacci 10

# 1 1 2 3 5 8 13 21 34 55 89

I like the fact that the code makesit  self-evident that we’re passing the sum of the current number (fib) and its previous (prev) as the new fibonacci number, just like is stated by the fibonacci definition.

I hope you had fun with continuations loops so far, and keep experimenting with them.

Leave a Reply

wpDiscuz