Tramp.oline
For various reasons I’ve taken it upon myself to learn Ruby and I thought I would share a humdinger.
Implementing functions checking for odd-ness and even-ness is often held as an example for illustrating mutual function recursion, and the same can be illustrated with Ruby:
def e?(n)
if n.zero?
true
else
o?(n.abs - 1)
end
end
def o?(n)
if n.zero?
false
else
e?(n.abs - 1)
end
end
And these functions will work mostly as expected:
o? 201
#=> true
e? 991
#=> false
However, you run into stack issues when attempting to check larger values:
e? 20000
# SystemStackError: stack level too deep
The simplest way to ensure that the stack is maintained is by avoiding the stack altogether. We can do this by re-writing o?
and e?
to wrap the mutually recursive calls in a proc taking no args:
def e?(n)
if n.zero?
true
else
lambda {| | o?(n.abs - 1) }
end
end
def o?(n)
if n.zero?
false
else
lambda {| | e?(n.abs - 1) }
end
end
Making the new call as you might expect returns a Proc
:
o? 3
#=> #<Proc:0x00000001011be868>
So what do we do with this beast? Well, the simple thing to do is to manually check for a “callable”1 thing and call it iteratively; otherwise, we use the first “non-callable” thing as the final result. Or, we can write something called a trampoline2 to do those steps for us:
class Tramp
def self.new
raise "Cannot create instances of #{self.inspect}"
end
def self.oline(fun, *args)
ret = fun.call(*args)
while (ret.is_a? Proc) or (ret.is_a? Method)
ret = ret.call
end
ret
end
end
And now, we can check larger numbers without blowing the stack:
Tramp.oline(method(:e?), 20000)
#=> true
Tramp.oline(lambda {| | o? 200000 })
#=> false
Fun, fun, fun.
:f
4 Comments, Comment or Ping
Nikolai Weibull
A somewhat more idiomatic alternative:
Feb 25th, 2011
Colin Jones
Nice! FWIW, callable seems like exactly the right word to me there.
I do agree with Nikolai above on the
respond_to? :call
idiomaticness. I don’t mind usingclass << self
and the statement modifier for thewhile
, but either way seems fine to me. I also agree that if you just want this namespace Tramp and want to prevent object creation, you’re better off using a module. And one last syntax nitpick: it’s more idiomatic to omit the pipes when defining a block that doesn’t take any arguments, likelambda { o?(n.abs - 1) }
.It’s really cool to see Ruby written in this way. I tend to forget how many great functional features are available day-to-day.
Feb 25th, 2011
Janus
Shouldn’t Tramp.oline(method(:e?), 20000) be Tramp.oline?(method(:e?), 20000). Is it a typo or Ruby magic which I need to learn?
Mar 1st, 2011
fogus
@Janus
The correct call is
Tramp.oline(...)
. I am not sure how the?
got into there as it’s not in my original source. I blame sunspots. ;-) Thanks for the catch — it’s been fixed.:f
Mar 1st, 2011
Reply to “Tramp.oline”