The Artima Developer Community
Sponsored Link

Ruby Buzz Forum
Kata Two Worked (continued) -- Call/CC

0 replies on 1 page.

Welcome Guest
  Sign In

Go back to the topic listing  Back to Topic List Click to reply to this topic  Reply to this Topic Click to search messages in this forum  Search Forum Click for a threaded view of the topic  Threaded View   
Previous Topic   Next Topic
Flat View: This topic has 0 replies on 1 page
Jim Weirich

Posts: 351
Nickname: jimw
Registered: Jul, 2003

Jim Weirich is a long time software developer and a relatively recent Ruby enthusiast.
Kata Two Worked (continued) -- Call/CC Posted: Jul 26, 2003 4:11 PM
Reply to this message Reply

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:
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 | }

Finally, here is the write up on continuations and callcc that I’ve been promising. This has been a hard one to write. I had the basics written up about the same time as the KataTwoNoTail article, but I felt it needed some refinement. In a lot of ways, writing about and explaining continuations is a lot harder than actually using them.


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
      n * fact(n-1)

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| * res) })

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

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

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}

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"            # [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)"RETURN THIS")

  def level2(cont)
    return "NEVER RETURNED"
  def top_level_function
    callcc { |cc|

  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.


  # 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)
  # 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) ? :
      mid = list.size/2
      if list[mid] > target
          mid + callcc { |cc|
          } )
  class TestChopContinuations < Test::Unit::TestCase
    alias chop chop_with_cc
    include ChopTests

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)

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

Next Time

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

Read: Kata Two Worked (continued) -- Call/CC

Topic: Happy Birthday, Ruby Previous Topic   Next Topic Topic: Welcome to

Sponsored Links


Copyright © 1996-2019 Artima, Inc. All Rights Reserved. - Privacy Policy - Terms of Use