From: Eero Saynatkari <ruby-forum-reg@...>
Date: 2005-12-17T05:42:55+09:00
Subject: Re: Ruby tail recursion

Collins, Justin 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.

I really only call it 'tail-recursion optimization'
(or TRO) because that is its common name in the
literature.

> Code like:
> 
> def fun(x)
>     fun(x)
> end
> 
> fun(10)
> 
> should run forever, like it would in a language like Scheme or Lua. A 
> function calls itself, which calls itself, for infinitly. Unfortunately, 
> Ruby does not currently work that way.
>
> It's not that Ruby doesn't work "right" in this case, it just runs into 
> the limits of hardware (the size of the stack). The "proper" way of 
> implementing tail calls would never use the stack, so it wouldn't be an 
> issue.

Lua also stops running when you pull the power cord :)
There are limitations to all implementations, and the
'correct' way to do recursion is to actually recurse.
The TRO modifies code to run more efficiently (in the
broadest sense) for a special case which is why, I
presume, it was called an optimization. A non-frame-based
call system, for example, would not require this.

> By the way, is there a particular reason why tail calls aren't 
> implemented that way?

It is much harder to implement correctly :)

> -Justin


E


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