This post originated from an RSS feed registered with Ruby Buzz
by Jim Weirich.
Original Post: Kata Two Worked (continued) -- Eliminating Tail Recursion
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.
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.
Variation #5: Eliminating 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.
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).
First Attempt
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.
Second Attempt
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
Problems Encountered
No problems were encounter other than the already discussed issue regarding
the reassignment of found and mid.
References
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.
Next Time
We still haven’t talked about callcc. I promise we will get
to it next time.
Previous Topic
