R devel - Apr 2011 - Tail Call Elimination?

Dear R-programmers,

I am trying to program a Newton-Raphson in R (yes, i will try GSL, not right
now), and it would be a real boon if R had tail call elimination, so that a
recursive program has a guarantee not to fail due to stack overflows, given
how slow loops in R are. I did look at the documentation, but could not find
a reason for it.

Regards,
Mohit Dayal
Researcher
Applied Statistics & Computing Lab
ISB

	[[alternative HTML version deleted]]

The Scheme-inspired function callCC may support this to some extent, but
the R man page on this function is very sketchy. Examples have been
posted by the author of callCC, so you might want to search the archives.

Dominick

On Sun, Apr 17, 2011 at 1:34 AM, Mohit Dayal <ken.sensei at gmail.com>
wrote:
> Dear R-programmers,
>
> I am trying to program a Newton-Raphson in R (yes, i will try GSL, not
right
> now), and it would be a real boon if R had tail call elimination, so that a
> recursive program has a guarantee not to fail due to stack overflows, given
> how slow loops in R are. I did look at the documentation, but could not
find
> a reason for it.
>
> Regards,
> Mohit Dayal
> Researcher
> Applied Statistics & Computing Lab
> ISB
>
> ? ? ? ?[[alternative HTML version deleted]]
>
> ______________________________________________
> R-devel at r-project.org mailing list
> https://stat.ethz.ch/mailman/listinfo/r-devel
>

The premise of your post is false: contrary to popular belief, R's
looping constructs are not particularly inefficient. Slowness of loops
relative to vectorized code comes from the cost of interpreting the
body of the loop.  That exact same interpreter would be used to
interpret the bodies of functions used to express loops using
recursion, so it is not reasonable to expect this to improve
performance. In fact, due to the inefficiency of the current function
call mechanism in R, quite the opposite is true.

As to the question: tail call optimization cannot be applied in R, at
least not in a simple way, because the semantics of R provide access
to the call stack via the sys.xyz functions and parent.frame and such.
It might be possible to make some semantic changes, such as only
guaranteeing access to the immediate caller, but there isn't much
point unless/until the performance of the function calling mechanism is
improved.

Best,

luke

On Sun, 17 Apr 2011, Mohit Dayal wrote:
> Dear R-programmers,
>
> I am trying to program a Newton-Raphson in R (yes, i will try GSL, not
right
> now), and it would be a real boon if R had tail call elimination, so that a
> recursive program has a guarantee not to fail due to stack overflows, given
> how slow loops in R are. I did look at the documentation, but could not
find
> a reason for it.
>
> Regards,
> Mohit Dayal
> Researcher
> Applied Statistics & Computing Lab
> ISB
>
> 	[[alternative HTML version deleted]]
>
> ______________________________________________
> R-devel at r-project.org mailing list
> https://stat.ethz.ch/mailman/listinfo/r-devel
>
-- 
Luke Tierney
Statistics and Actuarial Science
Ralph E. Wareham Professor of Mathematical Sciences
University of Iowa                  Phone:             319-335-3386
Department of Statistics and        Fax:               319-335-3017
    Actuarial Science
241 Schaeffer Hall                  email:      luke at stat.uiowa.edu
Iowa City, IA 52242                 WWW:  http://www.stat.uiowa.edu