Re: [Rd] Tail Call Elimination?

From: <luke-tierney_at_uiowa.edu>
Date: Mon, 18 Apr 2011 15:42:51 -0500

On Mon, 18 Apr 2011, Dominick Samperi wrote:

> On Mon, Apr 18, 2011 at 10:41 AM, <luke-tierney@uiowa.edu> wrote:
>> 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
>
> To what extent does the recently introduced byte-code compilation
> help here?

It can help quite a bit if the loop body is such that its evaluation is dominated by interpreter overhead. If the body involves calls to computationally expensive fucntons then compiling the loop itself may not help very much, but compiling those functions might.

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
>>
>> ______________________________________________
>> 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


______________________________________________ R-devel_at_r-project.org mailing list https://stat.ethz.ch/mailman/listinfo/r-devel

Received on Mon 18 Apr 2011 - 20:46:03 GMT

Archive maintained by Robert King, hosted by the discipline of statistics at the University of Newcastle, Australia.
Archive generated by hypermail 2.2.0, at Tue 19 Apr 2011 - 00:10:51 GMT.

Mailing list information is available at https://stat.ethz.ch/mailman/listinfo/r-devel. Please read the posting guide before posting to the list.

list of date sections of archive