Generators with Continuations

I ran into the Generator concept recently and saw that they could be implemented with continuations. Ruby supports continuations but I have never really understood them or found a use for them. There is a Prime number example in Python on the Generators wiki page so I thought I would take a crack at implementing it in Ruby.

I couldn't quite get my head around it so I first built a linear (non continuation) version. Here it is.

class Integer
  def prime?
    divisible_by.empty?
  end

  def divisible_by( include_one_and_self=false )
    range = include_one_and_self ? (1..self) : (2..self-1)
    range.select{ |x| self % x == 0 }
  end
end

class LinearPrime
  def initialize
    @last = 0
  end

  def next
    @last += 1
    @last += 1 while !@last.prime?
    @last
  end
end

>> p = LinearPrime.new
=> #
>> (0..10).collect{ p.next }
=> [1, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

Simple stuff, but how would it be done with continuations? Some googling got me to a chapter in the book 'The Ruby Way' which included a generator implementation from Jim Weirich. Here is the Prime number generator that I came up with based on Jim's generator class.

 
class Generator
  def initialize
    do_generation
  end

  def next
    callcc do |here|
      @main_context = here
      @generator_context.call
    end
  end

  private
  def do_generation
    callcc do |context|
      @generator_context = context;
      return
    end
    generating_loop
  end

  def generate(value)
    callcc do |context|
      @generator_context = context
      @main_context.call(value)
    end
  end
end

class ContinuationPrime < Generator 
  def generating_loop
    number = 1
    loop do 
      number += 1 while !number.prime?
      generate( number )
      number += 1
    end
  end
end

Much more complicated than the LinearExample, but it did finally get me to understand continuations. Here is the usage for ContinuationPrime.

>> p = ContinuationPrime.new
=> #ContinuationPrime:0x3376d8 @generator_context=#Continuation:0x33769c
>> (0..10).collect{ p.next }
=> [1, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

For those new to continuations, here is how it works.

1. Initializer calls do_generation which first creates a new continuation (callcc) and assigns it to @generator_context. It then exits the method because it hits a return from inside the block, bypassing the call to generating_loop.


2. Calling next on the new instance creates a new continuation and assigns it to @main_context, it then calls the @generator_context that was captured in the previous step.


3. The do_generation method continues after the block that created the @generator_context, invoking the generating_loop method (implemented in the ContinuationPrime subclass.


4. The generating_loop method only gets called once, it initializes the first prime number to 1 and then goes into a forever loop which increments the number until it is a prime number. When it has a prime it passes it to the generate method in the superclass.


5. The generate method creates a new continuation and assigns it to @generator_context and then resumes the @main_context that was created in the next method, passing to it the prime number that was generated.


6. The next method continues after the block that created the @main_context, but first the call to callcc returns with the value that was passed to in when the continuation was resumed. The call to callcc is the last execution of the next method so the return is also the return of next.

Subsequent calls to next take a slightly different path because the @generator_context is now a continuation from generate instead of do_generation.

Still confused?

There were two things that were tripping up my understanding that might be useful to reiterate. The first is regarding the exact point of continuation which seems obvious now but was confusing initially. To be clear, the entire block passed to to callcc is executed during the initial invocation and the continuation starts directly after the call to callcc.

The other thing that was confusing was the parameter passed to the call method on the continuation when invoking it. The parameter is the return value of the callcc when the continuation happens. This is party confusing because the return type is different depending on if it is returning initially or resuming from a continuation. On the initial call (to capture the continuation) the callcc method returns the last value of the block. On the continuation call callcc returns the value that was passed to the continuation's call method. The code below illustrates this difference.

>> def foo
>>  @v = callcc{ |c| c }
>>  puts "foo has #{ @v }"
>> end 
=> nil
>> foo 
foo has #Continuation:0x34bb10
=> nil
>> @v.call( "value on continuation" ) 
foo has value on continuation
=> nil

For this reason, I would suggest only assigning the continuation to a value within the callcc block and using the return value only for values that are valid to the resume of the continuation. For example.

>> def foo 
>>   value = callcc{ |c| @continuation = c; "initial value" } 
>>   puts "foo has #{ value }" 
>> end 
=> nil
>> foo 
foo has initial value
=> nil
>> @continuation.call( "resuming value" ) 
foo has resuming value