fogus: Tramp.oline

Tramp.oline

Feb 25, 2011

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”¹ thing and call it iteratively; otherwise, we use the first “non-callable” thing as the final result. Or, we can write something called a trampoline² 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.

I’m new to Ruby, so bear with me when I use incorrect terms. Better yet, post a comment to let me know. ↩
I implemented in this way for various reasons, but mostly because I wanted to test out some orthogonal features of Ruby. ↩

4 Comments, Comment or Ping

Nikolai Weibull

A somewhat more idiomatic alternative:

module Tramp
  class << self
    def oline(f, *args)
      result = f.call(*args)
      result = result.call while result.respond_to? :call
      result
    end
  end
end

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 using class << self and the statement modifier for the while, 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, like lambda { 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

Send More Paramedics

Tramp.oline

4 Comments, Comment or Ping

Reply to “Tramp.oline”