From: "Collins, Justin" <collinsj@...>
Date: 2005-12-17T14:22:20+09:00
Subject: Re: Ruby tail recursion

------_=_NextPart_001_01C602C9.D4166B77
Content-Type: text/plain;
	charset="iso-8859-1"
Content-Transfer-Encoding: quoted-printable

Yes, you are right - it can improve performance. What I meant was more =
that performance gains aren't usually the reason for doing it.

However, I am fairly sure it isn't that difficult (in the general case) =
to implement tail calls this way. For example, in one of my classes we =
implemented a parser,interpreter,stack,heap,etc. with proper tail calls. =
Of course, it was for a tiny language, so that's why I'm not sure about =
how easy it would be to do with Ruby.=20

The article you linked says at the end:
"Automatic optimization, on the other hand, is easy to implement in a =
compiler
and has little run-time cost. It will always identify opportunities for
tail recursion removal, even in complex functions. It improves execution
time without degrading the quality of source code, in some
cases by more than 700%, and can even beat carefully hand-optimized
code. Tail recursion removal frees the programmer to program
in the most elegant and natural style, without worrying about
performance problems resulting from inefficient language =
implementations."

Sounds like a good reason to implement it to me!

I do agree that Ruby doesn't encourage programming recursively, really, =
but why shouldn't it? Recursion isn't necessary, but it can allow for =
"nicer" solutions to naturally recursive problems.

BTW, I am not going to be upset if this isn't implemented in Ruby, I'm =
just saying it would nice :)

-Justin

-----Original Message-----
From: Jakub Hegenbart [mailto:kyosuke@seznam.cz]
Sent: Fri 12/16/2005 2:28 PM
To: ruby-talk ML
Subject: Re: Ruby tail recursion
=20
Collins wrote:
> I wouldn't really call it optimization (although I guess it is), it's =
more like implementing them in such a way that you get around the =
limitations of computer memory. (As opposed to just making them run =
faster or something.) It doesn't really have anything to do with =
efficiency in that sense.
>  =20
Well, what about this, for example?

http://big-oh.cs.hamilton.edu/~bailey/pubs/techreps/TR-2001-2.pdf

Tail calls are essentialy safe GOTOs with argument passing, there is a=20
potential for performance gain. ;-) But in Ruby, its benefits wouldn't=20
be that noticeable, I guess...I kind of don't think that the programming =

style that Ruby encourages is a good candidate for tail call=20
optimization. :-D

That doesn't mean that a (fictional) Ruby implementation compiling to=20
native code couldn't take advantage of some tail-call optimizable=20
intermediate form, but the current implementation IMO doesn't need it.

Jakub


------_=_NextPart_001_01C602C9.D4166B77--