«

I did some googling to find out if Ruby supports tail call optimization,
as I wanted to write tail-recursive functions. All posts I found
indicated that 1.9 supports this, but it is not enabled by default.
However, all those posts were about two years old, so I'm wondering what
is the current situation: do I still need to upgrade to 1.9 to get that
capability? Or is there something in 1.8 I can enable?

--
Posted via http://www.ruby-forum.com/.

Terry Michaels wrote in post #993440:
> I did some googling to find out if Ruby supports tail call optimization,
> as I wanted to write tail-recursive functions. All posts I found
> indicated that 1.9 supports this, but it is not enabled by default.
> However, all those posts were about two years old, so I'm wondering what
> is the current situation: do I still need to upgrade to 1.9 to get that
> capability? Or is there something in 1.8 I can enable?

Couldn't you test that by creating two recursive functions: one with a
tail call and one without, and then benchmarking them?

--
Posted via http://www.ruby-forum.com/.

[Note: parts of this message were removed to make it a legal post.]

There's a flag that you can enable to turn it on.

Also, http://timelessrepo.com/tailin-ruby

7stud -- wrote:

> Terry Michaels wrote in post #993440:
> > I did some googling to find out if Ruby supports tail call optimization,
> > as I wanted to write tail-recursive functions. All posts I found
> > indicated that 1.9 supports this, but it is not enabled by default.
> > However, all those posts were about two years old, so I'm wondering what
> > is the current situation: do I still need to upgrade to 1.9 to get that
> > capability? Or is there something in 1.8 I can enable?
>
> Couldn't you test that by creating two recursive functions: one with a
> tail call and one without, and then benchmarking them?

def fib n, a = 0, b = 1
if n == 0
b
else
a, b = b, a + b
fib n - 1, a, b
end
end

1.upto(9){|n|
p [n, fib(n)]
}

p fib( 50_000 )

==>

[1, 1]
[2, 2]
[3, 3]
[4, 5]
[5, 8]
[6, 13]
[7, 21]
[8, 34]
[9, 55]
try4.rb:23:in `fib': stack level too deep (SystemStackError)
from try4.rb:23:in `fib'
from try4.rb:31


irb(main):004:0> VERSION
=> "1.8.7"

[Note: parts of this message were removed to make it a legal post.]

it seems like fib(50000) is not only too big for MRI ruby, but also Python
and Lua and Rubinius panic on it...

jRuby also complains but points to instructions to increase the stack...

otherways, I have MacRuby, Racket and Haskell in their tail recursive fib
solving routine, no results yet but all are still working...

2011/4/18 WJ <>

> 7stud -- wrote:
>
> > Terry Michaels wrote in post #993440:
> > > I did some googling to find out if Ruby supports tail call
> optimization,
> > > as I wanted to write tail-recursive functions. All posts I found
> > > indicated that 1.9 supports this, but it is not enabled by default.
> > > However, all those posts were about two years old, so I'm wondering
> what
> > > is the current situation: do I still need to upgrade to 1.9 to get that
> > > capability? Or is there something in 1.8 I can enable?
> >
> > Couldn't you test that by creating two recursive functions: one with a
> > tail call and one without, and then benchmarking them?
>
> def fib n, a = 0, b = 1
> if n == 0
> b
> else
> a, b = b, a + b
> fib n - 1, a, b
> end
> end
>
> 1.upto(9){|n|
> p [n, fib(n)]
> }
>
> p fib( 50_000 )
>
> ==>
>
> [1, 1]
> [2, 2]
> [3, 3]
> [4, 5]
> [5, 8]
> [6, 13]
> [7, 21]
> [8, 34]
> [9, 55]
> try4.rb:23:in `fib': stack level too deep (SystemStackError)
> from try4.rb:23:in `fib'
> from try4.rb:31
>
>
> irb(main):004:0> VERSION
> => "1.8.7"
>
>

Louis-Philippe wrote:

