M
Mark Ericson
In another thread someone mentioned tail recursion doesn't work right
in Ruby. Could someone please expand upon that?
in Ruby. Could someone please expand upon that?
J
Johannes Friestad
Here's a somewhat lengthy explanation. Well, you asked for it 
Here's a recursive method:
def tailrec_max(arr, i=3D0, best=3D-Infinity)
return best if i=3D=3Darr.length
rec_max(arr, i+1, (arr>best ? arr : 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=3D=3Darr.length, returns best=3D4
- 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=3D0, best=3D-Infinity)
return best if i=3D=3Darr.length
rec_max(arr, i+1, (arr>best ? arr : 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
Here's a recursive method:
def tailrec_max(arr, i=3D0, best=3D-Infinity)
return best if i=3D=3Darr.length
rec_max(arr, i+1, (arr>best ? arr : 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=3D=3Darr.length, returns best=3D4
- 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=3D0, best=3D-Infinity)
return best if i=3D=3Darr.length
rec_max(arr, i+1, (arr>best ? arr : 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
J
Johannes Friestad
Code corrections:
def tailrec_max(arr, i=3D0, best=3D-Infinity)
return best if i=3D=3Darr.length
tailrec_max(arr, i+1, (arr>best ? arr : best))
end
def non_tailrec(arr, i=3D0, best=3D-Infinity)
return best if i=3D=3Darr.length
non_tailrec(arr, i+1, (arr>best ? arr : best))+1
end
def tailrec_max(arr, i=3D0, best=3D-Infinity)
return best if i=3D=3Darr.length
tailrec_max(arr, i+1, (arr>best ? arr : best))
end
def non_tailrec(arr, i=3D0, best=3D-Infinity)
return best if i=3D=3Darr.length
non_tailrec(arr, i+1, (arr>best ? arr : best))+1
end
C
Collins, Justin
------_=_NextPart_001_01C60224.6EE5ACC1
Content-Type: text/plain;
charset="iso-8859-1"
Content-Transfer-Encoding: quoted-printable
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: (e-mail address removed)-cat.org on behalf of Eero Saynatkari
Sent: Thu 12/15/2005 7:55 PM
To: ruby-talk ML
Subject: Re: Ruby tail recursion
=20
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1
The current interpreter does not do tail-recursion optimization.
This means that deeply recursive operations are not as efficient
as they could be.
E=20
------_=_NextPart_001_01C60224.6EE5ACC1--
Content-Type: text/plain;
charset="iso-8859-1"
Content-Transfer-Encoding: quoted-printable
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: (e-mail address removed)-cat.org on behalf of Eero Saynatkari
Sent: Thu 12/15/2005 7:55 PM
To: ruby-talk ML
Subject: Re: Ruby tail recursion
=20
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1
The current interpreter does not do tail-recursion optimization.
This means that deeply recursive operations are not as efficient
as they could be.
E=20
------_=_NextPart_001_01C60224.6EE5ACC1--
M
Mark Ericson
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.
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.
does not currently work that way.
ting tail calls would never use the stack, so it wouldn't be an issue.
overflow the stack when doing tail recursion. Ruby doesn't have that
optimization, yet.
e 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.
ction calls itself, which calls itself, for infinitly. Unfortunately, Ruby =
does not currently work that way.
he limits of hardware (the size of the stack). The "proper" way of implemen=
ting tail calls would never use the stack, so it wouldn't be an issue.
d that way?
E
Eero Saynatkari
I really only call it 'tail-recursion optimization'
(or TRO) because that is its common name in the
literature.
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.
It is much harder to implement correctly
E
J
Johannes Friestad
I wouldn't really call it optimization (although I guess it is), it's mor=
e 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=3D-Infinity
elms.each {|x| max=3Dx if x>max }
max
end
def for_max(elms)
max=3D-Infinity
for elm in elms
max=3Delm if elm>max
end
max
end
The tail recursive version,
def tailrec_max(arr, i=3D0, max=3D-Infinity)
return max if i=3D=3Darr.length
tailrec_max(arr, i+1, (arr>max ? arr : 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.
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
e 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=3D-Infinity
elms.each {|x| max=3Dx if x>max }
max
end
def for_max(elms)
max=3D-Infinity
for elm in elms
max=3Delm if elm>max
end
max
end
The tail recursive version,
def tailrec_max(arr, i=3D0, max=3D-Infinity)
return max if i=3D=3Darr.length
tailrec_max(arr, i+1, (arr>max ? arr : 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.
d 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
J
Jakub Hegenbart
Well, what about this, for example?Collins said:
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. :-D
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
C
Collins, Justin
------_=_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:[email protected]]
Sent: Fri 12/16/2005 2:28 PM
To: ruby-talk ML
Subject: Re: Ruby tail recursion
=20
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.
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--
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:[email protected]]
Sent: Fri 12/16/2005 2:28 PM
To: ruby-talk ML
Subject: Re: Ruby tail recursion
=20
more like implementing them in such a way that you get around the =Collins said:
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=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--
N
Neil Stevens
Jakub said:
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!
H
Hal Fulton
Neil said:
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
G
gabriele renzi
Collins, Justin ha scritto:
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!).
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!).
G
gabriele renzi
Neil Stevens ha scritto:
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
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
J
jwesley
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.
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.
G
gwtmp01
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
`
G
gabriele renzi
(e-mail address removed) ha scritto:
<snip>
IIRC ruby 1.9 even has Process.setrlimit as a builtin, not sure about
1.8.4 .
<snip>
IIRC ruby 1.9 even has Process.setrlimit as a builtin, not sure about
1.8.4 .
P
Pit Capitain
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