In KataTwoCps we talked about passing continuations into functions. It turns out that continuations were just functions (we used Proc objects) that encapsulated the rest of the calculation to be performed. Using continuations allowed us to turn normal recursive calls into tail recursion.
One of the benefits of tail recursion is that it is easy to turn a tail recursive function into an iterative function. Lets try that transform on our CPS version from KataTwoCps.
Tail recursive calls can be transformed into gotos to the beginning of the function. Any parameters passed to the call are assigned to the existing parameters.
So, the following call …
sub_chop_cps(target, list[0...mid], found, not_found)
would be rewritten as …
target = target list = list[0...mid] found = found not_found = not_found goto BEGINNING_OF_FUNCTION
We can drop the redundant assignments (e.g. target = target). We will also cleverly use an infinite while loop instead of an explicit goto. (Ruby doesn’t have raw gotos, but if you are patient, I’ll show you how to implement gotos).
Here’s our first attempt at tail recursion removal.
def chop_tail_recursive(target, list)
sub_chop_tail_recursive(target, list, proc{|x| x}, proc{-1})
end
def sub_chop_tail_recursive(target, list, found, not_found)
while (true)
if list.size <= 1
return (list[0] == target) ? found.call(0) : not_found.call
else
mid = list.size/2
if list[mid] > target
list = list[0...mid]
else
list = list[mid..-1]
found = proc{|x| found.call(x+mid)} # PROBLEM
end
end
end
end
Unfortunately, this code fails the unit tests.
At the line marked PROBLEM we create a Proc object that references found. The intent of this line is that sometime in the future this proc will be called and the current value of found will be used. Unfortunately, we immediately clobber the value of found, sabotaging that future call. (The mid value has a similar problem).
To fix this, we need to create a new context where the value represented by found (and mid) is not lost. If we replace the PROBLEM line with the following, our problems are solved.
found = proc {|ret, m| proc{|x| ret.call(x+m)} }.call(found, mid)
Here we create our Proc object referencing ret and m instead of found and mid. Both ret and m are created in the scope of an enclosing block and initialized with the values of found and mid. The key is that ret and m are never reassigned, therefore they never become invalid.
Our second attempt changes the PROBLEM line and works much better. Here is the complete source code.
def chop_tail_recursive(target, list)
sub_chop_tail_recursive(target, list, proc{|x| x}, proc{-1})
end
def sub_chop_tail_recursive(target, list, found, not_found)
while (true)
if list.size <= 1
return (list[0] == target) ? found.call(0) : not_found.call
else
mid = list.size/2
if list[mid] > target
list = list[0...mid]
else
list = list[mid..-1]
found = proc {|ret, m| proc{|x| ret.call(x+m)} }.call(found, mid)
end
end
end
end
class TestChopTailRecursive < Test::Unit::TestCase
alias chop chop_tail_recursive
include ChopTests
end
No problems were encounter other than the already discussed issue regarding the reassignment of found and mid.
Dan Sugalski is also talking about Continuations, CPS, TailRecursion, and more. Dan is writing the byte code engine that will eventually power Perl 6 (and perhaps Ruby and Python as well). Dan’s viewpoint is a bit more oriented toward implementation issues surrounding tail recursion and continuations, but make a nice balance to what you read here.
We still haven’t talked about callcc. I promise we will get to it next time.