Forum: Ruby Ruby tail recursion

Announcement (2017-05-07): www.ruby-forum.com is now read-only since I unfortunately do not have the time to support and maintain the forum any more. Please see rubyonrails.org/community and ruby-lang.org/en/community for other Rails- und Ruby-related community platforms.
Mark E. (Guest)
on 2005-12-16 05:42
(Received via mailing list)
In another thread someone mentioned tail recursion doesn't work right
in Ruby.   Could someone please expand upon that?
Eero S. (Guest)
on 2005-12-16 05:57
(Received via mailing list)
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On 2005.12.16 12:41, Mark E. <removed_email_address@domain.invalid> 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
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.1 (GNU/Linux)

iD8DBQFDokNoxvA1l6h+MUMRAn0YAJ0Rq0LSRvjXtOS3HSwdtc9fsXURzACeJo6o
NrI1oMY1/FS/PyIcV1LU6ho=
=eoNK
-----END PGP SIGNATURE-----
Johannes F. (Guest)
on 2005-12-16 10:24
(Received via mailing list)
> On 2005.12.16 12:41, Mark E. <removed_email_address@domain.invalid> 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
Johannes F. (Guest)
on 2005-12-16 10:42
(Received via mailing list)
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
Collins, Justin (Guest)
on 2005-12-16 11:40
(Received via mailing list)
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
Mark E. (Guest)
on 2005-12-16 22:41
(Received via mailing list)
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.
Eero S. (Guest)
on 2005-12-16 22:42
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
Johannes F. (Guest)
on 2005-12-16 23:06
(Received via mailing list)
> 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
Jakub H. (Guest)
on 2005-12-17 00:30
(Received via mailing list)
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/techrep...

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
Collins, Justin (Guest)
on 2005-12-17 07:23
(Received via mailing list)
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
Neil S. (Guest)
on 2005-12-17 08:08
(Received via mailing list)
Jakub H. wrote:
> 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

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 S. - removed_email_address@domain.invalid

'A republic, if you can keep it.' -- Benjamin Franklin
Hal F. (Guest)
on 2005-12-17 08:32
(Received via mailing list)
Neil S. 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
gabriele renzi (Guest)
on 2005-12-17 16:24
(Received via mailing list)
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.
>
> 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!).
Christian N. (Guest)
on 2005-12-17 18:00
(Received via mailing list)
gabriele renzi <removed_email_address@domain.invalid> 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).
gabriele renzi (Guest)
on 2005-12-17 19:09
(Received via mailing list)
Neil S. ha scritto:
> 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
jwesley (Guest)
on 2005-12-18 16:57
(Received via mailing list)
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.
unknown (Guest)
on 2005-12-18 19:04
(Received via mailing list)
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:

$ 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 W.

`
gabriele renzi (Guest)
on 2005-12-18 21:38
(Received via mailing list)
removed_email_address@domain.invalid 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 .
Pit C. (Guest)
on 2005-12-19 22:04
(Received via mailing list)
removed_email_address@domain.invalid schrieb:
> $ ulimit -s
> 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.

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
This topic is locked and can not be replied to.