This post originated from an RSS feed registered with Ruby Buzz by Jim Weirich. Original Post: Kata Two Worked (continued) -- Call/CC Feed Title: { | one, step, back | } Feed URL: http://onestepback.org/index.cgi/synopsis.rss Feed Description: Jim Weirich's Blog on Software Development, Ruby, and whatever else sparks his interest. Latest Ruby Buzz Posts Latest Ruby Buzz Posts by Jim Weirich Latest Posts From { | one, step, back | }

Recap

Pragmatic Dave is up to Kata number twelve, and I’m still writing about KataTwo. I have a feeling that I’m not going to catch up any time soon.

If you recall from earlier Kata writeups (see KataTwoCps and KataTwoNoTail for details), a continuation is merely the bit of code that needs to be executed after a method returns. We can manually capture continuations as Proc objects and explicitly pass them around.

A simple example is appropriate at this point. In the following factorial function, the result of the fact(n-1) call must be multiplied by n before returning a result. That multiplication is the continuation of the fact(n-1) call.

  def fact(n)
    if n == 0
      1
    else
      n * fact(n-1)
    end
  end

We can manually capture the continuation in a proc …

  proc { |res| n * res }

Once captured, we can pass the continuation code around. In particular, we can pass it to the fact(n-1) call and let it handle its own continuation (where done is the name of the continuation passed into us) …

    fact(n-1, proc{|res| done.call(n * res) })

Rewriting our factorial function to handle its own continuation yields code like this …

  def fact_cps(n, done)
    if n == 0
      done.call(1)
    else
      fact_cps(n-1, proc {|res| done.call(res * n) })
    end
  end

Call with Current Continuation

Our "simulated" continuations are just procs (i.e. anonymous functions). They don’t really cause the function to return when called, they only calculate the return value. We must still arrange for that return value to be properly returned up the calling chain.

Wouldn’t it be nice if we could "grab" the real continuation of the current function. It would act just like our simulated continuations, but when called, it will really cause the function to return immediately.

If we had a mechanism to "grab" that current continuation, we could write a method that looked like this …

  def call_with_current_continuation
    current_continuation = #{magic to get the current continuation}
    yield(current_continuation)
  end

call_with_current_continuation yields to a block, passing in the continuation for itself. If the block ever calls current_continuation, it will immediately return from call_with_current_continuation.

If we could actually write call_with_current_continuation, then code like this is possible.

  call_with_current_continuation { |current_continuation|
    puts "This will be printed"
    current_continuation.call            # [A]
    puts "This will never get printed"
  }
  # Line [A] returns to HERE

Calling current_continuation will cause the program to go to the continuation immediately. The output will look like this …

  This will be printed

and the second puts will never be executed.

Enter Call/CC

Although we don’t have any magic code that will return the current continuation of an arbitrary method, Ruby does provide the functionality of call_with_current_continuation in the form of the callcc method. The continuation is passed to a block, and within the block we can do anything we want to with the continuation. Calling it will immediately cause the callcc call that created the continuation to return the value given to the continuation.

A Simple Example

Here is a fairly pedestrian use of callcc. This use of callcc is similar to the setjump/longjump functions in the C libarary.

  def level3(cont)
    cont.call("RETURN THIS")
  end

  def level2(cont)
    level3(cont)
    return "NEVER RETURNED"
  end

  def top_level_function
    callcc { |cc|
      level2(cc)
    }
  end

  answer = top_level_function
  puts answer        # => "RETURN THIS"

Here we are using continuations to immediately return a value from top_level, even though we are nested 3 levels deep in method calls.

Although callcc can be used to create some really mind-bending control structures, we will stick to using it to return to a point of execution higher up in the call stack in the following examples.

Variation #6: Eliminating Tail Recursion

Starting with recursive CPS version (from KataTwoCps), we replace the proc based continuations with the continuations from callcc. There is only minor differences between the proc based and callcc based versions.

Code

  # Setup the call with the top level continuations.  Notice that we
  # create two continuations in this function.  The outer-most one
  # (+ret+) is the normal return.  The inner continuation (+failed+)
  # is designed to indicate failure by returning a -1 from the top
  # level function

  def chop_with_cc(target, list)
    callcc { |ret|
      callcc { |failed|
        sub_chop_with_cc(target, list, ret, failed)
      }
      -1
    }
  end

  # Recursive helper function with continuations explicitly passed in.

  def sub_chop_with_cc(target, list, found, not_found)
    if list.size <= 1
      (list[0] == target) ? found.call(0) : not_found.call
    else
      mid = list.size/2
      if list[mid] > target
        sub_chop_with_cc(
          target,
          list[0...mid],
          found,
          not_found)
      else
        found.call(
          mid + callcc { |cc|
            sub_chop_with_cc(
              target,
              list[mid..-1],
              cc,
              not_found)
          } )
      end
    end
  end

  class TestChopContinuations < Test::Unit::TestCase
    alias chop chop_with_cc
    include ChopTests
  end

Mixing callcc and proc Based Continuations

One final twist before we are done. In KataTwoCps we wrote sub_chop_recursive_with_cps in a continuation passing style, but using proc based continuations. What would happed if we passed real callcc based continuations to a function expecting proc based ones?

It turns out that it works perfectly. Here’s the test code for it …

  def chop_with_cc_and_cps(target, list)
    callcc { |ret|
      callcc { |failed|
        # This function is defined in KataTwoCps
        sub_chop_recursive_with_cps(target, list, ret, failed)
      }
      -1
    }
  end

  class TestChopContinuations2 < Test::Unit::TestCase
    alias chop chop_with_cc_and_cps
    include ChopTests
  end

Next Time

Only one more variation to go, and this time it has nothing to do with continuations.