Tail call ``optimization''

[Sam Stephenson]

I was playing around with the retry keyword and realized it could be
used to implement tail recursive procedures in Ruby. So I came up with
this:

| class TailCall < Exception
| def initialize(*args)
| @args = args
| end
| attr_reader :args
| end
|
| class TailProc < Proc
| def call(*args)
| super *args
| rescue TailCall
| args = $!.args
| retry
| end
| end

Using TailProc to recurse with a depth of one million:
| irb(main):001:0> p = TailProc.new {|foo| raise TailCall.new(foo+1)
unless foo == 1000000}
| => #<TailProc:0x00056f5c@(irb):1>
| irb(main):002:0> p.call 0
(wait about a minute and a half here, on my system)
| => nil

Using a regular method for the same thing:
| irb(main):003:0> def foo(i); foo i+1 unless i == 1000000 end
| => nil
| irb(main):004:0> foo 0
| SystemStackError: stack level too deep

So I don't know how much of an ``optimization'' it really is, but it
does work. Just thought I'd share.

Sam

 

[Robert Klemme]

I was playing around with the retry keyword and realized it could be
used to implement tail recursive procedures in Ruby. So I came up with
this:

| class TailCall < Exception
| def initialize(*args)
| @args = args
| end
| attr_reader :args
| end
|
| class TailProc < Proc
| def call(*args)
| super *args
| rescue TailCall
| args = $!.args
| retry
| end
| end

Using TailProc to recurse with a depth of one million:
| irb(main):001:0> p = TailProc.new {|foo| raise TailCall.new(foo+1)
unless foo == 1000000}
| => #<TailProc:0x00056f5c@(irb):1>
| irb(main):002:0> p.call 0
(wait about a minute and a half here, on my system)
| => nil

Using a regular method for the same thing:
| irb(main):003:0> def foo(i); foo i+1 unless i == 1000000 end
| => nil
| irb(main):004:0> foo 0
| SystemStackError: stack level too deep

So I don't know how much of an ``optimization'' it really is, but it
does work. Just thought I'd share.

Interesting point. I'd just assume that this is more costly than doing a
tail call optimization by hand (i.e. converting a tail recursive method into
a method using iteration) because of the throw and object creations along
the way (btw, did you benchmark them?). The proper place would be the Ruby
interpreter although I readily admit that the implementation will be
definitely more complicated. But it will likely yield better results
perfoemance wise.

Kind regards

robert