Re: Proper Tail Recursive C++

William D Clinger <will@ccs.neu.edu> writes
>I think an example would help. If "properly tail recursive" has the
>meaning given to it by the functional programming community (e.g. the
>IEEE/ANSI Scheme standard), then a properly tail recursive C++
>compiler would have to translate the following program into machine
>code that terminates without overflowing the stack, heap, or any other
>storage segment, even on a tiny machine with much less than a megabyte
>of memory.


I've just tried this on Acorn's RISC OS C++ which is based on CFront +
Norcroft ARM C (which is good at optimizing TR).


Because of the "int A[1000]" in f() it fails to TR optimize the call to
g(A), and I can't immediately see how this could be optimised given that
each new invocation of f() needs a new A[]. Perhaps I'm missing
something.


For the record this compiler does generate nice tail call code for
functions which don't use any local storage. Here's what it does.


static void x1(int y)
{
      if (y > 0)
            x2(y-1);
}


static void x2(int y)
{
      if (y > 0)
            x1(y-1);
}


generates the following ARM code:


x1
                CMP a1,#0
                SUBGT a1,a1,#1
                BGT x2
                MOVS pc,lr


x2
                CMP a1,#0
                SUBGT a1,a1,#1
                BGT x1
                MOVS pc,lr


--
http://www.wonderworks.co.uk --> Free RISC OS software
Andy Armstrong, WonderWorks
--

Return to the comp.compilers page.
Search the comp.compilers archives again.