Re: knowing when it is tail recursion or not?

George Neuner <gneuner2@xxxxxxxxxxx> writes:

On Thu, 15 Jan 2009 16:06:25 -0800 (PST), raould <raould@xxxxxxxxx>
wrote:

why don't compilers tell us when we have recursion that is not going
to be tail-call-optimized-away into a loop?

Because then you'd get warnings on any use of recursion.

Local tail recursion is a special case that is easy to identify, but,
under the right circumstances, a mutual recursion that spans multiple
functions could potentially be turned into a loop. However the
analysis to identify such things is complex and if the loop path is
conditional it might require much code duplication to take advantage
of it.

That is not entirely true. You can locally identify tail calls and
non-tail calls, so you could conceivably give warnings with every
non-tail call, but you wouldn't know if it is part of a recursion.
However, mutually recursive functions are bound to be in the
compilation unit (unless you allow mutualy recursive compilation
units, which few languages do), so the analysis need not span more
than one compilation unit. Basically, make a local call graph and
mark all calls as tail or non-tail. If there is a loop in the graph
that contains a non-tail call, emit a warning.

However, any nontrivial program will contain non-tail recursion, so ou
should be able to annotate a call to mark that you know this is
non-tail recursion, and please don't warn me about this. This is,
however, rather tedious.

As for optimisation, tail self-recursion is obviously the easiest, but
any tail call can be optimised (even if it is not part of a
recursion), so even with only local detection of tail calls, you gain
a significant benefit.

However, the ideal is to find strongly connected components of tail
calls and turn each of these into a single function such that the tail
calls inside the component are all local jumps. If the component has
multiple entry points, this might be a bit complicated, but not too
bad. Tail calls into or out of the component would just get "normal"
tail-call optimisation.

Torben
.

Relevant Pages

  • Re: CAS, Lambda Calculus, Continuation and Functional Programming
    ... >>Recursion that's equivalent to loops can always be optimized back into ... and that tail calls are equivalent to loops. ... If a loop is formulated in a recursive way then ... >> that makes tail call elimination less attractive for compiler writers. ...
    (sci.math.symbolic)
  • Re: CL Implementations and Tail-Call Elimination
    ... where they use recursion to do iteration, and usually one of the first ... at least with the right set of declarations. ... straightforward way to declare that you need tail call merging. ... this misses a programming style where a state machine can be ...
    (comp.lang.lisp)
  • Re: better way to enumerate
    ... IMO LOOP is for blackbelts - not newbies ... A newbie will more readily understand this than tail recursion. ... Newbies should definitely not be taught obfuscated crap that can ...
    (comp.lang.lisp)
  • Re: knowing when it is tail recursion or not?
    ... Because then you'd get warnings on any use of recursion. ... Local tail recursion is a special case that is easy to identify, but, ... functions could potentially be turned into a loop. ...
    (comp.lang.functional)
  • Re: Recursive file listing function - which one is best?
    ... Proper recursion is one of the best things in Lisp/Scheme. ... Tail call elimination isn't mandated in Common Lisp. ... between CL and Scheme have been around the commercial/practical aspects ... the difference in "common practice" is encoded in the language. ...
    (comp.lang.lisp)