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
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.
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.
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.
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)
}
-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
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
Only one more variation to go, and this time it has nothing to do with continuations.