does CCS supports tail recursion?

[shailesh]

hi all,

I m new joiny.
I read that most of the compiler auto detect tail recursion in
program. can any body tell me that is Code compoaser studio for TI dsp
supports?

rgds,

 

[Ian Collins]

hi all,

I m new joiny.
I read that most of the compiler auto detect tail recursion in
program. can any body tell me that is Code compoaser studio for TI dsp
supports?

Try one of their support forums, your question is OT here.

 

[jacob navia]

hi all,

I m new joiny.
I read that most of the compiler auto detect tail recursion in
program. can any body tell me that is Code compoaser studio for TI dsp
supports?

rgds,

I suppose that if you write:

int main(void)
{
return main();
}

You will have an infinite loop if it DOES support
tail recursion, a stack fault (trap) if it doesn't...

P.S. Maybe the processor you are using doesn't have any
memory protection. In that case use a printf statement
before the call to main to see if there is other kind of problem.

#include <stdio.h>
int main(void)
{
printf("ignore this\n");
return main();
}

An infinite loop will look different than a stack overflow with
this setup.

 

[shailesh]

I suppose that if you write:

int main(void)
{
return main();

}

You will have an infinite loop if it DOES support
tail recursion, a stack fault (trap) if it doesn't...

P.S. Maybe the processor you are using doesn't have any
memory protection. In that case use a printf statement
before the call to main to see if there is other kind of problem.

#include <stdio.h>
int main(void)
{
printf("ignore this\n");
return main();

}

An infinite loop will look different than a stack overflow with
this setup.

thanks Jacob,
I could find out it using ur suggession.
It does not support

 

[Keith Thompson]

I read that most of the compiler auto detect tail recursion in
program. can any body tell me that is Code compoaser studio for TI dsp
supports?

That's a question about your compiler, not about C, so you'd have
better luck asking in a support forum for your compiler. But the
answer might not be a simple yes or no. A compiler might detect tail
recursion only with certain command-line options to enable
optimizations. Consult your documentation.

 

[Army1987]

thanks Jacob,
I could find out it using ur suggession.
It does not support

<ot>
Maybe it does with different options. Consult its documentation.
</ot>

 

[Richard Harter]

That's a question about your compiler, not about C, so you'd have
better luck asking in a support forum for your compiler. But the
answer might not be a simple yes or no. A compiler might detect tail
recursion only with certain command-line options to enable
optimizations. Consult your documentation.

A possibly more OT question is "Under what circumstances is it feasible to
detect candidates for tail recursion optimization in C programs?" My
impression is that in general it is neither feasible nor even possible.

 

[Walter Roberson]

A possibly more OT question is "Under what circumstances is it feasible to
detect candidates for tail recursion optimization in C programs?" My
impression is that in general it is neither feasible nor even possible.

See the paper "Proper Tail Recursion in C",
http://www.complang.tuwien.ac.at/schani/diplarb.ps

In part it lists the tail recursions already implemented in gcc

 

[CBFalconer]

A possibly more OT question is "Under what circumstances is it
feasible to detect candidates for tail recursion optimization in
C programs?" My impression is that in general it is neither
feasible nor even possible.

Whenever the last action of the routine is to call itself with
revised parameters, this can obviously be replaced by a loop. This
is so simple that it can be done directly by the original code
writer.

 

[Richard Harter]

Whenever the last action of the routine is to call itself with
revised parameters, this can obviously be replaced by a loop. This
is so simple that it can be done directly by the original code
writer.

You should look at http://www.complang.tuwien.ac.at/schani/diplarb.ps
mentioned elsewhere in this thread. It's a nice paper. The fun begins
when foo calls bar which calls foo and so on. The issue at at hand is not
whether you can convert the simplest instance of tail recursion into a loop
but whether the design of C makes it impossible to do proper tail recursion
generally.

 

[CBFalconer]

.... snip ...

