On 11/12/2018 5:52 AM, Rudi C wrote:
Does Racket support tail call elimination? I am not asking about just tail recursion, but any tail calls. If not, how about mutual tail recursion (where two functions keep tail callin each other, aka trampoline)?
Racket does tail call elimination [as will any Scheme]. Scheme refers to this as "proper" tail calling.
Eliminating any / every tail call in the program can be done by converting the program to Continuation-Passing Style (CPS). CPS code contains *only* tail calls - no ordinary call/returns. CPS doesn't use a stack ... or rather, in CPS the stack has only one valid frame - the current one.
AFAIAA, the Racket compiler does not do CPS conversion, but if you write code using *#lang web-server* then the program will be converted to CPS form before being compiled by Racket [though for reasons other than TCE].
Mutual recursion by tail calls can be turned into a loop, but in general the analysis to do it is very expensive *unless* the program is in CPS form. Remember that a recursive "loop" may span an arbitrary number of functions - so it can be arbitrarily hard to identify.
It used to be common for Scheme compilers to convert to CPS, but many don't do it any more because CPS doesn't play well with other optimization oriented representations - the biggies being Value Numbering and Static Single Assignment (SSA) form. And CPS isn't needed for simple TCE.
That said, one Scheme that (IIRC) can optimize mutual recursions is Stalin. George -- You received this message because you are subscribed to the Google Groups "Racket Users" group. To unsubscribe from this group and stop receiving emails from it, send an email to racket-users+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.
