Re: knowing when it is tail recursion or not?
- From: George Neuner <gneuner2@xxxxxxxxxxx>
- Date: Mon, 19 Jan 2009 17:49:23 -0500
On Mon, 19 Jan 2009 13:12:39 +0100, torbenm@xxxxxxxxxxxxxx (Torben
Ægidius Mogensen) wrote:
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.
Since the OP generalized and did not specify self recursion, most uses
in a non-trivial program would generate a warning.
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.
Identifying static mutual recursion cycles is not hard - even some
dynamic ones may be possible - but rewriting those cycles into loop
form can be quite difficult even if all the calls involved are in tail
position. Multiple entry points are not a problem, although as you
noted they can lead to slightly larger code - the real code explosion
happens with conditional cycles which may necessitate a customized
function for each possible branch.
George
.
- References:
- knowing when it is tail recursion or not?
- From: raould
- Re: knowing when it is tail recursion or not?
- From: George Neuner
- Re: knowing when it is tail recursion or not?
- From: Torben Ægidius Mogensen
- knowing when it is tail recursion or not?
- Prev by Date: Re: SML: find string in string
- Next by Date: sites on difference between OCaml, f#, Haskell
- Previous by thread: Re: knowing when it is tail recursion or not?
- Next by thread: Re: knowing when it is tail recursion or not?
- Index(es):
Relevant Pages
|