You should look at http://www.complang.tuwien.ac.at/schani/diplarb.ps
mentioned elsewhere in this thread. It's a nice paper. The fun
begins when foo calls bar which calls foo and so on. The issue
at at hand is not whether you can convert the simplest instance of
tail recursion into a loop but whether the design of C makes it
impossible to do proper tail recursion generally.

Conceded. However, my point is that the majority of common things
can be handled easily by the writer. This is probably enough to
gain most of the benefits, without any risks.

 

[Richard Tobin]

Whenever the last action of the routine is to call itself with
revised parameters, this can obviously be replaced by a loop.

Not necessarily. For example, consider the case where the address
of a local variable is passed.

And of course self-call is just the simplest example of tail call.

-- Richard

 

[jacob navia]

Not necessarily. For example, consider the case where the address
of a local variable is passed.

And of course self-call is just the simplest example of tail call.

-- Richard

Why would it matter?

suppose that as the last action you make
return sameproc(2,3,&local);

Since the value of "local" can't ever be used after
the call returns, it doesn't matter at all.

jacob

 

[Chris Dollin]

Why would it matter?

suppose that as the last action you make
return sameproc(2,3,&local);

Since the value of "local" can't ever be used after
the call returns, it doesn't matter at all.

I'm afraid you are mistaken, since the address of `local` can be used
/inside the call of `sameproc`/. Hence it's important that `local`
continue to exist, hence (in the usual implementation) that the
stack frame it's in continues to exist, hence you can't do the
straightforward stack-frame elimination part of tail-call optimisation.

Consider this horrible sketch of an example:

Answer example( Args x, struct Ex *uplink )
{
if (terminationCondition( x ))
{
return dependsOnUplinkChainAndX( x, uplink );
}
else
{
struct Ex another;
another.uplink = uplink;
another.stuff = hackeryOn( x );
return example( shrink( x ), &another );
}
}

The recursive call can't be TCOd; the number of `another` elements
needed depends on how much `x` needs to be shrunk before meeting
the termination condition, so you can't junk the stack frames.

 

[Richard Tobin]

Not necessarily. For example, consider the case where the address
of a local variable is passed.

[/QUOTE]

Why would it matter?

suppose that as the last action you make
return sameproc(2,3,&local);

Since the value of "local" can't ever be used after
the call returns, it doesn't matter at all.

The second activation of sameproc needs to have its own version of
"local" which is distinct from the one in the first activation.

For example, you could build a linked list out of stack-allocated cons
cells (though of course you couldn't return it). More realistically,
you might have local structures representing some kind of environment
that contain a pointer to the passed-in parent environment.

-- Richard

 

[jacob navia]

I'm afraid you are mistaken, since the address of `local` can be used
/inside the call of `sameproc`/. Hence it's important that `local`
continue to exist, hence (in the usual implementation) that the
stack frame it's in continues to exist, hence you can't do the
straightforward stack-frame elimination part of tail-call optimisation.

Consider this horrible sketch of an example:

Answer example( Args x, struct Ex *uplink )
{
if (terminationCondition( x ))
{
return dependsOnUplinkChainAndX( x, uplink );
}
else
{
struct Ex another;
another.uplink = uplink;
another.stuff = hackeryOn( x );
return example( shrink( x ), &another );
}
}

The recursive call can't be TCOd; the number of `another` elements
needed depends on how much `x` needs to be shrunk before meeting
the termination condition, so you can't junk the stack frames.

Thanks, I see now. Will remember next time I try to implement
that optimization. I have considered doing it, but never got into
that.

 

[jacob navia]

Why would it matter?

suppose that as the last action you make
return sameproc(2,3,&local);

Since the value of "local" can't ever be used after
the call returns, it doesn't matter at all.

The second activation of sameproc needs to have its own version of
"local" which is distinct from the one in the first activation.

For example, you could build a linked list out of stack-allocated cons
cells (though of course you couldn't return it). More realistically,
you might have local structures representing some kind of environment
that contain a pointer to the passed-in parent environment.

-- Richard[/QUOTE]

Thanks, I did not see that possibility.

jacob