does CCS supports tail recursion?

Discussion in 'C Programming' started by shailesh, Aug 5, 2007.

  1. shailesh

    shailesh Guest

    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,
    shailesh, Aug 5, 2007
    #1
    1. Advertising

  2. shailesh

    Ian Collins Guest

    shailesh wrote:
    > 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.

    --
    Ian Collins.
    Ian Collins, Aug 5, 2007
    #2
    1. Advertising

  3. shailesh

    jacob navia Guest

    shailesh wrote:
    > 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.
    jacob navia, Aug 5, 2007
    #3
  4. shailesh

    shailesh Guest

    On Aug 5, 3:35 pm, jacob navia <> wrote:
    > shailesh wrote:
    > > 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.


    thanks Jacob,
    I could find out it using ur suggession.:)
    It does not support:(
    shailesh, Aug 5, 2007
    #4
  5. shailesh <> writes:
    > 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.

    --
    Keith Thompson (The_Other_Keith) <http://www.ghoti.net/~kst>
    San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
    "We must do something. This is something. Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"
    Keith Thompson, Aug 5, 2007
    #5
  6. shailesh

    Army1987 Guest

    On Sun, 05 Aug 2007 04:40:51 -0700, shailesh wrote:

    > On Aug 5, 3:35 pm, jacob navia <> wrote:
    >> shailesh wrote:
    >> > 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.

    >
    > 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>
    --
    Army1987 (Replace "NOSPAM" with "email")
    "Never attribute to malice that which can be adequately explained
    by stupidity." -- R. J. Hanlon (?)
    Army1987, Aug 5, 2007
    #6
  7. On Sun, 05 Aug 2007 11:34:52 -0700, Keith Thompson <> wrote:

    >shailesh <> writes:
    >> 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.


    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.
    Richard Harter, Aug 5, 2007
    #7
  8. In article <>,
    Richard Harter <> wrote:

    >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
    --
    "No one has the right to destroy another person's belief by
    demanding empirical evidence." -- Ann Landers
    Walter Roberson, Aug 5, 2007
    #8
  9. shailesh

    CBFalconer Guest

    Richard Harter wrote:
    > Keith Thompson <> wrote:
    >> shailesh <> writes:
    >>
    >>> 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
    >> tailrecursion 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.


    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.

    --
    "Vista is finally secure from hacking. No one is going to 'hack'
    the product activation and try and steal the o/s. Anyone smart
    enough to do so is also smart enough not to want to bother."



    --
    Posted via a free Usenet account from http://www.teranews.com
    CBFalconer, Aug 6, 2007
    #9
  10. On Sun, 05 Aug 2007 20:33:30 -0400, CBFalconer <>
    wrote:

    >Richard Harter wrote:
    >> Keith Thompson <> wrote:
    >>> shailesh <> writes:
    >>>
    >>>> 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
    >>> tailrecursion 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.

    >
    >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.
    Richard Harter, Aug 6, 2007
    #10
  11. shailesh

    CBFalconer Guest

    Richard Harter wrote:
    > CBFalconer <> wrote:
    >> Richard Harter wrote:

    >

    .... snip ...
    >>
    >>> 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.

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

    --
    "Vista is finally secure from hacking. No one is going to 'hack'
    the product activation and try and steal the o/s. Anyone smart
    enough to do so is also smart enough not to want to bother."


    --
    Posted via a free Usenet account from http://www.teranews.com
    CBFalconer, Aug 6, 2007
    #11
  12. In article <>,
    CBFalconer <> wrote:

    >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
    --
    "Consideration shall be given to the need for as many as 32 characters
    in some alphabets" - X3.4, 1963.
    Richard Tobin, Aug 6, 2007
    #12
  13. shailesh

    jacob navia Guest

    Richard Tobin wrote:
    > In article <>,
    > CBFalconer <> wrote:
    >
    >> 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


    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
    jacob navia, Aug 6, 2007
    #13
  14. shailesh

    Chris Dollin Guest

    jacob navia wrote:

    > Richard Tobin wrote:
    >> In article <>,
    >> CBFalconer <> wrote:
    >>
    >>> 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

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

    --
    Chris "tails can't speak, never mind /call/." Dollin

    Hewlett-Packard Limited registered no:
    registered office: Cain Road, Bracknell, Berks RG12 1HN 690597 England
    Chris Dollin, Aug 6, 2007
    #14
  15. In article <46b6e180$0$27376$>,
    jacob navia <> wrote:

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


    >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
    --
    "Consideration shall be given to the need for as many as 32 characters
    in some alphabets" - X3.4, 1963.
    Richard Tobin, Aug 6, 2007
    #15
  16. shailesh

    jacob navia Guest

    Chris Dollin wrote:
    > jacob navia wrote:
    >
    >> Richard Tobin wrote:
    >>> In article <>,
    >>> CBFalconer <> wrote:
    >>>
    >>>> 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

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


    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, Aug 6, 2007
    #16
  17. shailesh

    jacob navia Guest

    Richard Tobin wrote:
    > In article <46b6e180$0$27376$>,
    > jacob navia <> wrote:
    >
    >>> Not necessarily. For example, consider the case where the address
    >>> of a local variable is passed.

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


    Thanks, I did not see that possibility.

    jacob
    jacob navia, Aug 6, 2007
    #17
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Cyb
    Replies:
    12
    Views:
    665
    Eric Bohlman
    Dec 2, 2003
  2. Christopher T King

    Proper tail recursion

    Christopher T King, Jul 6, 2004, in forum: Python
    Replies:
    10
    Views:
    594
  3. Kay Schluehr

    New tail recursion decorator

    Kay Schluehr, May 10, 2006, in forum: Python
    Replies:
    19
    Views:
    523
    Michele Simionato
    May 15, 2006
  4. Patrick Li
    Replies:
    4
    Views:
    120
    Thomas B.
    Sep 4, 2008
  5. Terry Michaels

    Tail Call Optimization (Tail Recursion)

    Terry Michaels, Apr 18, 2011, in forum: Ruby
    Replies:
    16
    Views:
    314
    Robert Klemme
    Apr 20, 2011
Loading...

Share This Page