In another thread someone mentioned tail recursion doesn't work right
in Ruby. Could someone please expand upon that?
The current interpreter does not do tail-recursion optimization.
This means that deeply recursive operations are not as efficient
as they could be.
E
···
On 2005.12.16 12:41, Mark Ericson <mark.ericson@gmail.com> wrote:
In another thread someone mentioned tail recursion doesn't work right
in Ruby. Could someone please expand upon that?
Here's a somewhat lengthy explanation. Well, you asked for it 
Here's a recursive method:
def tailrec_max(arr, i=0, best=-Infinity)
return best if i==arr.length
rec_max(arr, i+1, (arr[i]>best ? arr[i] : best))
end
Assuming we call tailrec_max([1,2,3,4]), the stack will at some point
look like this:
- tairec_max([..], 4, 4) # i==arr.length, returns best=4
- tairec_max([..], 3, 3)
- tairec_max([..], 2, 2)
- tairec_max([..], 1, 1)
- tairec_max([..], 0, -Infinity) # initial call
The method calls itself a number of times, and each invocation is
pushed on the stack. The callers stay on the stack, each waiting for
the return of the method it called.
This is standard method invocation, and happens every time a method
calls another. The calls further down the stack are waiting for the
calls above to complete before continuing whatever they were doing.
But in some cases there is no point for a method to hang around..
The tailrec_max method is such a case: After it has called itself,
there is nothing more for it to do, except to wait for the return
value and pass it on unchanged. This is called tail recursion.
Some languages optimize for this: When the compiler or interpreter can
determine that the return value of the method is the same as the
return value of the next method call, it can in effect skip the
recursive calls and recompile the entire method into a for loop, which
is faster and does not run into stack size limitations no matter how
many recursive calls there are.
Here's a similar method that cannot be optimized:
def non_tailrec(arr, i=0, best=-Infinity)
return best if i==arr.length
rec_max(arr, i+1, (arr[i]>best ? arr[i] : best))+1
end
The '+1' at the end means that this method needs the stack: It has to
wait for the return value in order to do the add.
Lisp does tail recursion optimization (in most implementations
anyway), Ruby doesn't.
It's not a matter of "not working right": Recursion, tail or no tail,
works just as well as any other method call in Ruby. Plenty of
languages thrive without optimizing for tail recursion, Java is one of
them.
The combination of a small stack and lack of tail recursion
optimization does mean that in Ruby, recursion can hardly replace
every other looping construct the way it can in Lisp. You'll be the
judge of whether that is important.
I think Lisp is a somewhat special case: The entire language grew out
of a recursive definition (called lambda calculus), and a Lisp dialect
I used at university had no 'for', no 'while' and no other data
structure than linked lists. Now in a language like that, it makes
sense to optimize for recursion 
jf
···
On 2005.12.16 12:41, Mark Ericson <mark.ericson@gmail.com> wrote:
> In another thread someone mentioned tail recursion doesn't work right
> in Ruby. Could someone please expand upon that?
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.
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.
By the way, is there a particular reason why tail calls aren't implemented that way?
-Justin
···
-----Original Message-----
From: ruerue@purr.magical-cat.org on behalf of Eero Saynatkari
Sent: Thu 12/15/2005 7:55 PM
To: ruby-talk ML
Subject: Re: Ruby tail recursion
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1
On 2005.12.16 12:41, Mark Ericson <mark.ericson@gmail.com> wrote:
In another thread someone mentioned tail recursion doesn't work right
in Ruby. Could someone please expand upon that?
The current interpreter does not do tail-recursion optimization.
This means that deeply recursive operations are not as efficient
as they could be.
E
The reason that tail recursion is "important" is that functional
programming style generally avoids using iterators (or more generally
it avoids changing any variable after it's initialized).
So instead of a "loop", one would use recursion. So most "functional"
programming languages require any implementation of that language to
properly handle tail-recursion. With this "optimization" one can
freely implement an algorithm in the "functional" style w/o concerns of
it bombing out when the input is too large.
I found that ~1300 is the maximum depth of the stack on my machine....
So I can't use recursion to iterate over more than ~1300 items.
Code corrections:
def tailrec_max(arr, i=0, best=-Infinity)
return best if i==arr.length
tailrec_max(arr, i+1, (arr[i]>best ? arr[i] : best))
end
def non_tailrec(arr, i=0, best=-Infinity)
return best if i==arr.length
non_tailrec(arr, i+1, (arr[i]>best ? arr[i] : best))+1
end
Thanks, I get it now! Some languages will generate code that won't
overflow the stack when doing tail recursion. Ruby doesn't have that
optimization, yet.
···
On 12/16/05, Collins, Justin <collinsj@seattleu.edu> 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.
Code like:
def fun(x)
fun(x)
endfun(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.
By the way, is there a particular reason why tail calls aren't implemented that way?
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)
endfun(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/\.
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 agree that it's not (just) optimization in the sense of 'runs
faster'. Without tail-recursion optimization there are things you
simply cannot do in a recursive fashion.
A simple example is iterating over a collection.
For example, these two 'max' methods are equivalent, so which one you
prefer is mainly a matter of style preferences.
def each_max(elms)
max=-Infinity
elms.each {|x| max=x if x>max }
max
end
def for_max(elms)
max=-Infinity
for elm in elms
max=elm if elm>max
end
max
end
The tail recursive version,
def tailrec_max(arr, i=0, max=-Infinity)
return max if i==arr.length
tailrec_max(arr, i+1, (arr[i]>max ? arr[i] : max)
end
would be equivalent to the first two, and offer a third style, if Ruby
had tail optimization.
As it is, each element access adds another method call on the stack,
and the recursion does not bottom out before the end of the sequence,
so we will get an exception whenever there are more than 'stack-limit'
elements in the sequence. The limit is 1200 on my system.
1200 elements in a sequence is nothing - consider iterating over
characters in a string, or lines in a log file, it doesn't take much
to have 1200 characters or lines.
This makes recursive iteration in Ruby a curiosity that cannot be
actually used for very much.
By the way, is there a particular reason why tail calls aren't implemented that way?
My guess is that it's not implemented simply because recursion isn't
used very much in Ruby. (It's the chicken and egg: Recursion won't be
generally viable until the optimization is in place.)
Although I can live without it, I'd like to see tail recursion
optimization in Ruby.
If it's up to debate, I'm voting yes
jf
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.
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 potential for performance gain. But in Ruby, its benefits wouldn't 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 optimization. 
That doesn't mean that a (fictional) Ruby implementation compiling to native code couldn't take advantage of some tail-call optimizable intermediate form, but the current implementation IMO doesn't need it.
Jakub
I hope people do realize that they can change the
maximum size of the stack allocated to their ruby process. For
example on Mac OS X using bash:
$ ulimit -s
8192
$ ruby -e '@i = 0; def foo; @i += 1; foo; end; begin; foo; rescue; puts @i; end'
1204
$ ulimit -s 16384
$ ruby -e '@i = 0; def foo; @i += 1; foo; end; begin; foo; rescue; puts @i; end'
2484
The ulimit command is built-in to the shell so if you are looking for
ways to change the maximum size of the stack for your processes, look
for ulimit or limit in your shell documentation.
I don't know enough about Windows to offer any hints for that environment.
Gary Wright
`
···
On Dec 18, 2005, at 9:57 AM, jwesley wrote:
I found that ~1300 is the maximum depth of the stack on my machine....
So I can't use recursion to iterate over more than ~1300 items.
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.
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
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.
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
potential for performance gain. But in Ruby, its benefits wouldn't
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
optimization.
That doesn't mean that a (fictional) Ruby implementation compiling to
native code couldn't take advantage of some tail-call optimizable
intermediate form, but the current implementation IMO doesn't need it.
Jakub
Jakub Hegenbart wrote:
Tail calls are essentialy safe GOTOs with argument passing, there is a
potential for performance gain.
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
optimization.
Good point. Tail-call recursion is just a form of recursion that's easy
to turn into iteration, but (at least to me) one of ruby's strengths is
its iterators, so one might as well just write code in iterative form
instead of tail-call recursive form!
···
--
Neil Stevens - neil@hakubi.us
'A republic, if you can keep it.' -- Benjamin Franklin
gwtmp01@mac.com ha scritto:
···
On Dec 18, 2005, at 9:57 AM, jwesley wrote:
I found that ~1300 is the maximum depth of the stack on my machine....
So I can't use recursion to iterate over more than ~1300 items.I hope people do realize that they can change the
maximum size of the stack allocated to their ruby process. For
example on Mac OS X using bash:
<snip>
IIRC ruby 1.9 even has Process.setrlimit as a builtin, not sure about 1.8.4 .
gwtmp01@mac.com schrieb:
I found that ~1300 is the maximum depth of the stack on my machine....
So I can't use recursion to iterate over more than ~1300 items.I hope people do realize that they can change the
maximum size of the stack allocated to their ruby process. For
example on Mac OS X using bash:$ ulimit -s
8192
$ ruby -e '@i = 0; def foo; @i += 1; foo; end; begin; foo; rescue; puts @i; end'
1204
$ ulimit -s 16384
$ ruby -e '@i = 0; def foo; @i += 1; foo; end; begin; foo; rescue; puts @i; end'
2484The ulimit command is built-in to the shell so if you are looking for
ways to change the maximum size of the stack for your processes, look
for ulimit or limit in your shell documentation.I don't know enough about Windows to offer any hints for that environment.
If you search in the tuby-talk archives, you can find this:
@i = 0
def foo
@i += 1
foo
end
begin
foo
rescue
puts @i # => 1342
end
self.class.tailcall_optimize :foo
require "timeout"
begin
Timeout.timeout 10 do
foo
end
rescue Exception => e
puts @i # => 542798
end
Implemented in Ruby, so not as fast as real TRO.
Regards,
Pit
···
On Dec 18, 2005, at 9:57 AM, jwesley wrote:
Neil Stevens wrote:
Good point. Tail-call recursion is just a form of recursion that's easy
to turn into iteration, but (at least to me) one of ruby's strengths is
its iterators, so one might as well just write code in iterative form
instead of tail-call recursive form!
Well, my take is this. If you happen to write recursive code, and it
happens to be tail-call optimizable, the interpreter should be smart
enough not to let the stack grow unnecessarily. That's a fairly easy
fix if I understand rightly.
That's a separate issue from whether that style is necessarily the
best in a given situation.
Hal
Collins, Justin ha scritto:
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.
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
I think it is worth noting that Koichi Sasada said once that he plans to support tail call optimization in YARV, even because IIRC he wants it to be able to support Scheme too, which requires TCO.
I think he'd appreciate if someone could do that (hint! hint!).
Neil Stevens ha scritto:
Jakub Hegenbart wrote:
Tail calls are essentialy safe GOTOs with argument passing, there is a
potential for performance gain.
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
optimization.Good point. Tail-call recursion is just a form of recursion that's easy
to turn into iteration, but (at least to me) one of ruby's strengths is
its iterators, so one might as well just write code in iterative form
instead of tail-call recursive form!
well, but maybe it could be nice to write iterators in a recursive way, i.e
class Parser
def each_token &blk
tok=shift_token!
blk.call(tok)
each_token(&blk)
end
end
gabriele renzi <surrender_it@-remove-yahoo.it> writes:
I think it is worth noting that Koichi Sasada said once that he plans
to support tail call optimization in YARV, even because IIRC he wants
it to be able to support Scheme too, which requires TCO.
I think he'd appreciate if someone could do that (hint! hint!).
IIRC, YARV already supports reusing the current stack frame for calls
to the same method (that's not real TCO, but far better than nothing).
···
--
Christian Neukirchen <chneukirchen@gmail.com> http://chneukirchen.org