>
> otherways, I have MacRuby, Racket and Haskell in their tail recursive fib
> solving routine, no results yet but all are still working...

I'm surprised that they are still working. Gambit Scheme takes
very little time for this.

(define (fib n a b)
(if (zero? n)
b
(fib (- n 1) b (+ a b))))

(time
(let ((bigfib (fib 50000 0 1)))
#t))

==>

453 ms real time
454 ms cpu time (438 user, 16 system)
762 collections accounting for 141 ms real time (125 user, 16 system)
119074992 bytes allocated
no minor faults
no major faults

On 2011-04-18, at 13:40, Louis-Philippe wrote:

> it seems like fib(50000) is not only too big for MRI ruby, but also =
Python
> and Lua and Rubinius panic on it...
There was some traffic on the Python mailing list maybe a year ago, it =
seems that Python will not implement TR optimization in the near (or =
likely far) future; Python's BDFL seems unconvinced of its value. AFAIK =
no TR PEP has ever been written. Lua's TR is very specific, I believe =
the recursive call has to stand as a statement on its own. When I tried =
this with Lua 5.2.0 (alpha), I saw every evidence of TR optimization.

> function fib(n)
>> local function fib1(n, a, b)
>> if n =3D=3D 0 then
>> return b
>> else
>> a, b =3D b, a + b
>> return fib1(n - 1, a, b)=20
>> end
>> end
>> return fib1(n, 0, 1)
>> end
> print(fib(1), fib(3), fib(10), fib(100), fib(1000), fib(10000))
1 3 89 5.7314784401382e+20 7.0330367711423e+208 =
inf
> print(fib(1000000))
inf

TR optimization can't easily be done on the JVM (and probably on .NET), =
because it interferes with the code verification process the JVM does. =
Accordingly, I doubt TR can be made mandatory for Ruby implementations, =
which is what I'd like. However, a boolean function or built-in constant =
that says whether it's performed would be very nice, so one can test =
this before running a program.=20

-- vincent=

[Note: parts of this message were removed to make it a legal post.]

Guido has said that any interpreter that implements TCO is not Python.

On 2011-04-18, at 18:42, Steve Klabnik wrote:
> Guido has said that any interpreter that implements TCO is not Python.

I recall that quote, and it totally mystifies me. Of course, he IS BDFL, =
and has the right to say what is and is not Python. But it seems like a =
very peculiar comment, and, based on some of the message traffic I saw =
at the time, he seems to misunderstand what this optimization is. There =
are good reasons (relating to the JVM, which I mentioned earlier) why =
one might decide NOT to make it mandatory, but his absolute refusal =
seems somewhat doctrinaire to me.=20

If every environment in which Ruby (or Python) runs supported TCO, then =
there would be little reason to ban it. If that isn't practical, then a =
way of discerning whether it's supported in a given implementation seems =
appropriate.

That said, very few tail recursive methods would likely be written in =
Ruby, given the many other fine ways of looping. So my reason for =
wanting it has more to do with a small set of cases where it's more =
expressive than other techniques, rather than something that =
substantially changes the way we write programs.=20

In reality, the more useful benefit of TCO comes when it's not a =
recursive procedure, but simply invoking another method, and thus using =
less stack. That leads, for example, to a very nice and clean way of =
writing state machines, for example.=20

-- vincent

On Apr 18, 2011, at 10:51 PM, Vincent Manis wrote:

> In reality, the more useful benefit of TCO comes when it's not a =
recursive procedure, but simply invoking another method, and thus using =
less stack. That leads, for example, to a very nice and clean way of =
writing state machines, for example.=20

This is the most compelling argument for me, especially regarding Ruby: =
modern
Ruby approaches emphasize heavy refactoring to small methods, and since =
nearly
everything else you do is a method call, I'm willing to bet TCO could =
kick in a fair
amount in the tail of those small methods. It might add up. But that's =
just my gut
instinct; I've never toyed with the TCO options.

Michael Edgar

http://carboni.ca/=